<p>This should be EXPSPACE-complete. I'll sketch how to achieve an exponential number of alternations, without reducing any EXPSPACE-complete problem to this one, but from here it should be simple to finish.</p>

<p>Denote the words in the oracle after <span class="math-container">$t$</span> rounds by <span class="math-container">$A_t$</span>, so initially <span class="math-container">$A_0=\emptyset$</span>.
Denote the words queried by <span class="math-container">$M^{A_t}$</span> by <span class="math-container">$Q_t$</span>.
The main observation is that whoever is losing with <span class="math-container">$A_t$</span>, can be assumed to add something from <span class="math-container">$Q_t$</span> to <span class="math-container">$A$</span>.
This is because in this game every move costs money, we want to move as little as possible; there's no point making a move until we're winning.
But this also implies that if we're losing, there's no point adding anything from outside <span class="math-container">$Q_t$</span>.</p>

<p>Assume for simplicity that <span class="math-container">$M$</span> runs for exactly <span class="math-container">$2n$</span> steps and at steps <span class="math-container">$2i$</span> and <span class="math-container">$2i+1$</span> it queries a word of length exactly <span class="math-container">$i$</span>.
The cost function <span class="math-container">$f$</span> will simply be <span class="math-container">$2^{-i}$</span> on words of length <span class="math-container">$i$</span>.
The game will be such that Alice always needs to add odd length words and Bob always needs to add even length words to <span class="math-container">$A$</span>.
Suppose that <span class="math-container">$n$</span> is odd and initially Alice is losing.</p>

<p>The budgets <span class="math-container">$m_A$</span> and <span class="math-container">$m_B$</span> will be set so that she can choose exactly one of the length <span class="math-container">$n$</span> words queried by <span class="math-container">$M^{A_0}$</span> to be added to <span class="math-container">$A$</span>.
The game will be such that this makes her the winner, so Bob will have to move.
Again due to budget constraints, he will have to choose exactly one of the length <span class="math-container">$n-1$</span> words queried by <span class="math-container">$M^{A_1}$</span> to be added to <span class="math-container">$A$</span>.
After any of these are added, <span class="math-container">$M^{A_2}$</span> will query two new length <span class="math-container">$n$</span> words (the same ones, regardless of what word Bob added to <span class="math-container">$A$</span>), and Bob will win.
Alice will be forced to add exactly one of these new length <span class="math-container">$n$</span> words to <span class="math-container">$A$</span> to make her win.</p>

<p>The game goes on in this manner, which can be imagined as following the branches of a complete binary tree of depth <span class="math-container">$n$</span>, though at each branching node one of the players (determined which by the parity of the depth of the node) needs to make a choice about which word to add to <span class="math-container">$A$</span>.
After they go through the tree, they will run out of their budget.
If at any stage of the game one of them decides to add some word that is shorter (e.g., Alice a length <span class="math-container">$k&lt;n$</span> word from <span class="math-container">$Q_0$</span> in the first step), then if the other player (in our example Bob) just plays always the longest word he can in the binary tree, he will have some money left at the end and we make the game so that he can use this to win.
(Note that Alice might also have some money left, but Bob will have more, so we design the end-game that if one of them has more money, then that player can win.)</p>

<p>This way Alice decides for exponentially many pairs of odd-length words, and Bob about exponentially many even-length words which one of each pair goes to <span class="math-container">$A$</span>, and they make these choices in an alternating manner.</p>

CC BY-SA 4.0
2018-10-30T08:03:38.730Z
Thank you for your answer. I asked you some questions by e-mail.
Alexey Milovanov
CC BY-SA 4.0
2018-10-27T22:02:48.147Z
2018-10-27T22:02:48.147Z
domotorp
<p>This is a generalization of my <a href="https://cstheory.stackexchange.com/questions/41399/is-this-game-expspace-complete">previous question</a>.</p>

<p>Let <span class="math-container">$M$</span> be a polynomial-time deterministic machine that can ask questions to some oracle <span class="math-container">$A$</span>. Initially <span class="math-container">$A$</span> is empty but this is can be changed after a game that will be described below. Let <span class="math-container">$x$</span> be some string. </p>

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

<p>At every step of the game a player can add some string <span class="math-container">$y$</span> to <span class="math-container">$A$</span>; this costs <span class="math-container">$f(y)$</span> dollar, where <span class="math-container">$f: \{0,1\}^* \to \mathbb{N}$</span> is a polynomial-time computable function. 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 <span class="math-container">$M^A(x)$</span>).</p>

<p><strong>Question:</strong> is the problem of defining the winner of this game for given 
<span class="math-container">$M, f, x, m_A, m_B$</span> is an</p>

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

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

<p>In my previous question adding of every string to <span class="math-container">$A$</span> costs one dollar (i.e. <span class="math-container">$f \equiv 1$</span>). Then (as it was shown by <a href="https://cstheory.stackexchange.com/users/550/lance-fortnow">Lance Fortnow</a>) this game belongs to <strong>EXPH</strong> and even to <strong>PSPACE</strong> if <span class="math-container">$m_A = m_B$</span>.  </p>

CC BY-SA 4.0
2018-10-27T03:11:10.563Z
Can you explain why you made this change to the problem? Alice can check to see if she can afford to pay for all the strings in $S$ (as defined in Lance’s answer to your other problem) in polynomial time. How does this not immediately resolve the problem?
Stella Biderman
CC BY-SA 4.0
2018-10-27T15:28:23.723Z
@StellaBiderman Alice indeed can check this in polynomial time. However, if she has not enough money then now this is does not mean that she can make only polynomial steps (as it was in the previous game).
Alexey Milovanov
CC BY-SA 4.0
2018-10-27T15:54:36.707Z
If she cannot afford $S$, can she ever beat an opponent who always skips their turn? Maybe there’s something about the game set-up I am not understanding.
Stella Biderman
CC BY-SA 4.0
2018-10-27T20:56:11.377Z
@Stella Yes, because their might be other accepting paths. E.g., suppose if $x_1\in A$, then $M$ stops and accepts. In this case, $S=\{x_1\}$. But if $x_1\notin A$, then $M$ might query $x_2$ and accept if $x_2\in A$. In this case it is enough if Alice has enough spondulix for $x_2$.
domotorp
<cc.complexity-theory><complexity-classes><gt.game-theory>
What is the complexity of this game?
Alexey Milovanov
# What is the complexity of this game?

(Asked by: username_0 on 2018-10-21)

This is a generalization of my [previous question](https://cstheory.stackexchange.com/questions/41399/is-this-game-expspace-complete).

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 some string $y$ to $A$; this costs $f(y)$ dollar, where $f: \{0,1\}^\* \to \mathbb{N}$ is a polynomial-time computable function. 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, f, 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**.

In my previous question adding of every string to $A$ costs one dollar (i.e. $f \equiv 1$). Then (as it was shown by [Lance Fortnow](https://cstheory.stackexchange.com/users/550/lance-fortnow)) this game belongs to **EXPH** and even to **PSPACE** if $m\_A = m\_B$.

**Tags:** cc.complexity-theory, complexity-classes, gt.game-theory
> **Comments:**
> **username_1**: Can you explain why you made this change to the problem? Alice can check to see if she can afford to pay for all the strings in $S$ (as defined in Lance’s answer to your other problem) in polynomial time. How does this not immediately resolve the problem?  
> **username_0**: @StellaBiderman Alice indeed can check this in polynomial time. However, if she has not enough money then now this is does not mean that she can make only polynomial steps (as it was in the previous game).  
> **username_1**: If she cannot afford $S$, can she ever beat an opponent who always skips their turn? Maybe there’s something about the game set-up I am not understanding.  
> **username_2**: @Stella Yes, because their might be other accepting paths. E.g., suppose if $x_1\in A$, then $M$ stops and accepts. In this case, $S=\{x_1\}$. But if $x_1\notin A$, then $M$ might query $x_2$ and accept if $x_2\in A$. In this case it is enough if Alice has enough spondulix for $x_2$.  

---

## 1 answers

### Answer by username_2 on 2018-10-27. Score: 5 | Accepted answer

This should be EXPSPACE-complete. I'll sketch how to achieve an exponential number of alternations, without reducing any EXPSPACE-complete problem to this one, but from here it should be simple to finish.

Denote the words in the oracle after $t$ rounds by $A\_t$, so initially $A\_0=\emptyset$.
Denote the words queried by $M^{A\_t}$ by $Q\_t$.
The main observation is that whoever is losing with $A\_t$, can be assumed to add something from $Q\_t$ to $A$.
This is because in this game every move costs money, we want to move as little as possible; there's no point making a move until we're winning.
But this also implies that if we're losing, there's no point adding anything from outside $Q\_t$.

Assume for simplicity that $M$ runs for exactly $2n$ steps and at steps $2i$ and $2i+1$ it queries a word of length exactly $i$.
The cost function $f$ will simply be $2^{-i}$ on words of length $i$.
The game will be such that Alice always needs to add odd length words and Bob always needs to add even length words to $A$.
Suppose that $n$ is odd and initially Alice is losing.

The budgets $m\_A$ and $m\_B$ will be set so that she can choose exactly one of the length $n$ words queried by $M^{A\_0}$ to be added to $A$.
The game will be such that this makes her the winner, so Bob will have to move.
Again due to budget constraints, he will have to choose exactly one of the length $n-1$ words queried by $M^{A\_1}$ to be added to $A$.
After any of these are added, $M^{A\_2}$ will query two new length $n$ words (the same ones, regardless of what word Bob added to $A$), and Bob will win.
Alice will be forced to add exactly one of these new length $n$ words to $A$ to make her win.

The game goes on in this manner, which can be imagined as following the branches of a complete binary tree of depth $n$, though at each branching node one of the players (determined which by the parity of the depth of the node) needs to make a choice about which word to add to $A$.
After they go through the tree, they will run out of their budget.
If at any stage of the game one of them decides to add some word that is shorter (e.g., Alice a length $k word from $Q\_0$ in the first step), then if the other player (in our example Bob) just plays always the longest word he can in the binary tree, he will have some money left at the end and we make the game so that he can use this to win.
(Note that Alice might also have some money left, but Bob will have more, so we design the end-game that if one of them has more money, then that player can win.)

This way Alice decides for exponentially many pairs of odd-length words, and Bob about exponentially many even-length words which one of each pair goes to $A$, and they make these choices in an alternating manner.

> **Comments:**
> **username_0**: Thank you for your answer. I asked you some questions by e-mail.  

---

