TTC (Top Trading Cycle) をNetworkXで実装する
学生の頃、マーケットデザインの授業で習った「TTC（Top Trading Cycle）アルゴリズム」を使ってプレゼント交換会などで使えるWebサイトを作成した際の、アルゴリズム部分のNetworkXを利用した実装サンプルを紹介します。
TTCアルゴリズムとは
2012年にノーベル経済学賞を受賞したロイド・シャープレーらが考案した、物々交換のためのアルゴリズムです。
近年経済学で注目を浴びているマーケットデザインの分野で利用されています。
アルゴリズムの詳細
財を１つずつ持っている各参加者が、ほかの参加者と財を1回交換するゲームを考えます。
- 現時点で残っている参加者の持つ財のうち、最も欲しいものを持つ参加者を、参加者それぞれが指す。（自分を指しても良い）
- 閉路（輪を作れる箇所）が必ず1つ以上できるので、その閉路に沿って財を交換する。
- 閉路に含まれる参加者をゲームから除外する。
- 残っている参加者で、①に戻って繰り返す。
以上がTTCアルゴリズムです。
ここで得られる交換の結果は、個人合理性や効率性を満たす「強コア」な配分となります。
アルゴリズムをもっと詳しく知りたい方は、ここなどをご覧ください。
実装例
import networkx as nx
import random
import matplotlib.pyplot as plt
def ttc_algorithm(preference_dict: dict):
result_cycles_list = []
while preference_dict != {}:
# create directed graph
g = nx.DiGraph()
# add nodes
nodes_list = []
for key in preference_dict:
nodes_list.append(key)
nodes_list.sort()
for elem in nodes_list:
g.add_node(elem)
for key in preference_dict:
g.add_edge(key, preference_dict[key][0])
# search for cycles
cycles = nx.simple_cycles(g)
cycles_list = list(cycles)
# Graph drawing part starts here
color_map_dict_pre = {key: "deepskyblue" for key in preference_dict.keys()}
for cycle in cycles_list:
for edge_name in cycle:
color_map_dict_pre[edge_name] = "yellow"
color_map = list(color_map_dict_pre.values())
nx.draw_networkx(g, node_color=color_map)
plt.show()
# Graph drawing part ends here
# add cycles to result
result_cycles_list.append(cycles_list)
# start removing edges from preference dict
for cycle in cycles_list:
for edge_name in cycle:
preference_dict.pop(edge_name, None)
for key in preference_dict:
if edge_name in preference_dict[key]:
preference_dict[key].remove(edge_name)
# end removing edges from preference dict
return result_cycles_list
if __name__ == "__main__":
num_gifts = random.randint(1, 100)
preferences = {}
for i in range(num_gifts):
preferences[i] = random.sample(list(range(num_gifts)), num_gifts)
print(preferences)
print(ttc_algorithm(preference_dict=preferences))
実装の説明
表題の通り、今回のプログラムはNetworkXを使って実装されています。
TTCアルゴリズムを実装するにあたって、アルゴリズムの②と③の部分（閉路の探索）が課題となります。
そこで、NetworkXを使うことにしました。
NetworkXは、グラフを扱うためのPythonのライブラリで、非常に便利なメソッドが多く用意されています。
TTCアルゴリズムの閉路探索の部分は、上記のコード28行目のわずか1行で実現できました。
cycles = nx.simple_cycles(g)
32行目から41行目は、matplotlibで実行の経過を可視化するためのコードになっています。
実行すると、こんな感じのグラフが出力されます。
このようにTTCアルゴリズムは、有向グラフの問題を解くライブラリを用いれば簡単に実装できます。
もっと広まってほしい。
あとがき
「クリスマス会のプレゼント交換でがっかりすることがなくなる！TTC最高！！！」って言ってノリノリでWebアプリケーションを作って、
いざ実戦投入しようと思ってサークル員にプレゼンしたら、
「プレゼント交換は何もらえるかわからないワクワク感が楽しいんだよ」って言われてお蔵入りになりました。
悲しい。。
