Algorithm to simplify a weighted oriented debt schedule

Question

I used a small python script that I wrote to manage debt among my roommates. This works, but there are some missing features, one of which simplifies overly complex debt structures. For example, if the following weighted oriented graph represents some people, and the arrows represent debts between them (Alice owes Bob $ 20 and Charlie $ 5, Bob owes Charlie $ 10, etc.):

It is clear that this graph should be simplified to the following graph:

It makes no sense at $ 10, starting from Alice to Bob, and then from Bob to Charlie, if Alice can just transfer it to Charlie directly.

In general, the goal is to take a debt graph and simplify it (i.e. create a new graph with the same nodes, but with different edges), so

• No node has edges indicating both inside and outside (without useless money changes)
• All nodes have the same “flow” through them, as in the original chart (it is identical in terms where the money ends).

By "flow" is meant the value of all inputs minus all outputs (is there a technical term for this? I'm not an expert on graph theory). Thus, in the above example, the stream values ​​for each node:

• Bob: +10
• Alice: -25
• Charlie: +15

You can see that the first and second graphs have the same stream through each node, so this is a good solution. There are other simple cases, for example, any cycle can be simplified by removing the least significant edge and subtracting its value from all other edges.

It:

should be simplified:

I cannot imagine that no one has studied this problem; I just don’t know what conditions to look for in order to find information about this (again, not an expert on graph theory). I searched for several hours to no avail, so my question is: what is an algorithm that will lead to simplification (new graph) in accordance with the conditions indicated above for any weighted oriented graph?

Answer 1

Simple algorithm

In O (n) you can find how much money is waiting or will pay. Thus, you can simply create two lists: one for debit and one for credit, and then balance the heading of the two lists until they are empty. In the first example:

• Initial state: Debit: (A: 25), Credit: (B: 15, C: 10)
• First transaction, A: 15 → B: Debit: (A: 10), Credit: (C: 10)
• The second transaction, A: 10 → C: Debit :(), Credit :()

Operations define the boundaries of your schedule. For n persons involved, there will be no more than n-1 transactions = edges. Initially, the total length of both lists is n. At each step, at least one of the lists (debit / credit) becomes shorter by one, and in the last, both lists disappear immediately.

The problem is that, in general, this graph should not be similar to the original graph, which, as I understand it, is a requirement. (Is this? There are times when the optimal solution consists of adding new edges. Imagine that A and B and B have the same amount, A must pay C directly, but this edge is not in the debt schedule.)

Less transaction

If the goal is to build an equivalent schedule, you can search for lists of creditors and debtors (as indicated in the section above) for exact matches or for cases where the loan amount matches the debit of one person (or bypass). Find a package of beans . In other cases, you will have no choice but to split the streams, but even the simple algorithm above creates a graph that has fewer edges than there are people involved - at most.

EDIT . Thanks to j_random_hacker for indicating that a solution with edges less than n-1 is possible if there is a group of people whose total debt corresponds to a loan of another group of people: Then, the problem can be divided into two subtasks with a total cost of n-2 edges for the transaction schedule. Unfortunately, the problem of summing a subset is NP-hard.

Flow problem?

Perhaps this can also be converted into a min-cost flow problem. If you just want to simplify your initial schedule, you create a stream on it, the maximum capacity is the original amount of debits / credits. Debtors serve as an inflow (through a node connector that serves all debtors with capacity edges equal to their total debt), lenders are used as outflow nodes (with a similar node connector).

If you want to minimize the number of transactions, you will prefer to keep the "large" transactions and reduce the "small" ones. Therefore, the cost of each edge can be modeled as the inverse of the flow on that edge.

Answer 2

Here is an academic article that explores this issue in great detail. At the end of 8, a code example for various algorithms is given in Section 8.

Verhoff, T. (2004). Effective settlement of several debts: an invitation to computer science. Computer Science in Education, 3 (1), 105-126.

Answer 3

I really ran into this problem in the same situation as you :)

I think that any krlmlr solution does not completely solve the problem. I'll think about how to solve it exactly (in terms of minimal boundaries), but at the same time, a practical alternative solution to your problem is to come up with a new person, Steve :

• Steve is not really a man. Steve is just a bucket with a sheet of paper attached to it.
• Each calculates the net amount they owe (or is due, if negative), and writes it on a piece of paper along with their name.
• Anyone whose net position is that they owe money, gives this net amount to Steve when they can, and crosses his name.
• Everyone whose pure position is that they owe money takes this money from Steve when they see that Steve has it and crosses out their name.

If the person who owes money cannot pay all this at once, they can simply give Steve what they can afford and withdraw this amount from the total amount against their name. Similarly, if you owe more money than Steve currently has, you can take all the money he currently has and withdraw that amount from the total amount against your name.

If everyone agrees to pay only the full amount to Steve from the very beginning, then each net-ower makes exactly one deposit, and each net player makes exactly one conclusion (although it may take several checks to check to see that there is currently enough cash ) The good thing about Steve is that he is always there and never too busy to figure out finances. Unfortunately, he is very gullible, so Alice, Bob and Charlie need to trust each other so as not to use it.