<p>I don't have an exact characterization but it's unlikely this problem is EXPSPACE-complete. Suppose $M^{\Sigma^*}(x)$ accepts and let $S$ be the polynomial-size set of strings queries by this machine. If I understand the game right, Alice can win by playing every string in $S$. The only way to prevent this is if $m_A$ is polynomially-bounded but that would put the game somewhere inside the exponential-time hierarchy (or lower).</p>

CC BY-SA 4.0
2018-08-25T13:36:05.887Z
2018-08-25T13:36:05.887Z
Lance Fortnow
<p>Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be some string. </p>

<p>Consider the following Alice and Bob game. Initially, Alice and Bob have $m_A$ and $m_B$ dollars respectively. Alice wants $M^A(x)=1$ and Bob wants $M^A(x)=0$. </p>

<p>At every step of the game a player can add one string to $A$; this costs one dollar. Also a player can miss his or her step.</p>

<p>The play ends if both players spends all money or if some player missed step when he or she in a losing position (that defines by the current value of $M^A(x)$).</p>

<p><strong>Question:</strong> is the problem of defining the winner of this game for given $M, x, m_A, m_B$ is an</p>

<p><strong>EXPSPACE</strong>-complete task?</p>

<p>Note that $M$ can ask (for belonging to $A$) only strings of polynomial length so there is no  sense for Alice or Bob to add more longer strings to $A$. Hence, this problem is in <strong>EXPSPACE</strong>.   </p>

<cc.complexity-theory><complexity-classes><gt.game-theory>
Is this game EXPSPACE-complete?
Alexey Milovanov
# Is this game EXPSPACE-complete?

(Asked by: username_0 on 2018-08-18)

Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be some string.

Consider the following Alice and Bob game. Initially, Alice and Bob have $m\_A$ and $m\_B$ dollars respectively. Alice wants $M^A(x)=1$ and Bob wants $M^A(x)=0$.

At every step of the game a player can add one string to $A$; this costs one dollar. Also a player can miss his or her step.

The play ends if both players spends all money or if some player missed step when he or she in a losing position (that defines by the current value of $M^A(x)$).

**Question:** is the problem of defining the winner of this game for given $M, x, m\_A, m\_B$ is an

**EXPSPACE**-complete task?

Note that $M$ can ask (for belonging to $A$) only strings of polynomial length so there is no sense for Alice or Bob to add more longer strings to $A$. Hence, this problem is in **EXPSPACE**.

**Tags:** cc.complexity-theory, complexity-classes, gt.game-theory

---

## 1 answers

### Answer by username_1 on 2018-08-25. Score: 7 | Accepted answer

I don't have an exact characterization but it's unlikely this problem is EXPSPACE-complete. Suppose $M^{\Sigma^\*}(x)$ accepts and let $S$ be the polynomial-size set of strings queries by this machine. If I understand the game right, Alice can win by playing every string in $S$. The only way to prevent this is if $m\_A$ is polynomially-bounded but that would put the game somewhere inside the exponential-time hierarchy (or lower).


---

