poster

Budget constrained bidding in keyword auctions and online knapsack problems

Authors:

Yunhong Zhou,

Deeparnab Chakrabarty,

Rajan LukoseAuthors Info & Claims

WWW '08: Proceedings of the 17th international conference on World Wide Web

Pages 1243 - 1244

https://doi.org/10.1145/1367497.1367747

Published: 21 April 2008 Publication History

Get Access

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 click-through-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, available until Febuary 2007. http://uv.bidtool.overture.com/d/search/tools/bidtool

Google Scholar

[2]

Awerbuch, Y. Azar, and S. A. Plotkin. Throughput- competitive on-line routing. In FOCS, pages 32--40, 1993.

Digital Library

Google Scholar

[3]

Buchbinder, K. Jain, and J. S. Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proc. ESA, pages 253--264, 2007.

Digital Library

Google Scholar

[4]

Marchetti-Spaccamela and C. Vercellis. Stochastic on-line knapsack problems. Math. Programming, 68:73--104, 1995.

Digital Library

Google Scholar

[5]

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

Digital Library

Google Scholar

[6]

Zhou, D. Chakrabarty, and R. Lukose. Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems. HP Labs tech report HPL-2008--9, 2008.

Google Scholar

Cited By

View all

Leng SGuo YZhang LHao FCao XLi FKou W(2024)Online and Collaboratively Mitigating Multi-Vector DDoS Attacks for Cloud-Edge ComputingICC 2024 - IEEE International Conference on Communications10.1109/ICC51166.2024.10623052(1394-1399)Online publication date: 9-Jun-2024
https://doi.org/10.1109/ICC51166.2024.10623052
Bai MCardonha C(2023)Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear UtilitiesSSRN Electronic Journal10.2139/ssrn.4350988Online publication date: 2023
https://doi.org/10.2139/ssrn.4350988
Gong ZNiu LZhao YXu MZhang HZheng ZZhang ZBai RYu CXu JZheng BWu FFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)MEBS: Multi-task End-to-end Bid Shading for Multi-slot Display AdvertisingProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3615486(4588-4594)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3615486
Show More Cited By

Index Terms

Budget constrained bidding in keyword auctions and online knapsack problems
1. Mathematics of computing
  1. Mathematical software

Recommendations

Correcting vindictive bidding behaviors in sponsored search auctions

In this study, we aim to develop a pricing mechanism that reduces the effects resulted by vindictive advertisers who bid on sponsored search auctions run by search engine providers. In particular, we aim to ensure payment fairness and price stability in ...
Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems
WINE '08: Proceedings of the 4th International Workshop on Internet and Network Economics

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) ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

WWW '08: Proceedings of the 17th international conference on World Wide Web

April 2008

1326 pages

ISBN:9781605580852

DOI:10.1145/1367497

General Chairs:
Jinpeng Huai
Beihang University, China
,
Robin Chen
AT&T Labs, USA
,
Hsiao-Wuen Hon
Microsoft Research Asia, China
,
Yunhao Liu
HK University of Science and Technology, Hong Kong
,
Program Chairs:
Wei-Ying Ma
Microsoft Research Asia, China
,
Andrew Tomkins
Yahoo! Research, USA
,
Xiaodong Zhang
The Ohio State University, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 April 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

WWW '08

Sponsor:

WWW '08: The 17th International World Wide Web Conference

April 21 - 25, 2008

Beijing, China

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
576
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)13

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Leng SGuo YZhang LHao FCao XLi FKou W(2024)Online and Collaboratively Mitigating Multi-Vector DDoS Attacks for Cloud-Edge ComputingICC 2024 - IEEE International Conference on Communications10.1109/ICC51166.2024.10623052(1394-1399)Online publication date: 9-Jun-2024
https://doi.org/10.1109/ICC51166.2024.10623052
Bai MCardonha C(2023)Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear UtilitiesSSRN Electronic Journal10.2139/ssrn.4350988Online publication date: 2023
https://doi.org/10.2139/ssrn.4350988
Gong ZNiu LZhao YXu MZhang HZheng ZZhang ZBai RYu CXu JZheng BWu FFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)MEBS: Multi-task End-to-end Bid Shading for Multi-slot Display AdvertisingProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3615486(4588-4594)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3615486
Li WXiang LGuo BLi ZWang X(2023)DPlanner: A Privacy Budgeting System for UtilityIEEE Transactions on Information Forensics and Security10.1109/TIFS.2022.323178618(1196-1210)Online publication date: 2023
https://doi.org/10.1109/TIFS.2022.3231786
Cao YSun BTsang D(2023)Online Network Utility Maximization: Algorithm, Competitive Analysis, and ApplicationsIEEE Transactions on Control of Network Systems10.1109/TCNS.2022.319922110:1(274-284)Online publication date: Mar-2023
https://doi.org/10.1109/TCNS.2022.3199221
Tu CBai RAickelin UZhang YDu H(2023)A deep reinforcement learning hyper-heuristic with feature fusion for online packing problemsExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.120568230:COnline publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.120568
Song QLin PMa HWu Y(2021)Explaining Missing Data in Graphs: A Constraint-based Approach2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00131(1476-1487)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00131
Tan XSun BLeon-Garcia AWu YTsang D(2020)Mechanism Design for Online Resource AllocationACM SIGMETRICS Performance Evaluation Review10.1145/3410048.341005548:1(11-12)Online publication date: 9-Jul-2020
https://dl.acm.org/doi/10.1145/3410048.3410055
Tan XSun BLeon-Garcia AWu YTsang DYeh EMarkopoulou ATay Y(2020)Mechanism Design for Online Resource AllocationAbstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems10.1145/3393691.3394201(11-12)Online publication date: 8-Jun-2020
https://dl.acm.org/doi/10.1145/3393691.3394201
Bhattacharjee RBanerjee SSinha A(2020)Fundamental Limits on the Regret of Online Network-CachingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33921434:2(1-31)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3392143
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

Correcting vindictive bidding behaviors in sponsored search auctions

Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems

Vindictive bidding in keyword auctions