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.



Complexity of winning strategies for open games (for open player)
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.


