【算法】外汇市场的套利与Bellman-Ford算法

前言

#

最近美元兑换人民币汇率跌破6.9（2022-09-04），蹭蹭热度来聊聊外汇市场的套利(Forex Arbitrage)算法，以及具体实现的限制。

问题概述

#

在外汇市场，如果货币A通过一系列货币兑换回到A，A数额竟然变大了，我们就认为该外汇市场存在套利。因为通过这一系列货币兑换，将获得更多A货币，无中生有。而且如果这些货币汇率保持不变，我们一直循环这样的兑换，那么理论上我们可以无限获取货币A。

问题分析

#

我们可以将这个问题转换成一个图问题。每种货币为一个节点vertex，如果货币A能直接兑换货币B，则两种货币对应的节点间有一条有向边edge，同时该边有一定的权重weight表示从货币A到B的汇率（A-> B的汇率不一定与B->A汇率相等）。这样我们就可以把整个外汇市场转换成一个有向边的图。

1. 最短路径问题目标函数是将权重相加而不是相乘
2. 最短路径问题是找目标函数的最小值而不是最大值

其实我们只需要针对这两个不同点做一定的转换就可以变成最短路径问题，最短路径问题我们就可以用最经典的Dijkstra算法来求解（计算机最基础的算法， 不展开解释）：

1. 从相乘变成相加，只需要取对数log就能将乘法变成加法 因为log(x*y) = log(x) + log(y)
2. 最大值变成最小值，只需要将目标函数取负数 那么我们相当于把原始图的每条边权重改成new-weight(a,b) = -log(weight(a,b))，问题就转换成从A到B的最短路程。 但由于log(x)在x< 1的时候为负值，那么我们转换的新图的每条边权重可能会有负值。很可惜Dijkstra算法只能解决所有边权重为正数的最短路径问题。如果图里面边权重为负数，一旦存在一个回路，路径和为负数，那么就A到B就不会有最小路径，因为可以一直走那个回路，让最小路径理论无穷小。 这是不是听起来和我们的套利问题很像？没错，套利问题其实就是在这个转换后的图里面，判断有没有存在路径和为负数的回路，并把这样的回路找出来。 ##Bellman-Ford算法 这个问题再简化一下其实就是一个存在负数权重边的图里面，找到路径和为负的回路。而这个问题也有一个专门的Bellman-Ford算法来解决。 Bellman-Ford算法说到底就是一个动态规划DP算法，来求从图里面的一点A，到其它所有点的最短路径。而算法的核心思想是：如果最短路径存在，那么这条路径最多有V个节点，V-1条边（V为图总节点个数) ，DP算法的状态即为distance(A,v,e) 意思为从节点A到节点v的最多包含e条边的最短路径。

def bellmanFord(graph, start):
 # Set initial dist and prev.
 for vertex in graph:
    vertex.dist = ∞
    vertex.prev = null
    start.dist = 0

 # Iterate |V| − 1 times.
 for iter in range(0, |V| − 1):
    # Look at each vertex.
    for v in vertex:
       # Check each neighbor of v.
       # neighbor means there is an edge from u to it
       for neigh of v:
          # Only update if the new value is better!
          if neigh.dist > v.dist + length(v, neigh):
             neigh.dist = v.dist + length(v, neigh)
             neigh.prev = v

 # Iterate One more time
 # If the neigh.dis changed for any vertex n
 # Then there is a negative cycle
 We found the arbitrage!!!
 Found the node v = neigh.dist changed in the last round
 Backtrack with v.prev to find the cycle

算法复杂度 : O(|V|^2*|E|) 最坏情况为全连接图那么E=V-1，所以算法复杂度是O(|V|*4)

具体实现限制

#

是不是掌握这个算法，一旦外汇市场出现了可套现的情况就一定能获利呢？那当然不是了。

佣金

#

外汇交易需要通过券商，而券商会收取佣金。 有的券商会直接将佣金反应在汇率上面，这样比较简单，因为汇率已经包括了所有的交易费用。 但有的券商会根据交易笔数和交易金额来收取佣金，这样的话就需要一些额外方法把这些交易费用反应在汇率上面，再用Bellman-Ford算法。

延迟Latency

#

汇率变化十分的快，即使汇率市场存在套利的机会，但是这个机会可能稍纵即逝，不同的延迟Latency会导致普通散户无法及时抓住这些机会。

获取数据的延迟

#

我们需要获取不同货币之间的汇率作为算法的输入。通常汇率数据由券商提供，需要用券商提供的API去获得，而不同API会有不同的延迟，延迟可能是由券商服务器或者网络导致，可能你得到数据的同时这些数据就已经过期了。

算法的复杂度

#

这个算法最差复杂度是O(|V|*4)，所以算法的速度不快，可能算出结果的同时，该结果已经不可用。

交易的延迟

#

通常券商的交易匹配系统是通过买和卖两个队列做匹配，而这个过程也需要时间，很有可能汇率一变，导致你指定的买卖价格匹配一直不成功。而如果直接用市场价很有可能你的交易价格与你最初算法的输入价格不一样，导致最后结果与期望结果不一致。

结语

#

购买外汇，按需购买就好。