Splitting Up: The Problem

Suppose you go out to share a meal with a bunch of friends. When the bill arrives, everybody puts different amounts of cash into a central pot, depending on what they have on them.

Assume there are N people, and the total bill is $B. Suppose the amounts pitched in are \(y_1, y_2, ... y_N\), so that \[y_1 + y_2 + ... + y_N = B.\] For concreteness assume that there are 4 friends, who contribute $15, $20, $1, and $4 to pay off a total bill of B = $40. Note 15 + 20 + 1 + 4 = $40.

We can create a list of net credit/debit by subtracting $B/N from each of the contributions. Thus, we set, \(x_i = y_i - B/N\). Note that \[x_1 + x_2 + ... + x_N = 0.\] In the case of our concrete example, we get a list $5, $10, -$9, -$6, which adds to zero.

The problem is to take such a list of numbers, and come up with a list of "binary" transactions transactions, so that the accounts are settled.

We want to try to do this while minimizing the total number of transactions.

In our concrete example, we could settle accounts with the following three transactions:

Person 4 -> Person 1: $5
Person 4 -> Person 2: $1
Person 3 -> Person 2: $9.

The solution is clearly not unique. For example, another possible solution with 3 transactions is:

Person 3 -> Person 1: $5
Person 3 -> Person 2: $4
Person 4 -> Person 2: $6.

Exemptions: Let me throw in an additional wrinkle, which is a common occurrence.

Suppose some of people "exempted" from certain costs. This could happen for all sorts of reasons. For example:

• You have one or two birthday boys/girls, who you don't want to take contributions from
• Some of you may order drinks. You may want to separate the "drinks" portion from the rest of the meal
• Same thing with vegetarian/non-vegetarian
• Etc.

So in addition to the contributions \(y_i\), suppose each person is exempt from a portion \(e_i\) of the total bill.

In our particular example, suppose Person 3 was exempt from $16 of the total bill (perhaps because he was a teetotaler and vegetarian), and Person 4 was exempt from $10 of the total bill (only vegetarian). Thus, a list of names, contributions (y), and exemptions (e), may look like:

Person1, $15, $0
Person2, $20, $0
Person3, $1, $16
Person4, $4, $10

Generating the set of \(\mathbf{x} = x_i\) from \(\mathbf{y} = y_i\) and \(\mathbf{e} = e_i\) is somewhat nontrivial. It can be obtained using the following algorithm:

1. initialize xi = 0, and n = N.
2. set the cost basis, fi = B - ei, for i = 1, 2, ..., n
3. sort fi from largest (f1) to smallest (fn)
4. let xi = xi + fn/n, for i = 1, 2, ..., n
5. let fi = fi - fn, for i = 1, 2, ..., n
6. reset n = number of nonzero fi
7. repeat steps 4 through 6, until n = 0.
8. set xi = yi - xi

For this problem,

Iteration 1:

1. n = 4

2 and 3. fi = {40, 40, 30, 24}, [note: names = {Person1, Person2, Person4, Person3}]

4. xi = {6, 6, 6, 6}

5. fi = {16, 16, 6, 0}

6. n = 3

Iteration 2:

4. xi = {8, 8, 8, 6}

5. fi = {10, 10, 0, 0}

6. n = 2

Iteration 3:

4. xi = {13, 13, 8, 6}

5. fi = {0, 0, 0, 0}

6. n = 0

Outside the loop, the net contributions are:

8. xi = {2, 7, -4, -5}

Note that the list of persons associated with the amounts has changed to {Person1, Person2, Person4, Person3}.