TY - GEN
T1 - Position auctions with bidder-specific minimum prices
AU - Even-Dar, Eyal
AU - Feldman, Jon
AU - Mansour, Yishay
AU - Muthukrishnan, S.
PY - 2008
Y1 - 2008
N2 - Position auctions such as the Generalized Second Price (GSP) auction are in wide use for sponsored search, e.g., by Yahoo! and Google. We now have an understanding of the equilibria of these auctions, via game-theoretic concepts like Generalized English Auctions and the "locally envy-free" property, as well as through a relationship to the well-known, truthful Vickrey-Clarke-Groves (VCG) mechanism. In practice, however, position auctions are implemented with additional constraints, in particular, bidder-specific minimum prices are enforced by all major search engines. The minimum prices are used to control the quality of the ads that appear on the page. We study the effect of bidder-specific minimum prices in position auctions with an emphasis on GSP. Some properties proved for standard GSP no longer hold in this setting. For example, we show that the GSP allocation is now not always efficient (in terms of advertiser value). Also, the property of "envy-locality" enjoyed by GSP-which is essential in the prior analysis of strategies and equilibria-no longer holds. Our main result is to show that despite losing envy locality, GSP with bidder-specific minimum prices still has an envy-free equilibrium. We conclude by studying the effect of bidder-specific minimum prices on VCG auctions.
AB - Position auctions such as the Generalized Second Price (GSP) auction are in wide use for sponsored search, e.g., by Yahoo! and Google. We now have an understanding of the equilibria of these auctions, via game-theoretic concepts like Generalized English Auctions and the "locally envy-free" property, as well as through a relationship to the well-known, truthful Vickrey-Clarke-Groves (VCG) mechanism. In practice, however, position auctions are implemented with additional constraints, in particular, bidder-specific minimum prices are enforced by all major search engines. The minimum prices are used to control the quality of the ads that appear on the page. We study the effect of bidder-specific minimum prices in position auctions with an emphasis on GSP. Some properties proved for standard GSP no longer hold in this setting. For example, we show that the GSP allocation is now not always efficient (in terms of advertiser value). Also, the property of "envy-locality" enjoyed by GSP-which is essential in the prior analysis of strategies and equilibria-no longer holds. Our main result is to show that despite losing envy locality, GSP with bidder-specific minimum prices still has an envy-free equilibrium. We conclude by studying the effect of bidder-specific minimum prices on VCG auctions.
UR - http://www.scopus.com/inward/record.url?scp=58849114994&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58849114994&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-92185-1_64
DO - 10.1007/978-3-540-92185-1_64
M3 - Conference contribution
AN - SCOPUS:58849114994
SN - 3540921842
SN - 9783540921844
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 577
EP - 584
BT - Internet and Network Economics - 4th International Workshop, WINE 2008, Proceedings
T2 - 4th International Workshop on Internet and Network Economics, WINE 2008
Y2 - 17 December 2008 through 20 December 2008
ER -