AAAI Publications, Twenty-Sixth AAAI Conference on Artificial Intelligence

Font Size: 
Optimal Auctions for Spiteful Bidders
Pingzhong Tang, Tuomas Sandholm

Last modified: 2012-07-14

Abstract


Designing revenue-optimal auctions for various settings is perhaps the most important, yet sometimes most elusive, problem in mechanism design. Spiteful bidders have been intensely studied recently, especially because spite occurs in many applications in multiagent system and electronic commerce. We derive the optimal auction for such bidders (as well as bidders that are altruistic). It is a generalization of Myerson’s (1981) auction. It chooses an allocation that maximizes agents’ virtual valuations, but for a generalized definition of virtual valuation. The payment rule is less intuitive. For one, it takes each bidder’s own report into consideration when determining his payment. Moreover, bidders pay even if the seller keeps the item; a similar phenomenon has been shown in other settings with neg- ative externalities (Jehiel, Moldovanu, and Stacchetti 1996; Deng and Pekec 2011). On the other hand, a novel aspect of our auction is that it sometimes subsidizes losers when the item is sold to some other bidder. We also derive a revenue equivalence theorem for this setting. Using it, we generate a short proof of (a slight generalization of) the previously known result that, in two-bidder settings with independently uniformly drawn valuations, second-price auctions yield greater expected revenue than first-price auctions. Finally, we present a template for comparing the expected revenues of any two auction mechanisms that have the same allocation rule (for the valuations distributions at hand).

Full Text: PDF