Top Trading Cycle
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.[1]:30–31
Wohnungsmarkt
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:
- Jeder Teilnehmer zeigt jeweils auf den Teilnehmer, der in seiner Lieblingswohnung wohnt.
- Nun muss es mindestens einen Kreis geben. Dabei kann es sein, dass dieser Kreis die Länge 1 hat, also ein Teilnehmer auf sich selbst zeigt, da er bereits in seiner Lieblingswohnung wohnt.
- Implementiere den mit dem Kreis verbundenen Austausch, also teile allen Teilnehmern im Kreis die Wohnung zu, auf die sie zeigen, und entferne diese Teilnehmer aus dem Diagramm.
- Wenn noch Teilnehmer übrig sind, gehe zurück zu Schritt 1, wobei jetzt jeder Teilnehmer auf den verbleibenden Teilnehmer zeigt, der in seiner verbleibenden Lieblingswohnung wohnt.
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:[2]:223–224 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.
Weiterentwicklungen
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:
- Der TTC-Algorithmus wurde für eine Situation weiterentwickelt, in der es zusätzlich zu den schon in den Wohnungen wohnenden Studenten auch neue Studenten ohne Häuser und leere Wohnungen ohne Studenten gibt.[3]
- Der TTC-Algorithmus wurde für die Schulwahl weiterentwickelt.[4] Ein Schulbezirk in New Orleans (Recovery School District) übernahm eine Schulwahl-Version des TTC im Jahr 2012.[5]
- Der TTC-Algorithmus wurde im Rahmen des Nierentauschs weiterentwickelt. Der erweiterte Algorithmus heißt Top Trading Cycles and Chains (TTCC).[6]
Implementierung in Softwarepaketen
Einzelnachweise
- Lloyd Shapley, Herbert Scarf: On cores and indivisibility. In: Journal of Mathematical Economics. 1, 1974, S. 23. doi:10.1016/0304-4068(74)90033-0.
- Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
- Atila Abdulkadiroğlu, Tayfun Sönmez: House Allocation with Existing Tenants. In: Journal of Economic Theory. 88, Nr. 2, 1999, S. 233–260. doi:10.1006/jeth.1999.2553. Siehe auch Präsentation von Katharina Schaar.
- Atila Abdulkadiroğlu, Tayfun Sönmez: School Choice: A Mechanism Design Approach. In: American Economic Review. 93, Nr. 3, 2003, S. 729–747. doi:10.1257/000282803322157061.
- Andres Vanacore: Centralized enrollment in Recovery School District gets first tryout. In: The Times-Picayune, 16. April 2012. Abgerufen am 4. April 2016.
- Alvin Roth, Tayfun Sönmez, M. Utku Unver: Kidney Exchange. In: Quarterly Journal of Economics. 119, Nr. 2, 2004, S. 457–488. doi:10.1162/0033553041382157.
- Thilo Klein: Analysis of Stable Matchings in R: Package matchingMarkets. In: Vignette to R Package matchingMarkets. 2015.
- matchingMarkets: Analysis of Stable Matchings. In: R Project.
- MatchingTools API.