pith. sign in

arxiv: 2606.05108 · v1 · pith:L4NQSQ7Gnew · submitted 2026-06-03 · 💻 cs.GT

Gradient Dynamics in First-Price Auctions: Iterative Strategy Elimination via Cubic Potentials

Mete \c{S}eref Ahunbay , Weiqiang Zheng , Tao Lin This is my paper

Pith reviewed 2026-06-28 03:30 UTC · model grok-4.3

classification 💻 cs.GT
keywords first-price auctionsonline gradient ascentpotential functionsiterative strategy eliminationsecond-price auctionsno-regret learningauction efficiency
0
0 comments X

The pith

In discretized first-price auctions, buyers using online gradient ascent achieve the efficient second-price outcome in time average.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that when buyers in discretized first-price auctions with complete information adjust bids via online gradient ascent, their time-averaged bids produce an outcome nearly identical to the efficient allocation of a second-price auction. The argument develops a potential-function method showing that certain strategies receive zero weight in the long run and supplies conditions allowing this elimination to proceed iteratively. It further introduces cubic candidate potential functions that certify no regret against quadratic modifications of mixed strategies on the simplex. A reader would care because the result ties a simple, decentralized learning rule to a desirable market outcome without assuming full strategic sophistication.

Core claim

In discretized first-price auctions with complete information, if the buyers learn to bid with online gradient ascent, in time-average the outcome is almost the efficient outcome of the second-price auction. The proof rests on a potential-function argument that deduces certain strategies will not be played in time average and on a novel class of cubic candidate potential functions that classify quadratic strategy modifications on the probability simplex against which online gradient ascent incurs no regret.

What carries the argument

Cubic candidate potential functions that bound regret for quadratic strategy modifications on the probability simplex, enabling iterative application of the potential argument to eliminate unused strategies.

If this is right

  • Certain bidding strategies receive zero weight in the time-average play.
  • The iterative elimination procedure produces the efficient allocation.
  • The convergence holds specifically for online gradient ascent applied to the normal-form representation of the auction.
  • Time-average outcomes approximate those of the second-price auction without requiring players to reason about dominance directly.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same potential-function technique could be tested on other no-regret dynamics such as multiplicative-weights updates in auction games.
  • Whether the result survives removal of the discretization assumption remains open for continuous bid spaces.
  • The iterative elimination may connect to solvability concepts in broader classes of normal-form games beyond auctions.

Load-bearing premise

The sufficient conditions that allow the potential-function argument to be applied iteratively to eliminate strategies.

What would settle it

A simulation or calculation in a small discretized first-price auction instance showing that the time-average bids under online gradient ascent fail to match the efficient second-price allocation.

read the original abstract

We show that in discretised first-price auctions with complete information, if the buyers learn to bid with online gradient ascent, in time-average the outcome is (almost) the efficient outcome of the second-price auction. Our proof rests on two novel innovations in the analysis of online gradient ascent in normal-form games, which may be useful in a wider range of applications. First, we develop a potential-function-based argument for the analysis of gradient ascent in normal-form games, allowing us to deduce that certain strategies will not be played in time-average. We provide sufficient conditions which ensure this argument can be applied iteratively, resulting in a procedure reminiscent of iterative elimination of dominated strategies. Second, we develop a novel class of cubic "candidate potential functions", classifying a family of quadratic strategy modifications on the probability simplex against which online gradient ascent incurs no regret.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that in discretized first-price auctions with complete information, buyers using online gradient ascent converge in time-average to (almost) the efficient outcome of the second-price auction. The proof introduces two innovations: (i) a potential-function argument for gradient ascent in normal-form games that identifies strategies eliminated from time-average play, equipped with sufficient conditions allowing iterative application reminiscent of iterative elimination of dominated strategies, and (ii) a class of cubic candidate potential functions that certify no-regret against quadratic strategy modifications on the probability simplex.

Significance. If the central claim holds, the result links online learning dynamics directly to auction efficiency, showing that first-price auctions under gradient ascent can replicate second-price outcomes in time average. The potential-function tools and cubic potentials are presented as reusable analytic devices for normal-form games and may apply beyond auctions. The manuscript supplies machine-checkable elements via the explicit sufficient conditions and the classification of cubic potentials, which strengthens the assessment if the iterative application succeeds for the auction payoff structure.

major comments (2)
  1. [§4] §4 (sufficient conditions for iterative elimination): the claim that the potential-function argument applies iteratively to reach the second-price outcome requires that the stated conditions (e.g., sign patterns or dominance relations in payoff differences) are preserved after each elimination round. The first-price payoff matrix (winner pays own bid) does not automatically inherit these properties from the initial game, so it is necessary to verify that the conditions remain satisfied for the reduced strategy sets at every step; without this verification the procedure may terminate before all inefficient strategies are eliminated.
  2. [Theorem 3.2] Theorem 3.2 and the cubic-potential construction: the no-regret guarantee is shown for quadratic modifications, but the iterative elimination argument in the auction setting invokes these potentials on successively reduced simplices. It is unclear whether the cubic form remains a valid candidate potential after the first elimination round, because the support restriction changes the geometry of the strategy modifications; an explicit check or counter-example for the reduced game would be required to confirm the time-average claim.
minor comments (2)
  1. [§2] Notation for the discretized bid grid and the time-average measure should be introduced once in §2 and used consistently; several later sections redefine the same objects with slightly different symbols.
  2. [Figure 1] Figure 1 caption states that the plotted trajectories reach the second-price bid, but the axis labels and legend do not indicate whether the plotted quantity is the time-average or the instantaneous bid; this should be clarified.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the careful review and for highlighting these points on the iterative application of the potential argument and the cubic potentials. We address each major comment below. We will revise the manuscript to incorporate explicit verifications where needed.

read point-by-point responses

  1. Referee: [§4] §4 (sufficient conditions for iterative elimination): the claim that the potential-function argument applies iteratively to reach the second-price outcome requires that the stated conditions (e.g., sign patterns or dominance relations in payoff differences) are preserved after each elimination round. The first-price payoff matrix (winner pays own bid) does not automatically inherit these properties from the initial game, so it is necessary to verify that the conditions remain satisfied for the reduced strategy sets at every step; without this verification the procedure may terminate before all inefficient strategies are eliminated.

    Authors: We agree that preservation of the sufficient conditions must be verified explicitly for the first-price payoff structure. The manuscript states the general conditions and claims they suffice for iterative elimination, but does not include a step-by-step check on the reduced simplices induced by the auction payoffs. In the revision we will add this verification, using the explicit form of the first-price payoffs (winner pays own bid) to confirm that the required sign patterns on payoff differences persist after each round of elimination. This will be placed in an expanded §4. revision: yes

  2. Referee: [Theorem 3.2] Theorem 3.2 and the cubic-potential construction: the no-regret guarantee is shown for quadratic modifications, but the iterative elimination argument in the auction setting invokes these potentials on successively reduced simplices. It is unclear whether the cubic form remains a valid candidate potential after the first elimination round, because the support restriction changes the geometry of the strategy modifications; an explicit check or counter-example for the reduced game would be required to confirm the time-average claim.

    Authors: The cubic candidate potentials are constructed to certify no regret against quadratic modifications on the full simplex. When the support is restricted by prior elimination rounds, the geometry of admissible modifications changes, and the manuscript does not supply an explicit re-verification that the same cubic form remains valid on each reduced simplex. We will add this check in the revision (or, if the original cubic coefficients fail, derive adjusted coefficients that work on the restricted supports) so that the iterative argument is fully rigorous for the auction instance. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation uses novel potential functions applied to auction payoffs

full rationale

The paper's central claim follows from two explicitly constructed innovations: a potential-function argument with stated sufficient conditions for iterative elimination, and a new class of cubic candidate potentials. These are developed within the manuscript and applied to the first-price payoff matrix; no step reduces by definition to its own output, no fitted parameter is relabeled as a prediction, and no load-bearing premise rests solely on a self-citation chain. The sufficient conditions are part of the new argument rather than presupposed, making the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available; no free parameters, invented entities, or non-standard axioms are mentioned. The analysis appears to rest on standard properties of online gradient ascent and the probability simplex.

axioms (1)
  • standard math Standard regret bounds and geometry of the probability simplex for online gradient ascent in normal-form games
    The new potential-function argument and cubic potentials are extensions of these background facts.

pith-pipeline@v0.9.1-grok · 5678 in / 1240 out tokens · 35648 ms · 2026-06-28T03:30:57.114736+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

78 extracted references · 7 canonical work pages

  1. [1]

    Gagan Aggarwal, Ashwinkumar Badanidiyuru, Santiago R Balseiro, Kshipra Bhawalkar, Yuan Deng, Zhe Feng, Gagan Goel, Christopher Liaw, Haihao Lu, Mohammad Mahdian, et al. 2024. Auto-bidding and auctions in online advertising: A survey.ACM SIGecom Exchanges22, 1 (2024), 159–183

    2024

  2. [2]

    Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. 2019. Autobidding with constraints. InInternational Conference on Web and Internet Economics. Springer, 17–30

    2019

  3. [3]

    Mete S ¸eref Ahunbay. 2025. First-order (coarse) correlated equilibria in non-concave games. arXiv preprint arXiv:2403.18174(2025)

    arXiv 2025

  4. [4]

    Mete S ¸eref Ahunbay and Martin Bichler. 2025. Semicoarse Correlated Equilibria and LP-Based Guarantees for Gradient Dynamics in Normal-Form Games. InProceedings of the 26th ACM Conference on Economics and Computation. 91–91

    2025

  5. [5]

    Mete S ¸eref Ahunbay and Martin Bichler. 2024. On the Uniqueness of Bayesian Coarse Corre- lated Equilibria in Standard First-Price and All-Pay Auctions. arXiv:2401.01185 [cs.GT]

    arXiv 2024

  6. [6]

    Andrade, Rafael Frongillo, and Georgios Piliouras

    Gabriel P. Andrade, Rafael Frongillo, and Georgios Piliouras. 2021. Learning in Matrix Games can be Arbitrarily Complex. InProceedings of Thirty Fourth Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 134), Mikhail Belkin and Samory Kpotufe (Eds.). PMLR, 159–185.https://proceedings.mlr.press/v134/andrade21a.html

    2021

  7. [7]

    Galit Ashkenazi-Golan, Domenico Mergoni Cecchelli, Panayotis Mertikopoulos, Edward Plumb, Bassel Tarbush, and Yannick Viossat. 2026. Survival of Dominated Strategies Un- der No-Regret Dynamics.forthcoming / unpublished work(2026). 23

    2026

  8. [8]

    Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, and Brendan Lucier. 2020. Non-quasi-linear agents in quasi-linear mechanisms.arXiv preprint arXiv:2012.02893(2020)

    arXiv 2020

  9. [9]

    Ashwinkumar Badanidiyuru, Zhe Feng, and Guru Guruganesh. 2023. Learning to Bid in Contextual First Price Auctions. InProceedings of the ACM Web Conference 2023. 3489– 3497

    2023

  10. [10]

    Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider

  11. [11]

    Contextual Bandits with Cross-Learning.Mathematics of Operations Research48, 3 (2023), 1607–1629

    2023

  12. [12]

    Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. 2020. Dual mirror descent for online allocation problems. InInternational Conference on Machine Learning. PMLR, 613–628

    2020

  13. [13]

    Santiago R Balseiro and Yonatan Gur. 2019. Learning in repeated auctions with budgets: Regret minimization and equilibrium.Management Science65, 9 (2019), 3952–3968

    2019

  14. [14]

    Martin Bichler, Maximilian Fichtl, Stefan Heidekr¨ uger, Nils Kohring, and Paul Sutterer. 2021. Learning equilibria in symmetric auction games using artificial neural networks.Nature Ma- chine Intelligence3 (2021), 687–695. doi:10.1038/s42256-021-00365-4

    work page doi:10.1038/s42256-021-00365-4 2021

  15. [15]

    Martin Bichler, Maximilian Fichtl, and Matthias Oberlechner. 2023. Computing Bayes-Nash equilibrium in auction games via gradient dynamics.Operations Researchto appear (2023)

    2023

  16. [16]

    Martin Bichler, Davide Legacci, Panayotis Mertikopoulos, Matthias Oberlechner, and Bary Pradelski. 2025. Characterizing the Convergence of Game Dynamics via Potentialness.arXiv preprint arXiv:2503.16285(2025)

    arXiv 2025

  17. [17]

    Martin Bichler, Stephan B Lunowa, Matthias Oberlechner, Fabian R Pieroth, and Barbara Wohlmuth. 2023. On the Convergence of Learning Algorithms in Bayesian Auction Games. arXiv preprint arXiv:2311.15398(2023)

    arXiv 2023

  18. [18]

    Avrim Blum and Yishay Mansour. 2007. From external to internal regret.Journal of Machine Learning Research8, 6 (2007)

    2007

  19. [19]

    Christian Borgs, Jennifer Chayes, Nicole Immorlica, Kamal Jain, Omid Etesami, and Mo- hammad Mahdian. 2007. Dynamics of bid optimization in online advertisement auctions. In Proceedings of the 16th international conference on World Wide Web. 531–540

    2007

  20. [20]

    Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg. 2018. Selling to a no- regret buyer. InProceedings of the 2018 ACM Conference on Economics and Computation. 523–538

    2018

  21. [21]

    George W Brown. 1951. Iterative solution of games by fictitious play.Activity analysis of production and allocation13, 1 (1951), 374–376

    1951

  22. [22]

    Samuel Burer. 2009. On the copositive representation of binary and continuous nonconvex quadratic programs.Mathematical Programming120 (2009), 479–495. 24

    2009

  23. [23]

    Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. 2024. On Tractable Φ-Equilibria in Non-Concave Games.Advances in Neural Information Processing Systems37 (2024), 140366–140404

    2024

  24. [24]

    Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. 2025. Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games.arXiv preprint arXiv:2511.01852(2025)

    arXiv 2025

  25. [25]

    Yang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. 2026. Is Online Linear Optimiza- tion Sufficient for Strategic Robustness?arXiv preprint arXiv:2602.12253(2026)

    arXiv 2026

  26. [26]

    Nicol` o Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. 2024. The role of transparency in repeated first-price auctions with unknown valua- tions. InProceedings of the 56th Annual ACM Symposium on Theory of Computing. 225–236

    2024

  27. [27]

    2006.Prediction, learning, and games

    Nicolo Cesa-Bianchi and G´ abor Lugosi. 2006.Prediction, learning, and games. Cambridge university press

    2006

  28. [28]

    Xi Chen, Christian Kroer, and Rachitesh Kumar. 2024. The complexity of pacing for second- price auctions.Mathematics of Operations Research49, 4 (2024), 2109–2135

    2024

  29. [29]

    Xi Chen and Yuhao Li. 2025. Constant Inapproximability of Pacing Equilibria in Second-Price Auctions.arXiv preprint arXiv:2501.15295(2025)

    arXiv 2025

  30. [30]

    Xi Chen and Binghui Peng. 2023. Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules.arXiv preprint arXiv:2303.16388(2023)

    arXiv 2023

  31. [31]

    Yun Kuen Cheung and Georgios Piliouras. 2021. Vortices Instead of Equilibria in MinMax Op- timization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games. InProceedings of Thirty Second Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 99). PMLR, 807–834.https://proceedings.mlr.press/v99/cheung19a.html

    2021

  32. [32]

    Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas E Stier- Moses, Eric Sodomka, and Christopher A Wilkens. 2022. Pacing equilibrium in first price auction markets.Management Science68, 12 (2022), 8515–8535

    2022

  33. [33]

    Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E Stier-Moses. 2022. Multi- plicative pacing equilibria in auction markets.Operations Research70, 2 (2022), 963–989

    2022

  34. [34]

    Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. 2024. From external to swap regret 2.0: An efficient reduction for large action spaces. InProceedings of the 56th Annual ACM Symposium on Theory of Computing. 1216–1222

    2024

  35. [35]

    Xiaotie Deng, Xinyan Hu, Tao Lin, and Weiqiang Zheng. 2022. Nash convergence of mean- based learning algorithms in first price auctions. InProceedings of the ACM Web Conference

    2022

  36. [36]

    Yuan Deng, Yilin Li, Wei Tang, and Hanrui Zhang. 2025. No-Regret Online Autobidding Algorithms in First-price Auctions.arXiv preprint arXiv:2510.16869(2025). 25

    arXiv 2025

  37. [37]

    Yuan Deng, Mohammad Mahdian, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, and Song Zuo. 2024. Efficiency of the generalized second-price auction for value maximizers. InProceed- ings of the ACM Web Conference 2024. 46–56

    2024

  38. [38]

    Yuan Deng, Jon Schneider, and Balasubramanian Sivan. 2019. Strategizing against no-regret learners.Advances in neural information processing systems32 (2019)

    2019

  39. [39]

    Mirjam D¨ ur. 2010. Copositive Programming – a Survey. InRecent Advances in Optimization and its Applications in Engineering, Moritz Diehl, Francois Glineur, Elias Jarlebring, and Wim Michiels (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 3–20

    2010

  40. [40]

    Michal Feldman, Brendan Lucier, and Noam Nisan. 2016. Correlated and Coarse Equilibria of Single-Item Auctions. InWeb and Internet Economics, Yang Cai and Adrian Vetta (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 131–144

    2016

  41. [41]

    Zhe Feng, Swati Padmanabhan, and Di Wang. 2023. Online Bidding Algorithms for Return-on- Spend Constrained Advertisers. InProceedings of the ACM Web Conference 2023. 3550–3560

    2023

  42. [42]

    Giannis Fikioris and ´Eva Tardos. 2023. Liquid welfare guarantees for no-regret learning in sequential budgeted auctions. InProceedings of the 24th ACM Conference on Economics and Computation. 678–698

    2023

  43. [43]

    Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, and Charalampos Kokkalis. 2024. On the computation of equilibria in discrete first-price auctions. InProceedings of the 25th ACM Conference on Economics and Computation. 379–399

    2024

  44. [44]

    Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, and Charalampos Kokkalis. 2025. Equilibrium Computation in First-Price Auctions with Correlated Priors. InProceedings of the 26th ACM Conference on Economics and Computation. 7–33

    2025

  45. [45]

    Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos, and Diogo Po¸ cas. 2021. On the Complexity of Equilibrium Computation in First-Price Auctions. In Proceedings of the 22nd ACM Conference on Economics and Computation(Budapest, Hun- gary)(EC ’21). Association for Computing Machinery, New York, NY, USA, 454–476. doi:10.1145/346...

    work page doi:10.1145/3465456.3467627 2021

  46. [46]

    Dean P Foster and Rakesh V Vohra. 1997. Calibrated learning and correlated equilibrium. Games and Economic Behavior21, 589 (1997), 40–55

    1997

  47. [47]

    Yoav Freund and Robert E Schapire. 1997. A decision-theoretic generalization of on-line learning and an application to boosting.Journal of computer and system sciences55, 1 (1997), 119–139

    1997

  48. [48]

    Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. 2022. Bud- get pacing in repeated auctions: Regret and efficiency without convergence.arXiv preprint arXiv:2205.08674(2022)

    arXiv 2022

  49. [49]

    Rigel Galgana and Negin Golrezaei. 2025. Learning in repeated multiunit pay-as-bid auctions. Manufacturing & Service Operations Management27, 1 (2025), 200–229. 26

    2025

  50. [50]

    Amy Greenwald and Amir Jafari. 2003. A general class of no-regret learning algorithms and game-theoretic equilibria. InLearning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings. Springer, 2–12

    2003

  51. [51]

    Yanjun Han, Tsachy Weissman, and Zhengyuan Zhou. 2025. Optimal no-regret learning in repeated first-price auctions.Operations Research73, 1 (2025), 209–238

    2025

  52. [52]

    Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman. 2020. Learning to bid optimally and efficiently in adversarial first-price auctions.arXiv preprint arXiv:2007.04568(2020)

    arXiv 2020

  53. [53]

    Shlomit Hon-Snir, Dov Monderer, and Aner Sela. 1998. A learning approach to auctions. Journal of Economic Theory82, 1 (1998), 65–88

    1998

  54. [54]

    Yoav Kolumbus and Noam Nisan. 2022. Auctions between regret-minimizing agents. InPro- ceedings of the ACM Web Conference 2022. 100–111

    2022

  55. [55]

    Rachitesh Kumar, Jon Schneider, and Balasubramanian Sivan. 2024. Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions. InProceedings of the 25th ACM Conference on Economics and Computation. 893–893

    2024

  56. [56]

    Jean Bernard Lasserre. 2000. Optimisation globale et th´ eorie des moments.Comptes Rendus de l’Acad´ emie des Sciences - Series I - Mathematics331, 11 (2000), 929–934. doi:10.1016/ S0764-4442(00)01750-X

    2000

  57. [57]

    Christopher Liaw, Aranyak Mehta, and Wennan Zhu. 2024. Efficiency of non-truthful auctions in auto-bidding with budget constraints. InProceedings of the ACM Web Conference 2024. 223–234

    2024

  58. [58]

    Marx, and Peng Sun

    Giuseppe Lopomo, Leslie M. Marx, and Peng Sun. 2011. Bidder collusion at first-price auctions. Review of Economic Design15, 3 (2011), 177–211. doi:10.1007/s10058-010-0104-9

    work page doi:10.1007/s10058-010-0104-9 2011

  59. [59]

    Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, and Mengxiao Zhang. 2024. Autobid- ders with budget and roi constraints: Efficiency, regret, and pacing dynamics. InThe Thirty Seventh Annual Conference on Learning Theory. PMLR, 3642–3643

    2024

  60. [60]

    2018.Cycles in Adversarial Regularized Learning

    Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Pil- iouras. 2018.Cycles in Adversarial Regularized Learning. 2703–2717. arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.172 doi:10.1137/1. 9781611975031.172

    work page doi:10.1137/1.9781611975031.172 2018

  61. [61]

    Panayotis Mertikopoulos and Zhengyuan Zhou. 2019. Learning in Games with Continuous Action Sets and Unknown Payoff Functions.Math. Program.173, 1–2 (jan 2019), 465–507. doi:10.1007/s10107-018-1254-8

    work page doi:10.1007/s10107-018-1254-8 2019

  62. [62]

    2022.Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics

    Jason Milionis, Christos Papadimitriou, Georgios Piliouras, and Kelly Spendlove. 2022.Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics. doi:10. 48550/ARXIV.2203.14129 27

    arXiv 2022

  63. [63]

    2012.Projected dynamical systems and variational inequal- ities with applications

    Anna Nagurney and Ding Zhang. 2012.Projected dynamical systems and variational inequal- ities with applications. Vol. 2. Springer Science & Business Media

    2012

  64. [64]

    John F. Nash. 1950. Equilibrium points inn-person games.Pro- ceedings of the National Academy of Sciences36, 1 (1950), 48–49. arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.36.1.48 doi:10.1073/pnas.36.1.48

    work page doi:10.1073/pnas.36.1.48 1950

  65. [65]

    Christos Papadimitriou and Georgios Piliouras. 2019. Game Dynamics as the Meaning of a Game.SIGecom Exch.16, 2 (May 2019), 53–63. doi:10.1145/3331041.3331048

    work page doi:10.1145/3331041.3331048 2019

  66. [66]

    2000.Structured Semidenite Programs and Semialgebraic Geometry Methods in Robustness and Optimization

    Pablo Parrilo. 2000.Structured Semidenite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. Ph. D. Dissertation

    2000

  67. [67]

    Binghui Peng and Aviad Rubinstein. 2024. Fast swap regret minimization and applications to approximate correlated equilibria. InProceedings of the 56th Annual ACM Symposium on Theory of Computing. 1223–1234

    2024

  68. [68]

    Julia Robinson. 1951. An iterative method of solving a game.Annals of mathematics(1951), 296–301

    1951

  69. [69]

    2021.Lyapunov Functions and Ensemble Approximations for Constrained Systems using Semidefinite Programming

    Marianne Souaiby. 2021.Lyapunov Functions and Ensemble Approximations for Constrained Systems using Semidefinite Programming. Ph. D. Dissertation. INSA de Toulouse

    2021

  70. [70]

    Yannick Viossat. 2015. Evolutionary dynamics and dominated strategies.Economic Theory Bulletin3 (2015), 91–113

    2015

  71. [71]

    Qian Wang, Zongjun Yang, Xiaotie Deng, and Yuqing Kong. 2023. Learning to bid in repeated first-price auctions with budgets. InInternational Conference on Machine Learning. PMLR, 36494–36513

    2023

  72. [72]

    Zifan Wang, Yi Shen, Michael Zavlanos, and Karl Henrik Johansson. 2023. No-Regret Learning in Strongly Monotone Games Converges to a Nash Equilibrium.https://openreview.net/ forum?id=Ey2ePmtABj

    2023

  73. [73]

    Wei Zhang, Yanjun Han, Zhengyuan Zhou, Aaron Flores, and Tsachy Weissman. 2022. Lever- aging the hints: Adaptive bidding in repeated first-price auctions.Advances in Neural Infor- mation Processing Systems35 (2022), 21329–21341

    2022

  74. [74]

    Junyao Zhao. 2026. From No-Regret to Strategically Robust Learning in Repeated Auctions. arXiv preprint arXiv:2601.03853(2026)

    arXiv 2026

  75. [75]

    differential equation

    Martin Zinkevich. 2003. Online convex programming and generalized infinitesimal gradient ascent. InProceedings of the 20th international conference on machine learning (icml-03). 928–936. 28 A Smooth Games & Mixed-Extensions The guarantees for online gradient ascent provided in [3, 4, 23] in fact apply to the setting of a smooth game. In this appendix, fo...

    2003

  76. [76]

    for anya i ∈A i \A ℓ i,x 0 i (ai) = 0,

  77. [77]

    for anya i ∈A ′ℓ i ,x 0 i (ai) =x i(ai), and

  78. [78]

    That is,x 0 corresponds to a mixed-strategy profile where each playerionly uses strategiesa i ∈A ℓ i

    for anya i ∈A ℓ i \A ′ℓ i ,x 0 i (ai)≥x i(ai). That is,x 0 corresponds to a mixed-strategy profile where each playerionly uses strategiesa i ∈A ℓ i. Moreover, the probability each such strategya i is used is weakly higher thanx i(ai), with the inequality strict only ifa i is not eliminated via a potential proof byh ℓ. Now, construct a sequencex 0, x1, ......