## Archive for the ‘Finance’ Category

### Optimal Account Balancing II

July 28, 2009

Consider a network of $n = 10$ agents, each owing money to and being owed money by other agents. The debts are represented pictorially by the weighted directed graph

which I called an IOU graph on my previous post on this topic. The IOU graph representing this network is an ordered triple $\mathcal{G} = (\mathcal{N}, \mathcal{E}, w)$, where $\mathcal{N} = \{1, 2, \ldots, 10\}$ 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 (containing $|\mathcal{E}| = 20$ elements), and $w: \mathcal{E} \rightarrow \mathbb{R}^{+}$ is a weight function that assigns positive weights to each edge in $\mathcal{E}$. Each directed edge of graph $\mathcal{G}$ 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}$. 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$.

Alternatively, the information contained in the IOU graph can be encoded in the following nonnegative matrix

$\left[\begin{array}{cccccccccc} 0 & 10 & 0 & 20 & 20 & 5 & 15 & 0 & 0 & 0\\ 0 & 0 & 5 & 10 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 15 & 0 & 5 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0\\ 5 & 20 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0\\ 0 & 15 & 0 & 0 & 0 & 0 & 0 & 20 & 0 & 10\\ 0 & 5 & 15 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array}\right]$

where entry $(i,j)$ is the amount of money node $i$ owes to node $j$. Since we do not allow nodes to owe money to themselves, the entries on the main diagonal of this matrix are zero. We will call this matrix the IOU matrix. Note that the IOU matrix is the adjacency matrix of the IOU graph. Every nonnegative matrix with zero entries on the main diagonal is an admissible IOU matrix, and we can associate with it a corresponding IOU graph.

If the IOU matrix contains all the information about the IOU graph, then we can work with the IOU matrix instead of the IOU graph. Is there any advantage in doing so? I believe there is. In my opinion, the IOU graph is good for conceptual thinking and intuition, while the IOU matrix is a data structure that is convenient for computation. However, the matrix is not the only data structure that one can use to encode the information in an IOU graph. Another possibility would be to use adjacency lists, for example.

__________

Divergence and IOU Matrices

Suppose we are given an IOU graph $\mathcal{G}_0 = (\mathcal{N}, \mathcal{E}_0, w_0)$, whose node set is $\mathcal{N} = \{1, 2, \ldots, n\}$. Note that $(i,i) \notin \mathcal{E}_0$ for each $i \in \mathcal{N}$, because nodes cannot owe money to themselves. We now introduce variables $y_{ij} \geq 0$ as follows

$y_{ij} = \displaystyle\left\{\begin{array}{cl} w_0 ((i,j)) & \text{if} \quad{} (i,j) \in \mathcal{E}_0\\ 0 & \text{if} \quad{} (i,j) \notin \mathcal{E}_0\\ \end{array}\right.$

and build the (nonnegative) adjacency matrix of the IOU graph $\mathcal{G}_0$

$Y = \left[\begin{array}{ccccc} 0 & y_{12} & y_{13} & \ldots & y_{1n}\\ y_{21} & 0 & y_{23} & \ldots & y_{2n}\\ y_{31} & y_{32} & 0 & \ldots & y_{3n}\\\vdots & \vdots & \vdots & \ddots & \vdots\\ y_{n1} & y_{n2} & y_{n3} & \ldots & 0\\\end{array}\right]$

which is the IOU matrix associated with the IOU graph $\mathcal{G}_0$. The $(i,j)$ entry of matrix $Y \in \mathbb{R}^{n \times n}$ denotes the amount of money that node $i$ owes to node $j$. The divergence of node $i \in \mathcal{N}$ is a scalar defined as

$\mbox{div}_i (\mathcal{G}_0) = \displaystyle \sum_{j \neq i} y_{ij} - \displaystyle \sum_{j \neq i} y_{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. In terms of the IOU matrix $Y$, the divergence of node $i \in \mathcal{N}$ is given by

$\mbox{div}_i (\mathcal{G}_0) = e_i^T Y 1_n - e_i^T Y^T 1_n = e_i^T Y 1_n - 1_n^T Y e_i$

where $e_i \in \mathbb{R}^{n}$ is the $i$-th vector of the canonical basis for $\mathbb{R}^n$, i.e., the $i$-th column of the $n \times n$ identity matrix $I_n$, and $1_n$ is an $n$-dimensional vector of ones. Let $\mbox{vec}$ denote the vectorization operator, which stacks a given matrix’s columns in one large column vector. Note that if we apply operator $\mbox{vec}$ to a scalar, we obtain the same scalar. Hence, we have that

$e_i^T Y 1_n = \mbox{vec} (e_i^T Y 1_n) = (1_n^T \otimes e_i^T) \mbox{vec} (Y)$

and

$1_n^T Y e_i = \mbox{vec} (1_n^T Y e_i) = (e_i^T \otimes 1_n^T) \mbox{vec} (Y)$

where $\otimes$ denotes the Kronecker product. Therefore, the divergence of node $i \in \mathcal{N}$ can be written as

$\mbox{div}_i (\mathcal{G}_0) = \left[(1_n^T \otimes e_i^T) - (e_i^T \otimes 1_n^T)\right] \mbox{vec} (Y)$.

We define also the divergence vector of graph $\mathcal{G}_0$ as the $n$-dimensional vector whose $i$-th component is $\mbox{div}_i (\mathcal{G}_0)$

$\mbox{div} (\mathcal{G}_0) = \left[\begin{array}{c} (1_n^T \otimes e_1^T) - (e_1^T \otimes 1_n^T)\\ (1_n^T \otimes e_2^T) - (e_2^T \otimes 1_n^T)\\ \vdots\\ (1_n^T \otimes e_n^T) - (e_n^T \otimes 1_n^T)\\\end{array}\right] \mbox{vec} (Y)$.

Alternatively, we can use equation $\mbox{div}_i (\mathcal{G}_0) = e_i^T Y 1_n - e_i^T Y^T 1_n$, and write the divergence vector as

$\mbox{div} (\mathcal{G}_0) = I_n Y 1_n - I_n Y^T 1_n = (Y - Y^T) 1_n$

and, since

$I_n Y 1_n = \mbox{vec} (I_n Y 1_n) = (1_n^T \otimes I_n) \mbox{vec} (Y)$

and

$I_n Y^T 1_n = \mbox{vec}(I_n Y^T 1_n) = (1_n^T \otimes I_n) \mbox{vec} (Y^T)$,

we obtain

$\mbox{div} (\mathcal{G}_0) = (1_n^T \otimes I_n) \mbox{vec} (Y) - (1_n^T \otimes I_n) \mbox{vec} (Y^T)$.

Note that $n^2$-dimensional vectors $\mbox{vec} (Y)$ and $\mbox{vec} (Y^T)$ contain the same entries, but in a different order. Hence, there exists a $n^2 \times n^2$ permutation matrix $P$ such that

$\mbox{vec} (Y^T) = P \mbox{vec} (Y)$

which allows us to write

$\mbox{div} (\mathcal{G}_0) = (1_n^T \otimes I_n) (I_{n^2} - P) \mbox{vec} (Y)$.

Do note that the permutation matrix depends on $n$ only. It does not depend on the entries of the matrix to which operator $\mbox{vec}$ is applied. Henceforth, we will denote $\tilde{y} = \mbox{vec}(Y)$. Finally, we have a rather compact equation for the divergence vector

$\mbox{div} (\mathcal{G}_0) = (1_n^T \otimes I_n) (I_{n^2} - P) \tilde{y}$.

The divergence vector of an IOU graph $\mathcal{G}_0$ 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.

__________

Minimum Money Flow

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, i.e., $\mbox{div} (\mathcal{G}) = \mbox{div} (\mathcal{G}_0)$. Moreover, we would like the new IOU graph to be “optimal” in some sense. On this post, we will consider the following optimality criterion:

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 weights of the IOU graph $\mathcal{G}$.

Let us start with matrix $X \in \mathbb{R}^{n \times n}$, which will be an admissible IOU matrix if we impose two constraints:

• nonnegativity: the entries of matrix $X$ must be nonnegative. This is equivalent to imposing the constraint that vector $\tilde{x} = \mbox{vec}(X)$ has nonnegative entries, i.e., $\tilde{x} \geq 0_{n^2}$, which is equivalent to $(-I_{n^2}) \tilde{x} \leq 0_{n^2}$.
• zero entries on the main diagonal: we must have $x_{ii} = 0$ for all $i \in \mathcal{N}$. Note that $x_{ii} = e_i^T X e_i = \mbox{vec}(e_i^T X e_i)$, and therefore $x_{ii} = 0$ is equivalent to $(e_i^T \otimes e_i^T) \tilde{x} = 0$. Hence, imposing the constraint that the entries on the main diagonal be zero is equivalent to imposing the $n$ equality constraints

$\left[\begin{array}{c} e_1^T \otimes e_1^T\\ e_2^T \otimes e_2^T\\ \vdots\\ e_n^T \otimes e_n^T\\\end{array}\right] \tilde{x} = 0_n$.

Once these two constraints have been imposed, matrix $X$ is the adjacency matrix of an IOU graph. Finally, we must impose the constraint that the divergence vector of the new IOU graph is the same as the divergence vector of the given IOU graph, i.e., $\mbox{div} (\mathcal{G}) = \mbox{div} (\mathcal{G}_0)$, which yields

$(1_n^T \otimes I_n) (I_{n^2} - P) \tilde{x} = \mbox{div} (\mathcal{G}_0)$

where $\mbox{div} (\mathcal{G}_0) = (Y - Y^T) 1_n$ can be computed from the given IOU graph. Considering the minimum money flow criterion, the cost function to be minimized is the following

$\displaystyle\sum_{i \in \mathcal{N}} \sum_{j \neq i} x_{ij} = 1_n^T X 1_n = (1_n^T \otimes 1_n^T) \tilde{x} = 1_{n^2}^T \tilde{x}$

and, hence, we obtain the following linear program in $\tilde{x} \in \mathbb{R}^{n^2}$

$\begin{array}{ll} \text{minimize} & \displaystyle 1_{n^2}^T \tilde{x}\\\\ \text{subject to} & (1_n^T \otimes I_n) (I_{n^2} - P) \tilde{x} = \mbox{div} (\mathcal{G}_0)\\\\ & \left[\begin{array}{c} e_1^T \otimes e_1^T\\ e_2^T \otimes e_2^T\\ \vdots\\ e_n^T \otimes e_n^T\\\end{array}\right] \tilde{x} = 0_n\\\\ & (-I_{n^2}) \tilde{x} \leq 0_{n^2}\\\\\end{array}$

which has $2 n$ equality and $n^2$ inequality constraints. One can easily solve this linear program with MATLAB using function linprog.

However, this formulation looks a bit silly. Note that initially we have $n^2$ degrees of freedom (the $n^2$ entries of matrix $X$), then we impose $n$ equality constraints $x_{ii} = 0$ to ensure that the entries on the main diagonal are zero, which leaves us with $m = n^2 - n = n (n-1)$ degrees of freedom. If we already know that the entries on the main diagonal are zero, why consider them as decision variables? Wouldn’t it make much more sense to consider only the $m = n (n-1)$ entries off the main diagonal as decision variables?

Let $R$ be a $m \times n^2$ binary matrix such that $\hat{x} = R \tilde{x}$ is the reduced vector of $m$ decision variables, containing solely the entries of $X$ off the main diagonal. We now eliminate the $n$ columns of $n \times n^2$ matrix $(1_n^T \otimes I_n) (I_{n^2} - P)$ which were to be multiplied by the $x_{ii}$ variables. We do so by multiplying matrix $(1_n^T \otimes I_n) (I_{n^2} - P)$ on the right by $R^T$, which produces a $n \times m$ matrix $(1_n^T \otimes I_n) (I_{n^2} - P) R^T$.

The new vector of decision variables is $\hat{x} \in \mathbb{R}^m$. Since we no longer consider the entries on the main diagonal as decision variables, we don’t need to impose the $n$ equality constraints $x_{ii} = 0$. Hence, we obtain a lower-dimensional linear program

$\begin{array}{ll} \text{minimize} & \displaystyle 1_{m}^T \hat{x}\\\\ \text{subject to} & (1_n^T \otimes I_n) (I_{n^2} - P) R^T \hat{x} = \mbox{div} (\mathcal{G}_0)\\\\ & (-I_m) \hat{x} \leq 0_{m}\\\\\end{array}$

where we now have $n$ equality constraints (divergences at the nodes), and $m$ inequality constrains ($x_{ij} \geq 0$). My intuition tells me that

$(1_n^T \otimes I_n) (I_{n^2} - P) R^T = \left[\begin{array}{c} (1_n^T \otimes e_1^T) - (e_1^T \otimes 1_n^T)\\ (1_n^T \otimes e_2^T) - (e_2^T \otimes 1_n^T)\\ \vdots\\ (1_n^T \otimes e_n^T) - (e_n^T \otimes 1_n^T)\\\end{array}\right] R^T$

is an incidence matrix of the directed complete graph on node set $\mathcal{N}$. What do you think? Do you agree?

__________

A Numerical Example

Consider a network of $n = 10$ agents whose debts are represented by the following IOU graph (with $15$ edges)

The IOU matrix associated with this given IOU graph is

$Y = \left[\begin{array}{cccccccccc} 0 & 0 & 0 & 20 & 20 & 5 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0\\ 5 & 20 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 20 & 0 & 10\\ 0 & 5 & 15 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array}\right]$

Solving the linear program, we obtain a new IOU matrix

$X = \left[\begin{array}{cccccccccc} 0 & 6.097 & 3.924 & 10.776 & 10.776 & 8.427 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0.850 & 0.644 & 1.234 & 1.234 & 1.039 & 0 & 0 & 0 & 0\\ 0 & 1.690 & 1.185 & 2.505 & 2.505 & 2.114 & 0 & 0 & 0 & 0\\ 0 & 4.672 & 3.063 & 7.980 & 7.980 & 6.306 & 0 & 0 & 0 & 0\\ 0 & 1.690 & 1.185 & 2.505 & 2.505 & 2.114 & 0 & 0 & 0 & 0\\\end{array}\right]$

which is the adjacency matrix of a new IOU graph. The given IOU graph and the new IOU graph are equi-divergent. The given IOU graph had $15$ edges and a total of $165$ flowing in it, while the new IOU graph has $25$ edges and a total of $95$ flowing in it. While the flow of money has been reduced, the number of edges (i.e., the number of transactions) has increased dramatically!!

On my previous post on this topic, I gave two very simple examples, and in both of them the minimum money flow solution also yielded the least number of transactions. I wondered back then if that was always the case. This example clearly shows that it is not. Generally speaking, not only does the minimum money flow criterion fail to minimize the number of transactions, but it can actually result in more transactions than the ones in the initial IOU graph. I cannot think of any reason why minimizing the total amount of money flowing in the IOU graph at the cost of a larger number of transactions would be a good idea…

Therefore, the next step is to abandon the minimum money flow criterion, and focus solely on the least number of transactions. Minimizing the number of transactions is a hard combinatorial problem, but maybe there are approximation algorithms that make the problem tractable.

### 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.

### Modeling Ponzi Schemes II

February 7, 2008

As I wrote a few days ago, one of my ongoing projects is to devise mathematical models of Ponzi schemes. On my previous post I briefly explained what a Ponzi scheme is, so I will now focus on building a first model which, though somewhat simplistic and crude, will hopefully give us some insight.

__________

Model Variables

For starters, let us introduce some variables:

• $c(t)$: cash in the scammer’s pockets at time $t \in [0,\infty)$.
• $q(t)$: cash influx rate at time $t \in [0,\infty)$. Note that this is a rate! Thus, the amount of cash that flows into the scammer’s pockets in a time interval of infinitesimal duration $[t, t + dt]$ is $q(t) dt$. You may wonder why I chose letter $q$ to denote influx: the reason is that I have used letter $q$ to denote influx since I started using it years ago to denote heat flow. Habits are hard to change.
• $T$: lock-up period ($T > 0$). The scammer promises to return the money to the investors after a lock-up period of $T$ units of time.
• $R$: promised return on investment ($R > 0$). The scammer promises to return to the investors $1+R$ times the money they invested, $T$ units of time after they invested.

Keeping track of the influx and outflow of cash, we can build a conservation law.

__________

Money Dynamics and the Law of Conservation of Cash

We can now write the “law of conservation of cash”: if more money comes in than it goes out, then the scammer’s pile of cash will be increasing (and so will his debt). We will assume that the scammer does not deposit the cash in a bank to earn interest on it, though we may consider that possibility in a more elaborate model. For the time being, our “law of conservation of cash” is given by the following differential equation

$\displaystyle\dot{c}(t) = \displaystyle q(t) - (1+R) q(t-T)$,

in which $c: [0,\infty) \rightarrow \mathbb{R}$ is the function to be determined, and $q: [0,\infty) \rightarrow \mathbb{R}$ is the forcing function. Note that the forcing function includes a delayed forcing term. Let us try to interpret this differential equation:

• the rate at which cash flows out is higher than the rate at which money flows in. This is NOT good! Imagine a wash basin in which the water influx from the tap is lower than the outflux going down the drain. That’s right, the basin will soon be empty, and that is precisely why Ponzi schemes are unsustainable: either you increase the cash influx over time, or you will soon be out of money. Since the cash influx cannot grow without bound, at some point the cash influx will be insufficient to pay off the debt and the scammer will be owing money to a lot of very angry creditors.
• cash flows out with a delay equivalent to the lock-up period.

We can now solve the differential equation.

__________

General solution of the differential equation

If we denote the initial amount of cash by $c(0) = c_0$ and solve the differential equation above, we obtain

$c(t) = c_0 + \displaystyle\int_{0}^t q(\tau) d\tau - (1+R) \displaystyle\int_{0}^{t} q(\tau - T) d\tau$.

Note that for $t \in [0,T)$

$\displaystyle\int_{0}^{t} q(\tau - T) d\tau = 0$,

and that for $t > T$

$\displaystyle\int_{0}^{t} q(\tau - T) d\tau = \displaystyle\int_{0}^{t -T} q(\tau ) d\tau$.

Therefore

$\displaystyle\int_{0}^{t} q(\tau - T) d\tau = \displaystyle\int_{0}^{\max(t-T,0)} q(\tau) d\tau$,

and therefore the general solution can be written as

$c(t) = c_0 + \displaystyle\int_{0}^t q(\tau) d\tau - (1+R) \displaystyle\int_{0}^{\max(t-T,0)} q(\tau) d\tau$.

This might look a bit complicated, but in fact it is very simple: the amount of cash the scammer will have in his pockets at time $t$ will be given by his initial amount of cash, plus the amount of cash his creditors lent him, minus the amount of cash he had to pay to his creditors (which is “amplified” by $R$) over time interval $(t-T, t)$. Note that the scammer only starts returning money to the investors at time $t=T$.

The aforementioned general solution can also be written as

$c(t) = c_0 + \displaystyle\int_{\max(t-T,0)}^t q(\tau) d\tau - R \displaystyle\int_{0}^{\max(t-T,0)} q(\tau) d\tau$.

Before we try out some forcing functions, let’s get the notation straight for the remainder of this post:

• the Heaviside step function will be denoted by $u(t)$. The Heaviside step function is the integral of the Dirac delta function.
• the ramp function will be denoted by $s(t)$. The ramp function is the integral of the Heaviside step function.

This is the usual notation in signal processing and control systems engineering. To understand the aforementioned general solution, let’s now try out a couple of forcing functions.

__________

Example: single discretionary cash influx at $t=0$

$\displaystyle q(t) = \displaystyle q_0 \delta(t)$

In this case, an amount of cash equal to $q_0$ is credited to the scammer’s pockets at time $t=0$. The solution will thus be

$\displaystyle c(t) = \displaystyle c_0 + q_0 u(t) - (1+R) q_0 u(t-T)$,

which is the Ponzi scheme’s impulse response (borrowing another signal processing expression), so to say. Note that $c(t) = c_0 + q_0$ for $t \in (0, T)$, while $c(t) = c_0 - R q_0$ for $t > T$.

__________

Example: constant cash influx rate

$\displaystyle q(t) = \displaystyle q_0 u(t)$

In this case, a constant influx of cash flows to the scammer’s pockets. Unfortunately for the scammer, he will have to repay this cash with interest $T$ units of time later. The solution of the differential equation is now

$c(t) = \displaystyle c_0 + q_0 s(t) - (1+R) q_0 s(t-T)$,

which is the Ponzi scheme’s step response (once again borrowing a signals & systems expression). The cash will increase linearly with time for $t \in (0,T)$, a maximum is reached at $t=T$ (maximum: $c(T) = c_0 + q_0 T$), and then the debt-paying time starts and the cash will decrease linearly with slope $- R q_0$ until the amount of cash reaches zero at $t = t_B > T$. Making $c(t_B) = 0$ we have

$\displaystyle c_0 + q_0 t_B - (1+R) q_0 (t_b - T) = 0$,

which yields

$t_B = \displaystyle\frac{c_0}{R q_0} + \displaystyle\left(1 + \frac{1}{R}\right) T$,

which is the “bankruptcy time”. For $t > t_B$, the scammer will have to go into debt to pay off to his investors.

__________

Concluding remarks

On this post, I presented a simple continuous-time model of a simplified Ponzi scheme. In the two examples I presented, one can conclude that the scammer’s best strategy is to run away at moment $t = T^{-}$, when he has the most cash in his pockets (and owes the most to his creditors).

However, if we think beyond this model’s assumptions and limitations, it is clear that running away just before the lock-up period has expired might not be the “best strategy”. Note that if the scammer returns the money to the earliest investors, these might believe that the scammer truly has a Midas touch and decide to re-invest their money. In addition to that, if the scammer honors the early contracts and returns the money to his earlist investors, these investors may tell their friends and thus serve as “viral marketers” of the scammer’s investing “ingenuity”. Hence, it would then be natural to expect an increase in the money influx after the scammer returns the money to the earliest investors.

I will be writing more on this topic on future posts.

__________

Disclaimer: I am NOT an accountant, I am an electrical engineer. I have NEVER studied any accounting at all. Please bear with me if I misused technical terms, or if I invented silly new ones. Thank you.

__________

Earlier posts in this series:

### Modeling Ponzi Schemes

February 3, 2008

At the height of his success in Boston in 1920, Charles A. Ponzi was hailed by those he was cheating as the greatest Italian who ever lived. “You’re wrong,” he said modestly, “there’s Columbus, who discovered America, and Marconi, who discovered radio.” “But, Charlie, you discovered money,” they told him.

(San Diego Daily Transcript – July 16, 1974)

I admit that it may sound a bit ludicrous, but lately I have been thinking on how to devise mathematical models of Ponzi schemes.

It is clear that a Ponzi scheme is unsustainable and that it will, sooner or later, collapse under its own weight. The scammer promoting such a scheme will be owing ever-increasing amounts of money to the investors, and as soon as the influx of cash is not enough to pay off the debts plus interest, the scheme will collapse.

[ Charles Ponzi in 1920 - photo courtesy of the U.S. government ]

Ponzi schemes have happened for a long time, but the scheme bears the name of its most “illustrious” scammer, Charles Ponzi (1882–1949) , who ran a huge fraudulent operation in the U.S. in 1919 and 1920.

Note that:

• the early investors in a Ponzi scheme will make money if they drop out before the whole thing collapses. On the other hand, the later investors will lose money.
• there’s a money transfer from the later investors to the scammer promoting the scheme and the earlier investors, so to say. As such, one has the incentive to be an early investor provided that the fraud lasts long enough for one to profit.
• an investor might be aware that there’s fraud going on and still invest if he thinks that the scheme will last a bit longer before it collapses so that he can get his money back and earn the interest.

How to devise mathematical models of Ponzi schemes? Which variables to choose? Which assumptions to make? It is not nearly as easy as one might think at first glance, I must say. An over-simplistic model is easy to devise, but it will tell us little. I have been building some models, and I will most likely write about them in future posts.