On Expressing Value Externalities in Position Auctions
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.
Cite
Text
Constantin et al. "On Expressing Value Externalities in Position Auctions." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.7889Markdown
[Constantin et al. "On Expressing Value Externalities in Position Auctions." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/constantin2011aaai-expressing/) doi:10.1609/AAAI.V25I1.7889BibTeX
@inproceedings{constantin2011aaai-expressing,
title = {{On Expressing Value Externalities in Position Auctions}},
author = {Constantin, Florin and Rao, Malvika and Huang, Chien-Chung and Parkes, David C.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2011},
pages = {644-649},
doi = {10.1609/AAAI.V25I1.7889},
url = {https://mlanthology.org/aaai/2011/constantin2011aaai-expressing/}
}