Settling Debts Efficiently: Zero-Sum Set Packing

Abstract

A common situation that arises in real life is the need to use peer-to-peer payment methods such as Venmo or Paypal to solve debts among a group of friends. Rather than sending each other money after every incurred expense, they can record all the debts on a spreadsheet, aggregating everyone's debt and credit over time. When it comes time to settle the debt, some people will have debt and owe money to the group, while other people will have credit and be owed money from the group. In this thesis, we try to explore the algorithmic problem of finding the minimum number of transactions necessary to settle all the debt among this group of friends. We prove that determining this minimum sequence of transactions to settle all the debt is NP-complete and discuss approximation algorithms for this problem. We also this problem to a special case of the famous set packing problem, and then show that this special case is just as hard to approximate as the general set packing problem. Finally, we explore an interesting variation of the debt settling problem where payments are only allowed between certain pairs of people and explore this problem's complexity for various classes of graphs.