Vickrey-Clarke-Groves-Mechanismus

Vickrey-Clarke-Groves-Mechanismen (VCG-Mechanismen) sind eine Verallgemeinerung der Vickreyauktion.

Mit diesem Begriff wird eine Klasse von Mechanismen bezeichnet, deren Mitglieder die Eigenschaft haben, dass wahrheitsgemäßes Bieten eine dominante Strategie für die Spieler ist.

VCG-Mechanismen können angewandt werden, wenn die Nutzenfunktion des Problems quasi-linear ist, also Geldzahlungen zwischen den Agenten möglich sind.

Ein Mechanismus wird als VCG-Mechanismus bezeichnet, wenn er folgende zwei Bedingungen erfüllt:

• Die Auswahlfunktion maximiert den Gesamtnutzen, und
• die Zahlung jedes Agenten entspricht den Opportunitätskosten, die durch seine Teilnahme entstehen.

Beispiel Vickreyauktion

Gegeben seien die Bieter $1,\ldots ,n$ mit den Typen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_i (1\leq i\leq n)} . Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_i} wird dabei als Nutzen des Gutes für Bieter Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} verstanden. Die Auswahlfunktion entscheidet, welcher Bieter den Zuschlag erhält, und erfüllt die Bedingung, dass einer der Höchstbieter gewinnt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x(t_1,\ldots,t_n)\in \arg \max_i t_i}

Die Opportunitätskosten für den Gewinner entsprechen dem entgangenen Gewinn, der bei Annahme des nächsthöchsten Gebotes entstanden wäre, also gerade der Höhe des zweithöchsten Gebotes bzw. 0, wenn kein solches vorliegt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(t_1,\ldots,t_n)\in \arg \max_{i'\neq i} t_{i'} }

Beispiel Kombinatorische Auktion

Die Bieter Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1,\ldots,n} bieten nun für Bündel aus der Gütermenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=\{g_1,\ldots,g_m\}} . Sei $v_{i}(G')\,$ der Nutzen, den Agent Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} aus dem Güterbündel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G'\subseteq G} zieht. Der Typ eines Agenten legt also für jedes Güterbündel den jeweiligen Nutzen fest:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t_i=\langle v_i(G'):G'\subseteq G\rangle}

Die Auswahlfunktion des VCG-Mechanismus verteilt die Güter so an die Agenten, dass die Gesamtsumme der individuellen Nutzen maximiert wird:

Bezeichne

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x(\vec{t})=(x_1(\vec{t}),\ldots,x_n(\vec{t}))\in \mathcal{P}(G)^n}

eine mögliche Auswahlfunktion (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i\,} ist also das Güterbündel, das Agent Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle i\,} erhält, wenn die Agenten ${\vec {t}}$ bieten.) und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T=\{\vec{t}=\langle t(G'): G'\subseteq G\rangle\}}

die Menge der möglichen Typvektoren der Agenten,

so löst Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x(\vec{t})} das Optimierungsproblem

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x(\vec{t})\rightarrow \max_{x\in \mathcal{P}(G)^n} \sum_{1\leq i\leq n} v_i(x_i) } mit den Nebenbedingungen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i\cap x_j=\emptyset} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i\neq j} .

Für die Zahlungsfunktion des VCG-Mechanismus gilt mit der Bezeichnung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V(x)=\sum_i v_i(x_i)\,}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i(t_1,\ldots,t_n)= V\left(x(t_1,\ldots,t_{i-1},0,t_{i+1},\ldots,t_n)\right)-V\left(x(t_1,\ldots,t_n)\right)}

Beispiel Bereitstellung öffentlicher Güter

Der Preis des öffentlichen Gutes wird durch alle Spieler gleich aufgeteilt. Nun kann der Nutzen der Spieler größer oder kleiner als dieser Preis sein und die Differenz entspricht den Geboten (und Wertschätzung). Ist die Summe aller Gebote $\geq$0 wird das öffentliche Gut bereitgestellt, ist die Summe <0 wird es nicht bereitgestellt. Damit die wahre Wertschätzung geboten wird, und nicht viel mehr, damit das gewünschte Ergebnis kommt, muss noch ein Zahlungsmechanismus eingeführt werden, der folgendermaßen funktioniert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t^i(\hat v)=\begin{cases} 0, & \text{wenn }\hat \sum \ge 0 \text{ und}\hat \sum {}^{-i} \ge 0\\ 0, & \text{wenn }\hat \sum < 0 \text{ und}\hat \sum {}^{-i} < 0\\ \hat \sum {}^{-i}, & \text{wenn }\hat \sum < 0 \text{ und}\hat \sum {}^{-i} \ge 0\\ - \hat \sum {}^{-i}, & \text{wenn }\hat \sum \ge 0 \text{ und}\hat \sum {}^{-i} < 0 \end{cases}}

D.h. wenn die Summe aller Gebote ohne das des Spielers i Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ge} 0 (<0) sind, und die Summe mit seinem Gebot<0 (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ge} 0), muss er den Betrag der Summe ohne ihn (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left| \hat \sum {}^{-i} \right|} ) bezahlen, sonst nichts. Dies lässt das Bieten der wahren Wertschätzung zur schwachdominanten Strategie werden. Der so über den Preis der Bereitstellung bezahlte Betrag muss allerdings vernichtet werden, da sonst Interdependenzen entstehen, die die Dominanz der Strategie beeinträchtigen würden. Somit ist der Mechanismus zwar effizient, aber nicht Wohlfahrtsmaximierend. Zudem besteht Kollusionsgefahr, wenn alle Gebote bekannt sind.

Einzigkeit der VCG-Mechanismen

Green und Laffont haben im Jahre 1977 gezeigt, dass unter der Voraussetzung, dass der Typenraum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} pfadverbunden ist, die VCG-Mechanismen die einzigen Mechanismen sind, die die Summe der individuellen Nutzen maximieren und bei denen wahrheitsgemäßes Spiel eine dominante Strategie ist.

Dieses Theorem kann auch aus dem Umhüllungssatz abgeleitet werden.

Literatur

• Mas-Colell, Andreu; Whinston, Michael; & Green, Jerry (1995). Microeconomic Theory. Oxford: Oxford University Press. ISBN 0-19-507340-1
• Milgrom, Paul (2004). Putting Auction Theory to Work. Cambridge: Cambridge University Press. ISBN 0-521-55184-6
• Kreps, David M. (1990). A Course in Microeconomic Theory. New York: Princeton University Press. ISBN 0-691-04264-0