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

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 2

So, I implemented this for a spreadsheet to keep track of my roommates' debt to each other. I know this is really old, but I referenced it in my solution, and it's high on Google when searching for the subject, so I wanted to post and see if anyone has any input.

My solution uses the "central bank" or "netting center" concept people mentioned here. Before running this algorithm I calculate the net profit each person is owed, which is the sum of all their credits, minus the sum of all their debts. The complexity of calculating this is dependent on the number of transactions, not the number of individuals involved.

Fundamentally the point of the algorithm is to have every individual be paid or pay out the correct amount regardless of what individual they are transferring money to. I would ideally like to do this in the fewest number of payments, however it's difficult to prove this to be the case. Note all debits and credits will sum to zero.

I was very, very verbose for part of this code. In part to communicate what I was doing, and in part to solidify the logic I am using as I go forward. Apologies if it's unreadable.

Input: {(Person, Net Profit)} //Net Profit < 0 is debt, Net Profit > 0 is credit.
Output: {(Payer, Payee, Amount paid)}

find_payments(input_list):
    if input_list.length() > 2: 
        //More than two people to resolve payments between, the non-trivial case

        max_change = input_list[0]
        not_max_change = []

        //Find person who has the highest change to their account, and
        //the list of all others involved who are not that person

        for tuple in input_list:
            if abs(tuple[Net Profit]) > abs(max_change[Net Profit])
                not_max_change.push(max_change)
                max_change = tuple
            else:
                not_max_change.push(tuple)

        //If the highest change person is owed money, they are paid by the 
        //person who owes the most money, and the money they are paid is deducted 
        //from the money they are still owed. 

        //If the highest change person owes money, they pay the person who 
        //is owed the most money, and the money they pay is deducted 
        //from the money they are still owe. 


        not_yet_resolved = []

        if max_change[Net Profit] > 0: 
            //The person with the highest change is OWED money 

            max_owing = not_max_change[0]

            //Find the remaining person who OWES the most money
            //Find the remaining person who has the LOWEST Net Profit
            for tuple in not_max_change:
                if tuple[Net Paid] < max_owing[Net Paid]:
                    not_yet_resolved.push(max_owing)
                    max_owing = tuple
                else:
                    not_yet_resolved.push(tuple)

            //The person who has the max change which is positive is paid
            //by the person who owes the most, reducing the amount of money
            //they are owed. Note max_owing[Net Profit] < 0.

            max_change = [max_change[Person], max_change[Net Profit]+max_owing[Net Profit]]

            //Max_owing[Person] has paid max_owing[Net Profit] to max_change[Person]
            //max_owing = [max_owing[Person], max_owing[Net Profit]-max_owing[Net Profit]]
            //max_owing = [max_owing[Person], 0]
            //This person is fully paid up.

            if max_change[Net Profit] != 0:
                not_yet_resolved.push(max_owing)

            //We have eliminated at least 1 involved individual (max_owing[Person])
            //because they have paid all they owe. This truth shows us 
            //the recursion will eventually end.
            return [[max_owing[Person], max_change[Person], max_owing[Net Profit]]].concat(find_payments(not_yet_resolved))

        if max_change[Net Profit] < 0:
            //The person with the highest change OWES money 
            //I'll be way less verbose here

            max_owed = not_max_change[0]

            //Find who is owed the most money
            for tuple in not_max_change:
                if tuple[Net Paid] > max_owed[Net Paid]:
                    not_yet_resolved.push(max_owed)
                    max_owed = tuple
                else:
                    not_yet_resolved.push(tuple)

            //max_change pays the person who is owed the most. 
            max_change = [max_change[Person], max_change[Net Profit]+max_owed[Net Profit]]                

            if max_change[Net Profit] != 0:
                not_yet_resolved.push(max_owing)

            //Note position of max_change[Person] moved from payee to payer
            return [[max_change[Person], max_owed[Person], max_owed[Net Profit]]].concat(find_payments(not_yet_resolved))

    //Recursive base case
    //Two people owe each other some money, the person who owes pays
    //the person who is owed. Trivial. 
    if input_list.length() == 2:
        if input_list[0][Net Profit] > input_list[1][Net Profit]:
            return [[input_list[1][Person], input_list[0][Person], input_list[0][Net Profit]]];
        else
            return [[input_list[0][Person], input_list[1][Person], input_list[1][Net Profit]]];

Note:

max_change = (payee, $A); max_owing = (payer, $B) 
|$A|>=|$B| by nature of 'max_change' 
$A > 0 => $A >= |$B| //max_change is owed money
$B < 0 by nature of 'max_owing'
$A >= -$B => $A + $B >= 0 => Payee does not go into debt

and:

max_change = (payee, $A); max_owed = (payer, $B) 
|$A|>=|$B| by nature of 'max_change' 
$A < 0 => -$A >= |$B| //max_change owes money
$B > 0 by nature of 'max_owed'
-$A >= $B => 0 >= $A + $B => Payee does not go into credit

also:

Sum of Payments = 0 = $A + $B + Remainder = ($A + $B) + 0 + Remainder

The sum always being 0 after someone's debt is completely settled is the basis of the recursion logic. Someone is paid/has paid, the problem gets smaller.

If this algorithm is running for n people with non-zero debts (discard people who broke even before running the algorithm) this algorithm will give at most n-1 payments to settle the debt. It's unclear if it is always an ideal payment scheme (I've yet to find a counter example). I may try to prove if the number of transactions < n-1 then a debt and a credit must be exactly equal, which this algorithm accounts for I believe.

I'm extremely interested in any errors anyone sees in this. I haven't done development in a while, never mind algorithmics, and people will be paying each other based off this. I had fun and this is an interesting, meaty question, I hope some of you are still around.

Answer 3

As one @Edd Barret stated, this can be solved approximately using linear programming. I have written a blog post describing this approach, along with a tiny R package that implements it.

Answer 4

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

In the world of the corporate treasury, this is known as payment or settlement netting.

Multinational corporates usually have many flows between their subsidiaries every month, often in different currencies. They can save considerable amounts by optimising the settlement of these flows. Typically a corporate will perform such an optimisation (a netting cycle) once a month. When there are multiple currencies, there are three sources of savings:

• bank transaction fees (fewer payments means lower fees)
• lower interest rate float and settlement risk arising from streamlined processing by the bank (the money spends less time tied up in the banking system)
• FX matching (much less foreign currency is exchanged because most of it is 'netted out')

There are two ways to actually calculate the optimised settlement.

Bilateral netting is the solution well described by @AndrewShepherd on this page. However, in a cross-border implementation, this approach can have legal and administrative problems implications since different borders are being crossed each month.

Multilateral netting solves the network by adding a new subsidiary called the netting centre and re-routes all amounts through it. Compare the before and after diagrams below:

Before netting

After netting

Although this adds one more flow than is necessary (compared to bi-lateral netting), the advantages are:

• the calculation is simpler and the result is easier to visualise (also, there is only one solution, as opposed to the bilateral approach)
• the netting centre becomes an invaluable resource regarding flows and FX exposure within the whole group
• if the netting centre is, say, in Germany, then all legal issues with cross-border payments are dealt once and for all within the netting centre's country (central bank reporting, etc.)
• all foreign exchange required for the optimised settlement can be bought or sold from the netting centre

(At it's basic level, the calculation is simple, but there can be many legal and administrative complications so corporates frequently develop or purchase a netting system from a software vendor or service provider.)

Answer 6

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.