On Expressing Value Externalities in Position Auctions

DSpace/Manakin Repository

On Expressing Value Externalities in Position Auctions

Citable link to this page


Title: On Expressing Value Externalities in Position Auctions
Author: Constantin, Florin; Rao, Malvika; Huang, Chien-Chung; Parkes, David C.

Note: Order does not necessarily reflect citation order of authors.

Citation: Florin, 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.
Full Text & Related Files:
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 NPhard, we bound the approximation ratio for social welfare in eGSP and provide parameterized complexity results.
Other Sources: http://www.eecs.harvard.edu/econcs/pubs/Constantin_aaai11.pdf
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAP
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4906326
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search