dead simple arbitrage algorithm

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?

Related Questions

Constructing a random bipartite graph

Updated January 11, 2017 08:08 AM