algorithm to determine minimum payments amongst a group

Question

The Problem

I was recently asked to calculate the money owed amongst a group of people who went on a trip together and came upon an interesting problem: given that you know the amounts that each person owes another, what is a general algorithm to consolidate the debts between people so that only the minimum number of payments needs to be made? Take this as an example:

• Mike owes John 100
• John owes Rachel 200
• Mike owes Rachel 400

We can remove a payment between Mike and John by reformulating the debts like this:

• Mike owes John 0
• John owes Rachel 100
• Mike owes Rachel 500

I did the math by hand since it was easy enough, but then the programmer in me was itching to figure out a general algorithm to do it for an arbitrarily large group. This seems like a graph algorithm to me, so I'll reformulate this as a graph:

Viewed as a Graph

• The vertices are the people in the group
• The edges are directed and weighted by the amount owed. For example, an edge from Mike to Rachel with weight 500 means that Mike owes Rachel 500.
• Constraint: the net sum of weights for each node must remain unchanged.
• The goal is to find a graph with the minimum number of edges that still satisfy the constraint.

Answer 1

My opinion: You're making this overly complicated.

Think of it as a "pool" of money, and lose the relationships altogether:

Instead of:

• Mike owes John 100
• John owes Rachel 200
• Mike owes Rachel 400

The algorithm only has to think:

• Mike owes 100
• John is owed 100
• John owes 200
• Rachel is owed 200
• Mike owes 400
• Rachel is owed 400

Netting this:

• Mike owes 500
• John owes 100
• Rachel is owed 600

Separate this into a list of "givers" and "receivers". Each giver on the list will go through the list of receivers, giving each receiver what they need until the giver has payed up. When a receiver receives everything they need, they go off the list.

Later Edit

As other posters have observed, this simplifies the problem. However, there might be an optimal ordering of the "givers" and "receivers" lists, but we haven't yet identified a straightforward way to determine this ordering.

Answer 2

It does not suffice to just figure out the receivers and givers. While I think this strategy is on the right track it also does not ensure an algorithm to find the least possible amount of payments.

For Example,

• Person A owes 25
• Person B owes 50
• Person C owes 75
• Person D is owed 100
• Person E is owed 50

While it is obvious that this can be done in 3 pays (A and C to D, B to E). I can't think of an efficient algorithm that will satisfy this for all problem sets.

Better Example,

• Person A owes 10
• Person B owes 49
• Person C owes 50
• Person D owes 65
• Person E is owed 75
• Person F is owed 99

If we took the greedy approach of having person D pay to F we would wind up with a sub-optimal solution as opposed to the optimal(A&D to E, B&C to F).

This problem has a lot of similarity with the Bin Packing Problem which has been proven to be NP-hard. The only difference being that we have multiple bins of varying sizes and the condition that the total space in all bins is equal to the total size of all items. This leads me to believe that the problem is likely NP-hard but with the added constraints it may be possible to solve in polynomially time.

Answer 3

While I concur with Andrew that turning this into a graph problem is probably overcomplicated, I'm not sure his approach yields the minimal number of transactions. It's how you'd solve the problem in real life to save yourself a headache; just pool the money.

A few steps that seem 'right':

• Remove all individuals with zero debt; they don't need to send or receive money from anyone.
• Pair all givers and receivers with identical amounts owed/owing. Since the minimal connectivity per node of non-zero debt is 1, their transactions are already minimal if they just pay each other. Remove them from the graph.
• Starting with the individual with the largest amount to pay back, create a list of all receivers with owed less than that amount. Try all combinations of payment until one is found that satisfies most receivers with one transaction. 'Save' the surplus debt remaining.
• Move on to the next largest giver, etc.
• Allocate all the surplus debt to the remaining receivers.

As always, I'm afraid I'm pretty sure about the first two steps, less sure about the others. In any case, it does sound like a textbook problem; I'm sure there's a 'right' answer out there.

Answer 4

Hi,

if A, B and C each owe $1 to each of D, E and F, the "list" or "central bank" solution creates five transactions (e.g. A,B,C -$3-> D, D -$3-> E,F) whereas the naive solution results in nine transactions. However, if A owes only to D, B only to E and C only to F the central bank solution creates still five transactions (A,B,C -$1-> D, D -$1-> E,F) whereas the best solution needs only three (A -$1-> D, B -$1-> E, C -$1-> F). This shows that the "list" or "central bank" solution is not optimal in general.

The following greedy algorithm can be used to create better solutions to the problem, but they are not always optimal. Let "debt[i,j]" denote the amount of money person i owes to person j; initially this array is initialized according to the situation.

repeat until last:
  find any (i, j) such that |K = {k : debt[i,k] > 0 and debt[j,k] > 0}| >= 2
  if such (i, j) found:
     // transfer the loans from i to j
     total = 0
     for all k in K:
       debt[j,k] += debt[i,k]
       total += debt[i,k]
       debt[i,k] = 0 
     person i pays 'total' to person j
  else:
     last

for every i, j in N:
  if (debt[i,j] > 0)
    person i pays debt[i,j] to person j

They key of this algorithm is the observation that if both A and B owe money to both C and D, instead of the four transactions required for direct payments, B can pay the net debt to A who can take care of paying back both A's and B's loans.

To see how this algorithm works, consider the case where A, B and C each own $1 to each of D, E, F:

1. A transfers A's debts to B, and pays $3 to B (one transaction)
2. B transfers B's debts to C, and pays $6 to C (one transaction)
3. Only C has debts any more; C pays $3 to D, E and F each (three transactions)

But in the case where A owes D, B owes E and C owes F, the algorithm falls through immediately to the payment loop, resulting in the optimal number of transactions (only three) instead of five transactions which would result from the "central bank" approach.

An example of non-optimality is where A owes to D and E, B owes to E and F and C owes to F and D (assume $1 for every debt). The algorithm fails to consolidate the loans because no two payers share two common payees. This could be fixed by changing ">= 2" on the second line to ">= 1", but then the algorithm would most likely become very sensitive to the order in which the debts are collateralized.

Answer 5

Take a look at this blog article, "Optimal Account Balancing", goes over your problem exactly.

Answer 6

This exact problem was presented and optimally solved by Rod Carvalho about a month ago in his blog:

Optimal Account Balancing

Little to add to what he wrote...