Who owes who money optimization

Say you have n people, each who owe each other money. In general it should be possible to reduce the amount of transactions that need to take place. i.e. if X owes Y £4 and Y owes X £8, then Y only needs to pay X £4开发者_运维百科 (1 transaction instead of 2).

This becomes harder when X owes Y, but Y owes Z who owes X as well. I can see that you can easily calculate one particular cycle. It helps for me when I think of it as a fully connected graph, with the edges being the amount each person owes.

Problem seems to be NP-complete, but what kind of optimisation algorithm could I make, nevertheless, to reduce the total amount of transactions? Doesn't have to be that efficient, as N is quite small for me.

Edit:

The purpose of this problem would be to be able to have in the accounting system something that can say to each person when they log in "You can remove M amount of transactions by simply paying someone X amount, and someone else Y amount". Hence the bank solution (though optimal if everyone is paying at the same time) cannot really be used here.

Are people required to clear their debts by paying somebody that they actually owe money to personally? If not, the following seems to work suspiciously easily:

For each person, work out the net amount they should pay, or should receive.

Have somebody who owes money net pay somebody who should receive money net min(amount owed, amount to be received). After this, at least one of the two participants owes nothing and should receive nothing, and so can be removed from the problem.

Assuming I have missed something, what are the constraints that apply (or gross error made)?

I have created an Android app which solves this problem. You can input expenses during the trip, it even recommends you "who should pay next". At the end it calculates "who should send how much to whom". My algorithm calculates minimum required number of transactions and you can setup "transaction tolerance" which can reduce transactions even further (you don't care about $1 transactions) Try it out, it's called Settle Up:

https://market.android.com/details?id=cz.destil.settleup

Description of my algorithm:

I have basic algorithm which solves the problem with n-1 transactions, but it's not optimal. It works like this: From payments, I compute balance for each member. Balance is what he paid minus what he should pay. I sort members according to balance increasingly. Then I always take the poorest and richest and transaction is made. At least one of them ends up with zero balance and is excluded from further calculations. With this, number of transactions cannot be worse than n-1. It also minimizes amount of money in transactions. But it's not optimal, because it doesn't detect subgroups which can settle up internally.

Finding subgroups which can settle up internally is hard. I solve it by generating all combinations of members and checking if sum of balances in subgroup equals zero. I start with 2-pairs, then 3-pairs ... (n-1)pairs. Implementations of combination generators are available. When I find a subgroup, I calculate transactions in the subgroup using basic algorithm described above. For every found subgroup, one transaction is spared.

The solution is optimal, but complexity increases to O(n!). This looks terrible but the trick is there will be just small number of members in reality. I have tested it on Nexus One (1 Ghz procesor) and the results are: until 10 members: <100 ms, 15 members: 1 s, 18 members: 8 s, 20 members: 55 s. So until 18 members the execution time is fine. Workaround for >15 members can be to use just the basic algorithm (it's fast and correct, but not optimal).

Source code:

Source code is available inside a report about algorithm written in Czech. Source code is at the end and it's in English:

http://settleup.destil.cz/report.pdf

Nominate one person arbitrarily to be the banker.

Each other person transfers the sum of all the outgoing transactions minus the incoming transactions (so either deposits or withdraws) to that person.

There will be a maximum of (n-1) transactions, which is pretty small. It is fast. It is simple.

Given that everyone who transfers money will have to be involved in a transaction anyway*, it is bounded to be at worst twice the optimal case.**

* The exception is the banker themselves. A quick optimisation is to ensure the nominated banker is not someone who holds a neutral position.

** Explaining my upper bound logic further:

Suppose the optimal case is A gives $1 to B, and C gives $1 to D, and E is neutral = two transactions.

Then with this logic, if E is the nominated banker, A gives $1 to E, E gives $1 to B, C gives $1 to E and E gives $1 to D = four transactions.

With the optimisation, making sure you don't choose a neutral person for banker, select A instead. A gives $1 to B, C gives $1 to A. A gives $1 to D = three transactions.

for each debt in debts
  debt.creditor.owed -= debt.amount
  debt.deptor.owed += debt.amount
end

for each person in persons
  if person.owed > 0 then
    deptors.add person
  else if person.owed < 0 then
    creditors.add person
  end
end

deptors.sort_by_owed_desc
creditor.sort_by_owed_asc

for each debtor in deptors
  while debtor.owed > 0
    creditor = creditors.top
    amount = min( debtor.owed, -creditor.owed)
    creditor.owed += amount
    debtor.owed -= amount
    if creditor.owed == 0 then
      creditors.remove_top
    end
    write debtor.name " owes " creditor.name " " amount "€"
  end
end

Just thinking about it I'd start by looking at each cycle in the directed graph and reducing each edge in the cycle by the value of the minimum edge in the cycle, then remove the minimum edge altogether. Rinse and repeat.

Here's the Python solution I used; it's the same idea as Gunner's post, with a few line changes:

for i in N:
    for j in N:
        if i!=j and owes[i][j] > owes[j][i]:
            owes[i][j] -= owes[j][i]
            owes[j][i] = 0
for k in N:
    for i in N:
        for j in N:
            if k == i or i == j or k == j:
                continue
            if owes[j][k] > owes[i][j]:
                owes[i][k] += owes[i][j]
                owes[j][k] -= owes[i][j]
                owes[i][j] = 0;

Works a treat.

You can test it with i.e.:

owes = [[0,2,11], [4,0,7], [2,3,0]]
N = range(len(owes))

I think you need to build a different data structure ( a tree, each time one person is the root node) that will check for each person how many "transaction" can you "kill", than, choose the best one, make the cycle, and rebuild it again.it is not o(N), I Think it's N^2 though, and it will not give you the best result. it is just a strategy.

This problem may be tackled with the Warshall algorithm.

for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    if ( i!= j && owes[i][j] > owes[j][i] )
owes[i][j] -= (owes[i][j] - owes[j][i]), owes[j][i] = 0;

for(k=0;k<n;k++)
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
  {
if( k == i || i == j || k == j ) continue;
if ( owes[j][k] > owes[i][j] )
{
int diff = owes[j][k] - owes[i][j]; 
owes[i][j] = 0;
owes[i][k ] += diff;
owes[j][k] -= diff;
} 
}

After the algorithm finishes, the total number of transactions required would be the number of positive entries in the owes table.

I have not verified yet whether the algorithm will work, based on nature of the problem it may work. Solution is O(N^3).

I think you must remove all cicles reducing edges by minimal edge value and removingedges with value 0. After it you will get graph withouth cicles. I think you must find vertexes, wich have no pointers to them (man's wich owes only others money). This man's must pay money, beacouse there is no one to pay the money for them. So my point is that you must find somehow who they must pay.

I have a solution to the problem written in matlab. It is based on a matrix of who owes who what. The number in the (i,j) means that person j owes person i the number. E.g.

B owes A 2 and A owes B 1

of course in this case it is trivial that B should just give A 1

This becomes more complex with more entries. However, with the algorithm i wrote i can guarantee that no more than N-1 transactions occurs where N is the number of persones 2 in this case.

Here is the code i wrote.

function out = whooweswho(matrix)
%input sanitation
if ~isposintscalar(matrix)
    [N M] = size(matrix);
    if N ~= M
        error('Matrix must be square');
    end

    for i=1:N
        if matrix(N,N) ~= 0
            error('Matrix must have zero on diagonals');
        end
    end
else
    %construction of example matrix if input is a positive scalar
    disp('scalar input: Showing example of NxN matrix randomly filled');
    N = matrix;
    matrix = round(10*N*rand(N,N)).*(ones(N,N)-eye(N))
end

%construction of vector containing each persons balance
net = zeros(N,1);
for i=1:N
  net(i) = sum(matrix(i,:))-sum(matrix(:,i));
end

%zero matrix, so it can be used for the result
matrix = zeros(size(matrix));

%sum(net) == 0 always as no money dissappears. So if min(net) == 0 it
%implies that all balances are zero and we are done.
while min(net) ~= 0
  %find the poorest and the richest.
  [rec_amount reciever] = max(net);
  [give_amount giver] = min(net);
  %balance so at least one of them gets zero balance.
  amount =min(abs(rec_amount),abs(give_amount));
  net(reciever) = net(reciever) - amount;
  net(giver) = net(giver) + amount;
  %store result in matrix.
  matrix(reciever,giver) = amount;
end
%output equivalent matrix of input just reduced.
out = matrix;

end