Pith. sign in

REVIEW 3 major objections 4 minor 295 references

The paper argues that PPAD hardness of autobidding equilibria is an artifact of atomic valuations: with non-atomic value distributions the equilibrium becomes a separately monotone generalized Nash equilibrium, and the PRIME algorithm conve

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 18:45 UTC pith:ELM5KNY3

load-bearing objection Worth a serious referee, but the headline convergence theorem is not proven as stated: Assumption 4.1 silently excludes many diffuse instances, including zero- and small-budget ones. the 3 major comments →

arxiv 2608.01889 v1 pith:ELM5KNY3 submitted 2026-08-03 cs.GT

Beyond the PPAD hardness of Auto-bidding Auctions

Li Chen , Jamie Morgenstern , Yuanyuan Yang This is my paper
classification cs.GT MSC 91A1091B26
keywords autobidding auctionsdiffuse analysisgeneralized Nash equilibriumpacing equilibriumthrottling equilibriumPPAD-hardnesslinear convergenceMoreau envelope
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper's central claim is that the worst-case PPAD-completeness of computing second-price pacing and throttling equilibria is an accident of atomic (deterministic) value distributions. When bidder values are modeled as independent draws from a smooth, non-atomic distribution, expected value and expected payment become well-behaved, and the autobidding equilibrium becomes a separately monotone generalized Nash equilibrium (GNE). The paper proves that its algorithm PRIME converges linearly in the last iterate to this GNE, so an approximate equilibrium is found in O(log(1/ε)) iterations. A sympathetic reader should care because this reconciles the theoretical hardness barrier with the rapid convergence advertisers actually observe, and it supplies the first last-iterate linear-rate solver for this equilibrium class.

Core claim

Under a distributional regularity condition—positive C1 density, bounded density and derivative, finite third moment—the expected value and payment functions of pacing and throttling bidders are smooth, monotone, and satisfy Polyak–Łojasiewicz and relative-Lipschitz inequalities. Hence the ex-ante autobidding equilibrium becomes a separately monotone GNE. Theorem 5.1 states that PRIME, using a hinge-augmented Lagrangian and two nested Moreau envelopes, contracts the sum of squared best-response gaps by a factor of 3/4 each iteration, so O(log(1/ε)) iterations suffice to certify an ε-approximate equilibrium.

What carries the argument

The central object is the separately monotone GNE: each player's loss is decreasing and PŁ in its own strategy, each constraint is increasing and PŁ, and the functions are smooth with controlled cross-player second derivatives. The solver PRIME combines a hinge-penalized augmented Lagrangian, which activates the constraint gradient only when the constraint binds, with a nested Moreau envelope that smooths the landscape and keeps rival updates from moving the target too much. Progress is measured by the local best-response gap, not by distance to a fixed equilibrium, which sidesteps nonuniqueness.

Load-bearing premise

Assumption 4.1: every admissible instance has an equilibrium with all multipliers bounded below by a fixed positive constant α; the paper does not prove this, and very small budgets can force equilibrium multipliers below any such α.

What would settle it

Take a diffuse instance satisfying Assumption 3.4 (for example, i.i.d. Gaussian values) with one bidder's budget set to 0. That bidder's equilibrium multiplier is 0 or arbitrarily small, violating Assumption 4.1 for any fixed α>0. Running PRIME on the restricted domain [α,1]^n would then output a point that is not an equilibrium of the original budget-constrained problem.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • PPAD hardness of second-price pacing and throttling equilibria is avoided in the diffuse model: the barrier rests on atomic value distributions.
  • A single algorithm now covers FPPE, SPPE, FPTE, SPTE, and convex combinations of first- and second-price payments, replacing separate case-by-case analyses.
  • Under the regularity assumptions, an approximate equilibrium is reached in O(log(1/ε)) iterations with a linear last-iterate guarantee, matching empirical convergence.
  • The best-response gap gives a computable certificate of approximate equilibrium even when equilibria are nonunique.
  • The regularity conditions hold for strongly log-concave, power-law (tail exponent greater than 3), and sub-Gaussian value distributions.

Where Pith is reading between the lines

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

  • If Assumption 4.1 fails—for example, a bidder with zero budget—the restricted-domain GNE may not be an equilibrium of the original game; a robust treatment would need an adaptive lower bound or explicit handling of boundary bidders.
  • The diffuse framework suggests that other PPAD-hard equilibrium problems whose hardness relies on atoms may become tractable under smooth non-atomic inputs, provided a separately monotone GNE structure can be established.
  • A direct empirical test: on Gaussian or power-law synthetic instances, PRIME's best-response gap should contract by roughly 3/4 per iteration, while near-atomic approximations of the same instances should slow down or fail to converge.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces a diffuse (non-atomic valuation) framework for autobidding auctions and claims that worst-case PPAD hardness disappears in this regime. It proves regularity properties of Bayesian SPPE/SPTE under smooth densities, reformulates them as separately monotone generalized Nash equilibria, and presents PRIME, a nested-Moreau-envelope algorithm, with Theorem 5.1 claiming last-iterate linear convergence when Assumption 4.1 holds. It also sketches extensions to first-price and convex-combination payment rules.

Significance. If the main theorem can be repaired, the paper would be a substantial contribution. It gives explicit, checkable integral formulas for SPPE/SPTE regularity and a clean reduction to separately monotone GNE, spanning pacing and throttling under first- and second-price rules. It also presents an explicit linear-rate algorithm with a concrete 3/4 contraction target and correctly identifies atomicity as the source of the PPAD hardness. The weaknesses described below are in the global convergence machinery and in the 'any diffuse instance' framing; they are technical gaps rather than disagreements with prior consensus.

major comments (3)
  1. [Assumption 4.1 / App. D.1] Assumption 4.1 is load-bearing for the paper's main claim: Thm. 3.5, the PŁ constants, and PRIME's analysis are all stated on Xα=[α,1]^n, and the reduction to separately monotone GNE assumes an equilibrium in that restricted domain. The assumption is not proved, and it is false for admissible instances. Problems D.1/E.1 allow ρ_i≥0. In a two-bidder SPPE with ρ_1=0 and ρ_2>0, any profile with α_1,α_2>0 has g_1(α)=E[x_1 α_2 v_2]>0 under Assumption 3.4, so no equilibrium with α_1≥α>0 exists; every equilibrium has α_1=0. With equal positive budgets ε, the symmetric equilibrium multiplier is O(ε), so for any fixed α there are admissible instances whose active equilibrium lies below α. Thus Thm. 1.1's 'any diffuse instance' and Thm. 5.1's applicability are not established. The authors should either prove a lower bound on equilibrium multipliers, or explicitly restrict the theorems to instances
  2. [Appendix H, Lemma H.1] Lemma H.1 asserts that m(α)=max_{λ∈[0,Cλ]} Lη(α,λ) satisfies the PŁ condition, but no proof is given. The proof paragraph establishes Lipschitzness and smoothness and then states 'This indicates that m satisfies PŁ condition'; smoothness alone does not imply PŁ. The claim that the maximizer never takes the L+ branch is also not justified. Lemma H.4 assumes m is µm-PŁ to prove the nested envelope is PŁ, and Lemma H.5/Theorem H.6 depend on this for linear convergence. This is a central missing argument, not a presentation issue.
  3. [Appendix H, Theorem H.6] In the proof of Theorem H.6, the second inequality bounds the movement of the best response α_i^*(α_-i^{(t-1)})−α_i^*(α_-i^{(t)}) by (n−1) max_j ||∂α_j^*/∂α_-j||^2 ||α_i^{(t-1)}−α_i^{(t)}||^2. This uses the wrong variable: the best response moves because rivals' strategies α_-i change, not because player i's own iterate changes. A correct argument needs a bound on ||α_-i^{(t-1)}−α_-i^{(t)}|| and a subsequent sum over players; the proof also does not bound ||α_i^{(t)}−α_i^{(t-1)}|| in terms of the previous best-response gap. As written, the displayed 3/4 contraction is not established.
minor comments (4)
  1. [Abstract / §1.1] Typographical and wording issues: 'Reducting' in the §1.1 heading, 'equlibriums' in Theorem 3.5, and 'Exisitence' in Theorem 3.3 should be fixed.
  2. [Theorem 5.1 / Algorithm 1] Algorithm 1 fixes λ_i = C_i^λ at line 3 and never updates λ, but Theorem 5.1 claims convergence 'to a GNE point (α*, λ*)'. The role of λ* should be clarified; under the proof's choice it appears λ*=Cλ.
  3. [Assumption C.1 / D.2 / E.2] The distributional regularity assumption is stated almost verbatim as Assumption 3.4, C.1, D.2, and E.2. Consolidating into one numbered assumption would reduce ambiguity.
  4. [Notation, App. B/G] The domain Xα appears as (0,1] in App. B and G but as [α,1]^n in App. D/E. Use a consistent notation, e.g., Xα=[α,1]^n throughout.

Circularity Check

0 steps flagged

No circular derivation found; the diffuse-analysis reduction is self-contained, though Assumption 4.1 is an unproven load-bearing domain restriction (a correctness gap, not circularity).

full rationale

The paper's positive chain is: Assumption 3.4 → explicit integral formulas (Lemma D.4/E.4) → smoothness, Hessian bounds, monotonicity, PŁ and relative Lipschitz constants (Thm 3.5, Lemmas D.7–D.11/E.6–E.7) → separately monotone GNE (Def 4.1) → saddle-point equivalence and envelope estimates (Thm G.1, Lemmas H.2–H.5) → linear last-iterate contraction (Thm H.6). The PŁ constants are explicit functions of the model's densities and moments (e.g., μ_l = (m_l)^2/(2U_l(1−α)) in Lemma D.10), not fitted parameters. The PPAD-hardness results are imported only as external benchmarks ([CKK21a], [CKK21b], [CL25]), and the convergence theorem is not derived from them. I find no step where a quantity is defined in terms of the target conclusion, no fitted quantity renamed as a prediction, and no load-bearing self-citation. The one notable caveat is Assumption 4.1 (Existence of Active Equilibrium), stated in Section 4 with only an intuitive justification ('This assumption is mild: ...'); it is load-bearing because all regularity and convergence results are proved on the restricted domain Xα=[α,1]^n. If the assumption fails (e.g., zero-budget diffuse instances), PRIME may compute a GNE of the restricted game rather than an SPPE/SPTE of the original problem. This is a missing-support/correctness risk, not a circularity: the assumption is not derived from the convergence conclusion, and the formal theorem is conditional on it. Hence overall circularity score 1.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 0 invented entities

The central convergence theorem rests on three groups of assumptions: (1) distributional regularity (Assumption 3.4), which excludes atomic and heavy-tailed distributions but covers log-concave, power-law with tail exponent > 3, and sub-Gaussian families; (2) the active-equilibrium assumption (Assumption 4.1), which is asserted as mild but not proven and can fail for zero-budget bidders; and (3) the game-modeling choices of i.i.d. per-round values and per-iteration ex-ante budgets, which make the expected objectives smooth. The PŁ constants and Lipschitz bounds are derived, not fitted, so the ledger contains no data-fitting parameters; the algorithm's hyperparameters (envelope parameters, step sizes, inner-loop counts) are shown to exist but are not given explicit numerical values.

free parameters (3)
  • α (domain lower bound) = unspecified, a sufficiently small constant in (0,1]
    All proofs restrict multipliers to [α,1]^n; the PŁ constants in Lemma D.10 depend on (1-α) and Assumption 4.1 requires equilibrium multipliers be ≥ α. Chosen by hand, not derived.
  • C_λ (dual-variable cap) = unspecified, at least the relative Lipschitz constant L_c + 1
    The saddle-point equivalence (Theorem G.1) and the fixed-λ analysis in Appendix H require λ ∈ [0, C_λ] with C_λ sufficiently large; no concrete value is given.
  • PRIME hyperparameters (η1, η̃, τ1, k) = existence only: η̃ ≥ 4 L_m, τ1 ≤ 1/L_m, k ≥ log(μ1/η̃)/log(1-τ1 μ̃)
    The algorithm's convergence is existential; no explicit numerical formulas are provided for computing these from the distribution's P, Q, and moments.
axioms (4)
  • domain assumption Distributional Regularity (Assumption 3.4): each value density p_i is positive, C^1, with bounded density, bounded density derivative, and finite third moment.
    This is the core smoothness input; the paper shows it holds for smooth log-concave, power-law (tail exponent > 3), and sub-Gaussian families, but it excludes all atomic and heavy-tailed distributions.
  • ad hoc to paper Existence of an active equilibrium (Assumption 4.1): there is an equilibrium α* with α*_i ≥ α for all i.
    Asserted as mild with only an intuitive complementary-slackness argument; no proof is given, and zero-budget bidders would produce multipliers below any fixed α.
  • domain assumption i.i.d. per-round values from a fixed product distribution, with per-iteration ex-ante budget constraints (Problems 3.1 and 3.2).
    The Bayesian ex-ante equilibrium is a different solution concept from the ex-post PPAD-hard equilibrium; without this modeling choice, the expected payment functions are not smooth.
  • standard math Existence of ex-ante SPPE/SPTE/FPPE/FPTE (Theorem 3.3), cited from [CKK21b, BKMM21, CKP+22].
    The paper relies on prior existence results for the equilibria it computes; it does not reprove them.

pith-pipeline@v1.3.0-daily-deepseek · 51705 in / 23309 out tokens · 215795 ms · 2026-08-04T18:45:39.157350+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Beyond the PPAD hardness of Auto-bidding Auctions." pith.science (2026). https://pith.science/paper/ELM5KNY3

@misc{pith2026260801889,
  author       = {Pith},
  title        = {Pith review of: Beyond the PPAD hardness of Auto-bidding Auctions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ELM5KNY3}},
  note         = {Machine review of arXiv:2608.01889}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Computing certain autobidding equilibria is PPAD complete in the worst case. Yet such instances rarely arise in practice, where advertisers running simple, decentralized learning strategies usually converge quickly. We show there is no contradiction: the hardness requires atomicity and vanishes once the value distribution is nonatomic, as it is in real world markets. To bridge worst case hardness and practical convergence, we introduce diffuse analysis, a beyond worst case framework that studies equilibrium computation when bidder values are drawn from general nonatomic distributions. Under this framework, the autobidding equilibrium becomes a separately monotone generalized Nash equilibrium (GNE). For this GNE, we give the first solver with last iterate linear convergence. Thus, the equilibrium has polynomial diffuse complexity, matching the convergence observed in real-world markets. Concretely, our framework subsumes the budget pacing and the throttling equilibrium as special cases when the payment rule is a convex combination of first and second price.

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

295 extracted references · 19 linked inside Pith

  1. [1]

    Auto-bidding and auctions in online advertising: A survey

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

    2024

  2. [2]

    Selling joint ads: A regret minimization perspective

    Gagan Aggarwal, Ashwinkumar Badanidiyuru, Paul D \"u tting, and Federico Fusco. Selling joint ads: A regret minimization perspective. In Proceedings of the 25th ACM Conference on Economics and Computation , pages 164--194, 2024

    2024

  3. [3]

    Aggarwal, A

    G. Aggarwal, A. Badanidiyuru, and A. Mehta. Autobidding with constraints. In Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10--12, 2019, Proceedings 15 , pages 17--30. Springer, 2019

    2019

  4. [4]

    Existence of an equilibrium for a competitive economy

    Kenneth J Arrow and Gerard Debreu. Existence of an equilibrium for a competitive economy. In The Foundations of Price Theory Vol 5 , pages 289--316. Routledge, 2024

    2024

  5. [5]

    Online bandit learning against an adaptive adversary: from regret to policy regret

    Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against an adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Coference on International Conference on Machine Learning , pages 1747--1754, 2012

    2012

  6. [6]

    A convergence theory for saddle functions

    H \'e dy Attouch and Roger J-B Wets. A convergence theory for saddle functions. Transactions of the American Mathematical Society , 280(1):1--41, 1983

    1983

  7. [8]

    A dynamic near-optimal algorithm for online linear programming

    Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research , 62(4):876--890, 2014

    2014

  8. [9]

    Approximating nash equilibria and dense bipartite subgraphs via an approximate version of carath\'eodory's theorem

    Siddharth Barman. Approximating nash equilibria and dense bipartite subgraphs via an approximate version of carath\'eodory's theorem. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC) , pages 361--369, 2015

    2015

  9. [10]

    Smoothed complexity of 2-player nash equilibria

    Shant Boodaghians, Joshua Brakensiek, Samuel B Hopkins, and Aviad Rubinstein. Smoothed complexity of 2-player nash equilibria. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 271--282. IEEE, 2020

    2020

  10. [11]

    Repeated auctions with budgets in ad exchanges: Approximations and design

    Santiago R Balseiro, Omar Besbes, and Gabriel Y Weintraub. Repeated auctions with budgets in ad exchanges: Approximations and design. Management Science , 61(4):864--884, 2015

    2015

  11. [12]

    The best of both worlds: Asymptotically efficient mechanisms with a guarantee on the expected gains-from-trade

    Moshe Babaioff, Yang Cai, Yannai A Gonczarowski, and Mingfei Zhao. The best of both worlds: Asymptotically efficient mechanisms with a guarantee on the expected gains-from-trade. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC) , 2018

    2018

  12. [13]

    Dynamics of bid optimization in online advertisement auctions

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

    2007

  13. [14]

    Smoothed online learning is as easy as statistical learning

    Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory , pages 1716--1786. PMLR, 2022

    2022

  14. [15]

    Achieving optimal backlog in multi-processor cup games

    Michael A Bender, Mart \' n Farach-Colton, and William Kuszmaul. Achieving optimal backlog in multi-processor cup games. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages 1148--1157, 2019

    2019

  15. [16]

    Nash stability in social distance games

    Alkida Balliu, Michele Flammini, Giovanna Melideo, and Dennis Olivetti. Nash stability in social distance games. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI) , 2017

    2017

  16. [17]

    Learning in repeated auctions with budgets: Regret minimization and equilibrium

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

    2019

  17. [18]

    Bulow-klemperer-style results for welfare maximization in two-sided markets

    Moshe Babaioff, Kira Goldner, and Yannai A Gonczarowski. Bulow-klemperer-style results for welfare maximization in two-sided markets. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2020

    2020

  18. [19]

    Truthful mechanisms for two-sided markets via prophet inequalities

    Alexander Braun and Thomas Kesselheim. Truthful mechanisms for two-sided markets via prophet inequalities. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC) , 2021. arXiv:2105.15032

    Pith/arXiv arXiv 2021

  19. [20]

    Balseiro, C

    S. Balseiro, C. Kroer, and R. Kumar. Contextual standard auctions with budgets: Revenue equivalence and efficiency guarantees. Management Science , 69(11):6837--6854, 2023

    2023

  20. [21]

    Budget-management strategies in repeated auctions

    Santiago Balseiro, Anthony Kim, Mohammad Mahdian, and Vahab Mirrokni. Budget-management strategies in repeated auctions. Operations Research , 2021

    2021

  21. [22]

    One-dimensional empirical measures, order statistics, and Kantorovich transport distances , volume 261

    Sergey Bobkov and Michel Ledoux. One-dimensional empirical measures, order statistics, and Kantorovich transport distances , volume 261. American Mathematical Society, 2019

    2019

  22. [23]

    Agnostic smoothed online learning

    Mo \" se Blanchard. Agnostic smoothed online learning. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 1997--2006, 2025

    1997

  23. [24]

    Balseiro, H

    Santiago R. Balseiro, H. Lu, and V. Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research , 71(1):101--119, 2023

    2023

  24. [25]

    Approximation algorithms for the weighted nash social welfare via convex and non-convex programs

    Adam Brown, Aditi Laddha, Madhusudhan Reddy Pittu, and Mohit Singh. Approximation algorithms for the weighted nash social welfare via convex and non-convex programs. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2024

    2024

  25. [26]

    Convex optimization: Algorithms and complexity

    S \'e bastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and trends in Machine Learning , 8(3-4):231--357, 2015

    2015

  26. [27]

    Convex optimization

    Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge UP , 2004

    2004

  27. [28]

    Online learning with switching costs and other adaptive adversaries

    Nicolo Cesa-Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems , 26, 2013

    2013

  28. [29]

    Fair division of indivisible goods for a class of concave valuations

    Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn. Fair division of indivisible goods for a class of concave valuations. Journal of Artificial Intelligence Research , 74:111--142, 2022

    2022

  29. [30]

    Online learning with knapsacks: the best of both worlds

    Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In International Conference on Machine Learning , pages 2767--2783. PMLR, 2022

    2022

  30. [31]

    Recent development in computational complexity characterization of nash equilibrium

    Xi Chen and Xiaotie Deng. Recent development in computational complexity characterization of nash equilibrium. Computer Science Review , 1(2):88--99, 2007

    2007

  31. [32]

    Convex program duality, fisher markets, and nash social welfare

    Richard Cole, Nikhil R Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V Vazirani, and Sadra Yazdanbod. Convex program duality, fisher markets, and nash social welfare. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC) , 2017

    2017

  32. [33]

    Playing anonymous games using simple strategies

    Yu Cheng, Ilias Diakonikolas, and Alistair Stewart. Playing anonymous games using simple strategies. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2017

    2017

  33. [34]

    Computing nash equilibria: Approximation and smoothed complexity

    Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Computing nash equilibria: Approximation and smoothed complexity. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) , pages 603--612. IEEE, 2006

    2006

  34. [35]

    Settling the complexity of computing two-player nash equilibria

    Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM (JACM) , 56(3):1--57, 2009

    2009

  35. [36]

    A simple mechanism for a budget-constrained buyer

    Yu Cheng, Nick Gravin, Kamesh Munagala, and Kangning Wang. A simple mechanism for a budget-constrained buyer. In Web and Internet Economics (WINE) . Springer, 2018

    2018

  36. [37]

    The query complexity of uniform pricing

    Houshuang Chen, Yaonan Jin, Pinyan Lu, and Chihao Zhang. The query complexity of uniform pricing. In Proceedings of the ACM Web Conference (WWW) , 2026. arXiv:2507.12733

    arXiv 2026

  37. [38]

    The complexity of pacing for second-price auctions

    Xi Chen, Christian Kroer, and Rachitesh Kumar. The complexity of pacing for second-price auctions. The Twenty-Second ACM Conference on Economics and Computation , 2021

    2021

  38. [40]

    Pacing equilibrium in first price auction markets

    Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas E Stier-Moses, Eric Sodomka, and Christopher A Wilkens. Pacing equilibrium in first price auction markets. Management Science , 2022

    2022

  39. [41]

    Multiplicative pacing equilibria in auction markets

    Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E Stier-Moses. Multiplicative pacing equilibria in auction markets. Operations Research , 70(2):963--989, 2022

    2022

  40. [43]

    Restricted max-min fair allocation

    Siu-Wing Cheng and Yuchen Mao. Restricted max-min fair allocation. In International Colloquium on Automata, Languages, and Programming (ICALP) , 2018

    2018

  41. [44]

    Theoretical properties of the log-concave maximum likelihood estimator of a multidimensional density

    M Cule and R Samworth. Theoretical properties of the log-concave maximum likelihood estimator of a multidimensional density. ELECTRONIC JOURNAL OF STATISTICS , 4, 2009

    2009

  42. [45]

    Dynamic budget throttling in repeated second-price auctions

    Zhaohua Chen, Chang Wang, Qian Wang, Yuqi Pan, Zhuming Shi, Zheng Cai, Yukun Ren, Zhihua Zhu, and Xiaotie Deng. Dynamic budget throttling in repeated second-price auctions. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 38, pages 9598--9606, 2024

    2024

  43. [46]

    Faster stochastic algorithms for minimax optimization under polyak- \ L \ ojasiewicz condition

    Lesi Chen, Boyuan Yao, and Luo Luo. Faster stochastic algorithms for minimax optimization under polyak- \ L \ ojasiewicz condition. Advances in Neural Information Processing Systems , 35:13921--13932, 2022

    2022

  44. [47]

    Budget-constrained auctions with unassured priors: Strategic equivalence and structural properties

    Zhaohua Chen, Mingwei Yang, Chang Wang, Jicheng Li, Zheng Cai, Yukun Ren, Zhihua Zhu, and Xiaotie Deng. Budget-constrained auctions with unassured priors: Strategic equivalence and structural properties. In Proceedings of the ACM Web Conference 2024 , pages 14--24, 2024

    2024

  45. [48]

    Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems

    Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal on Optimization , 29(3):1908--1930, 2019

    1908

  46. [50]

    Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized nash equilibrium problems

    Axel Dreves and Christian Kanzow. Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized nash equilibrium problems. Computational Optimization and Applications , 50(1):23--48, 2011

    2011

  47. [51]

    Efficiency guarantees in auctions with budgets

    Shahar Dobzinski and Renato Paes Leme. Efficiency guarantees in auctions with budgets. In International Colloquium on Automata, Languages, and Programming , pages 392--404. Springer, 2014

    2014

  48. [52]

    Autobidding equilibria in sponsored shopping

    Paul D \"u tting, Yuhao Li, Renato Paes Leme, Kelly Spendlove, and Yifeng Teng. Autobidding equilibria in sponsored shopping. In Proceedings of the 27th ACM Conference on Economics and Computation (EC) , 2026. arXiv:2602.21966

    arXiv 2026

  49. [53]

    Secretaries with advice

    Paul D \"u tting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC) , 2021

    2021

  50. [54]

    A combinatorial polynomial algorithm for the linear arrow-debreu market

    Ran Duan and Kurt Mehlhorn. A combinatorial polynomial algorithm for the linear arrow-debreu market. In International Colloquium on Automata, Languages, and Programming (ICALP) . Springer, 2013

    2013

  51. [55]

    Online markov decision processes

    Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathematics of Operations Research , 34(3):726--736, 2009

    2009

  52. [56]

    Consensus of subjective probabilities: The pari-mutuel method

    Edmund Eisenberg and David Gale. Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics , 30(1):165--168, 1959

    1959

  53. [57]

    Online allocation with traffic spikes: Mixing adversarial and stochastic models

    Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni. Online allocation with traffic spikes: Mixing adversarial and stochastic models. In Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC) , 2015

    2015

  54. [58]

    Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords

    Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American economic review , 97(1):242--259, 2007

    2007

  55. [59]

    Finite-dimensional variational inequalities and complementarity problems, 2003

    F Facchinei. Finite-dimensional variational inequalities and complementarity problems, 2003

    2003

  56. [60]

    Generalized nash equilibrium problems and newton methods

    Francisco Facchinei, Andreas Fischer, and Veronica Piccialli. Generalized nash equilibrium problems and newton methods. Mathematical Programming , 117(1):163--194, 2009

    2009

  57. [61]

    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. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 35, pages 5399--5406, 2021

    2021

  58. [62]

    Constant approximation for weighted nash social welfare with submodular valuations

    Yuda Feng, Yang Hu, Shi Li, and Ruilong Zhang. Constant approximation for weighted nash social welfare with submodular valuations. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) , 2025. arXiv:2411.02942

    arXiv 2025

  59. [63]

    Generalized nash equilibrium problems

    Francisco Facchinei and Christian Kanzow. Generalized nash equilibrium problems. Annals of Operations Research , 175(1):177--211, 2010

    2010

  60. [64]

    Penalty methods for the solution of generalized nash equilibrium problems

    Francisco Facchinei and Christian Kanzow. Penalty methods for the solution of generalized nash equilibrium problems. SIAM Journal on Optimization , 20(5):2228--2253, 2010

    2010

  61. [65]

    Learning in budgeted auctions with spacing objectives

    Giannis Fikioris, Robert Kleinberg, Yoav Kolumbus, Raunak Kumar, Yishay Mansour, and \'E va Tardos. Learning in budgeted auctions with spacing objectives. In Proceedings of the 26th ACM Conference on Economics and Computation (EC) , 2025. arXiv:2411.04843

    Pith/arXiv arXiv 2025

  62. [66]

    Gerald B. Folland. Real Analysis: Modern Techniques and Their Applications . Wiley, 2 edition, 1999

    1999

  63. [67]

    Z. Feng, S. Padmanabhan, and D. Wang. Online bidding algorithms for return-on-spend constrained advertisers. In Proceedings of the ACM Web Conference 2023 , pages 3550--3560, 2023

    2023

  64. [68]

    Consensus-halving: Does it ever get easier? In Proceedings of the 21st ACM Conference on Economics and Computation (EC) , 2020

    Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis. Consensus-halving: Does it ever get easier? In Proceedings of the 21st ACM Conference on Economics and Computation (EC) , 2020

    2020

  65. [69]

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

    Giannis Fikioris and \'E va Tardos. Liquid welfare guarantees for no-regret learning in sequential budgeted auctions. In Proceedings of the 24th ACM Conference on Economics and Computation , pages 678--698, 2023

    2023

  66. [70]

    On profit-maximizing envy-free pricing

    Venkatesan Guruswami, Jason D Hartline, Anna R Karlin, David Kempe, Claire Kenyon, and Frank McSherry. On profit-maximizing envy-free pricing. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1164--1173, 2005

    2005

  67. [71]

    A smoothed fptas for equilibria in congestion games

    Yiannis Giannakopoulos. A smoothed fptas for equilibria in congestion games. In Proceedings of the 25th ACM Conference on Economics and Computation , pages 401--413, 2024

    2024

  68. [72]

    First-order methods for large-scale market equilibrium computation

    Yuan Gao and Christian Kroer. First-order methods for large-scale market equilibrium computation. Advances in Neural Information Processing Systems , 33:21738--21750, 2020

    2020

  69. [73]

    Budget pacing in repeated auctions: Regret and efficiency without convergence

    Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget pacing in repeated auctions: Regret and efficiency without convergence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , pages 52--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2023

    2023

  70. [74]

    The landscape of the proximal point method for nonconvex--nonconcave minimax optimization

    Benjamin Grimmer, Haihao Lu, Pratik Worah, and Vahab Mirrokni. The landscape of the proximal point method for nonconvex--nonconcave minimax optimization. Mathematical Programming , 201(1):373--407, 2023

    2023

  71. [75]

    Procurement auctions with best and final offers

    Vasilis Gkatzelis, R Preston McAfee, and Renato Paes Leme. Procurement auctions with best and final offers. In Proceedings of the ACM Web Conference (WWW) , pages 3335--3343, 2025. arXiv:2503.10910

    Pith/arXiv arXiv 2025

  72. [77]

    Generalized nash games and quasi-variational inequalities

    Patrick T Harker. Generalized nash games and quasi-variational inequalities. European journal of Operational research , 54(1):81--94, 1991

    1991

  73. [78]

    Matrix analysis

    Roger A Horn and Charles R Johnson. Matrix analysis . Cambridge university press, 2012

    2012

  74. [79]

    Smoothed analysis with adaptive adversaries

    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries. Journal of the ACM , 71(3):1--34, 2024

    2024

  75. [80]

    Strong equilibria in bayesian games with bounded group size

    Qishen Han, Grant Schoenebeck, Biaoshuai Tao, and Lirong Xia. Strong equilibria in bayesian games with bounded group size. In Proceedings of the ACM Web Conference (WWW) , 2025. arXiv:2502.00260

    Pith/arXiv arXiv 2025

  76. [81]

    Adwords in a panorama

    Zhiyi Huang, Qiankun Zhang, and Yuhao Zhang. Adwords in a panorama. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , 2020

    2020

  77. [82]

    Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors

    Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, and Kirk Pruhs. Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) , pages 531--540, 2014

    2014

  78. [83]

    Immorlica, K

    N. Immorlica, K. Sankararaman, R. Schapire, and A. Slivkins. Adversarial bandits with knapsacks. Journal of the ACM , 69(6):1--47, 2022

    2022

  79. [84]

    First-order algorithms for nonlinear generalized nash equilibrium problems

    Michael I Jordan, Tianyi Lin, and Manolis Zampetakis. First-order algorithms for nonlinear generalized nash equilibrium problems. Journal of Machine Learning Research , 24(38):1--46, 2023

    2023

  80. [85]

    Efficiently computing nash equilibria in adversarial team markov games

    Fivos Kalogiannis, Ioannis Anagnostides, Ioannis Panageas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Vaggos Chatziafratis, and Stelios Stavroulakis. Efficiently computing nash equilibria in adversarial team markov games. In International Conference on Learning Representations (ICLR) , 2023

    2023

Showing first 80 references.