Vickrey-Clarke-Groves Mechanism

Vickrey-Clarke-Groves mechanisms ( VCG mechanisms ) are a generalization of the Vickrey auction .

This term is used to describe a class of mechanisms whose members have the property that truthful bidding is a dominant strategy for the players.

VCG mechanisms can be used if the utility function of the problem is quasi-linear , i.e. cash payments between the agents are possible.

A mechanism is called a VCG mechanism if it meets the following two conditions:

• The selector maximizes the overall utility, and
• each agent's payment equals the opportunity cost of participating.

Example Vickrey auction

Given are the bidders with the types . is understood as the benefit of the good for bidders . The selection function decides which bidder will win and fulfills the condition that one of the highest bidders wins: ${\displaystyle 1,\ldots ,n}$ ${\displaystyle v_{i}(1\leq i\leq n)}$ ${\displaystyle v_{i}}$ ${\displaystyle i}$

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

The opportunity costs for the winner correspond to the lost profit that would have arisen if the next highest bid had been accepted, i.e. the amount of the second highest bid or 0 if there was none:

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

Example of a combinatorial auction

The bidders are now bidding for bundles from the quantity of goods . Be the benefit that the agent draws from the bundle of goods . The type of agent determines the respective benefit for each bundle of goods: ${\displaystyle 1,\ldots ,n}$ ${\displaystyle G=\{g_{1},\ldots ,g_{m}\}}$ ${\displaystyle v_{i}(G')\,}$ ${\displaystyle i}$ ${\displaystyle G'\subseteq G}$

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

The selection function of the VCG mechanism distributes the goods to the agents in such a way that the total sum of the individual benefits is maximized:

Denote

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

a possible selection function (i.e. the bundle of goods that the agent receives if the agents bid) and ${\displaystyle x_{i}\,}$ ${\displaystyle i\,}$ ${\displaystyle {\vec {t}}}$

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

the set of possible type vectors of the agents,

so solves the optimization problem ${\displaystyle x({\vec {t}})}$

${\displaystyle x({\vec {t}})\rightarrow \max _{x\in {\mathcal {P}}(G)^{n}}\sum _{1\leq i\leq n}v_{i}(x_{i})}$ with the constraints

${\displaystyle x_{i}\cap x_{j}=\emptyset }$for . ${\displaystyle i\neq j}$

The designation applies to the payment function of the VCG mechanism

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

Example provision of public goods

The price of the public good is shared equally by all players. Now the players' utility can be greater or lesser than this price and the difference corresponds to the bids (and appreciation). If the sum of all bids is 0, the public good is provided, if the sum is <0 it is not provided. In order for the true appreciation to be offered, and not much more for the desired result to come about, a payment mechanism has to be introduced that works as follows: ${\displaystyle \geq }$

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

Ie if the sum of all bids without that of the player i are 0 (<0), and the sum with his bid <0 ( 0), he has to pay the amount of the sum without him ( ), nothing else. This makes offering true appreciation the weak dominant strategy. The amount paid over the price of the provision must be destroyed, however, since otherwise interdependencies arise that would impair the dominance of the strategy. Thus the mechanism is efficient, but not welfare-maximizing. In addition, there is a risk of collusion if all the bids are known. ${\displaystyle \geq }$ ${\displaystyle \geq }$ ${\displaystyle \left|{\hat {\sum }}{}^{-i}\right|}$

Uniqueness of the VCG mechanisms

Green and Laffont showed in 1977 that, assuming the type space is path- connected, the VCG mechanisms are the only mechanisms that maximize the sum of individual benefits and where truthful play is a dominant strategy. ${\displaystyle T}$

This theorem can also be derived from the enveloping theorem .

literature

• 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