Who owes whom: settling a group in the fewest payments
When a trip is over, the question is never "what did we spend". It is "who pays whom, and how much, so that we can stop thinking about it". This post is about how xplit answers that, because the method is simple enough to explain and worth understanding even if you never use the app.
Start from balances, not debts
The tempting way to think about shared costs is as a web of debts: Ben owes Ana for dinner, Ana owes Chloé for the boat, Chloé owes Dan for groceries, and so on. With four people there are six possible pairs; with eight people there are twenty-eight. Paying back along every pair is how a weekend ends with fifteen bank transfers of 11.20.
The better way is to forget the pairs and give each person one number: their balance. It is what they paid, minus their share of everything they took part in.
- Paid a lot, took part in little: large positive balance. The group owes you.
- Paid nothing, joined everything: negative balance. You owe the group.
- Balances always add up to zero, because every cent paid is someone's share.
Once everyone has a balance, the question becomes: what is the shortest set of transfers that brings every balance to zero? The pairs no longer matter. It does not matter that Ben's debt "came from" Ana's dinner; money is money.
Match the biggest creditor with the biggest debtor
Here is the method xplit uses, and it is the one most people arrive at by hand after a minute's thought.
- Line up everyone who is owed money, largest first. Line up everyone who owes, largest first.
- The largest debtor pays the largest creditor. The amount is whichever of the two balances is smaller.
- That payment reduces both balances. At least one of them is now zero and drops out.
- Repeat with whoever is left.
Every step settles at least one person completely, so with n people it takes at most n − 1 transfers. Four people, three payments at the very most, and often fewer, because a transfer sometimes zeroes both sides at once.
An example
Four friends, a long weekend, five activities. After xplit has added up what everyone paid and subtracted everyone's shares, the balances are:
| Person | Paid | Share | Balance |
|---|---|---|---|
| Ana | 310.00 | 153.10 | +156.90 |
| Ben | 0.00 | 153.10 | −153.10 |
| Chloé | 182.40 | 153.10 | +29.30 |
| Dan | 120.00 | 153.10 | −33.10 |
The creditors are Ana (156.90) and Chloé (29.30). The debtors are Ben (153.10) and Dan (33.10).
- Ben pays Ana 153.10. Ben is done; Ana is still owed 3.80.
- Dan pays Ana 3.80. Ana is done; Dan still owes 29.30.
- Dan pays Chloé 29.30. Everyone is at zero.
Three payments. By pairs it could have been six, and by "paying back after each dinner" it would have been a dozen.
Is it the absolute minimum?
Usually, and always close. Finding the smallest possible number of transfers for an arbitrary set of balances is, in the general case, a hard problem: there are cases where some clever subset of people happens to sum to exactly zero and can settle among themselves with one fewer payment. Searching for those subsets is expensive and the gain is one transfer, occasionally.
The largest-with-largest method never needs more than n − 1 transfers, is predictable, and produces a list that looks like what a sensible person would have written down. That is the trade xplit makes. If you spot a shorter settlement for your trip, pay that way; the balances are the same either way.
Groups: when two people pay as one
A couple sharing a card does not want two lines in the settlement. In xplit, drag one onto the other to make a group. The group's balance is the sum of its members' balances, and the group settles as one person. If one of them is owed 40 and the other owes 15, the group is owed 25, and that is the single transfer that appears.
Everything else stays the same: what each person paid, which activities they joined, their individual shares. Disband the group and the two of them are back in the list on their own.
The one case to check in any tool
Someone pays for an activity they do not take part in: a parent booking the kids' boat trip, a host paying the caterer for a dinner they did not sit down to. Their share of that activity is zero, so their balance should be the full amount they paid. It is an easy case to get wrong in code, and an irritating one to get wrong for real, so it is the first thing worth testing in any expense splitter, including this one.