0
$\begingroup$

I'm working on a game where there are several different entities represented by nodes. Each node has a starting balance, and directed edges show where money is owed from one account to another.

One problem I'm trying to figure out is which order to process transactions in, take this example below:

Initial balances and amounts owed

If you start by processing node 'B', because there is no balance, the \$30 is not transferred to node C. Node A only receives \$20 instead of \$50, bringing the balance to \$50. 'A' can't afford to pay both D and B, so depending on which is paid first the result is different. If D is paid first the balance goes up to \$80. The remaining \$20 goes to B. Then B also receives \$80. The final graph is:

One possible final result

Is there an algorithm for solving situations like this? Is this related to network flow graphs or is that something different? I'm trying to figure out what problem class this is.

$\endgroup$
5
  • $\begingroup$ It's not clear what your question is. Is your question whether or not it is possible to pay all the debt? What happens when A owes 20 to B but only has 10? Does B receive 10, with A still owing 10? $\endgroup$
    – Pål GD
    Oct 28 at 11:05
  • 1
    $\begingroup$ Let $v_A$ be the money A has, let $L^-_A$ be all incoming links to $A$ and $L^+_A$ be all outgoing links from A. Then if you for each person X let $t_X = v_X + \sum L^-_X - \sum L^+_X$, then you have the surplus/deficit for each player. If all values are non-negative, then it is possible to pay off all debts. $\endgroup$
    – Pål GD
    Oct 28 at 11:09
  • 1
    $\begingroup$ What happens if you have a cycle $A {{1}\over{\rightarrow}} B {{1}\over{\rightarrow}} C {{1}\over{\rightarrow}} A$ and everyone's balance is 0? $\endgroup$
    – Pål GD
    Oct 28 at 11:18
  • 1
    $\begingroup$ If you find a cycle with bottleneck value $b$ (i.e. the smallest value of the cycle), can we then deduct $b$ from all edges of that cycle, or do you demand that each player actually pays that money? $\endgroup$
    – Pål GD
    Oct 28 at 11:20
  • $\begingroup$ The above question also stands wrt transitivity, if $A {1 \over \rightarrow} B {1 \over \rightarrow} C$, can we shortcut it to $A {1 \over \rightarrow} C$ instead? $\endgroup$
    – Pål GD
    Oct 28 at 18:20

1 Answer 1

2
$\begingroup$

Depending on your rules, here's a greedy algorithm:

Maintain a priority queue of all nodes where the value in the queue is how many debts they are able to pay down. Let the debt for each player be sorted by value.

Pop off a player $X$. If $X$ can pay, pop off the first debt. Then update the recipient's balance, and the number of debts they can pay off (binary search), and update the PQ. Then you push $X$ back onto the PQ with its updated count.

All in all, this should take $O(m \log m)$ time where $m$ is the number of debts.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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