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 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
pair | bid | ask |
---|---|---|
EUR_USD | 1.21048 | 1.21090 |
EUR_GBP | 0.87052 | 0.87113 |
EUR_CHF | 1.07987 | 1.08110 |
GBP_USD | 1.38998 | 1.39058 |
GBP_CHF | 1.23988 | 1.24138 |
USD_CHF | 0.89199 | 0.89280 |
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.
Figure 1: The graph associated with the above table
Now assume we want to compute the rate from EUR to GBP through USD as
the intermediate currency. That is equivalent to taking path
where
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:
where
import numpy as np | |
def best_forex_rate(graph, src, T): | |
N=len(graph) | |
rate=np.array([0] * (N*(T+1)), dtype=np.double).reshape(T+1, N) | |
rate[0][src]=1 | |
pre=np.array([None] * (N*(T+1))).reshape(T+1, N) | |
for d in range(T): | |
for via, weight in enumerate(rate[d]): | |
if weight > 0: | |
for dst, edge_weight in enumerate(graph[via]): | |
if via != dst and rate[d+1][dst] < weight * edge_weight: | |
rate[d+1][dst] = weight * edge_weight | |
pre[d+1][dst] = via | |
return rate, pre |
The algorithm is basically computes the best rates according to the
recursion described by
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.