Lecture 15: Zermelo's Theorem and Games of Perfect Information

What this lecture covers

This lecture formalizes the backward-induction reasoning used in earlier sessions by proving Zermelo's theorem: any finite two-player game of perfect information with win, loss, or tie outcomes has a solution, meaning one player can force a win, force a tie, or is destined to lose. Polak sketches a proof by induction on the length of the game and applies it to tic-tac-toe, checkers, and chess.

The second half formally defines games of perfect information and pure strategies, then uses a market entry example to show that mechanically finding Nash equilibria in a sequential game can surface equilibria built on threats no rational player would actually carry out. This sets up the need for backward induction, rather than Nash equilibrium alone, as the correct solution concept for sequential games.

Key ideas

• Zermelo's theorem: any finite, two-player game of perfect information with win, loss, or tie outcomes has a solution, one side can force a win, force a tie, or will lose if the other plays well.
• Proof by induction on game length: showing the claim holds for one-move games, then showing that if it holds for all games up to length N, it holds for games of length N+1.
• Game of perfect information: a game where, at every node, the player to move knows exactly how the game reached that point.
• Pure strategy: a complete plan specifying what a player will do at every one of their decision nodes, including nodes that will never actually be reached.
• Incredible threat: a strategy that is a Nash equilibrium only because a player is never actually called on to carry out a costly threatened action.
• Sub-game: a smaller game contained within a larger game tree, starting at some node and including everything that follows it.

Walkthrough

Stating Zermelo's theorem (0:00)

Polak generalizes the Nim lesson from the prior lecture: in any finite two-player game of perfect information with win, loss, or tie outcomes, the game divides cleanly into one of three categories, a forced win for Player 1, a forced tie, or a forced win for Player 2. He checks this against tic-tac-toe (a forced tie), checkers, and chess, noting the theorem guarantees chess has a solution without revealing what it is.

Proving the theorem by induction (10:17)

The proof starts with the trivial case of a one-move game, where the player obviously picks the best available outcome. The inductive step treats a longer game as an initial move followed by smaller sub-games; since each sub-game (by the induction hypothesis) already has a solution, the first mover can just pick the sub-game with the best solution. Chaining this argument from length 1 upward proves the theorem for games of any finite length.

Applying the proof: a rock-removal game (17:06)

Students play a game where players remove a rock from a grid, deleting it and everything to its northeast, and the player who takes the last rock loses. Polak notes Zermelo's theorem guarantees this game has a solution for any grid size, and leaves finding that solution as an optional, harder challenge than Nim.

Defining perfect information and pure strategies (31:20)

Polak formally defines a game of perfect information and a pure strategy as a complete plan of action at every decision node a player might reach. A worked example shows a subtlety: a strategy must specify a choice even at nodes that a player's own earlier choice makes unreachable, so Player 1 in a simple four-node example actually has four strategies, not the three that intuition suggests.

Perfect information and market entry (40:27)

Comparing backward induction to a straightforward Nash equilibrium search on the same game reveals two equilibria: one matching backward induction, and one built on a strategy that would be foolish if ever actually played. Applying this to a market-entry game between an entrant and an incumbent, Polak shows that a Nash equilibrium where the incumbent "threatens" to fight relies on a threat that is not credible, since fighting would cost the incumbent money it would rather not spend.

Setting up reputation (1:01:56)

The lecture ends by noting that an incumbent facing many potential entrants in sequence, such as a firm with monopolies in multiple markets, might have a genuine reason to fight early entrants to deter later ones, previewing the reputation and chain-store paradox topics of the next lecture.

Before you watch

• Lecture 13 and 14's treatment of backward induction and game trees is assumed throughout.
• Familiarity with Nash equilibrium from earlier in the course is needed to follow the comparison between Nash equilibrium and backward induction.

Check your understanding

1. What three possible outcomes does Zermelo's theorem guarantee for a finite two-player game of perfect information?
2. In the inductive proof, why does knowing that all sub-games of length N or less have a solution guarantee that a game of length N+1 also has one?
3. Why does Player 1 in the worked strategy example have four strategies rather than three?
4. Why is the "out, fight" equilibrium in the market-entry game considered not credible, even though it is a Nash equilibrium?