Search code examples
algorithmgraphlanguage-agnosticexpense-splitting

What algorithm to use to determine minimum number of actions required to get the system to "Zero" state?

This is kind of more generic question, isn't language-specific. More about idea and algorithm to use.

The system is as follows:

It registers small loans between groups of friends. Alice and Bill are going to lunch, Bill's card isn't working, so Alice pays for his meal, $10.
The next day Bill and Charles meet each other on a railway station, Charles has no money for ticket, so Bill buys him one, for $5. Later that day Alice borrows $5 from Charles and $1 from Bill to buy her friend a gift.

Now, assuming they all registered that transactions in the system, it looks like this:

Alice -> Bill $10
Bill -> Alice $1
Bill -> Charles $5
Charles -> Alice $5

So, now, only thing that needs to be done is Bill giving Alice $4 (he gave her $1 and Charles transferred his $5 to Alice already) and they're at the initial state.

If we scale that to many different people, having multiple transaction, what would be the best algorithm to get as little transactions as possible?

Solution

  • This actually looks like a job that the double entry accounting concept could help with.

    Your transactions could be structured as bookkeeping entries thus:

                              Alice  Bill  Charles  Balance
Alice   -> Bill    $10      10    10-       0        0
Bill    -> Alice    $1       9     9-       0        0
Bill    -> Charles  $5       9     4-       5-       0
Charles -> Alice    $5       4     4-       0        0

    And there you have it. At each transaction, you credit one ledger account and debit another so that the balance is always zero. At at the end, you simply work out the minimal number transactions to be applied to each account to return it to zero.

    For this simple case, it's a simple $4 transfer from Bill to Alice. What you need to do is to reduce at least one account (but preferably two) to zero for every transaction added. Let's say you had the more complicated:

                              Alice  Bill  Charles  Balance
Alice   -> Bill    $10      10    10-       0        0
Bill    -> Alice    $1       9     9-       0        0
Bill    -> Charles  $5       9     4-       5-       0
Charles -> Alice    $5       4     4-       0        0
Charles -> Bill     $1       4     5-       1        0

    Then the transactions needed would be:

    Bill     -> Alice   $4       0     1-       1        0
Bill     -> Charles $1       0     0        0        0

    Unfortunately, there are some states where this simple greedy strategy does not generate the best solution (kudos to j_random_hacker for pointing this out). One example is:

                     Alan  Bill  Chas  Doug  Edie  Fred  Bal
Bill->Alan   $5    5-    5     0     0     0     0    0
Bill->Chas  $20    5-   25    20-    0     0     0    0
Doug->Edie   $2    5-   25    20-    2     2-    0    0
Doug->Fred   $1    5-   25    20-    3     2-    1-   0

    Clearly, this could be reversed in four moves (since four moves is all it took to get there) but, if you choose your first move unwisely (Edie->Bill $2), five is the minimum you'll get away with.

    You can solve this particular problem with the following rules:

    • (1) if you can wipe out two balances, do it.
    • (2) otherwise if you can wipe out one balance and set yourself up to wipe out two in the next move, do it.
    • (3) otherwise, wipe out any one balance.

    That would result in the following sequence:

    • (a) [1] not applicable, [2] can be achieved with Alan->Bill $5.
    • (b) [1] can be done with Chas->Bill $20.
    • (c) and (d), similar reasoning with Doug, Edie and Fred, for four total moves.

    However, that works simply because of the small number of possibilities. As the number of people rises and the group inter-relations becomes more complex, you'll most likely need an exhaustive search to find the minimum number of moves required (basically the rules 1, 2 and 3 above but expanded to handle more depth).

    I think that is what will be required to give you the smallest number of transactions in all circumstances. However, it may be that that's not required for the best answer (best, in this case, meaning maximum "bang per buck"). It may be that even the basic 1/2/3 rule set will give you a good-enough answer for your purposes.