@article{Constantin_Rao_Huang_Parkes_2011, title={On Expressing Value Externalities in Position Auctions}, volume={25}, url={https://ojs.aaai.org/index.php/AAAI/article/view/7889}, DOI={10.1609/aaai.v25i1.7889}, abstractNote={ <p> 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. </p> }, number={1}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Constantin, Florin and Rao, Malvika and Huang, Chien-Chung and Parkes, David}, year={2011}, month={Aug.}, pages={644-649} }