Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Von Neumann's Minimax theorem (quoted from Wikipedia):

For every two-person, zero-sum game with finite strategies, there exists a value V and a mixed strategy for each player, such that (a) Given player 2's strategy, the best payoff possible for player 1 is V, and (b) Given player 1's strategy, the best payoff possible for player 2 is −V.

Nash's theorem:

Every finite game has a mixed strategy equilibrium.

Now, to me, it seems that the Minimax theorem is simply a specific instance of the Nash theorem, for a two-player zero-sum game (the moment an equilibrium is established, the results concerning the game value follow immediately).

But in my Game Theory course, we studied these as two separate theorems, with entirely different proofs. Some exams even had proving both theorems as two exam questions - making it seem like a claim that "Minimax follows immediately from Nash's theorem" would be suspect.

Am I misunderstanding some fundamental difference between these two theorems? Or did we simply learn two different proofs of the same thing?

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

Wikipedia agrees with you, saying "In zero-sum games, the minimax solution is the same as the Nash equilibrium" (second statement of contents of the article about Minimax). So the existence of Nash equilibrium is a generalization of the Minimax theorem.

Presumably, the proof of the minimax theorem is much simpler than the proof of the general theorem. Another crucial difference is that the proof of the minimax theorem is constructive (it amounts to linear programming), whereas finding a Nash equilibrium is PPAD-complete, even for two player games. It is even hard to find an approximate Nash equilibrium.

share|improve this answer
1  
Well, well - fancy meeting you here! This is Ziv Wities :) Great answer - I actually found the Nash proof significantly simpler than Minimax's, but Minimax being constructive while Nash only proves existence is certainly a significant difference. Thanks! –  Ziv Feb 20 '11 at 4:20
    
Welcome... Great to hear from you! –  Yuval Filmus Feb 20 '11 at 4:34
    
Isn't Nash equilibrium for two players equivalent to the system of linear equations? –  Ilya Apr 13 '11 at 13:36
add comment

If a game has a value, it need not to have a mixed strategy Nash equilibrium. In the Von Neumann's Minimax theorem stated above, it is assumed that, for each player, the set of mixed strategy best responses is nonempty given the other player's mixed strategy. However, this assumption is not needed for a game to have a value.

share|improve this answer
add comment

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.