Kuhn's Theorem

Also attributed to Zermelo

Every sequential game with perfect information has a Nash equilibrium.

The theorem can be proved using backward induction. In the
above game with Bob, Ted and Alice consider the rightmost nodes first, starting at the
bottom. The terminal node at the bottom belongs to Alice; she will play **J**.
The node above her belongs to Ted; he will play **H**. The next terminal node
above him belongs to Bob; he will play **D**. Above him is Alice and she will
play **B**. After trimming the branches that won't be played we get:

Trim the game tree again, from right to left. Now Bob has
the rightmost decision node. He will play **N** and the trimmed tree looks
like:

Now we have rolled the game tree back to Ted's initial move.
At this point Ted's dominant strategy is to play **T**. The game tree, after
eliminating the dominated strategies in the terminal nodes, looks like:

As long as we know the ordinal ranking of the payoffs we could use the same rollback solution method to any perfect information game.

Note that backward induction doesn't find all of the Nash equilibria. An example is the following game between Sally and Jesse.

The rollback solution to the game is for Sally to play **1**
and for Jesse to then play **1**. However, when you look at the
strategic form representation of the game then you can see that there are two Nash
equilibria.

Check the best response table to find them.

Sally | Jesse |

b^{S}(11^{J})= 1 |
b^{J}(1^{S}) = 11 |

b^{S}(21^{J}) = 2 |
b^{J}(1^{S}) = 11 |