The efficient settlement of many-way debts

How to reduce the number and size of transactions to settle debts between members of a group.
Read full article here : PDF 87Kb

Problem

If Amanda owes you ten pounds and you owe Bert five pounds then the direct settlement method means you have to write a cheque for five pounds even though in total you're owed money.

Solution

Amanda pays you five pounds and Bert five. You don't write any cheque at all.

This can be applied to any group of traders.

Algorithm

  1. Each member of a group calculates the total owed or owing to the others.
  2. Members are paired and settle by one transaction between them and one 'to the rest'.
  3. Each pair is now treated as a single entity and the process repeated
The selection of pairs and which is to deal on behalf of both can be optimised.

Analysis

This method is at least twice as good in number and size of transactions as the 'all debtors pay into the pool then all creditors take out' method.
Financial institutions that get paid commission or charge interest while we're waiting to get paid won't be too happy.
CommentsPossibilities
  1. Roll on that happy day when somebody other than me is writing all the cheques.
  1. There's more work to be done to tie down a few loose ends in optimisation, simulation and dealing with the binary-chop discrepancy system. Be my guest.
  2. Actually my curiosity is fired up about how errors can be detected. I'm sure there must be a scheme that's even better than pure binary chop for fingering rogue reporting. Here's a general problem description
Contact details are in the article