11
$\begingroup$

Given a set $A\subseteq\mathbb{R}_{>0}$, consider the following (two-player, perfect-information, length-$\omega$) game $H_A$:

  • Players $1$ and $2$ alternately play strictly increasing natural numbers $k_0<k_1<...$ subject to the rules that $$\left(\sum_{k_{n-1}<i\le k_n}{1\over i}\right) >\left( \sum_{k_n<j\le k_{n+1}}{1\over j}\right)$$ for all $n\in\mathbb{N}$ (using the convention that $k_{-1}=0$).

  • Given a play $\pi=\langle k_i\rangle_{i\in\mathbb{N}}$, define $\sigma_\pi:\mathbb{N}\rightarrow\{1,-1\}$ as follows:

    • If $n\le k_0$ then $\sigma_\pi(n)=1$.

    • If $k_{2m}<n\le k_{2m+1}$ for some $m$, then $\sigma_\pi(n)=-1$.

    • If $k_{2m+1}<n\le k_{2m+2}$ for some $m$, then $\sigma_\pi(n)=1$.

  • Player $1$ wins a play $\pi$ iff $$\sum_{n\in\mathbb{N}}{\sigma_\pi(n)\over n}\in A.$$

Basically, players $1$ and $2$ are building a conditionally convergent version of the harmonic series by determining the signs of blocks of terms appropriately. Of course we could play this game with any decreasing-to-zero sequence of positive reals in place of the harmonic sequence, but the harmonic sequence seems like a good first candidate to consider.

I'm interested in the complexity of determining when player $1$ has a winning strategy in $H_A$ for a given $A$. There are a few natural ways to pose this. First, I'm curious whether we can code meaningful difficulty into the $H_A$ games:

Question 1: Does $\mathsf{ZFC}$ prove that some $H_A$ is undetermined?

Results about the Banach game (see e.g. here) suggest that the answer is yes, but I don't immediately see how to prove that here.

Separately, we can look at the difficulty of determining whether a given "reasonably simple" (in particular, low-level Borel) set $A$ yields a player-$1$-winning $H_A$. For example:

Question 2: Is there a simple description of which open sets $A$ make $H_A$ a player-$1$ win?

Improve this question
$\endgroup$
6
  • $\begingroup$ One strange-seeming observation: if player 1 plays $k_0=1$, then the players must form the alternating harmonic series, and player 1 wins if and only if $\ln(2) \in A$. Similarly, either player has the freedom, at any point in the game, to effectively end things by playing $k_{n+1} = k_n+1$, as your rules then force $k_{m+1} = k_m+1$ for all $m > n$ as well. $\endgroup$
    – Will Brian
    Commented Jul 18, 2022 at 0:05
  • $\begingroup$ @WillBrian Yup! That's true (and perhaps annoying). $\endgroup$
    – Noah Schweber
    Commented Jul 18, 2022 at 0:11
  • $\begingroup$ I don't know about annoying -- I think it makes things interesting. My first thought was that your game should be pretty similar to one called Baker's game, where players alternately choose $a_0,b_0,a_1,b_1,\dots$ in such a way that $a_0 < a_1 < \dots < b_1 < b_0$, and then player 1 wins if $\lim a_n$ is in some payoff set. This game is well understood: player 1 wins if and only if the payoff set contains a perfect set, and player 2 wins if and only if the payoff set is countable. But after thinking about it for a bit, your game seems much weirder than this one. (In a good way!) $\endgroup$
    – Will Brian
    Commented Jul 18, 2022 at 0:15
  • $\begingroup$ @WillBrian I always interpret "weirder" in a good way. :P $\endgroup$
    – Noah Schweber
    Commented Jul 18, 2022 at 0:16
  • $\begingroup$ Correction to my first comment: if player 1 plays $k_0 = 1$ then player 2 can respond with $k_1 = 2$ or $3$. But it is true that if either player plays $k_{n+1} = k_n+1$ for any $n \geq 0$ (any time after the very first move), then this forces $k_{m+1} = k_m+1$ for all $m > n$ and effectively ends the game. $\endgroup$
    – Will Brian
    Commented Jul 18, 2022 at 12:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .