[1]: 216–233 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.
is represented as a function: 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
is: Our goal is to select an outcome that maximizes the sum of values, i.e.: In other words, our social-choice function is utilitarian.
, a sum of money equal to the total values of the other agents: 4.
, an additional sum, based on an arbitrary function of the values of the other agents: where
An alternative function is: It is called the Clarke pivot rule.
[2] When the valuations of all agents are weakly-positive, the Clarke pivot rule has two important properties: 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.
The VCG mechanism from above can easily be generalized by changing the price function in step 3 to: 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).
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
The Vickrey–Clarke–Groves auction is a specific application of the VCG mechanism to the problem of selling goods.
It is the most general form of incentive-compatible double-auction since it can handle a combinatorial auction with arbitrary value functions on bundles.
Hence, in order to make it work, the auctioneer has to subsidize the trade.
The project should be undertaken if the sum of values of all citizens is more than the cost.
Here, the VCG mechanism with the Clarke pivot rule means that a citizen pays a non-zero tax for that project if and only if they are pivotal, i.e., without their declaration the total value is less than C and with their declaration the total value is more than C. This taxing scheme is incentive-compatible, but again it is not budget-balanced – the total amount of tax collected is usually less than C.[1]: 221 The quickest path problem is a cost-minimization problem.
[3] The goal is to send a message between two points in a communication network, which is modeled as a graph.
Different computers have different transmission speeds, so every edge in the network has a numeric cost equal to the number of milliseconds it takes to transmit the message.
Our goal is to send the message as quickly as possible, so we want to find the path with the smallest total cost.
If we know the transmission-time of each computer (-the cost of each edge), then we can use a standard algorithm for solving the shortest path problem.
For example, a computer might tell us that its transmission time is very large, so that we will not bother it with our messages.
The payment in step 3 is negative: each agent should pay to us the total time that the other agents spent on the message (note that the value is measured in units of time.
The Clarke pivot rule can be used to make the mechanism individually-rational: after paying us the cost, each agent receives from us a positive payment, which is equal to the time it would have taken the message to arrive at its destination if the agent would not have been present.
Intuitively, each agent is paid according to its marginal contribution to the transmission.
Other graph problems can be solved in a similar way, e.g. minimum spanning tree or maximum matching.
A similar solution applies to the more general case where each agent holds some subset of the edges.
[3] For another example, where the VCG mechanism provides a sub-optimal approximation, see truthful job scheduling.
Roberts' theorem proves that, if: then only weighted utilitarian functions can be implemented.
A VCG mechanism has to calculate the optimal outcome, based on the agents' reports (step 2 above).
For example, in combinatorial auctions, calculating the optimal assignment is NP-hard.