IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v49y2024i4p2109-2135.html

The Complexity of Pacing for Second-Price Auctions

Author

Listed:
  • Xi Chen

    (Columbia University, New York, New York 10027)

  • Christian Kroer

    (Columbia University, New York, New York 10027)

  • Rachitesh Kumar

    (Columbia University, New York, New York 10027)

Abstract

Budget constraints are ubiquitous in online advertisement auctions. To manage these constraints and smooth out the expenditure across auctions, the bidders (or the platform on behalf of them) often employ pacing: each bidder is assigned a pacing multiplier between zero and one, and her bid on each item is multiplicatively scaled down by the pacing multiplier. This naturally gives rise to a game in which each bidder strategically selects a multiplier. The appropriate notion of equilibrium in this game is known as a pacing equilibrium. In this work, we show that the problem of finding an approximate pacing equilibrium is PPAD-complete for second-price auctions. This resolves an open question of Conitzer et al. [Conitzer V, Kroer C, Sodomka E, Stier-Moses NE (2022a) Multiplicative pacing equilibria in auction markets. Oper. Res . 70(2):963–989]. As a consequence of our hardness result, we show that the tâtonnement-style budget-management dynamics introduced by Borgs et al. [Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Proc. 16th Internat. Conf. World Wide Web (ACM, New York), 531–540] are unlikely to converge efficiently for repeated second-price auctions. This disproves a conjecture by Borgs et al. [Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Proc. 16th Internat. Conf. World Wide Web (ACM, New York), 531–540], under the assumption that the complexity class PPAD is not equal to P. Our hardness result also implies the existence of a refinement of supply-aware market equilibria which is hard to compute with simple linear utilities.

Suggested Citation

  • Xi Chen & Christian Kroer & Rachitesh Kumar, 2024. "The Complexity of Pacing for Second-Price Auctions," Mathematics of Operations Research, INFORMS, vol. 49(4), pages 2109-2135, November.
    • Handle: RePEc:inm:ormoor:v:49:y:2024:i:4:p:2109-2135
    DOI: 10.1287/moor.2022.0009
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.0009
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.0009?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    2. Santiago Balseiro & Anthony Kim & Mohammad Mahdian & Vahab Mirrokni, 2021. "Budget-Management Strategies in Repeated Auctions," Operations Research, INFORMS, vol. 69(3), pages 859-876, May.
    3. Santiago R. Balseiro & Omar Besbes & Gabriel Y. Weintraub, 2015. "Repeated Auctions with Budgets in Ad Exchanges: Approximations and Design," Management Science, INFORMS, vol. 61(4), pages 864-884, April.
    4. Eric Budish, 2011. "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1061-1103.
    5. Santiago R. Balseiro & Yonatan Gur, 2019. "Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium," Management Science, INFORMS, vol. 65(9), pages 3952-3968, September.
    6. Ashlagi Itai & Braverman Mark & Hassidim Avinatan & Lavi Ron & Tennenholtz Moshe, 2010. "Position Auctions with Budgets: Existence and Uniqueness," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 10(1), pages 1-32, May.
    7. Dobzinski, Shahar & Lavi, Ron & Nisan, Noam, 2012. "Multi-unit auctions with budget limits," Games and Economic Behavior, Elsevier, vol. 74(2), pages 486-503.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Vincent Conitzer & Christian Kroer & Eric Sodomka & Nicolas E. Stier-Moses, 2022. "Multiplicative Pacing Equilibria in Auction Markets," Operations Research, INFORMS, vol. 70(2), pages 963-989, March.
    2. Luofeng Liao & Christian Kroer, 2024. "Statistical Inference and A/B Testing in Fisher Markets and Paced Auctions," Papers 2406.15522, arXiv.org, revised Mar 2025.
    3. Vincent Conitzer & Christian Kroer & Debmalya Panigrahi & Okke Schrijvers & Nicolas E. Stier-Moses & Eric Sodomka & Christopher A. Wilkens, 2022. "Pacing Equilibrium in First Price Auction Markets," Management Science, INFORMS, vol. 68(12), pages 8515-8535, December.
    4. Kotowski, Maciej H., 2020. "First-price auctions with budget constraints," Theoretical Economics, Econometric Society, vol. 15(1), January.
    5. Yuan Gao & Christian Kroer & Alex Peysakhovich, 2021. "Online Market Equilibrium with Application to Fair Division," Papers 2103.12936, arXiv.org, revised Oct 2021.
    6. Luofeng Liao & Christian Kroer & Sergei Leonenkov & Okke Schrijvers & Liang Shi & Nicolas Stier-Moses & Congshan Zhang, 2024. "Interference Among First-Price Pacing Equilibria: A Bias and Variance Analysis," Papers 2402.07322, arXiv.org, revised Jan 2025.
    7. Santiago Balseiro & Christian Kroer & Rachitesh Kumar, 2023. "Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees," Management Science, INFORMS, vol. 69(11), pages 6837-6854, November.
    8. Artur Gorokh & Siddhartha Banerjee & Krishnamurthy Iyer, 2021. "From Monetary to Nonmonetary Mechanism Design via Artificial Currencies," Mathematics of Operations Research, INFORMS, vol. 46(3), pages 835-855, August.
    9. Condorelli, Daniele, 2013. "Market and non-market mechanisms for the optimal allocation of scarce resources," Games and Economic Behavior, Elsevier, vol. 82(C), pages 582-591.
    10. Bergemann, Dirk & Bonatti, Alessandro & Wu, Nicholas, 2025. "Bidding with budgets: Data-driven bid algorithms in digital advertising," International Journal of Industrial Organization, Elsevier, vol. 102(C).
    11. Erdmann, Anett & Arilla, Ramón & Ponzoa, José M., 2022. "Search engine optimization: The long-term strategy of keyword choice," Journal of Business Research, Elsevier, vol. 144(C), pages 650-662.
    12. Piotr Dworczak & Scott Duke Kominers & Mohammad Akbarpour, 2021. "Redistribution Through Markets," Econometrica, Econometric Society, vol. 89(4), pages 1665-1698, July.
    13. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object auction design: Ex-post revenue maximization with no wastage," Discussion Papers 17-03, Indian Statistical Institute, Delhi.
    14. Narendra Agrawal & Sami Najafi-Asadolahi & Stephen A. Smith, 2023. "A Markov Decision Model for Managing Display-Advertising Campaigns," Manufacturing & Service Operations Management, INFORMS, vol. 25(2), pages 489-507, March.
    15. Giannis Fikioris & Éva Tardos, 2025. "Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions," Mathematics of Operations Research, INFORMS, vol. 50(2), pages 1233-1249, May.
    16. Mengzhou Zhuang & Eric (Er) Fang & Jongkuk Lee & Xiaoling Li, 2021. "The Effects of Price Rank on Clicks and Conversions in Product List Advertising on Online Retail Platforms," Information Systems Research, INFORMS, vol. 32(4), pages 1412-1430, December.
    17. Hana Choi & Carl F. Mela & Santiago R. Balseiro & Adam Leary, 2020. "Online Display Advertising Markets: A Literature Review and Future Directions," Information Systems Research, INFORMS, vol. 31(2), pages 556-575, June.
    18. Rica Gonen & Anat Lerner, 2013. "The Incompatibility of Pareto Optimality and Dominant-Strategy Incentive Compatibility in Sufficiently-Anonymous Budget-Constrained Quasilinear Settings," Games, MDPI, vol. 4(4), pages 1-21, November.
    19. Zikun Ye & Dennis J. Zhang & Heng Zhang & Renyu Zhang & Xin Chen & Zhiwei Xu, 2023. "Cold Start to Improve Market Thickness on Online Advertising Platforms: Data-Driven Algorithms and Field Experiments," Management Science, INFORMS, vol. 69(7), pages 3838-3860, July.
    20. Mohammad Zia & Ram C. Rao, 2019. "Search Advertising: Budget Allocation Across Search Engines," Marketing Science, INFORMS, vol. 38(6), pages 1023-1037, November.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:49:y:2024:i:4:p:2109-2135. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.