Zum Inhalt springen
Zurück zu den Suchergebnissen

Top Trading Cycles

Eingeführt von
Lloyd Shapley, Herbert Scarf
Jahr
1974
Typ
algorithm
Familie
Game-theoretic

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Top Trading Cycles (TTC) ist ein Algorithmus zur Zuteilung von unteilbaren Gütern an Agenten, sodass die Zuteilung Pareto-effizient und individuell rational ist.

Der 1974 von Lloyd Shapley und Herbert Scarf entwickelte Algorithmus identifiziert Handelszyklen in einem Präferenz-Digraphen, führt diese Handelsgeschäfte aus und wiederholt den Vorgang iterativ, bis keine weiteren Handelsgeschäfte vorteilhaft sind. TTC wird aufgrund seiner Effizienz und einfachen Implementierung häufig im Bereich des Nierenaustauschs und der Wohnungsvermittlung eingesetzt.

Die Intuition hinter der Methode

Stellen Sie sich eine Gruppe von Personen vor, von denen jede ein Haus besitzt, und jede Person alle Häuser nach Präferenz ordnet. Der TTC-Algorithmus fragt: Wer ist mein Favorit? Zeigen Sie auf ihn. Schauen Sie nun, wer auf Sie gezeigt hat. Wenn es sich um einen Zyklus handelt (A zeigt auf B, B zeigt auf C, C zeigt auf A), führen Sie diese Tauschgeschäfte aus – A erhält das Haus von B, B erhält das Haus von C, C erhält das Haus von A. Jeder im Zyklus ist glücklich, weil er das Haus von jemandem erhalten hat, den er seinem aktuellen Haus vorzieht. Entfernen Sie den Zyklus und wiederholen Sie den Vorgang, bis keine weiteren Zyklen mehr existieren. Das Ergebnis ist effizient, da alle vorteilhaften Tauschgeschäfte durchgeführt werden.

Geschichte

Lloyd Shapley und Herbert Scarf führten den Top Trading Cycles-Algorithmus 1974 als Lösung für das Wohnungsproblem ein und bewiesen, dass er eindeutige Pareto-effiziente Zuteilungen liefert. Der Algorithmus gewann durch die Arbeit von Alvin Roth am Nierenaustausch, wo er zentral für das Matching von Spendern und Empfängern wurde, an praktischer Bedeutung. Der Nobelpreis 2012 für Roth bestätigte die Bedeutung von TTC für das reale Marktdesign, insbesondere bei der Organtransplantation.

Wann wird sie eingesetzt?

Wenden Sie TTC bei der Zuteilung unteilbarer Güter (Häuser, Organe, Schulplätze) an Agenten mit strengen Präferenzen für Bündel an. Verwenden Sie es, wenn Pareto-Effizienz unerlässlich ist und keine monetären Transfers verfügbar oder wünschenswert sind. TTC ist ideal für dezentrale Märkte, auf denen Agenten vorteilhafte Tauschgeschäfte lokal identifizieren können. Funktioniert am besten, wenn Agenten vollständige, azyklische Präferenzinformationen haben.

Grenzen und Hinweise

  • Erfordert strenge Präferenzordnungen ohne Indifferenz; Erweiterungen auf schwache Präferenzen sind komplex
  • Nicht koalitionsresistent: Koalitionen von Agenten können Präferenzen falsch angeben, um das kollektive Ergebnis zu verbessern
  • Sensitivität gegenüber Präferenzzyklen: Das Nichtvorhandensein von Zyklen kann dazu führen, dass einige Agenten unvermittelt bleiben
  • Beschränkt auf Matching ohne monetäre Transfers; ineffizient bei heterogenen Bewertungen

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Pareto-effizient: Es gibt keine handelsfreien Verbesserungen; alle gegenseitig vorteilhaften Tauschgeschäfte werden ausgeführt
  • Individuell rational: Jeder Agent bevorzugt die endgültige Zuteilung schwach gegenüber seiner anfänglichen Ausstattung
  • Strategie-resistent in bestimmten Konstellationen: Agenten können sich nicht verbessern, indem sie Präferenzen falsch angeben
  • Recheneffizient: Polynomielle Zeit mit einfacher Implementierung
  • Transparent: Agenten verstehen, wie ihre gewählte Option zur Zuteilung führt

Anwendungen

  • Nierenaustausch: Abgleich von Organspendern und -empfängern zur Erhöhung der Transplantationskompatibilität durch Mehrparteien-Austauschgeschäfte
  • Wohnungsvermittlung: Effiziente Zuweisung von Universitätswohnheimzimmern oder Sozialwohnungen
  • Schulwahl: Zuweisung von Schülern zu Schulen mit Kapazitätsbeschränkungen und Präferenzvielfalt
  • Leberlappenaustausch: Ermöglichung von Paaraustauschgeschäften für Lebendspender-Lebertransplantationen
  • Möbel- und Tauschhandel: Organisation effizienter Tauschgeschäfte auf Community-Sharing-Plattformen

So funktioniert es

So funktioniert es

1

Erstellen Sie einen gerichteten Graphen, in dem jeder Agent auf den Agenten mit der höchsten Präferenz unter denen zeigt, die sich noch auf dem Markt befinden.

2

Finden Sie alle Zyklen im Digraphen (Sequenzen, bei denen A auf B zeigt, B auf C, ..., zurück zu A).

3

Führen Sie für jeden identifizierten Zyklus die Tauschgeschäfte aus: Jeder Agent erhält die Ausstattung des Agenten, auf den er gezeigt hat.

4

Entfernen Sie gehandelte Agenten und ihre Ausstattungen vom Markt. Rekonstruieren Sie den Präferenz-Digraphen unter den verbleibenden Agenten und wiederholen Sie den Vorgang, bis keine weiteren Zyklen mehr existieren.

Häufige Fallstricke

  • Verwechslung von Pareto-Effizienz mit Fairness oder Gerechtigkeit; TTC maximiert die Effizienz, aber nicht die Gleichheit der Ergebnisse
  • Annahme von Strategie-Resistenz in allen Konstellationen; TTC ist nur in bestimmten Kontexten wahrheitsgemäß (z. B. Wohnungsmarkt, nicht Nierenaustausch mit Priorisierung)
  • Übersehen, dass der Algorithmus terminiert, wenn keine profitablen Zyklen mehr existieren, was potenziell Agenten unvermittelt lässt
  • Vergessen, dass TTC strenge Präferenzen ohne Indifferenz erfordert; die Anwendung mit schwachen Präferenzen erfordert eine Erweiterung

Häufig gestellte Fragen

Warum ist Pareto-Effizienz bei der Ressourcenallokation wichtig?

Pareto-Effizienz stellt sicher, dass kein Agent besser gestellt werden kann, ohne einen anderen schlechter zu stellen. Sie ist eine Mindestanforderung für eine 'gute' Zuteilung; die Verletzung bedeutet, dass Ressourcen verschwendet werden und neu zugewiesen werden könnten, um jemandem zugutezukommen.

Kann TTC mehrere verschiedene Zuteilungen erzeugen?

Nein. Der TTC-Algorithmus erzeugt mit seinem eindeutigen Präferenz-Digraphen eine eindeutige Pareto-effiziente Zuteilung. Der Weg zu dieser Zuteilung (Reihenfolge der Zyklenerkennung und Ausführung von Tauschgeschäften) kann variieren, aber das Endergebnis ist immer dasselbe.

Wie wird TTC für den Nierenaustausch modifiziert, wenn nicht alle Spender-Empfänger-Paare kompatibel sind?

Beim Nierenaustausch wird der Präferenz-Digraph nur über kompatible Paare konstruiert. Der Algorithmus identifiziert dann Zyklen und Ketten von Austauschgeschäften zwischen kompatiblen Agenten und erweitert das ursprüngliche TTC, um biologische Einschränkungen zu berücksichtigen.

Verwandte Methoden

Quellen

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

    DOI-Referenz öffnen
    Kopiert.
  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-Referenz öffnen
    Kopiert.