Archive for June, 2009

Optimal Account Balancing

June 20, 2009

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.