1
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ math.stackexchange.com/questions/3329380/… $\endgroup$ – Asaf Karagila Aug 21 at 8:53
  • $\begingroup$ @AsafKaragila The OP's account on MSE seems to have been deleted, so it seems simplest to leave the question open here unless people decide its level is more appropriate for MSE $\endgroup$ – Yemon Choi Aug 24 at 3:25
  • $\begingroup$ @YemonChoi: I agree. $\endgroup$ – Asaf Karagila Aug 24 at 5:55
  • $\begingroup$ In your definition of $F$, do you mean to require that the $k_n$ are increasing? $\endgroup$ – Johannes Schürz Sep 8 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.