Kapitel 12Mechanismusdesign und Marktdesign

Einleitung

Kapitel 11 fragte: Produzieren Wettbewerbsmärkte bei gegebenen Präferenzen und Ausstattungen effiziente Ergebnisse? Die Antwort lautet ja, sofern die Bedingungen der Wohlfahrtssätze gelten, und sie nimmt den Marktmechanismus als gegeben an. Dieses Kapitel kehrt die Frage um: Kann man bei einem gewünschten Ergebnis einen Mechanismus entwerfen, um es zu erreichen?

Mechanismusdesign wird oft als „umgekehrte Spieltheorie“ bezeichnet. Statt das Ergebnis eines Spiels vorherzusagen, entwerfen wir das Spiel, um ein gewünschtes Ergebnis zu erzielen. Marktdesign wendet diese Ideen auf reale Institutionen an: Auktionen, Matching-Märkte, Frequenzvergabe, Nierentausch.

Am Ende dieses Kapitels werden Sie in der Lage sein:
  1. Das Offenbarungsprinzip formulieren und erklären, warum es das Mechanismusdesign vereinfacht
  2. Anreizkompatibilität definieren und auf Mechanismusdesign-Probleme anwenden
  3. Die optimale Auktion (Myerson) und die Erlösäquivalenz ableiten
  4. Das Gibbard-Satterthwaite-Unmöglichkeitsresultat formulieren
  5. Den Gale-Shapley-Algorithmus auf Matching-Märkte anwenden
  6. Die Gestaltung realer Marktinstitutionen bewerten

Voraussetzungen: Kapitel 6 (Grundlagen der Spieltheorie, Nash-Gleichgewicht) und 11 (Wohlfahrtssätze, allgemeines Gleichgewicht).

12.1 Soziale Wahl und das Offenbarungsprinzip

Soziale Wahlfunktionen

Soziale Wahlfunktion (SWF). Eine Abbildung von den Typen der Agenten (private Information wie Bewertungen oder Präferenzen) auf Ergebnisse: $$f: \Theta_1 \times \cdots \times \Theta_n \to \mathcal{A}$$ wobei $\Theta_i$ der Typenraum von Agent $i$ und $\mathcal{A}$ die Menge möglicher Allokationen ist.

Die Herausforderung: Die Typen der Agenten sind privat. Wie bringen wir sie dazu, ihre Typen wahrheitsgemäß zu offenbaren?

Mechanismen

Mechanismus. Ein Paar $(\mathcal{M}, g)$ bestehend aus einem Nachrichten-(Strategie-)Raum $\mathcal{M}_i$ für jeden Agenten und einer Ergebnisfunktion $g: \mathcal{M}_1 \times \cdots \times \mathcal{M}_n \to \mathcal{A}$. Ein Mechanismus implementiert die SWF $f$, wenn im Gleichgewicht das Ergebnis des Mechanismus $f(\theta)$ für alle Typenprofile $\theta$ entspricht.

Abbildung 12.1. Zeitstrahl des Mechanismusdesigns.

Der Mechanismusdesigner wählt die Regeln (Nachrichtenraum und Ergebnisfunktion), um eine gewünschte soziale Wahlfunktion zu erreichen.

Das Offenbarungsprinzip

Das Offenbarungsprinzip. Jede durch irgendeinen Mechanismus in irgendeinem Gleichgewichtskonzept implementierbare soziale Wahlfunktion kann auch durch einen direkten Mechanismus implementiert werden, bei dem die Agenten ihre Typen wahrheitsgemäß berichten.
Direkter Mechanismus. Ein Mechanismus, bei dem der Nachrichtenraum jedes Agenten seinem Typenraum entspricht ($\mathcal{M}_i = \Theta_i$). Agenten werden einfach gebeten, ihre private Information direkt zu berichten. Das Offenbarungsprinzip garantiert, dass die Beschränkung auf direkte Mechanismen ohne Allgemeinheitsverlust ist.
Anreizkompatibilität (IC). Ein Mechanismus ist anreizkompatibel, wenn wahrheitsgemäße Offenbarung eine Gleichgewichtsstrategie für jeden Agenten ist: kein Agent kann durch Verfälschung seines Typs profitieren. IC gibt es in zwei Stärken: dominante Strategie (DSIC) und Bayes’sch (BIC).
Dominante-Strategie-Anreizkompatibilität (DSIC). Wahrheitsgemäße Offenbarung ist für jeden Agenten optimal, unabhängig davon, was andere Agenten berichten. DSIC-Mechanismen sind robust gegenüber Annahmen über das Verhalten anderer: $U_i(\theta_i, \theta_i) \geq U_i(\hat{\theta}_i, \theta_i)$ für alle $\hat{\theta}_i$ und alle $\theta_{-i}$.
Bayes’sche Anreizkompatibilität (BIC). Wahrheitsgemäße Offenbarung ist im Erwartungswert über die Typen der anderen optimal (unter der Annahme, dass andere ebenfalls wahrheitsgemäß berichten). Schwächer als DSIC, erlaubt aber eine reichere Menge implementierbarer Ergebnisse. Erfordert, dass Agenten korrekte Annahmen über die Typenverteilung haben.

Ein direkter Mechanismus bittet jeden Agenten, einfach seinen Typ (seine private Information) zu berichten. Er ist anreizkompatibel (IC), wenn wahrheitsgemäße Offenbarung eine Gleichgewichtsstrategie ist: kein Agent profitiert vom Lügen.

Dies ist die mächtigste Vereinfachung im Mechanismusdesign. Prinzipiell ist der Raum möglicher Mechanismen unendlich groß. Eine Auktion könnte beliebig viele Runden haben, beliebige Gebotsregeln, beliebige Zahlungsformeln. Ein Matching-Algorithmus könnte auf jede erdenkliche Weise funktionieren. Die Suche nach dem besten Mechanismus unter allen möglichen scheint aussichtslos.

Das Offenbarungsprinzip besagt: Sie müssen nicht suchen. Welches Ergebnis auch immer irgendein Mechanismus erzielen kann, ein direkter Mechanismus (fragen Sie einfach jeden, wahrheitsgemäß zu berichten) kann dasselbe Ergebnis erzielen. Das Mechanismusdesign-Problem reduziert sich also auf: Finde die beste Zuteilungsregel und Zahlungsregel als Funktionen der gemeldeten Typen, unter der Nebenbedingung, dass wahrheitsgemäße Offenbarung optimal ist. Dies verwandelt eine unmöglich breite Suche in ein wohldefiniertes Optimierungsproblem.

Dominante-Strategie-Anreizkompatibilität (DSIC): $$U_i(\theta_i, \theta_i) \geq U_i(\hat{\theta}_i, \theta_i) \quad \forall \hat{\theta}_i, \forall \theta_{-i}$$ (Gl. 12.1)
Bayes’sche Anreizkompatibilität (BIC): $$E_{\theta_{-i}}[U_i(\theta_i, \theta_i)] \geq E_{\theta_{-i}}[U_i(\hat{\theta}_i, \theta_i)] \quad \forall \hat{\theta}_i$$ (Gl. 12.2)
Intuition

Was das besagt: Wenn ein noch so ausgeklügeltes Spiel ein Ergebnis erreichen kann, dann erreicht auch ein schlichtes Spiel nach dem Muster „Sagen Sie einfach die Wahrheit“ dasselbe Ergebnis, und ausgeklügelte Mechanismen muss man deshalb gar nicht erst untersuchen. Untersucht werden immer nur wahrheitsgemäße direkte Mechanismen, in denen jeder Agent einfach seinen privaten Typ meldet. „Anreizkompatibel“ heißt dann genau eines: Ehrlichkeit ist der beste Zug des Agenten.

Warum das wichtig ist: Die beiden Stärken unterscheiden sich darin, wie robust diese Ehrlichkeit ist. Ehrlichkeit in dominanten Strategien (DSIC) gilt unabhängig davon, was alle anderen tun, und Sie müssen die Typen der anderen nie erraten. Bayes’sche Ehrlichkeit (BIC) gilt nur im Durchschnitt und setzt voraus, dass auch alle anderen die Wahrheit sagen. Sie ist schwächer, erlaubt es dem Mechanismusdesigner aber, mehr Ergebnisse zu implementieren.

Im vollständigen Modus formulieren Gl. 12.1 (DSIC) und Gl. 12.2 (BIC) die beiden Anreizkompatibilitätsbedingungen formal.

DSIC ist stärker, aber schwerer zu erreichen. BIC ist schwächer, erlaubt aber mehr Mechanismen.

Auktionstheorie und Mechanismusdesign waren zum Teil ein Produkt des Kalten Krieges: RAND, von Neumann und das Programm der strategischen Rationalität haben das Fach geprägt.

12.2 Das Gibbard-Satterthwaite-Theorem

Gibbard-Satterthwaite-Theorem. Wenn es mindestens 3 Alternativen gibt und die SCF surjektiv ist (jede Alternative ist erreichbar), dann ist die einzige DSIC-SCF eine Diktatur: die Präferenz eines Agenten bestimmt das Ergebnis unabhängig von den anderen.

Dies ist das Mechanismusdesign-Analogon zu Arrows Unmöglichkeitstheorem. Es besagt, dass in allgemeinen Sozialwahlsituationen kein nicht-diktatorischer Mechanismus wahrheitsgemäße Präferenzoffenbarung in dominanten Strategien erzielen kann.

Der Ausweg: den Präferenzbereich einschränken. Mit quasi-linearen Präferenzen ($U_i = v_i(a) + t_i$, wobei $t_i$ ein monetärer Transfer ist) fällt die Gibbard-Satterthwaite-Barriere. Der VCG-Mechanismus erreicht Effizienz und DSIC mit Transfers.

12.3 Der VCG-Mechanismus

VCG-Mechanismus. Der Vickrey-Clarke-Groves-Mechanismus alloziert effizient ($\max \sum_i v_i$) und belastet jeden Agenten mit einer Zahlung, die der Externalität entspricht, die er auf andere ausübt. Wahrheitsgemäße Offenbarung ist eine dominante Strategie, da die Zahlung jedes Agenten nur von den Meldungen der anderen abhängt.
Vickrey-Auktion (Zweitpreisauktion mit verdeckten Geboten). Der einfachste VCG-Mechanismus für einen einzelnen Gegenstand: Der Höchstbietende gewinnt und zahlt das zweithöchste Gebot. Wahrheitsgemäßes Bieten ist dominant, da die Zahlung unabhängig vom Gebot des Gewinners ist. Eingeführt von Vickrey (1961).
Clarke-Pivot-Regel. Die VCG-Zahlungsformel: Agent $i$ zahlt die Differenz zwischen der sozialen Wohlfahrt, die die anderen ohne $i$ erreichen würden, und der Wohlfahrt, die die anderen mit $i$ tatsächlich erreichen. Jeder Agent ist in dem Maße „pivotal“, wie er das Ergebnis für andere verändert.

Der Vickrey-Clarke-Groves (VCG)-Mechanismus erreicht eine effiziente Allokation mit wahrheitsgemäßer Offenbarung als dominante Strategie unter Verwendung monetärer Transfers.

Ist Wettbewerb ein Endzustand, den man herstellen kann, oder ein Entdeckungsverfahren, das sich dem Entwurf entzieht? Hurwicz’ Programm der Anreizkompatibilität liegt genau auf dieser Bruchlinie.

Die effiziente Allokation maximiert den Gesamtwert: $a^*(\theta) = \arg\max_a \sum_i v_i(a, \theta_i)$.

VCG-Zahlung für Agent $i$: $$t_i(\theta) = \sum_{j \neq i} v_j(a^*(\theta_{-i}), \theta_j) - \sum_{j \neq i} v_j(a^*(\theta), \theta_j)$$ (Gl. 12.3)

Agent $i$ zahlt die Externalität, die er auf andere ausübt: die Differenz zwischen der Wohlfahrt der anderen mit und ohne $i$.

Warum ist wahrheitsgemäße Offenbarung dominant? Bei wahrheitsgemäßer Offenbarung ist die Auszahlung von Agent $i$:

$$v_i(a^*(\theta)) + t_i = v_i(a^*(\theta)) + \sum_{j \neq i} v_j(a^*(\theta_{-i})) - \sum_{j \neq i} v_j(a^*(\theta))$$

Dies vereinfacht sich zu $\sum_j v_j(a^*(\theta)) - \sum_{j \neq i} v_j(a^*(\theta_{-i}))$. Der zweite Term hängt nicht von $i$s Meldung ab. Also maximiert $i$ seine Auszahlung, indem er seine Meldung so wählt, dass $\sum_j v_j(a^*(\theta))$ maximiert wird, was bei wahrheitsgemäßer Offenbarung geschieht, da $a^*$ bereits den Gesamtwert maximiert.

Intuition

Was das besagt: Sie zahlen den Schaden, den Ihre Anwesenheit allen anderen zufügt: die Differenz zwischen dem, was die anderen ohne Sie hätten erreichen können, und dem, was sie mit Ihnen im Raum erreichen. Diese Rechnung hängt allein von den Werten der anderen ab, nie von Ihrer eigenen Meldung, und Sie können sie deshalb nicht durch eine Falschmeldung verkleinern.

Warum das wichtig ist: Weil Ihre Zahlung von den anderen festgelegt wird, bleibt Ihnen als einziger Hebel, dem Mechanismus zu dem Ergebnis zu verhelfen, das den Gesamtwert maximiert, und dieses Ergebnis ist genau dann das beste für Sie, wenn Sie Ihren wahren Wert melden. Lügen kann die Allokation nur von der effizienten wegführen, und das kann Sie nie besserstellen. Deshalb ist wahrheitsgemäße Offenbarung eine dominante Strategie: Sie funktioniert unabhängig davon, was alle anderen tun. Beim einzelnen Gegenstand ist diese Regel genau die Zweitpreisauktion (Vickrey), bei der der Gewinner das Gebot des Zweitplatzierten zahlt.

Im vollständigen Modus zeigt die Rechnung, dass der zweite Term der Auszahlung unabhängig von der Meldung des Agenten $i$ ist.

Interaktiv: VCG-Zahlungsrechner

Geben Sie Agentenwerte für einen einzelnen unteilbaren Gegenstand ein. Der Rechner berechnet VCG-Zahlungen (äquivalent zu einer Zweitpreisauktion für einen einzelnen Gegenstand).

Klicken Sie auf „Berechnen“, um die Ergebnisse zu sehen.

Abbildung 12.2. Agentenwerte und VCG-Zahlungen. Jeder Agent zahlt die Externalität, die er auf andere ausübt. Der Gewinner zahlt den zweithöchsten Wert (bei einem einzelnen Gegenstand reduziert sich VCG auf die Vickrey-Auktion).

Beispiel 12.1 — VCG für ein öffentliches Gut

Drei Bürger bewerten eine Brücke mit $v_1 = 30$, $v_2 = 25$, $v_3 = 15$. Die Kosten betragen $C = 60$.

Bauen, wenn $\sum v_i > C$: $70 > 60$ → ja.

Clarke-Steuerzahlungen:

Gesamteinnahmen: $20 + 15 + 5 = 40 < 60$. Es gibt ein Budgetdefizit von 20. VCG erreicht im Allgemeinen keinen Budgetausgleich. Jeder Agent zahlt seinen „pivotalen“ Beitrag.

12.4 Optimale Auktionen und Erlösäquivalenz

Auktionsformate

FormatRegelnGewinner zahlt
Englisch (aufsteigend)Bieter erhöhen Gebote; letzter Bieter gewinntZweithöchster Wert (ca.)
Holländisch (absteigend)Preis sinkt, bis jemand zugreiftSein Gebot
Erstpreisauktion mit verdeckten GebotenHöchstes Gebot gewinntSein Gebot
Zweitpreisauktion mit verdeckten Geboten (Vickrey)Höchstes Gebot gewinntZweithöchstes Gebot

Die Vickrey-Auktion (Zweitpreisauktion mit verdeckten Geboten) ist DSIC: Die dominante Strategie jedes Bieters ist, seinen wahren Wert $v_i$ zu bieten. Über $v_i$ zu bieten, riskiert einen Gewinn zu einem Preis über dem Wert; unter $v_i$ zu bieten, riskiert einen Verlust, wenn das zweithöchste Gebot unter $v_i$ liegt.

Erlösäquivalenz

Erlösäquivalenzsatz (Myerson, 1981). Wenn Bieter risikoneutral sind mit unabhängigen privaten Werten aus derselben Verteilung, liefert jeder Auktionsmechanismus, der (a) den Gegenstand dem Bieter mit dem höchsten Wert zuteilt und (b) dem Bieter mit dem niedrigstmöglichen Wert eine erwartete Auszahlung von null gibt, dem Verkäufer denselben erwarteten Erlös.

Die Implikation: Unter diesen Bedingungen sind die Unterschiede zwischen Auktionsformaten (offen vs. verdeckt, aufsteigend vs. absteigend, Erstpreis vs. Zweitpreis) für den erwarteten Erlös irrelevant.

Die Erlösäquivalenz bricht in mehreren häufigen Fällen zusammen:

Interaktiv: Auktionssimulator

Legen Sie die Anzahl der Bieter und ihre Wertverteilung fest. Führen Sie einzelne Auktionen durch, um individuelle Ergebnisse zu sehen, oder führen Sie 100 Runden durch, um die Erlösäquivalenz zu beobachten (Durchschnittserlöse konvergieren über Formate). Passen Sie den Risikoaversions-Schieberegler an, um die Äquivalenz zu brechen.

Risikoneutral (0) Moderat (0,4) Hoch (0,8)
Klicken Sie auf eine Schaltfläche, um den Auktionssimulator zu starten.

Abbildung 12.3. Auktionsergebnisse. In einzelnen Durchläufen unterscheiden sich die Erlöse zwischen den Formaten aufgrund von Zufälligkeit. Über 100 Durchläufe konvergieren die durchschnittlichen Erlöse und demonstrieren die Erlösäquivalenz. Erhöhen Sie die Risikoaversion ($\rho > 0$), um die Äquivalenz zu brechen: Der Erstpreiserlös steigt über den Zweitpreiserlös.

Myersons optimale Auktion

Virtueller Wert. Der virtuelle Wert eines Bieters $\psi(\theta_i) = \theta_i - (1 - F(\theta_i))/f(\theta_i)$ korrigiert den wahren Wert nach unten, um die Informationsrente zu berücksichtigen, die der Verkäufer dem Bieter lassen muss, um Anreize für wahrheitsgemäßes Bieten zu setzen. Die optimale Auktion maximiert den erwarteten virtuellen Überschuss statt des erwarteten wahren Überschusses.
Optimaler Reservepreis. Das Mindestgebot, unter dem der Verkäufer nicht verkauft, selbst wenn der Gegenstand für den Verkäufer keinen Wert hat. Gesetzt dort, wo der virtuelle Wert null ist: $\psi(r^*) = 0$. Der optimale Reservepreis wägt die Verkaufswahrscheinlichkeit gegen den Erlös aus hochbewertenden Bietern ab.

Wenn der Verkäufer den Erlös maximieren will (nicht die Effizienz), zeigte Myerson, dass der optimale Mechanismus den virtuellen Wert verwendet:

$$\psi(\theta_i) = \theta_i - \frac{1 - F(\theta_i)}{f(\theta_i)}$$ (Gl. 12.4)

wobei $F$ die Verteilungsfunktion und $f$ die Dichtefunktion der Wertverteilung des Bieters ist.

$$\text{Zuteilung an den höchsten virtuellen Wert, wenn } \psi(\theta_i) > 0$$ (Gl. 12.5)

Die optimale Auktion teilt dem Bieter mit dem höchsten virtuellen Wert zu, vorausgesetzt dieser ist positiv. Wenn alle virtuellen Werte negativ sind, behält der Verkäufer den Gegenstand. Dies impliziert einen Reservepreis: der Verkäufer setzt ein Mindestgebot gleich $\psi^{-1}(0)$.

$$r^*: \quad \psi(r^*) = r^* - \frac{1 - F(r^*)}{f(r^*)} = 0$$ (Gl. 12.6)
Intuition

Was das besagt: Ein erlösmaximierender Verkäufer nimmt ein Gebot nicht für bare Münze. Er zieht von jedem Gebot im Kopf die „Informationsrente“ ab, die er den Bietern lassen muss, damit sie ehrlich bleiben, und die so verminderte Zahl ist der virtuelle Wert des Bieters. Der Verkäufer teilt den Gegenstand dem höchsten virtuellen Wert zu und verkauft überhaupt nur dann, wenn selbst dieser verminderte Wert über null liegt.

Warum das wichtig ist: Genau dieser Nulldurchgang ist der optimale Reservepreis. Darunter ist Behalten besser als Verkaufen, denn der zusätzliche Erlös, den ein hoher Reservepreis den hochbewertenden Bietern abpresst, wiegt schwerer als die entgangenen Verkäufe an niedrigbewertende Bieter. Deshalb sollte selbst ein Verkäufer, für den der Gegenstand wertlos ist, den Verkauf manchmal verweigern. Der Reservepreis ist eine strategische Selbstbindung, keine Kostenuntergrenze. Dieselbe Logik kehrt in der optimalen Einkommensbesteuerung wieder: Der Planer zieht bei jedem Steuerzahler die Anreizkosten der Besteuerung ab und verteilt nur dort um, wo der so verminderte Gewinn positiv bleibt.

Im vollständigen Modus definieren Gl. 12.4–12.6 den virtuellen Wert $\psi(\theta)$ und die Bedingung für den Reservepreis $\psi(r^*) = 0$.
$$\text{Alle Mechanismen mit derselben Zuteilungsregel liefern denselben erwarteten Erlös}$$ (Gl. 12.7)
Beispiel 12.2 — Optimaler Reservepreis

Werte gleichverteilt auf $[0, 1]$: $F(\theta) = \theta$, $f(\theta) = 1$.

$\psi(\theta) = \theta - (1-\theta)/1 = 2\theta - 1$

$\psi(\theta) = 0 \implies \theta = 1/2$. Optimaler Reservepreis = $1/2$.

Eine Zweitpreisauktion mit Reserve $1/2$ ist optimal: Der Gegenstand wird nur verkauft, wenn mindestens ein Bieter ihn über $1/2$ bewertet.

Interaktiv: Myersons optimale Auktion

Für Werte aus der Gleichverteilung$[0, V_{\max}]$ ist der virtuelle Wert $\psi(\theta) = 2\theta - V_{\max}$. Ziehen Sie den Reservepreis-Schieberegler. Die Erlöskurve zeigt den erwarteten Erlös als Funktion des Reservepreises. Der optimale Reservepreis (der den erwarteten Erlös maximiert) ist hervorgehoben.

Kein Reservepreis (0) Optimum ($r^*$) Maximum (1)
Laden...

Abbildung 12.4a. Virtuelle Wertfunktion $\psi(\theta) = 2\theta - 1$ (für $U[0,1]$). Der Reservepreis wird dort gesetzt, wo $\psi(r) = 0$. Bieter mit $\theta < r$ werden ausgeschlossen (rot schattiert).

Abbildung 12.4b. Erwarteter Erlös als Funktion des Reservepreises. Der grüne Punkt markiert den optimalen Reservepreis, der den erwarteten Erlös maximiert. Ihr gewählter Reservepreis wird als blauer Punkt angezeigt.

Beispiel 12.4 — Anreizkompatibilitätsprüfung

Eine Regierung vergibt eine Lizenz an eines von zwei Unternehmen. Unternehmen $i$ hat einen privaten Wert $\theta_i \in \{L, H\} = \{10, 50\}$, jeweils gleich wahrscheinlich.

Zuteilung an das Unternehmen, das den höheren Wert meldet; bei Gleichstand Zuteilung an Unternehmen 1. Der Gewinner zahlt 30.

IC-Prüfung für ein Unternehmen mit hohem Wert ($\theta = 50$):

Wahrheitsgemäße Offenbarung ist besser. IC gilt für Typ $H$.

IC-Prüfung für ein Unternehmen mit niedrigem Wert ($\theta = 10$):

Wahrheitsgemäße Offenbarung ist besser. IC gilt für Typ $L$. Der Mechanismus ist anreizkompatibel.

Beispiel 12.5 — Überprüfung der Erlösäquivalenz

Zwei Bieter mit Werten, die unabhängig aus $U[0, 100]$ gezogen werden.

Zweitpreisauktion: Erwarteter Erlös = $E[\text{zweithöchster Wert}] = 100/3 \approx 33.33$.

Erstpreisauktion: Optimales Gebot bei 2 Bietern: $b(\theta) = \theta/2$. Erwarteter Erlös = $E[\max(b_1, b_2)] = E[\max(\theta_1/2, \theta_2/2)] = E[\max(\theta_1, \theta_2)]/2 = (200/3)/2 = 100/3 \approx 33.33$.

Beide Formate liefern einen erwarteten Erlös von $100/3$, was die Erlösäquivalenz bestätigt. Die Erstpreisauktion erzeugt weniger variable Erlöse (jeder Gewinner zahlt genau die Hälfte seines Wertes), während die Zweitpreisauktion eine höhere Varianz aufweist (die Zahlung hängt vom zweithöchsten Wert ab, der stark variieren kann).

Myerson-Satterthwaite-Unmöglichkeit

Myerson-Satterthwaite-Theorem (1983). Im bilateralen Handel mit privater Information (ein Käufer und ein Verkäufer, die jeweils nur ihre eigene Bewertung kennen) gibt es keinen Mechanismus, der gleichzeitig alle vier Eigenschaften erfüllt:
  1. Individuelle Rationalität (IR): Beide Parteien nehmen freiwillig teil
  2. Anreizkompatibilität (IC): Beide Parteien berichten wahrheitsgemäß
  3. Budgetausgleich (BB): Keine externen Subventionen erforderlich
  4. Effizienz: Handel findet genau dann statt, wenn $v_B > c_S$

Der Verkäufer möchte seine Kosten zu hoch angeben (um einen höheren Preis zu erzielen). Der Käufer möchte seinen Wert zu niedrig angeben (um weniger zu zahlen). Anreizkompatibilität erfordert, beiden Parteien „Informationsrenten“ zu überlassen. Diese Renten sind kostspielig, und bei Budgetausgleich reicht der Überschuss nicht aus, um beide Renten zu zahlen und sicherzustellen, dass alle effizienten Tausche stattfinden.

Reale Verhandlungen unter privater Information beinhalten stets Ineffizienz: Gehaltsverhandlungen, Gebrauchtwagenkauf, Unternehmensübernahmen. Institutionen wie Festpreise, Reputationssysteme und standardisierte Verträge mildern das Problem, können es aber nicht vollständig beseitigen.

12.5 Matching-Märkte

Marktdesign. Der Zweig der Volkswirtschaftslehre, der reale Institutionen und Allokationsmechanismen gestaltet und Mechanismusdesign sowie Matching-Theorie auf praktische Probleme anwendet. Wichtige Anwendungen umfassen die Facharzt-Zuordnung (NRMP), Schulwahl, Nierentausch und Frequenzauktionen. Roth beschrieb dies als den „Ökonomen als Ingenieur“.

Manche Güter können nicht durch Preise zugeteilt werden: wir verkaufen Schulzulassungen, Organtransplantationen und Facharztpositionen nicht (oder sollten es nicht tun). Matching-Märkte verwenden stattdessen Algorithmen.

Gale-Shapley-Algorithmus mit Deferred Acceptance

Stabile Zuordnung. Eine Zuordnung, bei der kein nicht zugeordnetes Paar sich gegenseitig dem aktuellen Partner vorzieht. Stabilität stellt sicher, dass es keine blockierenden Paare gibt: kein Paar hat den Anreiz und die Möglichkeit, von der zugewiesenen Zuordnung abzuweichen.
Deferred-Acceptance-Algorithmus (Verfahren der aufgeschobenen Annahme). Der Gale-Shapley-Algorithmus zur Findung einer stabilen Zuordnung: Vorschlagende machen Angebote in der Reihenfolge ihrer Präferenz, Antwortende halten vorläufig ihr bestes Angebot und lehnen den Rest ab, abgelehnte Vorschlagende gehen zu ihrer nächsten Wahl. Der Algorithmus terminiert in höchstens $n^2$ Runden.
Vorschlagsoptimale stabile Zuordnung. Die stabile Zuordnung, die entsteht, wenn eine Seite im Deferred-Acceptance-Algorithmus vorschlägt. Sie ist die beste stabile Zuordnung für Vorschlagende und die schlechteste für Antwortende. Diese Asymmetrie bedeutet, dass die Wahl, wer vorschlägt, erhebliche Verteilungskonsequenzen hat.
Strategiesicherheit. Ein Mechanismus ist strategiesicher, wenn wahrheitsgemäße Offenbarung eine dominante Strategie für jeden Teilnehmer ist. Der Deferred-Acceptance-Algorithmus ist strategiesicher für die vorschlagende Seite, aber nicht für die antwortende Seite.
Aufbau: Zwei Seiten eines Marktes (z.B. Studierende und Schulen). Jeder Agent ordnet die andere Seite.

Algorithmus (vorschlagsoptimale Version):
  1. Jeder Vorschlagende macht dem am höchsten bewerteten Partner einen Vorschlag
  2. Jeder Antwortende akzeptiert vorläufig den besten Vorschlag und lehnt den Rest ab
  3. Abgelehnte Vorschlagende machen ihrem nächsten Wunsch einen Vorschlag
  4. Wiederhole, bis keine Ablehnungen mehr auftreten
$$\text{GS terminiert in } \leq n^2 \text{ Runden und erzeugt die vorschlagsoptimale stabile Zuordnung}$$ (Gl. 12.8)
Intuition

Was das besagt: Beobachten Sie, wie der Deferred-Acceptance-Algorithmus abläuft: Vorschlagende gehen ihre Präferenzlisten stets abwärts (jede Ablehnung schickt sie zu einer weniger bevorzugten Wahl), während Antwortende stets aufwärts tauschen (sie ersetzen einen vorläufigen Partner nur durch einen besseren). Nach einer Ablehnung wird niemand erneut angesprochen, der Ablauf kann also nicht in eine Endlosschleife geraten und terminiert schnell (in höchstens $n^2$ Runden).

Warum das wichtig ist: Wenn der Algorithmus terminiert, ist die Zuordnung stabil: Es gibt kein Paar, das sich gegenseitig den zugewiesenen Partnern vorzieht, und niemand hat deshalb einen Anreiz, „durchzubrennen“. Stabilität ist genau das, was eine Zuordnung selbstdurchsetzend macht: Sie bleibt bestehen, ohne dass Preise oder Zahlungen nötig wären. Deshalb läuft derselbe Algorithmus hinter der Facharzt-Zuordnung, der Schulwahl und dem Nierentausch, denn er erzeugt ein stabiles Ergebnis in Märkten, in denen Geld die Zuteilung nicht leisten kann.

Im vollständigen Modus formuliert Gl. 12.8 die Schranke für die Terminierung und die Garantie einer stabilen Zuordnung.

Theorem (Gale & Shapley, 1962). Der Algorithmus terminiert in höchstens $n^2$ Runden und erzeugt eine stabile Zuordnung: kein nicht zugeordnetes Paar zieht sich gegenseitig dem aktuellen Partner vor.

Der Deferred-Acceptance-Algorithmus hat vier bemerkenswerte Eigenschaften:

Interaktiv: Gale-Shapley Schritt für Schritt

Geben Sie Präferenzlisten für Studierende und Schulen ein. Der Algorithmus animiert jede Runde: Vorschläge, vorläufige Zusagen und Ablehnungen. Geben Sie Präferenzen als kommagetrennte Namen ein (z.B. „W,X,Y,Z“).

Beispiel 12.3 — Gale-Shapley mit vier Studierenden

Vier Studierende (A, B, C, D) und vier Schulen (W, X, Y, Z). Studierende machen Vorschläge.

Studierende/rPräferenzenSchulePräferenzen
AW > X > Y > ZWB > A > D > C
BX > W > Y > ZXA > B > C > D
CW > Y > X > ZYC > D > A > B
DY > W > X > ZZD > C > B > A

Die endgültige Zuordnung ist A-W, B-X, C-Y, D-Z, die stabil ist: Kein Paar möchte abweichen. Nutzen Sie die interaktive Grafik oben zur schrittweisen Überprüfung.

Interaktiv: Vorschlagsvorteil

Führen Sie Gale-Shapley mit Studierenden als Vorschlagende vs. Schulen als Vorschlagende aus. Vergleichen Sie die beiden stabilen Zuordnungen. Die vorschlagende Seite erhält stets ihre beste stabile Zuordnung; die antwortende Seite ihre schlechteste.

Marktdesign in der Praxis

Alvin Roth (Nobelpreis 2012, geteilt mit Lloyd Shapley) beschreibt dies als den Ansatz des „Ökonomen als Ingenieur“: die Nutzung ökonomischer Theorie nicht nur zur Erklärung der Welt, sondern zur Gestaltung realer Institutionen, die das Leben der Menschen verbessern.

Märkte sind keine natürlichen Objekte, die spontan entstehen. Sie sind gestaltete Institutionen: Regeln, Algorithmen und Durchsetzungsmechanismen, die bestimmen, wer was bekommt, zu welchem Preis und durch welchen Prozess. Die Designentscheidungen bestimmen die Ergebnisse.

Leitbeispiel: Mayas Unternehmen

Die Stadt beschließt, das exklusive Recht zum Betrieb eines Limonadenstands an der besten Innenstadtecke zu versteigern. Drei potenzielle Anbieter: Maya ($v_M = 50$/Tag), Nate ($v_N = 35$/Tag), Olivia ($v_O = 20$/Tag). Werte gezogen aus $U[0, 60]$.

Zweitpreisauktion (Vickrey): Die dominante Strategie ist wahrheitsgemäßes Bieten. Maya bietet 50, Nate bietet 35, Olivia bietet 20. Maya gewinnt und zahlt 35.

Optimale Auktion (Myerson): Virtuelle Werte mit $F(\theta) = \theta/60$, $f(\theta) = 1/60$:

$\psi(\theta) = \theta - (60 - \theta) = 2\theta - 60$

Reservepreis: $\psi(\theta) = 0 \implies \theta = 30$.

Mayas virtueller Wert: $2(50) - 60 = 40$. Nates: $10$. Olivias: $-20$ (von der optimalen Auktion ausgeschlossen).

In einer Zweitpreisauktion mit Reserve 30: Maya gewinnt und zahlt $\max(35, 30) = 35$.

Historische Perspektive

Roth als „Ökonom als Ingenieur“. Alvin Roth (Nobelpreis 2012) verwandelte das Mechanismusdesign von reiner Theorie in eine praktische Disziplin, die reale Märkte umgestaltet. Seine Arbeit zeigt, dass Märkte gestaltete Institutionen sind, keine Naturphänomene.

Das National Residency Matching Program (NRMP): Roth diagnostizierte, warum das ursprüngliche Facharzt-Matching versagte (Instabilität, strategische Manipulation) und gestaltete es mit Deferred Acceptance neu. Das neue System ordnet jährlich ca. 40.000 Facharztpositionen zu.

Nierentausch: Roth, Sönmez und Ünver entwickelten Tauschprotokolle, die es inkompatiblen Spender-Patienten-Paaren ermöglichen, Spender über Transplantationsketten zu tauschen und so Tausende von Leben zu retten. Dies war reines Marktdesign: die Schaffung eines Marktes, wo keiner existierte, ohne Preise zu verwenden.

Schulwahl: Roth und Kollegen ersetzten Bostons manipulierbaren Schulzuweisungsmechanismus durch ein strategiesicheres System. Im alten System wurden Eltern bestraft, die ihre wahren Präferenzen angaben; im neuen System ist Ehrlichkeit stets optimal.

Frequenzauktionen: Milgrom und Wilson (Nobelpreis 2020) entwarfen kombinatorische Auktionen für die FCC, die Milliarden von Dollar einbrachten und gleichzeitig Frequenzlizenzen effizient zuteilten. Die Anreizauktion von 2017 allein brachte \$19,8 Milliarden ein.

Der rote Faden: Die ökonomische Theorie liefert den Bauplan, aber die Umsetzung erfordert das Verständnis des spezifischen institutionellen Kontexts, der „Details“, von denen die reine Theorie abstrahiert.

Wo das Mechanismusdesign in der weiteren Ideengeschichte steht und welche Denklinie von Neumanns Spieltheorie mit dem Entwurf realer Märkte verbindet, zeigt der Ideengraph (Zeitleiste zur Geschichte des ökonomischen Denkens).

Die Denklinie hinter diesem Instrumentarium, also Hurwicz’ Programm der Anreizkompatibilität, Maskin und Myerson zu Implementierung und optimalen Auktionen, Roth zum Matching, Milgrom und Wilson zum Auktionsdesign (die Nobelpreise 2007 und 2020), ist das Thema von Ideengeschichte, Kapitel 11 (Informationsökonomik und die spieltheoretische Revolution).

Hurwicz verstand das Mechanismusdesign als Antwort auf ein Problem, das zuerst die Österreicher gestellt hatten: Wie bringt man dezentrale Agenten, von denen jeder private Information besitzt, dazu, nach einem Wissen zu handeln, über das kein zentraler Planer verfügt? Zu dieser älteren Debatte, zu Hayeks „Wissensproblem“ und zu dem Gedanken, dass Wettbewerb ein Entdeckungsverfahren ist und kein entwerfbarer Endzustand, siehe die österreichische Tradition (Ideengeschichte, Kapitel 6).

Die Wende zum Ingenieurwesen hatte einen Vorlauf von hundertzwanzig Jahren. 1874 versuchte der französische Ingenieur Léon Walras, sämtliche Preise einer Volkswirtschaft auf einmal als ein System simultaner Gleichungen aufzuschreiben, und der Wettbewerbsmaßstab, der dabei herauskam, beschrieb Märkte, die niemand gebaut hatte. Auktionsdesign, Deferred Acceptance und die Nierenketten weiter oben sind der Punkt, an dem aus der Beschreibung ein Bauplan wird. Marktstruktur: wie die Ökonomik vom Beschreiben zum Bauen von Märkten überging verfolgt diesen Strang und fragt, ob die Konstruktion gelungen ist.

Zusammenfassung

Wichtige Gleichungen

BezeichnungGleichungBeschreibung
Gl. 12.1$U_i(\theta_i, \theta_i) \geq U_i(\hat{\theta}_i, \theta_i)$ für alle $\hat{\theta}_i, \theta_{-i}$DSIC
Gl. 12.2$E[U_i(\theta_i, \theta_i)] \geq E[U_i(\hat{\theta}_i, \theta_i)]$BIC
Gl. 12.3$t_i = \sum_{j \neq i} v_j(a^*(\theta_{-i})) - \sum_{j \neq i} v_j(a^*(\theta))$VCG-Zahlung
Gl. 12.4$\psi(\theta) = \theta - (1-F(\theta))/f(\theta)$Myersons virtueller Wert

Übungen

Übung

  1. Ein einzelner unteilbarer Gegenstand wird an zwei Bieter mit Werten $v_1 = 10$, $v_2 = 7$ versteigert. Berechnen Sie Gewinner und Zahlung bei: (a) Erstpreisauktion mit verdeckten Geboten (Annahme: jeder Bieter reduziert sein Gebot um die Hälfte), (b) Zweitpreisauktion mit verdeckten Geboten, (c) englischer Auktion.
  2. Drei Wähler ordnen drei Alternativen {A, B, C}. Konstruieren Sie Präferenzprofile, bei denen: (a) Mehrheitsregel einen Zyklus erzeugt (Condorcet-Paradoxon), (b) eine diktatorische Regel den Zyklus vermeidet.
  3. Führen Sie Gale-Shapley (Studierende schlagen vor) aus für: Studierende {1,2,3}, Schulen {X,Y,Z}. Präferenzen: 1: X>Y>Z, 2: Y>X>Z, 3: X>Y>Z. Schulen: X: 1>2>3, Y: 2>3>1, Z: 3>1>2.

Anwendung

  1. Eine Regierung möchte CO2-Emissionsrechte effizient zuteilen. Vergleichen Sie: (a) einen VCG-Mechanismus (Unternehmen melden Vermeidungskosten), (b) eine Standardauktion, (c) einen Cap-and-Trade-Markt. Unter welchen Bedingungen erzeugen sie dieselbe Allokation?
  2. Erklären Sie, warum eBay eine Zweitpreisauktion (Proxy-Bieten) statt einer Erstpreisauktion verwendet. Wie hängt das Vickrey-Ergebnis mit eBays Design zusammen?
  3. Der Bostoner Schulwahlmechanismus (vor der Reform) bestrafte Eltern, die beliebte Schulen angaben, wenn sie keine hohe Priorität hatten. Erklären Sie, warum dies nicht strategiesicher ist und wie Deferred Acceptance dies behebt.
  4. Das Myerson-Satterthwaite-Theorem besagt, dass effizienter bilateraler Handel bei privater Information unmöglich ist. Dennoch ermöglichen eBay, Craigslist und Gebrauchtwagenmärkte täglich Millionen von Transaktionen. Wie mildern diese Institutionen das Unmöglichkeitsresultat?

Herausforderung

  1. Leiten Sie den optimalen Reservepreis für eine Zweitpreisauktion mit $n$ Bietern ab, deren Werte i.i.d. aus $U[0, 1]$ gezogen werden. Zeigen Sie, dass der Reservepreis unabhängig von $n$ bei $1/2$ liegt. Was ist der erwartete Erlös als Funktion von $n$?
  2. Beweisen Sie, dass der Gale-Shapley-Algorithmus eine stabile Zuordnung erzeugt. (Hinweis: Nehmen Sie an, es existiert ein blockierendes Paar. Zeigen Sie, dass dies zu einem Widerspruch mit der Ablehnungslogik des Algorithmus führt.)
  3. Ein Verkäufer hat zwei identische Gegenstände und drei Bieter mit Werten $v_1 > v_2 > v_3$. Entwerfen Sie einen VCG-Mechanismus für diese Mehrobjekt-Auktion. Was zahlt jeder Gewinner?
  4. Betrachten Sie einen Matching-Markt, bei dem eine Seite strikte Präferenzen hat, die andere Seite aber bei einigen Zuordnungen indifferent ist (Gleichstände). Erzeugt Gale-Shapley immer noch eine stabile Zuordnung? Wenn Gleichstände zufällig aufgelöst werden, ist das Ergebnis eindeutig?

Quellen

Grundlegende Literatur: Myerson (1981); Vickrey (1961); Clarke (1971); Groves (1973); Gale & Shapley (1962); Roth (2002); Milgrom (2004).

Sie haben Teil IV abgeschlossen — Methoden & Fortgeschrittene Mikroökonomie

Sie können jetzt bewerten:

  • Kausalaussagen in der Ökonomik (IV, DiD, RD, RCTs)
  • Ob Milliardäre effizient oder ein Marktversagen sind
  • Die Wohlfahrtstheoreme: wann Märkte funktionieren, formal

Große Fragen zum Erkunden:

In Teil V: fortgeschrittene Makroökonomie. Die Modelle werden ernst, und die politischen Debatten ebenso.