Finding The Best Rate in Forex Graph

Currencies are traded in pairs by simultaneously buying one and selling the other. Each pair is associated with an exchange rate, which indicates the relative price of the first currency with respect to the second one. For instance pair EUR_USD with rate 1.2 shows every Euro values 1.2 US dollar. Let say you want to change your Euros to US dollars and want to get the best rate possible. One way is of course to change them directly to dollar with rate 1.2. You require to submit only one trade. But maybe, you get a better rate if you first sell the Euros and get some Japanese yens and then change the yens to US dollar. This includes two trades, which imposes the uncertainty coming from two order executions. In this post, I explain how to get the best rate between two currencies, possibly through some intermediate currency exchanges when the maximum number of trades is restricted.

Formulation and modeling

We are given a list of currency pairs with their associated bid and ask rates. For each pair, the bid rate is the price of selling one unit of the first currency with respect to the second. The ask rate is similar but for buying one unit of the first currency. With both bid and ask rates given, it is possible to model tradable currencies as a directed graph. In this graph, currencies are modeled as nodes which are connected by edges, provided that they are directly tradable. That is to say, a pair between currency \(C_1\) and \(C_2\) with bid rate \(b\) and ask rate \(a\) is simply modeled by an edge from \(C_1\) to \(C_2\) with weight \(b\) and an edge from \(C_2\) to \(C_1\) with weight \(\frac{1}{a}\). As an example, assume EUR_USD is traded with bid rate 1.2 and ask rate 1.4, then the edge between EUR to USD has weight 1.2 and the edge between USD to EUR has weight \(\frac{1}{1.4}=\frac{5}{7}\). The following example shows how to construct the graph, given the list of currency pairs.

The result is a directed graph with four nodes and 12 edges. Since all currencies are directly tradable, the graph is complete, i.e. each currency is connected to all others via a direct edge. The edges are, depending on their direction, associated either with the bid or with the ask rate. Their weights are computed as explained above.

Now assume we want to compute the rate from EUR to GBP through USD as the intermediate currency. That is equivalent to taking path \(\mathrm{EUR}\rightarrow\mathrm{USD}\rightarrow\mathrm{GBP}\) in the forex graph. The rate is computed by multiplying the rates of each edge along the path, which is \(0.87048=1.21048\times0.71912\). This value is the multiplicative distance from EUR to GBP via USD in the graph. In general, the rate between two currencies through a certain path coincides with multiplicative distance between them. The multiplicative distance from \(c_1\) to \(c_n\) through path \(c_1\rightarrow c_2\rightarrow\cdots\rightarrow c_n\) is computed by

\begin{equation*} \prod_{i=1}^{n-1}w(c_i,c_{i+1}) \end{equation*}

where \(w(c_i,c_{i+1})\) is the weight of the edge from \(c_i\) to \(c_{i+1}\), i.e. the direct rate of selling \(c_i\) and buying \(c_{i+1}\). This path composed of \(n-1\) consecutive trades. In practice we may want to restrict the number of trades, i.e. considering only paths up to a certain length. Each of those paths gives one rate, with the maximum one being the best rate. Formally speaking, for a given currency \(c\) and the maximum number of trades \(T\), we want to compute the maximum rate from \(c\) to any other currency by doing at most \(T\) trades. This is equivalent to the maximum multiplicative distance from \(c\) to any other currency considering the paths with length of at most \(T\).

Dynamic programming

The maximum multiplicative distance can be computed in a similar way as the shortest path in a graph. However, the length of paths, which is equivalent to the number of trades, is bounded. That is not usually the case in classical variations of shortest path problem. Moreover, the shortest path is indeed the minimum additive distance, which is different than the maximum bounded multiplicative distance needed here. In order to adapt shortest path computation to bounded multiplicative distance maximization, I use a variant of Bellman-Ford algorithm. The core of Bellman-Ford algorithm is a recursive formula which updates the shortest path iteratively. This formula is required to be adapted to multiplicative distance maximization as follows:

\begin{equation} \label{eq:rec} R_c(d,t+1)=\max_{(u,d)\in E}\left\{R_c(u,t)*w(u,d)\right\} \end{equation}

where \(R_c(d,t)\) is the maximum multiplicative distance from \(c\) to \(d\) over paths of length \(t\) and \(E\) is the set of edges in the forex graph. The idea is to extend the maximum multiplicative distance over paths of length \(t\) by attaching a single edge to it. It establishes the maximum multiplicative distance over paths of length \(t+1\). In trading world, we find all currencies that can be directly exchanged to \(d\), use them as the middle currency and choose the one that gives the best rate. The middle currency that gives the best result is the t-th vertex on the optimal path. By storing the middle currencies in each iteration, we can construct the optimal path. An implementation of the algorithm in python is given below.

The algorithm is basically computes the best rates according to the recursion described by \(\eqref{eq:rec}\). This operations is repeated \(T\) times, each time for all currencies in the graph. Therefore, the complexity of the algorithm is quadratic in the number of currencies and linear in the number of trades.

The forex graph is passed as variable graph, which stores the adjacency matrix of the graph. That is to say, graph[c][d] is the rate of exchanging currency c to d. Other inputs are the source currency src and the maximum number of trades T. As the output, it returns two tables both with T+1 rows. Each column is associated with a currency. The rates are stored in dist table, where dist[t,c] stores the best rate from src to c by doing t trades. The optimal path i.e. the middle currencies are stored in pre. For example, pre[t,c] indicates the middle currency right before c along the optimal path from src to c.

Conclusions

Forex trading rates can be aggregated and modeled by a graph. Doing so enables us to conduct certain analysis on the forex graph in order to answer some questions in the trading world. As an example, we have seen that an adaptation of shortest path algorithm can be used for computing the maximum rate between two currencies when there is an upper bound on the number of trades.