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.[1]

Formal definition

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)[2] solution is unique.[3]

Publication history

Zermelo's original paper describing the theorem, Uber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, was published in German in 1913. Ulrich Schwalbe and Paul Walker translated Zermelo's paper into English in 1997 and published the translation in the appendix to Zermelo and the Early History of Game Theory.[4]

Details

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. Although in the game only finitely many positions are possible, Zermelo allows infinite sequences of moves since he does not consider stopping rules. Thus, he allows for the possibility of infinite games. Then he addresses two problems:

  1. What does it mean for a player to be in a 'winning' position and is it possible to define this in an objective mathematical manner?
  2. If he is in a winning position, can the number of moves needed to force the win be determined?

To answer the first question, Zermelo states that a necessary and sufficient condition is the nonemptyness of a certain set, containing all possible sequences of moves such that a player wins independently of how the other player plays. But should this set be empty, the best a player could achieve would be a draw. So he defines another set containing all possible sequences of moves such that a player can postpone his loss for an infinite number of moves, which implies a draw. This set may also be empty, i. e., the player can avoid his loss for only finitely many moves if his opponent plays correctly. But this is equivalent to the opponent being able to force a win. This is the basis for all modern versions of Zermelo's theorem.

About the second question, Zermelo claimed that it will never take more moves than there are positions in the game. His proof is a proof by contradiction: Assume that a player can win in a number of moves larger than the number of positions. Of course, at least one winning position must have appeared twice. So the player could have played at the first occurrence in the same way as he does at the second and thus could have won in fewer moves than there are positions.

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".[5]

Notes

  1. ↑ http://hkumath.hku.hk/~ntw/EMB(giftedstudents_6-April-2008).pdf
  2. ↑ http://www.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf
  3. ↑ Mas-Colell, Whinston, Greene Microeconomic Theory
  4. ↑ http://www.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf
  5. ↑ http://www.gap-system.org/~history/Projects/MacQuarrie/Chapters/Ch4.html

External Links

This article is issued from Wikipedia - version of the Thursday, February 18, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.