An online mechanism for ad slot reservations with cancellations

ABSTRACT

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.

REFERENCES

• 1: M. Babaioff, J. Hartline, and R. Kleinberg. Selling banner ads: Online algorithms with buyback. In Fourth Workshop on Ad Auctions, 2008. To appear.
• 2: Moshe Babaioff , Nicole Immorlica , Robert Kleinberg, Matroids, secretary problems, and online mechanisms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.434-443, January 07-09, 2007, New Orleans, Louisiana
• 3: Moshe Babaioff , Ron Lavi , Elan Pavlov, Single-value combinatorial auctions and implementation in undominated strategies, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1054-1063, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109674]
• 4: S. Bikhchandani, J. Schummer, S. de Vries, and R. Vohra. An ascending Vickrey auction for selling bases of a matroid. November 2006.
• 5: Matthew C. Cary , Abraham D. Flaxman , Jason D. Hartline , Anna R. Karlin, Auctions for structured procurement, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.304-313, January 20-22, 2008, San Francisco, California
• 6: N. B. Dimitrov and C. G. Plaxton. Competitive weighted matching in transversal matroids. UT Austin, Technical Report T-08-03, January 2008.
• 7: Ureil Feige , Nicole Immorlica , Vahab Mirrokni , Hamid Nazerzadeh, A combinatorial allocation mechanism with penalties for banner advertising, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367521]
• 8: J. Gallien and S. Gupta. Temporary and permanent buyout prices in online auctions. Mgmt. Science, 53:814--833, 2007.
• 9: V. Krishna. Auction Theory. Academic Press, 2002.
• 10: Ron Lavi , Noam Nisan, Competitive analysis of incentive compatible on-line auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.233-241, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352897]
• 11: A. McGregor. Finding graph matchings in data streams. In Proceedings of APPROX-RANDOM, pages 170--181, 2005.
• 12: T. C. Schelling. The Strategy of Conflict. Harvard University Press, 1960.
• 13: K. Talluri and G. V. Ryzin. The theory and practice of revenue management. Kluwer Academic Publ, 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation