-
Notifications
You must be signed in to change notification settings - Fork 4
Introduction
Arbitrage is an opportunity to make profits by taking advantage of the differences in prices between similar financial instruments or similar assets.
Arbitrage can happen with two currencies as well as with a possibility of more than two currencies. When arbitrage happens with more than two currencies, a third currency is used for transactions as well, which is called the vehicle currency. For example, if you wanted to convert $1 to pounds, and if we first convert the dollar to yens, and further convert the yens to pound, yen is the vehicle currency in our example.
The currency exchange rate is the exact exchange rate between any particular two currencies at a point of time. In our project, we wanted to explore the arbitrage opportunities between any two currencies, to determine the possibility of making a profit through that exchange.
We get the latest (about a minute old) currency exchange rate data from the Yahoo Finance xchange database.
We cannot use all possible pairs of currencies because otherwise the call to the API uses a URL which is too long for any browser. So, we used a base currency (here, USD) and used the API to find the exchange rates between the base currency and other currencies. Then, we used that data to find the exchange rates between any two currencies, by following this documentation.
We also could not include all available currencies, because performance of the graph (see below) decreases after a certain size, and so we limited our program to a subset of currencies.
We modeled the currency arbitrage problem as a graph, so that we can run an algorithm on the graph to find arbitrage opportunities.
A graph is basically a collection of objects (nodes or vertices) and connections between them (edges). Edges can have weights (or a cost) associated with them. When the edges have a direction associated with them (from one node to another, but not the reverse), then the graph is a Directed Graph.
A path between two nodes is a set of edges such that one can start at one node and reach the other node by following those edges. A cycle is a path in the graph such that one can come back to the node they started with.
We can perform several operations on graphs, such as finding the shortest path between two nodes, and much more. Graph algorithms are a significant field of interest within computer science.
Every currency is a node in the graph. There is an edge between every pair of currencies, with the exchange rate between them as the edge weight. To find an arbitrage opportunity, we need to find a cycle in the graph (currency_1, currency_2, ..., currency_n, currency_1) such that
currency_1_currency_2_fxrate * currency_2_currency_3_fxrate * ... * currency_n_currency_1_fxrate > 1
However, we need to convert the above inequality into a summation because standard graph algorithms add the edge weights during traversal. Hence, we take the logarithm of the above:
log(currency_1_currency_2_fxrate) + log(currency_2_currency_3_fxrate) + ... + log(currency_n_currency_1_fxrate) > log(1) = 0
Multiplying the above by -1, we have:
-log(currency_1_currency_2_fxrate) - log(currency_2_currency_3_fxrate) - ... - log(currency_n_currency_1_fxrate) < 0
Hence, using -log(currency_i_currency_j_fxrate) as the edge weights, the currency arbitrage problem reduces to finding a negative cycle in the graph. The advantage of this is that finding negative cycles is a well-studied problem in graph theory.
An efficient way to find out whether a graph contains a negative cycle is to use the Bellman-Ford algorithm. If we modify the algorithm, we can find what the actual negative cycle is. So, using a modified version of the Bellman-Ford algorithm, we are guaranteed to find a negative cycle (and an arbitrage opportunity), if one exists. This is what we used in the program. However, we cannot find all possible negative cycles using this approach. Finding all negative cycles will need an algorithm which is very inefficient.
The program we developed is a purely client-side web application, hosted on GitHub Pages. We used CoffeeScript as the main scripting language, along with the usual web technologies (HTML, CSS, JS and jQuery). We used Bootstrap as the front-end UI framework, and the select2 library for the currency selection box. We used the wonderful Cytoscape.js library for the graphs.
One interesting problem we faced was floating point arithmetic. Because the exchange rates are not integers, simple operations (addition, equality) were causing unexpected bugs. After some debugging, we realized that the bugs were caused due to the way floating point arithmetic works, something we had only known in theory. We used math.js to take care of this. It was interesting to see the nuances of floating point arithmetic manifest in a real project.
Currency exchange arbitrage opportunities are rare, and even if available, are very short-lived. Also, there are many complications in finding and exploiting these opportunities, such as the presence of brokers and transaction costs.
This project can obviously not be used for monetary benefit. But we believe there is tremendous educational value in the project. Although the currency arbitrage problem is commonly shown as an example to students learning about graph theory, there aren't any projects actually showing this in action along with visualizations and real currency data. This project intends to fill this gap.
This project is a great example of applying Computer Science to solve a problem in Economics --- we took an Economics problem (currency arbitrage), modeled it as a CS problem (negative cycles in a graph), and used CS theory (Bellman-Ford algorithm) to solve it. It shows the usefulness of CS in solving problems in other domains. @neelabhg recently gave a talk showing this project to a camp of high-school students, in the hopes of demonstrating the power of programming.
- Graph (abstract data type) - Wikipedia
- Professor Sariel's CS 473 Lecture Notes (especially slides 10--13 / pdf pages 25--39)
- Bellman-Ford algorithm - Wikipedia
- "Currency Arbitrage In 99 Lines of Ruby" - Kelvin Jiang's blog post
- Stack Overflow - "Interesting Problem (Currency arbitrage)"
- Open Exchange Rates Documentation - "Currency Conversion 101: how to use the exchange rates"
- Stack Overflow - "How do I get currency exchange rates via an API such as Google Finance?"