The Nash Equilibrium: A Perspective

Charles A. Holt and Alvin E. Roth1 University of Virginia and Harvard University Abstract In 1950, John Nash contributed a remarkable one-page PNAS article that defined and characterized a notion of equilibrium for n-person games. This notion, now called the "Nash Equilibrium," has been widely applied and adapted in economics and other behavioral sciences. Indeed, game theory, with the Nash equilibrium as its centerpice, is becoming the most prominent unifying theory of social science. In this perspective, we summarize the historical context and subsequent impact of Nash's contribution. In a brief 1950 communication to the PNAS (1), John Forbes Nash formulated the notion of equilibrium that bears his name and that has revolutionized economics and parts of other sciences. Nash, a young mathematics graduate student at Princeton, was a part of the Camelot of game theory centered around von Neumann and Morgenstern. They had written Theory of Games and Economic Behavior (2) to expand economic analysis to allow economists to model the rules of the game that influence particular environments, and to extend the scope of economic theory to include strategic, smallgroup situations in which each person must try to anticipate others actions. von Neumann and Morgensterns definition of equilibrium for noncooperative games was largely confined to the special case of two-person zero-sum games in which one persons gain is anothers loss, so the payoffs always sum to zero (3). Nash proposed a notion of equilibrium that applied to a much wider class of games without restrictions on the payoff structure or number of players (1,4,5,). von Neumanns reaction was polite but not enthusiastic.2 Nevertheless, the Nash equilibrium, as it has become known, helped produce a revolution in the use of game theory in economics, and it was the contribution for which Nash was cited by the Nobel Prize committee at the time of his award, 44 years later. Equilibrium Points in N-Person Games The first part of the 1950 PNAS paper introduces the model of a game with n participants or players, who must each select a course of action or strategy: One may define a concept of an n-person game in which each player has a finite set of pure strategies and in which a definite set of payments to the n players corresponds to each n-tuple of pure strategies, one strategy being taken for each player... (1, p. 48) The notion of a strategy is quite general, and it includes mixed strategies that are probability distributions over decisions, e.g. an inspector who audits on a random basis,
1 2

This work was funded in part by a National Science Foundation Infrastructure Grant (SES 0094800). In a personal communication with one of the authors, Nash notes that von Neumann was a European gentleman, but was not an enthusiastic supporter of Nashs approach.

or a poker player who sometimes bluffs. Another interpretation of a mixed-strategy equilibrium is that of a population of randomly-matched individuals in the role of each player of the game, some proportion of whom make each of a number of available choices. The idea of the Nash equilibrium is that a set of strategies, one for each player, would be stable if nobody has a unilateral incentive to deviate from their own strategy: Any n-tuple of strategies, one for each player, may be regarded as a point in the product space obtained by multiplying the n strategy spaces of the players. One such n-tuple counters another if the strategy of each player in the countering n-tuple yields the highest obtainable expectation for its player against the n - 1 strategies of the other other players in the countered n-tuple. A self-countering n-tuple is called an equilibrium point. (1,.49) That is, a Nash equilibrium is a set of strategies, one for each of the n players of a game, that has the property that each players choice is his best response to the choices of the n1 other players. It would survive an announcement test: if all players announced their strategies simultaneously, nobody would want to reconsider. The Nash equilibrium has found many uses in economics, partly because it can be usefully interpreted in a number of ways. When the goal is to give advice to all the players in a game (i.e. to advise each player what strategy to choose), any advice that was not an equilibrium would have the unsettling property that there would always be some player for whom the advice was bad, in the sense that, if all the other players followed the parts of the advice directed to them, it would be better for some player to do differently than he was advised. If the advice is an equilibrium, however, this wont be the case, because the advice to each player is the best response to the advice given to the other players. This point of view is sometimes also used to derive predictions of what players would do, if they can be approximated as perfectly rational players who can all make whatever calculations are necessary, and so are in the position of deriving the relevant advice for themselves. When the goal is prediction rather than prescription, a Nash equilibrium can also be interpreted as a potential stable point of a dynamic adjustment process in which individuals adjust their behavior to that of the other players in the game, searching for strategy choices that will give them better results. This point of view has been productive in biology also, when mixed strategies are interpreted as the proportion of a population choosing each of a set of strategies, game payoffs are interpreted as the change in inclusive fitness that results from the play of the game, and the dynamics are interpreted as population dynamics (6,7) No presumptions of rationality are made in this case of course, but only of simple, self- interested dynamics. This evolutionary approach has also been attractive to economists (e.g. 8). A third interpretation is that a Nash equilibrium is a self-enforcing agreement, that is, an (implicit or explicit) agreement that, once reached by the players, does not need any external means of enforcement, since it is in the self interest of each player to follow the

agreement if the others do. Viewed in this way, Nash equilibrium has helped to clarify a distinction sometimes still made between cooperative and non-cooperative games, with cooperative games being those in which agreements can be enforced (e.g. through the courts), and non-cooperative games being those in which no such enforcement mechanism exists, so that only equilibrium agreements are sustainable. One trend in modern game theory, often referred to as the Nash program, is to erase this distinction by including any relevant enforcement mechanisms in the model of the game, so that all games can be modeled as noncooperative. Nash took initial steps in this direction in his early and influential model of bargaining as a cooperative game (9), and then as a noncooperative game (10). Nashs 1950 PNAS paper not only formulated the definition of equilibrium, but announced the proof of existence that he obtained using Kakutanis (11) fixed point theorem. This technique of proof subsequently became standard in economics, e.g. the notion of a competitive equilibrium as a vector of anticipated prices resulting in production and consumption decisions that generate the same vector of prices. In a personal communication to one of the authors, Nash remarked: I know that Kakutanis generalized fixed point theorem was actually inspired to improve upon some arguments made by von Neumann in an economic context in the 30s. Nash shared the 1994 Nobel prize with John Harsanyi and Reinhard Selten. Harsanyi was cited for extending the Nash equilibrium to the larger class of games called games of incomplete information, in which players need not be assumed to know other players preferences and feasible choices (12). Selten was cited for his work on equilibrium refinements, which takes the point of view that the requirements of Nash equilibrium are necessary conditions for advice to perfectly rational players, but are not sufficient conditions, and there may be superfluous equilibria that can be removed from consideration by appropriate refinements that focus attention on a non-empty subset of Nash equilibria (13,14). Nash equilibrium has been extended, refined, and generalized in other directions as well. One noteworthy generalization of mixed strategy equilibrium is correlated equlibrium (15) which considers not only independently randomized strategies for each player, but also jointly randomized strategies that may allow coordination among groups of players. Equilibrium and Social Dilemmas The Nash equilibrium is useful not just when it is itself an accurate predictor of how people will behave in a game, but also when it is not, since then it identifies situations in which there is a tension between individual incentives and other motivations. A class of problems that have received a good deal of study from this point of view is the family of social dilemmas in which there is a socially desirable action that is not a Nash equilibrium. Indeed, one of the first responses to Nashs definition of equilibrium gave rise to one of the best known models in the social sciences, the Prisoners Dilemma. This model began life as a simple experiment conducted in January 1950 at the Rand Corporation by mathematicians Melvin Dresher and Merrill Flood, to demonstrate that

the Nash equilibrium would not necessarily be a good predictor of behavior. Each of the two players in that game had to choose one of two decisions, which for expositional purposes, we will call cooperate or defect. The game specifies the payoffs for each player for each of the four possible outcomes: (cooperate, cooperate), (cooperate, defect), (defect, cooperate) and (defect, defect). The payoffs used were such that each players best counter to either of the others choices was to defect, but both players would earn more if they both cooperated than if they both chose their equilibrium decision and defected. Nashs thesis advisor, Albert Tucker, was preparing a talk on recent developments in game theory to be given to the Stanford Psychology Department when he saw the Dresher and Flood payoff numbers on a blackboard at the RAND Corporation. Tucker then devised the famous story of the dilemma faced by two prisoners who are each given incentives by the prosecutor to confess, even though both would be better off if neither confesses than if they both do.(16,17) In the initial experiment (18) and in innumerable experiments that followed, players often succeed, at least to some degree, in cooperating with one another and avoiding equilibrium play.(19) Social scientists across many disciplines have found prisoners dilemmas helpful in thinking about phenomena ranging from ecological degradation (20) to arms races. What the Nash equilibrium makes clear, even in a game like the prisoners dilemma in which it may not be an accurate point predictor, is that the cooperative outcome, since it is not an equilibrium, is going to be unstable in ways that can make cooperation difficult to maintain. This observation has been confirmed in many subsequent experiments on this and more general social dilemmas, (see e.g. 21-23). You can put yourself into a social dilemma game by going to the link: http://veconlab.econ.virginia.edu/tddemo.htm and playing against decisions retrieved from a database. This Travelers Dilemma game is somewhat more complex than a prisoners dilemma, in that the best decision is not independent of your beliefs about what strategy might be selected by the other player (24). Design of Markets and Social Institutions One of the ways in which research on dilemmas and other problems of collective action has proceeded is to look for the social institutions that have been invented to change games from prisoners dilemmas to games in which cooperation is sustainable as an equilibrium; see e.g. Elinor Ostroms (1998) presidential address to the American Political Science Association (25). For example, just as firms selling similar products may undercut each others price until price is driven down to cost, it is possible for a series of actions and reactions to force players in a game into a situation that is relatively bad for all concerned, which provides strong incentives for restrictions on unilateral actions. This kind of unraveling is encountered in some labor markets in which employers may try to gain an advantage by making early offers. In the market for federal appellate court clerks, for example, positions began to be arranged earlier and earlier, as some judges tried to hire clerks just before their competitors. This continued until offers (for jobs that would begin only upon graduation from law school) were being made to

law students two years in advance, only on the basis of first-year law school grades (see 26). This situation was widely viewed as unsatisfactory, since it forced both judges and law students to make decisions far in advance, on the basis of too little information. The most recent of many attempts to reform this market took the form of a year-long moratorium on the hiring of clerks by appellate judges, which ended the day after Labor Day 2003, with only third year law students to be hired. It is still too early to know whether this relatively mild intervention will finally solve the unraveling of the law clerk market. An alternative solution to this prisoners dilemma problem of timing in such markets is to arrange an organized clearinghouse in which both employers and job candidates participate. Such clearinghouses arose, for example, as a result of situations in which medical students were being hired well over a year before graduation; this happened in the U.S. in the 1940s and in the U.K. in the 1960s. Today, graduates of American medical schools (and others applying for residencies at American hospitals) submit rank order lists of preferred positions to a clearinghouse called the National Resident Matching Program (NRMP). Roth (27, 28) studies these U.S. and U.K. matching markets. It turns out that one important factor in whether such a labor market clearinghouse succeeds or fails is whether the clearinghouse is designed so that it is a Nash equilibrium for applicants and employers to participate in a way that produces a matching of workers to jobs that is stable in the sense that no employer and applicant who are not matched to one another would both prefer to be (29, 30). Participation in such a clearinghouse is even more straightforward if the clearinghouse is constructed so that it is a Nash equilibrium for applicants to simply put down their true preferences, regardless of how likely they think they are to receive each of the jobs for which they have applied, or how other applicants are ranking those jobs. For matching markets like these entry level labor markets, this kind of equilibrium is possible for an appropriately designed clearinghouse. Thus the current version of the NRMP algorithm, designed by Roth and Peranson (31), has the property that applicants can confidently be advised that it is in their best interest to submit rank order lists of residencies that correspond to their true preferences. The fact that game theorists have started to play a role in designing such clearinghouses, and other markets, is an indication of how game theory has grown from a conceptual to a practical tool. Auctions are another kind of market in which it is becoming increasingly common for game theorists to be asked for design advice (see e.g. 32-33). And the economic theory of auctions (for which a Nobel prize was given to William Vickery in 1996, in large part for his seminal 1961 paper(34)), is a perfect example of how game theory and Nash equilibrium have changed economics. Before game theory, economists often analyzed markets simply in terms of the supply and demand of the goods to be sold, with no way to discuss the rules of the game that make one kind of auction different from another, or make auctions different from other kinds of markets (such as stock markets, or shopping malls). Today, that discussion is most often carried forward by analyzing the Nash equilibria of the auction rules.

Experimental Economics It is worth mentioning that Nash both commented on and participated in early experiments in economics (see 35). It was a natural progression to move from a fascination with mathematical models of strategic behavior to the observation of decisions made by people who are playing for real money payoffs under controlled conditions in the laboratory. Indeed, as game theory started its move to the forefront of economic theory, it generated scores of testable predictions, and helped lay the groundwork for the introduction of experimental methods into economics (36,37). The increasing use of experimental methods in economics and the growing interaction between economics and psychology was itself recognized by the 2002 Economics Nobel prize that was awarded to a psychologist, Daniel Kahneman (see e.g. 38), and an economist, Vernon Smith (see e.g. 39). Before Smiths experiments, it was widely believed that the competitive predictions of supply/demand intersections required very large numbers of well-informed traders. Smith showed that competitive, efficient outcomes could be observed with surprisingly small numbers of traders, each with no direct knowledge of the others costs or values. An important developing area of game theory is to explain these and other experimental results in the context of well-specified dynamic models of the interaction of strategic traders. Another emerging connection between game theory and experimentation is the increased use of experimental methods in teaching. A well designed classroom experiment shows students that the seemingly abstract equilibrium models can have surprising predictive power. The internet makes it much easier to run complex games with large groups of students. For example, over 30 different types of games, auctions, and markets can be set up and run from a site: http://veconlab.econ.virginia.edu/admin.htm that also provides sample data displays from classroom experiments. Most of the data displays and dynamically generated data graphs have options for hiding the relevant Nash predictions when the results are being discussed, and then showing the Nash predictions subsequently. . Modeling Learning and Stochastic Equilibrium Experimentation has helped move game theorists to focus on approaches that are able to predict how people actually behave when the perfect foresight and perfect rationality assumptions of classical game theory are not satisfied. The experimental literature is full of examples both of games in which observed behavior quickly converges to equilibrium behavior, and games in which equilibrium is a persistently poor predictor. This has helped to reinforce the trend, already apparent in the theoretical literature, to extend the static, often deterministic formulation of equilibrium, and consider dynamic and stochastic models. Experiments make clear that players often do not conform to equilibrium behavior when they first experience a game, even if it is a game in which behavior quickly converges to equilibrium as the players gain experience. One reaction to this has been to develop

models of learning that converge to equilibrium in the limit, starting from nonequilibrium behavior (see e.g. 40,41). Another has been the beginning of attempts to develop models of learning that can predict observed behavior in simple experimental games (see e.g. 42). In particular, learning models are useful for explaining patterns of adjustment, e.g. whether prices converge from above or below, as well as the ultimate steady-state distributions (e.g. 43,44). Some games are only played once, e.g. the exact strategic environments in many military, legal, and political conflicts are unique to the particular time and place. In that case, there is no history that can be used to form precise predictions about others decisions. Therefore learning must occur by introspection, or thinking about what the other person might do, what they think you might do, etc. Such introspection is likely to be quite imprecise, especially when thinking about others beliefs, or their beliefs about your beliefs. There has been some recent progress in formulating models of noisy introspection, which can then be used to predict and explain non-Nash behavior in experiments using games played only once (24,45). If a game is repeated, e.g. with random matchings from a population of players, some noise may persist even after average tendencies have stabilized. The quantal response equilibrum is based on the idea that players responses to differences in expected payoffs are sharper when such differences are large, and are more random when such differences are small (see (46) for an existence proof, and (47) for application to bidding in an auction). This notion of equilibrium is a generalization of the Nash equilibrium in the sense that the quantal response predictions converge to a Nash equilibrium as the noise is diminished. But the effect of non-negligible noise is not merely to spread decisions around Nash predictions; strategic interactions cause feedbacks in some games that magnify and distort the effects of noise. This approach has been used to explain data from some laboratory experiments in which observed behavior deviates from a unique Nash equilibrium and ends up on the opposite side of the set of feasible decisions (24, 43). Still another approach seeks to reconcile experimental evidence and equilibrium predictions by considering how those predictions would differ if systematic regularities in participants preferences were modeled. One lesson that consistently emerges from smallgroup bargaining experiments is that people are often as concerned with fairness issues as they are with their own payoffs (see e.g. 48). The incorporation of fairness and other notions of non-selfish preferences into standard models often brings economic game theory into contact with evolutionary explanations of human behavior (see e.g. 49,50). Nashs Contributions in Perspective In the last 20 years, the notion of a Nash equilibrium has become a required part of the tool kit for economists and other social and behavioral scientists, so well known that it does not need explicit citation, any more than one needs to cite Adam Smith when discussing competitive equilibrium. There have been modifications, generalizations, and

refinements, but the basic equilibrium analysis is the place to begin (and sometimes end) the analysis of strategic interactions, not only in economics, but also in law, politics, etc. The Nash equilibrium is probably invoked as often in small-group (and not so small group) situations as competitive equilibrium is used in large markets. Students in economics classes today probably hear John Nashs name as much or more than that of any economist. In the half century following the publication of Nashs PNAS paper, game theory moved into center stage in economic theory. Game theory has also become part of a lively scientific conversation with experimental and other empirical scientists, and, increasingly, the source of practical advice on the design of markets and other economic environments. Looking ahead, if game theorys next fifty years are to be as productive, the challenges facing game theorists include learning to incorporate more varied and realistic models of individual behavior into the study of strategic behavior, and learning to better use analytical, experimental, and computational tools in concert to deal with complex strategic environments.

Bibliography 1. Nash, J.F. (1950a) Equilibrium Points in N-Person Games, Proceedings of the National Academy of Sciences, USA 36, 48-49. 2. von Neumann, J. and Morgenstern, O. (1944) Theory of Games and Economic Behavior, Princeton, N.J.: Princeton University Press. 3. von Neumann, J. (1928) Zur Theorie der Gesellchaftsspiele, Math. Annalen 100, 295-320. 4. Nash, J.F. (1951a) Non-cooperative Games, Ph.D. Dissertation, Princeton University. 5. Nash, J.F. (1951b) Non-cooperative Games, Annals of Mathematics, 54, 286-295. 6. Maynard-Smith, J. (1974) The Theory of Games and the Evolution of Animal Conflict, Journal of Theoretical Biology, 47, 209-221. 7. Hoffbauer, J. and K. Sigmund (1988) The Theory of Evolution and Dynamical Systems, Cambridge: Cambridge University Press. 8. Weibull, J. W. (1995) Evolutionary Game Theory, Cambridge, Massachusetts: The MIT Press. 9. Nash, J.F. (1950b) The Bargaining Problem, Econometrica, 18, 155-162. 10. Nash, J.F. (1953), Two-Person Cooperative Games, Econometrica, 21, 128-140. 11. Kakutani, S. (1941) Duke Math. Journal, 8, 457-459. 12. Harsanyi, J. (1967-68) Games with Incomplete Information Played by Bayesian Players, Management Science, 14, 159-182, 320-334, 486-502. 13. Selten, R. (1965), Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetragheit, Zeitschrift fur die gesamte Staatswissenschaft 121, 301-324 and667689. 14. Selten, R. (1975), Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games, International Journal of Game Theory 4, 25-55. 15. Aumann, R.J. (1974) Subjectivity and Correlation in Randomized Games, Journal of Mathematical Economics, 1, 67-96. 16. Straffin, P. D. Jr., (1980) The Prisoners Dilemma, UMAP Journal, 1, 102-3.

17. Tucker, A. W. (1950) A Two-Person Dilemma, mimeo, Stanford University, publised under the heading: On Jargon: The Prisoners Dilemma, UMAP Journal, 1, 101. 18. Flood, M. M. (1958) Some Experimental Games, Management Science, 5, 5-26. 19. Raiffa, H. (1992) Game Theory at the University of Michigan in E.R.Weintraub, Toward a History of Game Theory, Durham: Duke University Press, 165-175. 20. Hardin, G. (1968) Tragedy of the Commons Science 162, 1243-1248. 21. Rapaport, Anatol and A.M. Chammah (1965) Prisoners Dilemma: A Study in Conflict and Cooperation, Ann Arbor: University of Michigan Press. 22. Axelrod, R. (1984) The Evolution of Cooperation, New York: Basic Books. 23. Ledyard, J. (1995) "Public Goods: A Survey of Experimental Research," in J. Kagel and A. Roth (eds.), Handbook of Experimental Economics. Princeton: Princeton University Press, 111-194. 24. Goeree, J.K. and C.A. Holt (1999) "Stochastic Game Theory: For Playing Games, Not Just For Doing Theory," Proceedings of the National Academy of Sciences, U.S.A., 96, 10564-67. 25. Ostrom, E. (1998) A Behavioral Approach to the Rational Choice Theory of Collective Action: Presidential Address, American Political Science Association, 1997, American Political Science Review, 92 1-22. 26. Avery, C., C. Jolls, R. A. Posner, and A. E. Roth, The Market for Federal Judicial Law Clerks, University of Chicago Law Review, 68, 3, Summer, 2001, 793-902. 27. Roth, A.E. (1984) "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy, 92, 991-1016. 28. Roth, A.E. (1990) "New Physicians: A Natural Experiment in Market Organization," Science, 250, 1524-1528. 29. Gale, David and Lloyd Shapley [1962], "College Admissions and the Stability of Marriage," American Mathematical Monthly, 69, 9-15. 30. Roth, A.E. and M. Sotomayor (1990) Two-Sided Matching: A Study in GameTheoretic Modeling and Analysis, Econometric Society Monograph Series, Cambridge University Press.

10

31. Roth, A.E. and E. Peranson (1999) "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design, American Economic Review, 89, 4, September, 748-780. 32. Milgrom, P. R. (2004) Putting Auction Theory to Work, Cambridge University Press, forthcoming. 33. Wilson, R.B. (2002) Architecture of Power Markets, Econometrica, 70, 4, July, 1299-1340. 34. Vickrey, W. (1961) Counterspeculation, Auctions, and Competitive Sealed Tenders, Journal of Finance, 16, 8-37. 35. Kalisch, G. K., J.W. Millnor, J.F. Nash, and E.D. Nering (1954) Some Experimental n-Person Games, in R.M. Thrall, C.H. Coombs, and R.L. Davis, Decision Processes, New York: Wiley, 513-518. 36. Kagel, J.H. and A.E. Roth, eds. (1995) Handbook of Experimental Economics. Princeton: Princeton University Press. 37. Davis, D.D. and C.A. Holt (1993) Experimental Economics, Princeton, N.J.: Princeton University Press. 38. Kahneman, D. and A. Tversky (1979) Prospect Theory: An Analysis of Decision Under Risk, Econometrica, 47, 263-291. 39. Smith, V.L. (1962) An Experimental Study of Competitive Market Behavior, Journal of Political Economy, 70, 111-137. 40. Fudenburg, D. and D. Kreps (1993) Learning Mixed Equilibria, Games and Economic Behavior, 5, 320-367. 41. Fudenberg, D. and M. Levine (1998) Learning in Games, Boston: MIT Press. 42. Erev, I. and A.E. Roth "Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria," American Economic Review, 88,4, September, 1998, 848-881. 43. Capra, C.M., Goeree, J.K., Gomez, R. & Holt, C.A. (2002) Learning and Noisy Equilibrium Behavior in an Experimental Study of Imperfect Price Competition, International Economic Review, 43(3), 613-636. 44. Goeree, J.K. & Holt, C.A. (2002). Learning in Economics Experiments. In L. Nadel (ed.), Encyclopedia of Cognitive Science, Vol. 2 (pp. 1060-1069), London: Nature Publishing Group, McMillan.

11

45. Goeree, J.K. & Holt, C.A. (2003) A Model of Noisy Introspection. Games and Economic Behavior, forthcoming. 46. McKelvey, R.M. and T.R. Palfrey (1995) "Quantal Response Equilibria for Normal Form Games," Games and Economic Behavior, 10(1), 6-38. 47. Goeree, J.K., Holt, C.A., & Palfrey, T.R. (2002) Quantal Response Equilibrium and Overbidding in Auctions. Journal of Economic Theory, 104(1), 247-272. 48. Bolton, G.E. and A. Ockenfels, ERC - A Theory of Equity, Reciprocity and Competition, American Economic Review, March 2000, 90(1), 166-193. 49. Fehr, E. and S. Gchter (2002) Altruistic Punishment in Humans, Nature 415, 10 January, 137-140. 50. Nowak, M.A. and K. Sigmund (1998) Evolution of Indirect Reciprocity by Image Scoring, Nature 393 (6685): 573-577 June 11

12