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.

Screenshot 2015-04-08 15.27.43

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.

Screenshot 2015-04-08 16.28.11

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.

Screenshot 2015-04-08 21.55.31

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.

Screenshot 2015-04-08 22.14.20

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.

Screenshot 2015-04-08 22.04.44

This denotes that the first person will pay the second person $50.

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.

Screenshot 2015-04-08 22.07.25

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.

Screenshot 2015-04-08 22.09.18

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.