Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm trying to understand why John Nash's 1950 2-page paper that was published in PNAS was such a big deal. Unless I'm mistaken, the 1928 paper by John von Neumann demonstrated that all n-player non-cooperative and zero-sum games possess an equilibrium solution in terms of pure or mixed strategies.

From what I understand, Nash used fixed point iteration to prove that non-zero-sum games would also have the analogous result. Why was this such a big deal in light of the earlier work by von Neumann?

There are two references I provide that are good: One is this discussion on simple proofs of Nash's theorem and this one is a very well done (readable and accurate) survey of the history in PNAS.

share|improve this question
1  
To me the real big deal about John Nash is not this paper, but the fact that he recovered from schizophrenia spontaneously. –  Sylvain JULIEN Apr 8 at 20:51
7  
The big deal is not a theorem, but a definition. The concept of Nash equilibrium captures an essential feature of social and economic interactions. –  alvarezpaiva Apr 8 at 20:52
2  
@SylvainJULIEN Is that why he got the Nobel prize? I believe that was the OP's question. –  Igor Rivin Apr 8 at 21:04
2  
From talking to economists (I am not one) I think the answer is that there was little general theory about non-zero-sum games until Nash's result. I assume that people had found mixed strategy solutions for the prisoner's dilemma since it is elementary, but it is not at all obvious that such solutions exist in more complicated games. –  Paul Siegel Apr 8 at 21:15

5 Answers 5

up vote 25 down vote accepted

I think von Neumann dealt with the case $n=2$, and it was by no means obvious how to extend the concept of equilibrium for the general case and prove that it always exists. More precisely, $n$ players before Nash were reduced to the $n=2$ case by partioning the players into two groups in all possible ways. Once you regard several players as a single player, they are meant to cooperate as they must act like a single player. Nash is very clear about this in his 1951 Annals paper:

Von Neumann and Morgenstern have developed a very fruitful theory of two-person zero-sum games in their book Theory of Games and Economic Behavior. This book also contains a theory of $n$-person games of a type which we would call cooperative. This theory is based on an analysis of the interrelationships of the various coalitions which can be formed by the players of the game.

Our theory, in contradistinction, is based on the absence of coalitions in that it is assumed that each participant acts independently, without collaboration or communication with any of the others.

The notion of an equilibrium point is the basic ingredient in our theory. This notion yields a generalization of the concept of the solution of a two-person zero-sum game. It turns out that the set of equilibrium points of a two-person zero-sum game is simply the set of all pairs of opposing "good strategies." In the immediately following sections we shall define equilibrium points and prove that a finite non-cooperative game always has at least one equilibrium point. We shall also introduce the notions of solvability and strong solvability of a non-cooperative game and prove a theorem on the geometrical structure of the set of equilibrium points of a solvable game.

share|improve this answer
1  
In the comments to the OP Paul Siegel suggests that Nash's notion also extended the earlier results from the zero-sum case to the non-zero-sum case. It is ambiguous from the abstract, where Nash writes "This notion yields a generalization of the concept of the solution of a two-person zero-sum game." As your answer stresses the $n >2$ generalization I just wanted to remark that it may also generalize earlier results in that Nash's notion of equilibrium does not depend on the game being zero-sum. I trust someone will correct me if I have this wrong. –  R Hahn Apr 8 at 22:10
    
@R Hahn: I agree with you. In Nash's paper, the payoff function of each player is an arbitrary linear function on the convex polytope representing the mixed strategies. –  GH from MO Apr 8 at 23:49
4  
It's not too hard to see that if you know how to generalize to additional players, you also know how to generalize to non-zero-sum. Simply add an additional player with one strategy whose payoff is minus the sum of the other player's payoffs. –  Will Sawin Apr 16 at 1:13

This answer overlaps with other answers but I think another restatement may be helpful because the situation is slightly confusing.

After the two-person zero-sum result, it is natural to ask about extending the results to $n>2$ and to non-zero-sum games. Sometimes it is stated that Nash was the first to carry out this extension, but this is slightly misleading, because von Neumann and Morgenstern did consider both $n>2$ and non-zero-sum games and proved various things about them. However, the key point is that it's important to ask the right question. Intuitively, the basic question in game theory is to find the "optimal strategy", but it's not immediately clear what this means in an $n$-person non-cooperative game. We now understand, thanks to Nash, that a basic necessary condition for a set of strategies to be "optimal" is for them to form a Nash equilibrium, but von Neumann and Morgenstern did not hit on this concept. When they treated $n$-person games, they addressed different questions, such as what happens if the players form two coalitions. So Nash didn't just answer the obvious question; the right question wasn't obvious, but he found it anyway, and answered it.

The second innovative aspect of Nash's work is that the two-person zero-sum result was based on the theory of linear programming and minimax. Proving the existence of a Nash equilibrium requires different techniques. So the naive approach to generalization, namely staring at the existing result and trying to figure out how to use the same ideas to prove something more general, does not lead to Nash's key insight.

share|improve this answer

The significance is best interpreted in conjunction with Nash's accompanying work.

Myerson gives a good history of the theory: http://home.uchicago.edu/rmyerson/research/jelnash.pdf

Here are some important points:

Thus von Neumann (1928) argued that virtually any competitive game can be modeled by a mathematical game with the following simple structure: There is a set of players, each player has a set of strategies, each player has a payoff function from the Cartesian product of these strategy sets into the real numbers, and each player must choose his strategy independently of the other players. ...

Von Neumann did not consistently apply this principle of strategic independence, however. In his analysis of games with more than two players, von Neumann (1928) assumed that players would not simply choose their strategies independently, but would coordinate their strategies in coalitions. Furthermore, by his emphasis on max-min values, von Neumann was implicitly assuming that any strategy choice for a player or coalition should be evaluated against the other players' rational response, as if the others could plan their response after observing this strategy choice. Before Nash, however, no one seems to have noticed that these assumptions were inconsistent with von Neumann's own argument for strategic independence of the players in the normal form.

Von Neumann (1928) also added two restrictions to his normal form that severely limited its claim to be a general model of social interaction for all the social sciences: He assumed that payoff is transferable, and that all games are zero-sum.

In contrast, Nash provided a way to deal with the more general problem of non-transferable utility and non-zero-sum games.

But the most important new contribution of Nash (1951), fully as important as the general definition and the existence proof of Nash (1950b), was his argument that this noncooperative equilibrium concept, together with von Neumann's normal form, gives us a complete general methodology for analyzing all games.... Von Neumann's normal form is our general model for all games, and Nash's equilibrium is our general solution concept. ...

Nash (1951) also noted that the assumption of transferable utility can be dropped without loss of generality, because possibilities for transfer can be put into the moves of the game itself, and he dropped the zero-sum restriction that von Neumann had imposed.

share|improve this answer

As as been rightly said, Nash defined a concept of equilibrium for zero-sum games with $n$ players, and proved the existence (but no uniqueness of course) of such, while Von Neumann and Morgenstern did that only for $n=2$ (or larger $n$ but with very strong hypotheses on the game that reduces the problem to a game with $n=2$ players). But it is important to note than while doing so, Nash also defines a concept of equilibrium for non-zero sum games with $n$ players, for such a game is equivalent to a zero sum game with $n+1$ players: just add one new player, the "bank", whose gain/loss is defined as the negative of the sum of the gains of each other players.

That being said, the real-world meaning of the concept of Nash equilibrium is very tricky, and it is far from clear if/when that concept is the right one to analyze a game situation, while in the case $n=2$, the Von Neumann/Morgenstern concept is much more obviously the only right one.

share|improve this answer
1  
Joël, Of course there are also issues with the notion of value for zero-sum 2-person games, like the need to have mixed strategies which is problematic in various cases (and various others issues). Once you apply Von Neumann and Morgenstern utility theory on mixed outcomes you often loose the zero-sum property. But I agree that the notion of a value of zero-sum games is also very important. –  Gil Kalai Apr 24 at 7:18

Let me start with my own view:

The Nash equilibrium concept and the accompanying existence theorem is among the very few cornerstones in mathematical modeling of our reality .

Let me add a few more links. A paper by Ariel Rubinstein entitled "John Nash the master of economic modeling" and a document based on a seminar entitled: "The work of John Nash in Game theory." This includes the following quote from an earlier paper by Aumann.

enter image description here

Nash equilibrium is probably the main reason for the "game-theoretic revolution" in theoretical economics.

share|improve this answer
    
And yet, in practice, in each of the specific applications your paper mentions that I know of, the concept of Nash equilibrium has important shortcomings, to begin with its non-uniqueness. It is often refined or altogether replaced by other notion of :equilibrium", such as evolutionary stable strategy etc. I am not saying that the concept of Nash equilibrium is not important and beautiful, but I want to warn the over-enthusiastic mathematician that it is not the miracle concept clarifying all the problems in applied game theory. –  Joël Apr 23 at 15:40
    
Dear Joël, I agree. To a large extent Nash equilibrium is a miracle concept leading to (almost) all the problems in applied game theory. It often represents genuine problems and shortcomings not only of economics theory but also of economics reality. Certainly this is something we, as mathematicians can celebrate and be enthusiastic about! –  Gil Kalai Apr 23 at 16:26
    
@Joël If warning over-enthusiastic people is an issue, I recommend the following article by Ariel Rubinstein: faz.net/aktuell/feuilleton/debatten/… –  Waldemar Apr 24 at 12:25
    
@Waldemar "How game theory will solve the problems of the Euro Bloc and stop Iranian nukes" hmm, that seems promising. One day I'll explain how I successfully used game theory to solve of my educational problem with my daughter (I needed Nash's concept because obviously it was not a zero sum game). –  Joël Apr 24 at 15:11
2  
@Joël The title is purposefully misleading - see the last paragraph of the article. In fact, the main idea is that game theory isn't useful to solve real-world problems. The article is written by a well-known researcher in the field. That's why I said that it is recommended if you want to warn over-enthusiastic people. –  Waldemar Apr 24 at 16:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.