Vickrey-Clarke-Groves (VCG) Auction
VCG is a generic truthful mechansim:
Allocation = the one that maximizes social welfare or total value (assuming value = bid)
Price (i ) = cost imposed by i on others
= total increase in others’ value if i were to disappear.
To run VCG for prefix auctions:
Find max-value cutoff-respecting matching of ads to positions.
For each advertiser i ,
Remove i from the pool of advertisers.
Recalculate max matching.
Set price(i ) = value of all other advertisers.