10
$\begingroup$

Me and a number of friends occasionally met up and play some game (often pool or some card game) and play for small stakes to give the game a little extra spice. After each round we jot down the results of the round to keep tally of who owes who how much.

Round | A owes B | A owes C | A owes D | B owes C | B owes D | C owes D -----------------------------------------------------------------------     1 |        4 |        2 |        3 |          |          |     2 |          |       -3 |          |       -6 |          |        2     3 |       -2 |          |          |        1 |        2 |     4 |          |          |       -5 |          |       -4 |       -6 ----------------------------------------------------------------------- Total |        2 |       -1 |       -2 |       -5 |       -2 |       -4 

At the end of the session we have a list of IOUs between each of the friends that can by common sense be simplified. In the above example A owes B 2 coins, but D owes A 2 coins, which can be simplified by transferring A's debt to B to D.

      | A owes B | A owes C | A owes D | B owes C | B owes D | C owes D ----------------------------------------------------------------------- Total |        0 |       -1 |        0 |       -5 |       -4 |       -4 

My question, should this be deemed appropriate for this site, is how a formula to perform this simplification would look like? Specifically a function to determine the amount X owes Y. The idea is to automate the above using an excel sheet or similar (and spend the conclusion of the evening in small talk instead of fiddling with pen and paper).

My current thoughts are around minimizing the amount of transactions. By adding a persons winnings you could easily come up with the following table that gives the total gain/loss of every person

A | B |  C |  D ---------------- 1 | 9 | -2 | -8 

From the above table one can easily see that only 10 coins should transfer hands, whereas the "simplified" example above involve transactions of 14 coins. One can also notice that there are more than one solution (either of C or D could owe A a single coin).

  • 0
    The remaining task of dividing the debts into transactions is pretty interesting mathematically. Finding the *minimum* number of transactions turns out to be NP-hard, though doing it with exactly $n-1$ transactions is easy. See the answers to [my previous question](http://math.stackexchange.com/q/4312/856).2012-11-20

1 Answers 1

2

A solution with $\leq n-1$ transactions:

Order the list by net surpluses (all that matters really is that the ones on top have a positive surplus and the bottom ones a negative), then have the bottom pay the top until either the bottom runs out of money or the top receives all it is owed.

Remove the bottom from the list if it has paid all it owes or remove the top if it has received all it is owed (remove both if both are true).

Repeat the procedure with the new list until there is no one left in the list.


In your example:

$\begin{matrix}B & A & C & D \\ 9 & 1 & -2 & -8 \end{matrix}$

$1.$ The bottom ($D$) pays all it owes to the top ($B$):

$\begin{matrix}B & A & C & D \\ {\color{red}1} & 1 & -2 & {\color{red}0} \end{matrix}$

$2.$ New bottom ($C$) pays $1$ to the top ($B$):

$\begin{matrix}B & A & C \\ {\color{red}0} & 1 & {\color{red}{-1}} \end{matrix}$

$3.$ Bottom ($C$) pays $1$ to the new top ($A$):

$\begin{matrix} A & C \\ {\color{red}0} & {\color{red}0} \end{matrix}$


Proof that the solution involves at most $n-1$ transactions:

At every iteration at least one agent is removed from the list, so the maximum number of iterations is $n-1$.* If two agents are removed in $k$ of the iterations, the number of transactions will be $n-1-k$.

[*] This involves assuming that the act of one agent paying one or two agents some amount counts as one transaction. If you prefer counting that as two transactions, then a solution that gives exactly $n-1$ would be to do exactly as above except that the agent who owes something transfers all it owes to its pair in the iteration (if this is more than that agent was owed than that agent now owes the difference when the next iteration starts).

  • 0
    Yes, sorry, I didn't mean that as a criticism. For some reason I was trying to head off a potential response that this specific choice of ordering may reduce the number of transactions. It doesn't make much sense in retrospect and I'll delete my comment.2018-04-23