Nash.dvi

John F. Nash, Jr., submitted his Ph.D. dissertation entitled Non-CooperativeGames to Princeton University in 1950. Read it 58 years later, and you willfind the germs of various later developments in game theory. Some of theseare presented below, followed by a discussion concerning dynamic aspects ofequilibrium.
What is a Nash equilibrium1? John Nash defines an equilibrium point as “an n-tuple s such that each player’s mixed strategy maximizeshis pay-off if the strategies of the others are held fixed. Thus eachplayer’s strategy is optimal against those of the others.” (page 3) Nash emphasizes the non-cooperative aspect of his theory, in contrast to the“cooperative” approach of von Neumann and Morgenstern that was prevalentat the time: “Our theory, in contradistinction, is based on the absence of coali-tions in that it is assumed that each participant acts indepen-dently, without collaboration or communication with any of theothers. [.] The basic requirement for a non-cooperative game ∗Presented at the Opening Panel of the Conference in Honor of John Nash’s 80th Birthday at Princeton University in June 2008. Updated: October 2010.
†Center for the Study of Rationality, Institute of Mathematics, and Department of Economics, The Hebrew University of Jerusalem.
e-mail : hart@huji.ac.il 1 I have seen “nash equilibrium” in print, as if “nash” were an English word. Having one’s name spelled with a lower-case initial letter is surely a sign of lasting fame! is that there should be no pre-play communication among theplayers [.]. Thus, by implication, there are no coalitions and noside-payments.” (pages 1, 21) In the last section of his thesis, “Applications,” Nash introduces what hascome to be known as the Nash program, namely: “a ‘dynamical’ approach to the study of cooperative games basedupon reduction to non-cooperative form. One proceeds by con-structing a model of the pre-play negotiation so that the steps ofnegotiation become moves in a larger non-cooperative game [.]describing the total situation. This larger game is then treatedin terms of the theory of this paper [.]. Thus the problem ofanalyzing a cooperative game becomes the problem of obtaininga suitable, and convincing, non-cooperative model for the nego-tiation.” (pages 25–26) Nash himself used this approach for the two-person bargaining problem inhis 1953 paper. Since then, the Nash program has been applied to a largenumber of models (see, e.g., the surveys of Mas-Colell 1997 and Reny 1997).
The whole area of implementation—discussed in this panel by Eric Maskin—may also be regarded as a successful offshoot of the Nash program.
The next-to-last section of the dissertation is entitled “Motivation and In-terpretation.” Two interpretations of the concept of Nash equilibrium areprovided. The first, the “mass-action” interpretation, assumes that “there is a population [.] of participants for each position in thegame.” (page 21) This framework brings us to a significant area of research known as evolu-tionary game theory, with important connections to biology; it is discussedin this panel by Peyton Young.
The second interpretation of Nash equilibrium provided in the dissertationrefers to “a ‘rational’ prediction of the behavior to be expected of rationalplaying the game [.]. In this interpretation we need to assumethe players know the full structure of the game [.]. It is quitestrongly a rationalistic and idealizing interpretation.” (page 23) With the development of the area known as interactive epistemology, whichdeals formally with the issues of knowledge and rationality in multi-playersituations, one can now state precise conditions for Nash equilibria. Forinstance, to obtain Nash equilibria in pure strategies, it suffices for each playerto be rational and to know his own payoff function as well as the choices ofthe pure strategies of the other players (see Aumann and Brandenburger1995; for mixed strategies the conditions are more complicated).
Nash equilibrium is by definition a static concept. So what happens in dy-namic setups where the players adjust their play over time? Since Nashequilibria are essentially “rest points,” it is reasonable to expect that appro-priate dynamical systems should lead to them.
However, after more than half a century of research, it turns out that There are no general, natural dynamics leading to Nash equilibria.
Let us clarify the statement (*). First, “general” means “for all games,”rather than “for specific classes of games only.”2 Second, “leading to Nashequilibria” means that the process reaches Nash equilibria (or is close tothem) from some time on.3 Finally, what is a “natural dynamic”? While itis not easy to define the term precisely, there are certain clear requirements fora dynamic to be called “natural”: it should be in some sense adaptive—i.e.,the players should react to what happens, and move in generally improvingdirections (this rules out deterministic and stochastic variants of “exhaustivesearch” where the players blindly search through all the possibilities); and itshould be simple and efficient—in terms of how much information the playerspossess, how complex their computations are at each step, and how long ittakes to reach equilibrium. What (*) says is that, despite much effort, nosuch dynamics have yet been found.
2 Indeed, there are classes of games—in fact, no more than a handful—for which such dynamics have been found, e.g., two-player games, and potential games.
3 Dynamics that are close to Nash equilibria most of the time have been constructed in particular by Foster and Young (2003) and recently by Young (2009). These dynamicswill reach a neighborhood of equilibria and stay there for a long time, but always leavethis neighborhood eventually and the process then restarts.
A natural informational restriction is for each player to know initially only his own payoff (or utility) function, but not those of the other players; thisis called uncoupledness (Hart and Mas-Colell 2003) and is a usual conditionin many setups. However, it leads to various impossibility results on theexistence of “natural” uncoupled dynamics leading to Nash equilibria (Hartand Mas-Colell 2003, 2006; Hart and Mansour 2010). Thus (*) turns out tobe not just a statement about the current state of research in game theory,but in fact a result: There cannot be general, natural dynamics leading to Nash equilibria.
A generalization of the concept of Nash equilibrium is the notion of correlatedequilibrium (Aumann 1974): it is a Nash equilibrium of the extended gamewhere each player may receive certain information (call it a “signal”) beforeplaying the game; these signals do not affect the game directly. Nevertheless,the players may well take these signals into account when deciding whichstrategy to play. When the players’ signals are independent, this reduces tonothing more than Nash equilibria; when the signals are public, this yieldsa weighted average of Nash equilibria; and when the signals are correlated(but not fully), new equilibria obtain.
Interestingly, there are general, natural dynamics leading to correlated equilibria (such as “regret matching”: Hart and Mas-Colell 2000, Hart 2005).
The dissertation that John Nash submitted in 1950 is relatively short (cer-tainly by today’s standards). But not in content! Besides the definition ofthe concept of non-cooperative equilibrium and a proof of its existence, onecan find there intriguing and stimulating ideas that predate a lot of moderngame theory.
Aumann, R. J. (1974), “Subjectivity and Correlation in Randomized Strate- gies,” Journal of Mathematical Economics 1, 67–96.
Aumann, R. J. and A. Brandenburger (1995), “Epistemic Conditions for Nash Equilibrium,” Econometrica 63, 116–180.
Foster, D. and H. P. Young (2003), “Learning, Hypothesis Testing, and Nash Equilibrium,” Games and Economic Behavior 45, 73–96.
Hart, S. (2005), “Adaptive Heuristics,” Econometrica 73, 1401–1430.
Hart, S. and Y. Mansour (2010), “How Long to Equilibrium? The Commu- nication Complexity of Uncoupled Equilibrium Procedures,” Games andEconomic Behavior 69, 107–126.
Hart, S. and A. Mas-Colell (2000), “A Simple Adaptive Procedure Leading to Correlated Equilibrium,” Econometrica 68, 1127–1150.
Hart, S. and A. Mas-Colell (2003), “Uncoupled Dynamics Do Not Lead to Nash Equilibrium,” American Economic Review 93, 1830–1836.
Hart, S. and A. Mas-Colell (2006), “Stochastic Uncoupled Dynamics and Nash Equilibrium,” Games and Economic Behavior 57, 286–303.
Mas-Colell, A. (1997), “Bargaining Games,” in Cooperation: Game Theoretic Approaches, S. Hart and A. Mas-Colell (editors), Springer-Verlag, 69–90.
Nash, J. F. (1950), “Non-Cooperative Games,” Ph.D. Dissertation, Princeton Nash, J. F. (1953), “Two-Person Cooperative Games,” Econometrica 21, Reny, P. H. (1997), “Two Lectures on Implementation Under Complete In- formation: General Results and the Core,” in Cooperation: Game The-oretic Approaches, S. Hart and A. Mas-Colell (editors), Springer-Verlag,91–113.
Von Neumann, J. and O. Morgenstern (1944), Theory of Games and Eco- nomic Behavior, Princeton: Princeton University Press.
Young, H. P. (2009), “Learning by Trial and Error,” Games and Economic

Source: http://ma.huji.ac.il/~hart/papers/nash-old.pdf