Optimal Account Balancing

Suppose that Alice owes Bob $5 and is owed $10 by Bob. These debts can be represented as the weighted directed graph

which we will call an IOU graph. Alice pays Bob $5 and Bob pays Alice $10. The debts are paid and $15 have been exchanged in a total of two transactions. Let us now consider the following cash flow diagram

and, accounting for the net cash flows, we obtain

which illustrates that if Bob paid Alice $5, then the debts would still be paid, though only $5 would be exchanged and only one transaction would be made. This looks much cleverer and more efficient than exchanging $15 in a total of two transactions. Hence, the following IOU graph

is “equivalent” to the original IOU graph. In both IOU graphs, if debts are paid then Alice will be $5 up, while Bob will be $5 down.

We add a third agent, Charlie. Consider now the IOU graph

where:

Alice must pay a total of $20 and be paid a total of $30.

Bob must pay a total of $15 and be paid a total of $20.

Charlie must pay a total of $35 and be paid a total of $20.

Hence, after the debts are paid, Alice will have $30 – $20 = $10 more in her account, Bob will have $20 – $15 = $5 more in his account, and Charlie will have $20 – $35 = -$15 more (= $15 less) in his account. Note that $10 + $5 – $15 = $0, i.e., money is conserved. In total, $70 have been exchanged in six transactions. We can do better than that. For example, we could pay all debts in just three transactions, as illustrated in the following IOU graph

where a total of $20 are exchanged. Note that Alice is $10 up, Bob is $5 up, and Charlie is $15 down, just like before. We can do even better than this. If Charlie pays Bob’s debt to Alice, then all debts can be paid in just two transactions as shown in the IOU graph below

where only $15 are exchanged. This is an “optimal” debt-paying scheme because the debts cannot be paid in less than two transactions, nor exchanging less than $15. Do you agree?

__________

Debts and IOU Graphs

An IOU graph is a weighted directed graph given by an ordered triple $\mathcal{G} = (\mathcal{N}, \mathcal{E}, w)$ , where:

$\mathcal{N}$ is the node set. Each node of the IOU graph represents a different agent.

$\mathcal{E} \subset \mathcal{N} \times \mathcal{N}$ is the edge set. Each directed edge is an ordered pair $(i,j)$ , where $i$ is the edge’s tail and $j$ is the edge’s head. If $(i,j) \in \mathcal{E}$ then node $i$ owes money to node $j$ . We do not allow nodes to owe money to themselves and, therefore, for each $i \in \mathcal{N}$ we must have $(i,i) \notin \mathcal{E}$ .

$w: \mathcal{E} \rightarrow \mathbb{R}^{+}$ is a weight function that assigns positive weights to each edge in $\mathcal{E}$ . The weight of edge $(i, j) \in \mathcal{E}$ is given by $w\left( (i, j) \right) > 0$ , and it tells us the amount of money that node $i$ owes to node $j$ .

We define the in-neighborhood and out-neighborhood of node $i$ as follows

$\begin{array}{ll} \mathcal{N}_i^{in} &= \displaystyle\{ j \in \mathcal{N} \mid (j,i) \in \mathcal{E}\}\\\\ \mathcal{N}_i^{out} &= \displaystyle\{ j \in \mathcal{N} \mid (i,j) \in \mathcal{E}\}\end{array}$

and illustrate them below

The divergence [1] of node $i$ of graph $\mathcal{G}$ is a scalar defined as

$\textbf{div}_i (\mathcal{G}) = \displaystyle \sum_{j \in \mathcal{N}_i^{out}} x_{ij} - \displaystyle \sum_{j \in \mathcal{N}_i^{in}} x_{ji}$

and it gives us the amount of money node $i$ owes to other nodes minus the amount of money node $i$ is owed to by other nodes. The divergence of a node can be viewed as the discrete, graph-theoretic analogue of the divergence operator in vector calculus. We define also the divergence vector of graph $\mathcal{G}$ as the vector whose $i$ -th component is $\textbf{div}_i (\mathcal{G})$

$\textbf{div} (\mathcal{G}) = \left[\begin{array}{c} \vdots\\ \textbf{div}_i (\mathcal{G})\\ \vdots \\ \end{array}\right]$ .

The divergence vector of an IOU graph $\mathcal{G}$ tells us how much money each node in the graph will lose after debts have been paid. We say that two IOU graphs (on the same node set) are equi-divergent if their divergence vectors are the same. This means that, although the debt relationships are different, both IOU graphs result in every node getting paid what he is owed and paying what he owes.

__________

Optimal Account Balancing

Suppose we are given an IOU graph $\mathcal{G}_0 = (\mathcal{N}, \mathcal{E}_0, w_0)$ . We would like to find a new IOU graph $\mathcal{G} = (\mathcal{N}, \mathcal{E}, w)$ on the same node set $\mathcal{N}$ , such that the two IOU graphs are equi-divergent

$\textbf{div} (\mathcal{G}) = \textbf{div} (\mathcal{G}_0)$ .

Moreover, we would like the new IOU graph to be “optimal” in some sense. I can think of the two following optimality criteria:

minimum money flow: we want to minimize the total amount of money being exchanged between the nodes. This is the same as minimizing the sum of the (positive) weights of the edges of the IOU graph.

least number of transactions: we want to minimize the total number of transactions being made. This is the same as minimizing the number of edges in the IOU graph, i.e., maximizing the sparsity of the IOU graph.

Can you think of other interesting optimality criteria?

It would be reasonable to consider the case where the transaction fees are nonzero. If these are variable and proportional to the amount of money being transferred, then we would like to minimize the amount of money flowing in the network of agents. If the transaction fees are fixed, then we would like to minimize the total number of transactions being made. For example, in the two examples above the minimum money flow solution is the same as the least number of transactions solution. Is this always the case?

In order to find the optimal IOU graph, we start with a weighted directed graph on node set $\mathcal{N}$ whose edge set is the one of the directed complete graph on $\mathcal{N}$ . Hence, every two distinct nodes are connected by two directed edges with opposite directions. The weight of edge $(i,j)$ is denoted by $x_{ij} \geq 0$ . Since some of these weights might be zero, there might be edges in this graph which do not represent debt relationships! Therefore, although this graph is weighted and directed, it is not necessarily an IOU graph. We optimize for the $n (n-1)$ nonnegative variables $\{x_{ij}\}$ and, in the end, we remove the edges whose weight is zero so that we obtain an IOU graph. I view this approach as somewhat akin to scaffolding ;-)

For example, considering the minimum money flow criterion, we have the following minimum cost flow problem [1]

$\begin{array}{ll} \text{minimize} & \displaystyle \sum_{i \in \mathcal{N}}\sum_{j \neq i} x_{ij}\\\\ \text{subject to} & \displaystyle \sum_{j \neq i} x_{ij} - \displaystyle \sum_{j \neq i} x_{ji} = \textbf{div}_i (\mathcal{G}_0), \quad{} \forall i \in \mathcal{N}\\\\ & x_{ij} \geq 0, \quad{} \forall i \neq j \in \mathcal{N}\\\\\end{array}$

which can be solved via linear programming [2]. In words: we want to find the debts $x_{ij} \geq 0$ such that all debts are paid (each node should be paid what it is owed minus what it owes to other nodes) and the total amount of debt is minimized, which results in the total amount of money flowing to be also minimized.

The least number of transactions criterion is much harder to tackle because we want to maximize the sparsity of the graph, while ensuring that the graph and the original IOU graph equi-divergent. We want to optimize the topology of the graph and, hence, a combinatorial flavor is added to the problem. I will write more about it on future posts.

__________

A Numerical Example

Let us again consider the $3$ -agent example where the agents are Alice, Bob and Charlie. The IOU graph is

where the node set is $\mathcal{N} = \{\text{a}, \text{b}, \text{c}\}$ . We introduce vector

$x = (x_{ab}, x_{ac}, x_{ba}, x_{bc}, x_{ca}, x_{cb})$

where $x_{ij} \geq 0$ is the amount of money node $i$ owes to node $j$ . The divergence of the new graph at each node must be the same as the divergence of the given IOU graph at each node, which yields the equality constraint $C x = b$ , where

$C = \left[\begin{array}{rrrrrr} -1 & -1 & 1 & 0 & 1 & 0\\ 1 & 0 & -1 & -1 & 0 & 1\\ 0 & 1 & 0 & 1 & -1 & -1\\\end{array}\right]$

is the incidence matrix of the graph, and $b = [\begin{array}{ccc} 10 & 5 & -15\end{array}]^T$ is the opposite of the divergence vector of the given IOU graph above. This equality constraint guarantees that the given IOU graph and the new graph we obtain are equi-divergent.

Let $I_6$ be the $6 \times 6$ identity matrix, let $1_6$ be the $6$ -dimensional vector of ones, and let $0_6$ be the $6$ -dimensional vector of zeros. The $6$ nonnegativity constraints $x_{ij} \geq 0$ can be written in matrix form as $(-I_6) x \leq 0_6$ . Considering the minimum money flow criterion, we obtain the linear program

$\begin{array}{ll} \text{minimize} & 1_6^T x\\\\ \text{subject to} & C x = b, \quad{} (-I_6) x \leq 0_6\\\\\end{array}$

Note that the equality constraint $C x = b$ is equivalent to two inequality constraints: $C x \leq b$ and $C x \geq b$ . Thus, we can transform the linear program above into a linear program with inequality constraints only

$\begin{array}{ll} \text{minimize} & 1_6^T x\\\\ \text{subject to} & \left[\begin{array}{r} C\\ -C\\ -I_6\\\end{array}\right] x \leq \left[\begin{array}{r} b\\ -b\\ 0_6\\\end{array}\right]\\\\\end{array}$

If you have MATLAB, you can easily solve these linear programs using function linprog. The following Python 2.5 script solves the latter linear program using CVXOPT:

from cvxopt import matrix
from cvxopt import solvers

# -------------------
# auxiliary matrices
# -------------------

# defines incidence matrix
C = matrix([ [-1.0, 1.0, 0.0],
             [-1.0, 0.0, 1.0],
             [1.0, -1.0, 0.0],
             [0.0, -1.0, 1.0],
             [1.0, 0.0, -1.0],
             [0.0, 1.0, -1.0] ])

# defines desired divergence vector
d = matrix( [-10.0, -5.0, 15.0] )

# defines 6x6 identity matrix
Id = matrix([ [1, 0, 0, 0, 0, 0],
              [0, 1, 0, 0, 0, 0],
              [0, 0, 1, 0, 0, 0],
              [0, 0, 0, 1, 0, 0],
              [0, 0, 0, 0, 1, 0],
              [0, 0, 0, 0, 0, 1] ])

# ---------------
# linear program
# ---------------

# defines objective vector
c = matrix(1.0, (6,1))

# defines inequality constraint matrices
G = matrix( [C, -C, -Id] )
h = matrix( [-d, d, matrix(0.0, (6,1))] )

# solves linear program
solvers.options['show_progress'] = True
solution = solvers.lp(c, G, h)

# prints solution
print solution['x']

The solution is

$x = \left[\begin{array}{r}5.86\text{e-}008\\ -1.50\text{e-}008\\ -1.36\text{e-}008\\ -1.99\text{e-}008\\ 1.00\text{e+}001\\ 5.00\text{e+}000\\\end{array}\right]$ ,

which is “contaminated” with numerical noise. Adjusting the tolerances of the numerical solver, one can reduce the numerical noise and obtain the true solution, which is $x = (0, 0, 0, 0, 10, 5)$ . Removing the edges with zero weight, we obtain an IOU graph with 2 edges

and, hence, only two transactions are required, and only $15 need to be exchanged. This is the exact same solution we obtained previously via heuristic methods! :-)

__________

Concluding Remarks

The two optimal debt-paying schemes considered on this post rely on an “accountant” who has perfect global information about all the debts in the network of agents. This accountant solves an optimization problem to find out what transactions should be carried out. This is a centralized approach, as the decision power is centralized in the accountant. Another (and arguably more interesting) approach would be a decentralized one, where the nodes have only local information (i.e., each node only knows who owes him money and to whom he owes money) and where each node solves a local optimization problem using, for example, message-passing algorithms. I will write about it on future posts.

The only modeling of this problem I have found was on Demetri Spanos‘ PhD thesis [3]. If you know of any papers on this topic, please let me know.

Last but not least, allow me to add a personal note: I first started thinking of this problem years ago, while going to dinners with friends and trying to figure out how to split the bill in an efficient manner. The real world is a great source of inspiration when it comes to interesting problems.

__________

References

[1] Dimitri Bertsekas, Network Optimization: Continuous and Discrete Models, Athena Scientific, 1998.

[2] Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

[3] Demetri Spanos, Distributed gradient systems and dynamic coordination, Ph.D. thesis, California Institute of Technology, December 2005.

Tags: Accounting, CVXOPT, IOU Graphs, Linear Programming, Operations Research

This entry was posted on June 20, 2009 at 19:38 and is filed under Accounting, Operations Research, Python. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

21 Responses to “Optimal Account Balancing”

Sune Kristian Jakobsen Says:
June 20, 2009 at 23:45 | Reply
Do you know any examples of IOU’s that doesn’t have a solution, that minimize number of transactions and money flow at the same time?
- Rod Carvalho Says:
  June 21, 2009 at 21:05 | Reply
  Hej Sune! Velkommen tilbage! :-)
  
  I believe all IOU graphs have a “solution”. Of course, we need to define what we mean by “solution”. Suppose I give you an IOU graph. You should be able to come up with another IOU graph which is equi-divergent to the one I gave you. If there are no IOU graphs which are equi-divergent to the one I gave you, then the one I gave you is “optimal” already.
  
  For instance, suppose I give you an IOU graph which has at least one pair of nodes connected by two directed edges with different directions. Let us call such nodes $i$ and $j$ , and let us suppose that the weights of these edges are $x_{ij} > 0$ and $x_{ji} > 0$ . Suppose that $x_{ij} > x_{ji}$ , then a naive improvement would be to replace these pair of edges with one edge (from $i$ to $j$ ) of weight $x_{ij} - x_{ji}$ , which would result in a new IOU graph which is equi-divergent to the initial one, but which has one edge less (i.e., one transaction less) and which requires less money to flow in order to have the debts paid. This is essentially what is depicted in the simple Alice & Bob example with which I started this post.
  
  Does minimizing the number of transactions result in the same optimal IOU graph as minimizing the money flow? I don’t know. In the two examples I gave in the post, that seems to be the case. Since I don’t have a method to solve a general least number of transactions problem, I can’t answer your question at this point.
  
  I believe that the minimum number of transactions required is greater or equal to the number of nonzero entries of the IOU graph’s divergent vector divided by two. The rationale is this: if the divergence of a node is nonzero, then that node’s net cash flow is nonzero and, hence, a net amount of money needs to flow in or out of that node. In other words, there needs to be a directed edge inciding or radiating from that node. If a node has zero divergence, then it is not necessary to have a directed edge inciding on it or radiating from it and the node can be disconnected from the IOU graph. My thoughts on this are not too precise at the moment, but I have a gut feeling this is correct.
  - Sune Kristian Jakobsen Says:
    June 22, 2009 at 00:08 | Reply
    Hej. Kan du dansk, eller bare et par hilsener?
    
    By solution I meant optimal equi-divergent IOU.
    
    If there are no IOU graphs which are equi-divergent to the one I gave you, then the one I gave you is “optimal” already.
    
    If I understand you correctly, there will alway be infinitely many equi-divergent IOUs. You can just add some number to $x_{ij}$ and $x_{ji}$ . Of cause you are right since FALSE => p ;)
    
    I believe that the minimum number of transactions required is greater or equal to the number of nonzero entries of the IOU graph’s divergent vector divided by two.
    
    That is correct. Let $n$ be the number of nonzero entries (entries with nonzero divergence). Now you need at least $n/2$ and at most $n-1$ transactions. The reason for the upper bound is that an IOU with minimal number of transactions cannot contain cycles: If you have a cycle in an IOU, you can remove one transaction, and change the value (and possibly direction) of the other transactions in the cycle accordingly. The minimal number of transactions will be less that $n-1$ iff the sum of a proper nonempty subset of the nonzero divergents is $0$ .
    - Rod Carvalho Says:
      June 22, 2009 at 01:58 | Reply
      I don’t speak Danish. I just know some words and simple sentences because I spent a Summer in Copenhagen some years ago. I attended a summer school at DTU, and a conference at the Københavns Universitet. It was a jolly good Summer :)
      
      If I understand you correctly, there will alway be infinitely many equi-divergent IOUs. You can just add some number to $x_{ij}$ and $x_{ji}$ .
      
      I believe that is right. For instance, suppose we have 3 agents: Alice, Bob, and Charlie. Alice owes $1 to Bob and $1 to Charlie. Any IOU graph where Alice owes $c+1$ to Bob and Charlie and is owed $c$ by Bob and Charlie is equi-divergent to the original IOU graph. Of course, $c \geq 0$ , otherwise we may not obtain an IOU graph (the weight nonnegativity constraint might not be satisfied).
      
      Of course, an example does not prove anything. To make sure that any IOU graph we obtain is equi-divergent to the original one, we must satisfy the constraint that their divergence vectors are the same
      
      $\textbf{div} (\mathcal{G}) = \textbf{div} (\mathcal{G}_0)$ ,
      
      and if the graphs have $n$ nodes, this means we have $n$ equations. In matrix form, we have
      
      $C x = - \textbf{div} (\mathcal{G}_0)$
      
      where $x \in \mathbb{R}^{n (n-1)}$ is a vector containing the weights of the new IOU graph (which are to be determined), and $C \in \mathbb{R}^{n \times n(n-1)}$ is the incidence matrix of the directed complete graph with $n$ nodes. Please note that we are looking for an IOU graph in the set of complete directed graphs, i.e., we have a lot of freedom and the new IOU graph does not need to have the topology of the original IOU graph. In fact, the new IOU graph can be complete! We thus have a linear system of $n$ equations in $n (n-1)$ unknowns, which is an under-determined system for $n > 1$ . The $n (n -2)$ degrees of freedom lead to the existence of an infinite number of solutions $x$ . We restrict these solutions to be nonnegative, but still, we have an infinite number of them. For this reason, I believe that, indeed, there will always be infinitely many equi-divergent IOU graphs. Do you agree?
      - Sune Kristian Jakobsen Says:
        June 22, 2009 at 03:04
        Yes, as long as the IOU contain at least 2 persons, it would alway be possible to add a positive number to the weight of $x_{12}$ and $x_{21}$ . However the IOU with one person or none at all are both unique!
        
        For a given IOU there might be more than one equi-divergent IOU with minimal money flow, but a least one of these don’t have cycles: If a minimal IOU have a cycle, you can remove it without increasing the money flow. Simply find the direction in the cycle that the most transactions go, find the smallest transaction in this direction, and “send this amount the other way round”.
- Sune Kristian Jakobsen Says:
  June 22, 2009 at 06:34 | Reply
  I have found a proof that every IOU-graph has an equi-divergent IOU-graph that minimize both money flow and number of transactions:
  
  First we observe that the minimal money flow is at least the sum of the positive entries in the divergence-vector. Is it also easy to see that it is possible to meat this bound.
  
  Given an IOU-graph G, we want to construct an IOU-graph that minimize both money flow and number of transactions:
  There exist an IOU that minimize the number of transactions. Find such a graph G’. We know that there cannot be any cycles in G’. We now create a new graph G”: For each connected component, we minimize the money flow. Now the money flow in G” is the sum of the positive entries in the divergence-vector, thus G” has minimal money flow. Finally, we know that we can remove cycles without increasing the money flow. Do this to obtain the graph H. Now H minimize both money flow and number of transactions.
  - Paolo Codenotti Says:
    June 23, 2009 at 13:02 | Reply
    I think you are right: there is always a graph which minimizes the number of transactions and the total money flow at once.
    
    The proof you gave for removing cycles however is wrong: you have to sometimes create “shortcuts” in your cycles, you can’t just send the money the other way, because that could contain many edges. Consider the following example: there are $4$ vertices, $a, b, c, d$ , and an IOU graph as follows: $w(a,b ) = 5$ , $w(b, d) = 1$ , $w(a, c) = 1$ , $w(c, d) = 5$ . All other weights are $0$ . If we remove either of the $1$ edges and send the money the other way, we end up with a solution of total cost $1$ more than this one, because we are adding the $1$ back twice. However, we can remove both $1$ edges, and send only $4$ from $a$ to $b$ , $4$ from $c$ to $d$ and $1$ from $a$ to $d$ . In this sense we might have to introduce “shortcuts. So in general, given an undirected cycle $c_1, \ldots, c_t$ (with directions on the edges), let $w_i$ be the weight of the edge in the cycle between $c_i$ and $c_{i+1}$ (here $t+1 =1$ , and $w_i$ is always positive: we are ignoring the direction of this edge).
    
    Let us look at two cases. First if our cycle has an index j such that $c_{j-1}$ -> $c_j$ and $c_j$ -> $c_{j+1}$ are both edges in the IOU graph (in that direction). If $w_{j-1} \geq w_j$ , then remove $w_j$ , and subtract $w_j$ from $w_{j-1}$ . This removes the cycle, and we’re done. If $w_{j-1}$ , $c_j$ and $c_j$ -> $c_{j+1}$ . Note that the number of the edges in the graph must be even. We remove the edge with smallest $w_i$ , and send the weight the other way around the cycle. Now we are subtracting $w_i$ more times than we are adding it, so we get an IOU graph with no cycle that is less costly.
    
    Given this, your algorithm works: we have just proven that the min-cost solution will be acyclic: our process of removing cycles actually reduces the total cost every time we remove a cycle. Moreover, it’s fairly easy to see that the min cost solution on a tree is the solution wiht the min number of edges.
    - Sune Kristian Jakobsen Says:
      June 23, 2009 at 13:46 | Reply
      I cannot see why my proof shouldn’t work. If you send $1$ the other way around in your example you will get $w(a,b) = 4$ , $w(b,d) = 0$ , $w(a,c) = 2$ , $w(c,d) = 6$ . These add up to 12, as in the original IOU graph.
      - Paolo Codenotti Says:
        June 23, 2009 at 14:57
        Sorry, you are right, that example does not work. Consider this modified example. There are $5$ vertices, $a, b, c, d, e$ .
        
        $w(a, b) = 5$ , $w(b, e) = 1$ , $w(a, c) = 5$ , $w(c, d) = 5$ , $w(d, e) = 5$ .
        
        Now sending the $(b, e)$ edge the other way gives us new weights:
        
        $w(a, b) = 4$ , $w(b, e) = 0$ , $w(a, c) = 6$ , $w(c, d) = 6$ , $w(d, e) = 6$ .
        
        These add up to $22$ , one more than the original weights.
      - Sune Kristian Jakobsen Says:
        June 23, 2009 at 20:49
        Simply find the direction in the cycle that the most transactions go, find the smallest transaction in this direction, and “send this amount the other way round”.
        
        In your example you send money the wrong way around. If you use my algorithm, you will get:
        
        $w(a,b)=10, w(b,e)=6,w(a,c)=0,w(c,d)=0,w(d,e)=0$
        
        These add up to $16\leq21$
      - Paolo Codenotti Says:
        June 26, 2009 at 07:03
        I am sorry, you are right. I misread that you wanted to find the direction in which the most money was sent (not the largest number of transactions).
Michael Trick Says:
June 21, 2009 at 02:56 | Reply
See “A Solution to Post Crash Debt Entanglements in Kuwait’s al-Manakh Stock Market” Interfaces 27:1 89-106 (1997) (there is also an Operations Research 44:5, 665-??? (1996) where all this was done in practice. Of course, Kuwait was able to impose a centralized decision, but it is interesting to read of their objectives.
Ganesh Says:
June 21, 2009 at 06:38 | Reply
When I was living with roommates, I wrote Mshare just for this sort of problem. This information would have surely helped back then.
- Rod Carvalho Says:
  June 22, 2009 at 02:24 | Reply
  I downloaded the source code and skimmed through it. It’s been a few years since I last wrote any JavaScript code, but I was curious to see how you implemented it.
Perspicacious Says:
June 29, 2009 at 09:53 | Reply
Hi just a few random thoughts on your above post:

-If you just want to understand the basics of all this check out the book Introduction to Operations Research by Hillier and Lieberman. It has a good chapter on Network Flow optimization

-What you have made is extremely interesting and has some really wide applications, for example the entire credit crisis around Lehman’s fall was an IOU graph that went haywire and when AIG was going down the Fed stepped in to sort of stabilize the graph. Quite simply the central bank should have some sort of global IOU graph, it can then choose the best points which will stimulate maximum stability with minimum money should such a crisis recur.

-Any market settlement mechanism where there is trade between members and open positions (unpaid or unreceived amounts) should find this useful, e.g. a stock exchange, a clearing house, etc.

-An additional constraint your model should have would be taxes or would that be covered under transactional costs?

-Can you mix this with your Ponzi scheme model you blogged about earlier? For example, out of $n$ nodes – one node is a Ponzi scheme, how can it be neutralized without disrupting the graph?
- Rod Carvalho Says:
  June 29, 2009 at 16:53 | Reply
  Thanks for your comment. You have proposed some truly interesting ideas!
  
  If you just want to understand the basics of all this check out the book Introduction to Operations Research by Hillier and Lieberman. It has a good chapter on Network Flow optimization
  
  I am acquainted with Hillier & Lieberman’s book. It was the recommended textbook for an undergrad Operations Research course I took some years ago. I like the book, but I like Bertsekas’ book more. I suppose Hillier & Lieberman is more directed towards practitioners, whereas Bertsekas’ book is more academic.
  
  The central bank should have some sort of global IOU graph, it can then choose the best points which will stimulate maximum stability with minimum money should such a crisis recur.
  
  That’s an area of application I had not yet thought of. If I can find data on how much money each bank owed to other financial institutions, I could write a script to generate an IOU graph automatically. That would pretty cool!
  
  I am a big believer in the power of diagrams. Better than solve a problem using heavy machinery is to formulate the problem in such a way that the solution can almost be found by visual inspection. Unfortunately, this is seldom possible or easy to attain.
  
  An additional constraint your model should have would be taxes or would that be covered under transactional costs?
  
  What kind of taxes are you thinking of? What motivated this problem was the desire to find a way to split the bill with friends in an efficient manner. Hence, I did not consider taxes. I would like to extend the model and consider taxes, but I would have to focus on something specific, like securities trading or something.
  
  The model I wrote about on this post is indeed simplistic, but it’s a starting point. Building on top of it should be easy because the model is very general.
  
  Can you mix this with your Ponzi scheme model you blogged about earlier?
  
  I thought about it. The debts could be illustrated in the form of an IOU graph. This would be aesthetically interesting, but from a computational viewpoint, I don’t think it would add much value.
  
  A graphical approach would allow one to visualize the money flowing from the later investors in the Ponzi scheme to the earlier ones. The graph would be dynamic, i.e., new nodes would be added to the graph as time went on. After a while, the pool of potential investors would be depleted, and the Ponzi scheme would collapse.
Aurelie Says:
June 30, 2009 at 16:42 | Reply
This will make a great exercise for my students in the Fall, when we cover network optimization!
Bill Tozier Says:
July 15, 2009 at 11:54 | Reply
Two quick comments:

1. It comes up locally in regular lunch meetings sometimes.

2. While the central-planning old-school Operations Research approach you take makes a good deal of sense, I wonder if there is also an agent-based version. That is, can one develop a general local strategy by which agents can pass one (or a few) iterated “negotiation” messages with their immediate neighbors, and then simultaneously exchange funds on that information to reach the global optimal solution? This opens up a third objective to minimize: the number of messages passed before trading occurs.

Just strikes me that there should be a distributed algorithm to solve this problem efficiently, perhaps in the number of iterations it would take for messages to propagate across the graph.
- Rod Carvalho Says:
  July 17, 2009 at 07:48 | Reply
  I am intrigued by the problem you proposed. When I have some time, I will try to model it…
  
  I wonder if there is also an agent-based version. That is, can one develop a general local strategy by which agents can pass one (or a few) iterated “negotiation” messages with their immediate neighbors, and then simultaneously exchange funds on that information to reach the global optimal solution?
  
  You have guessed my thoughts exactly! The centralized, textbook solution I proposed here is just a start. On future posts I would like to:
  
  a) develop a framework that allows one to easily compute the optimal debt allocation in a centralized manner. I have done this already, and it uses matrices, as expected. Some Kronecker products too. It looks sexy.
  
  b) develop a decentralized framework where each agent can only use local information, i.e., can only communicate with its neighbors. Like you said, minimizing the number of messages being exchanged, not just the number of transactions being made, would be an avenue worth pursuing, imho.
  
  c) design a decentralized, distributed debt-allocation protocol and implement it in software, purely for recreational purposes.
  - Bill Tozier Says:
    July 17, 2009 at 08:44 | Reply
    Where “recreational purposes” should be understood to refer to “next killer app for community-based financial services.” Unless you’re not paying attention :)
    - Rod Carvalho Says:
      July 18, 2009 at 14:13 | Reply
      Well, combining social networks, trust and financial services is not exactly a new idea. For example, take the Ripple Project. I have wondered why Facebook has not yet launched a community-based financial services system. That could be their “killer app”. But then, I guess the SEC would be more than happy to shut the system down in order to “protect” the people.
      
      I am an engineer, and I am fascinated by the technical challenges that one encounters when implementing complex systems. However, financial systems are much more than a technical problem. They are also legal and regulatory problems. And these are notorious innovation-killers indeed, don’t you agree?
      
      Therefore, implementing stuff purely for “recreational purposes” is an interesting (and stealthy) way of stimulating discussion on news ideas. It allows one to focus on the technical side and ignore the burdens of the legal and regulatory hassles…

Rod Carvalho

Optimal Account Balancing

Like this:

21 Responses to “Optimal Account Balancing”

Leave a Reply Cancel reply

Follow “Rod Carvalho”