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 quasilinear 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 $v_i (1\leq i\leq n)$. v_i wird dabei als Nutzen des Gutes für Bieter i verstanden. Die Auswahlfunktion entscheidet, welcher Bieter den Zuschlag erhält, und erfüllt die Bedingung, dass einer der Höchstbieter gewinnt:

$x(t_1,\ldots,t_n)\in \arg \max_i t_i$

Die Opportunitätskosten für den Gewinner entsprechenden 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:

$p(t_1,\ldots,t_n)\in \arg \max_{i'\neq i} t_i$

Beispiel Kombinatorische Auktion

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

$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

$x(\vec{t})=(x_1(\vec{t}),\ldots,x_n(\vec{t}))\in \mathcal{P}(G)^n$

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

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

die Menge der möglichen Typvektoren der Agenten,

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

$x(\vec{t})\rightarrow \max_{x\in \mathcal{P}(G)^n} \sum_{1\leq i\leq n} v_i(x_i)$ mit den Nebenbedingungen

$x_i\cap x_j=\emptyset$ für $i\neq j$.

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

$V(x)=\sum_i v_i(x_i)\,$

$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 $\ge$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:

$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 $\ge$0 (<0) sind, und die Summe mit seinem Gebot<0 ($\ge$0), muss er den Betrag der Summe ohne ihn ($\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 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