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.
The most obvious generalization to multiple or divisible goods is to have all winning bidders pay the amount of the highest non-winning bid. This is known as a uniform price auction. The uniform-price auction does not, however, result in bidders bidding their true valuations as they do in a second-price auction unless each bidder has demand for only a single unit. A generalization of the Vickrey auction that maintains the incentive to bid truthfully is known as the Vickrey–Clarke–Groves (VCG) mechanism. The idea in VCG is that items are assigned to maximize the sum of utilities; then each bidder pays the “opportunity cost” that their presence introduces to all the other players. This opportunity cost for a bidder is defined as the total bids of all the other bidders that would have won if the first bidder didn’t bid, minus the total bids of all the other actual winning bidders.
For example, suppose two apples are being auctioned among three bidders.
- Bidder A wants one apple and bids $5 for that apple.
- Bidder B wants one apple and is willing to pay $2 for it.
- Bidder C wants two apples and is willing to pay $6 to have both of them but is uninterested in buying only one without the other.
First, the outcome of the auction is determined by maximizing bids: the apples go to bidder A and bidder B. Next, the formula for deciding payments gives:
- A: B and C have total utility $2 (the amount they pay together: $2 + $0) – if A were removed, the optimal allocation would give B and C total utility $6 ($0 + $6). So A pays $4 ($6 − $2).
- B: A and C have total utility $5 ($5 + $0) – if B were removed, the optimal allocation would give A and C total utility $6 ($0 + $6). So B pays $1 ($6 − $5).
- similarly, C pays $0 (($5 + $2) − ($5 + $2)).