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

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.

Intuitively, this sounds like an NP-complete problem (it reduces to a problem very like bin packing), however the following algorithm (a modified form of bin packing) should be pretty good (no time for a proof, sorry).

1. Net out everyone's positions, i.e. from your example above:

   Alice = $4 Bill = $-4 Charles = $0

2. Sort all net creditors from highest to lowest, and all debtors from lowest to highest, then match by iterating over the lists.

3. At some point you might need to split a person's debts to net everything out - here it is probably best to split into the biggest chunks possible (i.e. into the bins with the most remaining space first).

This will take something like O(n log n) (again, proper proof needed).

See the Partition Problem and Bin Packing for more information (the former is a very similar problem, and if you limit yourself to fixed precision transactions, then it is equivalent - proof needed of course).

Well, the first step is to totally ignore the transactions. Just add them up. All you actually need to know is the net amount of debt a person owes/owns.

You could very easily find transactions by then creating a crazy flow graph and finding max flow. Then a min cut...

Some partial elaboration: There is a source node, a sink node, and a node for each person. There will be an edge between every pair of nodes except no edge between source node and sink node. Edges between people have infinite capacity in both directions. Edges coming from source node to person have capacity equal to the net debt of the person (0 if they have no net debt). Edges going from person node to sink node have capacity equal to the net amount of money that person is owed (0 if they have no net owed).

Apply max flow and/or min cut will give you a set of transfers. The actual flow amount will be how much money will be transfered.

Only if someone owes more than 2 people, whom also owe to the same set, can you reduce the number of transactions from the simple set.

That is, the simple set is just find each balance and repay it. That's no more than N! transactions.

If A owes B and C, and some subset of B C owe each other, so B owes C, then instead of: A -> B, A -> C (3 transactions). You'd use: A -> B, B -> C (2 transactions).

So in other words you are building a directed graph and you want to trim vertices on order to maximize path length and minimize total edges.

Sorry, I don't have an algorithm for you.

You should be able to solve this in O(n) by first determining how much each person owes and is owed. Transfer the debts of anyone who owes less than he is owed to his debtors (thus turning that person into an end point). Repeat until you can't transfer any more debts.

The most optimal solution will require looking ahead to find equal pairs of debtors/creditors to minimize the total number of transactions.

The non-optimized solution is not too hard:

1. Sum up each person's total credit and debits
2. Match any two people (it actually does not need to be a debtor and a creditor)
3. One of these people will owe/be due $A, one will be owe/be due $B
4. Transfer the lower of |$A| and |$B| so that one person goes to $0
5. Go back to Step 2 and repeat until all $0

So note you always get one person to zero. With N people, on round (N-1), you will have +$X and -$X (a perfect match) and you set two people to zero. So this is always done in, at most, (N-1) rounds.

To optimize as an 'easy' step, you can always pair up people as soon as you see them That is, someone with +$X and someone with -$X. This alteration should cover >99% of all cases. So you get (N-1) rounds but sometimes (N-2), (N-3), etc if you happen upon a pair of +$X and -$X - you match them up for that round.

However, I have found that a truly optimal solution require (I believe) polynomial-time complexity as you need to run scenarios to try to force pairs.

Example in picture form

Simple solution - pick, say, highest creditor (+$) and lowest debtor (-$). Max of 5 rounds since Round 5 always has a match.

    Round 1 Round 2 Round 3 Round 4 Round 5
a   $100    
b   $ 90    $90 
c   $ 35    $35     $ 35    $ 10
d   $ 10    $10     $ 10    $ 10    $ 10    
e  -$110   -$110   -$ 20   -$ 20   -$ 10
f  -$125   -$25    -$ 25    
From    f       e        f       e     e    
To      a       b        c       c     d    
Amount  $100    $90     $25     $10   $10

Here is us forcing a match by altering Round 1 - we need an automated way of doing this

    Round 1 Round 2 Round 3 Round 4
a   $100    
b   $ 90    $ 90    $ 90
c   $ 35    $ 35    $ 35    $ 35
d   $ 10    $ 10        
e  -$110   -$ 10   
f  -$125   -$125   -$125   -$ 35    
From    e       e        f      f       
To      a       d        b      c       
Amount  $100   $10      $90    $35    

Another example, showing how in some cases forgoing a "settle up at least one person" round may be an advantage. It doesn't beat the example above, but one could see with enough people, setting up chain reaction of pairs may result in that being optimal.

    Round 1 Round 2 Round 3 Round 4
a   $ 40    $ 55
b   $ 20    $  5    $  5
c   $  4    $  4    $  4    $ 4
d  -$  4   -$  4   -$  4   -$ 4 
e  -$  5   -$  5   -$  5
f  -$ 55   -$ 55     
From    a       f        e      d       
To      b       a        b      c       
Amount $15    $55       $5     $4     

If you take states as nodes of graph then you will be able to use shortest path algorithm to know the answer.