Detecting Currency Arbitrage with Negative-Cycle Algorithms

# When looking for arbitrage among a LARGE amount of assets, is there an optimal way?


# When looking for arbitrage among a LARGE amount of assets, is there an optimal way?












Looking for arbitrage opportunities when looking at 3 pairs of related currencies is easy. However if we assume that we have a large amount of currencies, is there an optimal way to swipe through them and checking the vast amount of different possible permutations? I haven't been able to find any research so far and the main problem is that I'm not entirely sure how to look for this.

Thank you

## Answer by Dimitri Vulis (score 10)

https://quant.stackexchange.com/a/63313

For example, Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms, problem 24-3 says:

> 24-3 Arbitrage Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 U.S. dollar buys 49 Indian rupees, 1 Indian rupee buys 2 Japanese yen, and 1 Japanese yen buys 0.0107 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy 49 $\times$ 2 $\times$ 0.0107 = 1.0486 U.S. dollars, thus turning a profit of 4.86 percent. Suppose that we are given $n$ currencies $c_1, c_2, \ldots , c_n$ and an $n \times n$ table $R$ of exchange rates, such that one unit of currency $c_i$ buys $R[i, j]$ units of currency $c_j$. a. Give an efficient algorithm to determine whether or not there exists a sequence of currencies $<c_{i_1}, c_{i_2}, \ldots , c_{i_k}>$ such that $R[i_1, i_2] \cdot R[i_1, i_2] \cdots R[i_{k-1}, i_k] \cdot R[i_k, i_1] > 1$ Analyze the running time of your algorithm. b. Give an efficient algorithm to print out such a sequence if one exists. Analyze the running time of your algorithm.

Selected Solutions says:

> Solution to Problem 24-3 a. We can use the Bellman-Ford algorithm on a suitable weighted, directed graph $G =(V,E)$, which we form as follows. There is one vertex in $V$ for each currency, and for each pair of currencies $c_i$ and $c_j$, there are directed edges $(v_i,v_j)$ and $(v_j,v_i)$. (Thus, $|V|= n$ and $|E|= n(n - 1)$.) To determine edge weights, we start by observing that $R[i_1, i_2] \cdot R[i_1, i_2] \cdots R[i_{k-1}, i_k] \cdot R[i_k, i_1] > 1$ if and only if $\dfrac{1}{R[i_1, i_2]} \cdot \dfrac{1}{R[i_1, i_2]} \cdots \dfrac{1}{R[i_{k-1}, i_k]} \cdot \dfrac{1}{R[i_k, i_1]} < 1$. Taking logs of both sides of the inequality above, we express this condition as $\lg\dfrac{1}{R[i_1, i_2]} + \lg\dfrac{1}{R[i_1, i_2]} + \cdots +\lg\dfrac{1}{R[i_{k-1}, i_k]} +\lg \dfrac{1}{R[i_k, i_1]} < 0$. Therefore, if we define the weight of edge $(v_i,v_j)$ as $w(v_i,v_j) = \lg \dfrac{1}{R[i, j]} = -\lg R[i, j]$. then we want to find whether there exists a negative-weight cycle in $G$ with these edge weights. We can determine whether there exists a negative-weight cycle in $G$ by adding an extra vertex $v_0$ with $0$-weight edges $(v_0, v_i)$ for all $v_i \in V$, running Bellman-Ford from $v_0$, and using the boolean result of Bellman-Ford (which is TRUE if there are no negative-weight cycles and FALSE if there is a negative-weight cycle) to guide our answer. That is, we invert the boolean result of Bellman-Ford. This method works because adding the new vertex 0 with 0-weight edges from 0 to all other vertices cannot introduce any new cycles, yet it ensures that all negative-weight cycles are reachable from $v_0$. It takes $\Theta(n^2)$ time to create $G$, which has $\Theta(n^2)$ edges. Then it takes $O(n^3)$ time to run Bellman-Ford. Thus, the total time is $O(n^3)$. Another way to determine whether a negative-weight cycle exists is to create $G$ and, without adding $v_0$ and its incident edges, run either of the all-pairs shortest-paths algorithms. If the resulting shortest-path distance matrix has any negative values on the diagonal, then there is a negative-weight cycle. b. Assuming that we ran Bellman-Ford to solve part (a), we only need to find the vertices of a negative-weight cycle. We can do so as follows. First, relax all the edges once more [pp 648ff]. Since there is a negative-weight cycle, the $d$ value of some vertex $u$ will change. We just need to repeatedly follow the $\pi$ values until we get back to $u$. In other words, we can use the recursive method given by the PRINT-PATH procedure of Section 22.2, but stop it when it returns to vertex $u$. The running time is $O(n^3)$ to run Bellman-Ford, plus $O(n)$ to print the vertices of the cycle, for a total of $O(n^3)$ time.

Someone's sample code is in github. I am not sure if it's implemented correctly.

Related question: https://stackoverflow.com/questions/2282427

Related dicussion: https://www.thealgorists.com/Algo/ShortestPaths/Arbitrage

Related class notes on Bellman-Ford: http://cseweb.ucsd.edu/classes/sp20/cse101-a/Slides/Week-09/Lec-29.pdf

(I wonder if additional optimization is possible when the matrix is sparse because some currency pairs are not quoted. Also I wonder how people handle non-linear costs, e.g. fixed fees, or exchange rates that change depending on the size of the rate.)

## Answer by Bob Jansen (score 3)

https://quant.stackexchange.com/a/63310

I feel this is not a duplicate of a question asking about applications of graph theory as this goes the other way.

If you're talking purely about currency arbitrage, the quickest way seems to be finding a negative cycle in a graph of currency where the vertices are the currencies and the nodes the exchange rate.