Zermelo's theorem (game theory)

For Zermelo's theorem in set theory, see well-ordering theorem.

In game theory, Zermelo’s theorem, named after Ernst Zermelo, says that in any finite two-person game of perfect information in which the players move alternatingly and in which chance does not affect the decision making process, if the game cannot end in a draw, then one of the two players must have a winning strategy.

Formal definition

More formally ...

Every finite extensive-form game exhibiting full information has a Nash equilibrium that is discoverable by backward induction. If every payoff is unique, for every player, this backward induction (starting from the end of the game and then working backwards to its beginning) solution is unique.

A little history

Zermelo's paper, published in 1913, was originally published only in German. Ulrich Schwalbe and Paul Walker faithfully translated Zermelo's paper into English in 1997 and published the translation in the appendix to Zermelo and the Early History of Game Theory. Zermelo considers the class of two-person games without chance, where players have strictly opposing interests and where only a finite number of positions are possible.

Example

When applied to chess, Zermelo's Theorem states "either white can force a win, or black can force a win, or both sides can force at least a draw".

Further reading

• Zermelo and the Early History of Game Theory