In auction theory, a Vickrey–Clarke–Groves (VCG) auction is a type of sealed-bid auction of multiple items. Bidders submit bids that report their valuations for the items, without knowing the bids of the other people in the auction. The auction system assigns the items in a socially optimal manner: it charges each individual the harm they cause to other bidders. It also 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 is a generalization of a Vickrey auction for multiple items.
Contents
- Intuitive description
- Formal description
- Example 1
- Example 2
- Example 3
- Optimality of Truthful Bidding
- References
The auction is named after William Vickrey, Edward H. Clarke, and Theodore Groves for their papers that successively generalized the idea.
The VCG auction is a specific use of the more general VCG Mechanism. 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.
Intuitive description
We 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). Once all the bids are made, the auction is closed.
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. Bidders who have made a successful bid then receive the product quantity specified in their bid. The price they pay in exchange, however, is not the amount they had bid initially but only the marginal harm their bid has caused to other bidders (which is at most as high as their original bid).
This marginal harm caused to other participants (i.e. the final price paid by each individual with a successful bid) can be calculated as: (sum of bids of the auction from the second best combination of bids) - (what other bidders have bid in the current (best) combination of bids). If the sum of bids of the second best combination of bids is the same as that of the best combination, then the price paid by the buyers will be the same as their initial bid. 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. This type of auction, however, will not maximize the seller's revenue unless the sum of bids of the second best combination of bids is equal to the sum of bids of the best combination of bids.
Formal description
For any set of auctioned items
A bidder
Indeed, the set of bidders other than
The winning bidder whose bid is the true value
Example #1
Suppose two apples are being auctioned among three bidders.
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. Thus, after the auction, the value achieved by bidder A is $5, by bidder B is $2, and by bidder C is $0 (since bidder C gets nothing). 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).
Example #2
Assume that there are two bidders,
If person
If person
Example #3
Here we will look at a multiple item auction. Consider the situation when there are
If we do not know the values, then we instead solicit bids
The first term is another max weight bipartite matching, and the second term can be computed easily from
Optimality of Truthful Bidding
The following is a proof that bidding one's true valuations for the auctioned items is optimal.
For each bidder
As
To make it clearer, let us form the difference