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 , where:

• is the node set. Each node of the IOU graph represents a different agent.

• is the edge set. Each directed edge 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 .

• is a weight function that assigns positive weights to each edge in . The weight of edge is given by , and it tells us the amount of money that node owes to node .

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

and illustrate them below

The divergence [1] of node of graph 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. 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 as the vector whose -th component is

.

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.

__________

Optimal Account Balancing

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

.

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 whose edge set is the one of the directed complete graph on . Hence, every two distinct nodes are connected by two directed edges with opposite directions. The weight of edge is denoted by . 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 nonnegative variables 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]

which can be solved via linear programming [2]. In words: we want to find the debts 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 -agent example where the agents are Alice, Bob and Charlie. The IOU graph is

where the node set is . We introduce vector

where is the amount of money node owes to node . 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 , where

is the incidence matrix of the graph, and 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 be the identity matrix, let be the -dimensional vector of ones, and let be the -dimensional vector of zeros. The nonnegativity constraints can be written in matrix form as . Considering the minimum money flow criterion, we obtain the linear program

Note that the equality constraint is equivalent to two inequality constraints: and . Thus, we can transform the linear program above into a linear program with inequality constraints only

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

,

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

Interview with C.N. Yang and Jim Simons

Here’s an interview with renowned theoretical physicist and Nobel laureate Chen Ning Yang (of Yang-Mills fame) and renowned mathematician, hedge fund manager and philanthropist James Harris Simons (of Chern-Simons fame) on the deep connections between Geometry and Physics, the new Simons Center for Geometry and Physics, their careers and their views on various topics.

[ video courtesy of Stony Brook University ]

Related:

• Interview with Chen Ning Yang

• Interview with James Simons

How would you design this contract?

[ source ]

Let us start with the following joke:

Two business partners asked their lawyer to hold $20,000, making him promise to get both of their signatures before disbursing any of it. As soon as one partner left town, the other pressed the lawyer for $15,000, citing an emergency. The lawyer reluctantly gave it to him, and he disappeared. On his return, the other partner was irate, so the lawyer explained that he had donated the $15,000 out of his own pocket.

“Then give me the $20,000 you’re holding,” said the partner.

“All right,” said the lawyer. “Give me the two signatures.”

__________

These two business partners and their lawyer should have signed a contract. If the lawyer disbursed any of the partners’ money without having both of their signatures, he would face legal action for breach of contract. However, this contract would still not be immune to collusion: one of the two partners could split the money with the lawyer and disappear, and the other partner would never have the two signatures required by contract to have his money back. How would you design a better contract? By “better contract”, I mean:

• a contract that would NOT give any of the parties involved an incentive to break it.

• a contract that would be robust (and, ideally, immune) to collusion.

I make no claims that such a “perfect contract” even exists, but maybe one could devise a contract that would be better than the aforementioned one. Purely for recreational purposes, I propose a challenge: try to design the best contract you can think of!

If you have any ideas, please feel free to share them.

Radiology Art

The Radiology Art project was started by artist and medical student Satre Stuelke in the Summer of 2007. Stuelke uses a CT scanner to acquire DICOM images of various objects (e.g., electronic apparatuses, toys) and then processes them with OsiriX Imaging Software and Adobe Photoshop. Colors are assigned based on the varying densities of materials present throughout the object. The post-processed images are stunning.

For example, here’s a CT scan of a Teslovak KT88S vacuum tube:

[ image courtesy of Satre Stuelke ]

Related:

• A Cultural Scan

• Diagnostic Art

The Trials of J. Robert Oppenheimer

In the days of my almost infinitely prolonged adolescence, I hardly took an action, hardly did anything that did not arouse in me a very great sense of revulsion and of wrong. My feeling about myself was always one of extreme discontent.

- J. Robert Oppenheimer (1904-1967)

The Trials of J. Robert Oppenheimer is a two-hour documentary film on the life of the brilliant and charismatic American nuclear physicist J. Robert Oppenheimer (1904-1967), from his youth and emergence as one of America’s leading physicists, to his leadership of the Manhattan Project, and his most tragic humiliation during the anti-Communist witch-hunt in the 1950s.

The film was produced by David Grubin, and it features actor David Strathairn as Oppenheimer. You can watch it online for free. The transcript is also available.

__________

Related:

• Shubhendu Trivedi’s review of American Prometheus

• Aurélie Thiele’s review of American Prometheus

• Robert Oppenheimer: 104th birthday (by Luboš Motl)

• Oppenheimer (by E. Kowalski)

Distance between two words

Consider a finite set with distinct elements which we will call symbols. We will call set an alphabet. A word (also known as string) of length over set is formed by constructing an -tuple of symbols from alphabet

where for all . A string of length will be called an -string. The set of all -strings is given by the cartesian product

.

For example, in coding theory one usually works with binary words, i.e., words over alphabet . The set of all binary words of length is , whose cardinality is .

In this post we will work only with words over the alphabet

which is known as the Latin alphabet, and whose 26 symbols are known as letters. For example,  and are represented by the 3-strings and , respectively, where .

__________

Hamming distance

Given two strings of equal length, the Hamming distance between them is the number of positions for which the corresponding symbols are different. In other words, the Hamming distance between two strings of equal length is the minimum number of symbol substitutions required to change one string into the other.

Let function be defined as

where function is defined as

then is the Hamming distance between -strings and . For example, if and , then we have because and only differ in one symbol (the last one).

Suppose we are given an -string over the Latin alphabet . If we replace the letter at position with another letter in , where , we can obtain a total of new -strings, each within Hamming distance of the original -string. Let us call these -strings neighbors of the original -string. Thus, an -string has a total of neighbors.

__________

Word graphs

If two -strings are neighbors of one another when their Hamming distance is equal to , then a graphical approach would be the natural way to go. Let be an undirected graph whose set of nodes is (set of all -strings over alphabet ), and whose set of edges is . Two nodes are connected by an edge if their Hamming distance is equal to . Hence the total number of nodes in is , and the total number of edges in is

,

because each node has neighbors, there are nodes, and each edge is counted twice so we need to divide the total by . Note that is a regular graph (of degree ) because all nodes have the same number of neighbors.

For example, let and let us consider the -string , which has neighbors. Out of these words, I could count words which actually mean something in the English language:

bar, ear, far, gar, jar, mar, oar, par, tar, war, yar, cor, cur, cab, cad, cam, can, cap, cat, caw, cay.

Please let me know if I forgot to include any word in this list. These words form a sub-graph of the graph of all -strings. Note that the words

bar, car, ear, far, gar, jar, mar, oar, par, tar, war, yar

are all neighbors of one another, and hence, they form a clique of size . The words

car, cor, cur

form a clique of size . The words

cab, cad, cam, can, cap, car, cat, caw, cay

are all neighbors of one another as well, and thus they form a clique of size . The subgraph formed by the word “car” and its neighbors which make sense in the English language is illustrated below, where the three cliques are easy to identify

[ graph generated with Graphviz ]

It is not practical to depict the whole graph of -strings over alphabet since it contains nodes and edges!

__________

Python code

In case you are wondering: no, I did not type the 26 symbols of the Latin alphabet in . That would have been way too cumbersome. All it took was one single line of Python code:

", ".join([("\text{" + chr(i) + "}") for i in range(ord('a'),ord('z')+1)])

Suppose we would like to find all strings within Hamming distance of of string . The following Python script automates the process:

def MutateString(s, alphabet, index):
    li = []
    for ch in alphabet:
        if ch != s[index]:
            li.append(s[:index] + ch + s[index+1:])
    return li

# build Latin alphabet (lowercase symbols only)
Sigma = [chr(i) for i in range(ord('a'),ord('z')+1)]

# obtain list of mutated strings
print "Mutate 1st symbol:\n" + ", ".join(MutateString('cat', Sigma, 0)) + '\n'
print "Mutate 2nd symbol:\n" + ", ".join(MutateString('cat', Sigma, 1)) + '\n'
print "Mutate 3rd symbol:\n" + ", ".join(MutateString('cat', Sigma, 2)) + '\n'

The graph of the word “car” and its neighbors was generated also by a Python script using the GvGen library.

def HammingDistance(s1, s2):
    """Computes the Hamming distance between strings s1 and s2"""
    assert len(s1) == len(s2)
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

import gvgen

# list of words
words = ['car', 'bar', 'ear', 'far', 'gar', 'jar', 'mar', 'oar', 'par', 'tar', 'war', 'yar', 'cor', 'cur', 'cab', 'cad', 'cam', 'can', 'cap', 'cat', 'caw', 'cay']

# creates the new graph instance
graph = gvgen.GvGen()
graph.smart_mode = 1

# creates graph nodes
nodes = []
for elem in words:
    nodes.append(graph.newItem(elem))

# creates graph edges
for i in nodes:
    for j in nodes:

        # extracts the labels of each node
        node1 = i['properties']['label']
        node2 = j['properties']['label']

        # links nodes i and j if the Hamming
        # distance between their labels is 1
        if HammingDistance(node1,node2) == 1:
            graph.newLink(i,j)

# outputs the Graphviz code to a .dot file
filename = "test.dot"
FileOut = open(filename,"w")
graph.dot(FileOut)
FileOut.close()

The script outputs a DOT file which can be read by Graphviz. In particular, I used GVedit (with layout engine = circo) to generate the diagram depicted above.

Remark: these snippets of code worked with Python 2.5.2. I can not guarantee that they work with other versions.

Composing music with Noteflight

A start-up company named Noteflight has created a web application that allows one to compose and play music within one’s web browser. For example, here’s a sheet of Mozart’s Piano Sonata No. 11 (Klaviersonate Nr. 11):

You can play it and it sounds quite good for a web app.

This is an interesting idea: not only can one write music without having to buy an application, but one can also share one’s creations with the entire community of Noteflight’s users. You can use the web app for free, although you need to create an account if you want to compose music (no sign up is required if you just want to play music).

This web app raises some interesting questions regarding copyright infringement. If I write a sheet of a song which was composed by someone else, am I violating any copyright law? If I share that music sheet with other Noteflight users, am I doing anything illegal? Will Noteflight be held liable for promoting the distribution of copyrighted material?

Colored Water Figures

Fotoopa is a photographer from Belgium who has shot amazing high speed photos of dancing and splashing colored water drops. Here’s an example of a droplet captured in mid-splash in vivid detail:

[ photo courtesy of fotoopa ]

Apart from the standard photographic equipment (camera, lenses, multiple flashes), fotoopa uses some high-tech hardware more commonly found on a physics research lab: lasers, LEDs, homemade electronics, power amplifiers, microcontrollers, FPGAs. It’s very, very impressive indeed.

Distance between two lines

Suppose we are given two lines in , and . Line passes through the point and its direction is given by vector

.

Line passes through the point and its direction is given by vector

.

What is the distance between lines and ?

__________

Lines as functions

Let vector-valued functions and be defined as

.

Lines and are thus the images of set under functions and , respectively

.

Function maps each into point . Therefore, choosing a particular value of corresponds to choosing a point on line , and vice versa (because function is injective). Thus, each point on the line can be unambiguously specified by a value of . Similarly, following the same line of thought, each point on the line can be unambiguously specified by a value of .

__________

Distance between two points

In order to compute the distance between lines and , we first need to know how to compute the distance between two points in , i.e., we need to choose a metric on . For the sake of simplicity, we will use the Euclidean metric, i.e., we will use the 2-norm to measure lengths and distances. In other words, we will be working in normed vector space .

Let us fix parameters and , i.e., and , and compute the distance between fixed points and

.

Pictorially, we have that is the length of the line segment connecting fixed points and

To each pair of parameters , it is assigned a non-negative scalar

.

__________

Distance between a point and a line

Suppose now that we vary , while remains fixed, . As we vary , we travel along line and hence the distance between free point and fixed point is given by

.

Since is now free, is a function of .

For example, let us pick three distinct values for , say . The image below depicts the line segments connecting fixed point and points . The length of these line segments gives us the distance between the fixed point and each of the three points on line .

The distance between fixed point and line is thus

.

We have an optimization problem: we would like to find the value of parameter which minimizes function . This minimizer is (see appendix A)

.

Evaluating function at we obtain , the point on line that is closest to fixed point

,

where

is a symmetric, idempotent () projection matrix, and is the orthogonal projection of vector onto vector . It can be shown that vectors  and are orthogonal (see appendix B).

For example, let us consider the case: we have two lines in , and , where lies on plane . Pictorially, we have

We would like to find the point on line that is closest to fixed point . Projecting vector orthogonally onto vector , we obtain

The image above illustrates rather nicely that vectors  and are orthogonal (see appendix B). The distance between fixed point and line is

,

where . Please note that plane serves no purpose other than to make it easier to visualize in 3-d (plane gives an impression of depth). In other words, plane has some “artistic value”, but no “mathematical value”.

__________

Distance between two lines

Let us now vary both and . As we vary and , we travel along lines and , respectively. Since both parameters are free, the distance between free points and is

,

which is a function of both and . The distance between lines and is thus

.

The original problem of computing the distance between two lines has thus been cast as an optimization problem: we would like to find the pair which minimizes . Once we have found the pair of minimizers , the distance between and is

.

The pair is not necessarily unique. For example, if the lines are parallel to each other, then there are infinitely many pairs of minimizers .

Trying to find the pair which minimizes is a one-stage 2-dimensional optimization problem. However, we can solve this optimization problem in two stages, where at each stage we must solve a 1-dimensional optimization problem

.

Note that

is the distance between point and line , and thus

.

We already know how to compute the distance between a point on line and line : given a value of , the choice of which minimizes is , where function is defined as (see appendix A)

,

and the point on line which is closest to is

.

Therefore, for a given value of , we have that the distance between and line is

.

Note that is a function of only, as we have already optimized function for . Finally, the distance between lines and can be found by solving a 1-dimensional optimization problem in

.

Once we have found the which minimizes the distance , the distance between lines and is simply

.

Note that:

• : lines and do intersect.

• : lines and do not intersect.

The value of can be written in terms of points and direction vectors , as I will show on some future posts.

__________

The shortest distance game

It might seem a bit obscure that the one-stage 2-dimensional optimization problem

is equivalent to a two-stage optimization problem where at each stage one must solve a 1-dimensional optimization problem

.

Personally, I like to look at this from a game-theoretic viewpoint. Let us play a sequential game! We shall call the shortest distance game. I play first, then you play:

1. I choose a value for , I tell you what I chose.
2. You then choose such that is minimized.

Note that you are required to play optimally, i.e., to minimize distance. Hence you have no freedom in the choice of : you choose as a response to my choice of . Your choice is now coupled to mine, and thus, we are left with only one degree of freedom, the choice of . I now choose the value of which minimizes

.

Fortunately, I can use calculus to find the minimizer . Trying all values in for parameter would be rather tedious ;-)

__________

Appendix A

Note that the value of parameter which minimizes the distance is the same that minimizes the squared distance . Finding the minimizer of the squared norm is much easier, thus we introduce a cost function defined as

.

Differentiating with respect to , we obtain

The first derivative of must vanish at extrema. From the geometry of the problem, we know that there are no maxima (note that the cost function is unbounded above). Therefore we can find minima by checking the first derivative alone, without having to check the second derivative. We have

,

and since , the minimizer is

.

Note that this minimizer depends on the value of fixed parameter .

__________

Appendix B

We would like to show that vectors and are orthogonal. Recall that , and thus

.

Multiplying both sides on the left by , we obtain

and since (recall that ), then we finally have

,

which means that vectors and are orthogonal.

__________

Related:

• About Lines and Distance of a Point to a Line (by Dan Sunday)

• Distance between Lines and Segments with their Closest Point of Approach (by Dan Sunday)

Discrete Mechanics and Optimal Control

Last November 25, Prof. Jerrold Marsden (Caltech) was at UC Berkeley to give a lecture on Discrete Mechanics and Optimal Control (flyer / video):

If you are interested in Discrete Mechanics and Optimal Control, I suggest you take a look at these papers:

• Discrete mechanics and optimal control (by Junge, O., J. E Marsden, and S. Ober-Blöbaum)

• Discrete Mechanics and Optimal Control for Constrained Multibody Dynamics (by Leyendecker S., S. Ober-Blöbaum, J.E. Marsden, and M. Ortiz)

• A Discrete Geometric Optimal Control Framework for Systems with Symmetries (by Marin Kobilarov, Mathieu Desbrun, Jerrold E. Marsden, and Gaurav S. Sukhatme)

Related:

• Variational Integrators