The
Mathematics of Strategy
by
Erica Klarreich
Science Writer
|
What does it mean to behave rationally? This question sounds like a problem for philosophers. Yet mathematicians also have something to say about it. In the last few decades, game theory—the mathematical study of strategies and decision-making—has shed crucial light on the nature of rational behavior.
In 1950,
a young Princeton mathematics
graduate student named John Nash published a two-page note in PNAS
and his idea, the Nash equilibrium, has become the cornerstone of game
theory (1). The Nash equilibrium abstracts the
way we reason about strategies in a competitive situation: it codifies "I
think he will do X because he thinks I will do Y, so I should do Z...."
The Nash equilibrium concept has become a benchmark by which economists
and other scientists measure both rational behavior and the extent to
which humans depart from pure rationality. Over the years, this concept
has illuminated questions in economics, psychology, and even biology.
In 1994, it earned Nash the Nobel prize in economics.
"It was an incredibly short but incredibly influential paper," says Robert Weber, an economist at Northwestern University's Kellogg School of Management in Evanston, IL, who has applied game theory to auctions and other economic interactions.
Early
Game Theory
About a century ago, mathematicians became interested in studying strategic behavior through formal mathematical structures. Their interest was sparked by games such as chess and poker, but soon extended to more general situations in which players—whether people, nations, animal species, or other entities—have conflicting interests and various strategies to further those interests.
|
In 1928, Hungarian mathematician John von Neumann, then a lecturer at the University of Berlin, launched the field of game theory with a study of two-player "zero-sum" games, in which the players have completely opposite interests—chess, for instance. Von Neumann showed that in such games, there is a notion of mistake-free play (2). That is, there is some particular outcome that the players can always force, and this is the best outcome each player can hope for if both are playing rationally. For example, in tic-tac-toe it's always possible for the players to force a tie. Neither player can reasonably expect to win unless the other player makes a strategic error.
In 1944, von Neumann and economist Oscar Morgenstern, at the Institute for Advanced Study in Princeton and Princeton University, respectively, wrote the landmark book The Theory of Games and Economic Behavior (3), in which they argued that game theory had the potential to do for economics what calculus had done for physics. Their book, together with von Neumann's flashy personality, transformed game theory into the hot new subject for Princeton's math graduate students.
Although von Neumann's theory was useful in some contexts, such as military planning, in most real-world interactions the players are not pure rivals: rather, they have a mix of conflicting and common interests. For instance, in labor negotiations, both labor and management wish to avoid a strike. Two competing companies will both suffer if they enter into a price war. And, at least ideally, two people who marry will both gain in happiness.
Consequently, a new idea was needed to deal with games that involve a mix of cooperation and competition. That idea came from a brash, self-confident student who had come to Princeton with a one-line letter of recommendation from his Carnegie Institute of Technology professor, R. J. Duffin: "This man is a genius."
A
New Paradigm
|
While an undergraduate at Carnegie Tech in Pittsburgh (now known as Carnegie Mellon University), John Nash had grown interested in the mathematics of bargaining and, when he came to Princeton in 1948, he became swept up in the enthusiasm for game theory. At the time, von Neumann was trying to tackle non-zero-sum games by looking for cooperative solutions, in which players form coalitions. This approach, however, gave rise to complicated and intractable mathematics.
Nash believed that the right approach was to focus on individual decision-making, because choosing to join a coalition can simply be considered as one of the potential strategies at a player's disposal. He realized that there is a way to generalize von Neumann's idea of mistake-free play to games that are not zero-sum or have more than two players.
For such a game, Nash defined an equilibrium to be a set of strategies, one for each player, such that no player would benefit from unilaterally changing his strategy while the other players stick to their equilibrium strategies. Using sophisticated mathematical techniques, Nash proved that in a wide variety of games, an equilibrium always exists.
When Nash told von Neumann of his result, von Neumann dismissed it as trivial. Nash's fellow student and current Academy Member David Gale, however, was impressed by Nash's work and urged him to "plant a flag" by publishing his proof as quickly as possible in PNAS. Despite von Neumann's discouragement, Nash expanded the ideas in the PNAS paper into his doctoral dissertation.
The Nash equilibrium concept does not necessarily predict how people will behave in the real world. Rather, it provides a measure for how purely rational people might behave.
"The Nash equilibrium tells us what we might expect to see in a world where no one does anything wrong," Weber says.
To get a sense of how the Nash equilibrium works, consider the following scenario. Twenty people are dining at a restaurant that offers a luxurious $20 meal and a simpler $10 meal. The diners have agreed that the group will split the bill evenly. Suppose each person, if he had to pay only his own bill, would prefer the $10 meal. Despite these preferences, it is not a Nash equilibrium for everyone to choose the cheap meal, since for each individual, switching to the expensive meal will cost him only 50 cents more. The only Nash equilibrium is for all the players to choose the $20 meal. Unfortunately, the decisions of each member of the group result in the least desirable outcome for the group as a whole.
A similar principle is at work in the famous Prisoner's dilemma game, devised by mathematicians shortly after Nash announced his equilibrium result (4). In this game, two prisoners are each induced to incriminate the other despite the fact that they would both do better if they kept silent. Each acts to further his own interests, but the outcome is in the interests of neither.
The
Nash equilibrium gave researchers a new paradigm for economic interactions.
Traditional economics, dating back to 18th century economist Adam Smith,
views players as interacting not with each other but with a vast impersonal
market, in which each individual has only marginal impact. This assumption
works well for analyzing some situations, such as price determination
in large markets. However, it is less effective, for example, in transactions
involving a small number of players, such as auctions, or situations
where some of the players have private information.
By focusing on the impact of the individual, Nash offered a way to study how incentives will influence behavior in any social institution, not just markets. What's more, games such as the Prisoner's dilemma countered Smith's notion that if players pursue their own interests, an invisible hand will drive society toward a mutually beneficial outcome.
"Nash's theory of noncooperative games should now be recognized as one of the outstanding intellectual advances of the twentieth century," writes Roger Myerson, an economist and game theorist at the University of Chicago. "The formulation of Nash equilibrium has had a fundamental and pervasive impact in economics and the social sciences which is comparable to that of the discovery of the DNA double helix in the biological sciences." (5)
A
Classic Figure
|
At the time he wrote his PNAS paper, Nash had no idea that the equilibrium concept would eventually capture him a Nobel prize. "I knew it was good work, but I couldn't be sure of people's reactions and the ultimate consequences," he says.
Nash felt that he had to make his mark in other directions. After graduating from Princeton, he obtained a faculty position at MIT in 1952, where he did outstanding work in several fields of pure mathematics, such as his studies of when Riemannian manifolds—generalizations of geometric shapes—can fit into ordinary space (6). His work at MIT put him in contention for a Fields Medal, the highest honor in mathematics.
In 1958, Fortune magazine featured Nash as one of the brightest young stars of mathematics. But only a few months later, even as his mathematical career appeared to be approaching it's highest pinnacle, Nash began showing signs of what quickly became full-blown paranoid schizophrenia. In 1959, his wife Alicia reluctantly committed him to a mental institution, and he lost his job at MIT.
Over the following two decades, Nash was in and out of mental hospitals, virtually incapacitated by his disease. Many younger mathematicians and economists, hearing nothing of him, assumed he was dead.
"Nash's writings provided a valuable intellectual guide and a rich source of research ideas for many of us who learned game theory in that period, but John Nash himself seemed a classic figure as removed from us as [earlier economic thinkers] Cournot and Xenophon," Myerson writes. (5)
In 1970, Nash moved back to Princeton, where he took to shuffling through the halls of the mathematics building, occasionally scribbling enigmatic numerological messages on the walls. Students referred to him as the "Phantom of Fine Hall."
Gradually, however, Nash's mental condition began to improve. Schizophrenia rarely disappears completely, but by the 1990s Nash appeared to have made a remarkable recovery, and he had turned once again to mathematical research.
Private
Information
|
"Everyone at least knows their own interests better than other people do," Weber says. "The role of private information is important throughout economics."
Over the last 30 years, Nash and Harsanyi's work has led to an explosion of the use of game theory in economics. Economists have employed equilibrium analysis to show, for instance, that rational negotiators must sometimes fail to reach an agreement, even when a mutually advantageous bargain exists. They have used Nash's equilibrium concept to clarify the role played by reputation in long-term relationships, and the way that market prices reflect the private information held by market participants. They have analyzed strategic behavior by voters to understand better which election methods have the most desirable equilibrium properties.
In 1994, economists applied insights from game theory to help the Federal Communications Commission design its first-ever auction of electromagnetic spectrum licenses. In an auction in December of that year, the FCC took in $7 billion, in what the New York Times trumpeted as the "greatest auction ever."
The same year, the Royal Swedish Academy of Sciences awarded Nash the Nobel Prize for economics, together with Harsanyi and Reinhard Selten, a professor emeritus at the University of Bonn in Germany, "for their pioneering analysis of equilibria in the theory of noncooperative games."
Many
directions
The Nash equilibrium concept continues to give rise to fruitful research programs in a wide range of fields. For instance, there is the issue of what to expect in games that have more than one Nash equilibrium. Thomas Schelling of the University of Maryland at College Park and others have investigated how societal influences can focus the players on a particular Nash equilibrium.
By giving researchers a benchmark for rational behavior, the Nash equilibrium has also become a tool for investigating just how rational people really are.
"In some settings, people routinely deviate from the kind of behavior the Nash equilibrium predicts," Weber says. "These deviations have led to the discovery of pervasive psychological phenomena that pull people away from rational behavior."
|
Many researchers are now investigating the ways in which human behavior defies rationality, including Daniel Kahneman of Princeton University, who earned an economics Nobel prize in 2002 for his experiments showing "how human decisions may systematically depart from those predicted by standard economic theory." For instance, in 1981 Kahneman and his collaborator, the late Amos Tversky, asked subjects to consider a scenario in which they had two possible strategies for preventing the spread of a disease in a population of 600 people (8). Strategy A would save the lives of exactly 200 people; Strategy B had a 1/3 chance of saving everyone and a 2/3 chance of saving no one. Although these two strategies have the same average outcome, 72% of the subjects preferred the less-risky Strategy A. However, in a second experiment in which Kahneman and Tversky worded Strategy A differently, saying that it would kill exactly 400 people, only 22% chose it. Kahneman and Tversky found that subjects shun rational behavior in systematic ways when faced with the prospect of risk. They avoid risk when offered the chance of a sure gain, even if the risky move has a higher expected payoff than the sure one. On the other hand, when faced with the prospect of a sure loss, they will do the exact opposite: they will court risk, even if it is likely to leave them even worse off than the sure move.
The Nash equilibrium concept has also shed light on animal behavior. In the 1970s, biologists John Maynard Smith, of the University of Sussex in England, and the late George Price, then of the Galton Laboratories in London, used game theory to study ritual courtship battles within species (9). They modeled these conflicts by a game in which each player can choose to be either a hawk, who escalates the conflict, or a dove, who backs down if his opponent starts playing rough. The researchers found that in equilibrium, the population will consist of a mix of hawks and doves; the percentage of each type depends on how capable of hurting or killing each other the particular species is. Maynard Smith and Price also showed that if type is inherited from one generation to the next, the population should converge to its equilibrium distribution of doves and hawks.
"This was something that had been found decades ago by students of animal behavior, but they couldn't really explain it," says Karl Sigmund, a mathematical biologist at the University of Vienna in Austria. "Since that first classical example there have been hundreds of other applications of game theory to the behavior of animals, and even bacteria and plants. Journals on animal behavior are now filled with game theoretic ideas."
Nash himself has now resumed research in game theory. He is trying to apply the equilibrium concept to the cooperative games von Neumann studied, in which players can form coalitions of varying strengths.
"It's very difficult to model human cooperation, because it is a very complex thing," Nash says. "But maybe there's some way to simplify it. That's what I'm looking for."
The influence of a scientific paper can usually be measured by counting how many times other scientific papers have cited it. In the case of Nash's 1950 PNAS paper, however, that measure would be useless, observes economist Avinash Dixit of Princeton University. "No one cites Nash's paper any more, for the simple reason that 'Nash equilibrium' has become a word in the language," he says. "That's the ultimate test of success."
References
1.
Nash, J. F. (1950) Proc. Natl. Acad. Sci. USA 36, 48-49. |Article|
2. von Neumann, J. (1928) Math. Ann. 100,
295-320.
3. von Neumann, J., & Morgenstern, O. (1944) Theory
of Games and Economic Behavior (Princeton University Press, Princeton
NJ).
4. Tucker, A. (1950) unpublished memo.
5. Myerson, R. (1999) J. Econ. Lit. 36, 1067-1082.
|Article|
6.
Nash, J. (1956) Ann. Math. 63, 20-63.
7. Harsanyi, J. C. (1967-8) Manage. Sci. 14,
159-182, 320-334, and 486-502.
8. Tversky, A. & Kahneman, D. (1981) Science 211,
453-458.
9. Maynard Smith, J. & Price, G. A. (1973) Nature 246,
15-18.