Tuesday, September 25, 2007

Writing Down Von Neumann's Contributions to Game Theory

Today's New York Times, in the science section, contains an ad for the "Von Neumann Memorial Lectures". This reminded me that, several years ago in the Times, Hal Varian misrepresented Von Neumann's treatment of game theory:
"Modern game theory was developed by the great mathematician John Von Neumann in the mid-1940s. His goal was to understand the general logic of strategic interaction, from military battles to price wars.

Von Neumann, working with the economist Oscar Morgenstern, established a general way to represent games mathematically and offered a systematic treatment of games in which the players' interests were diametrically opposed. Games of this sort - zero-sum games - are common in sporting events and parlor games.

But most games of interest to economists are non-zero sum. When one person engages in voluntary trade with another, both are typically made better off. Although von Neumann and Morgenstern tried to analyze games of this sort, their analysis was not as satisfactory as that of zero-sum games. Furthermore, the tools they used to analyze these two classes of games were completely different.

Mr. Nash came up with a much better way to look at non-zero-sum games. His method also had the advantage that it was equivalent to the von Neumann-Morgenstern analysis if the game happened to be zero sum." -- Hal R. Varian (2002).
I find it hard to read this as saying anything other than:
  • Nash generalized the Von Neumann and Morgenstern (VNM) solution to zero-sum games to a solution (the Nash solution) applying to both zero-sum and non-zero-sum games.
  • Although VNM had a solution for non-zero-sum games, it was not a generalization of their solution for zero-sum games.
Both claims are false.

Varian's statement only makes sense if one pretends The Theory of Games and Economic Behavior (TGEB) is missing the almost 300 pages on zero-sum n-person games. Under this pretense, the only zero-sum games treated in TGEB would be two-person games. The Nash equilibrium is, in some sense, a generalization of the VNM minimax treatment of two-person zero sum games. And the TGEB treatment of coalitions in non-zero sum games is something else.

VMN do decompose their treatment of games into two phases, but not based on whether or not a game is zero sum. They decompose their treatment into zero-sum two-person games and all other games (All quotations of numbered paragraphs are of the third edition of TGEB):
"66.1.2. Our theory of games divides clearly into two distinct phases: The first one comprising the treatment of the zero-sum two-person game and leading to the definition of its value, the second one dealing with the zero-sum n-person game, based on the characteristic function, as defined with the help of the values of the two-person games."
The TGEB solution of n-person zero-sum games is, in some sense, a generalization of the TGEB minimax solution of zero-sum two person games. One can form two "collective persons" for the n-person game, where each "person" is one of two coalitions:
"25.1.2. Suppose then that we have a game Gamma of n players... Without yet making any predictions or assumptions about the course a play of this game is likely to take, we observe this: if we group the players into two parties, and treat each party as an absolute coalition - i.e. if we assume full cooperation within each party - then a zero-sum two-person game results..."
In the TGEB treatment, a coalition can pool their winnings and then redistribute them to the players in the coalition. VMN define a solution to a game as a set of imputations of payouts to the players. The definition of the set of imputations is concerned with why a player would chose to be in one coalition or the other, and why the remaining members of the winning coalition would chose to woo a player or not.

To help fix intuition, VMN define an interesting zero-sum three person game, the Majority Game:
"21.1...Each player, by a personal move, chooses the number of one of the two other players. Each one makes his choice uninformed about the choices of the two other players.

After this the payments will be made as follows: if two players have chosen each other's numbers we say that they form a couple. Clearly there will be precisely one couple, or none at all. If there is precisely one couple, then the two players who belong to it get one-half unit each, while the third (excluded) player correspondingly loses one unit. If there is no couple, then no one gets anything."
The TGEB analysis of a generalization of the Majority Game is indeterminate in two senses:
  • An uncountably infinite number of solution sets of imputations exist (some of which VMN describe as analogous to discrimination).
  • In the most obvious solution, { (1/2, 1/2, -1), (1/2, -1, 1/2), (-1, 1/2, 1/2) }, how much a player gets and whether or not he is in the winning two-person coalition is indeterminate (which of the three imputations is realized is unspecified)
VNM generalize their treatment of zero-sum games to non-zero sum games by introducing a powerless dummy:
"56.2.1. ...any given general [not necessarily zero-sum] game can be re-interpreted as a zero-sum game...Our procedure will be to interpret an n-person general game as an n+1-person zero-sum game."
Contrary to Varian, the TGEB treatment of non-zero sum games is a generalization of the TGEB treatment of zero sum games. The VNM solution has come to be known as a solution to cooperative games. (If one sets aside his analysis of bargaining, Nash treats non-cooperative games.) Trivially, only one set of imputations is a solution to a zero-sum two-person game. There is only one imputation in that set, and that imputation is equivalent to the minimax solution.

TGEB has lots of interesting asides and suggestions that relate to later ideas. For example, VNM suggest an alternative treatment in which an external enforcement mechanism for (contracts between players in) cooperative games is not needed. In this alternative treatment of iterative play, cooperation emerges spontaneously:
"21.2.3. If our theory were applied as a statistical analysis of a long series of plays of the same game - and not as the analysis of one isolated play - an alternative interpretation would suggest itself. We should then view agreements and all forms of cooperation as establishing themselves by repetition in such a long series of plays.

It would not be impossible to derive a mechanism of enforcement from the player's desire to maintain his record and to be able to rely on the record of his partner. However, we prefer to view our theory as applying to an individual play. But these considerations, nevertheless, possess a certain significance in a virtual sense. The situation is similar to the one which we encountered in the analysis of the (mixed) strategies of a zero-sum two-person game..."
I don't think this idea works for all cooperative games. But one can see here some ideas of evolutionary game theory.

I read TGEB, particularly the first chapter, as hostile to neoclassical economics. VNM disparage the idea that a model of Robinson Crusoe can tell us much about social phenomena. And they cast doubt on the idea that imitating the mathematical methods used in physics will bring much progress in economics.



YouNotSneaky! said...

This is really good but I think that if Varian just qualified his statements by inserting "non-cooperative" in appropriate places he wouldn't be that far off. I dunno, I'm told that one should cut NY Times columnists some slack. Space constraints and all that.

Now the one where you could really slap him around is the one where he talks about "production with fixed coefficients" and how it has been "dis-proven" (in the context of Harrod-Domar) which I saw some time ago. I can't find it again though and I'm not even sure if it was NYT or some other place.

Hal Varian said...

That's because I never wrote a piece about "production with fixed coefficients" and how it has been "dis-proven". You must have me confused with someone else.

Anyway, I stand by the game theory column. The non-cooperative game theory of the 2-person game analysis and the cooperative game theory analysis of the n-person games in vNM-M are quite different mathematically, despite vNM's valiant effort to tie them together.

Robert Vienneau said...

Thanks for the comments.

YouNotSneaky! said...

It's possible I confused my economic columnists, in which case I apologize. This was an old column from 2001 or so and back then there weren't that many economic publicists which is why I probably made the mistaken attribution.