Introduction to Zermerlo’s 1913 and 1927b

Paul B. Larson ^{∗}

August 13, 2008

Zermelo’s 1913 paper Über eine Anwendung der Mengenlehre auf die Theorie des Schachpiels [24] is an account of an address given to the Fifth International Congress of Mathematicians in Cambridge in 1912. It is often cited as the first mathematical analysis of strategies in games. While the paper claims to be an application of set theory, and while it would have appeared that way to Zermelo’s contemporaries, the set-theoretic notions in the paper have since become part of standard mathematical practice, and to modern eyes the arguments in the paper are more combinatorial than set-theoretic.^{1} The notion of “Zermelo’s Theorem” (usually described as a variant of “in chess, either White or Black has a winning strategy, or both can force a draw”) derives from this paper. Although statements of this sort follow from the claims made in the paper, Zermelo’s arguments for these claims are incomplete. As we shall see below, there are other gaps in the paper, one of which was fixed by Kőnig in his 1927 paper [12]. Kőnig’s paper also contains two paragraphs on arguments of Zermelo fixing this gap, using ideas similar to Kőnig’s.

In the beginning of the 1913 paper, Zermelo notes that although he will discuss chess, his arguments apply to a wider class of games. Initially he describes this class as those two-player games “of reason” in which chance has no role. In the second paragraph of the paper, he makes the assumption that the game has only finitely many possible positions (or, rather, invokes the fact that this is true of chess, where a position of the game consists of the positions of all the pieces plus the identity of the player to move next and information such as which players have castled^{2}), and in the third paragraph he says that the rules of the game allow infinite runs, which should be considered ties. In the first paragraph he mentions that there are many positions in the game of chess for which it is known that one player or the other can force a win in a certain number of moves, and proposes investigating whether such an analysis is possible in principle for arbitrary positions.

∗The author is supported in part by NSF grant DMS-0401603. Dr. Nicole Thesz of Miami University and Dr. Burkhard Militzer of the University of California at Berkeley helped with some original sources in German. Our historical remarks rely heavily on [5], [9] and [18].

1As an example of how set-theoretic language was percevied at the time (and even much later), note that von Neumann and Morgenstern spend Sections 8-10 of [21] on the importance of set theoretic notions for studying games.

2If one includes the list of previous moves then the set of positions becomes infinite.

Zermelo’s analysis begins by letting P denote the set of all possible positions of the game, and letting P^{𝔞} denote the set of countable sequences of positions, finite or infinite. Fixing a position q, he lets Q be the set of all sequences in P^{𝔞} starting with q, such that, for each successive pair of positions in the sequence the latter member is obtained by a legal move from the former, and such that the sequence either continues infinitely or ends with a stalemate or a win for one player or the other. Zermelo notes that given a position q and a natural number r (Zermelo is not explicit about whether the case r = 0 is to be included), White can force a win from q in at most r moves if and only if there is a nonempty set U_{r}(q) of members of Q such that each q in U_{r}(q) is a continuation of q in which White wins in at most r moves (starting from q), and such that for each q ∈ Q and each position in q where it is Black’s turn to move, and for each possible move for Black at that point, there is a q′ ∈ Q which agrees with q up to this point, and has the position resulting from Black making this move as its next member. In more modern terminology (appearing no later than [13]), Zermelo has introduced here a game-tree with root q of height at most r + 1, in which all terminal nodes are wins for White, and in which all nodes for which it is Black’s turn to move have successors corresponding to every move available to Black at that position. The existence of such a tree is indeed equivalent to the existence of a quasi-strategy^{3} for White guaranteeing a win in r moves or fewer: White simply plays to maintain the condition that the continuation of the game starting from q is an initial segment of a member of U_{r}(q).

Still fixing q and r, Zermelo notes that the union of all such sets U_{r}(q) would also satisfy the conditions on U_{r}(q). He calls this union Ū_{r}(q), and notes that as r increases the sets Ū_{r}(q) also increase under ⊆ (though of course they may eventually all be the same, and may all be the empty set). For each q such that Ū_{r}(q) is nonempty for some natural number r, Zermelo lets ρ_{q} be the least such r, and he lets U^{∗}(q) denote Ū_{ρ_{q}}(q). He also lets τ denote the maximum of the set of defined values ρ_{q}.

Zermelo lets t be the integer such that t + 1 is the size of P, and presents an argument to the effect that τ ≤ t. The idea behind this argument is that if some position is repeated during a play by a winning quasi-strategy for White, then one could adjust the quasi-strategy to play from the first occurrence of this position in the way that one played from the second, thus winning in fewer moves. This argument was later shown by Kőnig [12] to be incomplete, as it does not account for all possible sequences of moves for Black; that is, playing with the same strategy does not guarantee the same resulting sequence of moves.

For each q, Zermelo lets U(q) denote Ū_{τ} (q), and claims that U(q) being nonempty is equivalent to the assertion that q is a winning position for White. In fact, U(q) being nonempty is equivalent to the existence of some natural number r such that White has a quasi-strategy guaranteeing a win in r moves or fewer. Zermelo does not address in this paper what it means for a player to have a quasi-strategy guaranteeing a win without specifying an upper bound on the number of moves needed to win. Kőnig’s subsequent work [12] would show that in games in which each player has only finitely many moves available in each position, having a winning quasi-strategy in this more general sense implies having one with a fixed upper bound for the number of moves needed.

3A strategy for White specifies a move for White in each position obtainable by the strategy; a quasi-strategy merely specifies an acceptable set of moves (see [10]). The distinction is important when the Axiom of Choice fails, but is less important here, since P is finite.

Nonetheless, we will use the term “quasi-strategy” for the sets of sequences described by Zermelo in this paper.

Zermelo then defines sets V_{s}(q), analogous to U_{s}(q) except that the corresponding quasi-strategies merely guarantee that White does not lose in fewer than s moves, though they allow that White loses on the s-th move. So each V_{s}(q) is a set of members of Q such that each q in V_{s}(q) is a continuation of q in which White does not lose in fewer than s moves starting from q, and such that for each q ∈ V_{s}(q) and each position in q where it is Black’s turn to move, and for each possible move for Black at that point, there is a q′ ∈ V_{s}(q) which agrees with q up to this point, and has the position resulting from Black making this move as its next member. Again, the union V̄_{s}(q) of all such V_{s}(q) satisfies these conditions. Now, however, the sets V̄_{s}(q) are shrinking as s increases.

Zermelo now remarks that, given q, if V̄_{s}(q) is empty for any positive integer s, then, letting σ be the maximal s for which V̄ (s) is nonempty, σ ≤ τ (he also lets V^{∗}(q) denote V̄_{σ}(q) in this case). The argument for this is not given (Zermelo also reiterates here that τ ≤ t, which, as we noted above, is not satisfactorily demonstrated in this paper, but that issue does not affect this one.) The first missing claim is that if V̄_{s}(q) is empty, then Black has a quasi-strategy which guarantees a win in s − 1 moves or fewer, starting from q. Modulo precise notions of game and strategy, this fact is sometimes called determinacy for fixed finite length games of perfect information; indeed, this assertion is often called Zermelo’s Theorem, referring to the arguments in this paper (a generalization is called “the theorem of Zermelo-von Neumann” in [13]). Granting this point, one needs to see that if Black has a quasi-strategy guaranteeing a win in s − 1 moves or fewer, then he or she has a quasi-strategy guaranteeing a win in τ moves or fewer. Given the definition of τ this is clear for suitably symmetric games,^{4} but it need not hold in general. Finally, it is clear that if Black has a quasi-strategy that guarantees a win in τ moves or fewer starting from q, then V̄_{τ+1}(q) is empty.

Zermelo lets V (q) denote V̄_{τ+1}(q), and claims that V (q) being nonempty is equivalent to White being able to force a draw from the position q. This claim is missing the same steps as the corresponding claim for U(q) above. Given that the game is suitably symmetric, the statement that V (q) is nonempty is equivalent to the statement that White can delay a loss by any specified amount he or she chooses, which again by the subsequent work of Kőnig and the finiteness of chess means being able to delay a loss indefinitely.

The second-to-last paragraph of the paper provides a partial summary, and asserts in a roundabout manner that in chess, either one player or the other has a winning strategy, or both players can force a draw. Zermelo notes that in each position q, U(q) ⊆ V (q), and if U(q) is nonempty, then White can force a win from q. If U(q) is empty but V (q) is not, then White can force a draw (as we mentioned in the previous paragraph, this is true but not supported by the arguments in the paper). If both sets are empty, then White can delay a loss until the σ-th move, for the value of σ corresponding to q. Furthermore, the two sets U^{∗}(q) (in the case where White can force a win) and V^{∗}(q) (otherwise) make up the set of “correct” moves for White from the position q. Zermelo notes than an analogous situation holds for Black, so that there exists a subset W (q) of Q consisting of all continuations of the game (starting from q) in which both players can be said to have played correctly.

4That is, games where for every position where it is White’s term to move there is a position where is it Black’s turn such that the game trees below the two conditions are isomorphic.

Strictly speaking this is not true of chess, since it can only be White’s turn when the pieces are in their initial position.

The final paragraph of the paper notes that the paper gives no means of determining in general which player has a winning strategy from which positions in chess, and that, given such a method, chess would in some sense cease to be a game.

As mentioned above, Kőnig’s 1927 paper [12] points out that Zermelo’s argument for the statement τ ≤ t is incomplete. Kőnig’s proof of this statement uses the following statement, which had appeared in his 1926 paper [11] (as translated in [18] from [12]; see [6] for much more on the history of this statement): if E_{i} (i ∈ ℕ) are nonempty finite sets and R is a binary relation such that for each i ∈ ℕ and each x ∈ E_{i+1} there is a y ∈ E_{i} such that (y, x) ∈ R, then there exists a sequence ⟨x_{i} : i ∈ ℕ⟩ such that each x_{i} ∈ E_{i} and (x_{i}, x_{i+1}) ∈ R for all i ∈ ℕ (where ℕ denotes the set of natural numbers). This principle is now known as Kőnig’s lemma, often rephrased as “every infinite finitely-branching tree has an infinite branch.” Kőnig uses this principle to prove that if G is a game in which each player has only finitely many available moves at each point, and one player has a winning strategy in this game, then this player has a strategy guaranteeing a win within a fixed number of moves. Kőnig credits this application of his lemma to a suggestion of von Neumann.

Before publishing his paper, Kőnig wrote to Zermelo, pointing out the gap in Zermelo’s argument for τ ≤ t, and providing a correct proof. Zermelo then replied with a correct proof of his own. Zermelo’s 1927b consists of two paragraphs in the final section of Kőnig’s 1927 paper pertaining to Zermelo’s corrected proof.

The first paragraph was apparently written by Kőnig, summarizing Zermelo’s arguement. It contains a proof that if White can force a win from a given position within some fixed number of moves, then White has a winning strategy that guarantees a win in fewer than t moves, where t is the number of positions in the game where it is White’s turn to move (note that the definition of t has changed; this t is smaller than the t from [24], as we are counting only the number of moves that White makes). To show this, Zermelo lets m_{r}, for each positive integer r, be the number of such positions from which White can force a win in at most r moves, but cannot force a win in fewer moves (though Zermelo does not give a name for the set of such positions, let us call it M_{r}). Since the corresponding sets of positions are disjoint, and since there are only finitely many possible positions in the game, m_{r} is nonzero for only finitely many values of r. Furthermore, if p is a position from which White can win in at most r moves (for some r > 1) by first playing w_{1}, then there must be a response by Black such that the resulting position is in M_{r−1}, since from every such position White can win in at most r − 1 many moves, but if he could win in fewer moves from every such position, then White could win in fewer than r moves from the position p. Zermelo concludes that the set of values r such that m_{r} is positive is an initial sequence of the set of positive integers, so if λ is the largest integer r such that m_{r} is positive, then m_{r} ≥ 1 for all positive integers r ≤ λ. Then m = ∑_{r=1}^{λ} m_{r} is smaller than the number of positions in which it is White’s turn to play (since, for instance, Black can force a win from some such positions), so λ must be smaller than this version of t. This establishes that if p is a position from which White can force a win in at most r moves (for White), for some positive integer r, then r is less than the total number of positions in which it is White’s turn to move.

In the second paragraph, Kőnig quotes Zermelo directly. Zermelo gives a proof that if White has a strategy guaranteeing a win, then he has one guaranteeing a win in a fixed number of moves. This is shown by Kőnig using his lemma, and Zermelo’s argument uses the same idea (and implicitly includes a proof of the lemma). In brief, suppose that p is a position from which White cannot force a win in a fixed number of moves. Then no matter how White plays, there must be a move for Black such that White cannot force a win in a fixed number of moves from the resulting position (if each resulting position p′ were in some M_{r′}, then p would be in M_{r+1} for r the supremum of these values r′ – this uses the fact that each player has just finitely many possible available moves at each point). This observation gives a strategy for Black to postpone a loss forever, by always moving to ensure that the resulting position is not in any set M_{r}, contradicting the assumption that White has a winning strategy.

Kalmár [8] extended Kőnig’s analysis to games where there may be infinitely many possible moves at some points. In this paper he proved what is now known as Zermelo’s Theorem for these games, the statement that in each position of such a game, either one player or the other has a strategy guaranteeing a win, or both players can force a draw. His proof uses a ranking of nodes in the game tree by transfinite ordinals, which was to become an important method in descriptive set theory (see [10]). Using this method, he was able to show that if a player has a winning strategy in such a game, then he has one in which no position is repeated, thus realizing Zermelo’s idea from his 1913 paper.

Aside from the work of Kőnig and Kalmár, Zermelo’s 1913 paper would seem to have been forgotten for several decades after it was written. In the interval between Zermelo’s paper and Kőnig’s, Emile Borel published several notes on game theory (for example, [1, 2, 3]), none of which mentions Zermelo. Von Neumann’s work in game theory began during this period, and though he was informed of Zermelo’s work by Kőnig,^{5} he does not cite it in his 1928 paper [20]. Zermelo’s 1913 paper is not mentioned in von Neumann and Morgenstern’s book [21], which is often cited as the birthplace of game theory. Many authors credit the birth of game theory to some combination of Borel, von Neumann and Morgenstern (for instance, [15, 23, 19, 22, 7, 17, 16], and among these only [15, 23, 7] credit Borel). Aside from the work of Kőnig and Kalmár, the earliest citation of Zermelo’s 1913 paper that we have been able to find is Kuhn’s paper [13]. Kuhn credits Zermelo with proving that “a zero-sum two-person game with perfect information always has a saddle-point in pure strategies.” As we have seen, the argument that Zermelo gives for this fact in his 1913 paper is incomplete. Although Zermelo’s focus was on other issues, it seems fair to say that this fact is the most significant contribution of his paper.

References

[1] E. Borel, La théorie du jeu et les équations intégrales à noyau symétrique, Comptes Rendus Academie des Sciences, Vol. 173, 1921, pp. 1304-1308; English translation in [4]

[2] E. Borel, Sur les jeux où interviennent l’hasard et l’habileté des joueurs, Théorie des Probabilitiés, Paris : Librairie Scientifique, J. Hermann, 1924, pp. 204-224; English translation in [4]

[3] E. Borel, Sur les systèmes de formes linéaires à determinant symétrique gauche et la théorie générale de jeu, Comptes Rendus Academie des Sciences, Vol. 184, 1927, pp. 52-54; English translation in [4]

[4] M.A. Dimand, R.W. Dimand, eds., The Foundations of Game Theory, Aldershot: Edward Elger, 1997

[5] H.-D. Ebbinghaus, Ernst Zermelo. An approach to his life and work, Springer, 2007

[6] M. Franchella, On the origins of Dénes Kőnig’s infinity lemma, Arch. Hist. Exact Sci. 51 (1997), 3-27.

[7] A.J. Jones, Game Theory : Mathematical Models of Conflict, Horwood Publishing Limited, 2000

[8] L. Kalmár, Zur Theorie der abstrakten Spiele, Acta. Sci. Math. Szeged 4 (1928/1929), 65-85; English translation in [4]

[9] A. Kanamori, Zermelo and set theory, Bulletin of Symbolic Logic 10 (2004) 4, 487-553

[10] A.S. Kechris, Classical Descriptive Set Theory, Springer-Verlag, 1995 [11] D. Kőnig, Sur les correspondances multivoques des ensembles, Fund. Math.

5According to Kőnig in a 1927 letter to Zermelo, see [5].

8 (1926), 114-134

[12] D. Kőnig, Über eine Schlussweisse aus dem Endlichen ins Unendliche, Acta Sci. Math. Szeged 3 (1927), 121-130

[13] H.W. Kuhn, Extensive games the problem of information, in [14], 193-216

[14] H.W. Kuhn, A.W. Tucker, eds., Contributions to the Theory of Games, vol. 2, Annals of Mathematical Studies 28, Princeton University Press, Princeton, N. J., 1953

[15] H.D. Luce, H. Raiffa, Games and Decisions : A study of the Behavioral Models Project, Bureau of Applied Social Research, Columbia University, 1957

[16] E. Mendelson, Introducing Game Theory and Its Applications, Chapman & Hall/CRC, 2004

[17] K. Ritzberger, Foundations of Non-Cooperative Game Theory, Oxford University Press, 2002

[18] U. Schwalbe, P. Walker Zermelo and the Early History of Game Theory, Games and Economic Behavior 34 (2001), 123-137

[19] Straffin, Game Theory and Strategy, Mathematical Association of America, 1993

[20] J. von Neumann, Zur Theorie der Gesellschaftsspiele, Math. Annal. 100, 295-320; English translation in [4]

[21] J. von Neumann, O. Morgenstern, Theory of Games and Economic Behavior, Princeton, Princeton University Press 1943

[22] N.N. Vorob’ev, Foundations of Game Theory : Noncooperative Games, Birkhauser, 1994

[23] F.C. Zagare, Game Theory : Concepts and Applications, Quantitative Applications in the Social Sciences, Sage Publications, 1984

[24] E. Zermelo, Über eine Anwendung der Mengenlehre auf die Theorie des Schachpiels, Proc. Fifth Congress Mathematicians, (Cambridge 1912), Cambridge Univ. Press 1913, 501-504

Department of Mathematics and Statistics Miami University Oxford, Ohio 45056 USA larsonpb@muohio.edu