TY - JOUR AU - Constantin, Florin AU - Rao, Malvika AU - Huang, Chien-Chung AU - Parkes, David PY - 2011/08/04 Y2 - 2024/03/29 TI - On Expressing Value Externalities in Position Auctions JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 25 IS - 1 SE - AAAI Technical Track: Multiagent Systems DO - 10.1609/aaai.v25i1.7889 UR - https://ojs.aaai.org/index.php/AAAI/article/view/7889 SP - 644-649 AB - <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> ER -