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:
My code reads too much like pseudocode. Didn’t know a theory class corrupts so much.
