Skip to content
検索結果に戻る

トップ・トレーディング・サイクル

提唱者
Lloyd Shapley, Herbert Scarf
年
1974
種類
algorithm
系統
Game-theoretic

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

トップ・トレーディング・サイクル(TTC)は、分割不可能な財をエージェントに割り当てるためのアルゴリズムであり、その割り当てはパレート効率的かつ個々人に合理的である。1974年にロイド・シェプリーとハーバート・スカーフによって開発されたこのアルゴリズムは、選好の有向グラフにおける取引サイクルを特定し、それらの取引を実行し、それ以上有益な取引がなくなるまで反復的に繰り返す。TTCは、その効率性と実装の単純さから、腎臓交換や住宅割り当てにおいて広く利用されている。

手法の背後にある直感

人々がそれぞれ家を所有しており、各人がすべての家を好み順にランク付けしている状況を想像してほしい。TTCアルゴリズムは、「私の最も好きな人は誰か?その人に指を差せ。次に、誰があなたに指を差したかを見よ。もしそれがサイクル(AがBを指し、BがCを指し、CがAを指す)であれば、それらの取引を実行せよ—AはBの家を得て、BはCの家を得て、CはAの家を得る。サイクル内の全員が、現在の家よりも好む誰かの家を得るので満足する。サイクルを除去し、それ以上サイクルが存在しなくなるまで繰り返す。結果は効率的である。なぜなら、すべての有益な取引が行われるからだ。

歴史学

ロイド・シェプリーとハーバート・スカーフは、1974年に住宅市場問題の解決策としてトップ・トレーディング・サイクル・アルゴリズムを導入し、それが一意のパレート効率的な割り当てをもたらすことを証明した。このアルゴリズムは、アルヴィン・ロスによる腎臓交換の研究を通じて実用的な重要性を増し、ドナーとレシピエントのマッチングの中心となった。2012年のロスへのノーベル賞受賞は、特に臓器移植における現実世界の市場設計におけるTTCの重要性を裏付けた。

使うべき場面

分割不可能な財(家、臓器、学校の席)を、バンドルに対する厳密な選好を持つエージェント間で割り当てる際にTTCを適用する。パレート効率性が不可欠であり、金銭的移転が利用できないか望ましくない場合に用いる。TTCは、エージェントが局所的に有益な取引を特定できる分散型市場に理想的である。エージェントが完全で非循環的な選好情報を持っている場合に最も効果を発揮する。

限界と注意点

  • 無差別を伴わない厳密な選好順序を要求する;弱選好への拡張は複雑である
  • 協調的な証明ができない:エージェントの協調は、集団的な結果を改善するために選好を偽って報告できる
  • 選好サイクルへの感度:サイクルの非存在は、一部のエージェントが取引されないまま残る可能性がある
  • 金銭的移転を伴わないマッチングに限定される;異質な評価には非効率

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • パレート効率的:取引なしでの改善が存在しない;すべての相互に有益な交換が実行される
  • 個々人に合理的:各エージェントは最終的な割り当てを初期賦与よりも弱く好む
  • 特定の状況下では戦略的に証明可能:エージェントは選好を偽って報告しても改善できない
  • 計算効率が高い:単純な実装で多項式時間
  • 透明性が高い:エージェントは、自分の指名した選択がどのように割り当てにつながるかを理解する

応用

  • 腎臓交換:臓器ドナーとレシピエントをマッチングさせ、多者間交換を通じて移植適合性を向上させる
  • 住宅割り当て:大学の寮の部屋や公営住宅ユニットを効率的に割り当てる
  • 学校選択:定員制約と選好の多様性を持つ学校に生徒を割り当てる
  • 肝臓葉交換:生体ドナー肝移植のためのペアド・ドネーション交換を促進する
  • 家具・物品交換:コミュニティ共有プラットフォームでの効率的な物々交換を組織する

使い方

使い方

1

各エージェントが市場に残っているエージェントの中から最も好むエージェントを指す有向グラフを作成する。

2

グラフ内のすべてのサイクル(AがBを指し、BがCを指し、...、Aに戻るシーケンス)を見つける。

3

特定された各サイクルについて、取引を実行する:各エージェントは、自分が指したエージェントの財を受け取る。

4

取引されたエージェントとその財を市場から除去する。残りのエージェント間で選好の有向グラフを再構築し、それ以上サイクルが存在しなくなるまで繰り返す。

よくある落とし穴

  • パレート効率性と公平性またはエクイティとの混同;TTCは効率性を最大化するが、結果の均等性は最大化しない
  • すべての状況で戦略的証明可能性を仮定すること;TTCは真実であるのは特定の文脈(例:住宅市場、優先順位付けのある腎臓交換ではない)のみである
  • アルゴリズムは、それ以上有利なサイクルが存在しなくなったときに終了し、エージェントがマッチされないまま残る可能性があることを無視すること
  • TTCは無差別を伴わない厳密な選好を必要とすること;弱選好で適用するには拡張が必要であることを忘れること

よくある質問

資源配分においてパレート効率性が重要なのはなぜか?

パレート効率性は、他の誰かを悪化させることなく、あるエージェントをより良くすることができないことを保証する。「良い」割り当ての最小要件であり、これを侵害することは、資源が無駄にされており、誰かを利益のために再配分できることを意味する。

TTCは複数の異なる割り当てを生成できるか?

いいえ。TTCアルゴリズムは、その一意の選好グラフにより、一意のパレート効率的な割り当てを生成する。その割り当てへの道筋(サイクルの特定と取引実行の順序)は異なる場合があるが、最終的な結果は常に同じである。

すべてのドナー・レシピエントのペアが適合しない場合に、腎臓交換のためにTTCはどのように修正されるか?

腎臓交換では、選好グラフは適合するペアのみで構築される。アルゴリズムは次に、適合するエージェント間のサイクルと連鎖的な交換を特定し、生物学的な制約を考慮するために元のTTCを拡張する。

関連する手法

参考文献

  1. Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.

    DOI 文献を開く
    コピーしました。
  2. Roth, A. E., Sönmez, T., & Ünver, M. U. (2008). Efficient kidney exchange: Coincidence of wants in markets with compatibility. American Economic Review, 97(3), 828-851.

    DOI 文献を開く
    コピーしました。