Imagine the following problem: Amelia, Bill, Clemens, Dean and Eric are friends living together. Whenever they need to buy something to be used communally, one of them picks up the cost.

For a joint camping trip, Amelia pays £30 for food, Bill spends £45 on fuel, Clemens pays £10 for some cheap booze, Dean buys a tent for £35 and Eric gets some bug spray for £5.

Clearly, this isn’t fair. The friends could set up a joint account, and use it as an intermediate step to resolve all their debts, but it’s easier just to pay each other directly.

The problem is resolving the debt with the fewest transactions. I think I’ve come up with a solution, using quadratic programming, but I can’t prove its correctness.

First of all, let’s specify the problem more accurately. We want a set of transactions between the friends that will lead to them having spent the same amount of money. That amount of money is going to be the mean amount spent.

Let the balance, , be the difference between the amount spent and the goal value:

where is the amount spent by the Nth person, and N is the number of people in the group.

In our case, the average cost is £25, and:

Clearly, the optimal solution will only have transfer from people with negative balance to people with positive balance, so we split the friends into those who owe and those who are owed.

Another constraint we can add is that no one should pay more than they owe, and no one should receive more than they are owed. This makes the problem sound like a flow network.

In this flow network, all edges go from left to right, and their capacities are determined by the values .

This particular flow network corresponds to 5 inequalities:

If we make vectors out of the balances and the transaction values, we can write these inequalities as a matrix inequality:

With the further constraint that:

Our goal now is to find the solution to this inequality which has the most zero-value transactions. Up until here, I think everything I said was justified, but I’m going to make the following conjecture:

The solution to the inequalities that maximises the sum of squares of transactions (i.e ) will have the same number of zeros or fewer than any other solution.

This conjecture is based on the intuition that maximising the sum of squares will maximise the variance in transactions, and will do so by hitting as many boundaries as possible.

To test this conjecture out empirically, I used MATLAB’s GlobalSearch class, which attempts to optimise a problem by running an optimising algorithm from a random selection of starting points, picking the best local optimum found. Here’s some code. You’ll need the MATLAB Global Optimization Toolbox. Sorry about that.

Anyway, running the program on our sample data set produces the following output:

Clemens pays Amelia 5.00

Clemens pays Dean 10.00

Eric pays Bill 20.00

Which is a very acceptable solution. Trying out different numbers, I couldn’t come up with a counter example or a proof. Any ideas?

Try http://scroooge.it/ The website was developed by some compscis who wanted to keep track of how much they owed each other. You do need people to update all the transactions on the web though and personally I think that it would only be successful as an iphone app and if everyone had an iphone.

I think the contraints in the text might be too strong. If we assume a simpler problem (A paid 1, B paid 2, C paid 6) than A owes 2, B owes 1, and C shall receive 3. Now the trivial solution is that both A and B give the right amount to C, and this fulfills the constraints. But there is another, equally optimal solution: A gives 2 to B, then B gives 3 to C. IOW the constraints excluded a solution and we were just saved by the existence of another one.

Unfortunately, I couldn’t invent a problem where the constraints enforce a suboptimal solution, but I’d not enforce them without having a proof that they do not exclude the optimum.

There is always a trivial solution involving N-1 transactions: A gives what he totally owes to B,

B then to C etc. in such a way that each one balances his own account (that’s how I found the solution to my example, and the participants should be sorted to avoid the need for negative money). So for the problem to be interesting, the numbers probably have to be small integers, otherwise I think that the N-1 steps are necessary.

My idea about this would be brute force: start with the full directed graph, then we have N*(N-1) variables (flows along edges) and N-1 linear equations (balance at every node except the last one). I guess that unless there is a simple linear relation between the r.h.s. of the equations (i.e. the small integers mentioned above), we are stuck with n-1 variables being determined by the equation system. If that is true, then your solution (with only three transactions) is just one with ?our transactions of which one happens to be exactly zero.

I just found out that the problem is indeed special. If we order the people as E, B, C, A, D; then the chain of N-1=four payments in the worst-case general solution is 20, 0, 15, 10. The zero payment from Bill to Clemens is an accident caused by the special values of the numbers.

I left a comment on Reddit showing that the problem is NP-hard, because the subset sum problem can be reduced to it.

http://www.reddit.com/r/math/comments/dioxr/resolving_debts_to_your_friends_with_minimal/c10huhd

That’s pretty awesome. Thanks!

If we imagine that each transaction happens in sequence, then maximising the squares of the sum of the transactions is equivalent to ensuring that the maximum possible value of transaction occurs at any one time. This is better explained with an example, I think (though it should probably be one that is slightly more complicated than yours):

A pays £13 => owes £7

B pays £2 => owes £18

C pays £31 => owed £11

D pays £25 => owed £5

E pays £29 => owed £9

Start with the biggest transaction, so B pays C £11. That leaves:

A owes 7, B owes 7

D owed 5, E owed 9

Now A pays E £7, leaving:

B owes 7,

D owed 5, E owed 2

And now B pays D £5 and E £2.

So we have payments of £11, £7, £5 and £2. (Sum of the squares = 199)

Now, the question is, is this algorithm equivalent to maximising the sum of the squares? The answer is yes, since each transaction adds the most to the sum of the squares that it can at that point. There is no way to improve on total because you can never increase the maximum possible transaction by doing a lesser valued option.

So that algorithm is equivalent to your matrix based approach. It then has to be proven that this algorithm must be as efficient as any other approach. I can’t see how to do this off the top of my head (I’ve tried a few basic approaches that spiral off into nasty-land), but I have a vague recollection that we were taught an algorithm like this in the Maths Tripos (Part 1B Optimization, IIRC).

Possible Counter-example:

7 people have paid the following amounts:

A = £5

B = £4

C = £3

D = £5

E = £21

F = £19

G = £13

Put this into your spreadsheet to check, but if the algorithm work I did in my above post is correct, then maximizing the squares gives you the following payments:

A->E £4

A->F £1

B->F £6

C->E £7

D->F £2

D->G £3

Square Sum: 115

However, here is a way of doing it in 5 transactions that has a lower sum of squares:

A->E £5

B->E £6

C->F £4

C->G £3

D->F £5

Square Sum: 111

Now I haven’t used your optimization program to check that that 154 is the largest square sum (so I would do that) but I’m pretty sure that the first example has maximised the squares.

I’m not going to cling on to the correctness of this plan too much, now that I know the problem is NP-complete, but in this particular example,

A->E 5

B->E 6

C->F 7

D->F 2

D->G 3

gets sum of squares of 123 and only 5 transactions.

Fun fact: the NP-hardness of the problem doesn’t directly cast doubt on the correctness of your conjectured algorithm. You’re trying to *maximize* a positive definite quadratic function; equivalently, what you’re minimizing is negative definite. This makes it *non-convex* quadratic programming, which is also NP-hard: http://en.wikipedia.org/wiki/Quadratic_programming#Complexity

I have written on a similar problem, although I tried to minimize the total amount of money being exchanged, rather than the number of transactions. In case you wanna take a look at it:

http://stochastix.wordpress.com/2009/06/20/optimal-account-balancing/

http://stochastix.wordpress.com/2009/07/28/optimal-account-balancing-ii/

I thought about that constraint, but it seemed unsatisfactory. Incidentally don’t you find that the linear program ends up with the total transaction cost:

?