1
$\begingroup$

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

$\endgroup$
1
10
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Incredibly helpful, also really appreciate the extra links at the end, have a great day! $\endgroup$
    – Hiperfly
    Apr 10 at 11:21
  • 1
    $\begingroup$ 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? $\endgroup$ Apr 10 at 15:59
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 10 at 16:10
  • $\begingroup$ Non-linear costs, such as slippage? $\endgroup$ Apr 10 at 16:37
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.