1
$\begingroup$

Zermelo's theorem states that in a finite game, with two players, $a$ and $b$, where each player takes turns, the following is true:

  1. Player $a$ has a winning strategy,
  2. Player $b$ has a winning strategy,
  3. Both players have an at-least-drawing strategy.

Now consider the following game: Either player $a$ wins or player $b$ wins but they cannot draw, so the game continues indefinitely until one of them wins.

Does Zermelo's theorem hold?

My initial thought and an obvious solution is: No, because the Zermelo's theorem specifically states that the game must be finite. However, I'm struggling to see why this doesn't work like so:

  1. Player $a$ has a winning strategy,
  2. Player $b$ has a winning strategy,
  3. Both players have an at-least-not-winning strategy (i.e. game continues forever).

Can someone provide a proof for why this extension of Zermelo's theorem does not work in this new game?

$\endgroup$
  • 1
    $\begingroup$ You want at-least-not-losing in 3. $\endgroup$ – Ross Millikan Jan 19 '18 at 15:36
  • 1
    $\begingroup$ I think those three things should be stated as "at least one of the following is true." The way it is stated sounds like all are claimed to be true. $\endgroup$ – Michael Jan 19 '18 at 15:48
  • $\begingroup$ What if the game deterministically has each player scoring 0 points per round, and the game continues until one player accumulates 10 more points than the other. So the game never ends and nobody ever wins. $\endgroup$ – Michael Jan 19 '18 at 15:51
  • $\begingroup$ First, Zermelo's theorem applies to games with finitely many positions, the game need not be finite. Second, so who is going to win if the game is going on forever? $\endgroup$ – Michael Greinecker Jan 20 '18 at 3:03
1
$\begingroup$

Something similar, but not quite identical, to what you want is true.

It is not possible to guarantee strategies which ensure that the game continues forever, if neither has a winning strategy. For example, consider the really sad game whose only moves for either player are "pass" or "resign." Neither player has a winning strategy - all they can do is refrain from resigning - but neither player can ensure that the game goes on forever, either (since each player could resign at any given moment).

However, what we can guarantee is that at least one player has a non-losing strategy (i.e. when they play according to that strategy, either they win or the game continues forever). This follows from the Gale-Stewart theorem; this is a significant strengthening of Zermelo's theorem, and represented the first real step into the land of infinite games.

Call your game $G$. Consider the related game $G^*$ where players $a$ and $b$ play the game you've described, and if it goes on forever then player $b$ is said to win. This is an example of an open game, and the Gale-Stewart theorem says that every open game is determined. A winning strategy for $a$ in $G^*$ is also a winning strategy for $a$ in $G$; meanwhile, a winning strategy for $b$ in $G^*$ is a non-losing strategy for $b$ in $G$. So we see that one player or the other has a non-losing strategy in your game $G$, as desired.

So in fact we have the following "lopsided" determinacy principle:

In a (perfect-information, $2$-player) no-draws-possible but not-necessarily-terminating game $G$, either player $a$ has a winning strategy or player $b$ has a non-losing strategy.


There are essentially two proofs of the Gale-Stewart theorem. One is a "ranking" argument, where we assign nodes in the "game tree" ordinals (or "$\infty$") in a recursive way. The other "magical" one is the following: looking at the game tree, color a node red if player $a$ has a winning strategy from that node and blue otherwise. Now show that if the root of the game tree (= the beginning of the game) gets colored blue, then $b$ has a non-losing strategy. HINT: think about what color the nodes directly above a given blue node can get, based on the parity of that node (even length or odd length).

There are much, much stronger determinacy principles out there - see in particular Borel determinacy, due to Martin. The general study of determinacy principles is a major topic in set theory and descriptive set theory, and has surprising connections to large cardinals and "regularity" properties (like measurability) of sets of real numbers. See this essay of Larson.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.