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

Strategizing against No-Regret Learners in First-Price Auctions

Published: 17 December 2024 Publication History

Abstract

We study repeated first-price auctions and general repeated Bayesian games between two players, where one player, the learner, employs a no-regret learning algorithm, and the other player, the optimizer, knowing the learner's algorithm, strategizes to maximize its own utility. For a commonly used class of no-regret learning algorithms called mean-based algorithms, we show that (i) in standard (i.e., full-information) first-price auctions, the optimizer cannot get more than the Stackelberg utility - a standard benchmark in the literature, but (ii) in Bayesian first-price auctions, there are instances where the optimizer can achieve much higher than the Stackelberg utility.
On the other hand, Mansour et al. (2022) showed that a more sophisticated class of algorithms called no-polytope-swap-regret algorithms are sufficient to cap the optimizer's utility at the Stackelberg utility in any repeated Bayesian game (including Bayesian first-price auctions), and they pose the open question whether no-polytope-swap-regret algorithms are necessary to cap the optimizer's utility. For general Bayesian games, under a reasonable and necessary condition, we prove that no-polytope-swap-regret algorithms are indeed necessary to cap the optimizer's utility and thus answer their open question. For Bayesian first-price auctions, we give a simple improvement of the standard algorithm for minimizing the polytope swap regret by exploiting the structure of Bayesian first-price auctions.

References

[1]
Eshwar Ram Arunachaleswaran, Natalie Collina, and Jon Schneider. 2024. Pareto-Optimal Algorithms for Learning in Games. arXiv preprint arXiv:2402.09549 (2024).
[2]
Ashwinkumar Badanidiyuru, Zhe Feng, and Guru Guruganesh. 2023. Learning to Bid in Contextual First Price Auctions. In Proceedings of the ACM Web Conference 2023. 3489--3497.
[3]
Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. 2019. Contextual bandits with cross-learning. Advances in Neural Information Processing Systems 32 (2019).
[4]
Avrim Blum and Yishay Mansour. 2007. From external to internal regret. Journal of Machine Learning Research 8, 6 (2007).
[5]
Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg. 2018. Selling to a no-regret buyer. In Proceedings of the 2018 ACM Conference on Economics and Computation. 523--538.
[6]
Linda Cai, S Matthew Weinberg, Evan Wildenhain, and Shirley Zhang. 2023. Selling to multiple no-regret buyers. In International Conference on Web and Internet Economics. Springer, 113--129.
[7]
Yuan Deng, Jon Schneider, and Balasubramanian Sivan. 2019. Strategizing against no-regret learners. Advances in neural information processing systems 32 (2019).
[8]
Stylianos Despotakis, Ramamoorthi Ravi, and Amin Sayedi. 2021. First-price auctions in online display advertising. Journal of Marketing Research 58, 5 (2021), 888--907.
[9]
Zhe Feng, Guru Guruganesh, Christopher Liaw, Aranyak Mehta, and Abhishek Sethi. 2021. Convergence analysis of no-regret bidding algorithms in repeated auctions. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 5399--5406.
[10]
Guru Guruganesh, Yoav Kolumbus, Jon Schneider, Inbal Talgam-Cohen, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Joshua R Wang, and S Matthew Weinberg. 2024. Contracting with a learning agent. arXiv preprint arXiv:2401.16198 (2024).
[11]
Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman. 2020b. Learning to bid optimally and efficiently in adversarial first-price auctions. arXiv preprint arXiv:2007.04568 (2020).
[12]
Yanjun Han, Zhengyuan Zhou, and Tsachy Weissman. 2020a. Optimal no-regret learning in repeated first-price auctions. arXiv preprint arXiv:2003.09795 (2020).
[13]
Yoav Kolumbus and Noam Nisan. 2022a. Auctions between regret-minimizing agents. In Proceedings of the ACM Web Conference 2022. 100--111.
[14]
Yoav Kolumbus and Noam Nisan. 2022b. How and why to manipulate your own agent: On the incentives of users of learning agents. Advances in Neural Information Processing Systems 35 (2022), 28080--28094.
[15]
Rachitesh Kumar, Jon Schneider, and Balasubramanian Sivan. 2024. Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions. arXiv preprint arXiv:2402.07363 (2024).
[16]
Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. 2022. Strategizing against Learners in Bayesian Games. In Conference on Learning Theory. PMLR, 5221--5252.
[17]
Denis Nekipelov, Vasilis Syrgkanis, and Eva Tardos. 2015. Econometrics for learning agents. In Proceedings of the sixteenth acm conference on economics and computation. 1--18.
[18]
Maurice Sion. 1958. On general minimax theorems. Pacific Journal of mathematics 8, 1 (1958), 171--176.
[19]
N. F. Taussig. 2017. Mathematics Stack Exchange. https://math.stackexchange.com/questions/2231965/count-number-of-increasing-functions-nondecreasing-functions-f-1-2-3-ld. Accessed: 2023-05-13.
[20]
Yunjian Xu and Katrina Ligett. 2018. Commitment in first-price auctions. Economic Theory 66, 2 (2018), 449--489.
[21]
Wei Zhang, Yanjun Han, Zhengyuan Zhou, Aaron Flores, and Tsachy Weissman. 2022. Leveraging the hints: Adaptive bidding in repeated first-price auctions. Advances in Neural Information Processing Systems 35 (2022), 21329--21341.

Index Terms

  1. Strategizing against No-Regret Learners in First-Price Auctions

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    EC '24: Proceedings of the 25th ACM Conference on Economics and Computation
    July 2024
    1340 pages
    ISBN:9798400707049
    DOI:10.1145/3670865
    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 the author(s) 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].

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 17 December 2024

    Check for updates

    Author Tags

    1. no-regret learning
    2. stackelberg utility
    3. bayesian games
    4. auctions

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    EC '24
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 664 of 2,389 submissions, 28%

    Upcoming Conference

    EC '25
    The 25th ACM Conference on Economics and Computation
    July 7 - 11, 2025
    Stanford , CA , USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 5
      Total Downloads
    • Downloads (Last 12 months)5
    • Downloads (Last 6 weeks)5
    Reflects downloads up to 19 Dec 2024

    Other Metrics

    Citations

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media