Check Currency Arbitrage with Bellman Ford

Problem

Suppose you are given a table of currency exchange rates, represented as a 2D array. Determine whether there is a possible arbitrage: that is, whether there is some sequence of trades you can make, starting with some amount A of any currency, so that you can end up with some amount greater than A of that currency.

There are no transaction costs and you can trade fractional quantities.

Examples

Example 1

Note that diagonal values are equal to one.

We have a graph like this:

Solution

Method 1 - Bellman-Ford Algorithm

When represented as a graph, the vertices correspond to the currencies, and the edges correspond to the exchange rates. Since our table is complete, the graph is also complete. The key insight is to transform the multiplicative nature of exchange rates into an additive one by taking the logarithm of the rates and negating them. Then, to solve this problem, we need to find a cycle whose edge weights product is greater than 1.

This transformation turns the problem of finding an arbitrage opportunity into detecting a negative-weight cycle in the graph.

Lemma Any amount of currency u can be obtained from currency S if and only if u is reachable from some node w where dist[w] decreased during the V-th iteration of Bellman-Ford.

We have already seen:

• Bellman-Ford 1 - Single Source Shortest Path in a Directed Graph (Given there is a negative cycle in a graph)
• Bellman-Ford 2 - Use to detect negative cycles

We know that:

log(a * b) = log(a) + log(b)

Taking the negative log of edge weights transforms the search for a product greater than 1 into a search for a negative sum cycle.

For example, say we have a weighted edge path a -> b -> c -> d. Since we want to see if a * b * c * d > 1, we’ll take the negative log of each edge:

-log(a) -> -log(b) -> -log(c) -> -log(d).

The total cost of this path will then be

-(log(a) + log(b) + log(c) + log(d)) = -log(a * b * c * d).

Since -log(x) < 0 if x is greater than 1, finding a negative cycle indicates that the edge weights’ product is greater than 1, revealing arbitrage. Bellman-Ford helps detect negative cycles, implying that its detection signifies an arbitrage opportunity.

To refresh, Bellman-Ford finds the shortest paths in a graph. If a graph has negative cycles, further relaxation identifies them. Starting with any vertex in a complete graph will discover any negative cycle. If another path is found after ( |V| - 1 ) iterations, a negative cycle exists.

Detect Infinite Arbitrage

1. Perform ( |V| ) iterations of Bellman-Ford; save nodes relaxed on the ( V )-th iteration to set ( A ).
2. Place nodes from ( A ) in queue ( Q ).
3. Use BFS with queue ( Q ) to find nodes reachable from ( A ). These nodes indicate possible infinite arbitrage.

Reconstruct Infinite Arbitrage

1. During BFS, track the parent of each visited node.
2. Reconstruct the path to ( u ) from node ( w ) relaxed on iteration ( V ).
3. Trace back from ( w ) to find the negative cycle reachable from ( w ).
4. Use this cycle to achieve infinite arbitrage from ( S ) to ( u ).

Steps:

We can take following steps:

1. Log Transformation:
   • Convert exchange rates to log values and negate them. This way, we transform the problem into finding negative cycles.
2. Bellman-Ford Algorithm:
   • The Bellman-Ford algorithm is used to find the shortest path from a single source to all other vertices in a graph. By performing up to (V-1) relaxations (where (V) is the number of vertices), we ensure the shortest paths are correctly calculated. If further relaxations are possible, it indicates a negative cycle (an arbitrage opportunity).
3. Checking for Negative Cycles:
   • After running the (V-1) relaxations, if you can still relax any edge, it confirms the presence of a negative-weight cycle.

Code

Java

public class ArbitrageDetection {

	public boolean detectArbitrage(double[][] exchangeRates) {
		int n = exchangeRates.length;
		double[][] logRates = new double[n][n];

		// Step 1: Transform the exchange rates to a log graph
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				logRates[i][j] = -Math.log(exchangeRates[i][j]);
			}
		}

		// Step 2: Use Bellman-Ford to detect negative weight cycles
		for (int source = 0; source < n; source++) {
			if (hasNegativeCycle(logRates, source)) {
				return true;
			}
		}

		return false;
	}

	private boolean hasNegativeCycle(double[][] graph, int source) {
		int n = graph.length;
		double[] dist = new double[n];
		Arrays.fill(dist, Double.POSITIVE_INFINITY);
		dist[source] = 0;

		// Step 3: Relax edges up to n-1 times
		for (int i = 0; i < n - 1; i++) {
			for (int u = 0; u < n; u++) {
				for (int v = 0; v < n; v++) {
					if (dist[u] != Double.POSITIVE_INFINITY && dist[u] + graph[u][v] < dist[v]) {
						dist[v] = dist[u] + graph[u][v];
					}
				}
			}
		}

		// Step 4: Check for negative cycles
		for (int u = 0; u < n; u++) {
			for (int v = 0; v < n; v++) {
				if (dist[u] != Double.POSITIVE_INFINITY && dist[u] + graph[u][v] < dist[v]) {
					return true;
				}
			}
		}

		return false;
	}
}

Complexity

• ⏰ Time complexity: O(V^3) where V is number of vertices(currencies).
  • Transforming the exchange rates into their negative logarithms involves iterating over all currency pairs, resulting in ( O(V^2) ) time complexity.
  • Bellman-Ford algorithm takes O(V.E), and since graph is complete, E = V^2, hence O(V^3).
  • Negative cycle detection takes O(V^2)
• 🧺 Space complexity: O(V^2)
  • Storing the weights of the graph (matrix of negative logarithms) requires O(V^2) space.
  • Distance array requires O(V)
  • Queue for BFS requires O(V)