The auction system assigns the items in a socially optimal manner: it charges each individual the harm they cause to other bidders.
[1] It gives bidders an incentive to bid their true valuations, by ensuring that the optimal strategy for each bidder is to bid their true valuations of the items; it can be undermined by bidder collusion and in particular in some circumstances by a single bidder making multiple bids under different names.
It is a generalization of a Vickrey auction for multiple items.
The auction is named after William Vickrey,[2] Edward H. Clarke,[3] and Theodore Groves[4] for their papers that successively generalized the idea.
While the VCG auction tries to make a socially optimal allocation of items, VCG mechanisms allow for the selection of a socially optimal outcome out of a set of possible outcomes.
If collusion is likely to occur among bidders, the VCG outperforms the generalized second-price auction for both revenues produced for the seller and allocative efficiency.
[5] Consider an auction where a set of identical products are being sold.
Bidders can take part in the auction by announcing the maximum price they are willing to pay to receive N products.
Each buyer is allowed to declare more than one bid, since its willingness-to-pay per unit might be different depending on the total number of units it receives.
Bidders cannot see other people's bids at any moment since they are sealed (only visible to the auction system).
All the possible combinations of bids are then considered by the auction system, and the one maximizing the total sum of bids is kept, with the condition that it does not exceed the total amount of products available and that at most one bid from each bidder can be used.
In all other cases, the price paid by the buyers will be lower.
At the end of the auction, the total utility has been maximized since all the goods have been attributed to the people with the highest combined willingness-to-pay.
If agents are fully rational and in the absence of collusion, we can assume that the willingness to pay have been reported truthfully since only the marginal harm to other bidders will be charged to each participant, making truthful reporting a weakly-dominant strategy.
be the social value of the VCG auction for a given bid-combination.
That is, how much each person values the items they've just won, added up across everyone.
, which is the social cost of their winning that is incurred by the rest of the agents.
The difference between the two levels of welfare is therefore the loss in attainable welfare suffered by the rest of the bidders, as predicted, given the winner
The winning bidder whose bid is the true value
First, the outcome of the auction is determined by maximizing bids: the apples go to bidder A and bidder B, since their combined bid of $5 + $2 = $7 is greater than the bid for two apples by bidder C who is willing to pay only $6.
Note that the determination of winners is essentially a knapsack problem.
Next, the formula for deciding payments gives: After the auction, A is $1 better off than before (paying $4 to gain $5 of utility), B is $1 better off than before (paying $1 to gain $2 of utility), and C is neutral (having not won anything).
; however, the socially optimal assignment gives item
Possible outcomes are characterized by bipartite matchings pairing houses with people.
If we know the values, then maximizing social welfare reduces to computing a maximum weight bipartite matching.
, a maximum weight bipartite matching with respect to the bids, and compute The first term is another max weight bipartite matching, and the second term can be computed easily from
The following is a proof that bidding one's true valuations for the auctioned items is optimal.
is given by their own valuation of the item they've won, minus the price they've paid: As
is the corporate gross utility obtained with the non-truthful bidding.
which gets maximum (true) gross corporate utility.