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

$\endgroup$
  • $\begingroup$ The solution that minimize $\sum|a_i|$ is exactly the strategy that you described: sum each player earnings (or loss) and then the winners collect money from the loosers. $\endgroup$ – carlop May 6 '12 at 10:40
  • $\begingroup$ I kind of guessed as much (it is beneficial to try to formulate your question cleanly, it often leads you in the right direction). The remaining task of dividing losses into who ows who is more difficult in excel, than in real life... $\endgroup$ – erikxiv May 6 '12 at 10:45
  • $\begingroup$ 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. $\endgroup$ – Rahul Nov 20 '12 at 6:42
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You don't even need to order the list. Just pick an arbitrary pair of one positive and one negative and have them settle up as much as possible. This doesn't change the total number of coins transferred in the end. $\endgroup$ – Rahul Apr 23 '18 at 4:37
  • $\begingroup$ I did not claim this procedure gave the "minimum number of transaction". Since you commented above that this would be NP-hard and that a solution with $n-1$ could easily achieved, I thought relevant to lay out what an example of such a solution would look like. $\endgroup$ – mzp Apr 23 '18 at 12:37
  • $\begingroup$ I added some more content to address your other point, though I agree one agent transferring some amount to two agents could also be defined as two transactions. $\endgroup$ – mzp Apr 23 '18 at 12:46
  • 1
    $\begingroup$ If the strategy is simply to pick one player with a positive score and one with a negative score and have the negative-score player pay the positive-score one until one of them reaches zero score, then you will always zero-out at least one player at each step, and two players on the last step, hence $n - 1$ transactions. So the only part about the order that really is critical is that you distinguish those who owe from those who are owed. $\endgroup$ – David K Apr 23 '18 at 13:13
  • $\begingroup$ OK, I edited to make this explicit. $\endgroup$ – mzp Apr 23 '18 at 13:38

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.