Vickrey–Clarke–Groves (VCG) auction

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.[1] 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 auction is named after William Vickrey,[2] Edward H. Clarke,[3] and Theodore Groves[4] for their papers that successively generalized the idea.

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)).
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s