Anton YarkovFollowBetter Programming--ListenShareIf 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.The task explicitly mentioned that the algorithm’s foundation must be rooted in graph theory.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 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 their exchange rate.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 moreMany providers employ mathematical modeling and analysis to secure their own profits and prevent others from profiting from 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 vary among banks or 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 can access 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 the exchange rates of these intermediate transactions.Let’s imagine we want to buy Swiss Franks for US Dollars, exchange Franks for Japanese Yens, and then sell Yens for US Dollars again. In Autumn 2023, we have the following exchange rates:Let’s present it with a table:Now, we need to find a product of those values. A sequence of transactions becomes profitable when this product yields a value of less than one:As we can see, the result is larger than one. We lost 0.05% of our money. But how many exactly? We can sort it out like this: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:A product will be less than 1:This means that in the real currencies, it will give us more than 1 US Dollar. Here’s what that looks like:Whoa, 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 three Arbitrage Pairs would look like this: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 the matrix like this:Depending on the number of pairs involved, our matrix can expand:Consequently, our table can become considerably larger, even for just two currencies, if we consider more exchange platforms and resources.To address real currency arbitrage problems, a complete graph encompassing all currency quote relationships is often utilized. A three-currency exchange table might appear as follows:We can employ a simple graph data structure to represent our currency pairs in memory:Now, we only need to find out how to traverse this graph and find the most profitable circle. But there is still one problem…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, logarithms are a mathematical way to transition from a product to a sum to circumvent this limitation. 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: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 two digits after the point, now look like this:Now, this problem becomes more solvable using classical graph algorithms. What we need is to traverse the graph looking for the most profitable path of exchange.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 challenge the algorithm since it continually finds better solutions on each iteration.To address this issue, the Bellman-Ford algorithm 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 the 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 billions of videos about it), practical implementation for our needs requires some effort. Let’s dig into it.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:The code example below finds a path between two nodes using the Bellman-Ford algorithm when the graph lacks negative cycles:Running this code for the Chinese Yuan fills the _previousVertex array and yields results like this: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 negative-cycle graphs.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:And now we play with a more intricate graph that includes negative cycles:Our program halts and displays a message:We were able to indicate the problem. However, we need to navigate around problematic segments of the graph.To accomplish this, we’ll mark vertices that are part of negative cycles with a constant value, NEG_INF: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):Whoa! Our code identified several profitable chains despite our data being “a bit dirty.”All the code examples mentioned above, including test data, are shared with you on my GitHub.Let’s now consolidate what we’ve learned. Given a list of exchange rates for three currencies, we can easily detect negative cycles:Here’s the result:However, even slight changes in the exchange rates (i.e., adjustments to the matrix) can lead to significant differences:Look, we have found one profitable chain:We can apply these concepts to much larger graphs involving multiple currencies:As a result, we might find multiple candidates to get profit:There are two important factors, though: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 two to three 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 low-level commissions. Usually, only large financial institutions have such a resource in their hands.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 creating 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 has considerable hype and significant risks related to wallets and legal compliance.While there are undoubtedly talented individuals and teams profiting from this field, regulatory bodies are striving to uphold market rules.Despite global economics' complexity, obscurity, and unpredictability, 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 peacefully benefit one another, 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 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 are still hard to understand and fit into one model.However, playing with code and finding a solution for a practical problem helped me get more clues on it. I hope you enjoyed this little exploration trip as much as I am.Stay tuned!----Better ProgrammingSenior Software Engineer and Engineering manager with 10+ years of experience in development of high loaded online systems.Anton YarkovinBetter Programming--Benoit RuizinBetter Programming--199VinitainBetter Programming--32Anton Yarkovinoptiklab--Yuri BettinStackademic--1Brendan Gray--7Haifeng Li--Damian GilinTowards Data Science--22Will LockettinPredict--28AL Anany--364HelpStatusWritersBlogCareersPrivacyTermsAboutText to speechTeams