如何使用套利建立最短路径

;

谁不喜欢赚钱？

如果你能把赚钱的问题变成寻找最短路径的问题呢？ 我们至少可以通过一种特定方式做到这一点：利用套利机会。

什么是套利？

套利是指在不同市场或以不同形式交易商品，从价格差异中获利的行为。 相关人员该怎么办？ 他们被称为套利者，多么花哨的头衔。

让我们从一个例子开始。 假设保罗、彼得和鲍勃住在一个村庄里，用胡萝卜、土豆和生菜交换食物。 鲍勃用土豆换胡萝卜，彼得用生菜换土豆，保罗用生菜换胡萝卜。

此外，鲍勃用两个土豆换一个胡萝卜，彼得用一个生菜换两个土豆，保罗用两个胡萝卜换一个生菜。 如果我们将每个人都视为自己产品的市场，汇率会是多少？

你觉得有机会吗？

作为一个有进取心的人，你可以尝试使用它。 从 5 根胡萝卜开始，您接近保罗并以他愿意支付的价格用 5 根胡萝卜换取 10 个土豆。

接下来，您将土豆带给彼得，他将用五个生菜换土豆。 然后你拿 5 个生菜接近保罗，他用 10 个胡萝卜换你的生菜。

经过几次明智的交易后，您的胡萝卜财富翻了一番。 利用套利机会，您可以将 5 根胡萝卜变成 10 根。

以后，村民们可能会开发更复杂的市场，Bob、Peter 和 Paul 并不是唯一的投资者。 相反，村子可以发展一个胡萝卜/生菜市场，一个生菜/土豆市场，一个土豆/胡萝卜市场，每笔交易的汇率会根据人们的交易意愿而浮动。

但套利原则并没有改变，直到没有胡萝卜、生菜或土豆可供愿意以此价格交易的交易者使用，这些机会才会出现。 利用套利机会，直到市场达到均衡。

现代套利

当您想到现代市场时，您可能不会想到交易胡萝卜、土豆和生菜。 如果您投资外汇交易，您更有可能考虑交易美元、英镑和日元。 在这种情况下，我们将有 USD/GBP 市场、GBP/JPY 市场和 JPY/USD 市场。 每个市场都有很多投资者。 从现在开始，让我们以这些商品币作为交易的例子，但请记住，这些原则适用于所有可以交易的东西。

在给定时间，汇率如下：

如果您从 Bob、Peter 和 Paul 的胡萝卜、生菜和土豆贸易中学到了什么，您就会在这里找到机会。

如果你用一美元兑换一英镑，你最终会得到 0.80 英镑。 换成日元就80日元。 您将日元带到日元对美元的兑换处，在那里您可以将其兑换成美元，但现在您只有 1.04 美元！

但是在另一个套利者打败你之前，你必须快速行动。 在流动性耗尽和利率平衡之前，这些机会只是暂时的。

你们中的一些人可能已经注意到，在我们的例子中我们没有考虑交易成本。 当然，您必须将这些因素考虑在内，才能计算出是否真的存在有利可图的套利机会。

快速反应

我希望您对为什么需要快速行动有一些直觉。 汇率波动很快，“东西”的选择是有限的。

虽然我们在这里使用的是相对简单的例子，但套利机会可以跨越许多交易并变得极其复杂。 我们的示例使用 3 个事务，但如果需要 10 个事务怎么办？ 在 20 个硬币的网络中，每对硬币都有一个市场。 你能快速找到机会吗？

使用计算机是一个显而易见的答案，但我们需要一种高效的算法，这样其他人就不会打败我们。

为此，我们可以从数学和计算机科学中汲取一些巧妙的见解。

市场地图

图是一种非常重要的结构，广泛应用于许多应用程序中。 许多社会和自然结构都可以用图形表示。 事实证明，市场就是其中之一。

在我们的示例中，让我们将每批硬币视为一个节点。 从一个节点移动到另一个节点相当于将一种商品币换成另一种商品币。

所以沿着节点之间的边移动，我们可以用汇率来换算硬币的商品数量。

这意味着从美元节点移动到英镑节点相当于乘以 0.8 英镑/美元。 让我们为每一方分配汇率权重。

请注意，每个方向的汇率是互为倒数的。 这意味着如果 GBP/USD 汇率为 0.8 GBP/USD，反向汇率为 1/(0.8 GBP/USD) = 1.25 USD/USD。 对我们来说，结果是我们需要谨慎交易每个市场，因为不同的定向腿有不同的权重。

双向汇率之所以只是近似于倒数，是因为货币交易商品的价差很小，称为买卖价差。 例如，如果在给定时刻，您可以以每美元 0.8 英镑的价格购买英镑（有人会以当前价格卖给您），但您可以以每美元 0.82 英镑（或每磅 1.22 美元，有人会以当前价格出售）的价格购买英镑您购买它的时间）那么您的图表将如下所示（为简单起见，不包括其他汇率）：-

一系列交易可以通过沿着图中的边移动来建模，交易的结果是通过将边权重乘以边权重来计算的。

看到机会

现在我们有了一个工作模型，我们在对应于套利机会的图表中寻找什么？

为了确定一系列交易是否盈利，我们需要一个一致的盈利指标。 换句话说，如果我们以美元开始一系列交易比特币回报率图表，我们也需要以美元结束。 通过将最终金额与初始金额进行比较，我们可以知道它是否有利可图。

在我们的图中，这意味着我们的一系列交易必须在它们开始的同一节点结束。 在这个例子中，我们从美元节点开始，以美元节点结束。 在图表术语中，我们称这些为周期。 所以我们知道我们正在寻找某种循环，但什么样的循环会使其有利可图？

请注意，如果我们沿着周期的边缘乘以，我们将转换为有效汇率的单位。

;

然而，当我们回到起始节点时，数量就变成了无量纲。 它是由汇率转换为回报率！ 在我们的图表上经过一段时期并计算利率乘积相当于在完成一系列交易后计算回报率。

如果市场完全有效，我们的收益率 ABC 将为 1，因为汇率已经相等。 如果权重的乘积大于 1，比如 1.02，那么套利机会会给我们带来 2% 的回报。

因此，对于任意数量的交易，套利机会对应于以下不等式：

式中，ei对应第i个汇率。 对于每笔交易 I，除以 N 笔交易。

所以我们需要的是一种算法，它可以在市场图中找到边权重乘积大于 1 的环。你可能会发明一种算法来解决这个问题，但在计算机科学中，就像在日常生活中一样，它很有用将问题简化为您已经知道如何解决的问题。

贝尔曼-福特算法

寻找最短路径是计算机科学中一个常见的基本问题，可以应用于许多不同的场景。 一个显而易见的方法是通过将图形映射到地图来找到地图上的最短路径。 然而，通过一些技术，许多其他类别的问题也可以转化为最短路径问题。 我想论证的是，寻找套利机会的问题就是其中之一。

首先，让我们确定什么是最短路径问题。 给定图中的两个节点 s 和 T，最短路径是使边权重之和最短的路径。 换句话说，我们沿着从 s 到 t 的路径移动，沿路径添加边权重。 一般来说，最短路径是最短的路径，也是成本最低的路径。

接下来，将有助于理解不同类别的最短路径问题。 在明显的情况下，例如地图上的最短路线，边权重必须为正。 除非你有时间机器，否则在路上开车会减少你的旅行时间。 在只有正边权重的图中，Dijkstra 著名的算法计算到图中所有节点的最短路径。

然而，没有理由说图不能有负边权。 在这种情况下，沿边移动可以降低路径的总成本。 但是，如果环的权重为负，则可以不断遍历环——每次都减少路径的总代价，最短路径的代价接近于-infin;。 在这种情况下，我们的最短路径算法拥有一种确定负权重周期的机制将非常有用。 否则，最短路径总是陷入负权重的循环。

bellman-Ford算法就是这种算法。 可以处理负权重的 Dijkstra 最短路径算法的更通用版本。 为此，它会检测负权重周期（图中的周期）并将权重相加以产生负值。

然而，当我们需要一种算法来检测副积大于 1 的环时，我们如何找到副积小于 0 的环？

登录救援

下一点是可以使用对数函数将乘积转换为总和，这要归功于以下等式：

;

因此，我们可以将乘积大于1的周期问题转化为和大于0的周期问题！ 我们取每个汇率的对数作为各方的权重。

让我们通过记录不等式两边的对数来证明这一点。首先，取左边的对数，将乘积的计算转换为计算的总和

右边的对数简单地将 1 转换为 0：

我们很近，但还不算太近。 最后一步是将我们的问题简化为我们可以用这个已知算法解决的问题，即将每条边的权重乘以-1。这将寻找正负循环的问题转化为寻找负权重循环的问题

我们知道 Bellman-Ford 算法可以做到！ 将套利问题转化为寻找最短路径（即无限最短路径）的问题，按照指定的方法构造图，并在图上执行Bellman-Ford算法，将有助于快速有效地寻找套利机会。

现在看来，负权重循环（每次遍历都会降低路径成本）和套利机会（每次都有利可图）之间应该存在对应关系。 关键是通过将对数应用于边权重，将查找大于 1 的乘积的问题转化为查找小于 0 的和的问题。

证明给我看

让我们在汇率上运行这个算法，看看它是否正确识别套利机会。 通过对数汇率换算，得到如下结果：

总而言之比特币回报率图表，我们的平等成立了，我们找到了一个负权重循环！

我们可以撤消对数以恢复乘积并计算收益：

这是我们之前计算的 4% 的回报率。

在现实世界

由于套利机会对应负权重时期，我们似乎可以永远通过这个时期赚取无限的钱。 当然，事实并非如此。

任何套利机会的可用流动性（在价格发生重大变化之前可用的数量）都是有限的，并且会被算法投资者迅速利用，从而使计算边界和物理定律相互抵触。

话虽如此，我希望你能用图论和著名的最短路径算法来解决金融问题（并赚钱），这对我来说一直很有趣。