[Python] ベルマンフォード法を使う外国為替市場の裁定取引

下記を参考に、外国為替市場での裁定取引について Python を使い考えます。

外国為替取引におけるネットワーク計画の利用

グラフには下記モジュールを使います。

NetworkX

外国為替市場の裁定取引

外国為替市場の裁定取引について具体的に考えてみます。

2020年2月28日のドル・円・ユーロの17時時点を使います。

下限では、ドル/円が108.83円、ユーロ/ドルが1.0996ドル（ドル/ユーロはその逆数で ≒ 0.9094 ユーロ)、ユーロ/円が119.67円となっています。

ドルをユーロ経由で円にするには、ドル/ユーロにユーロ/円をかけます。

となり、ドル/円のレートの下限と一致しています。

もしここで、ユーロ/円の交換に、上限の119.71円を使えるとします。

この時点でのドル/円のレンジは108.83～108.85なので、ドル→ユーロ→円→ドルを一度巡回すると、0.01～0.03円儲けることが出来ることになります。

グラフの最短経路問題への変換

ノードを通貨に、為替レートの対数に -1 をかけたものを辺の重みとするグラフを考えることで、上の問題を負の重み付きグラフの最短経路問題として考えることができます。

例えば、ドル→ユーロ→円の変換である0.9094×119.67 という計算は、左辺の対数を取ることで log(0.9094×119.67)=log0.9094+log119.67 と和として考えることができ、さらに -1 をかけることで、和を最小化するルートを探索する問題になります。

さらに負の閉路があった場合に負の閉路を取り出すことできれば、上のような裁定取引が実現できます。

具体的に計算する

以下から表を借りてきて、具体的に計算を行います。

以下の c のコードを参照します。

Finding a negative cycle in the graph

ベルマンフォードの応用です。

[グラフ] ベルマンフォード法

ベルマンフォード法 ベルマン–フォード法(英:Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキュー...

yottagin.com

2020-02-15 13:22

import collections
import math

import networkx as nx


def neg_log(x):
    return - math.log(x)

def negative_cycle(graph):
    n = len(graph.nodes())
    dist = collections.defaultdict(lambda: 100000)
    pred = collections.defaultdict(lambda: -1)
    x = -1

    for _ in range(n):
        for u, v in graph.edges():
            weight = graph[u][v]['weight']
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                pred[v] = u
                x = v

    if x == -1:
        print('No negative cycle')
        return None

    for _ in range(n):
        x = pred[x]

    cycle = []
    v = x
    while True:
        cycle.append(v)
        if v == x and len(cycle) > 1:
            break
        v = pred[v]

    return list(reversed(cycle))


if __name__ == '__main__':
    lst_currency = ['yen', 'dollar', 'pond', 'euro', 'krona', 'franc']

    forex_matrix = [
        [1, 0.00973, 0.00608, 0.00972, 0.07222, 0.01549],
        [102.67, 1, 0.6248, 0.9983, 7.0422, 1.5908],
        [164.32, 1.6005, 1, 1.5978, 11.88, 2.5461],
        [102.85, 1.0017, 0.625, 1, 7.435, 1.5935],
        [13.83, 0.1347, 0.0841, 0.1344, 1, 0.2143],
        [64.54, 0.6286, 0.3927, 0.6275, 4.6657, 1]
        ]

    graph = nx.DiGraph()
    graph.add_nodes_from(lst_currency)

    for i, from_currency in enumerate(lst_currency):    
        for j, to_currency in enumerate(lst_currency):
            if i == j:
                continue
            graph.add_edge(from_currency, to_currency, weight=neg_log(forex_matrix[i][j]))

    # ['dollar', 'pond', 'euro', 'dollar']
    print(negative_cycle(graph))

ドル→ポンド→ユーロ→ドル が負の閉路を形成しています。

実際0.6248×1.5978×1.0017=1.0288 と、一回の巡回で2％ほどの利益が出るようです。

個人で応用する分には、メルカリ、ヤフオク、その他中古品取扱いの裁量取引かな。