I just watched The Dollar Game - Numberphile, in which a game involving graphs is presented. I recommend you watch the video for complete information.

The game involves a graph with integer values on its nodes, positive and negative. For instance, the following graph:

Each **node** corresponds to a person, the **node value** is the amount of
money that person has, the **edges** are the people that person can give or
take money from.
The objective of the game is to have everyone have a non-negative amount of money.
In each **move** of the game, one person decides to give or take money,
**however**, that person either takes 1 dollar from each of their connections,
or gives 1 dollar to each one.

On Numberphile, there are two questions: (i) does the problem has a solution? (ii) what’s the least amount of moves to find it? I’ve decided to implement this problem using optimization, since it looked almost straightfoward. The optimization model was indeed very simple, and it took more time drawing graphs than modelling. Still fun though.

## The model

Given the undirected graph $G = (V, E)$, and values $w_i, i \in V$, our model is based on the following observations:

- The order of moves is irrelevant;
- Whether the move is a
*give*or a*take*, is just a question of**sign**; - The value of a node after the moves can be computed by accounting for the moves done by the done and by its neighbours.

Hence, we can model it using two non-negative integer variables $g_i$ and $t_i$ storing the number of gives and takes of node $i$. Notice that we could use $y_i = g_i - t_i$, but this is more descriptive.

- Objective: minimize the number of moves

$$\min \sum_i (g_i + t_i)$$

- Constraint: after the moves, the values of the nodes should be non-negative

$$ w_i + \sum_i (t_i - g_i) |N_i| + \sum_{j \in N_i} (g_j - t_j) \geq 0, \qquad \forall i \in V. $$

As it turns out, it’s a very simple model. The implementation is also very simple. We’re using Julia Language with the JuMP modelling language, and the LightGraphs package from JuliaGraphs. Here’s the code:

```
function dollar_game(g, W)
nv = length(vertices(g))
model = Model(solver = CbcSolver())
@variable(model, give[1:nv] >= 0, Int)
@variable(model, take[1:nv] >= 0, Int)
@objective(model, Min, sum(give[i] + take[i] for i = 1:nv))
@expression(model, x[i=1:nv], W[i] +
(take[i] - give[i]) * length(neighbors(g, i)) +
sum(give[j] - take[j] for j = neighbors(g, i)))
@constraint(model, x .>= 0)
status = solve(model)
println("status = $status")
if status != :Optimal
return zeros(nv), W
end
give = Int.(getvalue(give))
take = Int.(getvalue(take))
sol = Int.(getvalue(x))
println("give = $give")
println("take = $take")
println("sol = $sol")
return give - take, sol
end
```

The code should be pretty self-explanatory, but ping me on twitter if you need clarification.

Using the results and the packages Plots and GR, we
obtain a solution for the problem above. The moves are illustrated below, where
blue means giving, and red means taking.*mad plotting skillz*

The full code is available at GitHub.