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 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

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<j$ 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<j<k$ the edge $j$ to $k$ is not greater than from $i$ to $k$.

  • 4
    $\begingroup$ 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: en.wikipedia.org/wiki/…) $\endgroup$ – Neal Young Aug 21 '19 at 23:54
  • $\begingroup$ @Neal Young The player chooses one graph to make one move in. $\endgroup$ – Alexey Milovanov Aug 25 '19 at 4:25
  • $\begingroup$ 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. $\endgroup$ – Neal Young Aug 25 '19 at 22:03
  • 1
    $\begingroup$ @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... $\endgroup$ – Alexey Milovanov Aug 30 '19 at 6:29
  • $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Aug 30 '19 at 12:27

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,$


$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]$


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

  • $\begingroup$ 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 $\endgroup$ – Alexey Milovanov Sep 3 '19 at 17:16
  • $\begingroup$ Oops. Try univerally quantifying $u$ in the recurrence? I'll check it over in the meantime. $\endgroup$ – gdmclellan Sep 3 '19 at 17:19
  • $\begingroup$ @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? $\endgroup$ – gdmclellan Sep 3 '19 at 18:11
  • $\begingroup$ Table W does not define the winner. I do not know is it true for some another table... $\endgroup$ – Alexey Milovanov Sep 3 '19 at 18:41
  • $\begingroup$ @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. $\endgroup$ – gdmclellan Sep 4 '19 at 5:14

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. So your problem is at least PSPACE-hard.

  • 1
    $\begingroup$ 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. $\endgroup$ – Antti Röyskö Feb 6 at 3:18
  • $\begingroup$ @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). $\endgroup$ – Steven Stadnicki Feb 6 at 19:28
  • $\begingroup$ It is unclear: are there edges to $\alpha$ or $\beta$? If all (except $0$) nodes are marked by A then Alice will not move... $\endgroup$ – Alexey Milovanov Feb 6 at 23:16
  • $\begingroup$ @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. $\endgroup$ – Steven Stadnicki Feb 7 at 1:09
  • $\begingroup$ @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. $\endgroup$ – Alexey Milovanov Feb 8 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.