What is the complexity of this game?

Question

This is a generalization of my previous question.

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) this game belongs to EXPH and even to PSPACE if $m_A = m_B$.

Answer 1

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