Selling ad campaigns: online algorithms with cancellations

ABSTRACT

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.

REFERENCES

• 1: Gagan Aggarwal , Jason D. Hartline, Knapsack auctions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1083-1092, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109677]
• 2: Moshe Babaioff , Michael Dinitz , Anupam Gupta , Nicole Immorlica , Kunal Talwar, Secretary problems: weights and discounts, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1245-1254, January 04-06, 2009, New York, New York
• 3: Babaioff, M., Hartline, J.D., and Kleinberg, R. Online algorithms with buyback. In Proc. 4th Workshop on Ad Auctions (2008).
• 4: Moshe Babaioff , Nicole Immorlica , David Kempe , Robert Kleinberg, A Knapsack Secretary Problem with Applications, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_2]
• 5: 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
• 6: Eyal Biyalogorsky , Ziv Carmon , Gila E. Fruchter , Eitan Gerstner, Research Note: Overselling with Opportunistic Cancellations, Marketing Science, v.18 n.4, p.605-610, April 1999 [doi>10.1287/mksc.18.4.605]
• 7: Christian Borgs , Jennifer Chayes , Nicole Immorlica , Kamal Jain , Omid Etesami , Mohammad Mahdian, Dynamics of bid optimization in online advertisement auctions, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242644]
• 8: Buchbinder, N., Jain, K., and Naor, J.S. Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA (2007), pp. 253--264.
• 9: Yunhong Zhou , Deeparnab Chakrabarty , Rajan Lukose, Budget constrained bidding in keyword auctions and online knapsack problems, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367747]
• 10: Constantin, F., Feldman, J., Muthukrishnan, S., and Pál, M. An online mechanism for ad slot reservations with cancellations. In Proc. 4th Workshop on Ad Auctions (2008).
• 11: Florin Constantin , Jon Feldman , S. Muthukrishnan , Martin Pál, An online mechanism for ad slot reservations with cancellations, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1265-1274, January 04-06, 2009, New York, New York
• 12: Nedialko B. Dimitrov , C. Greg Plaxton, Competitive Weighted Matching in Transversal Matroids, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_33]
• 13: Dynkin, E.B. Optimal choice of the stopping moment of a Markov process. Dokl. Akad. Nauk SSSR 150 (1963), 238--240.
• 14: 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]
• 15: Kazuo Iwama , Shiro Taketomi, Removable Online Knapsack Problems, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.293-305, July 08-13, 2002
• 16: Kazuo Iwama , Guochuan Zhang, Optimal Resource Augmentations for Online Knapsack, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_13]
• 17: Robert Kleinberg, A multiple-choice secretary algorithm with applications to online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 18: George S. Lueker, Average-case analysis of off-line and on-line knapsack problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.179-188, January 22-24, 1995, San Francisco, California, United States
• 19: A. Marchetti-Spaccamela , C. Vercellis, Stochastic on-line knapsack problems, Mathematical Programming: Series A and B, v.68 n.1, p.73-104, Jan. 2, 1995 [doi>10.1007/BF01585758]
• 20: J. Medhi, Stochastic models in queueing theory, Academic Press Professional, Inc., San Diego, CA, 1991
• 21: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and generalized online matching, Journal of the ACM (JACM), v.54 n.5, p.22-es, October 2007 [doi>10.1145/1284320.1284321]
• 22: John Noga , Veerawan Sarbua, An Online Partially Fractional Knapsack Problem, Proceedings of the 8th International Symposium on Parallel Architectures,Algorithms and Networks, p.108-112, December 07-09, 2005 [doi>10.1109/ISPAN.2005.19]
• 23: Sidney I. Resnick, Adventures in stochastic processes, Birkhauser Verlag, Basel, Switzerland, 1992
• 24: Paat Rusmevichientong , David P. Williamson, An adaptive algorithm for selecting profitable keywords for search-based advertising services, Proceedings of the 7th ACM conference on Electronic commerce, p.260-269, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134736]
• 25: Sandholm, T., and Lesser, V.R. Advantages of a leveled commitment contracting protocol. In AAAI/IAAI, Vol. 1 (1996), pp. 126--133.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Economics, Theory

Keywords:
costly decision revocation, knapsack, matroids, online algorithms, selling advertisements