Gale und Shapleys Algorithmus von 1962 machte Matching-Märkte ehrlich

David Gale und Lloyd Shapley veröffentlichten 1962 „College Admissions and the Stability of Marriage“ im American Mathematical Monthly. Sie fragten, ob stabile Matchings – Zuordnungen, bei denen kein Paar von Akteuren lieber miteinander zusammen wäre – in zweiseitigen Märkten wie Ehe oder Studienzulassung immer existieren.

Ihre Antwort war konstruktiv: der Algorithmus der verzögerten Annahme (deferred acceptance), bei dem eine Seite Angebote macht und die andere vorläufige Angebote hält, endet stets in einem stabilen Matching. Dasselbe Verfahren liefert der anbietenden Seite ihr bestmögliches stabiles Ergebnis, weshalb die wahrheitsgemäße Rangfolge für die Anbietenden die dominante Strategie ist.

Fünfzig Jahre später verlieh die Königlich Schwedische Akademie den Wirtschaftspreis 2012 an Shapley und Alvin Roth „für die Theorie stabiler Allokationen und die Praxis der Marktgestaltung“. Roth hatte gezeigt, dass Stabilität erklärt, welche realen Märkte überleben, und baute die Facharztvermittlung (residency match), die Schulwahl und den Nierenaustausch auf diesem Algorithmus neu auf.

Verzögerte Annahme findet für alle ein stabiles Matching

Existenz plus ein Algorithmus machten Stabilität nutzbar statt abstrakt.

Wahrheitsgemäße Präferenzlisten wurden zur dominanten Strategie für die Anbietenden.

Er gab Gestaltern eine Linse: stabile Märkte überleben, instabile brechen zusammen.

Er trieb praktische Neugestaltungen in Medizin, Bildung und Organaustausch voran.

Bevor man einen Markt aufbaut, sollte man prüfen, ob der Matching-Mechanismus stabil und strategiefest ist: Wenn Falschangaben sich lohnen, füllt sich der Markt mit Manipulation. Ein Algorithmus, der Ehrlichkeit optimal macht, ist Marktgestaltung.

Der Algorithmus wurde zum Motor der Neugestaltung der US-Facharztvermittlung, der Schulwahl in Boston und New York sowie von Nierenaustausch-Ketten – alle in der Nobel-Begründung genannt. Gale-Shapley gehört heute zum Standardvokabular in Marktgestaltung, Operations Research und Informatik.