Greedy Debt Minimization: Reducing Group Expenses to at Most N−1 Transfers
How circular dining debts and tangled multi-currency expenses are mathematically condensed into the minimal number of peer-to-peer settlements.
The Pairwise Settlement Bottleneck
In a group of 6 travelers over a 10-day vacation, hundreds of micro-expenses occur: someone pays for the rental car, another buys street food, a third pays for accommodation. If settled pairwise, the group would need up to 15 separate bank transfers, many of which cancel each other out.
The Net Balance Equation
SplitBill models every participant by their net balance: net(u) = paid(u) − share_total(u) + repaid_out(u) − repaid_in(u). All foreign currencies are converted to the trip's base currency using rates frozen on the transaction date. Across all participants, the fundamental invariant Σ net(u) ≡ 0 holds true.
Greedy Bipartite Settlement Algorithm
To clear all debts, a greedy bipartite matching algorithm repeatedly pairs the participant with the largest net debt with the participant with the largest positive credit. The minimum of the two amounts is settled, moving at least one party to exactly zero. This algorithm mathematically guarantees full settlement in at most N−1 transactions.