Vickrey-Clark-Groves (VCG) Auction

vcg.txt

The Vickrey-Clark-Groves (VCG) auction
Auctions are often about selling multiple items at the same time
  Timber   spectrum   oil fields   etc
But it is often the case that the buyers want only a subset of the items. However,
  bidders would like to bid more items than needed
  bidders do not want to buy more items than needed.
The Vickrey-Clark-Groves (VCG) auction is the solution to this problem.
  
  B = {1,2,...,n} is the set of bidders
  X = {x1,x2,...,xk} is the set of items to be sold.
Each bidder i has a valuation vi over the sets of items.
Suppose that bidder 1’s most preferred is to have items x1 and x2, and then x2 and x3, and then x1, x2, x3. His/her valuation would be then (for instance)
  v1({x1,x2}=20
  v1({x2,x3}=15
  v1({x1,x2,x3}=10
  
  More generally, each bidder has a valuation function that assigns to each set of items a value.
So bidder i’s valuation is a function vi that assigns for each subset S ⊆ X a valuation vi (S).
The interpretation is the same as before: vi(S) is how much bidder i is willing to pay to get the items S:
  all the items that are contained in S   no item that is not contained in S.
  
  The VCG auction works as follows:
1. Each bidder submits his bid function.
⇒ it is like a sealed-bid auction.
2. The assignment is the one that maximizes the social value
3. Each bidder pays the externality he/she imposes on the other bidders.

TBC