The fewest payments that settle everyone up

The short version

Do not pay people back expense by expense. Work out one number per person, which is what they paid minus their share of everything they took part in, and then send money only from the people who are down to the people who are up. Nobody should be paying and being paid.

On the trip below, 6 shared expenses across 5 people come to $3,863.50. Paying each other back item by item takes 21 payments. Settling on the net takes 4, and every single person is out exactly the same amount either way.

Stop thinking in pairs

The reason a group holiday ends in a spreadsheet nobody trusts is that people settle up the way the expenses happened: you covered dinner so I owe you a quarter, I bought the groceries so you owe me a fifth, and around it goes. Every expense generates one payment per person who was in it, and they all point in different directions.

This page assumes the shares themselves are already agreed. If that part is still open, whether a cost should be divided equally, by income, by room or by usage, how to split shared costs fairly is the place to start, because settling the wrong shares efficiently is still the wrong answer.

Here is the trip. One week, five people, and deliberately not everybody in everything, because that is the case where the arithmetic stops being obvious.

• Ana booked the flights, $1,250, all five
• Ben paid for the house, $1,800, all five
• Ana also took the car hire, $340, all five
• Cleo did the big grocery run, $212.50, all five
• Dan covered dinner, $186, but Eve had already eaten
• Eve paid for the museum, $75, and only Ana and Ben went

Item by item, that is 21 separate paybacks: four people owing Ana for the flights, four owing Ben for the house, four more owing Ana for the car, four owing Cleo, three owing Dan, two owing Eve. Twenty one separate transfers for six purchases, and Ana is both sending money and receiving it four times over.

Work out the net, once

One number per person: what they paid out, minus what their fair share of everything came to. Positive means the group owes them, negative means they owe the group. The two things that make this reliable are that shares are computed per expense over only the people who were in it, and that the numbers add to zero when you are done, which is the check that catches a mistake.

The shares are not equal, and they should not be. Ana and Ben were in all six expenses, so they carry $792 each. Cleo and Dan missed the museum, so $767. Eve missed dinner, so $745.50. The differences are small but they are real, and an app that divided the total five ways would have charged Eve for a dinner she did not eat.

Route the payments

Two people are up and three are down, so money flows one way only. Take the largest debt and the largest credit and match them: whichever is smaller gets cleared completely, and that person drops out. Repeat with what is left. That is the whole algorithm.

On this trip it produces four payments:

• Eve pays Ben $670.50, which clears Eve
• Dan pays Ben $337.50, which finishes Ben
• Dan pays Ana $243.50, which clears Dan
• Cleo pays Ana $554.50, which clears Cleo and Ana together

Four transfers, no cash, nobody chasing anybody for a share of a museum ticket. Add the two payments Ben receives and you get $1,008, his exact net. That property, that the payments reproduce each person's net figure and nothing else, is what makes this safe rather than merely tidy.

Four payments is also four things somebody has to remember to do, and one of them not arriving is the normal outcome rather than the unlucky one. When someone doesn’t pay you back picks up from exactly here.

How few payments are possible

Each payment can be made to zero out at least one person completely, by sending exactly the smaller of the two amounts. Zero out one person per payment and after n minus 1 payments the last person must be square too, because the numbers sum to zero and there is nothing else left to balance.

So five people never need more than four payments, twenty never need more than nineteen, and the 21 paybacks the trip started with were never necessary. It is often fewer than the bound: anyone already square drops out before you start, and any pair whose amounts happen to match exactly clears in a single payment.

Where the greedy method loses, including ours

Matching biggest to biggest is fast and it always hits the n minus 1 bound, which is why essentially every app that does this uses it. What almost every app also says, ours included in the comment above the function, is that the result is the minimal set of payments. That is not quite true, and the counterexample is small enough to check by hand.

Take five people at -12, -11, +1, +11, +11. Greedy starts with the biggest debt, -12, and sends it to one of the +11s. That clears the creditor and leaves a dangling dollar, and the whole thing takes four payments. But look at the numbers: the person at -11 and one of the people at +11 cancel each other exactly. Pair those two off first and the remaining three settle in two payments, for a total of three. Greedy destroyed a perfect match by insisting on going in order of size.

Doing it optimally every time means finding as many groups as possible whose balances each sum to zero, and that is an NP-hard problem: there is no known method that is both fast and always right. Searching 53,163 random groups of four to seven people, greedy needed up to two payments more than the true optimum. So the honest claim is not that this is the minimum. It is that it is never worse than n minus 1, it is instant, and it gives the same answer every time you run it, which for settling a holiday is the trade every app makes and none of them mention.

Settle your own trip

Put your own people and expenses in. Toggle who actually shared each one, which is the part spreadsheets get wrong, and watch the payment count collapse.

This runs the same two functions the app runs, in your browser, and nothing is sent anywhere. If you would rather have one shared pot and just enter what each person paid, the standalone version is simpler.

The objection: why am I paying someone I never bought anything with?

This is the one real complaint about netting off, and it deserves a straight answer rather than a shrug. On the trip above Cleo pays Ana $554.50, even though Cleo's own spending was a grocery run that Ana only partly benefited from. The routing is chosen to minimize the number of payments, not to retrace who bought what.

What has to be true for that to be acceptable is that nobody's total changes, and it does not. Each person's net is settled before any routing happens. Cleo is down $554.50 whether she pays it to Ana in one transfer or to four people in seven. If the specific pairing genuinely matters, because you are splitting with someone you would rather keep a clean record with, settle each expense on its own: you will pay the same amount in more payments, and that is a legitimate choice rather than a mistake.

The one case to be careful with

If somebody in the group is unlikely to pay, netting concentrates that risk. Route the payments so the unreliable person owes one identifiable individual rather than being spread across three, and settle with them first. It costs a payment or two, and it means one person is chasing one debt instead of three people each being short.

Common questions

Every figure here was produced by running Halvy's own split and settlement functions on the worked example. The claim that the greedy method is not always minimal was checked rather than assumed: a brute-force optimum over every zero-sum grouping, compared against the shipped solver on 53,163 random groups, plus an exhaustive search for the smallest counterexample, which is the five-person case quoted above.