Winning strategies for games on the natural numbers

129 Views Asked by At

Define $$F=\{(l_n, k_n)_{n=1}^t: t,l_n, k_n \in \mathbb{N}, l_1<\ldots <l_t, m_1<\ldots <m_t\}.$$ Suppose that I have a collection $G\subset F$, which is a set of ''good'' sequences.

Define $$A=\{(l_n)_{n=1}^\infty: (\exists (k_n)_{n=1}^\infty)(\forall t\in \mathbb{N})((l_n, k_n)_{n=1}^t\in G)\}.$$

I want to define two games between two players and ask whether the existence of a winning strategy for Player I in the first game is equivalent to a winning strategy for Player I in the second game. Roughly speaking, one game requires Player I to choose their integers with limited information during the game, while the other allows Player I to choose their integers with full information. My naive hope that existence of winning strategies for the two distinct games would be equivalent is based on the fact that the "target set" for the game is defined using $G$ which, in some sense, only depends on the past choices.

Game 1 Player I chooses an infinite subset $L_1$ of the natural numbers. Player II chooses $l_1\in L_1$ and an infinite subset $M_1$ of $L_1$. Player I chooses $k_1\in \mathbb{N}$ and an infinite subset $L_2$ of $M_1$. Player II chooses $l_2\in L_2$ with $l_1<l_2$ and an infinite subset $M_2$ of $L_2$. Play continues in this way. Player I wins if $(l_n, k_n)_{n=1}^t\in G$ for all $t\in \mathbb{N}$. We note that Player I is allowed to choose any $k_n\in \mathbb{N}$, and is not required to choose $k_n$ from any particular subset of $\mathbb{N}$.

Game 2 Player I chooses an infinite subset $L_1$ of the natural numbers, Player II chooses $l_1\in L_1$ and an infinite subset $M_1$ of $L_1$. Player I chooses an infinite subset $L_2$ of $M_1$. Player II chooses $l_2\in L_2$ with $l_1<l_2$ and an infinite subset $M_2$ of $L_2$. Play continues in this way. Player I wins if $(l_n)_{n=1}^\infty\in A$, where $A$ is defined above. This means that Player I wins if there exists $(k_n)_{n=1}^\infty$ such that $(l_n, k_n)_{n=1}^t\in G$ for all $t\in \mathbb{N}$. Here, Player I has the luxury of choosing each $k_n$ after all $l_n$ choices have been made.

Is it true that Player I has a winning strategy in the first game if and only if Player II has a winning strategy in the second game?

In the particular case that I care about, $G$ has some additional nice properties, so please feel free to use them if it helps:

$1$: If $(l_n, k_n)_{n=1}^t\in G$ and if $1\leqslant r_1<\ldots <r_s\leqslant t$, then $(l_{r_n}, k_{r_n})_{n=1}^s\in G$.

$2$: If $(l_n, k_n)_{n=1}^t\in G$ and if $(m_n)_{n=1}^t$ is any increasing sequence of integers such that $k_n\leqslant m_n$ for each $1\leqslant n\leqslant t$, then $(l_n, m_n)_{n=1}^t\in G$.