Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If you have a group of people who purchase items together and split the costs (not always evenly). How can you calculate the most efficient number of transactions required to settle outstanding debt.

For example.

A may owe B £10, and B may owe C £10. Therefore A should pay C directly.

But this may be spread over many transactions and between many people.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

EDIT: After I wrote the following paragraphs, I realized that there is a more obvious way to see that $n-1$ transactions suffice. The proof is by induction and the base case $n=1$ is trivial. If $n-1$ transactions suffice for $n$ people, then given $n+1$ people, the first person can pick any other person, and by making a transaction with that person, either pay the total of what he owes or be paid the total of what he is owed, as appropriate. Then the inductive hypothesis says that the other $n$ people can settle with $n-1$ transactions, for a total of $n$ transactions.

Original answer: Let $n$ be the number of people. Then $n-1$ is an upper bound on the numbers of transactions required to settle all debts, and in the "typical" case no smaller number of transactions suffices. To see this, we may assume that the people numbered $1,\ldots,k$ are net debtors and the people numbered $k+1,\ldots,n$ are net creditors. Let $K$ be the sum of the net liabilities of the people numbered $1,\ldots,k$. We may assume that $K$ is an integer by working in terms of the least monetary unit.

First we choose a partition $P_L$ of $K$ into $k$ pieces, each piece corresponding to the net liability of one of the people numbered $1,\ldots,k$. Next we choose a second partition $P_A$ of $K$ into $N-k$ pieces, each piece corresponding to the net assets of one of the people numbered $k+1,\ldots,n$. The common refinement $P$ generated by $P_L$ and $P_A$ has at most $n-1$ pieces, and each piece corresponds to a transfer from one of the people numbered $1,\ldots,k$ to one of the people numbered $k+1,\ldots,n$.

Moreover, any optimal way of settling the debt does not involve transfers to net debtors or from net creditors, so it arises from some such pair of partitions $(P_L,P_A)$. The choices of $P_L$ and $P_A$ (really just the choice of $P_L$ given $P_A$ or vice versa) may affect the number of pieces in the common refinement $P$ that they generate. However, if we assume that the amount of each debt is chosen randomly, then for a fixed $n$, as $K$ grows the probability that some choice of partitions makes $|P| < n-1$ approaches zero. (This only happens when the total debts of some proper subset of the debtors sum to exactly the same amount as the total assets of some proper subset of the creditors.)

share|improve this answer
add comment

I get the feeling that I may be not seeing the question the right way - if so, let me know and I'll delete the answer. But, if we introduce an intermediate step, wouldn't the answer always be one?

All the people who net owe money to others could put what they owe in a big pile. All of the people who are net owed money could then take what they are owed.

In your example, A has a net debt of 10. B is flat, net. C has 10 coming to him, net. So A puts down 10, B does nothing, and C picks up 10. If instead B owed C 20 instead of 10, then B would also put 10 into the pile. Then C would pick up 20.

share|improve this answer
    
Even if you introduce the pot (which we can think of as an $(n+1)$-st person in a neutral position) I don't think that counts as a single transaction in total, although it is true that each person (except the pot) only participates in a single transaction. –  Trevor Wilson Dec 22 '12 at 5:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.