Theory of Games 85

Here is the game tree of a game to be played by Alice and Bob. Play starts at the top;

Alice makes the first choice, then Bob, and then Alice again. The winner is indicated in

the resulting final node. Who can force a win?

Alice Bob Bob Bob Bob Alice Alice Bob

Alice

chooses

Alice

chooses

Alice

chooses

Alice

chooses

Bob

chooses

Bob

chooses

start

Alice

chooses

A strategy in such a game is a function that tells a particular player, from any node, which

child node to select from that position. A play of the game accords with a strategy for a

particular player if at every node when it was that player’s turn, he or she did indeed select

the child node that the strategy specified. A strategy is a winning strategy for a player if

every play that accords with that strategy results in a win for that player. A strategy is a

drawing strategy for a player if every play that accords with that strategy results in either a

win for that player or a draw.

7.7 The fundamental theorem of finite games

We are now ready to prove the fundamental theorem in the theory of finite games, due

to Zermelo in 1913. I shall give three independent proofs for this central game-theoretic

result. First, consider the case of games without draws.

Theorem 60 (Fundamental theorem of finite games). In any finite two-player game of

perfect information, without draws, one of the players has a winning strategy.

First proof. This proof uses the back-propagation method, a form of backward induction.

Consider the underlying game tree T . We intend to label the nodes of the game tree with

the player who can win if play should start from that position. The terminal nodes are

already labeled. Working backward, consider a node u all of whose children are already

labeled. If it is Alice’s turn to play and there is a child node labeled Alice, then Alice