Show simple item record

dc.contributor.authorConstantin, Florin
dc.contributor.authorRao, Malvika
dc.contributor.authorHuang, Chien-Chung
dc.contributor.authorParkes, David C.
dc.date.accessioned2011-06-06T15:42:32Z
dc.date.issued2011
dc.identifier.citationFlorin, 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.en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4906326
dc.description.abstractWe 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_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherAmerican Association for Artificial Intelligenceen_US
dc.relation.hasversionhttp://www.eecs.harvard.edu/econcs/pubs/Constantin_aaai11.pdf
dash.licenseOAP
dc.titleOn Expressing Value Externalities in Position Auctionsen_US
dc.typeMonograph or Booken_US
dc.description.versionAccepted Manuscripten_US
dash.depositing.authorParkes, David C.
dc.date.available2011-06-06T15:42:32Z
dash.contributor.affiliatedRao, Malvika
dash.contributor.affiliatedParkes, David


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record