Wie funktionieren Märkte, in denen diejenigen, die etwas liefern, nicht finanziell kompensiert werden dürfen oder können? Der Empfänger darf den Spender eines Organs nicht entlohnen. Studienanfängern ist es verwehrt, Studienplätze zu kaufen. Es gibt unzählige Beispiele solcher Zuordnungsprobleme. Ist ein Zuordnungsmarkt dezentral organisiert, treten oft krasse Ineffizienzen auf. Studienanfänger akzeptieren Studienplätze, die sie eigentlich nicht wollen. Spenderorgane finden nicht den bedürftigsten oder medizinisch passendsten Patienten. Auf der anderen Marktseite bleiben Studienplätze unbesetzt, Patienten sterben.
Elegante Lösung von Zuordnungsproblemen
Lloyd Shapley, Weggefährte des A-Beautiful-Mind-Protagonisten und Nobelpreisträgers John Nash, hat in den Jahren 1962 und 1974, in kurzen Aufsätzen mit David Gale beziehungsweise Herbert Scarf, gezeigt, dass sich solche Zuordnungsprobleme elegant lösen lassen, wenn alle Betroffenen an einem zentralisierten Verfahren teilnehmen.
Gales und Shapleys (1962) zentrale Idee ist der Algorithmus der aufgeschobenen Zusagen (deferred-acceptance-Algorithmus). Sie veranschaulichen den Algorithmus anhand eines stilisierten Heiratsmarktes mit einer identischen Anzahl von Frauen und Männern. Jede Frau ordnet die Männer gemäß ihrer Präferenzen, jeder Mann die Frauen. Gale und Shapley beweisen mathematisch, dass ihr Algorithmus immer eine stabile Zuordnung erzielt, egal wie viele Marktteilnehmer es gibt und egal welche individuell verschiedenen Präferenzen diese haben. Instabilität einer Zuordnung würde bedeuten, dass es mindestens eine Frau und einen Mann gibt, die lieber miteinander gepaart wären als mit den bisher zugeordneten Partnern. Wenn diese ihre bisherigen Partner verlassen, zerbricht die Zuordnung. Ohne eine zentralisierte Zuordnung wird unter Umständen niemals Stabilität erreicht. Der Algorithmus löst dieses Problem.
In der ersten Runde des Algorithmus zeigt jede Frau auf den ihrer Ansicht nach attraktivsten Partner. Jeder Mann, der mindestens eine Bewerberin hat, wird der seiner Ansicht nach attraktivsten Bewerberin vorläufig zugeordnet. Die Frauen, die in der ersten Runde nicht vorläufig zugeordnet wurden, zeigen auf den jeweils zweitattraktivsten Partner. Jeder Mann, der mindestens eine Bewerberin hat, wird der seiner Ansicht nach attraktivsten aller seiner bisherigen Bewerberinnen vorläufig zugeordnet. In jeder Runde zeigen diejenigen Frauen, die am Ende der vorherigen Runde nicht vorläufig zugeordnet sind, auf den jeweils nächstattraktiven Partner. Der Algorithmus endet damit, dass alle Frauen und Männer zugeordnet sind.
Shapley und Scarf (1974) analysieren einen verwandten Algorithmus (David Gales' top-trading-cycle-Algorithmus) für Märkte, in denen Individuen unteilbare heterogene Güter besitzen. Durch eine Abfolge von potenziell komplexen Tauschhandlungen wird wiederum eine stabile Zuordnung erreicht.
Von der Theorie zur praktischen Anwendung
Alvin Roth, der in Harvard lehrt und fast 30 Jahre jünger ist als Shapley, ging den langen Weg von der Theorie bis zur praktischen Anwendung von Shapleys Ideen. Roth begann damit, Shapleys Algorithmen auf ihre strategische Robustheit hin zu untersuchen. Wenn die Teilnehmer starke Anreize hätten, ihre Präferenzen gegenüber dem Algorithmus falsch anzugeben, wären die Algorithmen nicht praktikabel. Roths entscheidender Schritt in die praktische Anwendung war die Reform eines Zuordnungsalgorithmus von Absolventen medizinischer Hochschulen und Krankenhäusern in den USA. Seither wurde mit Roths Hilfe eine Reihe von Zuordnungsmärkten, vor allem in den USA, reformiert oder neu geschaffen.
Besonders beeindruckend sind Roths Reformen bei der Zuordnung von Spendernieren in den USA. Roth (2004, mit Tayfun Sönmez und Utku Ünver) erkannte, dass der top-trading-cycle-Algorithmus an die speziellen Anforderungen dieses Zuordnungsproblems angepasst werden kann.
Impulse für einen sehr aktiven Forschungszweig
Angenommen, Patient A in Los Angeles hat einen Verwandten, welcher eine Niere spenden möchte, die aber nicht passend für Patient A ist. Die Niere passt hervorragend für einen fremden Patienten B in San Francisco. Patient B hat einen spendewilligen Verwandten, dessen Niere zu Patient C in Denver passt, und die Niere eines Verwandten von Patient C passt zu Patient A. Durch die gleichzeitige Operation der sechs Betroffenen können alle drei Patienten gerettet werden. Die zentralisierte Anwendung des top-trading-cycle-Algorithmus ermöglicht, solche Tauschketten zu finden und Tauschhandlungen insgesamt effizient zu strukturieren. Es ist deshalb nicht übertrieben zu sagen, dass eine wachsende Zahl von Dialyse-Patienten ihr Leben Alvin Roth verdankt.
Erweiterungen der Ideen von Shapley und Roth bilden einen sehr aktiven Forschungszweig. Es bleibt zu wünschen, dass diese Ideen auch in Europa vermehrt praktische Anwendungen finden werden. Es steht viel auf dem Spiel.
Literatur:
Economic Sciences Price Committee (2012), "Information for the Public: Stable matching: Theory, evidence, and practical design". Economic Sciences Price Committee (2012), "Scientific Background on the Sverige Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012: Stable Allocations and the Practice of Market Design".
Gale, D., und Shapley, L. (1962), "College admissions and the stability of marriage", American Mathematical Monthly 69, 9-15.
Osborne, M. (2004), "An Introduction to Game Theory" (Chapter 8), Oxford University Press. Roth, A., Sönmez, T. und Ünver, M. (2004), "Kidney Exchange", Quarterly Journal of Economics 119. Shapley, L., und Scarf, H. (1974), "On cores and indivisibility", Journal of Mathematical Economics 1, 23-37.