13
$\begingroup$

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

$\endgroup$
  • 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
2
$\begingroup$

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

  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

Graph for $x_2$:

enter image description here

Graph for $x_3$:

enter image description here

Graph for $x_4$:

enter image description here

Graph for capital sink:

enter image description here

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 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.