Algorithm for stochastic multiple-choice knapsack problem and application to keywords bidding

ABSTRACT

We model budget-constrained keyword bidding in sponsored search auctions as a stochastic multiple-choice knapsack problem (S-MCKP) and design an algorithm to solve S-MCKP and the corresponding bidding optimization problem. Our algorithm selects items online based on a threshold function which can be built/updated using historical data. Our algorithm achieved about 99% performance compared to the offline optimum when applied to a real bidding dataset. With synthetic dataset and iid item-sets, its performance ratio against the offline optimum converges to one empirically with increasing number of periods.

REFERENCES

• 1: Zoë Abrams, Revenue maximization when bidders have budgets, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1074-1082, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109676]
• 2: Zoe Abrams , Ofer Mendelevitch , John Tomlin, Optimal delivery of sponsored search advertisements subject to budget constraints, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250950]
• 3: 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]
• 4: N. Buchbinder, K. Jain, and J. S. Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proc. ESA, pages 253--264, 2007.
• 5: H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004.
• 6: George S. Lueker, Average-case analysis of off-line and on-line knapsack problems, Journal of Algorithms, v.29 n.2, p.277-305, Nov. 1998 [doi>10.1006/jagm.1998.0954]
• 7: S. Muthukrishnan, M. Pál, and Z. Svitkina. Stochastic models for budget optimization in search-based advertising. In Proc. WINE, LNCS 4858, pages 131--142, 2007.
• 8: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

General Terms:
Algorithms, Economics

Keywords:
keyword bidding, multiple-choice knapsack problem, sponsored search auction, stochastic optimization