What is the least number of payments to settle the score?

Question

Suppose $n$ guys go on holiday. Suppose their names are the numbers $1,\dots, n$.

Suppose that, at the end of the vacation, the guy $i$ has paid an amount of $a_i \geq 0$ for the entire group, which has thus to be divided by $n$. Thus the guy $i$ has to receive $\frac{a_i}{n}$ by everyone but he/she has to pay $\frac{a_1}{n}$ to $1$, $\dots$, $\frac{a_n}{n}$ to $n$. This is the trivial way to settle the score and the number of payments will be $n^2$. Obviously, it is not the most efficient. So the question is: what is the least number of payments that can make the guys pay off the debts? And what is the strategy associated with this number of payments?

Another assumption: assume that everyone has a bank account with infinite money in such a way anyone can pay any amount in any moment.

Answer 1

It's always possible in $n-1$ payments.

For convenience, let $a = \frac{a_1 + a_2 + \dots + a_n}{n}$: this is the "fair share" that everyone should be paying. Now, for $k=1, \dots, n-1$, have the $k^{\text{th}}$ person pay $a - a_k$ to the $n^{\text{th}}$ person if $a > a_k$, or have the $n^{\text{th}}$ person pay $a_k - a$ to the $k^{\text{th}}$ person if $a < a_k$. After this is done, the $k^{\text{th}}$ person has spent $a$ in net and has a settled balance.

By conservation of money, the $n^{\text{th}}$ person should also have a settled balance, and we can in fact check that the net amount spent by the $n^{\text{th}}$ person is $$ a_n - \sum_{k=1}^{n-1} (a - a_k) = -(n-1)a + \sum_{k=1}^n a_k = a. $$ So everyone is even.

---

It's possible to make fewer payments in some special cases, but those cases are hard to identify.

Let's draw an $n$-vertex graph where the vertices are people and an edge represents a payment. If only $n-k$ payments are made, then this graph will have at least $k$ connected components. However, if these $n-k$ payments are enough to solve the problem, this means that each connected component is "relatively" balanced: altogether, if there are $m$ people in the component, they have spent $ma$ on the vacation.

Conversely, if we can split up the people into $k$ groups such that each group is relatively balanced in this way, then there is a solution with $n-k$ payments: just apply the strategy at the beginning of this answer to each group.

However, finding these groups is hard in general. We can identify small groups of this type easily. The easiest is when the $i^{\text{th}}$ person has spent $a_i = a$; all such people can just go home without making any payments. But in general, finding even one of these groups is the subset sum problem, which is NP-complete. To solve it, we'd have to take a computationally intensive approach like the integer program in the other answer. In a real-life scenario, just making a few extra payments would be faster :)

Answer 2

You can solve the problem via mixed integer linear programming as follows. Define a complete directed graph on $n$ nodes, with supply $s_i=\frac{1}{n}\sum_j a_j - a_i$ for node $i$. Note that the total supply is $\sum_i s_i = 0$. For each arc $(i,j)$, let nonnegative decision variable $x_{ij}$ be the amount that $i$ pays $j$, and let binary decision variable $y_{ij}$ indicate whether $x_{ij}>0$. The ("network design") problem is to find a minimum cardinality set of arcs that support sending a net of $s_i$ units out of node $i$. That is, minimize $\sum_{i,j} y_{ij}$ subject to \begin{align} \sum_{j \not= i} \left(x_{ij} - x_{ji}\right) &= s_i &&\text{for all $i$} \tag1\label1\\ x_{ij} &\le \left(\sum_k a_k\right) y_{ij} &&\text{for all $i,j$} \tag2\label2\\ \end{align} Flow-balance constraint \eqref{1} enforces that each person pays the correct share. Big-M constraint \eqref{2} enforces the logical implication $x_{ij}>0 \implies y_{ij}=1$.

An easy lower bound on the optimal objective value is $$\max\left(\left|\left\{i: s_i > 0\right\}\right|,\left|\left\{i: s_i < 0\right\}\right|\right)$$ because each person who underpaid needs to make at least one transaction and each person who overpaid needs to make at least one transaction.