Graph problems are always interesting and currency arbitrage is one of the standard graph problems from CLRS book (Introduction to Algorithms).
Few weeks ago, I stumbled upon this problem when I was reading about forex trading & transaction costs.
Arbitrage is defined as near simultaneous purchase and sale of securities or foreign exchange in different markets in order to profit from price discrepancies.
Forex arbitrage is a risk-free trading strategy that allows forex traders to make a profit with no open currency exposure. The strategy involves acting on opportunities presented by pricing inefficiencies in the short window they exist. This type of arbitrage trading involves the buying and selling of different currency pairs to exploit any pricing inefficiencies. The act of exploiting the pricing inefficiencies will correct the problem so traders must be ready to act quickly with arbitrage strategies. For this reason, these opportunities are often around for a very short time.
Suppose we are given a table of currency exchange rates, represented as a 2D array. Determine whether there is a possible arbitrage, i.e, whether there are certain sequence of trades you can make, starting with some amount A of any currency, such that you can end up with some amount greater than A of same currency.
Let’s say, 1 U.S. dollar bought 0.82 Euro, 1 Euro bought 129.7 Japanese Yen, 1 Japanese Yen bought 12 Turkish Lira, and 1 Turkish Lira bought 0.0008 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy U.S. dollars, thus turning a 0.82*129.7*12*0.008 =1.02 US dollars, thus making a 2% profit.
For the sake of simplicity, let’s assume there are no transaction costs and you can trade any currency amount in fractional quantities.
How do we solve this?
Graph data structure
Weighted directed graphs can be represented as an adjacency matrix. For a graph with |V| X |V| vertices, an adjacency matrix is a |V| times |V| matrix of values, where the entry in row i & column j is a non-zero integer if and only if the edge (i, j) is in the graph. If you want to indicate an edge weight, put it in the row i, column j entry, and reserve a special value (perhaps None) to indicate an absent edge.
Finding arbitrage
Arbitrage opportunities arise when a cycle is determined such that the edge weights satisfy the following expression
w1 * w2 * w3 * … * wn > 1
The above constraint of finding the cycles is harder in graphs. Instead we must transform the edge weights of the graph such that the standard graph algorithms can be applied.
Let’s take the logarithm on both sides, such that
log(w1) + log(w2) + log(w3) + … + log(wn) > 0
Taking the negative log, this becomes
(-log(w1)) + (-log(w2)) + (-log(w3)) + … + (-log(wn)) < 0
Therefore we can conclude that if we can find a cycle of vertices such that the sum of their weights if negative, then we can conclude there exists an opportunity for currency arbitrage. Luckily, Bellman-Ford algorithm is a standard graph algorithm that can be used to easily detect negative weight cycles in O(|V*E|) time.
Bellman Ford Algorithm
Let G(V, E) be a graph with vertices, V, and edges, E.
Let w(x) denote the weight of vertex x.
Let w(i, j) denote the weight of the edge from source vertex i to destination vertex j.
Let p(j) denote the predecessor of vertex j.
The Bellman-Ford algorithm seeks to solve the single-source shortest path problem. It is used in situations where a source vertex is selected and the shortest paths to every other vertex in the graph need to be determined. After applying Bellman-Ford algorithm on a graph, each vertex maintains the weight of the shortest path from the source vertex to itself and the vertex which precedes it in the shortest path. In each iteration, all edges are relaxed if [w(i) + w(i, j) < w(j)] and the weight of each vertex is updated accordingly. After the i-th iteration, the algorithm finds all shortest paths consisting of at most i edges.
Once all shortest paths have been identified, the algorithm loops through all of the edges and looks for edges that can further decrease the value of the shortest path. If we can still relax the edges, then a negative weight cycle has been found since a path can have at most |V-1| edges.
Printing a negative weight cycle is done to show the arbitrage opportunity. We use the predecessor chain to print the cycle. Now that we have an edge which can be further relaxed, we have found the source & destination vertex of such an edge. Let’s start from the source vertex and go backwards until you see the source vertex again or any other vertex that predecessor chain has already shown us while printing the negative weighted cycle.
In the real world scenario, it may be hard to find the arbitrage opportunity. It is advisable to take the negative logarithm of currency value after converting the floating point value with 2 decimal places and multiply that by 100 . This is beneficial such that we can avoid arbitrage opportunities which are less than 1%.
Conclusion
Bellman Ford algorithm can be used to find arbitrage opportunities among a given bunch of currencies represented as a graph. Normally these opportunities exist for a very short period of time, so someone interested in profiting from such a risk free transaction must act quick.
Next Steps ?
- Visualization: We can make use of visualization libraries to plot the graph and visualize the vertices and edges. This will make understanding the concept easier as we can see the negative weighted cycles consisting of vertices and edges in a different color.
- Real World Currency Arbitrage: Using dummy values or historical data might be great for learning purposes, but how about using the real time currency value data and finding arbitrage in real time ? There are tons of Forex rates API providers (like xe.com) that provide real time currency rates which can be used for this purpose.
