One of my favorite game theoretic insights is that rational players should not play chess: The outcome is already determined at the beginning of the game. This is what’s usually called Zermelo’s Theorem, but it is a common rant among game theorists that this is a misattribute. Zamir, Maschler and Solan, for example, in their recent game theory textbook credit the theorem to von-Neumann, citing his minimax paper. Following a conversation with David Schmeidler, who suggested that Zermelo might have used this theorem but didn’t make a fuss over it because it’s so trivial, I decided to look at Zermelo’s paper myself. This is possible thanks to translation from German by Ulrich Schwalbe and Paul Walker.
A game in Zermelo’s setup is given by a finite set of positions. A position in chess includes the configuration of the board, whether White or Black has to move, whether there was castling, etc.. A history (Zermelo called it an endgame) is a sequence of positions that can follow each other in accordance with the rule of the games. An history can be finite, ending with a position which is win or loss to one of the players, but can also be infinite, in which case the outcome of the game is a draw. (In a game like chess there is also the possibility of a finite history that ends with a stalemate. This issue has no independent interest so, as mathematicians will do, we ignore it.)
What is usually called Zermelo’s Theorem in the literature now becomes:
Theorem 1 Let be a position. If there is a number such that the length of every history starting with is smaller than , then one and only one of the following holds:
- White can force a win for White.
- Black can force a win for Black.
I (and Zermelo) do not explicitly define strategies, but `force’ means what you think it means: That the player has a strategy such that every history which is consistent with this strategy achieves the desired outcome.
Zermelo’s theorem is true, though I hasten to add that the assumption about the existence of such a number  is unnecessary. However, this theorem is not the subject matter of Zermelo’s paper. The question that Zermelo asks is this:
for some natural number , what properties does a position q has such that White, independently of how the Black plays, can force a win in at most r moves?
(Apparently Zermelo was motivated by the kind of `chess problem’ which bound the number of moves until a checkmate)
So, Zermelo clearly did not set out to prove his eponymous theorem. But was he aware of it ? I guess the answer depends on what you mean by being aware of a mathematical statement (were you aware of the fact that any even number greater than 2 can be written as a sum of a prime number and an even number before you read this sentence ?). But I do believe that some of the logical implications in Zermelo’s paper only make sense if you already assume his theorem. Here is one such implication:
The numbers for which are either infinite or , since the opponent, if he can win at all, must be able to force a win in at most moves
Here are some sets histories of length and Zermelo shows that iff White can hold out until the -th move without losing. The argument makes sense only if you assume that (which, according to what Zermelo when White cannot postpone losing in moves) implies Black can force winning in moves, which is the essence of the theorem.
My conclusion ? I believe that Zermelo and his readers were taking what is now called Zermelo’s Theorem for granted, though they didn’t recognize its significance yet.
2 comments
February 15, 2010 at 5:25 pm
Computability in game theory « The Leisure of the Theory Class
[…] of the games. This is a finite game, which can be solved by a background induction. By the so called Zermelo’s Theorem, the game is determined: One of the player has a winning strategy. The […]
May 6, 2010 at 5:40 pm
Infinite past « The Leisure of the Theory Class
[…] and Morgenstern are not the only players here. Zermelo, for example, did not think about games in terms of their normal forms. And, as an interesting discussion over at Thoughts, Arguments and Rants blog (which, because of my […]