1,140 reads
Algorithmic Wizardry: Exploiting Graph Theory in the Foreign Exchange
by Anton YarkovOctober 28th, 2023
Too Long; Didn't Read
Following my previous endeavors, I keep playing with graphs and graph traversal algorithms in searching for a way for profitable currency exchange.
If you're familiar with the FinTech startup industry, you may have heard of Revolut, a well-known FinTech giant based in London, UK. Founded in 2015, Revolut has garnered substantial investments and become one of the fastest-growing startups in the UK, providing banking services to many European citizens.
While banking operations are often shrouded in mystery when it comes to how they generate revenue, some key figures about Revolut for the years 2020 and 2021 have shed some light on their income sources:
As illustrated, a significant portion of this neobank's revenue comes from Foreign Exchange (FX), wealth management (including cryptocurrencies), and card services. Notably, in 2021, FX became the most profitable sector.
A friend of mine, who is also a software engineer, once shared an intriguing story about his technical interview at Revolut's Software Engineering department a few years back. He was tasked with developing an algorithm to identify the most profitable way to convert two currencies using one or multiple intermediate currencies. In other words, they were looking for a strategy for Currency Arbitrage.
Currency Arbitrage is a trading strategy wherein a currency trader leverages different spreads offered by brokers for a particular currency pair through multiple trades.
It was explicitly mentioned in the task that the algorithm's foundation must be rooted in graph theory.
FX Basics
FX, or Foreign Exchange, plays a pivotal role in global trade, underpinning the functioning of our interconnected world. It's evident that FX also plays a substantial role in making banks some of the wealthiest organizations.
The profit generated from foreign exchange is primarily the difference or spread between the buying (BID) and selling (ASK) prices. While this difference might appear minuscule per transaction, it can accumulate into millions of dollars in profits given the volume of daily operations. This allows some companies to thrive solely on these highly automated financial operations.
In the realm of FX (Foreign Exchange), we always work with pairs of currencies, such as EUR/USD. In most cases, these exchanges are bidirectional (i.e., EUR/USD and USD/EUR), and the exchange rate value differs in each direction.
An Arbitrage Pair represents a numerical ratio between the values of two currencies (EUR and US Dollar, for example), determining the exchange rate between them.
Potentially, we can use multiple intermediate currencies for profitable trading, known as a sure bet.
Arbitrage sure bet is a set of pairs to be used in a circular manner. Read more
Many providers employ mathematical modeling and analysis to secure their own profits and prevent others from profiting off them. Hence, the term potentially is emphasized here.
Sure bet length refers to the number of pairs that constitute a set of potential arbitrage opportunities.
In the real world, exchange rates can vary among different banks or exchange platforms. It's not uncommon for tourists to traverse a city to find the best possible rate. With computer software, this process can be accomplished within milliseconds when you have access to a list of providers.
In practical profitable trades, multiple steps might involve conversions through various currencies across different exchange platforms. In other words, the Arbitrage Circle can be quite extensive.
Arbitrage Circle entails acquiring a currency, transferring it to another platform, conducting an exchange for other currencies, and ultimately returning to the original currency.
The exchange rate between two currencies via one or more intermediate currencies is calculated as the product of exchange rates of these intermediate transactions.
An example
For example, let's imagine we want to buy Swiss Franks for US Dollar, then exchange Franks to Japanese Yens, and then sell Yens for US Dollar again. In Autumn, 2023, we have following exchange rates:
-
We can buy 0.91 CHF (Swiss Frank) for 1 USD.
-
We can buy 163.16 Japanese Yens for 1 CHF.
-
We can buy 0.0067 USD for 1 Japanese Yen.
Let's present it with a table:
1 USD | 1 CHF | 1 YEN
0.91 CHF | 163.16 YEN | 0.0067 USD
----------------|-------------------|--------------
1.098901099 | 0.006128953 | 149.2537313
Now, we need to find a product of those values. A sequence of transactions becomes profitable when this product yields a value less than one:
1.098901099 * 0.006128953 * 149.2537313 = 1.005240803
As we can see the result is a larger than one, so it looks like we lost 0.05% of our money. But how many exactly? We can sort it out like this:
0.91 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 0.99478652 US Dollars
So, after selling 1 US Dollar in the beginning we have got 0.994 - less than 1 US Dollar in the end.
In simpler terms, Arbitrage Cycle is profitable when one unit of currency can be obtained for less than one unit of the same currency.
Let's imagine we have found an opportunity to take 0.92 CHF per 1 US Dollar in the initial transaction, instead of 0.91 CHF:
1 USD | 1 CHF | 1 YEN
0.92 CHF | 163.16 YEN | 0.0067 USD
----------------|-------------------|--------------
1.086956522 | 0.006128953 | 149.2537313
A product will be less than 1:
1.086956522 * 0.006128953 * 149.2537313 = 0.994314272
Which means, in the real currencies it will give us more than 1 US Dollar:
0.92 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 1.00571824 US Dollars
Wuolah, we got some PROFIT! Now, let's see how to automate this using graphs analysis.
So, the formula to check for profits or losses in an Arbitrage Circle of 3 Arbitrage Pairs would look like this:
USD/CHF * CHF/YEN * YEN/USD < 1.0
Graph representation
To automate those processes we can use graphs. The tables mentioned earlier can be naturally transformed into a matrix representation of a graph, where nodes represent currencies and edges represent bidirectional exchanges.
Hence, it is straightforward to represent two pairs exchange in matrix like this:
EUR USD
1 1 EUR
1 1 USD
Depending on the number of pairs involved, our matrix can expand:
EUR USD YEN CHF
1 1 1 1 EUR
1 1 1 1 USD
1 1 1 1 YEN
1 1 1 1 CHF
Consequently, our table can become considerably larger, even for just two currencies, if we take into account more exchange platforms and resources.
To address real currency arbitrage problems, a complete graph that encompasses all relationships for currency quotes is often utilized. A three-currency exchange table might appear as follows:
USD CHF YEN
{ 1.0, 1.10, 0.0067 } USD
{ 0.91, 1.0, 0.0061 } CHF
{ 148.84, 163.16, 1.0 } YEN
We can employ a simple graph data structure to represent our currency pairs in memory:
class GraphNode
{
public:
string Name;
};
class Graph
{
public:
vector<vector<double>> Matrix;
vector<GraphNode> Nodes;
};
Now, we only need to find out how to traverse this graph and find the most profitable circle. But there is still one problem...
Math saves us, again
Classical graph algorithms are not well-suited for working with the product of edge lengths because they are designed to find paths defined as the sum of these lengths (see implementations of any well-known classic path-finding algorithms BFS, DFS, Dijkstra or even A-Star).
However, to circumvent this limitation, there is a mathematical way to transition from a product to a sum: logarithms. If a product appears under a logarithm, it can be converted into a sum of logarithms.
On the right side of this equation, the desired number is less than one, indicating that the logarithm of this number must be less than zero:
LogE(USD/CHF) * LogE(CHF/YEN) * LogE(YEN/USD) < 0.0
This simple mathematical trick allows us to shift from searching for a cycle with an edge length product less than one to searching for a cycle where the sum of the edge lengths is less than zero.
Our matrix values converted to a LogE(x) and rounded with 2 digits after the point, now look like this:
USD CHF YEN
{ 0.0, 0.1, -5.01 } USD
{ -0.09, 0.0, -5.1 } CHF
{ 5.0, 5.09, 0.0 } YEN
Now this problem becomes more solvable using classical graph algorithms. What we need is to traverse the graph looking for most profitable path of exchange.
Graph algorithms
Every algorithm has its limitations. I mentioned some of them in my previous article.
We cannot apply classical BFS, DFS or even Dijkstra here because our graph may contain negative weights, which may lead to Negative Cycles while it traverses the graph. Negative cycles pose a challenge to the algorithm since it continually finds better solutions on each iteration.
To address this issue, the Bellman-Ford algorithm simply limits the number of iterations. It traverses each edge of the graph in a cycle and applies relaxation for all edges no more than V-1 times (where V is a number of nodes).
As such, the Bellman-Ford algorithm lies at the heart of this Arbitrage system, as it enables the discovery of paths between two nodes in the graph that meet two essential criteria: they contain negative weights and are not part of negative cycles.
While this algorithm is theoretically straightforward (and you can find billion videos about it), practical implementation for our needs requires some effort. Let's dig into it.
Bellman-Ford algorithm implementation
As the aim of this article is computer science, I will use imaginary exchange rates that has nothing to do with the real ones.
For a smoother introduction to the algorithm, let's use a graph that doesn't contain negative cycles at all:
graph.Nodes.push_back({ "USD" });
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" });
graph.Nodes.push_back({ "GBP" });
graph.Nodes.push_back({ "CNY" });
graph.Nodes.push_back({ "EUR" });
// Define exchange rates for pairs of currencies below
// USD CHF YEN GBP CNY EUR
graph.Matrix = { { 0.0, 0.41, INF, INF, INF, 0.29 }, // USD
{ INF, 0.0, 0.51, INF, 0.32, INF }, // CHF
{ INF, INF, 0.0, 0.50, INF, INF }, // YEN
{ 0.45, INF, INF, 0.0, INF, -0.38 }, // GBP
{ INF, INF, 0.32, 0.36, 0.0, INF }, // CNY
{ INF, -0.29, INF, INF, 0.21, 0.0 } }; // EUR
The code example below finds a path between two nodes using the Bellman-Ford algorithm when the graph lacks negative cycles:
vector<double> _shortestPath;
vector<int> _previousVertex;
void FindPath(Graph& graph, int start)
{
int verticesNumber = graph.Nodes.size();
_shortestPath.resize(verticesNumber, INF);
_previousVertex.resize(verticesNumber, -1);
_shortestPath[start] = 0;
// For each vertex, apply relaxation for all the edges V - 1 times.
for (int k = 0; k < verticesNumber - 1; k++)
for (int from = 0; from < verticesNumber; from++)
for (int to = 0; to < verticesNumber; to++)
if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
{
_shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to];
_previousVertex[to] = from;
}
}
Running this code for the Chinese Yuan fills the _previousVertex array and yields results like this:
Path from 4 to 0 is : 4(CNY) 3(GBP) 0(USD)
Path from 4 to 1 is : 4(CNY) 3(GBP) 5(EUR) 1(CHF)
Path from 4 to 2 is : 4(CNY) 3(GBP) 5(EUR) 1(CHF) 2(YEN)
Path from 4 to 3 is : 4(CNY) 3(GBP)
Path from 4 to 4 is : 4(CNY)
Path from 4 to 5 is : 4(CNY) 3(GBP) 5(EUR)
As you can observe, it identifies optimal paths between CNY and various other currencies.
And again, I will not focus on finding only one best one, as it is relatively simple task and not the goal of the article.
The above implementation works well in ideal cases but falls short when dealing with graphs containing negative cycles.
Detecting negative cycles
What we truly need is the ability to identify whether a graph contains negative cycles and, if so, pinpoint the problematic segments. This knowledge allows us to mitigate these issues and ultimately discover profitable chains.
The number of iterations doesn't always have to reach precisely V - 1. A solution is deemed found if, on the (N+1)-th cycle, no better path than the one on the N-th cycle is discovered. Thus, there's room for slight optimization.
The code mentioned earlier can be enhanced to not only find paths but also detect whether the graph contains negative cycles, including the optimization I mentioned:
vector<double> _shortestPath;
vector<int> _previousVertex;
bool ContainsNegativeCycles(Graph& graph, int start)
{
int verticesNumber = graph.Nodes.size();
_shortestPath.resize(verticesNumber, INF);
_previousVertex.resize(verticesNumber, -1);
_shortestPath[start] = 0;
// For each vertex, apply relaxation for all the edges V - 1 times.
for (int k = 0; k < verticesNumber - 1; k++)
{
updated = false;
for (int from = 0; from < verticesNumber; from++)
{
for (int to = 0; to < verticesNumber; to++)
{
if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
{
_shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to];
_previousVertex[to] = from;
updated = true;
}
}
}
if (!updated) // No changes in paths, means we can finish earlier.
break;
}
// Run one more relaxation step to detect which nodes are part of a negative cycle.
if (updated)
for (int from = 0; from < verticesNumber; from++)
for (int to = 0; to < verticesNumber; to++)
if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
// A negative cycle has occurred if we can find a better path beyond the optimal solution.
return true;
return false;
}
And now we play with a more intricate graph that includes negative cycles:
graph.Nodes.push_back({ "USD" }); // 1 (Index = 0)
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" });
graph.Nodes.push_back({ "GBP" });
graph.Nodes.push_back({ "CNY" });
graph.Nodes.push_back({ "EUR" });
graph.Nodes.push_back({ "XXX" });
graph.Nodes.push_back({ "YYY" }); // 8 (Index = 7)
// USD CHF YEN GBP CNY EUR XXX YYY
graph.Matrix = { { 0.0, 1.0, INF, INF, INF, INF, INF, INF }, // USD
{ INF, 0.0, 1.0, INF, INF, 4.0, 4.0, INF }, // CHF
{ INF, INF, 0.0, INF, 1.0, INF, INF, INF }, // YEN
{ INF, INF, 1.0, 0.0, INF, INF, INF, INF }, // GBP
{ INF, INF, INF, -3.0, 0.0, INF, INF, INF }, // CNY
{ INF, INF, INF, INF, INF, 0.0, 5.0, 3.0 }, // EUR
{ INF, INF, INF, INF, INF, INF, 0.0, 4.0 }, // XXX
{ INF, INF, INF, INF, INF, INF, INF, 0.0 } }; // YYY
Our program simply halts and displays a message:
Graph contains negative cycle.
We was able to indicate the problem, however, we need to navigate around problematic segments of the graph.
Avoiding negative cycles
To accomplish this, we'll mark vertices that are part of negative cycles with a constant value, NEG_INF:
bool FindPathsAndNegativeCycles(Graph& graph, int start)
{
int verticesNumber = graph.Nodes.size();
_shortestPath.resize(verticesNumber, INF);
_previousVertex.resize(verticesNumber, -1);
_shortestPath[start] = 0;
for (int k = 0; k < verticesNumber - 1; k++)
for (int from = 0; from < verticesNumber; from++)
for (int to = 0; to < verticesNumber; to++)
{
if (graph.Matrix[from][to] == INF) // Edge not exists
{
continue;
}
if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
{
_shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to];
_previousVertex[to] = from;
}
}
bool negativeCycles = false;
for (int k = 0; k < verticesNumber - 1; k++)
for (int from = 0; from < verticesNumber; from++)
for (int to = 0; to < verticesNumber; to++)
{
if (graph.Matrix[from][to] == INF) // Edge not exists
{
continue;
}
if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
{
_shortestPath[to] = NEG_INF;
_previousVertex[to] = -2;
negativeCycles = true;
}
}
return negativeCycles;
}
Now, if we encounter NEG_INF in the _shortestPath array, we can display a message and skip that segment while still identifying optimal solutions for other currencies. For example, with Node 0 (representing USD):
Graph contains negative cycle.
Path from 0 to 0 is : 0(USD)
Path from 0 to 1 is : 0(USD) 1(CHF)
Path from 0 to 2 is : Infinite number of shortest paths (negative cycle).
Path from 0 to 3 is : Infinite number of shortest paths (negative cycle).
Path from 0 to 4 is : Infinite number of shortest paths (negative cycle).
Path from 0 to 5 is : 0(USD) 1(CHF) 5(EUR)
Path from 0 to 6 is : 0(USD) 1(CHF) 6(XXX)
Path from 0 to 7 is : 0(USD) 1(CHF) 5(EUR) 7(YYY)
Whoala! Our code was able to identify a number of profitable chains despite the fact that our data was "a bit dirty". All the code examples mentioned above including test data is shared with you on my GitHub.
Even little fluctuations matter
Let's now consolidate what we've learned. Given a list of exchange rates for three currencies, we can easily detect negative cycles:
graph.Nodes.push_back({ "USD" }); // 1 (Index = 0)
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" }); // 3 (Index = 2)
// LogE(x) table: USD CHF YEN
graph.Matrix = { { 0.0, 0.489, -0.402 }, // USD
{ -0.489, 0.0, -0.891 }, // CHF
{ 0.402, 0.89, 0.0 } }; // YEN
from = 0;
FindPathsAndNegativeCycles(graph, from);
Result:
Graph contains negative cycle.
Path from 0 to 0 is: Infinite number of shortest paths (negative cycle).
Path from 0 to 1 is: Infinite number of shortest paths (negative cycle).
Path from 0 to 2 is: Infinite number of shortest paths (negative cycle).
However, even slight changes in the exchange rates (i.e., adjustments to the matrix) can lead to significant differences:
// LogE(x) table: USD CHF YEN
graph.Matrix = { { 0.0, 0.490, -0.402 }, // USD
{ -0.489, 0.0, -0.891 }, // CHF
{ 0.403, 0.891, 0.0 } }; // YEN
from = 0;
FindPathsAndNegativeCycles(graph, from);
Look, we have found one profitable chain:
Path from 0 to 0 is : 0(USD)
Path from 0 to 1 is : 0(USD) 2(YEN) 1(CHF)
Path from 0 to 2 is : 0(USD) 2(YEN)
We can apply these concepts to much larger graphs, involving multiple currencies:
graph.Nodes.push_back({ "USD" }); // 1 (Index = 0)
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" });
graph.Nodes.push_back({ "GBP" });
graph.Nodes.push_back({ "CNY" }); // 5 (Index = 4)
// LogE(x) table: USD CHF YEN GBP CNY
graph.Matrix = { { 0.0, 0.490, -0.402, 0.7, 0.413 }, // USD
{ -0.489, 0.0, -0.891, 0.89, 0.360 }, // CHF
{ 0.403, 0.891, 0.0, 0.91, 0.581 }, // YEN
{ 0.340, 0.405, 0.607, 0.0, 0.72 }, // GBP
{ 0.403, 0.350, 0.571, 0.71, 0.0 } }; // CNY
from = 0;
runDetectNegativeCycles(graph, from);
As a result, we might find multiple candidates to get profit:
Path from 0 to 0 is : 0(USD)
Path from 0 to 1 is : 0(USD) 2(YEN) 1(CHF)
Path from 0 to 2 is : 0(USD) 2(YEN)
Path from 0 to 3 is : 0(USD) 2(YEN) 3(GBP)
Path from 0 to 4 is : 0(USD) 2(YEN) 4(CNY)
There are two important factors, though:
-
Time is a critical factor in implementing arbitrage processes, primarily due to the rapid fluctuations in currency prices. As a result, the lifespan of a sure bet is exceedingly brief.
-
Platforms levy commissions for each transaction.
Therefore, minimizing time costs and reducing commissions are paramount, achieved by limiting the length of the sure bet.
Empirical experience suggests that an acceptable sure bet length typically ranges from 2 to 3 pairs. Beyond this, the computational requirements escalate and trading platforms impose larger commissions.
Thus, to make an income is not enough to have such technologies, but you also need access to the low-level commissions. Usually, only large financial institutions have such a resource in their hands.
Automation using smart contracts
I've delved into the logic of FX operations and how to derive profits from them, but I haven't touched upon the technologies used to execute these operations. While this topic slightly veers off-course, I couldn't omit mentioning smart contracts.
Using smart contracts is one of the most innovative ways to conduct FX operations today. Smart contracts enable real-time FX operations without delays or human intervention (except for the creation of the smart contract).
Solidity is the specialized programming language for creating smart contracts that automate financial operations involving cryptocurrencies. The world of smart contracts is dynamic and subject to rapid technological changes and evolving regulations. It's an area with considerable hype and significant risks related to wallets and legal compliance.
While there are undoubtedly talented individuals and teams profiting from this field, there are also regulatory bodies striving to ensure market rules are upheld.
Why are we looking into this?
Despite the complexity, obscurity, and unpredictability of global economics, Foreign Exchange remains a hidden driving force in the financial world. It's a crucial element that enables thousands of companies and millions of individuals worldwide to collaborate, provide services, and mutually benefit one another in a peaceful manner, transcending borders.
Of course, various factors, such as politics, regulations, and central banks, influence exchange rates and FX efficiency. These complexities make the financial landscape intricate. Yet, it's essential to believe that these complexities serve a greater purpose for the common good.
Numerous scientific papers delve into the existence and determination of exchange rates in the global economy, to mention a few:
These papers shed light on some fundamental mechanisms of Foreign Exchanges, which is still hard to understand and fit into one model.
Though, playing with code and trying to find a solution for a practical problem helped me to get a little more clue on it. I hope you enjoied this little exploration trip as much as I am.
Stay tuned!
Links
- Source code with all these examples
- Sedgewick R. - Algorithms in C, Part 5: Graph Algorithms
- Bellman Ford Algorithm Code Implementation
- William Fiset's GitHub examples - Bellman Ford On Adjacency Matrix
- William Fiset's GitHub examples - Bellman Ford On Edge List
Also published here.
L O A D I N G
. . . comments & more!
. . . comments & more!
