Imagine a group trip with 10 friends. Over a week, they generate 50 different shared expenses. Alice paid for dinner, Bob paid for the Uber, Charlie paid for drinks, and so on. At the end of the trip, if everyone tried to pay back exactly who they owed for each specific transaction, you would need dozens of bank transfers to settle up.
This is inefficient, confusing, and incurs unnecessary transaction fees. At Finovoo, our goal is to reduce this chaos to the absolute minimum number of transfers required. To do this, we turn to graph theory.
The N² problem
In a naive settlement approach, the number of potential transactions grows quadratically with the number of participants. If everyone owes everyone else, a group of 10 people could theoretically require 90 transactions (n * (n-1)).
Visualizing debt as a graph
We model the group's finances as a Directed Graph, where participants are nodes (vertices) and debts are directed edges. An edge from Node A to Node B with a weight of $20 means "A owes B $20".
Step 1: Calculating net balances
The first step in our algorithm is to ignore the individual transactions and calculate the Net Balance for each person. It does not matter that Alice owes Bob $10 and Bob owes Alice $5. All that matters is that Alice owes a net total of $5.
Example: Alice (+50), Bob (-20), Charlie (-30). Alice is owed $50, while Bob and Charlie owe money. The specific history of who paid for what is now irrelevant; we only care about clearing these balances.
Step 2: The greedy matching algorithm
Once we have the net balances, we need to reconstruct a new graph with the fewest edges possible. We use a Greedy Algorithm to match debtors and creditors.
- Sort the participants into two lists: Debtors (negative balance) and Creditors (positive balance).
- Take the largest Debtor and the largest Creditor.
- Match them. If the Debtor owes $100 and the Creditor is owed $80, the Debtor pays the Creditor $80. The Creditor is now settled (0 balance), and the Debtor remains with -$20.
- Repeat the process with the remaining balances until everyone is at 0.
Handling cycles
One of the most satisfying parts of graph simplification is removing cycles. A cycle occurs when A owes B, B owes C, and C owes A.
If the flow is equal (everyone owes $10 in a circle), the net effect is zero. Our net balance calculation (Step 1) naturally eliminates these cycles because the positive and negative flows cancel each other out before the settlement phase even begins.
Real-world constraints
While the math is elegant, the real world is messy. Sometimes, users specifically request not to simplify debts between certain people. In these cases, we partition the graph into subgraphs and run the optimization locally within those constraints.
By reducing the number of edges in the graph, we save our users time, money on transfer fees, and the headache of tracking dozens of small payments.