Suppose three persons have contributed to the expenses of a trip: Adam has paid for the hotel, $150, Bob pays the gas, $60, and Charlie provides the food, $120. After the trip they want to balance the expenses.
The easy solution is that each expense is split between the three persons and individually paid by the other participants to the one that purchased the good in the first place.
Naturally, if Adam owes $20 to Bob and Bob owes $50 to Adam, it's equivalent to Bob owing $30 to Adam. Continuing this logic, Bob owes $30 to Adam and $20 to Charlie, and Charlie owes $10 to Adam.
Here's the catch: this solution is not optimal. The number of transactions can be reduced. There is an amount of $10 that is first paid from Bob to Charlie and then from Charlie to Adam. Instead, Bob could add that $10 to the sum he is already paying to Adam.
In the end, Bob pays $10 to Charlie and $40 to Adam. Everyone has now covered the expenses with an equal amount of $110.
My questions are:
When the goal is to find the way the expensens are balanced with the absolute minimum amount of transactions, what is the general solution to this problem with n actors? Traversing the paths from the most owing to the most owed can become computationally expensive, so it's not trivial.
Can an NP-complete problem be reduced to this problem?
Is there a well-known name for this problem?
Say c people have paid more than their share (creditors), and d people less than their share (debtors). Since as per your definition, a solution is optimal if it implies a minimum number of transactions, the ideal case is that every debtor needs to make only a single transfer (they obviously have to make at least one). The question is then, can X1, the money owed to creditor 1, be obtained by an exact sum of amounts owed? Can X2 be obtained by an exact sum of remaining amounts? And so on until Xc. In that sense the problem is related to the subset sum problem, as stated (a bit tersely) by n.m..