A few months ago, I had the crazy idea of writing some code to automatically detect currency arbitrage given current foreign exchange rates. The brilliant plan was to (1) develop this evil-genius program (2) unleash it upon the market (3) and profit. Okay, not really, but the thought did cross my mind when for some unknown reason I was reminiscing about homework problems from my introductory data structures class. One of the problems involved looking for currency arbitrage in a graph of exchange rates, albeit it was a simplified exercise in depth-first search. The actual problem involves looking for a sequence of currency exchanges (a path in the graph) that starts at a given currency and ends up with more units of that currency than we started with. This problem is straight out of CLRS, and there are various solutions to it floating around on the web. Nevertheless, I decided to give it a go and see if arbitrage situations can really be found using real-world exchange rates.
Foreign exchange rates can be represented by a graph where each currency type is a vertex, and directed edges between vertices indicate the exchange rate. That is, weight w(u, v) for edge (u, v) means that one unit of currency u buys w(u, v) units of currency v. Since the goal is to simply end up with more money than we started with, we want to look for cycles in the graph where the product of the edge weights (that is, the product of all the exchange rates) is greater than 1. The first key observation is the product of edge weights can be reduced to a sum of the logarithm of the edge weights. Once we’re dealing with sums, the problem is reduced to searching for positive-weight cycles in the graph. By inverting the sums to look for negative-weight cycles instead, we can use the Bellman-Ford algorithm.
To start, we’ll read the currency exchange rates from STDIN. To make this exercise more applicable to the real world, we should include a fixed transaction cost for each exchange rate. Later on, we’ll see how this affects the outcomes.
#!/usr/bin/ruby
TRANSACTION_COST = 0.00001
# Initialize graph from currency exchange rates
rates = {}
graph = {}
STDIN.read.split("\n").each do |line|
c_1, r, c_2 = line.split(' ')
r = r.to_f * (1.0 - TRANSACTION_COST)
w = Math.log10(r)
graph[c_1] ||= {}
graph[c_1][c_2] = -1.0 * w
rates[c_1] ||= {}
rates[c_1][c_2] = r
end
Since the Bellman-Ford algorithm computes shortest path values for a single source in a graph, we can add a dummy “root” vertex to the graph and use it as the source. By adding a zero-weight edge between the root vertex and all other vertices, we ensure that no new negative-weight cycles are introduced.
# Add a dummy root node
root = 'Root'
graph[root] = {}
graph.each_key { |v| graph[root][v] = 0.0 }
# Initialize distances and predecessors
dist = {}
pred = {}
graph.each_key { |v| dist[v] = Float::MAX }
dist[root] = 0
The algorithm works by “relaxing” each edge in the graph n - 1 times, where n is the number of vertices. It has been shown that after n - 1 relaxations on each edge, the shortest paths to each vertex will be found. During all iterations of the algorithm, an estimate of the cost of the shortest path from the source to each vertex is kept. When an edge is relaxed, the algorithm checks whether or not the shortest path estimate can be improved by going through the edge, and updates the estimate accordingly.
# Relax every edge n - 1 times
(graph.keys.size - 1).times do
graph.each do |v_1, e|
e.each do |v_2, w|
if dist[v_2] > dist[v_1] + w
dist[v_2] = dist[v_1] + w
pred[v_2] = v_1
end
end
end
end
Intuitively, it makes more sense to think of the relaxation in terms of a rubber band wrapped around nobs on a surface, which are the vertices. As the initial estimate for a path is high, the rubber band is stretched and represents a high upper bound on the shortest path. When the rubber band is “relaxed,” the worst case shortest path estimate gets smaller; eventually the optimal path value is found.
The main reason for using the Bellman-Ford algorithm is to detect negative-weight cycles. In a graph without negative-weight cycles, all calculated shortest path values will be optimal after n - 1 iterations. For any vertices in a negative-weight cycles, the shortest path is actually undefined, since the cycle can be traversed an arbitrary number of times in order to decrease the path cost. Thus, to detect negative-weight cycles, we can simply attempt to relax every edge one more time. If any edges are relaxed (i.e. the shortest path estimate for one of the vertices improves), that means there’s a negative weight cycle. We can also use this opportunity to keep track of the actual vertices in these cycles for later use.
# Relax every edge again to find negative-weight cycles
arbitrage = false
cyclic = {}
graph.each do |v_1, e|
e.each do |v_2, w|
if dist[v_2] > dist[v_1] + w
arbitrage = true
dist[v_2] = dist[v_1] + w
# Keep track of vertices in negative-weight cycles
cyclic[v_2] = true
end
end
end
if !arbitrage
puts "No arbitrage found."
exit
end
Once we have a list of the vertices in negative-weight cycles, we can go through each one and calculate the arbitrage sequences required to make some money. Note that as we relaxed each edge, we also stored the predecessor vertices. We can now use this information to backtrack from a vertex in a cycle and find the remaining vertices in the cycle. Since these paths are cyclic, we’ll also need to keep track of visited vertices.
To calculate the amount of money made by making currency exchange transactions in each sequence, we simply multiply all the rates together to get the amount of money we end up with in units of the initial currency.
# Calculate the arbitrage sequences
sequences = []
cyclic.each_key do |v|
# Recursively visit predecessors to trace vertices in cycle
visited = {v => true}
seq = []
p = v
begin
seq.push(p)
visited[p] = true
p = pred[p]
end while !p.nil? && !visited[p]
seq.reverse!.push(seq.first)
# Calculate the arbitrage amount
val = (0..seq.size - 2).inject(1.0) do |v, i|
v * rates[seq[i]][seq[i+1]]
end
sequences.push({:currencies => seq, :value => val})
end
Finally, it’s simply a matter of sorting the sequences by their potential profit gains.
# Output the sequences in descending order of value
puts "Arbitrage sequences:"
sequences.sort! { |a, b| b[:value] <=> a[:value] }
sequences.each do |s|
break if s[:value] <= 1.0
puts ("%.14f " % s[:value].to_s) + s[:currencies].inspect.to_s
end
Pretty straightforward, right? The interesting results are revealed when you actually apply the algorithm to actual market exchange rates. I opted to write a simple script to scrape the exchange rates off of XE.com. All it takes to gather the various exchange rates are a few Mechanize calls followed by a few DOM traversals.
The output of the script matches the expected input of the arbitrage program. That is, a string identifier for the first currency, a space, the decimal representation of the exchange rate, another space, then the string identifier for the second currency. A sample output may look like this:
USD 0.69546 EUR
USD 0.61482 GBP
USD 90.7400 JPY
EUR 1.43790 USD
EUR 0.88405 GBP
EUR 130.475 JPY
GBP 1.62650 USD
GBP 1.13116 EUR
GBP 147.589 JPY
JPY 0.01102 USD
JPY 0.00766 EUR
JPY 0.00678 GBP
Running the arbitrage program on the sample output, with a transaction cost of 0.00001 (1/10th of a basis point), yields:
Arbitrage sequences:
1.00063340703167 ["JPY", "GBP", "JPY"]
1.00063340703167 ["GBP", "JPY", "GBP"]
1.00062075657692 ["JPY", "GBP", "USD", "JPY"]
1.00061730566045 ["JPY", "GBP", "EUR", "JPY"]
According to the output, we can simply exchange Japanese Yen to British Pounds then back to Yen, and we’ll be rich. Time to head down to the bank! Wait, there’s got to be a catch, right? Let’s see what happens when we try it on real exchange rates.
In practice, foreign exchange transaction costs are an order of magnitude higher. As an example, we’ll use the commission costs from Interactive Brokers, which is one basis point of the trade value. To focus solely on foreign exchange trading, we’ll also ignore the exchange rates between currencies and precious metals (the rates from XE.com include metals such as silver, gold, platinum, and palladium). Taking these factors into account, here are the profitable arbitrage sequences for real exchange rates taken on October 17, 2010:
Arbitrage sequences:
1.00009725953714 ["ZAR", "JPY", "ZAR"]
1.00009725953714 ["JPY", "ZAR", "JPY"]
For this particular set of exchange rates, the only arbitrage opportunity lies in exchanging Japanese Yen and South African Rand. However, the gain is minuscule, at slightly less than one basis point. Additionally, if we look closer at the costs from Interactive Brokers, we’ll see that there’s also a minimum cost per transaction. Unless we trade at least $25,000-equivalent worth of currency each transaction, we incur costs of more than a basis point each time. Combine that with the fact that currency exchange rates are constantly changing and fluctuating makes it clear that making a sure profit by exploiting currency arbitrage isn’t a trivial matter. Just to get in the game, you’ll need very powerful computers, an ability to execute currency trades at a very high frequency, and a very large bankroll.
Comments