Consider a network of 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 , where is the node set (each node of the IOU graph represents a different agent), is the edge set (containing elements), and is a weight function that assigns positive weights to each edge in . Each directed edge of graph is an ordered pair , where is the edge’s tail and is the edge’s head. If then node owes money to node . We do not allow nodes to owe money to themselves and, therefore, for each we must have . The weight of edge is given by , and it tells us the amount of money that node owes to node .
Alternatively, the information contained in the IOU graph can be encoded in the following nonnegative matrix
where entry is the amount of money node owes to node . 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 , whose node set is . Note that for each , because nodes cannot owe money to themselves. We now introduce variables as follows
and build the (nonnegative) adjacency matrix of the IOU graph
which is the IOU matrix associated with the IOU graph . The entry of matrix denotes the amount of money that node owes to node . The divergence of node is a scalar defined as
and it gives us the amount of money node owes to other nodes minus the amount of money node is owed to by other nodes. In terms of the IOU matrix , the divergence of node is given by
where is the -th vector of the canonical basis for , i.e., the -th column of the identity matrix , and is an -dimensional vector of ones. Let denote the vectorization operator, which stacks a given matrix’s columns in one large column vector. Note that if we apply operator to a scalar, we obtain the same scalar. Hence, we have that
where denotes the Kronecker product. Therefore, the divergence of node can be written as
We define also the divergence vector of graph as the -dimensional vector whose -th component is
Alternatively, we can use equation , and write the divergence vector as
Note that -dimensional vectors and contain the same entries, but in a different order. Hence, there exists a permutation matrix such that
which allows us to write
Do note that the permutation matrix depends on only. It does not depend on the entries of the matrix to which operator is applied. Henceforth, we will denote . Finally, we have a rather compact equation for the divergence vector
The divergence vector of an IOU graph 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 . We would like to find a new IOU graph on the same node set , such that the two IOU graphs are equi-divergent, i.e., . 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 .
Let us start with matrix , which will be an admissible IOU matrix if we impose two constraints:
- nonnegativity: the entries of matrix must be nonnegative. This is equivalent to imposing the constraint that vector has nonnegative entries, i.e., , which is equivalent to .
- zero entries on the main diagonal: we must have for all . Note that , and therefore is equivalent to . Hence, imposing the constraint that the entries on the main diagonal be zero is equivalent to imposing the equality constraints
Once these two constraints have been imposed, matrix 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., , which yields
where can be computed from the given IOU graph. Considering the minimum money flow criterion, the cost function to be minimized is the following
and, hence, we obtain the following linear program in
However, this formulation looks a bit silly. Note that initially we have degrees of freedom (the entries of matrix ), then we impose equality constraints to ensure that the entries on the main diagonal are zero, which leaves us with 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 entries off the main diagonal as decision variables?
Let be a binary matrix such that is the reduced vector of decision variables, containing solely the entries of off the main diagonal. We now eliminate the columns of matrix which were to be multiplied by the variables. We do so by multiplying matrix on the right by , which produces a matrix .
The new vector of decision variables is . Since we no longer consider the entries on the main diagonal as decision variables, we don’t need to impose the equality constraints . Hence, we obtain a lower-dimensional linear program
where we now have equality constraints (divergences at the nodes), and inequality constrains (). My intuition tells me that
A Numerical Example
Consider a network of agents whose debts are represented by the following IOU graph (with edges)
Solving the linear program, we obtain a new IOU matrix
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 edges and a total of flowing in it, while the new IOU graph has edges and a total of 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.