Vickrey–Clarke–Groves mechanism

There is a set ${\displaystyle X}$ of possible outcomes.

There are ${\displaystyle n}$ agents, each of which has a set of outcome valuations. The valuation of agent ${\displaystyle i}$ is represented as a function:

${\displaystyle v_{i}:X\longrightarrow R_{+}}$

which expresses the value it has for each alternative, in monetary terms.

It is assumed that the agents have quasilinear utility functions; this means that, if the outcome is ${\displaystyle x}$ and in addition the agent receives a payment ${\displaystyle p_{i}}$ (positive or negative), then the total utility of agent ${\displaystyle i}$ is:

${\displaystyle u_{i}:=v_{i}(x)+p_{i}}$

Our goal is to select an outcome that maximizes the sum of values, i.e.:

${\displaystyle x^{opt}(v)=\arg \max _{x\in X}\sum _{i=1}^{n}v_{i}(x)}$

In other words, our social-choice function is utilitarian.

The VCG family is a family of mechanisms that implements the utilitarian welfare function. A typical mechanism in the VCG family works in the following way:

1. It asks the agents to report their value function. I.e, each agent ${\displaystyle i}$ should report ${\displaystyle v_{i}(x)}$ for each option ${\displaystyle x}$.

2. Based on the agents' report-vector ${\displaystyle v}$, it calculates ${\displaystyle x^{*}=x^{opt}(v)}$ as above.

3. It pays, to each agent ${\displaystyle i}$, a sum of money equal to the total values of the other agents:

${\displaystyle p_{i}:=\sum _{j\neq i}v_{j}(x^{*})}$

4. It pays, to each agent ${\displaystyle i}$, an additional sum, based on an arbitrary function of the values of the other agents:

${\displaystyle p_{i}+h_{i}(v_{-i})}$

where ${\displaystyle v_{-i}=(v_{1},\dots ,v_{i-1},v_{i+1},\dots ,v_{n})}$, that is, ${\displaystyle h_{i}}$ is a function that depends only on the valuations of the other agents.

Every mechanism in the VCG family is a truthful mechanism, that is, a mechanism where bidding the true valuation is a dominant strategy.

The trick is in step 3. The agent is paid the total value of the other agents; hence, together with its own value, the total welfare of the agent is exactly equal to the total welfare of society. Hence, the incentives of the agent are aligned with those of the society and the agent is incentivized to be truthful in order to help the mechanism achieve its goal.

The function ${\displaystyle h_{i}}$, in step 4, does not affect the agent's incentives, since it depends only on the declarations of the other agents.

The function ${\displaystyle h_{i}}$ is a parameter of the mechanism. Every selection of ${\displaystyle h_{i}}$ yields a different mechanism in the VCG family.

We could take, for example:

${\displaystyle h_{i}(v_{-i})=0}$,

but then we would have to actually pay the players to participate in the auction. We would rather prefer that players give money to the mechanism.

An alternative function is:

${\displaystyle h_{i}(v_{-i})=-\max _{x\in X}\sum _{j\neq i}v_{j}(x)}$

It is called the Clarke pivot rule. With the Clarke pivot rule, the total amount paid by the player is:

(social welfare of others if ${\displaystyle i}$ were absent) - (social welfare of others when ${\displaystyle i}$ is present).

This is exactly the externality of player ${\displaystyle i}$.[2]

When the valuations of all agents are weakly-positive, the Clarke pivot rule has two important properties:

• Individual rationality: for every player i, ${\displaystyle v_{i}(x)+p_{i}\geq 0}$. It means that all the players are getting positive utility by participating in the auction. No one is forced to bid.
• No positive transfers: for every player i, ${\displaystyle p_{i}\leq 0}$. The mechanism does not need to pay anything to the bidders.

This makes the VCG mechanism a win-win game: the players receive the outcomes they desire, and pay an amount which is less than their gain. So the players remain with a net positive gain, and the mechanism gains a net positive payment.

Instead of maximizing the sum of values, we may want to maximize a weighted sum:

${\displaystyle x^{opt}(v)=\arg \max _{x\in X}\sum _{i=1}^{n}w_{i}v_{i}(x)}$

where ${\displaystyle w_{i}}$ is a weight assigned to agent ${\displaystyle i}$.

The VCG mechanism from above can easily be generalized by changing the price function in step 3 to:

${\displaystyle p_{i}:={1 \over w_{i}}\sum _{j\neq i}w_{j}v_{j}(x^{*})}$

The VCG mechanism can be adapted to situations in which the goal is to minimize the sum of costs (instead of maximizing the sum of gains). Costs can be represented as negative values, so that minimization of cost is equivalent to maximization of values.

The payments in step 3 are negative: each agent has to pay the total cost incurred by all other agents. If agents are free to choose whether to participate or not, then we must make sure that their net payment is non-negative (this requirement is called individual rationality). The Clarke pivot rule can be used for this purpose: in step 4, each agent ${\displaystyle i}$ is paid the total cost that would have been incurred by other agents, if the agent ${\displaystyle i}$ would not participate. The net payment to agent ${\displaystyle i}$ is its marginal contribution to reducing the total cost.

A VCG mechanism implements a utilitarian social-choice function - a function that maximizes a weighted sum of values (also called an affine maximizer). Roberts' theorem proves that, if:

• The agents' valuation functions are unrestricted (each agent can have as value function any function from ${\displaystyle X}$ to ${\displaystyle \mathbb {R} }$), and -
• There are at least three different possible outcomes (${\displaystyle |X|\geq 3}$ and at least three different outcomes from ${\displaystyle X}$ can happen),

then only weighted utilitarian functions can be implemented.[1]^{: 228, chap.12} So with unrestricted valuations, the social-choice functions implemented by VCG mechanisms are the only functions that can be implemented truthfully.

Moreover, the price-functions of the VCG mechanisms are also unique in the following sense.[1]^{: 230–231} If:

• The domains of the agents' valuations are connected sets (particularly, agents can have real-valued preferences and not only integral preferences);
• There is a truthful mechanism that implements a certain ${\displaystyle Outcome}$ function with certain payment functions ${\displaystyle p_{1},\dots ,p_{n}}$;
• There is another truthful mechanism that implements the same ${\displaystyle Outcome}$ function with different payment functions ${\displaystyle p'_{1},\dots ,p'_{n}}$;

Then, there exist functions ${\displaystyle h_{1},\dots ,h_{n}}$ such that, for all ${\displaystyle i}$:

${\displaystyle p'_{i}(v_{i},v_{-i})=p_{i}(v_{i},v_{-i})+h_{i}(v_{-i})}$

I.e, the price functions of the two mechanisms differ only by a function that does not depend on the agent's valuation ${\displaystyle v_{i}}$ (only on the valuations of the other agents).

This means that VCG mechanisms are the only truthful mechanisms that maximize the utilitarian social-welfare.

A VCG mechanism has to calculate the optimal outcome, based on the agents' reports (step 2 above). In some cases, this calculation is computationally difficult. For example, in combinatorial auctions, calculating the optimal assignment is NP-hard.[1]^{: 270–273, chap.11}

Sometimes there are approximation algorithms to the optimization problem, but, using such an approximation might make the mechanism non-truthful.[3]

• Algorithmic mechanism design
• Incentive compatibility
• Quadratic voting