Bellman-Ford Algorithm’s Applications – Triangular Arbitrage

A very interesting application of the bellman-ford algorithm is arbitrage, essentially, given a table of currencies and their exchange rates, one needs to be able to figure out if we can start with a certain amount of money in one currency, exchange this amount for other currencies and end up with more money than what we had at first.

Example: 1 USD gives us 0.8 Euro and 1 Euro gives us 0.8 GBP and 1 GBP gives us 1.7 USD. So if I start with 1 dollar, I can exchange it for 0.8 Euro which can then be exchanged for 0.64 GBP and if converted back to USD we have 1.088 dollars.

So if rate_i_j is used to represent the amount of currency_j which we can get for 1 unit of currency_i, we observe:

rate_i_j * rate_j_k * rate_k_l * ….. * rate_z_i > 1

Invert this to get:

1/(rate_i_j * rate_j_k * rate_k_l * ….. * rate_z_i) < 1

and take lg on both sides:

lg(1/rate_i_j) + lg(1/rate_j_k) + ….. + lg(1/rate_z_i) < 0

So we observe that if we represent our table using a graph with lg(1/exchange_rate) as the weights, then the presence of a negative weight cycle is all that is needed to ensure we get more $$ than we started out with.

And of course, negative weight cycle detection is really easy with the bellman-ford single source shortest path algorithm.

This algorithm operates by the following dynamic programming equation:

distanceFromSource(v) = distanceFromSource(w) + weight(w, v)

When we set the distance of vertex ‘v’ from the source, we look at the edge (w, v) and observe that if we can get to ‘v’ by a shorter path through ‘w’, we discard the old distance and set distanceFromSource(w) + weight(w, v) as the new distance. This operation is called “Relaxing an edge”

Now, we only need to observe every edge a certain number of times. Precisely |V| – 1 times. Why? Well, consider a graph where the max out-degree is 1.

So, we have something like: v1 —-> v2 —–> v3 —–> v4 ——> …….. ——> v{n}. This is a directed graph with n vertices. If our source is v1, in the first of |V| – 1 iterations, we relax the first edge and fix the path to v2 (cannot get to v2 using a shorter path see?). In the second iteration, the path to v3 is fixed and continuing this we finish fixing the paths to the vertices |V| – 1 iterations (Remember, you relax every edge in each iteration).

To detect a negative weight cycle, finish relaxing all the edges |V| – 1 times. Now, carry the relax operation out once again. Since, all paths from the source to each vertex are guaranteed to be fixed by now, if you ever stumble upon a situation where you change distanceFromSource(v) for a vertex v, then a negative weight cycle starts and ends at v. The result of this is that a shortest path to v cannot be found, since for every path to v, you can make another trip about this negative-weight cycle and obtain an even shorter path.

So, I wrote a simple script for the Bellman-Ford routine and tested it using the USD, Euro, GBP example.

Here’s the Bellman-Ford routine:

And the test itself:

And when run, I get:

?(shriphani@Shriphani-Palakodetys-MacBook-Pro)?(533/ttys001)?(09:10P:07/02/10)?-
??(%:~/scripts)?- python arbitrage_test.py
usd
??(shriphani@Shriphani-Palakodetys-MacBook-Pro)?(534/ttys001)?(09:10P:07/02/10)?-
??(%:~/scripts)?-

So, there’s a negative weight cycle and if you kick off with some USD, you can get rich.

Get my routines here:

• Bellman-Ford
• Test For Arbitrage

My code reads too much like pseudocode. Didn’t know a theory class corrupts so much.