The fewest payments to settle up: how debt simplification works

A weekend away with three friends, and nobody splits anything on the spot. Ann buys brunch for the table. Ben covers the rental car. Cara grabs the groceries. Dan picks up dinner. Four expenses, each one quietly owed back by the three people who didn’t pay — which is twelve little IOUs by Sunday night, none of them written down, all of them faintly remembered. That is the moment someone says “ugh, let’s just figure it out later,” and later never comes.

Here is the part nobody expects: that knot of twelve debts settles in two payments. Not because anyone forgives anything, but because most of those IOUs cancel each other out. Settling a group is not about paying back every debt — it’s about paying back every net balance, and there are far fewer of those. The math that proves it is the same math banks use to settle up with a fraction of the payments, and it has a clean guarantee at its center: any group of n people can settle up in at most n − 1 payments.

12 IOUs four friends can rack up in a weekend

2 payments that actually settle them

n − 1 payments that settle any group, guaranteed

96%+ funding CLS’s bank members save by netting instead of paying gross

Netting figure: CLS Group, “Netting for businesses.” The settlement bound is a result in combinatorial optimization (Verhoeff, 2004).

Why does settling up turn into a tangle?

Settling up feels tangled because the number of possible debts grows much faster than the number of people. When everyone covers a few things for the group, each expense splits into one IOU per person who didn’t pay. With four friends and four shared expenses, that’s already twelve directed debts; with bigger groups it explodes. Tom Verhoeff, a computing scientist at Eindhoven, put the worst case exactly: n people can owe each other up to n(n − 1) separate transfers — “i pays a to j for all relevant pairs.” For five people that’s twenty possible IOUs; for ten people, ninety. No wonder the group chat stalls. The mistake hidden in “let’s figure it out later” is treating every one of those arrows as a payment someone has to make.

   n(n − 1)The most IOUs a group of n people can owe each other when
nobody settles on the spot. Ten friends on a trip can generate up to
ninety little debts — which is exactly why “we’ll
sort it out at the end” turns into a spreadsheet nobody wants
to build. 

Source: Tom Verhoeff, “Settling Multiple Debts Efficiently,” Informatics in Education (2004).

splitty’s take: the cheapest web of debts to untangle is the one that never forms. splitty is built on the blunt version of that idea — settle each bill the moment it lands, so the n(n − 1) tangle never gets a chance to build — which is a different bet from every app that lets the debts pile into a ledger and then simplifies them later.

Do you have to pay back every single debt?

No — and this is the whole trick. The only thing that has to be true at the end is that each person’s net balance reaches zero: what they paid out minus what they owed. How the money gets there is free. So the first move in settling any group is to throw away the individual IOUs and compute one number per person. Take the weekend: brunch was $80, the car $160, groceries $60, dinner $100 — $400 total, an even $100 each. Line up what each person fronted against that $100 share and the twelve debts collapse into four net positions, two of which are owed money and two of which owe it.

FriendPaid for the groupNet balance

Ben (rental car) $160+$60 — is owed

Dan (dinner) $100$0 — even

Ann (brunch) $80−⁠$20 — owes

Cara (groceries) $60−⁠$40 — owes

Now the picture is simple. Ben is up $60, Cara is down $40, Ann is down $20, and Dan is square — he paid exactly his $100 share, so he neither sends nor receives a cent. The debtors’ shortfalls (−⁠$40 and −⁠$20) sum to the creditor’s surplus (+$60), as they always must. Settling is now just routing $60 from the two people below zero to the one person above it. That takes two payments: Cara sends Ben $40, Ann sends Ben $20. Twelve IOUs, two transfers, done.

Two is partly luck: Dan landed exactly on his $100 share, so he dropped out of the settlement entirely. Even when nobody zeroes out that cleanly, four people never need more than three payments — the n − 1 ceiling we’ll prove next. The coincidence shaved off one transfer; the guarantee is what caps the rest.

The one idea to keep: you don’t settle debts, you settle balances. Cancel everything that offsets first, and the number of payments left is almost always a fraction of the number of IOUs you started with.

What’s the fewest payments that can settle any group?

For a group of n people, the answer is never more than n − 1 payments — and often fewer. The intuition is short: arrange the payments so money never flows in a circle, and each one can fully zero out at least one person. With n people and nothing looping back, you never need more than n minus one transfers to drain everyone to zero. That’s a hard guarantee, not a rule of thumb — and when two people happen to zero out on the same payment, like Dan above, you need fewer still.

The ceiling: any group of n people settles in at most n − 1 payments — usually fewer. Eight people at dinner clear in at most seven transfers, no matter how scrambled the “I got yours, you got mine” history is.

The proof is a small piece of graph theory, for anyone who wants it. Draw an arrow from each person who owes to each person they pay; a valid settlement is a set of arrows that zeroes everyone’s balance. You can always rearrange those arrows so the picture has no loops — no money flowing in a circle — and a loop-free graph (a “directed acyclic graph”) on n points has at most n − 1 arrows. Verhoeff proves exactly this: “an acyclic graph on N points has at most N − 1 arrows… the graph contains no more than N − 1 transfers.”

Pay back every IOU up to n(n − 1) transfers

Settle net balances at most n − 1 transfers

the payments netting saves you grows with every person at the table

For ten people: up to 90 IOUs collapse to at most 9 payments — and usually far fewer.

Put plainly: a dinner for eight never needs more than seven payments to settle, no matter how scrambled the “I got yours, you got mine” history is. The tangle is an illusion created by counting debts instead of balances. Once you count balances, the ceiling is low and fixed.

Source: Tom Verhoeff, “Settling Multiple Debts Efficiently,” Informatics in Education (2004).

How did banks solve the same problem?

Banks hit this problem at enormous scale and solved it the same way: they net. Two banks that trade with each other all day don’t wire every deal — they offset the day’s flows and move the single difference, exactly like Ann and Cara routing their shortfalls to Ben. Done across many institutions at once, it’s called multilateral netting.

In 1990 the central banks of the G10 wrote the rulebook for it. The Bank for International Settlements’ Lamfalussy Report recognized the advantages netting “can have in terms of improving both the efficiency and the stability of interbank settlements, by reducing costs and risks” — provided it’s done right. The payoff is not subtle. CLS, which settles foreign-exchange trades for its member banks, reports that multilateral netting “shrink[s] funding requirements by over 96%” — the same value moves, with a fraction of the actual payments.

1941Frank Hitchcock poses the transportation problem — how to move goods from sources to destinations at least total cost. It turns out to be the math behind moving the least money, too.

1979Garey and Johnson publish the field guide to what’s computationally hard — the toolkit that later pins down why the absolute fewest payments is a tough problem.

   1990The BIS Lamfalussy Report codifies multilateral netting for the world’s banks — settle the net, not the gross. 

2004Verhoeff frames “settling multiple debts” as a clean computing-science problem — and proves the n − 1 ceiling.

todayCLS nets away over 96% of funding for its members. Your dinner is the same idea, four people instead of forty banks.

A clearing house and a group chat are solving the same puzzle: not “who owes whom,” but “what’s the smallest set of payments that makes every balance zero.”

Sources: Bank for International Settlements, Lamfalussy Report (1990); CLS Group, “Netting for businesses”; Hitchcock, Journal of Mathematics and Physics (1941).

Why is finding the absolute fewest payments so hard?

Because there are two different goals hiding inside “simplify the debts,” and one of them is famously hard. Minimizing the total amount of money that moves is the easy one: it’s the classical transportation problem from 1941, and a computer solves it efficiently. Minimizing the number of payments is the hard one. Verhoeff shows it is NP-hard — equivalent to a notorious problem called 3-Partition, “NP-complete in the strong sense.” In plain terms: there’s no known shortcut faster than checking enormous numbers of combinations, and as Verhoeff dryly notes, if you found one “you’d be famous instantly.”

Easy (solved 1941)

Move the least money

Minimize the total dollars that change hands. This is the transportation problem — a network-flow calculation a computer handles in an instant.

Fast, exact, scales to thousands of accounts

Doesn’t promise the fewest separate transfers

Hard (NP-hard)

Make the fewest payments

Minimize the count of transfers. Verhoeff proves this is NP-hard — as hard as 3-Partition — so the perfect minimum can’t be found quickly for big, messy webs.

Fewest possible Venmo notifications

No fast algorithm guarantees the true optimum

The saving grace is that you almost never need the perfect minimum. The n − 1 ceiling is easy to hit, and for the size of a real dinner or trip, a simple greedy pass usually lands on the optimum anyway. Apps that “simplify debts” lean on exactly this: a fast heuristic that gets you to a handful of payments, not a doomed search for the theoretical best. Worth a caveat, though: minimizing the count of payments is not the same as maximizing whether those payments actually get made — and the second is the number that decides if you’re paid.

Sources: Verhoeff, Informatics in Education (2004); Garey & Johnson, Computers and Intractability (W. H. Freeman, 1979).

How to settle your group in the fewest payments

You settle a group in the fewest payments by working with net balances, not IOUs: total each person up, sort them into who’s owed and who owes, then knock out the biggest mismatches first. Three steps clear almost any group at or below the n − 1 ceiling.

Net everyone to a single number

For each person, add up what they paid for the group and subtract what they owed. The result is one balance: positive means they’re owed money, negative means they owe it. Throw the individual IOUs away — from here on only the balances matter, and they always sum to zero.

Split the group into owers and owed

Put everyone with a negative balance in one column (they’ll send money) and everyone positive in the other (they’ll receive it). Anyone sitting at zero is already done and never touches a payment app.

Match biggest to biggest, repeat

Have the largest ower pay the largest owed person the smaller of their two amounts. That zeroes at least one of them; cross them off and repeat. Every round retires a person, so you finish in at most n − 1 payments — usually fewer, because some payments zero out two people at once.

How much does netting actually save a group?

On a real group, netting turns a wall of small transfers into a couple of clean ones. Take the same four friends and count it both ways. Paid back debt by debt, the weekend is a dozen separate Venmo requests — everyone pinging everyone for $15 here and $25 there. Netted, it’s two payments totaling $60, and one person never opens an app at all. The numbers themselves don’t change; the count of payments collapses, and the count is what makes settling up feel like a chore.

Pay every IOU (gross)Settle balances (netted)

Separate payments 122

People who must act 42

Total dollars moved $300 in fragments$60

Group-chat messages “wait who owes who?”two requests, sent

Scale that to a ten-person trip and the contrast gets dramatic: up to ninety possible IOUs versus at most nine payments. The bigger the group, the more netting saves — which is exactly why the institutions with the most payments to make, the banks, were the ones who industrialized it first.

Where does splitty fit in all this?

splitty’s answer is to stop the tangle before it starts. The fewest-payments algorithm is what you reach for after a web of debts has already formed — weeks of roommates covering each other’s share, a running ledger to untangle later. splitty works at the other end: it settles each bill the moment it happens, so the web never builds. One person pays the check; splitty reads the receipt, assigns each item to the people who shared it, and sends everyone else a single pre-filled request back to that one payer.

There’s a design reason to prefer “before” over “after” that goes beyond convenience: at the moment the check arrives, the net structure is already at its simplest. One person paid; everyone else owes only them. That’s already the n − 1 minimum — a star-shaped graph with one creditor at the center and everyone else pointing in. No algorithm can do better, because the graph is already optimal. Once that dinner joins a multi-week ledger, the shape gets complicated and simplification becomes necessary. splitty’s bet is that keeping each bill’s structure simple — one payer, everyone else owes them — is faster than letting structure accumulate and then reasoning it away.

Only net balances matter, and a single bill has one obvious net structure→splitty points every share back to the one person who paid, so a table of n settles in n − 1 requests — already the minimal shape, no algorithm required.

Finding the fewest payments across a messy web of debts is NP-hard→splitty never lets the messy web form: each bill is settled to its payer on the spot, so there’s nothing tangled left to simplify.

An ongoing balance across weeks is a different problem from one night out→A long-running ledger is a debt-tracker’s job. Splitwise tracks the ongoing balance; splitty settles tonight’s bill — pick the tool that matches the problem.

The math of debt simplification is worth knowing the next time a group chat seizes up over who owes whom — though computing the payments is the easy half; confirming everyone actually paid is the part that lingers. The most reliable way to make the fewest payments is to never accumulate the debts — to settle the $60 or $460 check while you’re still at the table, with each person’s share already worked out, so “I’ll Venmo you later” never has to be said.

FAQ

Settling up — quick answers

Straight answers about netting, the fewest-payments problem, and how to clear a group fast.

01 What is the fewest number of payments to settle a group’s debts?

At most one fewer than the number of people — n − 1 — and often less. Settling a group isn’t about paying back every IOU; it’s about zeroing each person’s net balance (what they paid minus what they owed). Because a valid settlement can always be arranged with no money flowing in a circle, and a loop-free graph on n people has at most n − 1 connections, you never need more than n − 1 payments. A dinner for eight settles in at most seven transfers no matter how scrambled the history; four friends who racked up twelve IOUs on a weekend can clear them in two.

02 What does it mean to simplify or net debts?

Simplifying debts (or netting) means cancelling out offsetting IOUs so only the leftover balances get paid. If you owe a friend $20 and they owe you $15, you don’t send two payments — you net to a single $5. Across a whole group, you total each person to one net balance, then route money only from the people below zero to the people above it. Banks do exactly this at massive scale: the CLS settlement system reports multilateral netting shrinks funding requirements by over 96%, moving the same value with a fraction of the payments.

03 Why is finding the absolute minimum number of payments hard?

There are two goals inside ‘simplify the debts.’ Minimizing the total amount of money moved is easy — it’s the classic transportation problem, solved efficiently by computers since the 1940s. But minimizing the number of separate payments is NP-hard: computing scientist Tom Verhoeff showed it’s equivalent to a problem called 3-Partition, which is ‘NP-complete in the strong sense.’ There’s no known fast method to guarantee the true minimum for a large, tangled web. The good news: the n − 1 ceiling is easy to reach, and a simple greedy pass usually hits the optimum for real-world group sizes.

04 How do you calculate who owes whom in a group?

Work in net balances, not IOUs. First, total what each person paid for the group and subtract their fair share; the result is one number per person, positive (owed money) or negative (owes money), and the numbers always sum to zero. Then sort people into owers and owed, and have the biggest ower pay the biggest owed person the smaller of their two amounts. That settles at least one person; cross them off and repeat. You’ll finish in at most n − 1 payments, and anyone whose balance is already zero never has to send or receive anything.

05 Is debt simplification the same as splitting a bill fairly?

No — they’re two different steps. Splitting a bill fairly decides how much each person owes in the first place (their share of the items, tax, and tip). Debt simplification decides who pays whom once those amounts exist, minimizing the number of transfers. You can have a perfectly fair split that still leaves a tangle of small IOUs, and netting is what untangles it. splitty handles the first step from a photo and sidesteps the second by sending every share back to one payer, so a single bill settles in one round.

06 Should I use splitty or Splitwise to settle up?

It depends on whether you’re settling one bill or tracking an ongoing balance. Splitwise is built to track a running ledger over weeks or months — roommates, recurring shared costs — and then simplify the accumulated debts. splitty is built to settle a bill on the spot: scan the receipt, assign items, and send each person a pre-filled request back to whoever paid, so the debt is cleared before it ever joins a ledger. Splitwise tracks; splitty settles. For tonight’s dinner or this weekend’s trip, settling immediately means there’s nothing left to simplify later.

The Fewest Payments to Settle Up: How Debt Simplification Works

Why does settling up turn into a tangle?

Do you have to pay back every single debt?

What’s the fewest payments that can settle any group?

How did banks solve the same problem?

Why is finding the absolute fewest payments so hard?

Move the least money

Make the fewest payments

How to settle your group in the fewest payments

Net everyone to a single number

Split the group into owers and owed

Match biggest to biggest, repeat

How much does netting actually save a group?

Where does splitty fit in all this?

Settling up — quick answers

More in Splitting a Bill

Sources

Order what you want.

Why does settling up turn into a tangle?

Do you have to pay back every single debt?

What’s the fewest payments that can settle any group?

How did banks solve the same problem?

Why is finding the absolute fewest payments so hard?

Move the least money

Make the fewest payments

How to settle your group in the fewest payments

Net everyone to a single number

Split the group into owers and owed

Match biggest to biggest, repeat

How much does netting actually save a group?

Where does splitty fit in all this?

Settling up — quick answers

Related guides

More in Splitting a Bill

Sources Sources (5)

Order what you want.

Sources