# Splitwise’s algorithm to simplify debts

A really useful app to use when you are sharing expenses with friends is called Splitwise. When you go on a trip with a group of friends, and there are many expenses that are shared, you can record everything easily using Splitwise. At the end of the trip, Splitwise will tell you exactly whom you owe and how much you owe. It makes things a lot easier so that you’re not constantly paying each other in cash during the trip or trying to keep track of all your debts in your head.

An interesting feature of Splitwise is the “simplify debts” option. At the end of a trip, even if you’ve split expenses with many people, Splitwise tries to simplify the debts so that the least number of payments have to take place to settle all the debts. So for example, if A owes B and B owes C, then the simplify debts option makes it so that A just owes C directly.

**Disclaimer:** The rest of this post is technical.

## Model the expenses in a graph

I’ve used this option quite frequently, but I never really thought about how the algorithm works. At first glance, it is quite easy to model the expenses as a weighted directed graph, where there is an edge from A to B with weight x if A owes B $x.

To “simplify debts”, we can find a directed path with edges of the same weight and replace it with just one edge. Then we can combine multiple edges between two nodes.

This method is very intuitive to understand; however, the implementation can be quite complicated. How do we find all the paths in a graph in an efficient manner? Which path do we pick to eliminate when there is more than one choice? What do we do when all the weights are different? How do we know the solution is optimal?

## Change the model

It turns out that this problem becomes much simpler if we just store less information. For each person, we just store their total balance, discarding the information of *to whom* the person owes money. So, if I’ve lent $40 to various people and borrowed $100 from others, my **balance** is $60, and we just have to store (Jackie, 60). A positive balance means the person owes money, and a negative balance means they are owed money.

Although this simplifies the model, it is less intuitive, and the results can be quite confusing. For example, even if I’ve only split expenses with A and B during the entire trip, the result may show that I owe money to C. This is because I never keep track of *with whom* I’ve split expenses.

Nonetheless, with this information, there is a simple algorithm that requires at most N-1 payments to settle all the debts:

## Algorithm for N-1 payments

Let’s say there are N people, indexed from 0 to N-1. Let **B[i]** denote the balance of the i’th person (a positive balance means they owe money). There is one constraint that we have on these values: since money was only loaned or borrowed from within the group, the *net* balance should be zero (i.e. B[0] + B[1] + … + B[N-1] = 0).

Create a graph such that there is a node for each person denoted with their balance.

Like before, a directed edge from B[i] to B[j] with weight x will represent a settlement where person i pays person j amount $x. If the edge has a negative weight, it is equivalent to flipping the direction of the edge and making the weight positive.

From the first node, create an edge to the second node with weight B[0]. In the example below, since the first person had a balance of 50, but then paid the second person 50, the first person is now debt free and has a balance of 0.

Then, create an edge from the second node to the third node with weight B[0] + B[1], an edge from the third node to the fourth node with weight B[0] + B[1] +B[2], and so on. Basically, we are adding an edge from person i to i+1 with weight that will make the balance of person i zero.

When we are finished, the weight of the last edge is B[0] + B[1] + … + B[N-2]. This value should equal -B[N-1], since we have the initial assumption that B[0] + B[1] + … + B[N-1] = 0.

We can make the graph look more intuitive by getting rid of the negative weights and flipping their edges.

Since the final graph has N-1 edges, this proves that any Splitwise group can be settled with N-1 transactions.

## Optimal?

Unfortunately, this algorithm is not optimal. The very first example with three people was settled with only one payment. It turns out that finding an optimal solution for this problem is NP-hard [1]. So there is no efficient way to find the best solution for this problem. Who knew that dealing with debts was so difficult?!

Practically, I think everyone having to deal with at most two transactions is simple enough for this specific debt-simplifying problem. Furthermore, using an exponential-time algorithm to find the optimal solution would be feasible for this specific problem, since the number of people sharing expenses within a Splitwise group is most likely pretty small.

I’m not sure which algorithm Splitwise actually uses; but whatever they use, it simplifies my life greatly!

—

[1] In the case that there are exactly two people who are owed money and the rest owe money, this problem is equivalent to subset sum, which is NP-hard.

Syed Ashrafulla

June 15, 2015@ 9:06 pmI like this post a lot! With respect to the triangle above, your algorithm basically works because B goes away (owed 0, so kick it out). Suppose we removed all 0s & all pairs that match up (easy O(N) with two running indices). How close do you think it is to optimal?

Also another interesting tweak which would decrease the maximum size of any transaction is to do two sorts and then interleave:

smallest positive -> smallest negative -> 2nd smallest positive -> 2nd smallest negative -> … -> largest positive -> largest negative

although I guess that increases the # of transactions?

Jackie Baek

June 15, 2015@ 10:46 pmGlad you enjoyed it!

Oh good point, yes the algorithm does work for the first example. For the algorithm to not be optimal, the optimal settlement would have at most n-2 transactions. For this to happen, I think we would need at least 2 people who are owed money, and at least 4 people owing money, so 6 ppl total. (Any less than that, my algorithm with the removed 0’s and matched pairs would be optimal)

Yea, I think there are many things that I didn’t consider if I actually wanted to implement this for settling debts, like decreasing the size of the maximum transaction. Another could be adding the constraint that I would never have to pay somebody I didn’t already owe before. Though this would make the algo more complicated as it would have to bring back the directed graph!

ologn13

November 19, 2015@ 7:22 pmFound out your blog while searching for splitwise app :). I did “deep dive” into the problem and figured out a simple greedy O(N^2) algorithm. And thus, I don’t think it is an NP-hard problem :).

The algorithm is simple.

1. First calculate the net amount for each person (might be debit or credit).

2. Then, find out the maximum creditor C(maximum net amount) and maximum debitor D(minimum net amount).

3. Settle up both of these person.

4. If the debitor D has given all of his money, remove him from the graph, else remove the creditor C from the graph. Now, we’re left with (N-1) persons, where N were total number of persons in starting.

5. Recur the algorithm from step 2.

O(N^2) can be improved to O(N*logN) with a priority_queue.

But anyway, you did write a nice blog post about it 🙂

PS: You can find a similar problem here: http://www.spoj.com/problems/ANARC08G/

-Vikrant

jackiewbaek

November 19, 2015@ 10:30 pmHi Vikrant,

I thought of that algorithm as well; but it is not optimal, where optimal is defined by the fewest number of transactions.

For example, if you consider three debts: [-6, -5, -5], and two credits: [10, 6], it is clear that the optimal solution only requires 3 transactions (first debt -> second credit, second debt -> first credit, third debt -> first credit). When I run through your algorithm, it requires 4 transactions. To get the optimal solution, we need to match the debit -6 with credit 6, but that is not possible using a greedy algorithm.

It is a very nice and simple algorithm though, and probably good enough in most scenarios!

ologn13

November 20, 2015@ 5:27 amHmm, I think you’re right. The algorithm I mentioned is not optimal when we have “sub-groups” which can settle up debts within themselves, i.e., sub-groups with net amount equal to 0. Though the standard subset sum problem can be solved in pseudo-polynomial time, still, finding all the sub-groups with certain sum(0 here) is exponential. I doubt splitwise having a polynomial-time algorithm for this problem 😀