The Vickrey (-Clarke-Groves)

Combinatorial Auction Procedure

Two items, A and B, are up for sale.

Bidder 1 wants only item A, and values the two items and the package at

 A B AB 150 0 150

Bidder 2 wants only item B, and values the two items and the package at

 A B AB 0 150 150

Bidder 3 wants only the package, and values the two items and the package at

 A B AB 0 0 200

Assume that each submits bids on the individual items and the package equal to their valuations.

Giving A to bidder 1 and B to bidder 2 maximizes the total bid at 300. If either bidder had not been present, the maximizing allocation would give AB to bidder 3 with a total bid of 200.

The VCG allocation rule: Each bidder receives the package assigned to him in the maximizing-total-bid partition.

������� Bidder 1 gets A

Bidder 2 gets B

The VCG pricing rule: Each winning bidder pays the amount he bid for the package received, and is rebated the increment to the maximizing total bid caused by his participation. (Note that, when only one item is up for sale, this is just the second-price auction procedure; when many identical items are being sold, it is the uniform-price procedure.)

Therefore:

Bidder 1 pays 150-(300-200) = 50

Bidder 2 pays 150-(300-200) = 50

The remarkable VCG property: Each bidder can do no better than to bid his own valuations. (In economic parlance, "truth-telling" is a dominant strategy for each bidder, and the procedure is a �demand-revealing mechanism.�)

The �Political� Problem with VCG

Bidder 1 values the two items and the package at

 A B AB 160 0 160

Bidders 2 and 3 are as before.

Again, each submits bids on the individual items and the package equal to their valuations.

Bidder 1 gets A, pays 160-(310-200) = 50

Bidder 2 gets B, pays 150-(310-200) = 40 (!!!)