On Expressing Value Externalities in Position Auctions

Authors

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

Abstract

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.

Downloads

Published

2011-08-04

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. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7889

Issue

Section

AAAI Technical Track: Multiagent Systems