The Debt Simplification Problem

Splitting bills with graphs

Marcin Szopa

The trip

  • Ala paid for the hotel
  • Bartek paid for fuel
  • Celina paid for dinner
  • Darek paid for nothing

Result: 6 debts, 4 people.

Marcin Szopa · Professional Skills in CS

The one idea that matters

Nobody cares who they pay. Only the net balance matters.

Balances always sum to zero. Positive = creditor, negative = debtor.

Marcin Szopa · Professional Skills in CS

Greedy: biggest debtor pays biggest creditor

Repeat until everyone is at zero:

  1. pick the person with the most negative balance
  2. pick the person with the most positive balance
  3. transfer min(|debt|, credit), one of them is settled

6 payments → 3. At most n − 1 payments, always.

Marcin Szopa · Professional Skills in CS

Greedy is not optimal

Balances: +6 +4 −3 −3 −2 −2

Greedy: 5 payments

Optimal: 4

  • {+6, −3, −3} settles itself
  • {+4, −2, −2} settles itself
  • two groups → n − 2 payments

Marcin Szopa · Professional Skills in CS

Why it is hard

Minimum payments = n − (max number of zero-sum groups)

Deciding "is there a zero-sum group?" is Subset Sum → the problem is NP-hard.

Verhoeff, Settling Multiple Debts Efficiently, 2004

Exact solution: DP over subsets, . Fine for a flat share, not for a company.

Marcin Szopa · Professional Skills in CS

The twist

Splitwise shipped debt simplification.

Users turned it off.

"Why am I paying someone I never had dinner with?"

Marcin Szopa · Professional Skills in CS

Thanks

Questions?

Slides: github.com/MrD4rkne/psics

Marcin Szopa · Professional Skills in CS

Hook: four friends, one weekend trip, nine payment requests in the group chat. This talk: why that is a graph problem, why the obvious fix is wrong, and why nobody wanted the right answer anyway. ~0:20

Every arrow is a payment somebody has to make. Six arrows is annoying; with 8 people it is dozens. Model: directed weighted graph, nodes = people, edge u->v with weight w = u owes v w. ~0:40

Collapse the graph: for each person, income minus outgoings. Now the question is: find the smallest set of transfers that moves every balance to zero. ~0:50

Each step zeroes at least one person, so at most n-1 steps. Linear-ish, trivial to code. This is what every "how Splitwise works" blog post describes. ~1:00

Greedy first sends -3 to +6 (fine) then -3 to +4 (mixes the groups) and ends at 5. Splitting people into independent zero-sum groups saves one payment per extra group. ~0:50

One sentence, no proof. Mention the exponential DP so it is clear "hard" does not mean "impossible" for 10 friends. ~0:40

Optimal graph, wrong UX. People trade an extra transaction for a payment that makes sense socially. Closing: the algorithm was right; the problem statement wasn't. VERIFY the Splitwise claim and quote before presenting. ~0:40