pith. sign in

arxiv: 2606.06085 · v1 · pith:OIXXDUFRnew · submitted 2026-06-04 · 💻 cs.GT

Revenue Guarantees of No-Swap-Regret Dynamics in First Price Auctions

Anders Bo Ipsen , Stratis Skoulakis This is my paper

Pith reviewed 2026-06-27 23:19 UTC · model grok-4.3

classification 💻 cs.GT
keywords first-price auctionsno-swap-regretcorrelated equilibriumrevenue guaranteeslearning in auctionsdiscrete bid gridsswap regret dynamics
0
0 comments X

The pith

Any ε-approximate correlated equilibrium in a discrete first-price auction yields revenue at least as high as the second-highest valuation minus terms that shrink with finer bid grids and better approximations.

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

The paper studies first-price auctions in which every bidder must choose a bid from a finite uniform grid of k+1 points between 0 and 1. It proves that any joint distribution of bids that forms an ε-approximate correlated equilibrium produces expected revenue no lower than the second-highest private value minus a term linear in 1/k and another term linear in ε k squared. Because no-swap-regret learning dynamics converge to such equilibria, the result supplies the first polynomial-time guarantee that the time-averaged revenue of these dynamics approaches the same lower bound. A concrete corollary states that optimal swap-regret algorithms reach this revenue level after a number of rounds polynomial in k and 1/ε.

Core claim

In a first-price auction whose allowable bids form the uniform grid {0, 1/k, …, 1}, the expected revenue of any ε-approximate correlated equilibrium is at least v₂ − Θ(1/k) − Θ(ε k²), where v₂ is the second-highest valuation. When the joint bid distribution is produced by no-swap-regret dynamics whose per-round swap regret is O(√(k T)), the time-averaged revenue after T rounds meets the same bound once T reaches O(k⁵ / ε²).

What carries the argument

ε-approximate correlated equilibrium over the uniform discrete bid grid, to which no-swap-regret dynamics converge.

If this is right

  • No-swap-regret bidders reach revenue within additive Θ(1/k) + Θ(ε) of v₂ after polynomially many rounds.
  • The same revenue lower bound applies to any learning rule whose empirical distribution converges to an ε-approximate correlated equilibrium.
  • The discretization penalty vanishes linearly as the grid becomes finer.
  • The approximation penalty scales quadratically with the grid size k.

Where Pith is reading between the lines

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

  • Taking the limit k → ∞ suggests that every exact correlated equilibrium of the continuous first-price auction extracts at least v₂ in revenue.
  • Similar revenue lower bounds might be provable for other equilibrium notions such as coarse correlated equilibrium or for second-price formats.
  • One could numerically search for the worst-case ε-approximate equilibrium on small grids to check how tight the Θ constants are.

Load-bearing premise

The joint distribution over bids must form an ε-approximate correlated equilibrium and every bid must lie exactly on the uniform grid of spacing 1/k.

What would settle it

An explicit ε-approximate correlated equilibrium (or a sequence of no-swap-regret play histories) whose realized revenue falls below v₂ − C/k − C ε k² for large enough constant C would falsify the claimed lower bound.

Figures

Figures reproduced from arXiv: 2606.06085 by Anders Bo Ipsen, Stratis Skoulakis.

Figure 1
Figure 1. Figure 1: Time-averaged revenue for different values of [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Impact of discretization level k on revenue convergence [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Revenue produced for different number of bidders. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Revenue produced for different number of bidders. [PITH_FULL_IMAGE:figures/full_fig_p023_4.png] view at source ↗
read the original abstract

We study the revenue of approximate correlated equilibrium in discrete first price auctions - the set of allowable bids is $\mathcal{B} = \{0, 1/k, \dots, 1 - 1/k, 1\}$ for some $k \in \mathbb{N}$. We show that the revenue of any $\epsilon$-approximate correlated equilibrium is at least $v_2 - \Theta(1/k)- \Theta(\epsilon k^2)$, where $v_2 \geq 0$ is the second-highest valuation. Our results establish the first polynomial convergence rates on the revenue generated by no-swap regret bidders in first-price auctions. For instance, if bidders admit the optimal swap regret of $\mathcal{O}(\sqrt{k T})$, then the time-averaged revenue is at least $v_2 - \Theta(1/k) - \Theta(\epsilon)$ after $\mathcal{O}(k^5/\epsilon^2)$ rounds.

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

0 major / 3 minor

Summary. The paper analyzes revenue in ε-approximate correlated equilibria for discrete first-price auctions on the uniform bid grid B = {0, 1/k, …, 1}. It proves that any such equilibrium yields expected revenue at least v₂ − Θ(1/k) − Θ(ε k²), where v₂ is the second-highest valuation. The result is then applied to no-swap-regret dynamics, showing that the time-averaged revenue reaches the same bound after O(k⁵/ε²) rounds when bidders achieve the optimal O(√(kT)) swap regret.

Significance. If the central bound holds, the manuscript supplies the first explicit polynomial convergence rates for revenue under no-swap-regret learning in first-price auctions. This is a concrete advance over prior work that either lacked rates or obtained only sub-polynomial dependence; the derivation directly converts the approximate-CE deviation inequalities into a revenue lower bound controlled by grid spacing and action-space size.

minor comments (3)
  1. [Theorem 1 (or equivalent statement of the main revenue bound)] The Θ notation in the abstract and main theorem should be expanded to explicit constants or at least the precise dependence on the number of bidders and valuations; this would make the bound easier to compare with subsequent work.
  2. [Section on dynamics (likely §4 or §5)] The reduction from no-swap-regret dynamics to ε-approximate correlated equilibrium is stated but the precise per-round ε in terms of T and k should be written explicitly in the convergence corollary.
  3. [Introduction or model section] A short remark clarifying whether the argument extends immediately to n > 2 bidders (using only v₂) would help readers; the current statement leaves this implicit.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of our results on revenue lower bounds for ε-approximate correlated equilibria in discrete first-price auctions, as well as the recognition of the first polynomial convergence rates for no-swap-regret dynamics. The recommendation of minor revision is noted; we will incorporate any editorial suggestions in the revised manuscript.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation applies the definition of ε-approximate correlated equilibrium directly: for any bidder i and any deviation function φ, the expected utility gain from φ is at most ε. The paper uses this to bound the total probability mass on bids materially below v₂ (via profitable upward deviations to v₂ or the grid point nearest v₂), yielding the Θ(1/k) discretization loss and the Θ(ε k²) term from the number of possible swaps (action space size |B|=k+1). Both terms arise from algebraic rearrangement of the equilibrium inequalities and the uniform grid structure; neither is obtained by fitting parameters to data nor by renaming a prior result. No self-citation is load-bearing for the central inequality, and the link from no-swap-regret dynamics to approximate CE is the standard external fact that average play of no-swap-regret algorithms converges to approximate CE. The argument is therefore self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard definition of ε-approximate correlated equilibrium and the first-price payment rule; no new free parameters or invented entities are introduced.

axioms (2)
  • standard math Standard definition of ε-approximate correlated equilibrium
    Used to bound revenue in the discrete bid space.
  • domain assumption Bidders submit bids from the uniform grid of spacing 1/k and pay their own bid if they win
    Core modeling choice for the discrete first-price auction.

pith-pipeline@v0.9.1-grok · 5695 in / 1136 out tokens · 25173 ms · 2026-06-27T23:19:02.708546+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

50 extracted references · 3 canonical work pages

  1. [1]

    Fast rate learning in stochastic first price bidding

    Juliette Achddou, Olivier Capp´ e, and Aur´ elien Garivier. Fast rate learning in stochastic first price bidding. In Vineeth N. Balasubramanian and Ivor Tsang, editors,Proceedings of The 13th Asian Conference on Machine Learning, volume 157 ofProceedings of Machine Learning Research, pages 1754–1769. PMLR, 17–19 Nov 2021

    2021

  2. [2]

    On the uniqueness of bayesian coarse correlated equilibria in standard first-price and all-pay auctions

    Mete Seref Ahunbay and Martin Bichler. On the uniqueness of bayesian coarse correlated equilibria in standard first-price and all-pay auctions. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 2491–2537. SIAM, 2025

    2025

  3. [3]

    Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games

    Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Stefano Leonardi and Anupam Gupta, editors,STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022,...

    2022

  4. [4]

    Uncoupled learning dynamics withO(log T)swap regret in multiplayer games

    Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics withO(log T)swap regret in multiplayer games. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors,Advances in Neural Information Processing Systems 35: Annual Conference on Neural Informati...

    2022

  5. [5]

    Robert J. Aumann. Subjectivity and correlation in randomized strategies.Journal of Mathematical Economics, 1(1):67–96, 1974

    1974

  6. [6]

    Contextual bandits with cross-learning.Math

    Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. Contextual bandits with cross-learning.Math. Oper. Res., 48(3):1607–1629, aug 2023

    2023

  7. [7]

    Balseiro and Yonatan Gur

    Santiago R. Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. In Constantinos Daskalakis, Moshe Babaioff, and Herv´ e Moulin, editors,Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017, page 609. ACM, 2017

    2017

  8. [8]

    Artificial intelligence and auction design

    Martino Banchio and Andrzej Skrzypacz. Artificial intelligence and auction design. In David M. Pennock, Ilya Segal, and Sven Seuken, editors,EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022, pages 30–31. ACM, 2022

    2022

  9. [9]

    Computing bayes nash equilibrium strategies in auction games via simultaneous online dual averaging

    Martin Bichler, Maximilian Fichtl, and Matthias Oberlechner. Computing bayes nash equilibrium strategies in auction games via simultaneous online dual averaging. In Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson, editors,Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, page ...

    2023

  10. [10]

    From external to internal regret.J

    Avrim Blum and Yishay Mansour. From external to internal regret.J. Mach. Learn. Res., 8:1307–1324, December 2007

    2007

  11. [11]

    Learning and collusion in multi-unit auctions

    Simina Brˆ anzei, Mahsa Derakhshan, Negin Golrezaei, and Yanjun Han. Learning and collusion in multi-unit auctions. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors,Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orle...

    2023

  12. [12]

    From external to swap regret 2.0: An efficient reduction for large action spaces

    Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. From external to swap regret 2.0: An efficient reduction for large action spaces. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1216–1222. ACM, 2024

    2024

  13. [13]

    A lower bound on swap regret in extensive-form games.CoRR, abs/2406.13116, 2024

    Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, and Brian Hu Zhang. A lower bound on swap regret in extensive-form games.CoRR, abs/2406.13116, 2024. 11

    work page arXiv 2024

  14. [14]

    Simple, credible, and approximately-optimal auctions

    Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, and Santhoshini Velusamy. Simple, credible, and approximately-optimal auctions. InProceedings of the 21st ACM Conference on Economics and Computation, EC ’20, page 713, New York, NY, USA, 2020. Association for Computing Machinery

    2020

  15. [15]

    Nash convergence of mean-based learning algorithms in first price auctions

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

    2022

  16. [16]

    Ravi, and Amin Sayedi

    Stylianos Despotakis, R. Ravi, and Amin Sayedi. First-price auctions in online display advertising.Journal of Marketing Research, 58(5):pp. 888–907, 2021

    2021

  17. [17]

    Mechanism with unique learnable equilibria

    Paul D¨ utting, Thomas Kesselheim, and´Eva Tardos. Mechanism with unique learnable equilibria. In Moshe Babaioff, Vincent Conitzer, and David A. Easley, editors,ACM Conference on Economics and Computation, EC ’14, Stanford , CA, USA, June 8-12, 2014, pages 877–894. ACM, 2014

    2014

  18. [18]

    Polynomial-time computation of exact$ \phi$-equilibria in polyhedral games

    Gabriele Farina and Charilaos Pipis. Polynomial-time computation of exact$ \phi$-equilibria in polyhedral games. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors,Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, N...

    2024

  19. [19]

    Correlated and coarse equilibria of single-item auctions

    Michal Feldman, Brendan Lucier, and Noam Nisan. Correlated and coarse equilibria of single-item auctions. In Yang Cai and Adrian Vetta, editors,Web and Internet Economics - 12th International Conference, WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings, volume 10123 ofLecture Notes in Computer Science, pages 131–144. Springer, 2016

    2016

  20. [20]

    Convergence analysis of no-regret bidding algorithms in repeated auctions

    Zhe Feng, Guru Guruganesh, Christopher Liaw, Aranyak Mehta, and Abhishek Sethi. Convergence analysis of no-regret bidding algorithms in repeated auctions. InThirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Adva...

    2021

  21. [21]

    Learning to bid without knowing your value

    Zhe Feng, Chara Podimata, and Vasilis Syrgkanis. Learning to bid without knowing your value. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18, page 505–522. Association for Computing Machinery, 2018

    2018

  22. [22]

    Liquid welfare guarantees for no-regret learning in sequential budgeted auctions

    Giannis Fikioris and ´Eva Tardos. Liquid welfare guarantees for no-regret learning in sequential budgeted auctions. In Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson, editors,Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, pages 678–698. ACM, 2023

    2023

  23. [23]

    Foster and Rakesh V

    Dean P. Foster and Rakesh V. Vohra. Calibrated learning and correlated equilibrium.Games and Economic Behavior, 21(1):40–55, 1997

    1997

  24. [24]

    Weintraub, Ralph A

    Shumpei Goke, Gabriel Y. Weintraub, Ralph A. Mastromonaco, and Samuel S. Seljan. Bidders’ responses to auction format change in internet display advertising auctions. In David M. Pennock, Ilya Segal, and Sven Seuken, editors,EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022, page 295. ACM, 2022

    2022

  25. [25]

    Optimal no-regret learning in repeated first-price auctions.Operations Research, 73(1):209–238, 2025

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

    2025

  26. [26]

    Learning to bid optimally and efficiently in adversarial first-price auctions, 2020

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

    2020

  27. [27]

    A simple adaptive procedure leading to correlated equilibrium

    Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127–1150, 2000

    2000

  28. [28]

    Hartline, Vasilis Syrgkanis, and ´Eva Tardos

    Jason D. Hartline, Vasilis Syrgkanis, and ´Eva Tardos. No-regret learning in bayesian games. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors,Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, p...

    2015

  29. [29]

    Introduction to online convex optimization, 2023

    Elad Hazan. Introduction to online convex optimization.CoRR, abs/1909.05207, 2019. 12

    work page arXiv 1909

  30. [30]

    No-regret learning from partially observed data in repeated auctions.IFAC-PapersOnLine, 53(2):14–19, 2020

    Orcun Karaca, Pier Giuseppe Sessa, Anna Leidi, and Maryam Kamgarpour. No-regret learning from partially observed data in repeated auctions.IFAC-PapersOnLine, 53(2):14–19, 2020. 21st IFAC World Congress

    2020

  31. [31]

    Auctions between regret-minimizing agents

    Yoav Kolumbus and Noam Nisan. Auctions between regret-minimizing agents. In Fr´ ed´ erique Laforest, Rapha¨ el Troncy, Elena Simperl, Deepak Agarwal, Aristides Gionis, Ivan Herman, and Lionel M´ edini, editors, WWW ’22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022, pages 100–111. ACM, 2022

    2022

  32. [32]

    Strategically-robust learning algorithms for bidding in first-price auctions

    Rachitesh Kumar, Jon Schneider, and Balasubramanian Sivan. Strategically-robust learning algorithms for bidding in first-price auctions. InProceedings of the 25th ACM Conference on Economics and Computation, EC ’24, page 893, New York, NY, USA, 2024. Association for Computing Machinery

    2024

  33. [33]

    Complex dynamics in autobidding systems

    Renato Paes Leme, Georgios Piliouras, Jon Schneider, Kelly Spendlove, and Song Zuo. Complex dynamics in autobidding systems. In Dirk Bergemann, Robert Kleinberg, and Daniela Sab´ an, editors,Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024, pages 75–100. ACM, 2024

    2024

  34. [34]

    Vulnerabilities of single-round incentive compatibility in auto-bidding: Theory and evidence from roi-constrained online advertising markets

    Juncheng Li and Pingzhong Tang. Vulnerabilities of single-round incentive compatibility in auto-bidding: Theory and evidence from roi-constrained online advertising markets. InProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI 2024, Jeju, South Korea, August 3-9, 2024, pages 2886–2894. ijcai.org, 2024

    2024

  35. [35]

    Auto-bidding with budget and roi constrained buyers

    Xiaodong Liu and Weiran Shen. Auto-bidding with budget and roi constrained buyers. IJCAI ’23, 2023

    2023

  36. [36]

    Learning and efficiency in games with dynamic population

    Thodoris Lykouris, Vasilis Syrgkanis, and ´Eva Tardos. Learning and efficiency in games with dynamic population. In Robert Krauthgamer, editor,Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 120–129. SIAM, 2016

    2016

  37. [37]

    Learning to bid in revenue-maximizing auctions

    Thomas Nedelec, Noureddine El Karoui, and Vianney Perchet. Learning to bid in revenue-maximizing auctions. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors,Proceedings of the 36th International Conference on Machine Learning, volume 97 ofProceedings of Machine Learning Research, pages 4781–4789. PMLR, 09–15 Jun 2019

    2019

  38. [38]

    Econometrics for learning agents

    Denis Nekipelov, Vasilis Syrgkanis, and ´Eva Tardos. Econometrics for learning agents. In Tim Roughgarden, Michal Feldman, and Michael Schwarz, editors,Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC ’15, Portland, OR, USA, June 15-19, 2015, pages 1–18. ACM, 2015

    2015

  39. [39]

    Bid prediction in repeated auctions with learning

    Gali Noti and Vasilis Syrgkanis. Bid prediction in repeated auctions with learning. In Jure Leskovec, Marko Grobelnik, Marc Najork, Jie Tang, and Leila Zia, editors,WWW ’21: The Web Conference 2021, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021, pages 3953–3964. ACM / IW3C2, 2021

    2021

  40. [40]

    Why do competitive markets converge to first-price auctions? InProceedings of The Web Conference 2020, WWW ’20, page 596–605, 2020

    Renato Paes Leme, Balasubramanian Sivan, and Yifeng Teng. Why do competitive markets converge to first-price auctions? InProceedings of The Web Conference 2020, WWW ’20, page 596–605, 2020

    2020

  41. [41]

    Fast swap regret minimization and applications to approximate correlated equilibria

    Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and applications to approximate correlated equilibria. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1223–1234. ACM, 2024

    2024

  42. [42]

    Improved learning rates in multi-unit uniform price auctions.Advances in Neural Information Processing Systems, 37:130237–130264, 2024

    Marius Potfer, Dorian Baudry, Hugo Richard, Vianney Perchet, and Cheng Wan. Improved learning rates in multi-unit uniform price auctions.Advances in Neural Information Processing Systems, 37:130237–130264, 2024

    2024

  43. [43]

    Composable and efficient mechanisms

    Vasilis Syrgkanis and ´Eva Tardos. Composable and efficient mechanisms. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors,Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 211–220. ACM, 2013

    2013

  44. [44]

    Counterspeculation, Auctions, And Competitive Sealed Tenders.Journal of Finance, 1961

    William Vickrey. Counterspeculation, Auctions, And Competitive Sealed Tenders.Journal of Finance, 1961

    1961

  45. [45]

    Learning to bid in repeated first-price auctions with budgets

    Qian Wang, Zongjun Yang, Xiaotie Deng, and Yuqing Kong. Learning to bid in repeated first-price auctions with budgets. InProceedings of the 40th International Conference on Machine Learning, ICML’23. JMLR.org, 2023. 13

    2023

  46. [46]

    Online learning in repeated auctions

    Jonathan Weed, Vianney Perchet, and Philippe Rigollet. Online learning in repeated auctions. InConference on Learning Theory, pages 1562–1583. PMLR, 2016

    2016

  47. [47]

    Williamson and David B

    David P. Williamson and David B. Shmoys.The Design of Approximation Algorithms.Cambridge University Press, 2011

    2011

  48. [48]

    Efficient Φ-regret minimization with low-degree swap deviations in extensive-form games.CoRR, abs/2402.09670, 2024

    Brian Hu Zhang, Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm. Efficient Φ-regret minimization with low-degree swap deviations in extensive-form games.CoRR, abs/2402.09670, 2024

    work page arXiv 2024

  49. [49]

    TX t=1 Xt ≥ϵ·T # = Pr

    Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. Mediator interpretation and faster learning algorithms for linear correlated equilibria in general sequential games. InThe Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. 14 A Revisiting the argument in [19] In this section...

    2024

  50. [50]

    7Notice that the fact thatv 1 ≥v 2 ≥

    + v2−2/kX s′ 2=s⋆+1 (v2 −s ′ 2)≥s ⋆ + 2 v2−2/kX s′ 2=s⋆+1 (v2 −s ′ 2) As a result, ˆbs ≥s ⋆ + 2 v2−2/kX s′ 2=s⋆+1/k (v2 −s ′ 2) =s ⋆ + 2v2(kv2 −2−ks ⋆ + 1−1)−2 1 k (kv2 −2)(kv 2 −1) 2 − ks⋆(ks⋆ + 1) 2 =s ⋆ + 2kv2 2 −4v 2 −2k·s ⋆v2 − 1 k (k2v2 2 −3kv 2 + 2−k 2s⋆2 −ks ⋆) =s ⋆ + 2kv2 2 −4v 2 −2k·s ⋆v2 −kv 2 2 + 3v2 − 2 k +ks ⋆2 +s ⋆ = 2s ⋆ +kv 2 2 −v 2 −2k·s...