Detecting Arbitrage in Foreign Exchange Markets

From EPI:

Suppose you are given a 2D matrix representing exchange rates between currencies. You want to determine if arbitrage exists in the market (i.e. if there is a way to start with a single unit of some currency C and convert it back to more than one unit of C through a sequence of exchanges).

Input: [
    [1.0,  2.0, 1.0],
    [0.5,  1.0, 4.0],
    [1.0, 0.25, 1.0]
]
Output: True

# Arbitrage Path:
# Value (idx)
# 1.0 (0) -> 2.0 (1) -> 8.0 (2) -> 8.0 (0)

We’re looking for a sequence of exchanges that lead to a specific kind of outcome. One might consider defining a DFS-style function that recursively calls itself and maps out all possible sequences, but it would be difficult to define a terminus for such an approach:

def has_arbitrage(M):
    def DFS(src, i, value):
        if i == src and value > 1:
            return True

        for j in range(n):
            if j != i:
                DFS(src, j, value * M[i][j])

        # ...

Consider the input we’ve been given –– doesn’t it already remind you of an adjacency matrix? The indices in the 2D array represent each currency type and we already have the conversion rates between every pair of currencies.

In this light, let’s see how we can think of these currencies and their conversion rates as components of a graph, with currency types as nodes and conversion rates as edges.

Arbitrage as Cycles

We want a series of conversions that:

• Lead us back to the original currency we started with
• Earn us more units of the original currency

In graph terms, you can imagine this to be a cycle with some kind of positive net “gain” to it. Defining what this “gain” looks like is a bit awkward, since we’re dealing with rates rather than weights. We can’t simply add up edge weights –– instead, we’d have to multiply them.

"""
Converting currency `a` to `b`:
(a) ---------> (b) 
1.0  *  0.5 =  0.5
"""

We can use the properties of logarithms to help us work around this:

"""
Let r(x, y) denote the rate of converting
one unit of x to one unit of y. 

If there's no arbitrage, we expect:

Balance = r(a, b) * r(b, c) * r(c, a) = 1


Wrapping the expression with logarithms:

Balance = log(r(a, b) * r(b, c) * r(c, a)) 
        = log(r(a, b)) + log(r(b, c)) + log(r(c, a)) 
        = log(1)
        = 0
"""

By applying a logarithmic conversion on the matrix we’ve been given, we can deal with the weights as if they were raw values to be summed, rather than rates to be multiplied. Note that doing this isn’t strictly necessary for solving the problem, but it does help us place the graph in a more familiar context.

def has_arbitrage(M):
    
    n = len(M)

    for i, j in itertools.product(range(n), repeat=2):
        M[i][j] = math.log2(M[i][j])

If the logarithms of our conversions (starting from a given currency and circling back to itself) sum to a positive number, then we’ll know that arbitrage exists in the market. Our problem now reduces to that of finding a positive weight cycle in a graph.

Cycle Detection

Intuituively, detecting a positive weight cycle shouldn’t be too different from finding a negative weight one, since the difference only lies in the sign. We can simply flip the weights of all the edges in our graph and then run a standard Bellman-Ford algorithm, since any positive cycle in a graph would be a negative cycle if all its weights were flipped.

def has_arbitrage(M):
    
    n = len(M)

    for i, j in itertools.product(range(n), repeat=2):
        M[i][j] = -math.log2(M[i][j])

    # Min attainable value from arbitrary source currency
    D = [math.inf for _ in range(n)]
    D[0] = 0 # Source currency at idx 0, starts with 0
 
    # Run Bellman-Ford
    for _ in range(n):
        for i, j in itertools.product(range(n), repeat=2):
            D[j] = min(D[j], D[i] + M[i][j])
    
    # Check for negative cycle
    for i, j in itertools.product(range(n), repeat=2):
        if D[i] + M[i][j] < D[j]:
            return True

    return False

With the help of a few logical steps, we were able to turn into the problem into one that we’re a lot more accustomed to seeing. It’s worth mentioning that, instead of changing our inputs to match the nature of Bellman-Ford, we can tweak Bellman-Ford itself to suit our needs.

Alternative Take

To detect arbitrage differently, we’ll run a modified version of Bellman-Ford where we:

• Keep track of the units of attainable value from one unit of a random source currency (e.g. index 0)
• Relax edges in the opposite manner by attempting to maximise value wherever possible
• Detect a positive cycle by seeing if the units of attainable value can still be increased after all edges have been considered n times

def has_arbitrage(M):

    # Max attainable value from source
    D = [0 for _ in range(len(M))]
    D[0] = 1 # Source currency at idx 0, start with 1 unit

    for _ in range(len(M)):
        for i, j in itertools.product(range(len(M)), repeat=2):
            D[j] = max(D[j], D[i] * M[i][j])

    for i, j in itertools.product(range(len(M)), repeat=2):
        if D[i] * M[i][j] > D[j]:
            return True

    return False

One might argue that this approach is more intuitive. We’re 1) starting with a single unit of some currency, 2) converting it into other currencies, and 3) seeing if we’re able to repeatedly increase our units of value.

Given n currencies, our algorithm runs in O(n^2) space and O(n^3) time.

With that, we’ve solved the Detecting Arbitrage in Foreign Exchange Markets problem 💵🏦💰.

Full Solution

def has_arbitrage(M):
    
    n = len(M)

    # Apply log on edges, flip signs
    for i, j in itertools.product(range(n), repeat=2):
        M[i][j] = -math.log2(M[i][j])

    # Track shortest "dist" from source for each node
    D = [math.inf for _ in range(n)]
    D[0] = 0
 
    # Run Bellman-Ford
    for _ in range(n):
        for i, j in itertools.product(range(n), repeat=2):
            D[j] = min(D[j], D[i] + M[i][j])
    
    # Check for -ve cycles
    for i, j in itertools.product(range(n), repeat=2):
        if D[i] + M[i][j] < D[j]:
            return True

    return False