Settling debts after shared expenses effectively: max 1 transaction per person

Question

Context

I'm creating a program to simplify sharing expenses between people. An expense has:

• a payer who initially paid for the expense
• some number of contributors, who will pay a share of the expense (note that the payer is also a contributor)

The shares that the contributors have to pay for a certain expense do not necessarily have to be equal. After some arbitrary number of expenses, some people will be owed money, while other people owe money.

Problem

The problem is to find an easy way for all the people to settle their debts. Instead of some people having to pay several others, and some people not having to pay anyone at all, I want one person to have to pay at most one other. Furthermore, I would like to minimize the excess amount of money a person receives beyond what he or she actually is owed. For instance, if you are owed $100, you don't really want to receive $2000, and have to forward $1900 to somebody else.

Model

Every person has a debt. The debt is:

• positive if the person owes money
• negative if the person is being owed money
• zero, if neither of the above

So, the model consists of a collection of numbers, representing debts.

This is a zero-sum situation: The amount of money people owes is equal to the amount of money people are being owed (there can't be a loan without a lender). This means that regardless of who receives a payment, if everyone at the end have paid what they owed, nobody is being owed any money.

Anne pays Bob $100. If Anne had a debt of 100, her debt is now 0. If Bob had a debt of -100, his debt is also 0. In the model, a transaction of money is equivalent to subtracting from the payer's debt, and adding the same amount to the recipient's.

In order to minimize the excess of money the recipient in a transaction receives, I'm thinking that it should be sufficient to add the largest positive debt to the largest negative debt for each transaction.

Implementation

I'm thinking about using a min-heap for the negative debts and a max-heap for the positive debts. Then repeatedly perform a transaction from the largest in max to the smallest in min. This can be done by increasing the key of min by the value of max, and removing max. If a debt is zero, remove it from the heap.

Pseudocode

Let max be the largest element of maxHeap and min the smallest element of minHeap. max.person and min.person is the person who holds the debt of max and min respectively.

while(not done) do:
    new transaction.from(max.person).to(min.person)
    if(max + min = 0) then:               //remove both
        maxHeap.removeMax
        minHeap.removeMin
    else if (max + min < 0) then:         //keep in minHeap
        minHeap.increaseKey(min).by(max)
        maxHeap.removeMax
    else                                  //move min to maxHeap
        maxHeap.decreaseKey(max).by(|min|)

This should give me a run time of O(nlogn), if I am not mistaken.

Question

Is my reasoning correct? Will my solution give fairly good results as per my problem description? Does anyone else have a faster and/or more simple solution, that still upholding the criteria of as little excess money as possible received?

Note: In case it matters any, I'm going to implement it in Java

EDIT: I found another question quite similar to this: Algorithm to share/settle expenses among a group. However, it does not solve my problem, as I have the criteria of maximum one transaction for each person.

Answer 1

I have edited the answer to also cater for the situation where one recipient may receive money from multiple persons, not only from a single one. See downmost.

---

Interesting problem - had to code it. Pseudo and data here, as made with Dyalog APL.

Often the only way to be sure of the optimum is to use brute force. For your problem, this works well when the number of participants is ca 12 or less:

┌──┬──┬──┬──┬───┬───┬─────┬──────┬───────┬─────────┬──────────┬───────────┬─────────────┬──────────────┬─────────────────┐
│!1│!2│!3│!4│!5 │!6 │!7   │!8    │!9     │!10      │!11       │!12        │!13          │!14           │!15              │
├──┼──┼──┼──┼───┼───┼─────┼──────┼───────┼─────────┼──────────┼───────────┼─────────────┼──────────────┼─────────────────┤
│1 │2 │6 │24│120│720│5,040│40,320│362,880│3,628,800│39,916,800│479,001,600│6,227,020,800│87,178,291,200│1,307,674,368,000│
└──┴──┴──┴──┴───┴───┴─────┴──────┴───────┴─────────┴──────────┴───────────┴─────────────┴──────────────┴─────────────────┘

As we see, the factorial of numbers increase rapidly. If 10 participants, it's still a reasonable 3.6 million, 12 guys is already 1/2 billion. Probably not worth considering much more than that.

If however we talk about sufficiently small gangs, it is rather trivial (except for one thing) to do the calculation.

You have set this condition:

The shares that the contributors have to pay for a certain expense do not necessarily have to be equal.

That doesn't change the calculation itself, but i leave outside this answer how the shares were concluded. You must have a way to determine what belongs to whom. The essential for the calculation here is that the sums of what should be payed and what was payed are equal.

Consider this example:

We have 4 guys who have consumed for 400 bucks. One guy payed it all and they have decided to share the cost equally:

┌──────────┬───┬───┬───┬───┬─────┐
│Guy       │1  │2  │3  │4  │Total│
├──────────┼───┼───┼───┼───┼─────┤
│Should pay│100│100│100│100│400  │
├──────────┼───┼───┼───┼───┼─────┤
│Payed     │0  │0  │0  │400│400  │
└──────────┴───┴───┴───┴───┴─────┘

As guy #1 has payed 0, he apparently needs to pay an additional 100, etc. This is a simple case. The only solution is:

    1 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬──────┬──────┬──────┬──────┬─────┬────────┐
│Guy #                    │1     │2     │3     │4     │Total│Turnover│
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Should pay               │100   │100   │100   │100   │400  │        │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Has paid                 │0     │0     │0     │400   │400  │        │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Gets from the one to left│0.00  │100.00│200.00│300.00│     │600     │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Pays to the one to right │100.00│200.00│300.00│0.00  │     │600     │
└─────────────────────────┴──────┴──────┴──────┴──────┴─────┴────────┘

Note that the table wraps - leftmost and rightmost are "neighbours".

We see that each almost guy does a payment to his right neighbour column in the table, and similarly gets one from his left neighbour. When adding what he originally payed, what he gets now, and what he pays now, he ends up in the correct total expense, as assigned to him.

However, if #2 payed 100 and #4 payed 300:

┌──────────┬───┬───┬───┬───┬─────┐
│Guy       │1  │2  │3  │4  │Total│
├──────────┼───┼───┼───┼───┼─────┤
│Should pay│100│100│100│100│400  │
├──────────┼───┼───┼───┼───┼─────┤
│Payed     │0  │100│0  │300│400  │
└──────────┴───┴───┴───┴───┴─────┘

we get 3 solutions, below the best one:

3 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬──────┬──────┬──────┬────┬─────┬────────┐
│Guy #                    │1     │3     │4     │2   │Total│Turnover│
├─────────────────────────┼──────┼──────┼──────┼────┼─────┼────────┤
│Should pay               │100   │100   │100   │100 │400  │        │
├─────────────────────────┼──────┼──────┼──────┼────┼─────┼────────┤
│Has paid                 │0     │0     │300   │100 │400  │        │
├─────────────────────────┼──────┼──────┼──────┼────┼─────┼────────┤
│Gets from the one to left│0.00  │100.00│200.00│0.00│     │300     │
├─────────────────────────┼──────┼──────┼──────┼────┼─────┼────────┤
│Pays to the one to right │100.00│200.00│0.00  │0.00│     │300     │
└─────────────────────────┴──────┴──────┴──────┴────┴─────┴────────┘

and the worst one:

Worst solution:
┌─────────────────────────┬──────┬──────┬──────┬──────┬─────┬────────┐
│Guy #                    │1     │2     │4     │3     │Total│Turnover│
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Should pay               │100   │100   │100   │100   │400  │        │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Has paid                 │0     │100   │300   │0     │400  │        │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Gets from the one to left│100.00│200.00│200.00│0.00  │     │500     │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Pays to the one to right │200.00│200.00│0.00  │100.00│     │500     │
└─────────────────────────┴──────┴──────┴──────┴──────┴─────┴────────┘

The above is worse, because the total turnover when settling the payments is bigger. You had this criterion:

I would like to minimize the excess amount of money a person receives beyond what he or she actually is owed.

This seems to be possible in most cases, but i doubt there exists any guarantee for that.

Now consider this situation:

┌──────────┬──┬──┬──┬──┬──┬──┬──┬──┬─────┐
│Guy       │1 │2 │3 │4 │5 │6 │7 │8 │Total│
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Should pay│10│10│10│10│10│10│10│10│80   │
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Payed     │0 │0 │0 │0 │0 │0 │0 │80│80   │
└──────────┴──┴──┴──┴──┴──┴──┴──┴──┴─────┘

The optimal (and only) solution is:

1 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬────────┐
│Guy #                    │1    │2    │3    │4    │5    │6    │7    │8    │Total│Turnover│
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼────────┤
│Should pay               │10   │10   │10   │10   │10   │10   │10   │10   │80   │        │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼────────┤
│Has paid                 │0    │0    │0    │0    │0    │0    │0    │80   │80   │        │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼────────┤
│Gets from the one to left│0.00 │10.00│20.00│30.00│40.00│50.00│60.00│70.00│     │280     │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼────────┤
│Pays to the one to right │10.00│20.00│30.00│40.00│50.00│60.00│70.00│0.00 │     │280     │
└─────────────────────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴────────┘

We see that the payment sums increase. Even though #7 only has a debt of 10, he receives 60 and pays 70. The reason is that all other guys must accumulate/build up a sum that is sufficient enough, to pay to #8. As the criterion was that #8 (and each other individual too) can only receive money from one other guy, not from multiple.

Now consider a more complex one - each made their own choice from the menu. Some paid for their own food, and #8 took care of the payment for #1, #3, #5, #7 and himself:

┌──────────┬──┬──┬──┬──┬──┬──┬──┬──┬─────┐
│Guy       │1 │2 │3 │4 │5 │6 │7 │8 │Total│
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Should pay│10│25│12│18│16│10│18│15│124  │
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Payed     │0 │25│0 │18│0 │10│0 │71│124  │
└──────────┴──┴──┴──┴──┴──┴──┴──┴──┴─────┘

The result is pretty good. Those who payed for themselves are untouched:

97 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬─────┬─────┬─────┬─────┬─────┬────┬────┬────┬─────┬────────┐
│Guy #                    │1    │3    │5    │7    │8    │2   │4   │6   │Total│Turnover│
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Should pay               │10   │12   │16   │18   │15   │25  │18  │10  │124  │        │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Has paid                 │0    │0    │0    │0    │71   │25  │18  │10  │124  │        │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Gets from the one to left│0.00 │10.00│22.00│38.00│56.00│0.00│0.00│0.00│     │126     │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Pays to the one to right │10.00│22.00│38.00│56.00│0.00 │0.00│0.00│0.00│     │126     │
└─────────────────────────┴─────┴─────┴─────┴─────┴─────┴────┴────┴────┴─────┴────────┘

Then a case where apparently the good guys emptied all pockets and got the 124 bucks paid:

┌──────────┬──┬──┬──┬──┬──┬──┬──┬──┬─────┐
│Guy       │1 │2 │3 │4 │5 │6 │7 │8 │Total│
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Should pay│10│25│12│18│16│10│18│15│124  │
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Payed     │17│20│10│19│10│20│16│12│124  │
└──────────┴──┴──┴──┴──┴──┴──┴──┴──┴─────┘

Pretty good! No big money to move:

67 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬────┬────┬────┬────┬─────┬─────┬────┬────┬─────┬────────┐
│Guy #                    │1   │3   │4   │8   │5    │6    │7   │2   │Total│Turnover│
├─────────────────────────┼────┼────┼────┼────┼─────┼─────┼────┼────┼─────┼────────┤
│Should pay               │10  │12  │18  │15  │16   │10   │18  │25  │124  │        │
├─────────────────────────┼────┼────┼────┼────┼─────┼─────┼────┼────┼─────┼────────┤
│Has paid                 │17  │10  │19  │12  │10   │20   │16  │20  │124  │        │
├─────────────────────────┼────┼────┼────┼────┼─────┼─────┼────┼────┼─────┼────────┤
│Gets from the one to left│7.00│0.00│2.00│1.00│4.00 │10.00│0.00│2.00│     │26      │
├─────────────────────────┼────┼────┼────┼────┼─────┼─────┼────┼────┼─────┼────────┤
│Pays to the one to right │0.00│2.00│1.00│4.00│10.00│0.00 │2.00│7.00│     │26      │
└─────────────────────────┴────┴────┴────┴────┴─────┴─────┴────┴────┴─────┴────────┘

And finally a case where all have paid an equal sum, but the obligation to pay differently was later resolved: should pay equally but have paid differently:

┌──────────┬──┬──┬──┬──┬──┬──┬──┬──┬─────┐
│Guy       │1 │2 │3 │4 │5 │6 │7 │8 │Total│
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Should pay│10│10│10│10│10│10│10│10│80   │
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Payed     │7 │20│10│5 │10│10│6 │12│80   │
└──────────┴──┴──┴──┴──┴──┴──┴──┴──┴─────┘

Tiny turnover:

54 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬────┬────┬────┬─────┬─────┬────┬────┬────┬─────┬────────┐
│Guy #                    │1   │8   │7   │4    │2    │3   │5   │6   │Total│Turnover│
├─────────────────────────┼────┼────┼────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Should pay               │10  │10  │10  │10   │10   │10  │10  │10  │80   │        │
├─────────────────────────┼────┼────┼────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Has paid                 │7   │12  │6   │5    │20   │10  │10  │10  │80   │        │
├─────────────────────────┼────┼────┼────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Gets from the one to left│0.00│3.00│1.00│5.00 │10.00│0.00│0.00│0.00│     │19      │
├─────────────────────────┼────┼────┼────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Pays to the one to right │3.00│1.00│5.00│10.00│0.00 │0.00│0.00│0.00│     │19      │
└─────────────────────────┴────┴────┴────┴─────┴─────┴────┴────┴────┴─────┴────────┘

How to do this calculation

As we do it by brute force, it means generating all permutaions of the number of participants. This may be the tricky part. As an example, all permutations of (1,2,3,4) are below (written column-wise, to increase readability):

1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4
2 2 3 3 4 4 1 1 3 3 4 4 1 1 2 2 4 4 1 1 2 2 3 3
3 4 2 4 2 3 3 4 1 4 1 3 2 4 1 4 1 2 2 3 1 3 1 2
4 3 4 2 3 2 4 3 4 1 3 1 4 2 4 1 2 1 3 2 3 1 2 1

You better do a search for this generation. It's ok if it happens in a loop. The essential is that you can access one column at time (or row, if they are row-wise).

Pseudo:

// NOTE: The data is written as arrays
//       For example "0 0 0 0" implies a 4-element array (vector) of integers
//       Of course there may be other number of participants ("guys"),
//        then we need "other-element" arrays, for example 7-element ones
//       The code below may require additional looping

ToPay = 100 100 100 100 // Topmost example in this answer
HasPayed = 0 0 0 400 // Ditto

// Calculate debt
// This probably requires a loop from 1...4
Debt[n] = ToPay[n] - HasPayed[n] // Debt is now: 100 100 100 -300

smallest = 9999999 // Sufficiently big initial value

:For Row :In [each permutation of (1 2 3 4) // Row is now for example: 2 4 3 1
    Test = Debt[Row] // Test is now for example: 100 -300 100 100
    Accu = [4-element vector of zeroes]
    Accu[1] = Row[1]
    minimum = Row[1]
    s = 2
    :Repeat
        Accu[s] = Accu[s-1] + Row[s]
        minimum = min(minimum, Accu[s]) // We simply grab the smalles element in Accu
        s += 1
    :Until (s > 4)
    // As this is ready, Accu may contain eg. 100 -200 -100 0
    //  and minimum would then contain -200
    sum = 0
    t = 1
    :Repeat
        Accu[t] -= minimum
        sum += Accu[t]
        t += 1
    :Until (t > 4) 
    // When ready, Accu would be eg. 300 0 100 200
    //  and sum would be 300+0+100+200, ie. 600
    :If (sum < smallest)
        [store Row as best so far, for example into "BestRow"]
        [store Accu, for example into BestAccu"]
        smallest = sum
    :End
:End

Now

• BestRow contains the order in which a guy pays another (from left to right), for example 1 2 3 4 (= 1 pays 2, 2 pays 3, 3 pays 4, 4 pays 1).
• BestAccu contains the sum to pay to the guy to right, for example 100 200 300 0.

One may apply other criteria for the "best way", but this solution minimises the amount of money "moved around" AND keeps the transactions to one payment per person.

Also to note, there are multiple "best solutions", where one permutation produces the same minimum turnover as another perumtation. For the last example, number of equally good solutions were (best to worst) were:

48  96  144  144  240  240  480  336  672  432  768  912  960  768  1296  864  1392  1104  1200  1056  1488  1488  1488  1200  1344  1152  1776  1056  1344  1056  1152  1152  1344  768  1104  768  1056  720  912  480  672  528  528  240  576  288  432  192  288  144  240  48  96  48 

... meaning 48 "best solutions", 96 "second best", etc.

---

Edit:

I was told of a criterion i had erratically assumed: That a person can only receive money from one other person. This was not the case, any person may give money to only one other person, but may receive money from none, one person or multiple persons.

It turns out that the solution given above was almost complete already. To resolve this new condition, one only needs to process the result a little more. Namely, the accumulations that now exist in the above logic, where multiple persons in a row may accumulate more and more money, while themselves contributing to the accumulation, in order to pay off to someone who did a big payment ("mister X") - this accumulation needs to be dismantled, so that the accumulative part of it is payed directly to X, instead of through other participants.

Consider this situation:

┌──────────┬──┬──┬──┬──┬──┬──┬─────┐
│Guy       │1 │2 │3 │4 │5 │6 │Total│
├──────────┼──┼──┼──┼──┼──┼──┼─────┤
│Should pay│10│10│20│30│10│20│100  │
├──────────┼──┼──┼──┼──┼──┼──┼─────┤
│Payed     │35│0 │25│0 │0 │40│100  │
└──────────┴──┴──┴──┴──┴──┴──┴─────┘

Although it looks simple, it's rather hard to resolve by head calculation, as it is circular. By earlier methods, we get the "accumulative" answer:

22 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬──┬──┬──┬──┬──┬──┬─────┬────────┐
│Guy #                    │1 │3 │2 │5 │6 │4 │Total│Turnover│
├─────────────────────────┼──┼──┼──┼──┼──┼──┼─────┼────────┤
│Should pay               │10│20│10│10│20│30│100  │        │
├─────────────────────────┼──┼──┼──┼──┼──┼──┼─────┼────────┤
│Has paid                 │35│25│0 │0 │40│0 │100  │        │
├─────────────────────────┼──┼──┼──┼──┼──┼──┼─────┼────────┤
│Gets from the one to left│30│5 │0 │10│20│0 │     │65      │
├─────────────────────────┼──┼──┼──┼──┼──┼──┼─────┼────────┤
│Pays to the one to right │5 │0 │10│20│0 │30│     │65      │
└─────────────────────────┴──┴──┴──┴──┴──┴──┴─────┴────────┘

Then we can resolve the debt for each one, it is the 2nd row - the 3rd row (debt is positive):

┌───┬──┬──┬──┬───┬──┐
│-25│-5│10│10│-20│30│
└───┴──┴──┴──┴───┴──┘

Using that, we can solve something called "accumulation - that's the 5th row - the debt:

┌──┬─┬─┬──┬──┬─┐
│30│5│0│10│20│0│
└──┴─┴─┴──┴──┴─┘

From that, we can resolve which payments may be changed from the "pay the guy to right" to a "pay guy #n" - this simply happens by comparing pairs of the accumulation, and comparing the last element of accumulation to the first (as this problem is circular). The first comparison is (30 < 5), then follows (5 < 0), then (0 < 10), etc; last one is (0 < 30):

┌─┬─┬─┬─┬─┬─┐
│0│0│1│1│0│1│
└─┴─┴─┴─┴─┴─┘

1 indicates that the next accumulation is bigger than the current one - these are the payments that can now be directed directly to #n.

Who is #n? #n is the next guy after a series of ones. Slot 3 and 4 (guys #2 and #5 in the first answer above) are followed by guy #6 - he is the one that #2 and #5 now pay to, while other payments remain untouched.

The coding of this is not very tricky, but is language dependant, so i'll leave that to the implementor. Just decrease the accumulations as you advance to right, within each group of ones, up to (and including) each zero after a group of ones, and re-address the payment. The answer is pretty:

┌──────────┬──┬──┬──┬──┬──┬──┐
│Guy       │1 │3 │2 │5 │6 │4 │
├──────────┼──┼──┼──┼──┼──┼──┤
│Should pay│10│20│10│10│20│30│
├──────────┼──┼──┼──┼──┼──┼──┤
│Payed     │35│25│0 │0 │40│0 │
├──────────┼──┼──┼──┼──┼──┼──┤
│Pays to   │3 │  │6 │6 │  │1 │
├──────────┼──┼──┼──┼──┼──┼──┤
│Amount    │5 │  │10│10│  │30│
└──────────┴──┴──┴──┴──┴──┴──┘

The answer is interesting, because guy #1, who was actually an "overpayer", has to pay 5 to guy #3. This happens because guy #4 (rightmost) has a debt of 30, that he must pay to one single other person - this causes an "overpayment" to #1, but as #1's neighbour #3 needs to get 5 from somewhere, #1 passes that to him. Then the rest fits perfectly, #6 gets his 20 from #2 and #5. The criterion was to minimise payments and find the best solution, right? :-)

Some examples (situation and solution). Below 2 equal payers:

 ┌──────────┬──┬──┬──┬─┬─┬──┬──┬──┬─────┐  ┌───────┬─┬─┬──┬──┬─┬─┬──┬──┐ 
 │Guy       │1 │2 │3 │4│5│6 │7 │8 │Total│  │Guy    │1│5│6 │8 │2│4│7 │3 │ 
 ├──────────┼──┼──┼──┼─┼─┼──┼──┼──┼─────┤  ├───────┼─┼─┼──┼──┼─┼─┼──┼──┤ 
 │Should pay│7 │11│13│8│5│10│12│14│80   │  │Pays to│ │2│2 │2 │ │1│1 │1 │ 
 ├──────────┼──┼──┼──┼─┼─┼──┼──┼──┼─────┤  ├───────┼─┼─┼──┼──┼─┼─┼──┼──┤ 
 │Payed     │40│40│0 │0│0│0 │0 │0 │80   │  │Amount │ │5│10│14│ │8│12│13│ 
 └──────────┴──┴──┴──┴─┴─┴──┴──┴──┴─────┘  └───────┴─┴─┴──┴──┴─┴─┴──┴──┘ 

One big and some small payers:

 ┌──────────┬──┬───┬──┬──┬──┬──┬──┬──┬──┬──┬─────┐  ┌───────┬─┬──┬──┬──┬──┬──┬──┬─┬──┬─┐ 
 │Guy       │1 │2  │3 │4 │5 │6 │7 │8 │9 │10│Total│  │Guy    │1│3 │7 │4 │10│6 │8 │2│5 │9│ 
 ├──────────┼──┼───┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤  ├───────┼─┼──┼──┼──┼──┼──┼──┼─┼──┼─┤ 
 │Should pay│10│10 │10│12│10│19│11│33│6 │12│133  │  │Pays to│2│2 │2 │2 │2 │2 │2 │ │9 │1│ 
 ├──────────┼──┼───┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤  ├───────┼─┼──┼──┼──┼──┼──┼──┼─┼──┼─┤ 
 │Payed     │5 │112│0 │0 │0 │1 │0 │0 │15│0 │133  │  │Amount │6│10│11│12│12│18│33│ │10│1│ 
 └──────────┴──┴───┴──┴──┴──┴──┴──┴──┴──┴──┴─────┘  └───────┴─┴──┴──┴──┴──┴──┴──┴─┴──┴─┘

Very irregular:

 ┌──────────┬──┬──┬──┬──┬──┬──┬──┬──┬─┬──┬─────┐  ┌───────┬──┬──┬─┬─┬─┬─┬─┬──┬──┬─┐ 
 │Guy       │1 │2 │3 │4 │5 │6 │7 │8 │9│10│Total│  │Guy    │1 │10│4│9│5│3│6│7 │8 │2│ 
 ├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─┼──┼─────┤  ├───────┼──┼──┼─┼─┼─┼─┼─┼──┼──┼─┤ 
 │Should pay│10│10│5 │12│10│19│11│33│6│12│128  │  │Pays to│10│  │9│5│3│ │2│2 │2 │ │ 
 ├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─┼──┼─────┤  ├───────┼──┼──┼─┼─┼─┼─┼─┼──┼──┼─┤ 
 │Payed     │7 │50│10│10│6 │12│1 │10│7│15│128  │  │Amount │3 │  │2│1│5│ │7│10│23│ │ 
 └──────────┴──┴──┴──┴──┴──┴──┴──┴──┴─┴──┴─────┘  └───────┴──┴──┴─┴─┴─┴─┴─┴──┴──┴─┘ 

As we see, the solution looks quite optimal.