Infinite game of perfect information

For $A\subseteq M^{\omega }$, the game $G(A)$ has two players alternately choose elements of the move set $M$, producing $x\in M^{\omega }$. Player I wins exactly when $x\in A$. Both players see the whole finite position before making each move.

A covering consists of a new game tree, a length-preserving prefix map to the original tree, and maps taking strategies of each player to strategies of that same player. Every play following a projected strategy lifts to a play following the original strategy, with identical projection or a premature terminal loss for that strategy's player. Terminal outcomes inherited from the original tree are respected. The strategy maps are local in depth. These conditions transfer every winning strategy, for any payoff pulled back by the prefix map. A $k$-covering leaves all positions, outcomes and strategy choices through depth $k$ unchanged.

In a sequence of game coverings whose unchanged initial depths tend to infinity, each finite game-tree level eventually stabilizes. These stable levels form a limit game. Compositions of prefix projections and depth-local strategy maps give limit projections and strategy maps. Lift a compatible play coherently through successive coverings. If no premature loss occurs, stabilization of its finite prefixes supplies a compatible limit play. If a premature loss occurs, subsequent lift lengths cannot increase and eventually stabilize, supplying a losing terminal limit play. This proves the lifting condition for the limit covering. It makes countably many pulled-back payoffs clopen simultaneously in the covering proof of Borel determinacy theorem.

A covering of an infinite game unravels a payoff when its inverse image is a clopen subset of the new infinite-play space. A closed payoff can be unravelled by letting Player I announce a subset of the first exit positions, and letting Player II accept that announcement or challenge one announced position. Accepted plays stop at exit positions, while challenged plays are forced through the challenged exit. Strategy-transfer maps make this more than an ordinary continuous representation of the payoff. Depth-stabilizing inverse limits of coverings handle countable unions in a transfinite induction.

After a fixed even-depth prefix, Player I announces a move and a set $X$ of first exit positions from a closed set of infinite plays. Player II accepts, or challenges an exit $r\in X$. Acceptance follows the old game until the first exit, where I wins exactly when that exit belongs to $X$. A challenge forces play through $r$ and then resumes the old game. Infinite accepted plays remain in the closed payoff; infinite challenged plays are outside it. Thus the pulled-back payoff is clopen. For an I-strategy, transfer by initially accepting and switching to the challenged simulation at an exit in $X$. For an II-strategy, announce the set of exits that this strategy never challenges under any announcement; it must accept this set. An exit outside it permits a challenged simulation, while an exit inside it is a premature loss for II. These maps prove the game covering lifting condition, rather than merely continuity of the projection.

In a turn-based game on a set of positions, Player I wins if the play visits a specified set $F$ infinitely often. Such games are determined even on infinite arenas. With $\mathrm{Pre}(X)$ meaning positions where I can force the next position into $X$, the winning region is the greatest fixed point of $X\mapsto \mu Y((F\cap \mathrm{Pre}(X))\cup \mathrm{Pre}(Y))$. Inner ordinal ranks force the next visit; outer removal ranks give Player II only finitely many visits outside the winning region.

A strategy assigns one legal move to every finite position at which its player is to move. A play follows the strategy when every move of that player is the assigned move.

A strategy is winning when every play that follows it is won by its player.

An infinite game of perfect information is determined when one of its two players has a winning strategy in an infinite game.

Every infinite game of perfect information on a set-sized move alphabet with a Borel payoff in its discrete product topology has a winning strategy in an infinite game for one player. A proof strengthens the induction hypothesis to existence of arbitrary-depth-preserving game coverings unravelling the payoff. The closed-set announcement construction starts the induction. For countable unions, successive coverings stabilize each finite level and their inverse limit makes every constituent payoff clopen; their union is open and can be unravelled once more.

With the axiom of choice, enumerate both players' binary-move strategies in an infinite game in length $\mathfrak{c}$. Each strategy admits $\mathfrak{c}$ compatible plays. At stage $\alpha$, reserve a fresh play following I's strategy as a loss for I, and a fresh play following II's strategy as a win for I. Avoid all previously reserved plays, which number less than $\mathfrak{c}$. The collection of the second reservations is a payoff set against which neither player has a winning strategy in an infinite game. This uses no regularity assumption on $\mathfrak{c}$.

An infinite game of perfect information with an open set of winning plays for I in the product topology on a discrete move set has a winning strategy in an infinite game for one player. Construct a winning-position attractor in an infinite game by transfinite recursion; ranks give I a terminating descent strategy inside it, and its complement gives II a strategy avoiding every winning prefix. The move set need not be countable, in the usual set theory with axiom of choice.

Allow terminal positions of an infinite game of perfect information to carry a losing-player label. A clopen set of infinite winning plays still gives a determined infinite game. At a position where all infinite continuations have one winner, the other player can win only by forcing a terminal loss for that winner. The usual winning-position attractor in an infinite game decides this reachability game. The tree of remaining undecided positions is well-founded: every infinite branch would eventually have its clopen payoff decided by a prefix. Assign the already decided winners upwards by well-founded recursion. Terminal labels are essential; a terminal node created by a covering need not be lost by the player whose turn would have come next.

Start with positions whose entire extension cylinder set lies in the winning open set. At each successor stage add I-positions with some successor already present and II-positions with every successor already present; take unions at limit ordinals. The stable set is the least fixed point of this order-preserving operation. The first entry ordinal supplies a strictly decreasing rank until the winning prefix is reached.

The axiom of determinacy states that every game $G(A)$ with $A\subseteq {\omega }^{\omega }$ is determined. Its version for a move set $M$ is denoted ${\mathsf{AD}}_M$.

Projective determinacy states that every infinite game of perfect information whose payoff is a projective set is determined.

A quasistrategy assigns a nonempty set of allowed moves to every position at which its player moves. It is winning when every play consistent with those allowed moves is won by that player.

An infinite game of perfect information is quasidetermined when one of the players has a winning quasistrategy. Choosing one allowed move at every relevant position refines a winning quasistrategy to a winning strategy in an infinite game whenever the required restricted choice principle holds.

For every move set $M$, the statement that every quasidetermined subset of $M^{\omega }$ is determined is equivalent in ZF to ${\mathsf{AC}}_{M^{<\omega }}(M)$. The forward direction encodes an arbitrary family of nonempty subsets of $M$ into a quasidetermined game; the reverse direction chooses one move from each value of a winning quasistrategy.