# Infinite games: are they well defined?

It is just my curiosity about this question where we have an infinite game and (according to the answers) winning strategies for both players. I am familiar with terminating games only, and I am pretty sure that nonterminating ones can cause many paradoxes. As this is a community wiki mode, I would be happy to see formal definitions, existence of wining strategies as well as possible collisions.

Thanks in advance for keeping my mind finite!

-
I was about to ask something like this. :-) –  Andrea Ferretti Jul 16 '10 at 14:14
Nice new "thanks" tag! :-) –  Joseph O'Rourke Jul 16 '10 at 14:38
Wadim, you may want to take a look at the following paper by Bollobas, Leader, and Walters, where an example is giving of a ("continuous") game where both players have winning strategies: arxiv.org/abs/0909.2524 For "discrete" games, set theory has studied infinite games for a while, and they are an essential tool in modern research. A book like Jech's "Set Theory" should give you a nice overview. –  Andres Caicedo Jul 16 '10 at 14:46
BlueRaja's comment is correct if the sequence of moves is well-ordered, because then you can define the play of one strategy against another by induction along that well-ordering. But when the set of moves is not well-ordered, as in the "continuous" games mentioned by Andres Caicedo, then there may not exist a play of the game in which both players follow their strategies. In such a case, they might both have winning strategies. –  Andreas Blass Jul 17 '10 at 3:48
Actually Wadim, I think the conclusion of the question was that even though it it appears that $P$ has a winning strategy actually the proofs given were flawed and $L$ does. It turns out this is not a case of there being "winning strategies for both players". However, this doesn't mean that there isn't another game where both players have winning strategies. –  Mark Bell Jul 19 '10 at 21:46

A relatively general definition of an infinite, discrete "Gale–Stewart game" is the one used in Martin's proof of Borel determinacy [1]. More information about this type of game can be found in Kechris's Classical Descriptive Set Theory and in Jech's Set Theory.

Definition. We define a game $G(X,P)$ based on a nonempty set $X$ and a set $P \subseteq X^\omega$. The elements of $X$ are the moves of the game. A play of the game is a sequence $r = (r_0, r_1, r_2, \ldots)$. If $r \in P$ then we say that player I wins, otherwise we say that player II wins. Hence every play of the game has a winner. The informal interpretation of this game is as follows: player I chooses $r_0$, then player II chooses $r_1$, then player I chooses $r_2$, etc.

The way that the game is played is formally specified by the definition of a winning strategy. In the game $G(X,P)$, a strategy is just a function $s \colon \left ( \bigcup_{i \in \omega}X^i \right ) \to X$. Intuitively, the value of $s(\tau)$ is the move that should be played if the other player's moves up this this point are listed in the sequence $\tau$.

A winning strategy for player I is a function $f \colon \left ( \bigcup_{i\in\omega} X^{i} \right ) \to X$ such that player I wins any play of the form $$f(\langle \rangle),\: r_1, f(\langle r_1\rangle),\: r_3, f(\langle r_1, r_3\rangle), \ldots$$

A winning strategy for player II is a function $g \colon \left ( \bigcup_{i\in\omega} X^{i+1} \right ) \to X$ such that player II wins any play of the form $$r_0, \: g(\langle r_0\rangle),\: r_2,\: g(\langle r_0, r_2\rangle),\: r_4, g(\langle r_0, r_2, r_4 \rangle),\ldots$$

This set of definitions leads to a well-defined, non-paradoxical collection of games. It is impossible for both players to have a winning strategy for the same game, because the strategies can be played against each other. However, it is possible for neither player to have a winning strategy, and in fact ZFC proves that in the specific case $X = \{0,1\}$ there is a set $P \subseteq \{0,1\}^\omega$ for which neither player has a winning strategy.

Donald Martin proved the Borel determinacy theorem in 1975: if $X$ is any nonempty set whatsoever and $P$ is a Borel subset of $X^\omega$ then one of the players has a winning strategy for $G(X,P)$. Here $X$ has the discrete topology and $X^\omega$ has the product topology.

The axiom of determinacy states that if $P$ is any subset of $\{ 0,1 \}^\omega$ then one of the players has a winning strategy in $G(\{0,1\}, P)$. This is inconsistent with ZFC but is consistent with ZF plus dependent choice.

The paper that Andres Caicedo gave above [2] studies an entirely different type of game, which is continuous rather than discrete.

-
Incidentally, there's no reason that the plays of an infinite ordinal game must be indexed by omega. Any infinite ordinal lambda will do, though let's just be concerned about countable ordinals here. Special care must be taken to know whose turn it is at each play (whose index is some ordinal < lambda). This is easily accomplished in a "fair" way as long as whose turn it is is defined for limit ordinals; this is not difficult. (Successor ordinals just follow the alternating turn rule, as for the case lambda = omega.) –  Daniel Asimov Jul 16 '10 at 17:47
(Cont'd.) Assume "whose turn it is" has been defined for all countable limit ordinals, and hence by alternation for all countable ordinals. Then it's not even necessary to predefine the length of the game. A simple example is this: let J be any countably infinite set. Each player on their turn claims some member of J. There must be a first countable ordinal at which the last member of J is claimed: the player who did that is defined as the winner. (I hope to expand on this soon in a short article.) –  Daniel Asimov Jul 16 '10 at 17:54
Oops, that should have read, "There must be a first countable ordinal beta at which there are no unclaimed members of J; the player whose turn it is at beta is defined as the winner. –  Daniel Asimov Jul 16 '10 at 17:58
Daniel, you may be interested in Itay Neeman's work on the determinacy of similar long transfinite games. See his book at math.ucla.edu/~ineeman/long-games.htm. He an others have also considered games going beyond the countable ordinals. –  Joel David Hamkins Jul 17 '10 at 2:04
@Carl, thanks a lot for your very detailed formalism and the references. It's an excellent review of the subject. Just a silly question (in view of Andres' example): aren't continuous games a part of this general construction? –  Wadim Zudilin Jul 17 '10 at 9:23

I'm aware of quite a number of theories of "games" in mathematics. A not-overly-naive preliminary is to ask about what these are, and then what they have in common.

I think the earliest is probably the Polish (Banach-Mazur) type, which have already been defined. "Game theory'' as in von Neumann-Morgenstern is another, important for economists. Combinatorial Game Theory (CGT) is another, with its distinctive ending rule. And then there is the use of "game semantics" in computer science.

The game-like aspect is certainly to do with quantifiers. What mathematicians would recognise as "uniformity" (there exists ... such that for all ...) is to be iterated. My winning is stated in the form "I have a play such that for all plays you make (I have a play such that for all plays you make (...))". This is the typical game quantifier G, and what matters is what happens to the ... . It happens to be true, for example, that any chess game is decided by the time 10,000-ply has been played, so for chess G is a simple iteration, not some sort of "fixed point" construction.

Examples from logic I think largely fall into the "Polish" style of game. That is to judge by the Hodges book on model theory. In CGT there is a no particular distinction between finitary and infinitary games. Whichever theory is being spoken about, you need to explain carefully what the winning or ending condition is, and quite what you mean by a "strategy" (recall that G is sort of non-constructive, being existential in nature).

-
Thanks, Charles, for your thoughts. As for "need to explain carefully what the winning or ending condition is" this is exactly the point I tried to get from the author of mathoverflow.net/questions/31936 (in that case there is no ending condition!). –  Wadim Zudilin Jul 17 '10 at 9:29

The Axiom of Choice implies that there exist infinite games in which neither player has a winning strategy. Thus, the Axiom of Choice is incompatible with the Axiom of Determinacy. An example of a game where neither player has a winning strategy is the following (caveat: I'm not a set-theorist).

The game is a subset $G \subset [0,1]$ of real numbers. At stage 1, player 1 chooses a bit which is either 0 or 1. At stage 2, player 2 (knowing player 1's choices so far) chooses another bit. The players then repeat. After $\omega$ steps, they have constructed a real number $g \in [0,1]$ where the odd bits of $g$ (in binary) are given by player 1's choices and the even bits of $g$ are given by player 2's choices. Player 1 wins if $g \in G$, and player 2 wins if $g \notin G$.

Regarding the question that inspired the question, I've had a look at the paper (it's available on Springerlink). I'm convinced that $L$ does have a winning strategy. So, that particular game is determined.

-
Each set $G$ leads to a different game. For some sets $G$, the game will be determined (e.g. if $G$ is empty). For other sets, it will not be determined. For example, if $G$ is a "Bernstein set", neither containing nor disjoint from any nonempty perfect closed set, then neither player will have a winning strategy. This is because a winning strategy for player 1 can be used to build a nonempty perfect closed set in $G$, and a winning strategy for player 2 can be used to build a nonempty perfect closed set in the complement. Bernstein sets can be constructed in ZFC using the axiom of choice. –  Carl Mummert Jul 16 '10 at 16:03
Carl, I won't be too critical to Tony's answer: there could be sets $G$ for which wining strategies do not exist. –  Wadim Zudilin Jul 17 '10 at 9:32

In recent years, a relatively abstract and general formulation of extensive form games has been developed by Carlos Alos-Ferrer and Klaus Ritzberger. The formulation is general enough to discuss when some useful properties hold- and when they fail. In particular, in Trees and Extensive Forms (WP version can be found here here), they give necessary and sufficient conditions for when every pure strategy in an extensive game induces an outcome and when this outcome is unique.

-
Michael, sorry for late reaction. I really wonder about how practical are the conditions, but this indeed complements the answers above. –  Wadim Zudilin Sep 8 '11 at 10:15