Abstract: In this post, we look at the Vickery-Clarke-Groves auction and discuss its implications. We also look at the generalized VCG-mechanism.
In our last post, we looked at how one would run a sealed bid auction with one item if one would want to maximize social utility. However what if we have more than one item? How could we then design an auction such that social utility was maximized?
Recall, that the reason the Vickery auction works is that we know that a person’s optimal bid is their true valuation for the item, thus we can safely assume that picking the person who bid the highest gives it to the person who wanted it the most. Thus, in order to do the same thing with multiple items, we need to make sure that the auction is DSIC. Once we have done that, we can simply pick the allocation that maximizes social utility.
Thus, the main question we need to answer is how to do we create a payment system that is DSIC. The answer is to charge the participants the harm they do to the system. Moreover, the payment for a bidder i is the sum of the bids in this result that don’t include bidder i, minus what would be the optimal auction without bidder i. This can also be thought of as the welfare loss caused by such the player and is often referred to as the externality caused by player i.
To see that this mechanism is DSIC let us consider the generalization of the VCG-auction, the VCG-mechanism. This mechanism works in a similar way, but it is slightly more general. Each participant submits their valuation for all possible outcomes and then selects the one that maximizes social benefit. We then pay (or require payment from) each agent an amount equal to the total values of all other agents. Finally, we then pay (or require payment) another amount based on a function of the other players’ valuations.
It is easy to see how this generalizes to the auction, with the arbitrary function being the welfare if player i was not present. We can also see that this mechanism is DSIC as an agent’s payout is determined by the valuations of the other agents. This combined with the individual player’s valuation is the total welfare, so the agent is allied with the group and is incentivized to help the mechanism maximize social welfare. The best way to do so is to give true valuations thus we can see how this mechanism is DSIC.
There are a number of issues with the VCG-mechanism, however. Although it shows that an optimal distribution does exist, calculating said distribution is (assuming P != NP) not really feasible for large inputs. Additionally, the mechanism is not immune to collusion, something that may be touched on in later posts. Finally, for a more rigorous mathematical analysis of these mechanism see the links below!
George Georgiadis notes
Tim Roughgarden notes
Wikipedia article
The Board Game Scholar 