Top Trading Cycle
# 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.^{: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:^{: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.
* Der TTC-Algorithmus wurde für die Schulwahl weiterentwickelt. Ein Schulbezirk in New Orleans (Recovery School District) übernahm eine Schulwahl-Version des TTC im Jahr 2012.
* Der TTC-Algorithmus wurde im Rahmen des Nierentauschs weiterentwickelt. Der erweiterte Algorithmus heißt Top Trading Cycles and Chains (TTCC).

## Implementierung in Softwarepaketen

* R: Der TTC-Algorithmus für das Wohnungsmarktproblem ist im Paket matchingMarkets implementiert.
* API: Die MatchingTools API stellt den TTC-Algorithmus über eine freie Programmierschnittstelle zur Verfügung.
