Complexity of winning strategies for open games (for open player)

2013-02-12T02:39:41Z

If $G\subseteq\omega^{<\omega}$ is a computable clopen game, then $G$ has a winning strategy which is hyperarithmetic $(\Delta^1_1)$, by an inductive ranking process. The key observation here is that the length of this induction is bounded above by the length of the Kleene-Brouwer ordering $G_{KB}$, which is a computable ordinal and hence $<\omega_1^{CK}$, and that each successive stage of the induction can be achieved by one application of the jump operator, so there is a winning strategy with complexity at most $0^{(\vert G_{KB}\vert)}$.

(An annoying subtlety here is that the theory $\Delta^1_1-CA_0$, which amounts to closure under hyperarithmeticity, does not prove determinacy of clopen games, since there are games which are not actually clopen but have no hyperarithmetic witnesses to their ill-foundedness.)

My question is whether a version of this result is also true for open games. Specifically, let $T\subseteq\omega^{<\omega}$ be an open game in which the "Open" player (i.e., the player trying to fall off the tree) has a winning strategy; do they necessarily have a winning strategy hyperarithmetic in $T$?

I'm asking this question because I was looking through my notes from a previous class, and I ran across the assertion that "a similar ranking argument" shows that the answer is 'yes;' however, I can't reconstruct this argument, and I'm wondering whether I (or the lecturer) was simply incorrect; or whether there's a basic argument I'm not seeing.

Answer by Joel David Hamkins for Complexity of winning strategies for open games (for open player)

2013-02-12T03:12:26Z

The answer is yes.

The point is that if there is any winning strategy for a designated player from a given position, then there is in a sense a canonical winning strategy, which is to make the first move that minimizes the game value of the resulting position, and for a given winning position in a fixed game, I claim that this strategy will have at worst hyperarithmetic complexity.

To explain, consider how the ordinal game values arise. We fix the tree of all possible finite plays. We assign value $0$ to any position in which the designated open player has already won. We assign value $\alpha+1$ to a position with the open player to move, if $\alpha$ is least among the values of the positions to which he or she can legally play. If it is the opponent's move and every move by the opponent has a value, then the value of the position is the supremum of these values. Thus, the open player seeks to reduce value, and wins when the value hits zero. The opposing player seeks to maintain the value as undefined or as high as possible.

Since playing according to the value-reducing strategy reduces value at every move for the open player, it follows that the tree $T_p$ of all positions arising from the value-reducing strategy is well-founded, and the value of $p$ is precisely the rank of the well-founded tree $T_p$, if one should consider only the positions where it is the opponent's turn to play.

Note that the assertion, "position $p$ in tree $T$ has value $\alpha$" is $\Sigma_1$ expressible in any admissible structure containing $T$ and $\alpha$, since this is equivalent to the assertion that there is a ordinal assignment fulfilling the recursive definition of game value, which gives $p$ value $\alpha$ in that tree. It follows that there can be no position in $T$ with value $\omega_1^{T}$, since otherwise we would get a $\Sigma_1$-definable map unbounded in $\omega_1^{T}$. So the value of a position in $T$ is a $T$-computable ordinal or undefined.

If a player has a winning strategy from a position $p$, then because the ordinal game value assignment is unique and all relevant values in the game proceeding from $p$ will be bounded by the fixed value $\beta_p$ of $p$, it follows that the value-reducing strategy from $p$ is $\Delta^1_1(T)$ definable and hence hyperarithmetic in $T$.

Basically, the way I think about it is that once you know a code for the ordinal value of the initial position, then the strategy only cares about positions with value less than that, and you can bound the ordinals that arise in the recursive definition of game value. Since the ordinal game value assignment is unique, this allows the strategy to become $\Delta^1_1$ in a code for the initial value, which is bounded by the ordinal value of the well-founded tree.

Complexity of winning strategies for open games (for open player) - MathOverflow

Complexity of winning strategies for open games (for open player)

Answer by Joel David Hamkins for Complexity of winning strategies for open games (for open player)