On Expressing Value Externalities in Position Auctions
MetadataShow full item record
CitationFlorin, Constantin, Rao Malvika, Chien-Chung Huang, and David C. Parkes. Forthcoming. On expressing value externalities in position auctions. In Proceedings of the Twenty-fifth AAAI Conference on Artificial Intelligence (AAAI-11): August 7-11, 2011. San Francisco, Calif., ed. American Association for Artificial Intelligence, Menlo Park, Calif.: AAAI Press.
AbstractWe introduce a bidding language for expressing negative value externalities in position auctions for online advertising. The unit-bidder constraints (UBC) language allows a bidder to condition a bid on its allocated slot and on the slots allocated to other bidders. We introduce a natural extension of the Generalized Second Price (GSP) auction, the expressive GSP (eGSP) auction, that induces truthful revelation of constraints for a rich subclass of unit-bidder types,namely downward-monotonic UBC. We establish the existence of envy-free Nash equilibrium in eGSP under a further restriction to a subclass of exclusion constraints, for which the standard GSP has no pure strategy Nash equilibrium. The equilibrium results are obtained by reduction to equilibrium analysis for reserve price GSP (Even-Dar et al. 2008). In considering the winner determination problem, which is NPhard, we bound the approximation ratio for social welfare in eGSP and provide parameterized complexity results.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4906326
- FAS Scholarly Articles