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

Any chance you'd share this code? It looks like something I could use in a ruby project I'm working on. Thanks

ReplyDeleteSure, feel free to use the code. If you could provide attribution in the form of a link to this post, that would be great :)

DeleteMinor comment: 1 basis point = 0.01%, not 0.00001

ReplyDeleteThe example transaction cost used was 1/10th of a basis point.

DeleteI have a question:

ReplyDeleteGBP 1.62650 USD

USD 0.61482 GBP

1 * 1.62650 * 0.61482 = 1.00000473

so there is an arbitrage 'cycle': GBP, USD, GBP?

Am I missing something?