by zermelozf   Last Updated October 15, 2018 18:20 PM

When googling for a solution to the currency arbitrage problem, a variant of the Bellman-Ford algorithm comes up as the most efficient solution. See for example this page or this stackexchange post.

Trying to solve the problem with a friend, we came up with what we think is a simpler solution with the same O(n^3) time complexity that does not involve any fancy names like Bellman-Ford. We are not sure however that our solution is indeed correct (seems a bit simple) and wanted your help to have it proof-read in case something escaped us. Thanks in advance for your help.

I describe the solution below and attached the complete (dead simple) algorithm in python at the end of this post.

An arbitrage opportunity occurs when you can exchange a currency into another and repeat the process until you end up with more of the initial currency in your hands.

In the following, we denote $$r_{ab}$$ the exchange rate between currency A and currency B. To avoid simple aribtrage opportunities, we should at least have $$r_{ab} * r_{ba} = 1.$$

Let's now assume no arbitrage opportunity exists using three or fewer currencies but that there is one for four currencies, that is A -> B -> C -> D -> A leads to an increase in currency A. Then we should have

$$r_{ab}*r_{bc}*r_{cd}*r_{da} \gt 1. \tag 1$$

Moreover, because A -> B -> C -> A involves only three currencies, there is no possible arbitrage and thus $$r_{ab}*r_{bc}*r_{ca} = 1. \tag 2$$ Similarly, $$r_{ac}*r_{ca}=1. \tag 3$$

From (1) and (2), we can write:

$$r_{cd}*r_{da} > r_{ca}. \tag 4$$

And using (3), we have $$r_{cd}*r_{da}*r_{ac} > 1$$, leading to the arbitrage with three currencies C -> D -> A -> C.

I believe we can use the same method to recursively prove that if there is a possible arbitrage with $$n+1 (n>=3)$$ currencies, there should be an arbitrage with $$n$$ currencies.

Using the above proof, we should be able to safely say that, if there is no arbitrage with three or fewer currencies, then there is no arbitrage at all.

Therefore, a simple algorithm to check for the existence of arbitrage would be as follow (with $$r$$ the exchange rate matrix and $$n$$ the number of currencies available):

``````def arbitrage(r):
for i in range(n):
for j in range(n):
for k in range(n):
if r[i, j] * r[j, k] * r[k, i] > 1:
return True
return False
``````

Is there something we missed?

Tags :