Dead simple arbitrage algorithm

algorithmsgraph theory

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

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 \to B \to C \to D \to 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 \to B \to C \to 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 \to D \to A \to C$.

I believe we can use the same method to recursively prove that if there is a possible arbitrage with $n+1$ (where $n \geq 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?

Best Answer

The proof is clearly wrong: you can only conclude that 2/3-cycles evaluate to $\leq 1$. In your example the only way to add in a cycle is to multiply with something that closes a cycle (like $r_{ca}$) but then you have to divide it out and you are back at the beginning. Multiplying with $r_{ca}r_{ac}$ does not work as this is $\leq 1$ in general and thus the inequality goes in the wrong direction.

Related Question