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:

#!/usr/bin/env python
#Author: Shriphani Palakodety

#Bellman Ford Implementation. Look it up on wikipedia.

distances = {}
parents = {}

def Initialize(graph, start):
    '''Prepares the graph for the bellman-ford algorithm'''
    for vertex in graph.V:
        if graph.E.has_key((start, vertex)):
            distances[vertex] = 9999999e6

    distances[start] = 0
    parents[start] = None

def Bellman_Ford(graph, start):

    Initialize(graph, start) #first initialize the graph

    for i in xrange(len(graph.V) - 1):
        for edge in graph.E.keys():
            if (graph.E[edge] + distances[edge[0]]) < distances[edge[1]]:
                distances[edge[1]] = graph.E[edge] + distances[edge[0]]
                parents[edge[1]] = edge[0]

    #one final check for negative weight cycles.

    for edge in graph.E.keys():
        if (graph.E[edge] + distances[edge[0]]) < distances[edge[1]]:
            distances[edge[1]] = graph.E[edge] + distances[edge[0]]
            parents[edge[1]] = edge[0]
            return edge[1] #return here since, a negative weight cycle is detected

    return None #return none on successful completion.

And the test itself:

!/usr/bin/env python
#Author: Shriphani Palakodety
#Mail: spalakod@purdue.edu

#Testing Arbitrage

#import graph
import bellman_ford
from math import log

#in the format cur1_cur2 = no. of units of cur2 for 1 unit of cur1

usd_euro = 0.8
euro_gbp = 0.8
gbp_usd = 1.7

#Nodes List
nodes = ["usd", "euro", "gbp"]
edge_dict = { ("usd", "euro") : log(1/usd_euro), ("euro", "gbp") : log(1/euro_gbp), ("gbp", "usd") : log(1/gbp_usd), ("euro", "usd") : log(usd_euro), ("gbp", "euro") : log(euro_gbp), ("usd", "gbp") : log(gbp_usd)}
#make a small graph to represent the currency network.

cur_graph = bellman_ford.Graph(nodes, edge_dict)

print bellman_ford.Bellman_Ford(cur_graph, "usd")

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.