Pythonで通貨アービトラージ（裁定取引）の機会を検出するプログラム

問題の概要

N × N の通貨レート表が与えられ、そこから一連の取引を実行できるかどうかを判定します。任意の通貨を金額 A からスタートし、最終的に同じ通貨で A より多い金額に戻せれば、裁定取引（アービトラージ）が成立していることになります。取引コストはなく、端数単位での取引も可能であると仮定します。

この行列の [i, j] 成分は、「通貨 i を 1 単位売ったときに通貨 j をいくら購入できるか」を表します。ここでは、通貨 0 を米ドル（USD）、通貨 1 をカナダドル（CAD）、通貨 2 をユーロ（EUR）とします。

アービトラージの具体例

たとえば、次のような取引の連鎖によって裁定取引が可能になります。

• 1 CAD を売って 0.65 EUR を得る
• 0.65 EUR を売って 0.7865 USD を得る（0.65 × 1.21）
• 0.7865 USD を売って 1.00672 CAD を得る（0.65 × 1.21 × 1.28）

最初の 1 CAD が最終的に約 1.0067 CAD に増えているため、リスクなしの利益が発生しています。

入力例と出力

入力が以下のような行列だった場合：

出力は True となります。

解法のアプローチ：対数変換とワーシャル・フロイド法

この問題は「グラフにおける負の閉路の検出」問題として捉えられます。解決の手順は以下の通りです。

1. 行列の各要素を matrix[i][j] = −log₂(matrix[i][j]) に変換します。これにより、為替レートの掛け合わせが距離の足し算に置き換わり、利益の出る循環は負のコスト経路として現れます。
2. v := 行列の行数とします。
3. k、i、j それぞれについて 0 から v の範囲で三重ループを回し、ワーシャル・フロイド法で全ペア間の最短距離を求めます。すなわち matrix[i][j] := min(matrix[i][j], matrix[i][k] + matrix[k][j]) を適用します。
4. 最後に、行列の対角成分にゼロ未満（負）の値がひとつでもあれば True を返します。これは負の閉路＝アービトラージの機会が存在することを意味します。

Pythonによる実装コード

import math
class Solution:
    def solve(self, matrix):
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j] = −math.log(matrix[i][j], 2)
    v = len(matrix)
    for k in range(0, v):
        for i in range(0, v):
            for j in range(0, v):
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
    return any(matrix[i][i] < 0 for i in range(len(matrix)))
ob = Solution()
matrix = [
    [1, 1.28, 0.82],
    [0.78, 1, 0.65],
    [1.21, 1.55, 1]
]
print(ob.solve(matrix))

入力

matrix = [
    [1, 1.28, 0.82],
    [0.78, 1, 0.65],
    [1.21, 1.55, 1]
]

出力

True