Minimum transactions to settle debts among friends

Question

You are given $n$ integers $x_1,x_2,\dots,x_n$ satisfying $\sum_{i=1}^n x_i=0$. A legal move is to choose an integer $a$ and two indices $i,j$, and to increase $x_i$ by $a$ and decrease $x_j$ by $a$. The goal is to have $x_1=x_2=\dots=x_n=0$.

What is an algorithm which achieves this goal in the fewest number of moves?

There is an algorithm which always takes $n-1$ moves; at the $i^{th}$ step, decrease $x_i$ by $x_i$ and increase $x_{i+1}$ by $x_i$. This is not always optimal, because if half of the $x_i$ equal $1$ and the other half equal $-1$, then $n/2$ moves suffice.

The motivation for this problem is the situation where $n$ friends have gone out to dinner, and have all contributed some amount of money bill, and now want to make it so they have all payed an equal amount.

Answer 1

Suppose we have some minimum size set of payments, then I claim the resulting (undirected!) payment graph is always a forest. Indeed, suppose the graph has a cycle, then we can adjust all the payments on this cycle by $\pm 1$ until one of the edges becomes a payment of $0$ and disappears. We can use this procedure to find an optimal way to resolve any $S \subseteq [n]$ with $\sum_{i\in S} x_i = 0$ using $|S|-1$ payments.

Clearly then, an optimal solution will partition $[n]$ into subsets $S_1,\dots,S_k$ such that $\sum_{i\in S_j} x_i = 0$ for all $1\leq j \leq k$ and resolve each subset using $|S_j|-1$ payments. In other words, the optimal solution has value $n - k$ where $[n] = S_1 \cup \dots \cup S_k$ is the largest decomposition into subsets summing to $0$.

However, note that if $S_1$ and $S_2$ sum to $0$, then so does $S_1 \cup S_2$, so equivalently we may find a maximum length chain $\emptyset \neq S_1 \subseteq \dots \subseteq S_k = [n]$ and resolve all sets $S_{i+1} \setminus S_i$ individually using $|S_{i+1} \setminus S_i|-1$ payments. We can find such a maximum length chain in $O(n2^n)$ time by precomputing for every subset $S \subseteq [n]$ the value $s(S) = \sum_{i\in S} x_i$ and then just using the recurrence:

$$b(S) = \begin{cases} 0 & \text{if $S = \emptyset$} \\ 1 + \max_{u\in S} b(S\setminus\{u\}) & \text{if $s(S) = 0$} \\ 0 + \max_{u\in S} b(S\setminus\{u\}) & \text{if $s(S) \neq 0$} \\ \end{cases} $$

This is again $O(n2^n)$ time. As was pointed out in the other answer we are unlikely to find a polynomial time algorithm.

Answer 2

Unfortunately, in this unbalanced world is hard to achieve equality even among friends. Namely, for this problem exists no polynomial algorithm unless $\mathcal{ P=NP}$, see below.

Put $[n]= \{1,\dots, n\}.$

Propositon. The goal can be achieved in less then $n-1$ moves iff there is a proper subset $S$ of $[n]$ such that $\sum_{i\in S} x_i=0$.

Proof. ($\Leftarrow$) If there exists such a set $S$ then we can annulate all $x_i$ with $i\in S$ by $|S|-1$ moves, and all $x_i$ with $i\in [n]\setminus S$ by $|[n]\setminus S |-1$ moves. Thus we can achieve the goal in at most $|S|-1+|[n]\setminus S |-1=n-2$ moves in total.

($\Rightarrow$) Assume that the friends can annulate all $x_i$ using $k<n-1$ moves. Consider a graph $G$ with the set $[n]$ of vertices such that the vertices $i$ and $j$ are adjacent by an edge of weight $a$ iff there was a pay of $a$ between $i$-th and $j$-th friend. Since the graph $G$ has less than $n-1$ edges, it has at least two connected components. Clearly, $\sum_{i\in S} x_i=0$ for each component $S$. $\square$

At last we remark that it is NP-hard to decide whether there exists a proper subset $S$ of $[n]$ such that $\sum_{i\in S} x_i=0$, because this problem is equivalent to Subset sum problem, which is NP-hard. Indeed, given integers $x_1,\dots, x_{n-1}$ and $x_n=-\sum_{i\in [n-1]} x_i$, there exists a subset $S$ of $[n-1]$ such that $\sum_{i\in S} x_i=0$ iff there exists a proper subset $S’$ of $[n]$ such that $\sum_{i\in S’} x_i=0$.