algorithm to determine minimum payments amongst a

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

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

Answer 2

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.