show/hide this revision's text 2 edited body

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(p)$ \Delta^1_1(T)$ definable and hence hyperarithmetic in $p$.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.
show/hide this revision's text 1

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(p)$ definable and hence hyperarithmetic in $p$.

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.