Position auctions with bidder-specific minimum prices

Eyal Even-Dar, Jon Feldman, Yishay Mansour, S. Muthukrishnan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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.

    Original languageEnglish (US)
    Title of host publicationInternet and Network Economics - 4th International Workshop, WINE 2008, Proceedings
    Number of pages8
    StatePublished - 2008
    Event4th International Workshop on Internet and Network Economics, WINE 2008 - Shanghai, China
    Duration: Dec 17 2008Dec 20 2008

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume5385 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference4th International Workshop on Internet and Network Economics, WINE 2008

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Position auctions with bidder-specific minimum prices'. Together they form a unique fingerprint.

    Cite this