Der Top Trading Cycle (TTC) ist ein Algorithmus für den Handel mit unteilbaren Gütern ohne den Einsatz von Geld. Er wurde von David Gale entwickelt und von Herbert Scarf und Lloyd Shapley vorgestellt.
Der grundlegende TTC-Algorithmus lässt sich mit der folgenden Situation auf dem Wohnungsmarkt illustrieren: n Studenten wohnen in Studentenwohnheimen. Jeder Student lebt in jeweils einer Wohnung. Jeder Student hat eine Präferenzrelation über die Wohnungen. Nun kann es vorkommen, dass manche Studenten die Wohnung eines anderen Studenten besser als die eigene finden, wodurch ein Austausch zum gegenseitigen Vorteil möglich sein kann. Wenn zum Beispiel Student 1 die Wohnung von Student 2 bevorzugt und andersherum, dann werden beide davon profitieren, wenn sie ihre Wohnungen tauschen. Das Ziel besteht darin eine Zuordnung zu finden, bei der kein weiterer Tausch existiert, der alle Beteiligten besser stellt. Man sagt, dass sich eine solche Zuordnung im Kern befindet, da keine Gruppe von Studenten ihre Situation gemeinsam dadurch verbessern kann, dass sie ihre Wohnungen erneut tauscht.
Der Algorithmus funktioniert folgendermaßen:
Der Algorithmus muss enden, weil in jeder Wiederholung ein Kreis bestehend aus mindestens einem Teilnehmer entfernt wird. Es kann gezeigt werden, dass dieser Algorithmus zu einer Allokation führt, die sich im Kern befindet.
Beispiel: Die Teilnehmer haben folgende Präferenzen über die verfügbaren Wohnungen, wobei nur maximal die obersten vier Präferenzen eines Teilnehmers bezüglich der Wohnungen relevant sind.
| Teilnehmer | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Erstwunsch | 3 | 3 | 3 | 2 | 1 | 2 |
| Zweitwunsch | 2 | 5 | 1 | 5 | 3 | 4 |
| Drittwunsch | 4 | 6 | 6 | 2 | 5 | |
| Viertwunsch | 1 | 4 | 6 |
In der ersten Runde existiert nur ein einziger Kreis. In diesem Fall zeigt Teilnehmer 3 auf sich selbst und es gibt den TTC {3}.
Nachdem Teilnehmer 3 den Markt verlassen hat, beginnt Runde 2. Jetzt zeigt Teilnehmer 1 auf Teilnehmer 2, Teilnehmer 2 auf Teilnehmer 5 und Teilnehmer 5 auf Teilnehmer 1, sodass sich erneut ein Kreis ergibt, der TTC {1,2,5}. Diese drei Teilnehmer tauschen entsprechend ihre Wohnungen und verlassen den Markt.
In der dritten Runde zeigt Teilnehmer 4 auf Teilnehmer 6 und umgekehrt, sodass sich der TTC {4,6} ergibt. Weil keine Teilnehmer mehr übrig sind, ist das Spiel vorbei. Die endgültige Allokation ist folgende:
| Teilnehmer | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Wohnung | 2 | 5 | 3 | 6 | 1 | 4 |
Diese Allokation befindet sich im Kern, da keine Gruppe von Teilnehmern ihre Situation durch gegenseitigen Austausch verbessern kann.
Der gleiche Algorithmus kann auch in anderen Situationen verwendet werden. Man nehme beispielsweise an, es gebe sieben Ärzte, die jeweils einer Nachtschicht in der Woche zugeteilt wurden. Manche Ärzte bevorzugen die Schichten, die anderen Ärzten gegeben wurden. Der TTC-Algorithmus kann hier eingesetzt werden, um den für alle vorteilhaftesten Austausch zu erreichen.
Der TTC-Algorithmus ist der einzige Mechanismus, der den Anforderungen der individuellen Rationalität, der Pareto-Effizienz und der Strategiesicherheit im klassischen Shapley-Scarf-Modell genügt. Dadurch ist er die folgerichtige Wahl für ähnliche Situationen. Hier einige wichtige Erweiterungen des TTC: