<p>Since Steven Stadnicki's answer doesn't appear to have been accepted by the asker, I figured it may still be helpful to provide an update: I have a reduction from 3SAT to MULTI-GAME. I haven't looked at Steven's answer carefully or followed through the link he provided, but based on the following reduction I won't be surprised if MULTI-GAME is indeed PSPACE-complete. I might not bother extending this result beyond NP-hardness, however.</p>

<p>A 3SAT instance consists of clauses <span class="math-container">$C_1, \dots, C_m$</span>, each clause being of the form <span class="math-container">$C_i = L_{i1} \vee L_{i2} \vee L_{i3}$</span> where each <span class="math-container">$L_{ik}$</span> is either one of the variables <span class="math-container">$x_1, \dots, x_n$</span> or the negation of one of the variables.</p>

<p>Given such a 3SAT instance, the reduction creates a MULTI-GAME instance consisting of <span class="math-container">$n + 1$</span> games -- one for each variable and another game used as an excess capital sink. First we'll define the structure of the graphs for each game, then look at an example and discuss the core idea, and then we'll figure out what exact costs to assign to the edges to make the reduction hold firm.</p>

<p>First, the variable game graph <span class="math-container">$G_j$</span> for each variable <span class="math-container">$x_j$</span>:</p>

<ol>
<li>Create vertex labeled <span class="math-container">$x_j$</span> marked with an A (i.e. a winning vertex for Alice). The chip for <span class="math-container">$G_j$</span> starts on vertex <span class="math-container">$x_j$</span>.</li>
<li>Create a vertex labeled <span class="math-container">$T$</span> and a vertex labeled <span class="math-container">$F$</span>, each marked with a B (i.e. both are winning positions for Bob). Create directed edges from <span class="math-container">$x_j$</span> to both <span class="math-container">$T$</span> and <span class="math-container">$F$</span>, both with costs of <span class="math-container">$1$</span>.</li>
<li><p>For each literal <span class="math-container">$L_{ik}$</span> of clause <span class="math-container">$C_i$</span>, if <span class="math-container">$L_{ik} = x_j$</span> or <span class="math-container">$L_{ik} = \neg x_j$</span>, create vertices labeled <span class="math-container">$C_iTA$</span> and <span class="math-container">$C_iFA$</span> marked with A and vertices labeled <span class="math-container">$C_iTB$</span> and <span class="math-container">$C_iFB$</span> marked with B. Add edges <span class="math-container">$(T, C_iTA)$</span> and <span class="math-container">$(F, C_iFA)$</span> with costs both set to <span class="math-container">$l_{ik}$</span>. (We'll define <span class="math-container">$l_{ik}$</span> later.)</p>

<p>Add edges <span class="math-container">$(C_iTA, C_iTB)$</span> and <span class="math-container">$(C_iTA, C_iTB)$</span>. If <span class="math-container">$L_{ik} = x_j$</span>, then set <span class="math-container">$(C_iTA, C_iTB)$</span>'s cost to <span class="math-container">$l_{ik} - 1$</span> and <span class="math-container">$(C_iTA, C_iTB)$</span>'s cost to <span class="math-container">$l_{ik}$</span>. Otherwise set <span class="math-container">$(C_iTA, C_iTB)$</span>'s cost to <span class="math-container">$l_{ik}$</span> and <span class="math-container">$(C_iTA, C_iTB)$</span>'s cost to <span class="math-container">$l_{ik} - 1$</span>.</p></li>
</ol>

<p>The capital sink game:</p>

<ol>
<li>Create a vertex labeled <span class="math-container">$C$</span>, marked with B.</li>
<li>For each clause <span class="math-container">$C_i$</span>, create a vertex labeled <span class="math-container">$C_iA$</span> marked with A, and a vertex labeled <span class="math-container">$C_iB$</span> marked with B. Create an edge <span class="math-container">$(C, C_iA)$</span> with edge cost <span class="math-container">$c_i$</span> (again to be determined below), and an edge <span class="math-container">$(C_iA, C_iB)$</span> also with edge cost <span class="math-container">$c_i$</span>.</li>
</ol>

<p>This is a lot to take in, so hopefully an example makes this a little more digestible. Our 3SAT instance is as follows:</p>

<p><span class="math-container">$C_1 = x_1 \vee x_2 \vee \neg x_3$</span></p>

<p><span class="math-container">$C_2 = x_2 \vee x_3 \vee \neg x_4$</span></p>

<p><span class="math-container">$C_3 = \neg x_1 \vee \neg x_3 \vee x_4$</span></p>

<p>The reduction turns this instance into 4 variable game graphs and 1 capital sink graph. In the diagrams below, the red vertices are marked with A (i.e. are winning positions for Alice), and the cyan vertices are marked with B (are winning positions for Bob).</p>

<p>Graph for <span class="math-container">$x_1$</span>:</p>

<p><a href="https://i.sstatic.net/C1WA5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/C1WA5.png" alt="enter image description here"></a></p>

<p>Graph for <span class="math-container">$x_2$</span>:</p>

<p><a href="https://i.sstatic.net/3kbNn.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3kbNn.png" alt="enter image description here"></a></p>

<p>Graph for <span class="math-container">$x_3$</span>:</p>

<p><a href="https://i.sstatic.net/DWvbu.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/DWvbu.png" alt="enter image description here"></a></p>

<p>Graph for <span class="math-container">$x_4$</span>:</p>

<p><a href="https://i.sstatic.net/m32Lr.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/m32Lr.png" alt="enter image description here"></a></p>

<p>Graph for capital sink:</p>

<p><a href="https://i.sstatic.net/hqno3.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/hqno3.png" alt="enter image description here"></a></p>

<p>The idea is as follows:</p>

<p>Bob is forced to make the first <span class="math-container">$n$</span> moves in order to get out of losing positions in the <span class="math-container">$n$</span> variable games. Each such move encodes an assignment of true or false to the corresponding variable.</p>

<p>Alice will then have enough capital to make exactly 4 moves, each of which Bob will need to have enough capital to match in order for Bob to win. The <span class="math-container">$c_i$</span> values and the <span class="math-container">$l_{ik}$</span> values are to be chosen so that Alice's only possible winning strategy is as follows, for some clause <span class="math-container">$C_i$</span>:</p>

<blockquote>
  <p><strong>Alice's clause <span class="math-container">$C_i$</span> strategy:</strong> let <span class="math-container">$C_i = L_{i1} \vee L_{i2} \vee L_{i3}$</span>. For each <span class="math-container">$k \in \{1, 2, 3\}$</span>, if <span class="math-container">$L_{ik} = x_j$</span> or <span class="math-container">$\neg x_j$</span>, move to <span class="math-container">$C_i?A$</span> in the variable game for <span class="math-container">$x_j$</span>. Also move to <span class="math-container">$C_iA$</span> in the capital sink game.</p>
</blockquote>

<p>(<span class="math-container">$C_i?A$</span> denotes either <span class="math-container">$C_iTA$</span> or <span class="math-container">$C_iFA$</span>, only one of which is reachable in a given variable game after Bob's opening moves.)</p>

<p>If Bob's opening corresponds to a truth assignment that leaves some clause <span class="math-container">$C_i$</span> unsatisfied, then Alice choosing <span class="math-container">$C_i$</span> and implementing the strategy above costs Alice <span class="math-container">$l_{i1} + l_{i2} + l_{i3} + c_i$</span> capital to implement, and Bob the same to beat; if on the other hand <span class="math-container">$C_i$</span> is satisfied, then Bob's counterplay gets a discount of at least <span class="math-container">$1$</span>. Our goal in setting the <span class="math-container">$c_i$</span> and <span class="math-container">$l_{ik}$</span> values and Alice and Bob's starting capitals is to ensure that said discount is the deciding factor in whether Alice or Bob wins.</p>

<p>To that end, set <span class="math-container">$b = m + 1$</span>, and set</p>

<p><span class="math-container">$l_{ik} = 2b^{10} + ib^{2k}$</span> for each <span class="math-container">$k \in \{1, 2, 3\}$</span>, </p>

<p><span class="math-container">$c_i = 3b^{10} + b^8 - \sum_{k=1}^3 ib^{2k}$</span>,</p>

<p>Alice's starting capital to <span class="math-container">$9b^{10} + b^8$</span>,</p>

<p>and Bob's starting capital to <span class="math-container">$9b^{10} + b^8 + n - 1.$</span></p>

<p>Note that all of these values are polynomial in <span class="math-container">$m$</span>, so the MULTI-GAME instance outputted by the reduction has size polynomial in the size of the 3SAT instance even if these costs are encoded in unary.</p>

<p>Note also that for each clause <span class="math-container">$C_i$</span>, <span class="math-container">$l_{i1} + l_{i2} + l_{i3} + c_i = 9b^{10} + b^8$</span> is Alice's starting capital. (Which is also <span class="math-container">$1$</span> greater than Bob's capital after making the first <span class="math-container">$n$</span> moves.)</p>

<p>First of all, it is immediately clear that if Bob's opening defines a truth assignment that leaves a clause <span class="math-container">$C_i$</span> unsatisfied, then Alice wins using her clause <span class="math-container">$C_i$</span> strategy given above.</p>

<p>If Bob's opening satisies all clauses, we can argue constraints on Alice's options which rule out any other possibility of Alice winning. Note that the order in which Alice makes her moves is irrelevant, as Bob's responses are forced and the total capital Bob will require to respond to Alice's moves is unchanged by the order of Alice's moves.</p>

<ul>
<li><strong>Alice can't make more than 4 moves:</strong> if Alice makes 5 or more moves, then her moves have a total cost of <span class="math-container">$\ge 5b^{10}$</span>, which exceeds her budget.</li>
<li><strong>Alice must make 4 moves:</strong> if Alice selects 3 moves from the capital sink game then her total cost is <span class="math-container">$\ge 9b^{10} + 3b^8 - 3b^7 &gt; 9b^{10} + 2b^8$</span> which is over budget. If she selects even one move of 3 from a variable game, then her total cost is <span class="math-container">$\le 8b^{10} + 2b^8 + b^7$</span> which is is substantially less than Bob's post-opening capital, so Bob can easily afford the counterplay.</li>
<li><strong>Alice must select a move from the capital sink game:</strong> if she doesn't, then she selects 4 moves from variable games, with total cost <span class="math-container">$\le 8b^{10} + 4b^7$</span>, and again Bob can easily afford the counterplay. (Note that if there were a separate capital sink game per clause, we could even show that Alice must play in exactly one such game.)</li>
</ul>

<p>From this stage we can disregard the <span class="math-container">$b^{10}$</span> and <span class="math-container">$b^8$</span> terms in the move costs chosen, as they will always sum to <span class="math-container">$9b^{10} + b^8$</span>.
Since Alice must choose exactly one move in the capital sink game, assume that move is to <span class="math-container">$C_iA$</span>. Then Alice has (ignoring <span class="math-container">$b^{10}$</span> and <span class="math-container">$b^8$</span> terms) <span class="math-container">$\sum_{k=1}^3 ib^{2k}$</span> capital remaining, and Bob has <span class="math-container">$1$</span> less than this amount remaining.</p>

<ul>
<li><strong>Alice must select at least one move costing <span class="math-container">$l_{j3}$</span> for some clause <span class="math-container">$C_j$</span>:</strong> if she doesn't, then her moves cost (again lower-order terms) <span class="math-container">$\le 3b^5$</span>, and Bob has more than enough capital for counterplay.</li>
<li><strong>Said move costing <span class="math-container">$l_{j3}$</span> must be the move costing <span class="math-container">$l_{i3}$</span>:</strong> it can't be a move costing <span class="math-container">$l_{j3}$</span> for <span class="math-container">$j &gt; i$</span>, otherwise this move alone costs <span class="math-container">$\ge (i+1)b^6$</span> which is greater than Alice's remaining budget. If it's <span class="math-container">$l_{j3}$</span> for <span class="math-container">$j &lt; i$</span>, then the <span class="math-container">$l_{(i - j)3}$</span> cost move must also be chosen by Alice to exhaust the <span class="math-container">$b^6$</span>-order term in Bob's remaining budget. But then Either the <span class="math-container">$b^2$</span>-order term in Bob's remaining budget or the <span class="math-container">$b^2$</span>-order term doesn't get exhausted, so Bob wins handily.</li>
</ul>

<p>Similar arguments should establish that Alice must select the moves costing <span class="math-container">$l_{i2}$</span> and <span class="math-container">$l_{i1}$</span>. If Bob's truth assignment satisfies <span class="math-container">$C_i$</span>, then even this strategy doesn't work, as the discount Bob gets on one of the <span class="math-container">$l_{ik}$</span>-based costs makes up for the <span class="math-container">$1$</span> less capital he has after his opening.</p>

<hr>

<p>A remark on my previous answer: it's obvious in hindsight that, for the TABLE-GAME variant of MULTI-GAME I defined in the comments of that answer, a knapsack-style DP suffices to determine which player has a winning strategy. You can argue that Bob's best strategy is to always respond to a losing state in a given game table with the minimal investment possible (this can't cut off a subsequent move for Bob that he would have otherwise), and from there that the order of Alice's moves doesn't matter. It then becomes a matter of choosing a split of Alice's capital among the games such that the sum of Bob's minimal winning responses over those games exceeds his budget, which can be reframed as a knapsack-style problem, which has a polynomial-time DP due to the unary representation of costs. (My recurrence actually would've worked for TABLE-GAME if I framed it in terms of Alice.)</p>

<p>It turns out that even a simple tree structure for each game, with constant depth and really only one meaningful fork per game (namely those at the start which force Bob to choose a truth assignment) is sufficient to get NP-hardness. I had some ideas for getting rid of that initial fork, which stalled out at somehow forcing Bob to invest a relatively large fixed amount of capital in <span class="math-container">$n$</span> games without Alice having to precommit to those games in advance, but obviously since TABLE-GAME is in P this is not possible without the fork.</p>

<p>I haven't thought much about your special case from <strong>UPD3</strong>. I suspect it's also NP-hard, for the reason that my variable gadgets seem at a glance like they may be adaptable to those constraints, but I probably won't look into it further.</p>

CC BY-SA 4.0
2022-01-08T11:27:10.467Z
,Could you please write me on e-mail (almas239@gmail.com) or write your e-mail?
Alexey Milovanov
CC BY-SA 4.0
2022-01-12T00:40:43.537Z
@AlexeyMilovanov Emailed.
gdmclellan
CC BY-SA 4.0
2020-04-04T17:09:45.513Z
2020-04-04T17:42:10.817Z
2020-04-04T17:42:10.817Z
gdmclellan
<p><strong>Update:</strong> likely incorrect, leaving up for now as a record of having explored an avenue. See comments.</p>

<p><strong>Update 2:</strong> definitely incorrect.</p>

<p>Consider a graph of form (B) -1-> (A) -1-> (B), i.e. <span class="math-container">$G = (V, E)$</span>, where <span class="math-container">$V = \{1, 2, 3\}$</span>, <span class="math-container">$E = \{(1, 2), (2, 3)\}$</span>, vertices 1, 2, 3 are labeled B, A, B respectively, and edges are all assigned costs of 1.</p>

<p>Define a 3-game instance of MULTI-GAME by setting <span class="math-container">$m_A = m_B = 2$</span>, <span class="math-container">$G_1 = G_2 = G_3 = G$</span>, with all three games starting on vertex 1. Clearly Alice cannot win this game.</p>

<p>However, the recurrence below fails for <span class="math-container">$M[3,2,2]$</span>: there is no split of Bob's funds <span class="math-container">$2-u, u$</span> between the first two games and the third game such that for all splits of Alice's funds <span class="math-container">$v, 2 - v$</span>, both <span class="math-container">$M[2, 2 - u, 2 - v] = B$</span> and <span class="math-container">$W[3, u, v] = B$</span>. If <span class="math-container">$u = 1$</span> or <span class="math-container">$u = 2$</span>, then <span class="math-container">$M[2, 2 - u, 2] = A$</span>; and if <span class="math-container">$u = 0$</span> then <span class="math-container">$W[3, u, 2] = A$</span>.</p>

<p>I don't see an immediate way to salvage this approach. Reversing the order of quantification on <span class="math-container">$u$</span> and <span class="math-container">$v$</span> makes the recurrence fail on the instance in update 2 of the question post.</p>

<hr>

<p>Given a MULTI-GAME instance <span class="math-container">$m_A, m_B, G_1, \dots, G_n,$</span></p>

<p>Precompute</p>

<p><span class="math-container">$W[k, x, y] = \begin{cases}A &amp; \text{if Alice wins GAME on $G_k$ with initial funds $x$ for Alice and $y$ for Bob,} \\ B &amp; \text{otherwise}\end{cases}$</span></p>

<p>for all games and all <span class="math-container">$x \le m_A$</span>, <span class="math-container">$y \le m_B$</span>.</p>

<p>Denote by <span class="math-container">$M[k, x, y]$</span> the winner of MULTI-GAME if the instance is restricted to the first <span class="math-container">$k$</span> graphs and funds <span class="math-container">$x \le m_A$</span>, <span class="math-container">$y \le m_B$</span>. (<span class="math-container">$M[k, x, y] = B$</span> if Bob wins, <span class="math-container">$A$</span> otherwise.) Then</p>

<p><span class="math-container">$M[1, x, y] = W[1, x, y]$</span></p>

<p>and</p>

<p><span class="math-container">$M[k+1, x, y] = B \quad\text{if and only if}\quad \exists v \forall u, W[k+1, u, v] = B \:\:\text{and}\:\: M[k, x-u, y-v] = B.$</span></p>

<p>Output "yes" if <span class="math-container">$M[n, m_A, m_B] = A$</span>, "no" otherwise.</p>

CC BY-SA 4.0
2019-09-03T17:16:38.967Z
Your algorithm is wrong. Consider the graph at the picture in my post. Consider the MULTI-GAME with two such graphs. Here W[1,0,2]=W[2,0,2] =B and W[1,1,3]=W[2,1,3]=B. However, for MULTI-GAME with m_A=1 and m_B=5 Alice wins
Alexey Milovanov
CC BY-SA 4.0
2019-09-03T17:19:16.330Z
Oops. Try univerally quantifying $u$ in the recurrence? I'll check it over in the meantime.
gdmclellan
CC BY-SA 4.0
2019-09-03T18:11:12.463Z
@AlexeyMilovanov with changes to the quantifiers the recurrence should go through for the example. But you have put doubt in my mind about this approach. It seems like it might require Bob to lay out a single distribution of funds that beats all distributions Alice could conceive of.
That said, I'm not sure that I've been persuaded off of the core idea here: that this problem isn't really about GAME. Is anything known about the related problem where each GAME instance is replaced by a simple table a la W above?
gdmclellan
CC BY-SA 4.0
2019-09-03T18:41:26.720Z
Table W does not define the winner. I do not know is it true for some another table...
Alexey Milovanov
CC BY-SA 4.0
2019-09-04T05:14:46.857Z
@AlexeyMilovanov Table W by definition determines the winner of GAME instances isolated to any specific one of the input graphs. I'm not sure why you'd say otherwise. I have updated my answer with a counterexample though, in case there was any lingering doubt that it was incorrect.
gdmclellan
CC BY-SA 4.0
2019-09-04T05:28:50.963Z
Also to expand on my question: we'll call a table $W:[n]\times[m]\to\{A,B\}$ a game table if $W[i,j]=A\implies W[p, j] = A$ for all $p > i$ and $W[i,j]=B\implies W[i, q] = B$ for all $q > j$. Clearly $W[k, \cdot, \cdot]$ in the answer above has this property for any $k$, and given any game table $W$ you could make a GAME instance graph that produces $W$ by building a "grid graph" with unit edge costs. GAME instances do seem more general, though: you could e.g. join two different grid graphs such that the first move "chooses" which to play on. But is the analogous MULTI-TABLE-GAME problem hard?
gdmclellan
CC BY-SA 4.0
2019-09-04T07:26:50.340Z
I mean all tables W for GAMES do not define the winner in MULTI-GAME.
Alexey Milovanov
CC BY-SA 4.0
2019-09-03T16:56:28.933Z
2019-09-04T04:59:16.930Z
2019-09-04T04:59:16.930Z
gdmclellan
<p>Per my comments above, here's a reduction that I think shows the problem to be PSPACE-hard (and presumably complete). Let <span class="math-container">$[n]$</span> be the graph with <span class="math-container">$n+1$</span> nodes, numbered <span class="math-container">$n\ldots 0$</span>, with a link from node <span class="math-container">$i+1$</span> to <span class="math-container">$i$</span> for all <span class="math-container">$0\leq i\lt n$</span>, all nodes other than <span class="math-container">$0$</span> marked for A, node <span class="math-container">$0$</span> marked for B, and the chit initially pleased on <span class="math-container">$n$</span>. (All edges here have cost 1). It should be clear that B wins <span class="math-container">$[n]$</span> iff they have <span class="math-container">$\geq n$</span> dollars. (If need be, we can give unit-cost edges from each node other than <span class="math-container">$0$</span> to itself, since A will always want to keep the chit as far from <span class="math-container">$0$</span> as possible and B will always want to move it closer; indeed, if self-links aren't allowed then we can 'double up' the line into two copies, forming a ladder with bidirectional links.</p>

<p>Now, consider the graph <span class="math-container">$G$</span> with two additional nodes <span class="math-container">$\alpha$</span> and <span class="math-container">$\beta$</span>: node <span class="math-container">$\alpha$</span> links to some <span class="math-container">$[i]$</span> and to <span class="math-container">$\beta$</span>, and node <span class="math-container">$\beta$</span> has links to <span class="math-container">$[j]$</span> and <span class="math-container">$[k]$</span> (Presume that <span class="math-container">$j\lt k$</span>). All of these links have cost zero. (This isn't strictly necessary for the reduction, but it's convenient.) Both <span class="math-container">$\alpha$</span> and <span class="math-container">$\beta$</span> are marked for A. Clearly from <span class="math-container">$\beta$</span> B will want to go to <span class="math-container">$[j]$</span> whereas A will want to go to <span class="math-container">$[k]$</span> (A would prefer not to move at all, but it can be worth moving to <span class="math-container">$[k]$</span> to make the cost higher for B). Similarly, it can be arranged that B never wants to move to <span class="math-container">$[i]$</span> and that A always wants to. Then the game-theoretical value of these positions is <span class="math-container">$\{i\mid\{j\mid k\}\}$</span>. But it's known that establishing the value of a sum of games (i.e. graphs) of this type is PSPACE-complete; this was shown in <a href="http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-348.pdf" rel="nofollow noreferrer">Laura Jo Yedwah's Masters' thesis</a>. So your problem is at least PSPACE-hard.</p>

CC BY-SA 4.0
2020-02-06T03:18:16.073Z
The proofs in the thesis seem to use large values of i, j and k in the games. Note that here all weights may be assumed to be at most the players' capitals, which were represented in unary.
Antti Röyskö
CC BY-SA 4.0
2020-02-06T19:28:15.673Z
@AnttiRöyskö I'll have to take a much closer look at the proof, then; I believe the result on PSPACE-completeness of Go endgames uses the thesis result and assumes unary counting as well (since there, i/j/k come from the sizes of board regions).
Steven Stadnicki
CC BY-SA 4.0
2020-02-06T23:16:10.217Z
It is unclear: are there edges to $\alpha$ or $\beta$? If all (except $0$) nodes are marked by A then Alice will not move...
Alexey Milovanov
CC BY-SA 4.0
2020-02-07T01:09:57.660Z
@AlexeyMilovanov Whoops, that's my fault — $\alpha$ should also link to $\beta$. Also, Alice may still want to move from such a position; imagine the case where we just have a single node, $\alpha$, with links to $[i] \gt [j]$, and Bob has $j+1$ dollars. Then Alice will move to $[i]$ to keep Bob from moving to $[j]$ and eventually winning.
Steven Stadnicki
CC BY-SA 4.0
2020-02-08T17:08:16.907Z
@StevenStadnicki it is steal unclear: Is it  possible to achieve $\alpha$ or $\beta$ from initital node $n$? Also if not all chips are at B then Bob has to go, so at your game either Bob will achieve A in all graphs (and win) or Bob will not have enough many and will lose.
Alexey Milovanov
CC BY-SA 4.0
2020-02-05T23:05:28.470Z
2020-02-07T01:10:50.520Z
2020-02-07T01:10:50.520Z
Steven Stadnicki
<p>Consider the following game on a directed weighted graph <span class="math-container">$G$</span> with a chip at some node.</p>

<p>All nodes of <span class="math-container">$G$</span> are marked by A or B. </p>

<p>There are two players Alice and Bob. The goal of Alice (Bob) is to shift the chip to a node that marked by A (B).</p>

<p>Initially Alice and Bob have <span class="math-container">$m_A$</span> and <span class="math-container">$m_B$</span> dollars respectively.</p>

<p>If a player is in a losing position (i.e., current position of the chip is marked by opposite letter) he or she can move the chip to a neighboring node. Such move costs some dollars (the weight of the corresponding edge).</p>

<p>The player loses if he or she is in a losing position and has not money to fix it. </p>

<p>Now consider the language GAME that consists of all directed weighted graphs <span class="math-container">$G$</span> (all weights are positive integers), initial position of the chip, and capitals of Alice and Bob that are given in the unary representation</p>

<p>such that Alice has a wining strategy at this game. </p>

<p>The language GAME belongs to <strong>P</strong>. Indeed, the current position of the game is defined by the position of the chip and the current capitals of Alice and Bob, so dynamic programming works (here it is important that initial capitals are given in the unary representation). </p>

<p>Now consider the following generalization of this game. Consider several directed weighted graphs <span class="math-container">$G_1, \ldots G_n$</span> with a chip at each graph. All nodes of all graphs are marked by A and B. Now Bob wins if all chips are marked by B and Alice wins  if at least one chip marked by A.</p>

<p>Consider the language MULTI-GAME that consists of all graphs <span class="math-container">$G_1, \ldots, G_n$</span>, initial positions and capitals <span class="math-container">$m_A$</span> and <span class="math-container">$m_B$</span> (in the unary representation) such that Alice wins at the corresponding game.  Here it is important that capitals are common for all graphs so, it is not just several independent GAMEs.</p>

<p><strong>Question</strong> What is the complexity of the language MULTI-GAMES? (Is it also belongs to <strong>P</strong> or there are some reasons to thing that this problem is hard?)</p>

<p><strong>UPD1</strong> <a href="https://cstheory.stackexchange.com/users/8237/neal-young">Neal Young</a> suggested to use Conway's theory. However I do not know is it possible to use this theory for several games with common capital. </p>

<p><strong>UPD2</strong> I want to show an example that shows that MULTI-GAME is not very simple.  Let Alice split her capital <span class="math-container">$m_A$</span> to some <span class="math-container">$n$</span> terms <span class="math-container">$m_A = a_1 + a_2 + \ldots a_n$</span> (She is going to use <span class="math-container">$a_i$</span> dollars for <span class="math-container">$i$</span>-th graph). Define <span class="math-container">$b_i$</span> as the minimal number such that in <span class="math-container">$i$</span>-th game Bob wins if Alice and Bob have <span class="math-container">$a_i$</span> and <span class="math-container">$b_i$</span> dollars respectively. If <span class="math-container">$b_1 + \ldots b_n &gt; m_B$</span> (for  some spliting <span class="math-container">$m_A = a_1 + a_2 + \ldots a_n$</span>) then Alice wins. However, the opposite is not true. Consider two copies of the following graph (initially the chip is at the left up A):
<a href="https://i.sstatic.net/ctQIe.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ctQIe.jpg" alt="enter image description here"></a></p>

<p>For one graph Bob wins if <span class="math-container">$m_A=0$</span> and <span class="math-container">$m_B=2$</span> or if <span class="math-container">$m_A=1$</span> and <span class="math-container">$m_B=3$</span>.
However for the game with two copies of this graph Bob loses if <span class="math-container">$m_A=1$</span> and <span class="math-container">$m_B=5$</span>. Indeed, Bob have to spend <span class="math-container">$4$</span> or <span class="math-container">$5$</span> dollars to shift both chips to a node marked by <span class="math-container">$B$</span>. Then Alice can shift at least one chip to a node marked by A. After that Bob have not money to save his position.</p>

<p><strong>UPD3</strong> Since the question for arbitrary graphs seems difficult consider specific graphs. Denote the nodes of some graph <span class="math-container">$G_i$</span> as <span class="math-container">$1, \ldots k$</span>. My restriction is the following: for every pair <span class="math-container">$i&lt;j$</span> there exists edge from <span class="math-container">$i$</span> to <span class="math-container">$j$</span> and there is no the reverse edge. Also there exists a restriction for the costs of edges: for <span class="math-container">$i&lt;j&lt;k$</span> the edge <span class="math-container">$j$</span> to <span class="math-container">$k$</span> is not greater than from <span class="math-container">$i$</span> to <span class="math-container">$k$</span>. </p>

CC BY-SA 4.0
2019-08-21T23:54:25.300Z
in MULTI-GAME, what constitutes a move?  The player makes one move in every graph?  Or chooses one graph to make one move in?  Have you looked into whether Conway's theory of games (heating and cooling) applies here?  (Some references can be found here: https://en.wikipedia.org/wiki/John_Horton_Conway#Combinatorial_game_theory)
Neal Young
CC BY-SA 4.0
2019-08-25T04:25:53.160Z
@Neal Young The player chooses one graph to make one move in.
Alexey Milovanov
CC BY-SA 4.0
2019-08-25T22:03:16.230Z
FWIW, If I recall, Conway's theory of games does consider how to play games that are composed from other games in that manner (in each move, the player chooses one of the sub-games to move in).  I don't know what relevance his theory has w.r.t. computational complexity though.
Neal Young
CC BY-SA 4.0
2019-08-30T06:29:29.573Z
@NealYoung Thank you, but as I understand the problem is that players have common capitals for all games. I do not find how it can be fixed by Conway's theory...
Alexey Milovanov
CC BY-SA 4.0
2019-08-30T12:27:39.460Z
Is Alice (Bob) forced to move the chip if it is on A (B) node? What are the winning condition of the multi-game? Does B win also when all the chips are on B nodes, but A still have some money? You say that A wins if at least one chip is on A, so A can simply try to keep two chips into a node marked with A in the "less expensive" two graphs; as soon as B move one of the two chips away from node A, Alice brings it back (and ignore the other graphs)
Marzio De Biasi
CC BY-SA 4.0
2019-08-30T14:41:23.383Z
In the GAME Alice (Bob) forced to move the chip if it is on B(A). In the MULTI-GAME Alice forced to move a chip if all chips are on B and Bob forced to move a chip that is on A. A player loses if he or she has not money to make such shift.
Alexey Milovanov
CC BY-SA 4.0
2019-08-30T14:45:44.050Z
@MarzioDeBiasi >You say that A wins if at least one chip is on A, so A can simply try to keep two chips into a node marked with A in the "less expensive" two graphs; as soon as B move one of the two chips away from node A, Alice brings it back (and ignore the other graphs)
Alice indeed can plays only in two or one graph. For example if she wins in some graph (with initial capitals $m_A$ and $m_B$) then she wins in all MULTI-GAME. The problem is that the reverse is not true...
Alexey Milovanov
CC BY-SA 4.0
2020-02-05T20:06:33.000Z
I'm going to second the comment that Conway's theory may still be relevant here; in particular, I wouldn't be surprised if there's some sort of reduction from a question of the form 'is the sum of these games' values greater than zero?' (possibly by including a 'simple' graph that corresponds to a position of value $n$; for instance, a directed line on $n$ nodes where all but the terminal node are marked $A$ and the edge weight is 1 on all edges). I'm pretty sure you could get games of value $\{m\mid\{n\mid p\}\}$ with simple graphs. (cont)
Steven Stadnicki
CC BY-SA 4.0
2020-02-05T20:07:34.320Z
And IIRC it's known that the positivity of a sum of those games is NP-HARD (I can't recall if it's NPC or PSPACE complete, and I don't have my references handy), so that would give you a comparable complexity result for your question.
Steven Stadnicki
CC BY-SA 4.0
2020-03-08T15:33:59.083Z
Is MULTI-GAME equivalent to a GAME instance where the game graph is some kind of cross product of the game graphs $G_1, \dots, G_n$ and appropiate edges, weights and labelings? Consider a Multigame instance with two subgames $G_1, G_2$ and define $G$ as: $V(G) = V(G_1) \times V(G_2)$ and $( (u_1, u_2), (u_1, v_2)) \in E(G)$ iff $(u_2, v_2) \in E(G_2)$ with weight $w_2(u_2, v_2)$ (and vice versa) and $(v_1, v_2)$ has label B iff $v_1$and $v_2$ have label B in $G_1$ and $G_2$ resp.
Daniel
CC BY-SA 4.0
2020-03-08T19:08:03.147Z
@Daniel exactly
Alexey Milovanov
<cc.complexity-theory><complexity-classes><gt.game-theory>
A game on several graphs
Alexey Milovanov
# A game on several graphs

(Asked by: username_0 on 2019-08-08)

Consider the following game on a directed weighted graph $G$ with a chip at some node.

All nodes of $G$ are marked by A or B.

There are two players Alice and Bob. The goal of Alice (Bob) is to shift the chip to a node that marked by A (B).

Initially Alice and Bob have $m\_A$ and $m\_B$ dollars respectively.

If a player is in a losing position (i.e., current position of the chip is marked by opposite letter) he or she can move the chip to a neighboring node. Such move costs some dollars (the weight of the corresponding edge).

The player loses if he or she is in a losing position and has not money to fix it.

Now consider the language GAME that consists of all directed weighted graphs $G$ (all weights are positive integers), initial position of the chip, and capitals of Alice and Bob that are given in the unary representation

such that Alice has a wining strategy at this game.

The language GAME belongs to **P**. Indeed, the current position of the game is defined by the position of the chip and the current capitals of Alice and Bob, so dynamic programming works (here it is important that initial capitals are given in the unary representation).

Now consider the following generalization of this game. Consider several directed weighted graphs $G\_1, \ldots G\_n$ with a chip at each graph. All nodes of all graphs are marked by A and B. Now Bob wins if all chips are marked by B and Alice wins if at least one chip marked by A.

Consider the language MULTI-GAME that consists of all graphs $G\_1, \ldots, G\_n$, initial positions and capitals $m\_A$ and $m\_B$ (in the unary representation) such that Alice wins at the corresponding game. Here it is important that capitals are common for all graphs so, it is not just several independent GAMEs.

**Question** What is the complexity of the language MULTI-GAMES? (Is it also belongs to **P** or there are some reasons to thing that this problem is hard?)

**UPD1** [username_1](https://cstheory.stackexchange.com/users/8237/neal-young) suggested to use Conway's theory. However I do not know is it possible to use this theory for several games with common capital.

**UPD2** I want to show an example that shows that MULTI-GAME is not very simple. Let Alice split her capital $m\_A$ to some $n$ terms $m\_A = a\_1 + a\_2 + \ldots a\_n$ (She is going to use $a\_i$ dollars for $i$-th graph). Define $b\_i$ as the minimal number such that in $i$-th game Bob wins if Alice and Bob have $a\_i$ and $b\_i$ dollars respectively. If $b\_1 + \ldots b\_n > m\_B$ (for some spliting $m\_A = a\_1 + a\_2 + \ldots a\_n$) then Alice wins. However, the opposite is not true. Consider two copies of the following graph (initially the chip is at the left up A):
[![enter image description here](https://i.sstatic.net/ctQIe.jpg)](https://i.sstatic.net/ctQIe.jpg)

For one graph Bob wins if $m\_A=0$ and $m\_B=2$ or if $m\_A=1$ and $m\_B=3$.
However for the game with two copies of this graph Bob loses if $m\_A=1$ and $m\_B=5$. Indeed, Bob have to spend $4$ or $5$ dollars to shift both chips to a node marked by $B$. Then Alice can shift at least one chip to a node marked by A. After that Bob have not money to save his position.

**UPD3** Since the question for arbitrary graphs seems difficult consider specific graphs. Denote the nodes of some graph $G\_i$ as $1, \ldots k$. My restriction is the following: for every pair $i there exists edge from $i$ to $j$ and there is no the reverse edge. Also there exists a restriction for the costs of edges: for $i the edge $j$ to $k$ is not greater than from $i$ to $k$.

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

> **Comments:**
> **username_1**: in MULTI-GAME, what constitutes a move?  The player makes one move in every graph?  Or chooses one graph to make one move in?  Have you looked into whether Conway's theory of games (heating and cooling) applies here?  (Some references can be found here: https://en.wikipedia.org/wiki/John_Horton_Conway#Combinatorial_game_theory)  
> **username_0**: @username_1 The player chooses one graph to make one move in.  
> **username_1**: FWIW, If I recall, Conway's theory of games does consider how to play games that are composed from other games in that manner (in each move, the player chooses one of the sub-games to move in).  I don't know what relevance his theory has w.r.t. computational complexity though.  
> **username_0**: @NealYoung Thank you, but as I understand the problem is that players have common capitals for all games. I do not find how it can be fixed by Conway's theory...  
> **username_2**: Is Alice (Bob) forced to move the chip if it is on A (B) node? What are the winning condition of the multi-game? Does B win also when all the chips are on B nodes, but A still have some money? You say that A wins if at least one chip is on A, so A can simply try to keep two chips into a node marked with A in the "less expensive" two graphs; as soon as B move one of the two chips away from node A, Alice brings it back (and ignore the other graphs)  
> **username_0**: In the GAME Alice (Bob) forced to move the chip if it is on B(A). In the MULTI-GAME Alice forced to move a chip if all chips are on B and Bob forced to move a chip that is on A. A player loses if he or she has not money to make such shift.  
> **username_0**: @MarzioDeBiasi >You say that A wins if at least one chip is on A, so A can simply try to keep two chips into a node marked with A in the "less expensive" two graphs; as soon as B move one of the two chips away from node A, Alice brings it back (and ignore the other graphs) Alice indeed can plays only in two or one graph. For example if she wins in some graph (with initial capitals $m_A$ and $m_B$) then she wins in all MULTI-GAME. The problem is that the reverse is not true...  
> **username_3**: I'm going to second the comment that Conway's theory may still be relevant here; in particular, I wouldn't be surprised if there's some sort of reduction from a question of the form 'is the sum of these games' values greater than zero?' (possibly by including a 'simple' graph that corresponds to a position of value $n$; for instance, a directed line on $n$ nodes where all but the terminal node are marked $A$ and the edge weight is 1 on all edges). I'm pretty sure you could get games of value $\{m\mid\{n\mid p\}\}$ with simple graphs. (cont)  
> **username_3**: And IIRC it's known that the positivity of a sum of those games is NP-HARD (I can't recall if it's NPC or PSPACE complete, and I don't have my references handy), so that would give you a comparable complexity result for your question.  
> **username_4**: Is MULTI-GAME equivalent to a GAME instance where the game graph is some kind of cross product of the game graphs $G_1, \dots, G_n$ and appropiate edges, weights and labelings? Consider a Multigame instance with two subgames $G_1, G_2$ and define $G$ as: $V(G) = V(G_1) \times V(G_2)$ and $( (u_1, u_2), (u_1, v_2)) \in E(G)$ iff $(u_2, v_2) \in E(G_2)$ with weight $w_2(u_2, v_2)$ (and vice versa) and $(v_1, v_2)$ has label B iff $v_1$and $v_2$ have label B in $G_1$ and $G_2$ resp.  
> **username_0**: @username_4 exactly  

---

## 3 answers

### Answer by username_5 on 2020-04-04. Score: 2 | Accepted answer

Since username_3's answer doesn't appear to have been accepted by the asker, I figured it may still be helpful to provide an update: I have a reduction from 3SAT to MULTI-GAME. I haven't looked at Steven's answer carefully or followed through the link he provided, but based on the following reduction I won't be surprised if MULTI-GAME is indeed PSPACE-complete. I might not bother extending this result beyond NP-hardness, however.

A 3SAT instance consists of clauses $C\_1, \dots, C\_m$, each clause being of the form $C\_i = L\_{i1} \vee L\_{i2} \vee L\_{i3}$ where each $L\_{ik}$ is either one of the variables $x\_1, \dots, x\_n$ or the negation of one of the variables.

Given such a 3SAT instance, the reduction creates a MULTI-GAME instance consisting of $n + 1$ games -- one for each variable and another game used as an excess capital sink. First we'll define the structure of the graphs for each game, then look at an example and discuss the core idea, and then we'll figure out what exact costs to assign to the edges to make the reduction hold firm.

First, the variable game graph $G\_j$ for each variable $x\_j$:

1. Create vertex labeled $x\_j$ marked with an A (i.e. a winning vertex for Alice). The chip for $G\_j$ starts on vertex $x\_j$.
2. Create a vertex labeled $T$ and a vertex labeled $F$, each marked with a B (i.e. both are winning positions for Bob). Create directed edges from $x\_j$ to both $T$ and $F$, both with costs of $1$.
3. For each literal $L\_{ik}$ of clause $C\_i$, if $L\_{ik} = x\_j$ or $L\_{ik} = \neg x\_j$, create vertices labeled $C\_iTA$ and $C\_iFA$ marked with A and vertices labeled $C\_iTB$ and $C\_iFB$ marked with B. Add edges $(T, C\_iTA)$ and $(F, C\_iFA)$ with costs both set to $l\_{ik}$. (We'll define $l\_{ik}$ later.)

   Add edges $(C\_iTA, C\_iTB)$ and $(C\_iTA, C\_iTB)$. If $L\_{ik} = x\_j$, then set $(C\_iTA, C\_iTB)$'s cost to $l\_{ik} - 1$ and $(C\_iTA, C\_iTB)$'s cost to $l\_{ik}$. Otherwise set $(C\_iTA, C\_iTB)$'s cost to $l\_{ik}$ and $(C\_iTA, C\_iTB)$'s cost to $l\_{ik} - 1$.

The capital sink game:

1. Create a vertex labeled $C$, marked with B.
2. For each clause $C\_i$, create a vertex labeled $C\_iA$ marked with A, and a vertex labeled $C\_iB$ marked with B. Create an edge $(C, C\_iA)$ with edge cost $c\_i$ (again to be determined below), and an edge $(C\_iA, C\_iB)$ also with edge cost $c\_i$.

This is a lot to take in, so hopefully an example makes this a little more digestible. Our 3SAT instance is as follows:

$C\_1 = x\_1 \vee x\_2 \vee \neg x\_3$

$C\_2 = x\_2 \vee x\_3 \vee \neg x\_4$

$C\_3 = \neg x\_1 \vee \neg x\_3 \vee x\_4$

The reduction turns this instance into 4 variable game graphs and 1 capital sink graph. In the diagrams below, the red vertices are marked with A (i.e. are winning positions for Alice), and the cyan vertices are marked with B (are winning positions for Bob).

Graph for $x\_1$:

[![enter image description here](https://i.sstatic.net/C1WA5.png)](https://i.sstatic.net/C1WA5.png)

Graph for $x\_2$:

[![enter image description here](https://i.sstatic.net/3kbNn.png)](https://i.sstatic.net/3kbNn.png)

Graph for $x\_3$:

[![enter image description here](https://i.sstatic.net/DWvbu.png)](https://i.sstatic.net/DWvbu.png)

Graph for $x\_4$:

[![enter image description here](https://i.sstatic.net/m32Lr.png)](https://i.sstatic.net/m32Lr.png)

Graph for capital sink:

[![enter image description here](https://i.sstatic.net/hqno3.png)](https://i.sstatic.net/hqno3.png)

The idea is as follows:

Bob is forced to make the first $n$ moves in order to get out of losing positions in the $n$ variable games. Each such move encodes an assignment of true or false to the corresponding variable.

Alice will then have enough capital to make exactly 4 moves, each of which Bob will need to have enough capital to match in order for Bob to win. The $c\_i$ values and the $l\_{ik}$ values are to be chosen so that Alice's only possible winning strategy is as follows, for some clause $C\_i$:

> **Alice's clause $C\_i$ strategy:** let $C\_i = L\_{i1} \vee L\_{i2} \vee L\_{i3}$. For each $k \in \{1, 2, 3\}$, if $L\_{ik} = x\_j$ or $\neg x\_j$, move to $C\_i?A$ in the variable game for $x\_j$. Also move to $C\_iA$ in the capital sink game.

($C\_i?A$ denotes either $C\_iTA$ or $C\_iFA$, only one of which is reachable in a given variable game after Bob's opening moves.)

If Bob's opening corresponds to a truth assignment that leaves some clause $C\_i$ unsatisfied, then Alice choosing $C\_i$ and implementing the strategy above costs Alice $l\_{i1} + l\_{i2} + l\_{i3} + c\_i$ capital to implement, and Bob the same to beat; if on the other hand $C\_i$ is satisfied, then Bob's counterplay gets a discount of at least $1$. Our goal in setting the $c\_i$ and $l\_{ik}$ values and Alice and Bob's starting capitals is to ensure that said discount is the deciding factor in whether Alice or Bob wins.

To that end, set $b = m + 1$, and set

$l\_{ik} = 2b^{10} + ib^{2k}$ for each $k \in \{1, 2, 3\}$,

$c\_i = 3b^{10} + b^8 - \sum\_{k=1}^3 ib^{2k}$,

Alice's starting capital to $9b^{10} + b^8$,

and Bob's starting capital to $9b^{10} + b^8 + n - 1.$

Note that all of these values are polynomial in $m$, so the MULTI-GAME instance outputted by the reduction has size polynomial in the size of the 3SAT instance even if these costs are encoded in unary.

Note also that for each clause $C\_i$, $l\_{i1} + l\_{i2} + l\_{i3} + c\_i = 9b^{10} + b^8$ is Alice's starting capital. (Which is also $1$ greater than Bob's capital after making the first $n$ moves.)

First of all, it is immediately clear that if Bob's opening defines a truth assignment that leaves a clause $C\_i$ unsatisfied, then Alice wins using her clause $C\_i$ strategy given above.

If Bob's opening satisies all clauses, we can argue constraints on Alice's options which rule out any other possibility of Alice winning. Note that the order in which Alice makes her moves is irrelevant, as Bob's responses are forced and the total capital Bob will require to respond to Alice's moves is unchanged by the order of Alice's moves.

* **Alice can't make more than 4 moves:** if Alice makes 5 or more moves, then her moves have a total cost of $\ge 5b^{10}$, which exceeds her budget.
* **Alice must make 4 moves:** if Alice selects 3 moves from the capital sink game then her total cost is $\ge 9b^{10} + 3b^8 - 3b^7 > 9b^{10} + 2b^8$ which is over budget. If she selects even one move of 3 from a variable game, then her total cost is $\le 8b^{10} + 2b^8 + b^7$ which is is substantially less than Bob's post-opening capital, so Bob can easily afford the counterplay.
* **Alice must select a move from the capital sink game:** if she doesn't, then she selects 4 moves from variable games, with total cost $\le 8b^{10} + 4b^7$, and again Bob can easily afford the counterplay. (Note that if there were a separate capital sink game per clause, we could even show that Alice must play in exactly one such game.)

From this stage we can disregard the $b^{10}$ and $b^8$ terms in the move costs chosen, as they will always sum to $9b^{10} + b^8$.
Since Alice must choose exactly one move in the capital sink game, assume that move is to $C\_iA$. Then Alice has (ignoring $b^{10}$ and $b^8$ terms) $\sum\_{k=1}^3 ib^{2k}$ capital remaining, and Bob has $1$ less than this amount remaining.

* **Alice must select at least one move costing $l\_{j3}$ for some clause $C\_j$:** if she doesn't, then her moves cost (again lower-order terms) $\le 3b^5$, and Bob has more than enough capital for counterplay.
* **Said move costing $l\_{j3}$ must be the move costing $l\_{i3}$:** it can't be a move costing $l\_{j3}$ for $j > i$, otherwise this move alone costs $\ge (i+1)b^6$ which is greater than Alice's remaining budget. If it's $l\_{j3}$ for $j < i$, then the $l\_{(i - j)3}$ cost move must also be chosen by Alice to exhaust the $b^6$-order term in Bob's remaining budget. But then Either the $b^2$-order term in Bob's remaining budget or the $b^2$-order term doesn't get exhausted, so Bob wins handily.

Similar arguments should establish that Alice must select the moves costing $l\_{i2}$ and $l\_{i1}$. If Bob's truth assignment satisfies $C\_i$, then even this strategy doesn't work, as the discount Bob gets on one of the $l\_{ik}$-based costs makes up for the $1$ less capital he has after his opening.

---

A remark on my previous answer: it's obvious in hindsight that, for the TABLE-GAME variant of MULTI-GAME I defined in the comments of that answer, a knapsack-style DP suffices to determine which player has a winning strategy. You can argue that Bob's best strategy is to always respond to a losing state in a given game table with the minimal investment possible (this can't cut off a subsequent move for Bob that he would have otherwise), and from there that the order of Alice's moves doesn't matter. It then becomes a matter of choosing a split of Alice's capital among the games such that the sum of Bob's minimal winning responses over those games exceeds his budget, which can be reframed as a knapsack-style problem, which has a polynomial-time DP due to the unary representation of costs. (My recurrence actually would've worked for TABLE-GAME if I framed it in terms of Alice.)

It turns out that even a simple tree structure for each game, with constant depth and really only one meaningful fork per game (namely those at the start which force Bob to choose a truth assignment) is sufficient to get NP-hardness. I had some ideas for getting rid of that initial fork, which stalled out at somehow forcing Bob to invest a relatively large fixed amount of capital in $n$ games without Alice having to precommit to those games in advance, but obviously since TABLE-GAME is in P this is not possible without the fork.

I haven't thought much about your special case from **UPD3**. I suspect it's also NP-hard, for the reason that my variable gadgets seem at a glance like they may be adaptable to those constraints, but I probably won't look into it further.

> **Comments:**
> **username_0**: ,Could you please write me on e-mail (almas239@gmail.com) or write your e-mail?  
> **username_5**: @AlexeyMilovanov Emailed.  

---

### Answer by username_5 on 2019-09-03. Score: 0

**Update:** likely incorrect, leaving up for now as a record of having explored an avenue. See comments.

**Update 2:** definitely incorrect.

Consider a graph of form (B) -1-> (A) -1-> (B), i.e. $G = (V, E)$, where $V = \{1, 2, 3\}$, $E = \{(1, 2), (2, 3)\}$, vertices 1, 2, 3 are labeled B, A, B respectively, and edges are all assigned costs of 1.

Define a 3-game instance of MULTI-GAME by setting $m\_A = m\_B = 2$, $G\_1 = G\_2 = G\_3 = G$, with all three games starting on vertex 1. Clearly Alice cannot win this game.

However, the recurrence below fails for $M[3,2,2]$: there is no split of Bob's funds $2-u, u$ between the first two games and the third game such that for all splits of Alice's funds $v, 2 - v$, both $M[2, 2 - u, 2 - v] = B$ and $W[3, u, v] = B$. If $u = 1$ or $u = 2$, then $M[2, 2 - u, 2] = A$; and if $u = 0$ then $W[3, u, 2] = A$.

I don't see an immediate way to salvage this approach. Reversing the order of quantification on $u$ and $v$ makes the recurrence fail on the instance in update 2 of the question post.

---

Given a MULTI-GAME instance $m\_A, m\_B, G\_1, \dots, G\_n,$

Precompute

$W[k, x, y] = \begin{cases}A & \text{if Alice wins GAME on $G\_k$ with initial funds $x$ for Alice and $y$ for Bob,} \\ B & \text{otherwise}\end{cases}$

for all games and all $x \le m\_A$, $y \le m\_B$.

Denote by $M[k, x, y]$ the winner of MULTI-GAME if the instance is restricted to the first $k$ graphs and funds $x \le m\_A$, $y \le m\_B$. ($M[k, x, y] = B$ if Bob wins, $A$ otherwise.) Then

$M[1, x, y] = W[1, x, y]$

and

$M[k+1, x, y] = B \quad\text{if and only if}\quad \exists v \forall u, W[k+1, u, v] = B \:\:\text{and}\:\: M[k, x-u, y-v] = B.$

Output "yes" if $M[n, m\_A, m\_B] = A$, "no" otherwise.

> **Comments:**
> **username_0**: Your algorithm is wrong. Consider the graph at the picture in my post. Consider the MULTI-GAME with two such graphs. Here W[1,0,2]=W[2,0,2] =B and W[1,1,3]=W[2,1,3]=B. However, for MULTI-GAME with m_A=1 and m_B=5 Alice wins  
> **username_5**: Oops. Try univerally quantifying $u$ in the recurrence? I'll check it over in the meantime.  
> **username_5**: @AlexeyMilovanov with changes to the quantifiers the recurrence should go through for the example. But you have put doubt in my mind about this approach. It seems like it might require Bob to lay out a single distribution of funds that beats all distributions Alice could conceive of. That said, I'm not sure that I've been persuaded off of the core idea here: that this problem isn't really about GAME. Is anything known about the related problem where each GAME instance is replaced by a simple table a la W above?  
> **username_0**: Table W does not define the winner. I do not know is it true for some another table...  
> **username_5**: @AlexeyMilovanov Table W by definition determines the winner of GAME instances isolated to any specific one of the input graphs. I'm not sure why you'd say otherwise. I have updated my answer with a counterexample though, in case there was any lingering doubt that it was incorrect.  
> **username_5**: Also to expand on my question: we'll call a table $W:[n]\times[m]\to\{A,B\}$ a game table if $W[i,j]=A\implies W[p, j] = A$ for all $p > i$ and $W[i,j]=B\implies W[i, q] = B$ for all $q > j$. Clearly $W[k, \cdot, \cdot]$ in the answer above has this property for any $k$, and given any game table $W$ you could make a GAME instance graph that produces $W$ by building a "grid graph" with unit edge costs. GAME instances do seem more general, though: you could e.g. join two different grid graphs such that the first move "chooses" which to play on. But is the analogous MULTI-TABLE-GAME problem hard?  
> **username_0**: I mean all tables W for GAMES do not define the winner in MULTI-GAME.  

---

### Answer by username_3 on 2020-02-05. Score: 0

Per my comments above, here's a reduction that I think shows the problem to be PSPACE-hard (and presumably complete). Let $[n]$ be the graph with $n+1$ nodes, numbered $n\ldots 0$, with a link from node $i+1$ to $i$ for all $0\leq i\lt n$, all nodes other than $0$ marked for A, node $0$ marked for B, and the chit initially pleased on $n$. (All edges here have cost 1). It should be clear that B wins $[n]$ iff they have $\geq n$ dollars. (If need be, we can give unit-cost edges from each node other than $0$ to itself, since A will always want to keep the chit as far from $0$ as possible and B will always want to move it closer; indeed, if self-links aren't allowed then we can 'double up' the line into two copies, forming a ladder with bidirectional links.

Now, consider the graph $G$ with two additional nodes $\alpha$ and $\beta$: node $\alpha$ links to some $[i]$ and to $\beta$, and node $\beta$ has links to $[j]$ and $[k]$ (Presume that $j\lt k$). All of these links have cost zero. (This isn't strictly necessary for the reduction, but it's convenient.) Both $\alpha$ and $\beta$ are marked for A. Clearly from $\beta$ B will want to go to $[j]$ whereas A will want to go to $[k]$ (A would prefer not to move at all, but it can be worth moving to $[k]$ to make the cost higher for B). Similarly, it can be arranged that B never wants to move to $[i]$ and that A always wants to. Then the game-theoretical value of these positions is $\{i\mid\{j\mid k\}\}$. But it's known that establishing the value of a sum of games (i.e. graphs) of this type is PSPACE-complete; this was shown in [Laura Jo Yedwah's Masters' thesis](http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-348.pdf). So your problem is at least PSPACE-hard.

> **Comments:**
> **username_6**: The proofs in the thesis seem to use large values of i, j and k in the games. Note that here all weights may be assumed to be at most the players' capitals, which were represented in unary.  
> **username_3**: @AnttiRöyskö I'll have to take a much closer look at the proof, then; I believe the result on PSPACE-completeness of Go endgames uses the thesis result and assumes unary counting as well (since there, i/j/k come from the sizes of board regions).  
> **username_0**: It is unclear: are there edges to $\alpha$ or $\beta$? If all (except $0$) nodes are marked by A then Alice will not move...  
> **username_3**: @AlexeyMilovanov Whoops, that's my fault — $\alpha$ should also link to $\beta$. Also, Alice may still want to move from such a position; imagine the case where we just have a single node, $\alpha$, with links to $[i] \gt [j]$, and Bob has $j+1$ dollars. Then Alice will move to $[i]$ to keep Bob from moving to $[j]$ and eventually winning.  
> **username_0**: @StevenStadnicki it is steal unclear: Is it  possible to achieve $\alpha$ or $\beta$ from initital node $n$? Also if not all chips are at B then Bob has to go, so at your game either Bob will achieve A in all graphs (and win) or Bob will not have enough many and will lose.  

---

