An online mechanism for ad slot reservations with cancellations

Florin Constantin, Jon Feldman, S. Muthukrishnan, Martin Pál

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


    Many advertisers (bidders) use Internet systems to buy display advertisements on publishers' webpages or on traditional media such as radio, TV and newsprint. They seek a simple, online mechanism to reserve ad slots in advance. On the other hand, media publishers (sellers) represent a vast and varying inventory, and they too seek automatic, online mechanisms for pricing and allocating such reservations. We propose and study a simple model for auctioning such ad slot reservations in advance. A seller will display a set of slots at some point T in the future. Until T, bidders arrive sequentially and place a bid on the slots they are interested in. The seller must decide immediately whether or not to grant a reservation. Our model allows the seller to cancel at any time any reservation made earlier, in which case the holder of the reservation incurs a utility loss amounting to a fraction of her value for the reservation and may also receive a cancellation fee from the seller. Our main result is an online mechanism for allocation and pricing in this model with many desirable game-theoretic properties. It is individually rational. Winners have an incentive to be honest and bidding one's true value dominates any lower bid. Further, it bounds the earnings of speculators who are in the game to obtain the cancellation fees. The mechanism in addition has optimization guarantees. Its revenue is within a constant fraction of the a posteriori revenue of the Vickrey-Clarke-Groves (VCG) mechanism which is known to be truthful (in the offline case). Our mechanism's efficiency is within a constant fraction of the a posteriori optimally efficient solution. If efficiency also takes into account the utility losses of bidders whose reservation was canceled, we show that our mechanism matches (for appropriate values of the parameters) an upper bound on the competitive ratio of any deterministic online algorithm. Our mechanism's technical core is a variant of the online weighted bipartite matching problem where unlike prior variants in which one randomizes edge arrivals or bounds edge weights, we may revoke previously committed edges. Our results make no assumptions about bidders' arrival order or value distribution. They still hold if we replace items with elements of a matroid and matchings with independent sets, or if all bidders have additive value for a set of items.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
    PublisherAssociation for Computing Machinery (ACM)
    Number of pages10
    ISBN (Print)9780898716801
    StatePublished - 2009
    Event20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States
    Duration: Jan 4 2009Jan 6 2009

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


    Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
    Country/TerritoryUnited States
    CityNew York, NY

    ASJC Scopus subject areas

    • Software
    • General Mathematics


    Dive into the research topics of 'An online mechanism for ad slot reservations with cancellations'. Together they form a unique fingerprint.

    Cite this