The math behind “simplify debts”

Five of you go away for the weekend. You booked the cabin, Sam paid for the groceries, Alex covered the gas and the kayak rental, someone else got dinner out twice. By Sunday nobody has a clear idea who owes who. So who pays who, and how few times does money actually need to change hands?

Only the net matters

The first thing to know is that all those separate expenses collapse into one number per person. Add up what you paid, subtract your share of everything, and you're left with a single balance. You're either up (the group owes you) or down (you owe the group). Add up everyone's balance and it comes to exactly zero. All the receipts and little IOUs disappear into five numbers that sum to nothing.

You never need more than a handful of payments

There's a clean result here, written up by the computer scientist Tom Verhoeff in 2004 and proved again from scratch in a 2017 Harvard thesis. Any group of n people can always settle up in at most n minus one payments.

The easy way to see why: pick one person to act as the bank. Everyone who owes money pays the bank. The bank then pays everyone who's owed. That's it, and it's never more than n minus one transfers. So five people can always square up in four payments or fewer. Ten people, nine or fewer. It never gets worse than that.

Two goals people mix up

When an app says it “simplifies debts,” it could mean one of two different things, and they are not the same:

• The fewest payments. The smallest number of separate transfers anyone has to send.
• The least money moved. The smallest total dollar amount sloshing around the group.

One of these is easy. The other is genuinely hard.

Least money moved is the easy one

Minimizing the total amount moved has a simple recipe. Take anyone who's owed money and anyone who owes, and settle the smaller of the two amounts between them. One of them is now at zero, so drop them and repeat. That always moves the least money possible, which works out to exactly half the sum of everyone's balances, and as a bonus it never needs more than n minus one payments. This is the sensible default, and it stays fast even for big groups.

Fewest payments is the hard one

Minimizing the number of payments sounds like it should be just as easy. It isn't. It's NP-hard, which is the computer science way of saying there's no known fast method that always finds the exact answer as the group grows, and most likely there never will be.

The reason is kind of elegant. The way you save a payment is by finding a subgroup whose balances already cancel out among themselves. Say three people's balances happen to add up to zero without anyone else's help. Those three can settle inside their own little circle and stay out of everyone else's transfers. Every self-canceling subgroup you find saves you one payment. But finding the most of those subgroups is the hard part. It's tangled up with classic hard problems like subset-sum and 3-partition, and nobody knows a shortcut.

Why none of that touches your dinner

In practice the hardness never reaches you. NP-hard is a statement about what happens as a group grows toward hundreds or thousands of people. For a real group, five people, twelve, even twenty, a computer can just try every possible grouping and hand you the true minimum in a blink. The problem is only frightening at a scale you will never split a bill at.

This is what the settle-up screen does

This is the math running behind the settle-up screen in dvup, and behind the free who owes who calculator on this site. You put in what everyone paid, and instead of five people firing money in every direction, you get one short list of who pays who. Fewer transfers, no arguing, everyone even.

Questions