Kuhn's Theorem
Also attributed to Zermelo

Every sequential game with perfect information has a Nash equilibrium.

wpe4.jpg (30501 bytes)

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:

wpe5.jpg (14004 bytes)

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:

wpe6.jpg (10794 bytes)

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:

wpe7.jpg (4724 bytes)

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.

wpe8.jpg (9608 bytes)

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. 

wpe9.jpg (6637 bytes)

Check the best response table to find them.

Sally Jesse
bS(11J)= 1 bJ(1S) = 11
bS(21J) = 2 bJ(1S) = 11