ZERMELO’S THEOREM AND STRATEGY STEALING

ALEXANDER WAUGH

In its most basic form, game theory is the quantitative study of incentive and
interaction. While our brief introduction to "games" has been largely focused on
the applications of game theory, there is a looming question of "what exactly is be-
ing applied?". Just as in many other quantitative pursuits, there is a mathematical
framework underlying all of game theory and consequently all of its applications. One
of the earliest pieces of this framework is a result called Zermelo’s theorem which in-
formally states that in every two player game of a certain type either (i) player 1 has
a winning strategy, (ii) player 2 has a winning strategy, or (iii) both have unbeatable
strategies. While intuitively obvious, there are already ambiguities in this statement
which make it far from a useful quantitative tool. For example, what is meant by "a
certain type" and "winning strategy"? This paper will proceed to give a quantitative
explanation interpretation of these ambiguities and explore the applications, both
practical and theoretical, which arise from Zermelo’s theorem.

Placing these qualms over definitions aside for the moment, the implication of Zer-
melo’s theorem is already far reaching even without having a precise statement of
the result. It shows that if Γ is a two-player game of "a certain type" then at any
stage of the game there must be a player which has an advantage over the other (i.e.
a "winning" strategy) or both players must be in an "equal position" strategically
(leading to a draw). Note here that Zermelo’s theorem is not stating that games of
"a certain type" must end in a draw or with one of the players winning (this will
be a consequence of the type of game we consider). Rather it is a statement about
the possible strategies the two players may posses relative to each other at any time
during the game.

Now, to make precise what is meant by "games of a certain type", it is first pru-
dent to introduce some definitions. Perhaps most important, a game is defined as a
conflict involving gains and losses between two or more opponents who follow formal
rules. This is perhaps an unsatisfying definition as it again prompts questions as to
what is meant by specific phrases. However, to stop ourselves from "travelling down
the rabbit hole" of definitions, we take the above definition as an axiom with the
understanding that these phrases will be made precise in the context of the game
we are considering. Continuing, a game is said to be of perfect information if each
player, when making any decision, is perfectly informed of all the events that have
previously occurred, including the initial states. That is, every player in the game is
aware of the history in the game and there is no ambiguity as to what has occurred
during the game.1 Finally, a game said to be finite if each player has a finite number
of moves, the number of players is finite, and the game terminates in a finite amount
of time. With this terminology, the modern interpretation of Zermelo’s theorem is

Date: May 18, 2020.

1Checkers is an example of such a game while Poker and Blackjack are not.
1
2 ALEXANDER WAUGH

"Every two player finite game of perfect information without chance where players
alternate taking turns must end in either a draw or with one of the players winning."

The notion of a winning strategy is much easier to make precise. For players A
and B let U and V be their respective payoff functions.2 Given two strategies ξ and
η and payoffs U (ξ, η), V (ξ, η), we call a strategy ξ unbeatable (resp. winning) if
U (ξ, η) ≥ V (ξ, η) (resp. U (ξ, η) > V (ξ, η)) for any other strategy η. Note that while
at first it may seem that this definition is the same as strategic dominance, it differs
in a very important aspect. Namely, in this notation, strategic dominance may be
stated: if ξ and ν are strategies for player 1, then strategy ξ is said to dominate
strategy ν if U (ξ, η) ≥ U (ν, η) for all strategies η of player 2. With this it becomes
apparent that strategic dominance is a statement about a single player’s payoffs rel-
ative to their set of strategies while winning strategies are a statement about how
the two players strategies compare to one another. Furthermore, giving this relation
the name "winning strategy" is appropriate here only if it is stipulated that the pay-
offs are only concerned with who wins the game. In this way winning/unbeatable
strategies reflect the potential outcome of the game in terms of wins, losses, and ties
as stipulated by the formal rules of that particular game without regards to how the
players may view such an outcome personally.

In relation to other game theoretic concepts discussed in Honors 220B, Zermelo’s

theorem is most closely related to the fundamentals of strategies and "solving" games
with one major caveat. Namely, solving a game usually connotes an understanding of
a strategy one uses to win while Zermelo’s theorem does not specify any such strategy.
Mathematically, Zermelo’s theorem is an example of an existence result that is non-
constructive. So, despite being a statement about winning and unbeatable strategies,
it does not give any indication of how a player may find/construct such a strategy.
For example, chess (with the 50 move limit) is easily seen to be a game satisfying
the above conditions and by Zermelo’s theorem either exactly one player must have
a winning strategy or both players have unbeatable strategies at any stage of the
game. However, even with a finite move limit, it is still computationally difficult to
determine such a strategy for either player and impossible for the average chess player
to do so during a game.

In lieu of reiterating a general proof of Zermelo’s theorem, which would require more
mathematical framework than has been established, it is rather easy to give a brief
intuitive argument why it is a reasonable result. Consider a game of two players, A
and B, satisfying the necessary conditions. Since the game is finite it must either
end in a draw or with one of the players winning.3 Suppose player A does not have
a winning strategy. Then whatever strategy A chooses, player B must always have
a strategy which prohibits A from winning. That is, if U and V are the payoff func-
tions for players A and B respectively then there exists a strategy {ξi }N i=1 for player
B such that V (ν, ξi ) ≥ U (ν, ξi ) for each strategy ν for player A and each 1 ≤ i ≤ N .4
2That is, U and V are functions from the set of strategies for each respective player to the real
numbers.
3Recall that the statement of Zermelo’s theorem is a statement about winning/unbeatable strate-
gies not about whether the game ends in a draw or with one player winning
4Here N is an upper-bound of the length of the finite game. Such a bound exists because it will
never take more moves than there are positions in the game to reach a winning position. To see
 ZERMELO’S THEOREM AND STRATEGY STEALING 3

Thus B has at least a strategy which leads to a draw (if the inequality were strict
B would have a winning strategy, but the weak inequality only ensures that B can
draw the game). This strategy ensures that B will not lose. Similarly, if B has no
winning strategy then A must have a strategy that results in a draw. Consequently,
if neither player has a winning strategy they must each have an unbeatable strat-
egy. Furthermore, both players cannot have a winning strategy as this would imply
U (ξi , νi ) > V (ξi , νi ) and V (ξi , νi ) > U (ξi , νi ) for any strategies {νi } for player 2 which
is impossible. So either exactly one player has a winning strategy or both players
have unbeatable strategies.

An interesting subcase of this theorem comes in examining games which cannot end
in a draw. Under this assumption, the theorem implies that one of the two players
must always have a winning strategy. While in practice the player with the win-
ning strategy may change as the game progresses, an interesting question to ask is
which player at the outset possesses the winning strategy. To answer this we begin
by examining John Nash’s game of Hex. The game of Hex is played on an 11 × 11
hexagonal board given in figure 1. Players then take turns placing markers on un-

Figure 1

occupied spaces in an attempt to connect opposite sides of the board. This game
satisfies all the conditions of Zermelo’s theorem because it is naturally finite, players
alternate turns, chance is not involved, and there is no hidden information. Moreover,
this game cannot end in a draw.5 Returning to our question, the above discussion
implies that one of the players must have a winning strategy and, in fact, this is
always the first player. To see this, suppose A and B are playing Hex and player A
goes first. Furthermore, suppose player B has a winning strategy against player A’s
first move. Then on player A’s second move, ignoring their piece that has already
placed, A finds themselves in the same situation as player B on their first move: a
single "enemy" marker on the board. The first player may then make their moves
according to the winning strategy for B, unless the strategy calls for A to place a
this, assume for contradiction that a player can win in a number of moves larger than the number of
positions. Then at least one winning position must have appeared twice. So the player could have
implemented the same strategy at the first occurrence as they had at the second and won in fewer
moves than there are positions.
5This would be a digression that would merit its own paper. There are two common ways of
proving this: (i) considering the game board as a finite graph and decompose a filled board into
subgraphs based on the marker colors. The result then follows from graph theory. (ii) One can also
show that the game board is equivalent to a certain lattice in [0, k]2 ⊂ R2 and use the Brouwer’s
fixed point theorem to show that there must always be a path on a filled board connecting opposite
sides of the square. The interested reader is referred to [2]
4 ALEXANDER WAUGH

marker in the position they have already used. If this is the case, player A may put
a marker in any random unused position with the net effect that this new piece will
now be the "ignored" marker with respect to player B’s strategy. For all subsequent
moves player A can effectively "steal" the winning strategy from player B. Since
Zermelo’s theorem shows that both players cannot have a winning strategy B could
not have had a winning strategy to begin with. Consequently, under optimal play,
player A will always win against B in Hex. This analysis, now formally known as
the "strategy stealing argument", was first introduced by John Nash in studying Hex
and actually has an analog in a larger class of games satisfying Zermelo’s hypotheses
known as strong positional games.

Again beginning with definitions, a strong positional game is a game with perfect
information described by

(1) A finite set of elements, X, usually called "the board".

(2) A family of subsets F, usually called "the winning-sets".
(3) A criterion for winning the game.
where players alternate turns to claim previously unclaimed positions. The winner
is the first player to occupy a complete winning set. Hex is obviously a game of this
form, but observe that this definition does not stipulate that such games cannot end
in a draw. In this more general case, where draws are possible, the first player is
no longer guaranteed a winning strategy but rather a drawing strategy. This can be
illustrated in Tic-Tac-Toe by noting that since the game can end in a draw Zermelo’s
theorem implies either the first player has a winning strategy or both players have un-
beatable strategies. That is, in Tic-Tac-Toe, with optimal play, the second player will
never win. While this is obvious to anyone who has ever played the game, the power
of this analysis comes in abstracting to a much larger game. For example, consider
Ultimate Tic-Tac-Toe.6 By the above logic, optimal play results in the second player
never having a winning strategy. However, in practice, the second player will almost
always develop a winning strategy because the extensive form of the game is so large
that the first player cannot hope to play optimally (without computer assistance).

While none of these results actually inform a player how to win a game, this analy-
sis does play a vital role in game design. In the instance of Tic-Tac-Toe, the game
is too simple by virtue of it being strategically "too small". This then results in a
trivial game where a draw almost inevitable. However by sufficiently complicating
the game, ultimate Tic-Tac-Toe is rather interesting because a winning strategy is
not entirely obvious to either player during the early stages of the game. This then
presents a question to game designers of when a game is "sufficiently complicated"
enough as to not be trivial but simple enough to be comprehensible to the general
public. An example of this trade off is in the early European game Rithmomachy.
The name literally translating as "The Battle of Numbers", this game is based upon
a complicated mathematical strategic system. Consequently, the game was beyond
the comprehension of the general public during the time of its creation. While Rith-
momachy now is thought to be more akin to a learning tool than a game for leisure,
the idea that it was designed for intellectual crowds showcases perfectly the inverse
relation between accessibility to a game and how complex the game is. In much the
6See [6]
 ZERMELO’S THEOREM AND STRATEGY STEALING 5

same way, modern game designers still need to consider Zermelo’s theorem and the
strategy stealing argument to create a game that is nontrivial but not so complicated
that they alientate people who will not be able to comprehend the game mechanics.

A more theoretical consequence of Zermelo’s theorem is that it implies that a game

may be solved by backwards induction. As the games are of perfect information,
finite and without chance where players alternate turns, the game tree is representa-
tive of every possible outcome in the game given a set of decisions for each player.
Beginning on a leaf to the game tree where player 1 wins, we may consider the last
decision made by a player (i.e. move backwards one step in the tree) and consider the
subgame at that node. By Zermelo’s theorem, player 1 has a winning strategy, player
2 has a winning strategy, or both players have unbeatable strategies. However since
we supposed that this node is connected to a leaf were player 1 wins, player 1 has
a winning strategy. Now proceeding by induction backwards through the game and
applying Zermelo’s theorem to each subgame it is possible to find a strategic profile
that ends in the player 1 win we began with. While this theoretically states that
every game satisfying Zermelo’s hypothesis is solvable this method is impractical.
Even for a relatively simple game such as Tic-Tac-Toe the game tree has 9! nodes.
For a game such as chess the number of nodes in the game tree will be intractable
even with computer aid.

As has been shown, Zermelo’s theorem is a theoretical necessity in analyzing the

games it applies to and even gives a method for solving such a game. However
even by strengthening our analysis with the strategy stealing argument, the practical
applications of Zermelo’s theorem are limited to games small enough that any aver-
age adult could solve them without any knowledge of game theory. While this may
appear troublesome at first, the theoretical framework for game theory is a mathe-
matical construct and is therefore concerned more with proving results rather than
their application. In this light, it does not matter that Zermelo’s theorem has little
to no practical application as its purpose is to expand our understanding of finite
games of perfect information. By that measure, it fulfills its purpose flawlessly and
by the above analysis, proves invaluable to the study of game theory.
6 ALEXANDER WAUGH

References
[1] Cornell Mathematics Explorers’ Club. Strategy Stealing. url: http://pi.math.
cornell.edu/~mec/2008-2009/ChorHangLam/strategy.html.
[2] MIT Mathematics Department. Hex. url: http://web.mit.edu/sp.268/www/
hex-notes.pdf.
[3] Dogonell the Juggler. Game of the month: Rithmomachy. url: http://www-
cs.canisius.edu/~salley/SCA/Games/rithmomachy.html.
[4] Igor Evstigneev Rabah Amir. On Zermelo’s Theorem. url: https://arxiv.
org/pdf/1610.07160.pdf.
[5] Paul Walker Ulrich Schwalbe. Zermelo and the Early History of Game Theory.
url: http://abel.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf.
[6] Ultimate Tic-Tac-Toe. url: https://en.wikipedia.org/wiki/Ultimate_tic-
tac-toe.
 REFERENCES 7

1. Reflection
My choice of topic largely stems from my interest in the mathematical underpin-
nings of game theory. I found the first part of the course very fascinating with regards
to how we can quantify and analyze incentive systems. My research into Zermelo’s
theorem and the strategy stealing argument are interesting to me because they pro-
vide a very broad result which applies to a very large class of games without having to
know the specific implementations of the games themselves. That is, the arguments
apply equally as well to Tic-Tac-Toe, chess, checkers, Hex, etc... with only needing
minimal knowledge of how the game is played. While I have grown accustomed to
such generalizations by studying mathematics, I was very surprised at the implica-
tions one can draw from Zermelo’s theorem and strategy stealing. In particular, I
found the fact that in many games the second player is at a disadvantage by virtue
of being the second player very interesting. I would not have guessed that the second
player is always in a position to draw or lose in examining these games independently.
However, this is were I found the power of the results I examined most apparent, in
that they "cut through" the unnecessary details of a game to get at the core of the
interaction. Without the extra details the elements I examined in the paper seem
very apparent.

Another reason I chose this topic is that it gives a means of examining why backwards
induction is a valid method of solving a game; a result which was very important in
the prior papers study of Centipede. While intuitively obvious that backwards induc-
tion will result in a solution to the game (and allow one to find subgame perfect Nash
equilibria) it was not mathematically clear to me at the time of writing the other pa-
per why the inductive step would allow us to continue backwards through the game
and still be able to find a winning/unbeatable strategy for a given player. While the
game of Centipede is simple enough to get around these details pretty easily it is not
entirely obvious why this should be true for a more complicated game with more than
two branches from a node in the game tree. Zermelo’s theorem fills in the details for
this argument by showing that in every subgame there is a strategy resulting in one
of the three outcomes described and, in sum, makes completely rigorous the idea of
backwards induction. This result came as a surprise as it was not a detail I originally
thought to be a big part of Zermelo’s theorem.

With regards to my prior views on Zermelo’s theorem and strategy stealing, I feel
that I have gained a better understanding of mathematical game theory and interac-
tions of the above type. Not knowing anything rigorous about mathematical game
theory prior to starting this paper, my prior views on the topic were restricted only
to the surface level of knowing the statement of the theorem. As such, my prior
views have not really changed over the course of writing this paper. My views have
certainly developed into a more sophisticated understanding of the implications of
these theorems both in practical instances and in analyzing classes of games. With
respect to the former, I now have a better understanding as to why Tic-Tac-Toe and
other such "trivial" games always end in a draw (that is, reasons other than that
which I have from experience in playing the games). As for the former, I now have a
better understanding of what it means to solve a game and the difficulties one may
have when trying to find a solution (i.e. we know a solution exists but it is compu-
tationally very difficult to find it).
8 REFERENCES

While the average person has no need for the theoretical aspects of my paper (i.e.
all games Zermelo’s theorem are concerned with are solvable, etc...) I do think that
the implications of these results should be taught to the general public as a means of
better understanding interactions. The results pertaining to the second player never
having a winning strategy I find particularly important because, while many people
know from experience the second player will never win in certain games, it can be
enlightening to see how the result generalizes. Similarly, I think the strategy stealing
argument is very fundamental to understanding antagonistic games which Zermelo’s
theorem is concerned with. If I were to name a demographic which I think would
benefit most from understanding these results, I would have to say high school seniors
or first year undergraduates. While many majors do not require this information, I
think these results are one of the pieces of information one should see at least once
in their life.

Finally, another topic that I considered for this paper regarded analyzing the pu-
rification theorem. The theorem may be framed as follows: Almost all mixed strat-
egy Nash equilibria in a complete information game are the limit of a pure strategy
Bayesian Nash equilibria in an incomplete game that converges to the complete in-
formation game. The proof of this theorem would take the paper too far afield so a
sketch would have been included and utilized to examine some games such as Hawk-
Dove. The importance of such a result is it answers, "what compels a player, when
indifferent among some of his pure strategies, to randomize over them precisely so as
to make the other players indifferent among some of their pure strategies." Moreover,
this theorem shows that we can think of the original game of perfect information as
a limit of "nearby" games with a small amount of uncertainty (i.e. Bayesian games).
As a Bayesian Nash equilibrium is a pure Nash equilibrium based upon the beliefs
rather than absolute certainty, a mixed Nash can be interpreted as the probability of
facing the opponent in either possible game.

This topic is still very interesting to me but I lacked sufficient knowledge to dis-
cuss Bayesian probabilities and analyze such games in any rigorous/intutive manner.
I was drawn to this topic for much the same reasons I was drawn to my chosen topic
but my interest in the purification theorem stems also from attempting to understand
why we use our opponents payoffs in calculating a mixed Nash equilibrium. The pu-
rification theorem recasts mixed Nash as a probability of facing the opponent over a
set of games (i.e. the opponent could be player on one of n possible strategic forms
for the game, each with different payoffs). In this way, a mixed Nash equilibrium
can be thought of as the probability a player will be facing their opponent on a par-
ticular strategic form which has a pure Nash equilibrium. While I did not research
this project for this paper I plan to look into Bayesian probablity in the future so
that I may understand how the purification theorem works both theoretically and in
practice.