6
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – badp
    Commented Dec 9, 2012 at 10:06

3 Answers 3

Reset to default
10
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chris Eagle
    Commented Dec 9, 2012 at 10:24
  • $\begingroup$ @ChrisEagle Thank you, that's interesting. $\endgroup$
    – Michael Greinecker
    Commented Dec 9, 2012 at 10:28
  • $\begingroup$ There is an upper bound on the number of moves of a chess game because of the 50-move rule . $\endgroup$
    – DanielWainfleet
    Commented Dec 22, 2016 at 22:52
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Michael Greinecker
    Commented Dec 9, 2012 at 11:12
  • $\begingroup$ @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? $\endgroup$
    – joriki
    Commented Dec 9, 2012 at 11:58
  • $\begingroup$ Yes, it looks fine to me now. $\endgroup$
    – Michael Greinecker
    Commented Dec 9, 2012 at 12:00
-2
$\begingroup$

Generally speaking chess theoretically always should end in a draw if the best moves are always played by both sides. The reason, being that a +4 advantage which is rare to achieve is very hard to win with, ie mating with a bishop is not possible nor is it with a horse alone in a king end game. Having a pawn is good, but the opponent can generally sacrifice that piece for the pawn to prevent a queen. Mating with a knight + bishop is a 48 move process, and you need to play it perfect to avoid the 50 move draw rule. This is why so many games end in draws. The only trump card is to force a draw, taking risks in other lines, can simply be refuted if the opponent can work it out OTB.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .