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.

All equilibria found with backwards induction on a tree of a perfect information game are Nash equilibria, but in general the reverse is not true:

        y
(1)---+---(0, 20)             ← Also a Nash equilibrium when (2) announces
      | n         y             he will play y: (0, 20) > (-10, -2)
      +---(2)---+---(-10, -2) 
                | n
                +---( +5, -1) ← Solution through backwards induction

(In class, we've called this the "icecream game", (1) is the mom who needs to decide whether to buy his son an ice cream and (2) is the son who needs to decide whether to cry or not about it.)

However, Chess (or Checkers, or Tic Tac Toe) are different from the "icecream game" because the payoffs are either (1, −1) (white win), (−1, 1) (black win) or (0,0) (draw).

Do these games still allow Nash equilibria that can't be found through backward induction?

share|improve this question
    
In other words, does the Zermelo theorem imply that a game of chess between two rational players will either always end in a white victory, always end in a black victory or always end in a draw? –  badp Dec 9 '12 at 10:06
add comment

2 Answers 2

up vote 5 down vote accepted

Chess is a zero-sum game, so all Nash equilibria will lead to the same of three outcomes: White wins. Black wins. Draw. By Zermelo's theorem, in the first case white can force a win. In the second case, black can force a win. In the third case, both can force a draw.

It is not known which case holds, but in the first two cases, there will be many Nash equilibria (a whole continuum). If one player plays a strategy that guarantees a win for her, her strategy combined with any strategy of the other player together will constitute a Nash equilibrium. Even if both players can force a draw, there may be several ways to do so.

So in conclusion, chess has probably more than one Nash equilibrium. If there is only one Nash equilibrium, it will end in a draw.

Remark: Zermelo did not use backward induction and his proof was not based on chess having a stopping rule.

share|improve this answer
1  
The history of stopping rules in chess seems to be rather complicated. Short version: some chess events before 1913 had rules designed to force the game to terminate. –  Chris Eagle Dec 9 '12 at 10:24
    
@ChrisEagle Thank you, that's interesting. –  Michael Greinecker Dec 9 '12 at 10:28
add comment

The equilibria found through backward induction are subgame perfect equilibria, that is, they are Nash equilibria of all subgames. This eliminates non-credible irrational threats and promises – since the child hurts herself by crying, without gaining anything, it's irrational to cry; thus the threat to cry is irrelevant if both players assume that the other player will act rationally. The Nash equilibrium in which the parent buys the ice cream is not a Nash equilibrium in the subgame after the buying choice; it is a best response for the parent only if the parent believes that the child may carry out a threat to act irrationally (which presumably most parents would be inclined to believe).

There are no irrational threats or promises in a zero-sum game like chess, since by definition there is no situation in which a player can hurt the other player while also hurting themselves. However, as Michael pointed out, even in a zero-sum game a Nash equilibrium need not be subgame perfect, and thus need not be found by backward induction, because a best response strategy may involve irrational moves in subgames that are irrelevant to the outcome because they're never actually played.

share|improve this answer
    
This is plainly not true. As explained in my answer, if one player in zero-sum game can force a win (has a strategy that archives the highest possible payoff), then such a strategy forcing a win gives you in combination with any strategy of the other player a NE. Clearly, such a profile will usually not be a SPE. –  Michael Greinecker Dec 9 '12 at 11:12
    
@Michael: Thanks very much. I had confused being relevant to the outcome with occurring in an equilibrium strategy. I replaced the last sentence -- is it OK now? –  joriki Dec 9 '12 at 11:58
    
Yes, it looks fine to me now. –  Michael Greinecker Dec 9 '12 at 12:00
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.