## 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

The Legacy of Paul Erdős Abstract Paul Erdős (Erdős Pál, 1913-1996) was one of the most influential mathematicians of the twentieth century. Erdős’ generation exhibited great talent due in part to the social and cultural changes between 1870 and 1930. In the 1930s, the Jewish Erdős left Hungary due to the worsening political climate, and eventually began a nomadic lifestyle

Organisatiebreed zorgpad voor Somatische screening en opvolging van Metabool Syndroom (MetS) Situering: Het OPZ Geel bestaat uit vier Divisies (Jongeren, Volwassenen, Ouderen, Rehabilitatie), heeft 320 erkende bedden/plaatsen en 538 plaatsen voor Gezinsverpleging. In 2010 bedroeg het aantal rechtstreekse opnames N= 1040. In 2009 beslisten artsen en directie om de ‘Screening en opvolgin