[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3543507.3583427acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article
Open access

Learning to Bid in Contextual First Price Auctions✱

Published: 30 April 2023 Publication History

Abstract

In this work, we investigate the problem of how to bid in repeated contextual first price auctions for a single learner (the bidder). Concretely, at each time t, the learner receives a context and decides the bid based on historical information and xt. We assume that the maximum bid of all the others follows a linear model, i.e., mt = ⟨α0, xt⟩ + zt, where is unknown to the learner and zt is randomly sampled from a noise distribution with log-concave density. In this work, we consider both binary feedback (the learner can only observe whether she wins or not) and full information feedback (the learner can observe mt) models of the learner. For binary feedback, when the noise distribution is (partially) known, we propose a bidding algorithm that achieves at most regret, where Δ is a constant reserve in first price auctions.1 For the full information feedback with unknown noise distribution, we provide an algorithm that achieves regret at most . Our approach combines an estimator for log-concave density functions and the Maximum Likelihood Estimation (MLE) method to learn the noise distribution and linear weight α0 simultaneously. We complement our results with a lower bound result such that any bidding policy in a broad class must achieve regret at least, even when the learner receives the full information feedback and is known.

Supplemental Material

PDF File
Supplementary Material

References

[1]
Mohammad Akbarpour and Shengwu Li. 2020. Credible Auctions: A Trilemma. Econometrica 88, 2 (March 2020), 425–467.
[2]
Mark Yuying An. 1996. Log-concave Probability Distributions: Theory and Statistical Testing. Game Theory and Information 9611002. University Library of Munich, Germany.
[3]
Mark Bagnoli and Ted Bergstrom. 2005. Log-Concave Probability and Its Applications. Economic Theory 26, 2 (2005), 445–469.
[4]
Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. 2019. Contextual Bandits with Cross-Learning. In Advances in Neural Information Processing Systems 32. 9679–9688.
[5]
Santiago Balseiro, Christian Kroer, and Rachitesh Kumar. 2021. Contextual First-Price Auctions with Budgets. CoRR abs/2102.10476 (2021).
[6]
Ross Benes. 2017. How SSPs use deceptive price floors to squeeze ad buyers. https://digiday.com/marketing/ssps-use-deceptive-price-floors-squeeze-ad-buyers/. Accessed: 2020-01-29.
[7]
Dirk Bergemann and Johannes Hörner. 2018. Should First-Price Auctions Be Transparent¿American Economic Journal: Microeconomics 10, 3 (August 2018), 177–218.
[8]
Jason Bigler. 2019. Rolling out first price auctions to Google Ad Manager partners Digiday. https://www.blog.google/ products/admanager/rolling-out-first-price-auctions-google-ad-manager-partners. Accessed: 2020-01-27.
[9]
Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour. 2015. Regret Minimization for Reserve Prices in Second-Price Auctions. IEEE Transactions on Information Theory 61, 1 (2015), 549–564. https://doi.org/10.1109/TIT.2014.2365772
[10]
Yuyu Chen. 2017. Programmatic advertising is preparing for the first-price auction era. https://digiday.com/marketing/ programmatic- advertising-readying-first-price-auction-era. Accessed: 2020-01-29.
[11]
Maxime C. Cohen, Ilan Lobel, and Renato Paes Leme. 2020. Feature-Based Dynamic Pricing. Management Science 66, 11 (2020), 4921–4943.
[12]
Lutz Dümbgen and Kaspar Rufibach. 2009. Maximum likelihood estimation of a log-concave density and its distribution function: Basic properties and uniform consistency. Bernoulli 15, 1 (2009), 40 – 68.
[13]
Jianqing Fan, Yongyi Guo, and Mengxin Yu. 2021. Policy Optimization Using Semi-parametric Models for Dynamic Pricing.
[14]
Zhe Feng, Sébastien Lahaie, Jon Schneider, and Jinchao Ye. 2021. Reserve Price Optimization for First Price Auctions in Display Advertising. In Proceedings of the 38th International Conference on Machine Learning (ICML-21).
[15]
Zhe Feng, Chara Podimata, and Vasilis Syrgkanis. 2018. Learning to Bid Without Knowing Your Value. In Proceedings of the 2018 ACM Conference on Economics and Computation. 505–522.
[16]
Negin Golrezaei, Patrick Jaillet, and Jason Cheuk Nam Liang. 2019. Incentive-aware Contextual Pricing with Non-parametric Market Noise. arxiv:1911.03508 [cs.LG]
[17]
Google. 2023. Process the Request. https://developers.google.com/authorized-buyers/rtb/request-guide. Accessed: 2023-02-10.
[18]
Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman. 2020. Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions. CoRR abs/2007.04568 (2020). arxiv:2007.04568
[19]
Yanjun Han, Zhengyuan Zhou, and Tsachy Weissman. 2020. Optimal No-regret Learning in Repeated First-price Auctions. CoRR abs/2003.09795 (2020). arxiv:2003.09795
[20]
Adel Javanmard and Hamid Nazerzadeh. 2018. Dynamic Pricing in High-dimensions. arxiv:1609.07574 [stat.ML]
[21]
V. Krishna. 2002. Auction Theory. Elsevier Science.
[22]
R. Paes Leme and J. Schneider. 2018. Contextual Search via Intrinsic Volumes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA, USA, 268–282.
[23]
Yiyun Luo, Will Wei Sun, and Yufeng Liu. 2021. Distribution-free Contextual Dynamic Pricing.
[24]
Jieming Mao, Renato Leme, and Jon Schneider. 2018. Contextual Pricing for Lipschitz Buyers. In Advances in Neural Information Processing Systems 31. 5643–5651.
[25]
Thomas Nedelec, Clément Calauzènes, Noureddine El Karoui, and Vianney Perchet. 2022. Learning in Repeated Auctions. Foundations and Trends® in Machine Learning 15, 3 (2022), 176–334. https://doi.org/10.1561/2200000077
[26]
Gali Noti and Vasilis Syrgkanis. 2021. Bid Prediction in Repeated Auctions with Learning. In Proceedings of the Web Conference 2021 (Ljubljana, Slovenia) (WWW ’21). Association for Computing Machinery, New York, NY, USA, 3953–3964.
[27]
Hanzhao Wang, Kalyan Talluri, and Xiaocheng Li. 2021. On Dynamic Pricing with Covariates.
[28]
Zihe Wang, Weiran Shen, and Song Zuo. 2020. Bayesian Nash Equilibrium in First-Price Auction with Discrete Value Distributions. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems(AAMAS ’20). 1458–1466.
[29]
Jonathan Weed, Vianney Perchet, and Philippe Rigollet. 2016. Online learning in repeated auctions. In 29th Annual Conference on Learning Theory. 1562–1583.
[30]
Jianyu Xu and Yu-Xiang Wang. 2022. Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event(Proceedings of Machine Learning Research, Vol. 151), Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (Eds.). PMLR, 9643–9662.
[31]
Jianyu Xu and Yu-Xiang Wang. 2021. Logarithmic Regret in Feature-based Dynamic Pricing. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.). Vol. 34. Curran Associates, Inc., 13898–13910. https://proceedings.neurips.cc/paper/2021/file/742141ceda6b8f6786609d31c8ef129f-Paper.pdf

Cited By

View all
  • (2024)Strategizing against No-Regret Learners in First-Price AuctionsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673613(894-921)Online publication date: 8-Jul-2024

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
WWW '23: Proceedings of the ACM Web Conference 2023
April 2023
4293 pages
ISBN:9781450394161
DOI:10.1145/3543507
This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 2023

Check for updates

Author Tags

  1. Contextual First Price Auctions
  2. Learning to Bid

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Data Availability

Conference

WWW '23
Sponsor:
WWW '23: The ACM Web Conference 2023
April 30 - May 4, 2023
TX, Austin, USA

Acceptance Rates

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

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)349
  • Downloads (Last 6 weeks)52
Reflects downloads up to 19 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Strategizing against No-Regret Learners in First-Price AuctionsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673613(894-921)Online publication date: 8-Jul-2024

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

HTML Format

View this article in HTML Format.

HTML Format

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media