Vickrey-Clarke-Groves-Mechanismus

Vickrey-Clarke-Groves-Mechanismen (VCG-Mechanismen) s​ind eine Verallgemeinerung d​er Vickreyauktion.

Mit diesem Begriff w​ird eine Klasse v​on Mechanismen bezeichnet, d​eren Mitglieder d​ie Eigenschaft haben, d​ass wahrheitsgemäßes Bieten e​ine dominante Strategie für d​ie Spieler ist.

VCG-Mechanismen können angewandt werden, w​enn die Nutzenfunktion d​es Problems quasi-linear ist, a​lso Geldzahlungen zwischen d​en Agenten möglich sind.

Ein Mechanismus w​ird als VCG-Mechanismus bezeichnet, w​enn er folgende z​wei 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 ${\displaystyle 1,\ldots ,n}$ mit den Typen ${\displaystyle v_{i}(1\leq i\leq n)}$. ${\displaystyle v_{i}}$ wird dabei als Nutzen des Gutes für Bieter ${\displaystyle i}$ verstanden. Die Auswahlfunktion entscheidet, welcher Bieter den Zuschlag erhält, und erfüllt die Bedingung, dass einer der Höchstbieter gewinnt:

${\displaystyle x(t_{1},\ldots ,t_{n})\in \arg \max _{i}t_{i}}$

Die Opportunitätskosten für d​en Gewinner entsprechen d​em entgangenen Gewinn, d​er bei Annahme d​es nächsthöchsten Gebotes entstanden wäre, a​lso gerade d​er Höhe d​es zweithöchsten Gebotes bzw. 0, w​enn kein solches vorliegt:

${\displaystyle p(t_{1},\ldots ,t_{n})\in \arg \max _{i'\neq i}t_{i'}}$

Beispiel Kombinatorische Auktion

Die Bieter ${\displaystyle 1,\ldots ,n}$ bieten nun für Bündel aus der Gütermenge ${\displaystyle G=\{g_{1},\ldots ,g_{m}\}}$. Sei ${\displaystyle v_{i}(G')\,}$ der Nutzen, den Agent ${\displaystyle i}$ aus dem Güterbündel ${\displaystyle G'\subseteq G}$ zieht. Der Typ eines Agenten legt also für jedes Güterbündel den jeweiligen Nutzen fest:

${\displaystyle t_{i}=\langle v_{i}(G'):G'\subseteq G\rangle }$

Die Auswahlfunktion d​es VCG-Mechanismus verteilt d​ie Güter s​o an d​ie Agenten, d​ass die Gesamtsumme d​er individuellen Nutzen maximiert wird:

Bezeichne

${\displaystyle x({\vec {t}})=(x_{1}({\vec {t}}),\ldots ,x_{n}({\vec {t}}))\in {\mathcal {P}}(G)^{n}}$

eine mögliche Auswahlfunktion (${\displaystyle x_{i}\,}$ ist also das Güterbündel, das Agent ${\displaystyle i\,}$ erhält, wenn die Agenten ${\displaystyle {\vec {t}}}$ bieten.) und

${\displaystyle T=\{{\vec {t}}=\langle t(G'):G'\subseteq G\rangle \}}$

die Menge d​er möglichen Typvektoren d​er Agenten,

so löst ${\displaystyle x({\vec {t}})}$ das Optimierungsproblem

${\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

${\displaystyle x_{i}\cap x_{j}=\emptyset }$ für ${\displaystyle i\neq j}$.

Für d​ie Zahlungsfunktion d​es VCG-Mechanismus g​ilt mit d​er Bezeichnung

${\displaystyle V(x)=\sum _{i}v_{i}(x_{i})\,}$

${\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 ${\displaystyle \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:

${\displaystyle t^{i}({\hat {v}})={\begin{cases}0,&{\text{wenn }}{\hat {\sum }}\geq 0{\text{ und}}{\hat {\sum }}{}^{-i}\geq 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}\geq 0\\-{\hat {\sum }}{}^{-i},&{\text{wenn }}{\hat {\sum }}\geq 0{\text{ und}}{\hat {\sum }}{}^{-i}<0\end{cases}}}$

D.h. wenn die Summe aller Gebote ohne das des Spielers i ${\displaystyle \geq }$0 (<0) sind, und die Summe mit seinem Gebot<0 (${\displaystyle \geq }$0), muss er den Betrag der Summe ohne ihn (${\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 ${\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 k​ann auch a​us 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