Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ows who how much.

Round | A ows B | A ows C | A ows D | B ows C | B ows D | C ows 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 ows B 2 coins, but D ows A 2 coins, which can be simplified by transferring As debt to B to D.

      | A ows B | A ows C | A ows D | B ows C | B ows D | C ows 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 ows 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).

share|improve this question
    
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. –  carlop May 6 '12 at 10:40
    
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... –  erikxiv May 6 '12 at 10:45
    
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. –  Rahul Nov 20 '12 at 6:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.