Article

Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems

Authors:

Yunhong Zhou,

Deeparnab Chakrabarty,

Rajan LukoseAuthors Info & Claims

WINE '08: Proceedings of the 4th International Workshop on Internet and Network Economics

Pages 566 - 576

https://doi.org/10.1007/978-3-540-92185-1_63

Published: 17 December 2008 Publication History

Abstract

We consider the budget-constrained bidding optimization problem for sponsored search auctions, and model it as an online (multiple-choice) knapsack problem . We design both deterministic and randomized algorithms for the online (multiple-choice) knapsack problems achieving a provably optimal competitive ratio. This translates back to fully automatic bidding strategies maximizing either profit or revenue for the budget-constrained advertiser. Our bidding strategy for revenue maximization is oblivious (i.e., without knowledge) of other bidders' prices and/or clickthrough-rates for those positions. We evaluate our bidding algorithms using both synthetic data and real bidding data gathered manually, and also discuss a sniping heuristic that strictly improves bidding performance. With sniping and parameter tuning enabled, our bidding algorithms can achieve a performance ratio above 90% against the optimum by the omniscient bidder.

References

[1]

Overture view bids (Febuary 2007), http://uv.bidtool.overture.com/d/search/tools/bidtool

Google Scholar

[2]

Awerbuch, B., Azar, Y., Plotkin, S.A.: Throughput-competitive on-line routing. In: FOCS, pp. 32-40 (1993)

Crossref

Google Scholar

[3]

Buchbinder, N., Jain, K., Naor, J.S.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 253-264. Springer, Heidelberg (2007)

Crossref

Google Scholar

[4]

Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Mathematical Programming 68, 73-104 (1995)

Crossref

Google Scholar

[5]

Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized on-line matching. In: Proc. FOCS, pp. 264-273 (2005)

Crossref

Google Scholar

[6]

Yao, A.C.-C.: Probabilistic computations: towards a unified measure of complexity. In: Proc. 18th IEEE FOCS, pp. 222-227 (1977)

Crossref

Google Scholar

Cited By

View all

Gourvès LPagourtzis A(2024)Removable Online Knapsack with Bounded Size ItemsSOFSEM 2024: Theory and Practice of Computer Science10.1007/978-3-031-52113-3_20(283-296)Online publication date: 19-Feb-2024
https://dl.acm.org/doi/10.1007/978-3-031-52113-3_20
Balseiro SKumar RMirrokni VSivan BWang DKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Robust budget pacing with a single sampleProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618478(1636-1659)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618478
Jalota DPaccagnan DSchiffer MPavone M(2023)Online Routing Over Parallel NetworksINFORMS Journal on Computing10.1287/ijoc.2023.127535:3(560-577)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1287/ijoc.2023.1275
Show More Cited By

Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Budget constrained bidding in keyword auctions and online knapsack problems
WWW '08: Proceedings of the 17th international conference on World Wide Web

We consider the budget-constrained bidding optimization problem for sponsored search auctions, and model it as an online (multiple-choice) knapsack problem. We design both deterministic and randomized algorithms for the online (multiple-choice) knapsack ...
Vindictive bidding in keyword auctions
ICEC '07: Proceedings of the ninth international conference on Electronic commerce

We study vindictive bidding, a strategic bidding behavior in keyword auctions where a bidder forces his competitor to pay more without affecting his own payment. We show that most Nash equilibria (NE) are vulnerable to vindictive bidding and are thus ...
Optimal bidding in stochastic budget constrained slot auctions
EC '08: Proceedings of the 9th ACM conference on Electronic commerce

We study optimal bidding strategies for advertisers in budget constrained multi-item multi-slot auctions. The classic application context is that of bidding in sponsored search auctions. In general, these auctions are run as variants of second-price ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

WINE '08: Proceedings of the 4th International Workshop on Internet and Network Economics

December 2008

731 pages

ISBN:9783540921844

Editors:
Christos Papadimitriou
Computer Science Division, University of California at Berkeley, Berkeley, USA
,
Shuzhong Zhang
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong,

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 December 2008

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gourvès LPagourtzis A(2024)Removable Online Knapsack with Bounded Size ItemsSOFSEM 2024: Theory and Practice of Computer Science10.1007/978-3-031-52113-3_20(283-296)Online publication date: 19-Feb-2024
https://dl.acm.org/doi/10.1007/978-3-031-52113-3_20
Balseiro SKumar RMirrokni VSivan BWang DKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Robust budget pacing with a single sampleProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618478(1636-1659)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618478
Jalota DPaccagnan DSchiffer MPavone M(2023)Online Routing Over Parallel NetworksINFORMS Journal on Computing10.1287/ijoc.2023.127535:3(560-577)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1287/ijoc.2023.1275
Ou WChen BDai XZhang WLiu WTang RYu Y(2023)A Survey on Bid Optimization in Real-Time Bidding Display AdvertisingACM Transactions on Knowledge Discovery from Data10.1145/3628603Online publication date: 18-Oct-2023
https://dl.acm.org/doi/10.1145/3628603
Moraes FManuel Proença HKornilova AAlbert JGoldenberg DFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Uplift Modeling: From Causal Inference to PersonalizationProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3615298(5212-5215)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3615298
Wu GSong GLv XLuo SShi CZhu HSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)DNet: Distributional Network for Distributional Individualized Treatment EffectsProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599809(5215-5224)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599809
Bostandoost RSun BJoe-Wong CHajiesmaili M(2023)Near-optimal Online Algorithms for Joint Pricing and Scheduling in EV Charging NetworksProceedings of the 14th ACM International Conference on Future Energy Systems10.1145/3575813.3576878(72-83)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3575813.3576878
Hajiaghayi MKhani MPanigrahi DSpringer MKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Online algorithms for the santa claus problemProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602498(30732-30743)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602498
Sun BYang LHajiesmaili MWierman ALui JTowsley DTsang D(2022)The Online Knapsack Problem with DeparturesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35706186:3(1-32)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1145/3570618
Yang LZeynali AHajiesmaili MSitaraman RTowsley D(2022)Competitive Algorithms for Online Multidimensional Knapsack ProblemsACM SIGMETRICS Performance Evaluation Review10.1145/3547353.352262750:1(87-88)Online publication date: 7-Jul-2022
https://dl.acm.org/doi/10.1145/3547353.3522627
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations