A truthful mechanism for offline ad slot scheduling

Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pál

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


    We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as well as a maximum cost per click, and may not be assigned to more than one slot for a particular search. We give a truthful mechanism under the utility model where bidders try to maximize their clicks, subject to their personal constraints. In addition, we show that the revenue-maximizing mechanism is not truthful, but has a Nash equilibrium whose outcome is identical to our mechanism. Our mechanism employs a descending-price auction that maintains a solution to a certain machine scheduling problem whose job lengths depend on the price, and hence are variable over the auction.

    Original languageEnglish (US)
    Title of host publicationAlgorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings
    Number of pages12
    StatePublished - 2008
    Event1st International Symposium on Algorithmic Game Theory, SAGT 2008 - Paderborn, Germany
    Duration: Apr 30 2008May 2 2008

    Publication series

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


    Other1st International Symposium on Algorithmic Game Theory, SAGT 2008

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'A truthful mechanism for offline ad slot scheduling'. Together they form a unique fingerprint.

    Cite this