Vickrey–Clarke–Groves mechanism
Vickrey–Clarke–Groves mechanism
In mechanism-design, the [[william-vickrey|Vickrey]]–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially optimal solution whenever monetary transfers are available. It generalizes the vickrey–clarke–groves-auction into a general-purpose mechanism for social choice, which can be used to select any outcome from a set of possible outcomes. However, the VCG mechanism also has several problems which keep it from fully solving the public goods problem, including its vulnerability to collusion and the issue of participants failing to pay their bids.
Notation There is a set <math>X</math> of possible outcomes.
There are <math>n</math> agents, each of which has a set of outcome valuations. The valuation of agent <math>i</math> is represented as a function:
: <math>v_i : X \to \mathbb{R}_+</math>
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 <math>x</math> and in addition the agent receives a payment <math>p_i</math> (positive or negative), then the total utility of agent <math>i</math> is:
: <math>u_i := v_i(x) + p_i</math>
Our goal is to select an outcome that maximizes the sum of values, i.e.:
: <math>x^{opt}(v) = \arg\max_{x\in X} \sum_{i=1}^n v_i(x) </math>
In other words, our social-choice function is utilitarian.
Solution family 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 <math>i</math> should report <math>v_i(x)</math> for each option <math>x</math>.
2. Based on the agents' report-vector <math>v</math>, it calculates <math>x^* = x^{opt}(v)</math> as above.
3. It pays, to each agent <math>i</math>, a sum of money equal to the total values of the other agents: : <math>p_i := \sum_{j\neq i} v_j(x^*)</math>
4. It pays, to each agent <math>i</math>, an additional sum, based on an arbitrary function of the values of the other agents: : <math>p_i + h_i(v_{-i})</math> where <math>v_{-i} = (v_1, \dots, v_{i-1}, v_{i+1}, \dots, v_n)</math>, that is, <math>h_i</math> is a function that depends only on the valuations of the other agents.
Truthfulness 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 <math>h_i</math>, in step 4, does not affect the agent's incentives, since it depends only on the declarations of the other agents.
The Clarke pivot rule The function <math>h_i</math> is a parameter of the mechanism. Every selection of <math>h_i</math> yields a different mechanism in the VCG family.
We could take, for example: : <math>h_i(v_{-i}) = 0</math>, 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: : <math>h_i(v_{-i}) = - \max_{x \in X} \sum_{j \neq i} v_j(x)</math> 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 <math>i</math> were absent) - (social welfare of others when <math>i</math> is present). This is exactly the externality of player <math>i</math>.
When the valuations of all agents are weakly-positive, the Clarke pivot rule has two important properties:
- Individual rationality: for every player i, <math>v_i (x) + p_i \geq 0</math>. 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, <math>p_i \leq 0 </math>. 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.
Weighted VCG mechanism Instead of maximizing the sum of values, we may want to maximize a weighted sum: : <math>x^{opt}(v) = \arg\max_{x\in X} \sum_{i=1}^n w_i v_i(x) </math> where <math>w_i</math> is a weight assigned to agent <math>i</math>.
The VCG mechanism from above can easily be generalized by changing the price function in step 3 to: : <math>p_i := {1 \over w_i} \sum_{j\neq i} w_j v_j(x^*)</math>
Cost minimization 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 <math>i</math> is paid the total cost that would have been incurred by other agents, if the agent <math>i</math> would not participate. The net payment to agent <math>i</math> is its marginal contribution to reducing the total cost.
Applications ### Auctions The vickrey–clarke–groves-auction is a specific application of the VCG mechanism to the problem of selling goods. Here, <math>X</math> is the set of all possible allocations of items to the agents. Each agent assigns a personal monetary value to each bundle of items, and the goal is to maximize the sum of values for all agents.
A well-known special case is the vickrey-auction, or the sealed second-bid auction. Here, there is only a single item, and the set <math>X</math> contains <math>n+1</math> possible outcomes: either sell the item to one of the <math>n</math> agents, or not to sell it at all. In step 3, the winner agent is paid 0 (since the total value of the others is 0) and the losers receive a payment equal to the declared value of the winner. In step 4, the winner pays the second-highest bid (the total value of the others had he not participated) and the losers pay the declared value of the winner (the total value of the others had they not participated). All in all, the winner pays the second-highest bid and the losers pay 0.
A VCG mechanism can also be used in a double-auction. It is the most general form of incentive-compatible double-auction since it can handle a combinatorial-auction with arbitrary value functions on bundles. Unfortunately, it is not budget-balanced: the total value paid by the buyers is smaller than the total value received by the sellers. Hence, in order to make it work, the auctioneer has to subsidize the trade.