Constantin, FlorinRao, MalvikaHuang, Chien-ChungParkes, David2011-06-062011Florin, 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.http://nrs.harvard.edu/urn-3:HUL.InstRepos:4906326We 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.en-USMonograph or Book2011-06-06