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

Balseiro SBhawalkar KFeng ZLu HMirrokni VSivan BWang DSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)A field guide for pacing budget and ROS constraintsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692175(2607-2638)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692175
Xiao LZhang XWu DHu MZhou YYu S(2024)History-Aware Privacy Budget Allocation for Model Training on Evolving Data-Sharing PlatformsIEEE Transactions on Services Computing10.1109/TSC.2024.3451187(1-15)Online publication date: 2024
https://doi.org/10.1109/TSC.2024.3451187
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
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

59
Total Citations
View Citations
585
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)3

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Balseiro SBhawalkar KFeng ZLu HMirrokni VSivan BWang DSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)A field guide for pacing budget and ROS constraintsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692175(2607-2638)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692175
Xiao LZhang XWu DHu MZhou YYu S(2024)History-Aware Privacy Budget Allocation for Model Training on Evolving Data-Sharing PlatformsIEEE Transactions on Services Computing10.1109/TSC.2024.3451187(1-15)Online publication date: 2024
https://doi.org/10.1109/TSC.2024.3451187
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
Kumar ABishnu P(2024)Identification of products for campaigning with budget constraintInternational Journal of Information Technology10.1007/s41870-024-02319-617:2(727-748)Online publication date: 8-Dec-2024
https://doi.org/10.1007/s41870-024-02319-6
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
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Correcting vindictive bidding behaviors in sponsored search auctions