Arbitrage - Bellman-Ford. Algorithm
Description of the Bellman-Ford algorithm in currency and crypto trading
Suppose you are given a set of exchange rates between certain currencies and want to determine if arbitrage is possible, i.e., if there is a way you can start with some currency C and perform a series of barter transactions. When there is more than one C unit. Assume that
- Zero transaction costs
- The exchange rate does not fluctuate
- Small amount of items can be sold
The figure above shows such a chart.
Let's see what happens if I receive the exchange in the following order:
USD -> EUR -> CAD -> USD
Let's say we start with 10000 USD and then exchange it for EUR. We get 7410 EUR. Now I want to exchange this with CAD.
7410 EUR = 7410 * 1,366 = 10122 CAD
Now exchange this for USD.
10122 CAD = 10122 * 0,995 = 10071
We started with 10000 USD and ended with 10071 USD. That's a reasonable $71 profit.
Design an efficient algorithm to determine if arbitrage exists - a way to start with a single currency and convert back to multiple currencies through a chain of exchanges.
Solution:
The painting would be a great start to solving this problem.
The relationship between currencies can be graphed: the money will correspond to the vertices, the exchange rate corresponds to the edges, and the edge weights are set to the exchange rate as shown below.
Let's say we have two currencies A and B and consider some scenarios below:
1. Let's say the exchange rate A -> B = 1.5 and B -> A = 0.6667
Note that the product of the exchange rate is 1.5 * 0.67 = 1
So if we exchange 1 unit of A for B and whatever we get, we convert to A again and get 1 unit of A back.
2. Now suppose the exchange rate A -> B = 1.5 and B -> A = 0.5
Multiply the exchange rate = 1.5 * 0.5 < 1>3. If the exchange rate from A to B is 1.5 and B to A is 0.8 then since 1.5 * 0.8 > 1 and we will end up with more than 1 unit of A if we start for 1 unit of A, convert to B, and whatever we get after the conversion, we convert back from B to Profit > 0.
We can also extend this observation to more than two currencies.
-----------------------------------------------
Let's say we have two currencies A and B, and consider some problems below:
let's say exchange rate A -> B = 1.5 and B -> A = 0.6667
Note that the rating of the Exchange Rate is 1.5 * 0.67 = 1.
So if we exchange 1 unit of A for B and whatever we get, we convert back to A we get 1 unit of A back.
Now suppose the exchange rate A -> B = 1.5 and B -> A = 0.5
Multiply the exchange rate = 1.5 * 0.5 < 1>If the A to B Exchange Rate is 1.5 and B to A is 0.8 then because 1.5 * 0.8 > 1. We will end up with more than 1 A unit if we start with 1 A unit, convert to B and whatever we receive after conversion, we convert back from B to Profit > 0.
We can also extend this observation to more than two currencies.
-----------------------------------------------
From the above discussion, we can say that if we represent the relationship between different currencies through a chart, as discussed above, the arbitrage situation will occur when the result of the weight multiplication of all edges forms a period greater than 1.
Suppose the exchange rate from A to B is a, B to C is b, and C to A is c.
Then we have a spread only if
a * b * c > 1
In the chart above, the exchange rate of
USD to EUR is 0.741,
EUR to CAD is 1.366,
CAD against USD is 0.995
Multiply these exchange rates = 0.741 * 1.366 * 0.995 = 1.007 > 1
So we have a multiplication relationship here. But the most popular graph algorithms are not well known for representing multiplication relationships and doing something meaningful. But if we can convert this multiplication relationship into some ADDITIONAL relationship, we can do something. We can restore the currency exchange relationship into an additive relationship where we can add edge weights and determine if a price difference exists based on the sum of the weights. Several edges of the cycle, we can then reconstruct the condition to get the spread like something like:
An arbitrage exists if the sum of the weights of the edges forming the cycle is greater than or less than a threshold. This threshold value will depend on how we convert the multiplication relationship to the additive relationship.
So if we have x * y = z, how do we get the additive relationship between x and y?
We know the logarithm of two or more variables that lead to the addition of the logarithm of each of these variables.
log(x*z*y) = log(x) + log(y) + log(z)
We also know
if we have a variable A then
logA = 0 if A = 1, every positive real number to the power of ZERO is ONE.
logA > 0 if A > 1
logA < 0>Assume A = 0.5
then we can also write A = 1/5
or, A = 5 -1
Therefore, logA = log(5-1) = -log5 < 0>
So use the following mathematical equations
a * b * c > 1
=> log(a * b * c) > log(1)
=> loga + logb + logc > 0, vì log1 = 0
Now the solution comes down to this; if the logarithm of the exchange rate multiplication of some currency forming a cycle is more significant than ZERO, then we have the arbitrage.
Or, as we saw above: if the logarithmic sum of each exchange rate is more significant than ZERO, then we have a price difference. This brings us to a conclusion: if we modify the graph and make the edge weights represent the logarithm of the exchange rate, then the price difference will form a cycle with the sum of all the edges developing process is more significant than ZERO. In short-term arbitrage, a positive weight cycle will begin if we have exchange rates such as A, B and C. In our previous graph, A, B and C would be the weights of the 'three sides.' According to the above discussion, we will modify the graph and the weights of the same edges will be logA, logB and logC instead of A, B and C. The graph will now look like that. This is when we take the base log e or ln:
We saw earlier that USD -> EUR -> CAD -> USD forms an arbitrage. Now let's see what the sum of the edge weights yields.
Edge Weight for USD -> EUR = ln (0.741) = -0.2998
Edge Weights for EUR -> CAD = ln(1.366) = 0.3119
Edge Weight of CAD -> USD = ln(0.995) = -0.005
(-0.2998) + (0.3119) + (-0.005) = 0.0071 > 0
So we have a sum greater than ZERO, as expected.
So now, the solution is reduced to finding the period of positive weights in the modified graph.
We have discussed in the previous two chapters how the Bellman-Ford Algorithm finds the period of negative weights in a graph very efficiently. So why not take advantage of that? We can modify the chart to transform the problem from finding a period of positive weights to cycles of negative weights. We can achieve this by negating the weights of all edges.
Algorithm:
1. Create a directed graph where the vertices are currencies and the weights of the edges are the negative logarithms of the currencies' exchange rates represented by the vertices to which the edges are joined.
For example, if the exchange rate of currency A to currency B is E, then in the graph, the directed edge connecting A to B will weigh (-lnE).
2. Find out if there is a negative balance period.
In the Crypto market, we have liquidity pools that exist under coin or token pairs. Applying the Bellman-Ford algorithm will help us have many arbitrage opportunities in the crypto market.