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.
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$:
- 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$.
- 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$.
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:
- Create a vertex labeled $C$, marked with B.
- 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$:
Graph for $x_2$:
Graph for $x_3$:
Graph for $x_4$:
Graph for capital sink:
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.
