トップ取引サイクル

トップトレーディングサイクル（TTC）は、お金を使わずに分割できないアイテムを取引するためのアルゴリズムです。これはデビッド・ゲイルによって開発され、ハーバート・スカーフとロイド・シャプレーによって公開されました。^{[1] ：30–31}

基本的な TTC アルゴリズムは、次の住宅割り当て問題で説明されます。学生寮には学生が住んでいます。各学生は 1 つの住宅に住んでいます。各学生には住宅に対する好みの関係があり、一部の学生は他の学生に割り当てられた住宅を好みます。これにより、相互に有益な交換が発生する可能性があります。たとえば、学生 1 が学生 2 に割り当てられた住宅を好み、その逆の場合、住宅を交換することで両者とも利益を得ます。目標は、コア安定割り当て、つまり相互に有益な交換がすべて実現されるように (つまり、住宅を交換しても状況を改善できない学生グループが一緒にならない) 学生への住宅の再割り当てを見つけることです。 ${\displaystyle n}$

アルゴリズムは次のように動作します。

1. 各エージェントに「トップ」（最も好む）住宅を指定してもらいます。
2. 各エージェントから、のトップハウスを保持するエージェント ( と表記) まで矢印を描きます。${\displaystyle i}$${\displaystyle \operatorname {Top} (i)}$${\displaystyle i}$
3. グラフには少なくとも 1 つのサイクルが存在する必要があることに注意してください (エージェントが現在自分の最上位の家を所有している場合、これは長さ 1 のサイクルになる可能性があります)。このサイクルで示される取引を実装し (つまり、各家をそれを指すエージェントに再割り当てします)、関係するすべてのエージェントをグラフから削除します。${\displaystyle i}$
4. エージェントが残っている場合は、手順 1 に戻ります。

各反復で少なくとも 1 つのエージェントを削除するため、アルゴリズムは終了する必要があります。このアルゴリズムにより、コアが安定した割り当てが実現されることが証明されています。

例えば、^{[2] :223–224では}、エージェントの優先順位が次のようになっていると仮定します（最大で上位4つの選択肢のみが関連します）。

最初の反復では、唯一のトップ取引サイクルは {3} (長さ 1 のサイクル) であるため、エージェント 3 は現在の家を維持し、市場を離れます。

2 回目の反復では、エージェント 1 のトップ ハウスは 2 です (ハウス 3 は利用できないため)。同様に、エージェント 2 のトップ ハウスは 5、エージェント 5 のトップ ハウスは 1 です。したがって、{1,2,5} はトップ取引サイクルです。実装すると、エージェント 1 はハウス 2、エージェント 2 はハウス 5、エージェント 5 はハウス 1 を取得します。これら 3 つのエージェントは市場から退出します。

3 回目の反復では、トップ取引サイクルは {4,6} なので、エージェント 4 と 6 は家を交換します。エージェントはもう残っていないので、ゲームは終了します。最終的な割り当ては次のようになります。

この配分は中核的に安定しており、相互交換によって状況を改善できる連合はない。

同じアルゴリズムは他の状況でも使用できます。たとえば、^[2]夜勤に割り当てられている医師が 7 人いるとします。各医師は週 1 日の夜勤に割り当てられます。一部の医師は、他の医師に割り当てられたシフトを好みます。TTC アルゴリズムは、ここで最大限の相互利益のある交換を達成するために使用できます。

TTCは真実のメカニズムです。これはアルビン・ロスによって証明されました。^[3]

選好が厳密な場合 (無差別がない場合)、TTC は常に厳密にパレート効率的な割り当てを見つけます。さらに、常にコア安定割り当てを見つけます。さらに、厳密な選好では、一意のコア安定割り当てがあり、それが TTC によって見つけられた割り当てです。

厳密な選好領域では、TTCは個人合理性、パレート効率性、戦略耐性を満たす唯一のメカニズムである。^{[4] [5]}

オリジナルのTTCアルゴリズムでは、選好が厳格であると想定されており、各エージェントは常に1つのトップハウスを持っています。現実的な設定では、エージェントはハウス間で無差別であり、エージェントは2つ以上のトップハウスを持つ場合があります。この設定に対して、いくつかの異なるアルゴリズムが提案されています。^{[6] [7]}これらは後にいくつかの方法で一般化されました。^{[8] [9] [10]}一般的なスキームは次のとおりです。

1. 各エージェントに、最も得意とする物件をすべて挙げてもらいます。
2. TTC グラフ Gを構築します。これは、各エージェントが自分の最上位の住宅を保有するすべてのエージェントを指す有向グラフです。
3. 繰り返す：
   • Gの強連結成分を分析します。
   • シンク(出力エッジを持たないコンポーネント (少なくとも 1 つあります)) を識別します。
   • ターミナル シンク(各エージェントが最優先の選択肢の 1 つを所有しているシンク) を特定します。
     • ターミナルシンクがない場合は、中断して手順 4 に進みます。
     • それ以外の場合、各ターミナルシンクSについて、 S内の各エージェントを現在の家に永続的に割り当て、それらを市場から削除し、TTC グラフを更新して、ステップ 3 に戻ります。
4. 事前に決定された選択ルールを使用して、互いに素な取引サイクルのセットを選択します。これらのサイクルによって示される取引を実行し、それらを市場から削除します。
5. エージェントが残っている場合は、手順 1 に戻ります。

メカニズムはステップ4で使用される選択ルールによって異なります。選択ルールはいくつかの条件を満たす必要があります。^[9]

• 一意性: このルールは、各エージェントに対して、そのエージェントの最上位のハウスの中から一意のハウスを選択します。
• 終了: ルールを使用するアルゴリズムは終了することが保証されます。
• 持続性: ルールによって得られた縮小グラフでは、不満足なエージェントi (最上位の住宅を保有していないエージェント)で終わる各有向パスは持続的です。つまり、エージェントi が市場を離れるか、住宅を売却するまで、パスはグラフ内に残ります。
• 不満足なエージェントの独立性: エージェントiが不満足で、 2 つの TTC グラフがiから出るエッジのみ異なる場合、縮小された TTC グラフもiから出るエッジのみが異なります。

選択ルールが一意性と終了性を満たす場合、結果として得られるメカニズムは、パレート効率的で弱いコア（エージェントのサブセットが、彼ら自身間で取引することによって、彼ら全員にとって厳密により良い家を得ることができない）の割り当てを生み出します。弱いコアは、それが個別に合理的であることも意味します。さらに、選択ルールが持続性、不満足なエージェントの独立性、およびその他の技術的条件を満たす場合、結果として得られるメカニズムは戦略証明可能です。

これらの条件を満たす特定の選択ルールは、最高優先度オブジェクト（HPO）ルールです。これは、事前に決定された家の優先順位を前提としています。それは次のように機能します。^[9]

• (a) 不満を持つエージェントは全員、自分のトップハウスの中で最も優先度の高いハウスの所有者を指します。不満を持つエージェントにはラベルが付けられます。
• (b) ラベル付けされていないエージェントのうち、ラベル付けされたエージェントが所有する最上位の家を持つエージェントを検討します。その中から、最も優先度の高い家を所有するエージェントi を選択します。iがラベル付けされたエージェントが所有する最も優先度の高い家を指すようにします。エージェントiにラベルを付けます。
• (c) ラベルのないエージェントがある場合は、(b) に戻ります。

ルールが終了すると、すべてのエージェントにラベルが付けられ、ラベルが付けられたエージェントにはそれぞれ固有の出力エッジがあります。ルールは、各反復で、すべてのサイクルに少なくとも 1 つの不満足なエージェントが含まれることを保証します。したがって、各反復で、少なくとも 1 つの新しいエージェントが満足します。したがって、アルゴリズムは最大n回の反復後に終了します。各反復の実行時間は です。ここで、 は無差別クラスの最大サイズです。したがって、合計実行時間は です。 ${\displaystyle O(n\log {n}+n\gamma )}$${\displaystyle \gamma}$${\displaystyle O(n^{2}\log {n}+n^{2}\gamma )}$

TTC アルゴリズムはさまざまな方法で拡張されてきました。

1. すでに住宅に住んでいる学生に加えて、住宅を持たない新入生や、学生が住んでいない空き家もあるという状況。^[11]

2.学校選択制度。^[12]ニューオーリンズ復興学区は2012年にTTCの学校選択制度を採用した。^[13]

3.腎臓交換の設定：トップトレーディングサイクルとチェーン（TTCC）。^[14]

• R：住宅市場問題のためのトップトレーディングサイクルアルゴリズムがパッケージの一部として実装されていますmatchingMarkets。^{[15] [16]}
• API : MatchingTools APIは、Top-Trading-Cyclesアルゴリズム用の無料のアプリケーションプログラミングインターフェイスを提供します。^[17]

• 交換経済
• 住宅市場