24

I am looking forward for an algorithm for the below problem.

Problem: There will be a set of people who owe each other some money or none. Now, I need an algorithm (the best and neat) to settle expense among this group.

Person AmtSpent
------ ---------
A       400  
B      1000  
C       100  
Total  1500

Now, expense per person is 1500/3 = 500. Meaning B to give A 100. B to give C 400. I know, I can start with the least spent amount and work forward.

Can some one point me the best one if you have.

To sum up,

  1. Find the total expense, and expense per head.
  2. Find the amount each owe or outstanding (-ve denote outstanding).
  3. Start with the least +ve amount. Allocate it to the -ve amount.
  4. Keep repeating step 3, until you run out of -ve amount.
    s. Move to next bigger +ve number. Keep repeating 3 & 4 until there are +ve numbers.

Or is there any better way to do?

7
  • Well.. I am just curious to settle my expenses with my bunch of friends.. Just acting smart to do something other than excel. No homework anyway. :)
    – Guru
    Jun 10, 2009 at 11:31
  • 4
    If by "better", you mean "fewer net payments", then it is only possible to the extent that a possibility exists for a deficit (or surplus) to be broken apart such that its parts EXACTLY match some group of surpluses (or deficits). But as granularity of payments increases (pennies rather than dollars), the likelihood of this approaches nil, and your described solution is optimal.
    – user447688
    Jun 10, 2009 at 11:41
  • Lets assume that each or few spend some amount and the total amount is shared among them equally. So, it has to part EXACTLY. Fewer payments is better. Anything else need to take into consideration?
    – Guru
    Jun 10, 2009 at 11:53
  • That's not what I mean by "part exactly"; of course, amount owed will always equal amount owing. What I mean is, e.g., with mean expenditure 500, C spent 432.85, owing 67.15. By lucky coincidence, F and G are owed exactly 67.15 in total. If you're only dealing in small integer values, these sub-optimizations are more likely; with high granularity in the values, they are much less so.
    – user447688
    Jun 10, 2009 at 15:20
  • 1
    and now have splitwise and settleup.
    – Lord Nick
    Aug 16, 2018 at 5:07

10 Answers 10

12

The best way to get back to zero state (minimum number of transactions) was covered in this question here.

2
  • That's a good solution (suggeested by "Pax "). The problem with me is, I am not going to limit the users to three. And solution suggested by "jwoolard" is very much as the one pointed already. I will be happy adopting this. :)
    – Guru
    Jun 10, 2009 at 12:00
  • Just be aware that this it's not an easy undertaking to get the absolute minimum - you basically have to look at the entire search space. The accepted answer in that other question will give you a very good answer but there are edge conditions which will mean it's not the minimum (I called it the best in terms of bang-per-buck).
    – paxdiablo
    Jun 10, 2009 at 12:17
10

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:

https://web.archive.org/web/20190214205754/http://www.settleup.info/files/master-thesis-david-vavra.pdf

7
  • +1. really interesting. It appears to be promising. I once built a appspot on Python (did not complete it successfully). So, you used which method? which algorithm? the double entry book keeping?
    – Guru
    Apr 23, 2011 at 17:25
  • It actually started as my semester project for class. So I had to "invent" the algorithm. It's quite hard to search for existing solutions, because I don't know the terms. Do you have some suggestions for further research? Apr 25, 2011 at 20:41
  • Description of my algorithm: I have for each member his balance (plus or minus). I have basic algorithm which solves it with N-1 transactions: order members according to balance and the the one with lowest balance sends money to next one and so on. This algorithm can be improved - I try to find two-pairs of people who settle up just with one transaction. Then I search for triples from the rest and so on. With each of these subgroups I use the basic algorithm. But transactions are spared. So worst-case is N-1 transactions, but usually less. Apr 25, 2011 at 20:49
  • thanks for the explanation, Destil. I have moved the comment to your answer about for easy reading. All the best.
    – Guru
    Apr 26, 2011 at 20:25
  • Hi, eventually I have changed the algorithm, because the previous one generated transactions with more money than it was needed. I have improved the description in my post. I have also attached link to the full source code. May 3, 2011 at 9:05
6

You have described it already. Sum all the expenses (1500 in your case), divide by number of people sharing the expense (500). For each individual, deduct the contributions that person made from the individual share (for person A, deduct 400 from 500). The result is the net that person "owes" to the central pool. If the number is negative for any person, the central pool "owes" the person.

Because you have already described the solution, I don't know what you are asking. Maybe you are trying to resolve the problem without the central pool, the "bank"?

I also don't know what you mean by "start with the least spent amount and work forward."

2
  • 2
    I think he means sorting first by amount spent can minimize the number of payment transactions, although that's not specified as a requirement
    – user447688
    Jun 10, 2009 at 11:15
  • I thought there would be some other better way to do so. To sum up, 1. Find the total expense, and expense per head. 2. Find the amount each owe or outstanding (-ve denote outstanding). 3. Start with the least +ve amount. Allocate it to the -ve amount. 4. Keep repeating step 3, until you run out of -ve amounts. Move to next bigger +ve number. Or is there any better way to do? I am just curious. :)
    – Guru
    Jun 10, 2009 at 11:28
3

Javascript solution to the accepted algorithm:

const payments = {
  John: 400,
  Jane: 1000,
  Bob: 100,
  Dave: 900,
};

function splitPayments(payments) {
  const people = Object.keys(payments);
  const valuesPaid = Object.values(payments);

  const sum = valuesPaid.reduce((acc, curr) => curr + acc);
  const mean = sum / people.length;

  const sortedPeople = people.sort((personA, personB) => payments[personA] - payments[personB]);
  const sortedValuesPaid = sortedPeople.map((person) => payments[person] - mean);

  let i = 0;
  let j = sortedPeople.length - 1;
  let debt;

  while (i < j) {
    debt = Math.min(-(sortedValuesPaid[i]), sortedValuesPaid[j]);
    sortedValuesPaid[i] += debt;
    sortedValuesPaid[j] -= debt;

    console.log(`${sortedPeople[i]} owes ${sortedPeople[j]} $${debt}`);

    if (sortedValuesPaid[i] === 0) {
      i++;
    }

    if (sortedValuesPaid[j] === 0) {
      j--;
    }
  }
}

splitPayments(payments);

/*
  C owes B $400
  C owes D $100
  A owes D $200
*/

1
  • 1
    Can you provide an explanation?
    – jhpratt
    Sep 13, 2018 at 1:43
2

I have recently written a blog post describing an approach to solve the settlement of expenses between members of a group where potentially everybody owes everybody else, such that the number of payments needed to settle the debts is the least possible. It uses a linear programming formulation. I also show an example using a tiny R package that implements the solution.

0
2

I had to do this after a trip with my friends, here's a python3 version:

import numpy as np
import pandas as pd

# setup inputs
people = ["Athos", "Porthos", "Aramis"]   # friends names
totals = [300, 150, 90]  # total spent per friend

# compute matrix
total_spent = np.array(totals).reshape(-1,1)
share = total_spent / len(totals)
mat = (share.T - share).clip(min=0) 

# create a readable dataframe
column_labels = [f"to_{person}" for person in people] 
index_labels = [f"{person}_owes" for person in people]
df = pd.DataFrame(data=mat, columns=column_labels, index=index_labels)
df.round(2)

Returns this dataframe:

to_Athos to_Porthos to_Aramis
Athos_owes 0 0 0
Porthos_owes 50 0 0
Aramis_owes 70 20 0

Read it like: "Porthos owes $50 to Athos" ....

This isn't the optimized version, this is the simple version, but it's simple code and may work in many situations.

1

I'd like to make a suggestion to change the core parameters, from a UX-standpoint if you don't mind terribly.

Whether its services or products being expensed amongst a group, sometimes these things can be shared. For example, an appetizer, or private/semi-private sessions at a conference.

For things like an appetizer party tray, it's sort of implied that everyone has access but not necessarily that everyone had it. To charge each person to split the expense when say, only 30% of the people partook can cause contention when it comes to splitting the bill. Other groups of people might not care at all. So from an algorithm standpoint, you need to first decide which of these three choices will be used, probably per-expense:

Universally split
Split by those who partook, evenly
Split by proportion per-partaker

I personally prefer the second one in-general because it has the utility to handle whole-expense-ownership for expenses only used by one person, some of the people, and the whole group too. It also remedies the ethical question of proportional differences with a blanket generalization of, if you partook, you're paying an even split regardless of how much you actually personally had. As a social element, I would consider someone who had a "small sample" of something just to try it and then decided not to have anymore as a justification to remove that person from the people splitting the expense.

So, small-sampling != partaking ;)

Then you take each expense and iterate through the group of who partook in what, and atomically handle each of those items, and at the end provide a total per-person.

So in the end, you take your list of expenses and iterate through them with each person. At the end of the individual expense check, you take the people who partook and apply an even split of that expense to each person, and update each person's current split of the bill.

Pardon the pseudo-code:

list_of_expenses[] = getExpenseList()
list_of_agents_to_charge[] = getParticipantList()

for each expense in list_of_expenses
    list_of_partakers[] = getPartakerList(expense)
    for each partaker in list_of_partakers
       addChargeToAgent(expense.price / list_of_partakers.size, list_of_agents_to_charge[partaker])

Then just iterate through your list_of_agents_to_charge[] and report each total to each agent.

You can add support for a tip by simply treating the tip like an additional expense to your list of expenses.

1
  • 1
    Thanks, its quite amazing that this is still interesting and inspires one to build application. I thought this was a settled problem.
    – Guru
    Sep 13, 2018 at 3:20
0

Straightforward, as you do in your text:

Returns expenses to be payed by everybody in the original array. Negativ values: this person gets some back

Just hand whatever you owe to the next in line and then drop out. If you get some, just wait for the second round. When done, reverse the whole thing. After these two round everybody has payed the same amount.

procedure SettleDepth(Expenses: array of double);
var
  i: Integer;
  s: double;
begin
  //Sum all amounts and divide by number of people
  // O(n) 
  s := 0.0;
  for i := Low(Expenses) to High(Expenses) do
     s := s + Expenses[i];

  s := s / (High(Expenses) - Low(Expenses));

  // Inplace Change to owed amount
  // and hand on what you owe
  // drop out if your even 
  for i := High(Expenses) downto Low(Expenses)+1 do begin
     Expenses[i] := s - Expenses[i];
     if (Expenses[i] > 0) then begin
        Expenses[i-1] := Expenses[i-1] + Expenses[i];
        Expenses.Delete(i);
     end else if (Expenses[i] = 0) then begin
        Expenses.Delete(i);
     end;
  end;

  Expenses[Low(Expenses)] := s - Expenses[Low(Expenses)];
  if (Expenses[Low(Expenses)] = 0) then begin
     Expenses.Delete(Low(Expenses));
  end;

  // hand on what you owe
  for i := Low(Expenses) to High(Expenses)-1 do begin
     if (Expenses[i] > 0) then begin
        Expenses[i+1] := Expenses[i+1] + Expenses[i];
     end;
  end;
end;  
0

The idea (similar to what is asked but with a twist/using a bit of ledger concept) is to use Pool Account where for each bill, members either pay to the Pool or get from the Pool. e.g. in below attached image, the Costco expenses are paid by Mr P and needs $93.76 from Pool and other members pay $46.88 to the pool.

enter image description here

0

There are obviously better ways to do it. But that would require running a NP time complexity algorithm which could really show down your application. Anyways, this is how I implemented the solution in java for my android application using Priority Queues:

class calculateTransactions {
public static void calculateBalances(debtors,creditors) {
// add members who are owed money to debtors priority queue
// add members who owe money to others to creditors priority queue
}

public static void calculateTransactions() {
    results.clear(); // remove previously calculated transactions before calculating again
    PriorityQueue<Balance> debtors = new PriorityQueue<>(members.size(),new BalanceComparator()); // debtors are members of the group who are owed money, balance comparator defined for max priority queue
    PriorityQueue<Balance> creditors = new PriorityQueue<>(members.size(),new BalanceComparator()); // creditors are members who have to pay money to the group

    calculateBalances(debtors,creditors);

    /*Algorithm: Pick the largest element from debtors and the largest from creditors. Ex: If debtors = {4,3} and creditors={2,7}, pick 4 as the largest debtor and 7 as the largest creditor.
    * Now, do a transaction between them. The debtor with a balance of 4 receives $4 from the creditor with a balance of 7 and hence, the debtor is eliminated from further
    * transactions. Repeat the same thing until and unless there are no creditors and debtors.
    *
    * The priority queues help us find the largest creditor and debtor in constant time. However, adding/removing a member takes O(log n) time to perform it.
    * Optimisation: This algorithm produces correct results but the no of transactions is not minimum. To minimize it, we could use the subset sum algorithm which is a NP problem.
    * The use of a NP solution could really slow down the app! */
    while(!creditors.isEmpty() && !debtors.isEmpty()) {
        Balance rich = creditors.peek(); // get the largest creditor
        Balance poor = debtors.peek(); // get the largest debtor
        if(rich == null || poor == null) {
            return;
        }
        String richName = rich.name;
        BigDecimal richBalance = rich.balance;
        creditors.remove(rich); // remove the creditor from the queue

        String poorName = poor.name;
        BigDecimal poorBalance = poor.balance;
        debtors.remove(poor); // remove the debtor from the queue

        BigDecimal min = richBalance.min(poorBalance);

        // calculate the amount to be send from creditor to debtor
        richBalance = richBalance.subtract(min);
        poorBalance = poorBalance.subtract(min);

        HashMap<String,Object> values = new HashMap<>(); // record the transaction details in a HashMap
        values.put("sender",richName);
        values.put("recipient",poorName);
        values.put("amount",currency.charAt(5) + min.toString());

        results.add(values);

        // Consider a member as settled if he has an outstanding balance between 0.00 and 0.49 else add him to the queue again
        int compare = 1;
        if(poorBalance.compareTo(new BigDecimal("0.49")) == compare) {
            // if the debtor is not yet settled(has a balance between 0.49 and inf) add him to the priority queue again so that he is available for further transactions to settle up his debts
            debtors.add(new Balance(poorBalance,poorName));
        }

        if(richBalance.compareTo(new BigDecimal("0.49")) == compare) {
            // if the creditor is not yet settled(has a balance between 0.49 and inf) add him to the priority queue again so that he is available for further transactions
            creditors.add(new Balance(richBalance,richName));
        }
    }
}
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.