Games that never begin

Question

Games that never end play a major role in descriptive set theory. See for example Kechris' GTM.

Question: Does there exist a literature concerning games that never begin?

I have in mind two players, Alice and Bob, making alternate selections from ${\Bbb N}$, their moves indexed by increasing non-positive integers, the game terminating when Bob plays his move 0.

As for payoff sets and strategies, define these as for games that never end, mutatis mutandis.

One major difference: a pair of strategies, one for Alice, one for Bob no longer determines a unique run of the game, but rather now a set of runs, possibly empty. Even so one may still say that Alice's strategy beats Bob's if every compatible run of one strategy against the other belongs to the payoff set.

Another major difference involves the set-theoretic size of strategies. Now Alice and Bob play every move in the light of infinite history. So size considerations mean that certain familiar arguments, for example non-determined games from the axiom of choice, don't work in any obvious way?

Question: What payoff sets give determined games that never begin?

Edits: By the cold light of morning, I see that I abused the words "mutatis mutandis." A la Kechris, Alice's strategy beats Bob's if the the unique run of the game falls in the payoff set. What I had in mind here was that Alice's strategy beats Bob's if the run set (consistent with both strategies) is a subset of the payoff set. Joel David Hamkins' clever answer remains trenchant, only now with the import that Alice always wins by playing a strategy with empty run sets regardless of Bob's strategy.

Joel's Alice needs an infinite memory, but if her strategy at each move consists of increasing her previous move by 1, that also necessarily produces an empty run set regardless of Bob's choice.

Possible fix 1 Alice must play an engaged strategy, a strategy that produces a nonempty run set against at least one strategy of Bob's.

Possible fix 2 The residual game at any turn only has a finite future, so one player has a winning strategy from that point on. Call a strategy rational if it requires the player to play a winning move in the residual game whenever one exists. Call a strategy strongly rational if it requires the player to play the least possible winning move whenever one exists. To avoid easy disengaged strategies that don't even reference the payoff set, insist on rational, or even strongly rational strategies.

Possible fix 3 Combine the previous fixes.

Answer 1

As a supplement to Joel's answer, you may want to look at this nice paper of Bollobas, Leader, and Walters concerning continuous games. As a starting point they discuss the classical Lion and Man game introduced by Rado. In this game there is a lion chasing a man inside the unit disk. Both have identical maximum speeds. The lion wins if he catches the man, and the man wins if he is never caught by the lion. If the lion chooses to always run directly toward the man, then he will get arbitrarily close to the man, but never catch him. On the other hand, if the lion instead moves at top speed so that he is always on the radial vector from the centre to the man, it was 'clear' that this was a winning strategy. Proof: without loss of generality, the man stays on the boundary of the disk. However, in 1952, Besicovitch exhibited an ingenious winning strategy for man! Thus, staying on the boundary is with loss of generality for man. Nonetheless, one can ask the perplexing question if lion also has a winning strategy? In this particular game, it turns out that the answer is no. But by changing the metric space, Bollobas, Leader, and Walters prove that there are games in a similar vein where both lion and man have winning strategies!

Answer 2

This is a very nice question.

Observation 1. Some strategies have no play that accords with them. Consequently, such a strategy for Alice is winning in any game, since every play in conformance with it is (vacuously) in her payoff set. (Similar strategies exist for Bob.)

Proof: Here, I consider a strategy to be a function mapping a game position to the number to be played. A game position is an almost-infinite sequence, with only the final finitely many digits remaining unspecified. Consider the strategy for Alice: faced with a game position of prior play, she inspects her own previous moves; if infinitely many of them were $0$, she plays $1$, and otherwise she plays $0$. There can be no play that accords with this strategy, since if the play shows Alice to have played infinitely many $0$s, then she should have been playing $1$ at any one of them; and conversely, if she had played only finitely many $0$s, then she should have started playing $0$ much earlier than she did.

Another instance is the always-add-one strategy you mentioned in response to this, and I find that to be quite elegant. If Alice plays so as to always add one to her previous move, then clearly she cannot have done this forever. This strategy makes sense in games with natural number plays, but actually one can use the same idea for binary games, where the players play $0$ or $1$, by having Alice play a (strictly longer) sequence of $n$ consecutive $1$s on her next $n$ moves (unless playing time runs out).

An earlier answer of mine (see edit history) contains another argument, using diagonalization and the axiom of choice. QED

Thus, it seems that Alice wins every game, according to the definition you have provided. But I prefer to say that both players have winning strategies, because they both have strategies such that any play that conforms with them is in their respective payoff sets.

Observation 2. If one modifies the definition of strategy so that one's moves depend only on the opponent's moves in a position, then not every pair of strategies for Alice and Bob have a conforming play.

Proof: Consider the strategy for Bob that simply copies Alice's previous move, and the strategy for Alice that plays $1$ if and only if all prior moves of Bob were $0$. There can be no conforming play for this pair of strategies, since if Bob was previously playing all zeros up to a point, then Alice should have played $1$ much earlier, and if not, then Alice must have played $1$ without cause. QED

Observation 3. There is a game for which both players have rational engaged winning strategies.

Proof: Consider the game where Alice wins every play having only finitely many $1$s. The always-play-$3$ strategy is a rational, engaged winning strategy for Bob, since it has conforming plays, every conforming play is a win for Bob, and from any position, it makes a move that is winning in the finitely remaining game. Meanwhile, Alice also has a winning strategy: to play $0$, if almost all previous moves were $0$, and otherwise add one to her previous move. This strategy is engaged, since Bob might have played $0$s, and it is strongly rational for Alice, since she is playing $0$s whenever she is in a winning position; and it is winning for Alice, since the only conforming plays are almost all $0$ and hence wins for Alice. QED

Theorem. (AC) There is a game for which neither player has winning rational engaged strategy.

Proof: This theorem will work regardless of whether one allows the strategies to depend on the full position or only on the opponent's prior moves. Let's say that two sequences are almost equal if they differ on only finitely many values. Using the axiom of choice, we may select a representative from each almost-equality class. Let $A$ be the game where Alice wins a play, if the play deviates from the representative of its class for the first time on her turn, and Bob wins if the play deviates for the first time on his turn, or not at all. The thing to notice is that if $s$ is a play of the game, then both Alice and Bob had incentive to have played differently earlier, for by making a much earlier different move, they would have caused a much earlier deviation in the play, causing them to have won earlier. Indeed, it was irrational of them not to have made the earlier move, since their opponent might have won on the next move. Thus, there can be no rational strategy for either player resulting in such a play. So neither player has a rational engaged strategy. QED

Define that a set is a tail set if it is invariant under finite modification. These are precisely the sets that are saturated with respect to the almost-equality relation.

Observation 4. In every game whose payoff set is a tail set, every strategy is rational.

Proof: The point is that when you are playing a game whose payoff set is a tail set, then the game is already won or lost when any particular move is made, since the tail equivalence class is already determined. So in such a game, no particular individual move affects the outcome of the game. QED

Finally, let me mention that your game concept reminds me of the archeological model of infinite time computation, where the infinite computation grows out of an infinite past rather than stretching into an infinite future. The idea is that, having opened up a chamber under the pyramid, you find a Turing machine, still running, with an infinite tape all filled out and with all indications that it has been running from time stretching infinitely into the past. What kind of problems are decidable in principle by such machines? For an interesting theory, assume we may find pyramids corresponding to any given program.

Answer 3

A slightly more tangential answer, but one which I hope is still useful: there is a well-known connection between infinite games and infintary logic. In the usual context of games with no ending, determinacy principles can be viewed as versions of De Morgan's Law for certain infinitary sentences: for $\Gamma$ a pointclass, $\Gamma$-Det is the statement that each of the disjunctions $$ \forall x_0\exists x_1\forall x_2\exists x_3 . . . . ((x_0, x_1, x_2, x_3, . . . )\not\in X) \vee \exists x_0\forall x_1\exists x_2\forall x_3 . . . ((x_0, x_1, x_2, x_3, . . . ) \in X)$$ for $X\in\Gamma$ is true. Similarly, games with no beginnings should be connected to the semantics of infinitary sentences with ill-founded strings of quantifiers. In the paper "On languages with non-homogeneous strings of quantifiers" (https://doi.org/10.1007/BF02771553), Saharon Shelah did some work on the behavior of such sentences (his semantics for these sentences is in terms of Skolem functions; it appears to avoid Joel's observation by requiring that a strategy for one player look only at moves made by the other player, but I'm not certain of this - please correct me if I'm wrong!). The main result is that "every linear string of quantifiers can be replaced by a well-ordered sequence of quantifiers," which goes some way towards reducing the study of beginningless games to the study of endless games.

However, it should be noted that non-linear "strings" (posets?) of quantifiers have also been studied (cf. "Dependence Logic"), and I have no idea what happens if we look at branching, ill-founded collections of quantifiers, or if this has been looked at in the past (although I vaguely recall a paper by either Hintikka or Vaananen on the subject, but I can't find it, so maybe it doesn't exist). I also don't know a good game-theoretic interpretation of such collections of quantifiers, but I imagine one would not be too hard to come by.