When can you win this directed graph game?

Question

I am trying to consider the conditions under which you can win the following directed graph game:

Directed graph game: At the start of the game, you are given a directed, acyclic graph $G$ with integer values marked on each node. During each round, you pick any edge $a\rightarrow b$ in the graph; the value at node $a$ is decreased by one, and the value of node $b$ is increased by one.

You win if at any point the labels of the nodes are all non-negative.

I am wondering what are the conditions on the initial values of the nodes under which this game is possible to win.As a special case, I am currently considering only DAGs which are trees. For example, if you have a three-node tree with $a\rightarrow b$ and $a\rightarrow c$, you can win the game just if every subset of nodes containing $a$ has a non-negative sum. But I am having trouble generalizing from this case.

Answer 1

For the special case, which I assume (at least for now) is the case of a rooted directed tree with edges directed away from the root, we can solve it for each subtree and then solve it for the whole tree. We define a function on the subtrees recursively. Let $$r(subtree)=n_{root}-\sum d(branch_i),$$ and then let $$d(subtree)=\left\{\begin{array}[cl] \mbox{}0 & r(subtree) \ge 0 \\ -r(subtree) & \text{otherwise.}\end{array}\right.$$

$d(subtree)$ measures how much needs to be added to the subtree to win. $r(subtree)$ measures how much will remain at the root after you make all the other subtrees win, and $d(subtree)$ checks to see whether what remains will be positive, then you don't need to add anymore, so $d(subtree)$ is zero, or whether we will have gone negative, so we need to add more to make the root nonnegative. Note that leaves have no branches, so $r(leaf)=n_{leaf} - 0 =n_{leaf}$.

I'm not sure about more general cases right now, and I don't know if you've already come up with this, but here are my first thoughts about the problem.

Edit:

Note that we can modify this to work for any directed graph with underlying undirected graph being acyclic. We can repeatedly prune leaves. If a leaf has its edge entering it, then we add enough to make it nonnegative, and delete the leaf. If a leaf has its edge leaving it, if the leaf is negative, it is impossible to win. If the leaf is nonnegative, make the value at the leaf zero and delete the leaf and recurse.

Note that these are algorithmic strategies to check whether the game is winnable, I'm not sure if they can be reduced to some set of simple equations.

Answer 2

Let $V$ be the set of nodes of your digraph. (I assume $V$ is finite.) Here is a necessary and sufficient condition for your game to be winnable:

For every set $S\subseteq V,$ if there are no edges from $V\setminus S$ to $S,$ then the sum of all the node values in $S$ is nonnegative.

The condition is obviously necessary. Sufficiency is an easy consequence of Hall's marriage theorem aka the bipartite matching theorem. I'm too lazy to write down a proof, but I'll give a hint.

Hint. For simplicity, suppose all node values are $\pm1$ or $0.$ Then winning the game is simply a matter of matching each negative-valued node $a$ with a positive-valued node which will "donate" its positive values to $a,$ either directly or via a chain of intermediate nodes. The general case, with general integer node values, is essentially the same, but may need a little more notation to write down.

P.S. Here's how to reduce your game to a bipartite matching problem.

Let $f(x)$ denote the value of a node $x\in V.$ Take pairwise disjoint sets $S_x\ (x\in V)$ with $|S_x|=|f(x)|.$ We constuct a bipartite graph with vertex set $W=A\cup B$ where $A=\bigcup\{S_x:f(x)\gt0\}$ and $B=\bigcup\{S_x:f(x)\lt0\}.$ For $a\in S_x\subseteq A$ and $b\in S_y\subseteq B,$ draw an edge $ab$ just in case there is, in the original digraph, a directed path from $x$ to $y.$ Note that an edge $ab$ represents the possibility of transferring one unit of value from $x$ to $y.$

Your game is winnable if and only if there is a matching of $B$ into $A.$ There is a well-known criterion for the existence of such a matching, and there are well-known good algorithms for constructing such a matching or determining that it does not exist.

P.P.S. Maybe it would be better to look at this as a network flow problem, but I'm not going to redo it.