On Expressing Value Externalities in Position Auctions


  • Florin Constantin Georgia Institute of Technology
  • Malvika Rao Harvard University
  • Chien-Chung Huang Humboldt-Universität zu Berlin
  • David Parkes Harvard University




We 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 NP-hard, we bound the approximation ratio for social welfare in eGSP and provide parameterized complexity results.




How to Cite

Constantin, F., Rao, M., Huang, C.-C., & Parkes, D. (2011). On Expressing Value Externalities in Position Auctions. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 644-649. https://doi.org/10.1609/aaai.v25i1.7889



AAAI Technical Track: Multiagent Systems