# 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

• Apr 10 at 12:02

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 $$$$ 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.)

• Incredibly helpful, also really appreciate the extra links at the end, have a great day! Apr 10 at 11:21
• In practical applications, how would one then factor in trading fees and spread? In markets today, triangular (or polynomial) arbitrage opportunities are fleeting. A sure way to fill your order immediately would be to 'cross the spread', meaning you would always be buying at a higher price and selling at a lower price. Could these impacts be costed directly into the exchange rate itself? Apr 10 at 15:59
• This already doesn't assume that R[i,j]=R[j,i], i.e. can have bid-ask spread. I see no reason not to include in R other linear fees/spreads. But I wonder what people do about non-linear costs. Apr 10 at 16:10
• Non-linear costs, such as slippage? Apr 10 at 16:37

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.