Top Trading Cycle

Im Nachfolgenden wird der Top Trading Cycle (TTC) Algorithmus vorgestellt. Dabei wird dieser zunächst im Kontext der Immobilienwirtschaft eingeführt und anschließend auf das School-Choice-Problem adaptiert. Abschließend werden Eigenschaften des TTC diskutiert und gegebenenfalls bewiesen.

TTC - Immobilienwirtschaft

Shapley und Scarf^sha1974 haben ein Modell für den Häusertausch in der Immobilienwirtschaft entworfen. In diesem Modell existieren $n \in \N$ Agenten und jeder dieser Agenten besitzt genau ein Haus. Außerdem hat jeder Agent $a_i$ eine Präferenzliste $H_i$ über alle Häuser auf dem Markt. Die Präferenzliste stellt dabei die Vorlieben der Agenten über die einzelnen Häuser in Abhängigkeit zueinander dar. So ist das am meisten präferierte Haus eines Agenten an erster Stelle seiner Präferenzliste. Im Modell gibt es kein Geld und somit können keine Häuser gekauft werden. Die Agenten können jedoch mit Häusern handeln. Ziel ist es dabei, den Agenten nur durch Tauschhandel ein gemäß ihrer Präferenzen besseres Haus zuzuordnen. Im Folgenden ist die Ausgangslage zusammengefasst.

Das Problem wird als gerichteter bipartiter Graph modelliert. Dabei stellen die Agenten beziehungsweise die Häuser die Knoten dar. Jeder Agent $a_j$ zeigt auf sein am stärksten präferiertes verfügbares Haus $h_j^*$ aus $H_j$ und jedes Haus $h_i$ zeigt auf seinen Besitzer $a_i$. Ein verfügbares Haus ist dabei ein Haus, welches den Graphen noch nicht verlassen hat. Da somit jeder Agent eine eingehende Kante hat und die Präferenzlisten der Agenten vollständig sind, existiert in diesem gerichteten Graphen immer mindestens ein Kreis. Ein gerichteter Kreis $(a_1',h_1',...\ ,a_m',h_m')$ besteht dabei aus einer alternierenden Folge von Agenten und Häusern, wobei diese jeweils durch eine gerichtete Kante verbunden sind. In jedem dieser Kreise werden die involvierten Händel vollzogen. Das heißt jeder Agent im Kreis bekommt das Haus auf das er zeigt. Anschließend werden die beteiligten Häuser und Agenten aus dem Kreis entfernt. Bevor der Algorithmus wieder nach Kreisen sucht, werden die Zeiger, welche von den Agenten ausgehen, aktualisiert. Jeder Agent zeigt wieder auf sein am stärksten präferiertes verfügbares Haus.

Der Algorithmus terminiert, wenn keine Agenten mehr im Graph vorhanden sind. Das finale Matching besteht dann aus den Agent-Haus Paaren, welche den Graph im Verlauf gemeinsam verlassen haben. Im nachfolgenden Pseudocode wird illustriert, wie der TTC vorgeht.

Pseudocode - Top Trading Cycle

$M\leftarrow\emptyset$
$V\leftarrow A ~\dot{\cup}~ H$
$E\leftarrow \{(h_i,a_i),\ \forall (h_i,a_i) \in S \}\cup\{(a_j, h_j^*),\ \forall a_j \in A\}$
$G \leftarrow (V, E)$
$\mathbf{while}$ $\exists \ a$ in $V$ $\mathbf{do}$
  
Finde gerichteten Kreis $(a_1',h_1',...\ ,a_m',h_m')$ in $G$
  
$M\leftarrow M\cup \{\{a_1',h_1'\},...\ ,\{a_m',h_m'\}\}$
  
$V\leftarrow V\setminus \{a_1',h_1',...\ ,a_m',h_m'\}$
  
$E\leftarrow\{(h_i,a_i),\ \forall h_i \in V \}\cup\{(a_j, h_j^*),\ \forall a_j \in V\}$
$\mathbf{return} \ M$

Beispiel

In der nachfolgenden Slideshow ist ein Beispiel für das Vorgehen des TTC Algorithmus in der Immobilienwirtschaft anhand eines Graphen visualisiert. Dabei wird wie im vorherigen Pseudocode beschrieben vorgegangen. Der besseren Übersicht halber werden die an den gefundenen Kreisen beteiligten Agenten und Häuser nicht aus dem Graphen entfernt. Die in den Kreisen enthaltenen Zuweisungen werden trotzdem terminiert. In dem Graph stehen also ungerichtete Kanten für getroffene Zuweisungen und alle inzidenten Agenten und Häuser sind inaktiv. Das heißt, kein aktiver Knoten kann auf sie zeigen. Dies muss dann nur bei den Zeigeraktualisierungen der Agenten berücksichtigt werden. Das Beispiel bekommt als Eingabe die Menge an Agent-Haus-Paaren $S=\{(h_1,a_1),(h_2,a_2),(h_3,a_3),(h_4,a_4)\}$ sowie eine Präferenzliste $H_i$ für jeden Agenten $a_i$, welche in der Slideshow links neben den jeweiligen Agenten dargestellt sind.

Top Trading Cycle - School Choice

Die Ausgangslage beim School-Choice-Problem unterscheidet sich in einigen Punkten von der im vorherigen Kapitel beschriebenen Situation. Vergleicht man die beiden Ausgangslagen, wird der Unterschied schnell deutlich. Die Schulen sind hier vergleichbar mit den Häusern und die Schüler mit den Agenten. Analog zu den Agenten, zeigt hier jeder Schüler $p_i$ gemäß seiner Präferenzliste $\succ_{p_i}$ auf seine am stärksten präferierte verfügbare Schule $s_{i}^*$. Eine verfügbare Schule ist hierbei eine Schule, welche dem Schüler noch einen Platz anbieten kann. Die Präferenzlisten der Schüler unterscheiden sich hingegen von denen der Agenten. Im Allgemeinen wird davon ausgegangen, dass in den Präferenzlisten der Schüler nicht alle Schulen enthalten sind. Das bedeutet, dass die Schüler bei ihrer Schulwahl aus allen Schulen meist nur eine begrenzte Anzahl wählen dürfen. Dies hat zur Folge, dass nicht zwangsläufig jedem Schüler eine Schule zugeordnet werden kann. Um diesem Umstand Rechnung zu tragen, wird eine Warteliste $w$ eingeführt. Sollte ein Schüler im Laufe des Algorithmus nicht mehr zuweisbar sein, wird er auf die Warteliste gesetzt. Ein Schüler ist nicht mehr zuweisbar, wenn auf seiner Präferenzliste nur noch Schulen sind, welche nicht mehr verfügbar sind. Die gegebenen Präferenzlisten werden somit um die Warteliste $w$ als letztes Element für jeden Schüler $p_i$ erweitert. Eine veränderte Präferenzliste $\succ_{p_i}$ eines Schülers $p_i$ wäre zum Beispiel $(s_4, s_8, s_9, w)$ statt $(s_4, s_8, s_9)$. In der Immobilienwirtschaft gehört jedes Haus einem Agenten. Hier gehören die Schulen nicht den Schülern, sondern sind initial nicht belegt. Außerdem hat jede Schule eine Präferenzliste über die Schüler. Jedoch sind meist für Schulen keine strikten Präferenzlisten über die Schüler gegeben. Das heißt sie enthalten Indifferenzen. Diese werden aufgelöst indem eine zufällige Reihenfolge über die indifferenten Schüler erzeugt wird. Eine veränderte Präferenzliste $\succ_{s_j}$ einer Schule $s_j$ wäre zum Beispiel $(p_4,p_2,p_5,p_6)$ statt $(\{p_2,p_4\},p_5,p_6)$. Folglich zeigt jede Schule $s_j$ nicht auf ihren Besitzer, sondern auf ihren am stärksten präferierten verfügbaren Schüler $p_j^*$ gemäß ihrer Präferenzliste $\succ_{s_j}$. Ein verfügbarer Schüler ist hierbei ein Schüler, welcher noch keiner Schule zugeordnet wurde. Des Weiteren gibt es noch eine Kapazität $C_j \in \N$ pro Schule $s_j$. Diese beschreibt, wie viele Schüler eine Schule aufnehmen kann. Für den Algorithmus bedeutet dies, dass der Schule $s_j$ maximal $C_j$ Schüler zugewiesen werden können. Um dies zu gewährleisten, wird hier ein Zähler $c_j$ für jede Schule $s_j$ eingeführt, welcher die derzeitige Auslastung angibt. Wenn für eine Schule die Kapazität erreicht ist, ist diese nicht mehr verfügbar und kein Schüler kann mehr auf sie zeigen.

Ablauf des Algorithmus

Pseudocode - Top Trading Cycle School Choice

$M\leftarrow\emptyset$, $c_j\leftarrow0$ $\forall s_j\in S$
$V\leftarrow P ~ \dot{\cup} ~ \{S ~ \cup ~ \{w\}\}$
Löse für jede Schule $s_j\in S$ Indifferenzen in $\succ_{s_j}$ auf
Erweitere $\succ_{p_i}$ für alle $p_i\in P$ um $w$ als letztes Element
$E\leftarrow \{(p_i,s_{i}^*),\ \forall p_i \in P \}\cup\{(s_j,p_j^*),\ \forall s_j \in S\}$
$G \leftarrow (V, E)$
$\mathbf{while} \ \exists \ p$ in $V$ $\mathbf{do}$
  
$\mathbf{while} \ \exists$ gerichteter Kreis $K=(p_1',s_1',...\ ,p_m',s_m')$ in $G$ $\mathbf{do}$
    
$M\leftarrow M\cup \{\{p_1',s_1'\},...\ ,\{p_m',s_m'\}\}$
    
$V\leftarrow V\setminus \{p_1',...\ ,p_m'\}$
    
$c_j\leftarrow c_j+1$, für alle $s_j' \in K$
    
$\mathbf{for~each}~{s_j' \in K}~\mathbf{do}~$
      
$\mathbf{if}$ $c_j=C_j$ $\mathbf{then}$
        
$V\leftarrow V\setminus s_j'$
  
$E\leftarrow \{(p_i,s_{i}^*),\ \forall p_i \in V\}\cup\{(s_j,p_j^*),\ \forall s_j \in V\}$
  
$\mathbf{for~each}~{p_i \in V}~\mathbf{do}~$
    
$\mathbf{if}$ $s_{i}^*=w$ $\mathbf{then}$
      
$M\leftarrow M\cup \{p_i,w\}$
      
$V\leftarrow V\setminus p_i$
$\mathbf{return} \ M$

Beispiel

Nachfolgend wird das Vorgehen des Algorithmus' anhand eines Beispiels dargestellt. Der besseren Übersicht halber werden auch hier die an den gefundenen Kreisen beteiligten Schüler und Schulen nicht aus dem Graphen entfernt. Die in den Kreisen enthaltenen Zuweisungen werden trotzdem terminiert. In dem Graph stehen also ungerichtete Kanten für getroffene Zuweisungen und alle Beteiligten sind inaktiv. Das heißt kein aktiver Beteiligter darf auf sie zeigen. Dies muss dann sowohl bei den Zeigeraktualisierungen der Schulen als auch bei denen der Schüler beachtet werden. Das Beispiel bekommt die Menge der Schulen $S = \{s_1,s_2,s_3\}$ und die Menge der Schüler $P = \{p_1,p_2,p_3,p_4,p_5\}$ als Eingabe. Außerdem noch die zugehörigen Kapazitäten $C_j$ und Präferenzlisten $\succ_{s_j}$ für jede Schule $s_j$, sowie die Präferenzlisten $\succ_{p_i}$ für jeden Schüler $p_i$, welche in der Slideshow jeweils neben den Schulen beziehungsweise den Schülern dargestellt sind.

Eigenschaften des Algorithmus

Stabilität

Pareto-Effizienz

Strategiesicherheit

Rangmaximalität

Kardinalitätsmaximalität