Selling ad campaigns: Online algorithms with cancellations

Moshe Babaioff*, Jason D Hartline, Robert D. Kleinberg

*Corresponding author for this work

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

39 Scopus citations


We study online pricing problems in markets with cancellations, i.e., markets in which prior allocation decisions can be revoked, but at a cost. In our model, a seller receives requests online and chooses which requests to accept, subject to constraints on the subsets of requests which may be accepted simultaneously. A request, once accepted, can be canceled at a cost which is a fixed fraction of the request value. This scenario models a market for web advertising campaigns, in which the buyback cost represents the cost of canceling an existing contract. We analyze a simple constant-competitive algorithm for a single-item auction in this model, and we prove that its competitive ratio is optimal among deterministic algorithms, but that the competitive ratio can be improved using a randomized algorithm. We then model ad campaigns using knapsack domains, in which the requests differ in size as well as in value. We give a deterministic online algorithm that achieves a bi-criterion approximation in which both approximation factors approach 1 as the buyback factor and the size of the maximum request approach 0. We show that the bi-criterion approximation is unavoidable for deterministic algorithms, but that a randomized algorithm is capable of achieving a constant competitive ratio. Finally, we discuss an extension of our randomized algorithm to matroid domains (in which the sets of simultaneously satisfiable requests constitute the independent sets of a matroid) as well as present results for domains in which the buyback factor of different requests varies.

Original languageEnglish (US)
Title of host publicationEC'09 - Proceedings of the 2009 ACM Conference on Electronic Commerce
Number of pages10
StatePublished - Dec 1 2009
Event2009 ACM Conference on Electronic Commerce, EC'09 - Stanford, CA, United States
Duration: Jul 6 2009Jul 10 2009

Publication series

NameProceedings of the ACM Conference on Electronic Commerce


Other2009 ACM Conference on Electronic Commerce, EC'09
CountryUnited States
CityStanford, CA


  • Costly decision revocation
  • Knapsack
  • Matroids
  • Online algorithms
  • Selling advertisements

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Selling ad campaigns: Online algorithms with cancellations'. Together they form a unique fingerprint.

Cite this