Kapitel 11: Mechanismusdesign und Marktdesign

Kapitel 10 fragte: Produzieren Wettbewerbsmärkte bei gegebenen Präferenzen und Ausstattungen effiziente Ergebnisse? Die Antwort — ja, unter den Bedingungen der Wohlfahrtssätze — 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.

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

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

11.1 Soziale Wahl und das Offenbarungsprinzip

Soziale Wahlfunktionen

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

Mechanismen

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

Das Offenbarungsprinzip

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

Dies ist die mächtigste Vereinfachung im Mechanismusdesign — wohl die mächtigste Vereinfachung in der gesamten ökonomischen Theorie. 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 Berichterstattung optimal ist. Dies verwandelt eine unmöglich breite Suche in ein wohldefiniertes Optimierungsproblem.

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

11.2 Das Gibbard-Satterthwaite-Theorem

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: Beschränke den Bereich. 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.

11.3 Der VCG-Mechanismus

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

Effiziente Allokation: $a^*(\theta) = \arg\max_a \sum_i v_i(a, \theta_i)$ — maximiere den Gesamtwert.

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 Berichterstattung dominant? Bei wahrheitsgemäßer Berichterstattung 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 Bericht ab. Also maximiert $i$ seine Auszahlung, indem er seinen Bericht so wählt, dass $\sum_j v_j(a^*(\theta))$ maximiert wird — was bei wahrheitsgemäßer Berichterstattung geschieht, da $a^*$ bereits den Gesamtwert maximiert.

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).

Wert von Agent 1:

Wert von Agent 2:

Wert von Agent 3:

Click "Compute" to see results.

Abbildung 11.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 11.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$: \$10 > 60$ → ja.

Clarke-Steuerzahlungen:

$t_1 = C - (v_2 + v_3) = 60 - 40 = 20$ (Agent 1 muss die Lücke decken)
$t_2 = C - (v_1 + v_3) = 60 - 45 = 15$
$t_3 = C - (v_1 + v_2) = 60 - 55 = 5$

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

11.4 Optimale Auktionen und Erlösäquivalenz

Auktionsformate

Format	Regeln	Gewinner zahlt
Englisch (aufsteigend)	Bieter erhöhen Gebote; letzter Bieter gewinnt	Zweithöchster Wert (ca.)
Holländisch (absteigend)	Preis sinkt, bis jemand zugreift	Sein Gebot
Erstpreisauktion mit verdeckten Geboten	Höchstes Gebot gewinnt	Sein Gebot
Zweitpreisauktion mit verdeckten Geboten (Vickrey)	Höchstes Gebot gewinnt	Zweithö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

Dies ist ein erstaunliches Ergebnis. Es besagt, dass die scheinbar großen Unterschiede zwischen Auktionsformaten — offen vs. verdeckt, aufsteigend vs. absteigend, Erstpreis vs. Zweitpreis — für den erwarteten Erlös unter diesen Bedingungen irrelevant sind.

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.

Anzahl der Bieter:

Maximalwert (Uniform[0, max]):

Risikoaversion (CRRA $\rho$): 0,00 (risikoneutral — Erlösäquivalenz gilt)

Risikoneutral (0) Moderat (0,4) Hoch (0,8)

Click a button to run the auction simulator.

Abbildung 11.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 — was die Erlösäquivalenz demonstriert. Erhöhen Sie die Risikoaversion ($\rho > 0$), um die Äquivalenz zu brechen: Der Erstpreiserlös steigt über den Zweitpreiserlös.

Myersons optimale Auktion

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

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

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)$.

Beispiel 11.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.

Anzahl der Bieter ($n$): 2

Reservepreis ($r$): 0,50

Kein Reservepreis (0) Optimal ($r^*$) Maximum (1)

Abbildung 11.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 11.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 11.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.

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

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

Wahrheitsgemäß berichten ($H$): Mit Wahrscheinlichkeit 3/4 gewinnen. Auszahlung = \$1/4 \times (50 - 30) = 15$.
$L$ berichten: Nur gewinnen, wenn der Rivale auch $L$ berichtet und Sie Firma 1 sind. Erwartete Auszahlung $\leq 1/4 \times 20 = 5$.

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

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

Wahrheitsgemäß berichten ($L$): Wahrscheinlich verlieren. Erwartete Auszahlung $\approx 0$.
$H$ berichten: Mit Wahrscheinlichkeit 3/4 gewinnen, aber 30 > 10 zahlen. Auszahlung = \$1/4 \times (10 - 30) = -15$.

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

Beispiel 11.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

Intuition: Der Verkäufer möchte seine Kosten übertreiben (um einen höheren Preis zu erzielen). Der Käufer möchte seinen Wert untertreiben (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 — Gehaltsverhandlungen, Gebrauchtwagenkauf, Unternehmensübernahmen — beinhalten stets Ineffizienz. Institutionen wie Festpreise, Reputationssysteme und standardisierte Verträge mildern das Problem, können es aber nicht vollständig beseitigen.

11.5 Matching-Märkte

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

Gale-Shapley-Algorithmus mit aufgeschobener Akzeptanz

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.

Beispiel 11.3 — Gale-Shapley mit vier Studierenden

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

Studierende/r	Präferenzen	Schule	Präferenzen
A	W > X > Y > Z	W	B > A > D > C
B	X > W > Y > Z	X	A > B > C > D
C	W > Y > X > Z	Y	C > D > A > B
D	Y > W > X > Z	Z	D > C > B > A

Endgültige Zuordnung: A-W, B-X, C-Y, D-Z. Dies ist stabil: Kein Paar möchte abweichen. Nutzen Sie die obige Interaktion zur schrittweisen Überprüfung.

Marktdesign in der Praxis

Alvin Roth (Nobelpreis 2012, geteilt mit Lloyd Shapley) beschreibt dies als „den Ö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.

Die übergeordnete Lektion: 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. Das Design ist von enormer Bedeutung.

Leitfadenbeispiel: 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: \$1(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$.

Die 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 aufgeschobener Akzeptanz 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 Dollar ein.

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

Zusammenfassung

Mechanismusdesign kehrt die Spieltheorie um: Statt Ergebnisse vorherzusagen, entwerfen wir Spiele, um gewünschte Ergebnisse zu erzielen.
Das Offenbarungsprinzip besagt, dass jedes implementierbare Ergebnis durch einen direkten Mechanismus erreicht werden kann, bei dem Agenten wahrheitsgemäß berichten. Dies vereinfacht das Designproblem erheblich.
Gibbard-Satterthwaite: Ohne Transfers sind nur Diktaturen allgemein DSIC. Bei quasi-linearen Präferenzen erreicht der VCG-Mechanismus Effizienz mit wahrheitsgemäßer Berichterstattung in dominanten Strategien.
Erlösäquivalenz: Standardauktionen mit derselben Zuteilungsregel liefern denselben erwarteten Erlös. Myersons optimale Auktion verwendet virtuelle Werte und einen Reservepreis zur Maximierung des Verkäufererlöses.
Myerson-Satterthwaite-Unmöglichkeit: Bilateraler Handel mit privater Information kann nicht gleichzeitig effizient, anreizkompatibel, individuell rational und budgetausgeglichen sein.
Matching-Märkte (Gale-Shapley) erzeugen stabile Zuordnungen ohne Preise. Der Algorithmus ist strategiesicher für die vorschlagende Seite und terminiert in polynomieller Zeit.
Marktdesign wendet diese Ideen auf reale Institutionen an: Facharztausbildung, Schulwahl, Nierentausch, Frequenzauktionen.

Bezeichnung	Gleichung	Beschreibung
Gl. 11.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. 11.2	$E[U_i(\theta_i, \theta_i)] \geq E[U_i(\hat{\theta}_i, \theta_i)]$	BIC
Gl. 11.3	$t_i = \sum_{j \neq i} v_j(a^(\theta_{-i})) - \sum_{j \neq i} v_j(a^(\theta))$	VCG-Zahlung
Gl. 11.4	$\psi(\theta) = \theta - (1-F(\theta))/f(\theta)$	Myersons virtueller Wert

Übungen

Übung

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.
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.
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

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?
Erklären Sie, warum eBay eine Zweitpreisauktion (Proxy-Bieten) statt einer Erstpreisauktion verwendet. Wie hängt das Vickrey-Ergebnis mit eBays Design zusammen?
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 die aufgeschobene Akzeptanz dies behebt.
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

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$?
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.)
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?
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?

Kapitel 11Mechanismusdesign und Marktdesign

Einleitung