pith. sign in

arxiv: 2605.17665 · v1 · pith:PWN2JTKCnew · submitted 2026-05-17 · 💻 cs.GT

On the Complexity of Correlated Equilibria Beyond Normal-Form Games

Ioannis Anagnostides , Constantinos Daskalakis , Gabriele Farina , Noah Golowich , Tuomas Sandholm , Brian Hu Zhang This is my paper

Pith reviewed 2026-05-19 22:00 UTC · model grok-4.3

classification 💻 cs.GT
keywords correlated equilibriumconcave quadratic gamescomputational complexityswap regretPhi-equilibriacontraction mappingonline learninggame theory
0
0 comments X

The pith

Computing a correlated equilibrium in concave quadratic games is as hard as computing the fixed point of a contraction mapping.

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

The paper proves that finding a correlated equilibrium in concave quadratic games has the same computational difficulty as locating the fixed point of a contraction mapping. This supplies the first concrete evidence that the problem is intractable once one moves past normal-form games to settings such as routing or extensive-form games. The work also establishes that any online algorithm needs exponentially many rounds in the dimension to drive average swap regret below 1/poly(d). To make progress despite these barriers, the authors introduce poly-dimensional Phi-equilibria and give a fully polynomial-time approximation scheme for them in general concave games, plus a poly(d, log(1/epsilon)) algorithm specialized to quadratic games.

Core claim

The central discovery is a reduction showing that any algorithm for computing a correlated equilibrium in a concave quadratic game can be used to compute a fixed point of a contraction mapping, and vice versa. This equivalence supplies the first strong hardness result for correlated equilibrium beyond polynomial-type games. The paper further proves an unconditional information-theoretic lower bound ruling out strongly sublinear swap-regret minimizers and then circumvents the hardness by designing efficient algorithms for the relaxed concept of poly-dimensional Phi-equilibria.

What carries the argument

A polynomial-time reduction from the fixed-point problem for contraction mappings to the computation of correlated equilibria in concave quadratic games.

If this is right

  • No polynomial-time algorithm exists for correlated equilibria in concave quadratic games unless contraction fixed points are polynomial-time computable.
  • Any online learning procedure requires exponentially many iterations in dimension d to reach 1/poly(d) average swap regret.
  • A fully polynomial-time approximation scheme exists for poly-dimensional Phi-equilibria in arbitrary concave games.
  • Poly(d, log(1/epsilon))-time algorithms exist for poly-dimensional Phi-equilibria in concave quadratic games.

Where Pith is reading between the lines

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

  • The same reduction technique may extend hardness results to other structured concave games if analogous payoff representations can be found.
  • Efficient Phi-equilibrium algorithms could be substituted for exact correlated equilibria in large-scale multi-agent systems where only approximate stability is required.
  • The ability to compute fixed points of mappings that contract under an unknown Mahalanobis norm may apply to optimization problems outside game theory.

Load-bearing premise

The hardness reduction is constructed specifically for concave quadratic games and the ordinary definition of correlated equilibrium.

What would settle it

A polynomial-time algorithm that returns a correlated equilibrium for every concave quadratic game would falsify the claimed equivalence unless contraction fixed points are also polynomial-time computable.

Figures

Figures reproduced from arXiv: 2605.17665 by Brian Hu Zhang, Constantinos Daskalakis, Gabriele Farina, Ioannis Anagnostides, Noah Golowich, Tuomas Sandholm.

Figure 1
Figure 1. Figure 1: A depiction of the class of tree-form decision problems used in the proof of [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
read the original abstract

Correlated equilibria are a fundamental solution concept in game theory. However, despite decades of research, the complexity beyond games of polynomial type -- such as extensive-form games, congestion or routing games, and more broadly concave games -- has remained a major open problem, first highlighted by Papadimitriou and Roughgarden (JACM '08). In this paper, we resolve several long-standing questions concerning the complexity of correlated equilibria and swap regret minimization. First, we show that computing a correlated equilibrium in concave quadratic games is as hard as computing the fixed point of a contraction mapping (Contr), providing the first strong evidence of intractability. Moreover, we establish an unconditional, information-theoretic lower bound ruling out the existence of a strongly sublinear swap regret minimizer: any online learning algorithm requires exponentially many iterations in the dimension $d$ to guarantee at most $1/\text{poly}(d)$ (average) swap regret. To circumvent these hardness results, we examine the complexity of $\Phi$-equilibria -- tractable relaxations of correlated equilibria. We obtain a fully polynomial-time approximation scheme (FPTAS) for computing poly-dimensional $\Phi$-equilibria in general concave games. We complement this by showing that Contr-hardness persists even under poly-dimensional swap deviations in the regime where the precision $\epsilon$ is exponentially small. Finally, we show that Contr-hardness can be bypassed in the canonical setting of concave \emph{quadratic games}, for which we provide a $\text{poly}(d, \log(1/\epsilon))$-time algorithm for computing poly-dimensional $\Phi$-equilibria. As a byproduct, we obtain an algorithm for computing fixed points of a mapping that is contracting with respect to an unknown Mahalanobis norm, which could be of independent interest.

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 resolves open questions on the complexity of correlated equilibria beyond normal-form games. It proves that computing a correlated equilibrium in concave quadratic games is Contr-hard via a direct reduction that encodes fixed-point conditions into equilibrium inequalities while preserving quadratic concavity of payoffs. It establishes an unconditional information-theoretic lower bound showing that any online algorithm requires exponentially many iterations in dimension d to achieve 1/poly(d) average swap regret. It provides an FPTAS for poly-dimensional Φ-equilibria in general concave games, shows that Contr-hardness persists for poly-dimensional swap deviations at exponentially small precision, and gives a poly(d, log(1/ε))-time algorithm for poly-dimensional Φ-equilibria in concave quadratic games, plus a byproduct algorithm for fixed points of contractions w.r.t. an unknown Mahalanobis norm.

Significance. If the results hold, this supplies the first strong evidence of intractability for correlated equilibrium computation in concave games, directly addressing the open problem posed by Papadimitriou and Roughgarden (JACM '08). The algorithmic contributions for Φ-equilibria supply tractable relaxations, and the direct reduction together with the Mahalanobis-norm fixed-point algorithm are explicit strengths that could be of independent interest in optimization and learning.

major comments (2)
  1. [§3] §3 (Reduction construction): the argument that concavity of the quadratic payoffs follows immediately from the contraction constant being strictly less than 1 should include an explicit verification that the Hessian remains negative definite for all deviation sets under the standard correlated-equilibrium definition; this step is load-bearing for the Contr-hardness transfer.
  2. [Swap regret lower bound] Theorem on information-theoretic lower bound (swap-regret section): the exponential dependence on d for achieving 1/poly(d) average swap regret is stated unconditionally, but the precise exponent and the precise notion of 'strongly sublinear' should be cross-referenced to the exact statement of the minimax theorem used, to confirm no hidden dependence on game parameters.
minor comments (2)
  1. [Abstract] Abstract: the phrase 'poly(d, log(1/ε))' should be expanded to 'poly(d, log(1/ε))-time' for immediate clarity on the complexity claim.
  2. [Introduction] Notation for Φ-equilibria and poly-dimensional deviations is introduced late; a brief forward reference in the introduction would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments. We are glad that the referee finds the results significant in addressing open questions on correlated equilibria beyond normal-form games. We address each major comment below and will make the suggested clarifications in the revised version.

read point-by-point responses

  1. Referee: [§3] §3 (Reduction construction): the argument that concavity of the quadratic payoffs follows immediately from the contraction constant being strictly less than 1 should include an explicit verification that the Hessian remains negative definite for all deviation sets under the standard correlated-equilibrium definition; this step is load-bearing for the Contr-hardness transfer.

    Authors: We agree that an explicit verification strengthens the presentation of the reduction. In the revised manuscript, we will add a self-contained calculation in §3 showing that, for any contraction constant κ < 1, the Hessian of each quadratic payoff remains negative definite over the deviation sets arising in the standard correlated-equilibrium definition. This step confirms that concavity is preserved under the reduction and supports the Contr-hardness transfer. revision: yes

  2. Referee: [Swap regret lower bound] Theorem on information-theoretic lower bound (swap-regret section): the exponential dependence on d for achieving 1/poly(d) average swap regret is stated unconditionally, but the precise exponent and the precise notion of 'strongly sublinear' should be cross-referenced to the exact statement of the minimax theorem used, to confirm no hidden dependence on game parameters.

    Authors: We thank the referee for this suggestion. We will revise the theorem statement and the surrounding text in the swap-regret section to include an explicit cross-reference to the minimax theorem (including its precise statement), specify the exponential dependence (e.g., requiring 2^Ω(d) iterations), and define 'strongly sublinear' as o(2^d / poly(d)) iterations. The revised text will also confirm that the bound is unconditional and contains no hidden dependence on other game parameters. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on explicit reduction from external fixed-point problem

full rationale

The paper's central hardness result for correlated equilibria in concave quadratic games is established via a direct reduction that encodes the contraction mapping fixed-point condition into the equilibrium deviation inequalities while preserving quadratic concavity of the payoffs (with concavity following from the contraction constant being strictly less than 1). This construction uses standard game-theoretic definitions of correlated equilibrium and does not reduce any claimed prediction or result to quantities defined in terms of the paper's own fitted parameters, self-citations, or ansatzes. External citations such as Papadimitriou and Roughgarden (JACM '08) provide independent context rather than load-bearing justification. The FPTAS for Φ-equilibria and other algorithmic results are likewise derived from explicit polynomial-time constructions without self-referential loops. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rely on standard mathematical assumptions from complexity theory and convex analysis together with domain assumptions about concavity and quadratic structure of payoff functions; no new free parameters or invented entities are introduced.

axioms (2)
  • domain assumption Concave quadratic games are a well-defined class closed under the relevant operations for equilibrium computation
    Invoked when stating hardness for this specific game class in the abstract
  • standard math Standard notions of correlated equilibrium and swap regret apply directly to extensive-form and concave games
    Background assumption underlying all complexity statements

pith-pipeline@v0.9.0 · 5885 in / 1470 out tokens · 45773 ms · 2026-05-19T22:00:40.630042+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

81 extracted references · 81 canonical work pages

  1. [1]

    First-order (coarse) correlated equilibria in non-concave games

    Mete S eref Ahunbay. First-order (coarse) correlated equilibria in non-concave games. In Symposium on Theory of Computing (STOC), 2026

    work page 2026

  2. [2]

    On the complexity of computing sparse equilibria and lower bounds for no-regret learning in games

    Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, and Manolis Zampetakis. On the complexity of computing sparse equilibria and lower bounds for no-regret learning in games. In Innovations in Theoretical Computer Science (ITCS), 2024

    work page 2024

  3. [3]

    Pareto-optimal algorithms for learning in games

    Eshwar Ram Arunachaleswaran, Natalie Collina, and Jon Schneider. Pareto-optimal algorithms for learning in games. In Dirk Bergemann, Robert Kleinberg, and Daniela Sab \' a n, editors, ACM Conference on Economics and Computation (EC), 2024

    work page 2024

  4. [4]

    Swap regret and correlated equilibria beyond normal-form games

    Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Swap regret and correlated equilibria beyond normal-form games. In ACM Conference on Economics and Computation (EC), 2025

    work page 2025

  5. [5]

    On the value of correlation

    Itai Ashlagi, Dov Monderer, and Moshe Tennenholtz. On the value of correlation. Journal of Artificial Intelligence Research, 33: 0 575--613, 2008

    work page 2008

  6. [6]

    Subjectivity and correlation in randomized strategies

    Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1: 0 67--96, 1974

    work page 1974

  7. [7]

    Query complexity of approximate N ash equilibria

    Yakov Babichenko. Query complexity of approximate N ash equilibria. Journal of the ACM, 63 0 (4): 0 36:1--36:24, 2016

    work page 2016

  8. [8]

    Communication complexity of approximate nash equilibria

    Yakov Babichenko and Aviad Rubinstein. Communication complexity of approximate nash equilibria. In Symposium on Theory of Computing (STOC), 2017

    work page 2017

  9. [9]

    Communication complexity of nash equilibrium in potential games

    Yakov Babichenko and Aviad Rubinstein. Communication complexity of nash equilibrium in potential games. In Symposium on Foundations of Computer Science (FOCS), 2020

    work page 2020

  10. [10]

    Settling the complexity of N ash equilibrium in congestion games

    Yakov Babichenko and Aviad Rubinstein. Settling the complexity of N ash equilibrium in congestion games. In Symposium on Theory of Computing (STOC), 2021

    work page 2021

  11. [11]

    Efficient phi-regret minimization in extensive-form games via online mirror descent

    Yu Bai, Chi Jin, Song Mei, Ziang Song, and Tiancheng Yu. Efficient phi-regret minimization in extensive-form games via online mirror descent. In Neural Information Processing Systems (NeurIPS), 2022

    work page 2022

  12. [12]

    From external to internal regret

    Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8: 0 1307--1324, 2007

    work page 2007

  13. [13]

    La th \'e orie du jeu et les \'e quations int \'e gralesa noyau sym \'e trique

    Emile Borel. La th \'e orie du jeu et les \'e quations int \'e gralesa noyau sym \'e trique. Comptes rendus de l’Acad \'e mie des Sciences , 173 0 (1304-1308): 0 58, 1921

    work page 1921

  14. [14]

    On tractable -equilibria in non-concave games

    Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen - Yu Wei, and Weiqiang Zheng. On tractable -equilibria in non-concave games. In Neural Information Processing Systems (NeurIPS), 2024

    work page 2024

  15. [15]

    Proximal regret and proximal correlated equilibria: A new tractable solution concept for online learning and games

    Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen - Yu Wei, and Weiqiang Zheng. Proximal regret and proximal correlated equilibria: A new tractable solution concept for online learning and games. In Symposium on Theory of Computing (STOC), 2026

    work page 2026

  16. [16]

    Prediction, learning, and games

    Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006

    work page 2006

  17. [17]

    Settling the complexity of computing two-player N ash equilibria

    Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player N ash equilibria. Journal of the ACM, 2009

    work page 2009

  18. [18]

    Computing a fixed point of contraction maps in polynomial queries

    Xi Chen, Yuhao Li, and Mihalis Yannakakis. Computing a fixed point of contraction maps in polynomial queries. Journal of the ACM, 2025

    work page 2025

  19. [19]

    Quadratic speedup for computing contraction fixed points

    Xi Chen, Yuhao Li, and Mihalis Yannakakis. Quadratic speedup for computing contraction fixed points. arXiv:2602.10296, 2026

    work page arXiv 2026

  20. [20]

    On the complexity of the optimal correlated equilibria in extensive-form games

    Vincent Cheval, Florian Horn, Soumyajit Paul, and Mahsa Shirmohammadi. On the complexity of the optimal correlated equilibria in extensive-form games. arXiv:2507.11509, 2025

    work page arXiv 2025

  21. [21]

    The complexity of stochastic games

    Anne Condon. The complexity of stochastic games. Information and Computation, 96 0 (2): 0 203--224, 1992

    work page 1992

  22. [22]

    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 Symposium on Theory of Computing (STOC), 2024

    work page 2024

  23. [23]

    Non-concave games: A challenge for game theory’s next 100 years, 2021

    Constantinos Daskalakis. Non-concave games: A challenge for game theory’s next 100 years, 2021. Written on the occasion of the Nobel Symposium ``One Hundred Years of Game Theory: Future Applications and Challenges,'' held in Stockholm in December 2021

    work page 2021

  24. [24]

    The complexity of computing a N ash equilibrium

    Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou. The complexity of computing a N ash equilibrium. SIAM Journal on Computing, 2008

    work page 2008

  25. [25]

    A converse to banach's fixed point theorem and its cls-completeness

    Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis. A converse to banach's fixed point theorem and its cls-completeness. In Symposium on Theory of Computing (STOC), 2018

    work page 2018

  26. [26]

    Efficient learning and computation of linear correlated equilibrium in general convex games

    Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Charilaos Pipis, and Jon Schneider. Efficient learning and computation of linear correlated equilibrium in general convex games. In Symposium on Theory of Computing (STOC), pages 542--553, 2025

    work page 2025

  27. [27]

    Strategizing against no-regret learners

    Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against no-regret learners. In Neural Information Processing Systems (NeurIPS), 2019

    work page 2019

  28. [28]

    On the complexity of N ash equilibria and other fixed points (extended abstract)

    Kousha Etessami and Mihalis Yannakakis. On the complexity of N ash equilibria and other fixed points (extended abstract). In Symposium on Foundations of Computer Science (FOCS), 2007

    work page 2007

  29. [29]

    Polynomial-time computation of exact P hi-equilibria in polyhedral games

    Gabriele Farina and Charilaos Pipis. Polynomial-time computation of exact P hi-equilibria in polyhedral games. In Neural Information Processing Systems (NeurIPS), 2024

    work page 2024

  30. [30]

    Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium

    Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium. Journal of the ACM, 69 0 (6): 0 41:1--41:41, 2022

    work page 2022

  31. [31]

    Unique end of potential line

    John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique end of potential line. Journal of Computer and System Sciences, 114: 0 1--35, 2020

    work page 2020

  32. [32]

    High-dimensional calibration from swap regret

    Maxwell Fishelson, Noah Golowich, Mehryar Mohri, and Jon Schneider. High-dimensional calibration from swap regret. In Neural Information Processing Systems (NeurIPS), 2025 a

    work page 2025

  33. [33]

    Full swap regret and discretized calibration

    Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Renato Paes Leme, Jon Schneider, and Yifeng Teng. Full swap regret and discretized calibration. In Algorithmic Learning Theory (ALT), 2025 b

    work page 2025

  34. [34]

    Calibrated learning and correlated equilibrium

    Dean Foster and Rakesh Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21: 0 40--55, 1997

    work page 1997

  35. [35]

    Forecast hedging and calibration

    Dean P Foster and Sergiu Hart. Forecast hedging and calibration. Journal of Political Economy, 129 0 (12): 0 3447--3490, 2021

    work page 2021

  36. [36]

    C alibeating

    Dean P Foster and Sergiu Hart. “ C alibeating”: Beating forecasters at their own game. Theoretical Economics, 18 0 (4): 0 1441--1474, 2023

    work page 2023

  37. [37]

    Foster, Noah Golowich, and Sham M

    Dylan J. Foster, Noah Golowich, and Sham M. Kakade. Hardness of independent learning and sparse equilibrium computation in markov games. In International Conference on Machine Learning (ICML), 2023

    work page 2023

  38. [38]

    Bayes correlated equilibria and no-regret dynamics

    Kaito Fujii. Bayes correlated equilibria and no-regret dynamics. arXiv:2304.05005, 2023

    work page arXiv 2023

  39. [39]

    Near-optimal communication lower bounds for approximate nash equilibria

    Mika G \" o \" o s and Aviad Rubinstein. Near-optimal communication lower bounds for approximate nash equilibria. SIAM Journal on Computing, 52 0 (6): 0 S18--316, 2023

    work page 2023

  40. [40]

    Swap agnostic learning, or characterizing omniprediction via multicalibration

    Parikshit Gopalan, Michael Kim, and Omer Reingold. Swap agnostic learning, or characterizing omniprediction via multicalibration. In Neural Information Processing Systems (NeurIPS), 2023

    work page 2023

  41. [41]

    No-regret learning in convex games

    Geoffrey J Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In International Conference on Machine Learning (ICML), 2008

    work page 2008

  42. [42]

    A general class of no-regret learning algorithms and game-theoretic equilibria

    Amy Greenwald and Amir Jafari. A general class of no-regret learning algorithms and game-theoretic equilibria. In Conference on Learning Theory (COLT), 2003

    work page 2003

  43. [43]

    Geometric algorithms and combinatorial optimization

    Martin Gr \"o tschel, L \'a szl \'o Lov \'a sz, and Alexander Schrijver. Geometric algorithms and combinatorial optimization. Springer, 1993

    work page 1993

  44. [44]

    Fixed points of nonexpanding maps

    Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73 0 (6): 0 957--961, 1967

    work page 1967

  45. [45]

    A simple adaptive procedure leading to correlated equilibrium

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

    work page 2000

  46. [46]

    Introduction to online convex optimization

    Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2 0 (3-4): 0 157--325, 2016

    work page 2016

  47. [47]

    Computational equivalence of fixed points and no regret algorithms, and convergence to equilibria

    Elad Hazan and Satyen Kale. Computational equivalence of fixed points and no regret algorithms, and convergence to equilibria. In Neural Information Processing Systems (NIPS), 2007

    work page 2007

  48. [48]

    Calibration error for decision making

    Lunjia Hu and Yifan Wu. Calibration error for decision making. In Symposium on Foundations of Computer Science (FOCS), 2024

    work page 2024

  49. [49]

    Approximating fixed points of weakly contracting mappings

    Z Huang, Leonid Khachiyan, and Krzysztof Sikorski. Approximating fixed points of weakly contracting mappings. Journal of complexity, 15 0 (2): 0 200--213, 1999

    work page 1999

  50. [50]

    Fast algorithms for finding randomized strategies in game trees

    Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel . Fast algorithms for finding randomized strategies in game trees. In Proceedings of the 26 th ACM S ymposium on T heory of C omputing ( STOC ) , 1994

    work page 1994

  51. [51]

    On the convergence rate of the H alpern-iteration

    Felix Lieder. On the convergence rate of the H alpern-iteration. Optimization Letters, 15 0 (2): 0 405--418, 2021

    work page 2021

  52. [52]

    M arkov games as a framework for multi-agent reinforcement learning

    Michael Littman. M arkov games as a framework for multi-agent reinforcement learning. In International Conference on Machine Learning (ICML), pages 157--163, 1994

    work page 1994

  53. [53]

    Sample efficient omniprediction and downstream swap regret for non-linear losses

    Jiuyao Lu, Aaron Roth, and Mirah Shi. Sample efficient omniprediction and downstream swap regret for non-linear losses. In Conference on Learning Theory (COLT), 2025

    work page 2025

  54. [54]

    Constant rank bimatrix games are ppad-hard

    Ruta Mehta. Constant rank bimatrix games are ppad-hard. In Symposium on Theory of Computing (STOC), 2014

    work page 2014

  55. [55]

    Moulin and J.-P

    H. Moulin and J.-P. Vial. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7 0 (3-4): 0 201--221, 1978

    work page 1978

  56. [56]

    Equilibrium points in n-person games

    John Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36: 0 48--49, 1950

    work page 1950

  57. [57]

    Accuracy certificates for computational problems with convex structure

    Arkadi Nemirovski, Shmuel Onn, and Uriel G Rothblum. Accuracy certificates for computational problems with convex structure. Mathematics of Operations Research, 35 0 (1): 0 52--78, 2010

    work page 2010

  58. [58]

    High-dimensional prediction for sequential decision making

    Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. High-dimensional prediction for sequential decision making. In International Conference on Machine Learning (ICML), 2025

    work page 2025

  59. [59]

    Papadimitriou and Tim Roughgarden

    Christos H. Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM, 55 0 (3): 0 14:1--14:29, 2008

    work page 2008

  60. [60]

    Papadimitriou, Emmanouil - Vasileios Vlatakis - Gkaragkounis, and Manolis Zampetakis

    Christos H. Papadimitriou, Emmanouil - Vasileios Vlatakis - Gkaragkounis, and Manolis Zampetakis. The computational complexity of multi-player concave games and kakutani fixed points. In ACM Conference on Economics and Computation (EC), 2023

    work page 2023

  61. [61]

    High dimensional online calibration in polynomial time

    Binghui Peng. High dimensional online calibration in polynomial time. In Symposium on Foundations of Computer Science (FOCS), 2025

    work page 2025

  62. [62]

    The complexity of approximate (coarse) correlated equilibrium for incomplete information games

    Binghui Peng and Aviad Rubinstein. The complexity of approximate (coarse) correlated equilibrium for incomplete information games. In Conference on Learning Theory (COLT), 2024 a

    work page 2024

  63. [63]

    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 Symposium on Theory of Computing (STOC), 2024 b

    work page 2024

  64. [64]

    Existence and uniqueness of equilibrium points for concave n-person games

    J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica: Journal of the Econometric Society, pages 520--534, 1965

    work page 1965

  65. [65]

    A class of games possessing pure-strategy N ash equilibria

    Robert W Rosenthal. A class of games possessing pure-strategy N ash equilibria. International Journal of Game Theory, 2: 0 65--67, 1973

    work page 1973

  66. [66]

    Forecasting for swap regret for all downstream agents

    Aaron Roth and Mirah Shi. Forecasting for swap regret for all downstream agents. In Conference on Economics and Computation (EC), 2024

    work page 2024

  67. [67]

    Routing games

    Tim Roughgarden. Routing games. In Algorithmic Game Theory, chapter 18, pages 461--486. Cambridge University Press, 2007

    work page 2007

  68. [68]

    On the communication complexity of approximate fixed points

    Tim Roughgarden and Omri Weinstein. On the communication complexity of approximate fixed points. In Symposium on Foundations of Computer Science (FOCS), 2016

    work page 2016

  69. [69]

    Strategizing against no-regret learners in first-price auctions

    Aviad Rubinstein and Junyao Zhao. Strategizing against no-regret learners in first-price auctions. In Dirk Bergemann, Robert Kleinberg, and Daniela Sab \' a n, editors, Conference on Economics and Computation (EC), 2024

    work page 2024

  70. [70]

    Extreme equilibria: the benefits of correlation

    Kirill Rudov, Fedor Sandomirskiy, and Leeat Yariv. Extreme equilibria: the benefits of correlation. In ACM Conference on Economics and Computation (EC), 2025

    work page 2025

  71. [71]

    Stochastic games

    Lloyd S Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39: 0 1095--1100, 1953 a

    work page 1953

  72. [72]

    A value for n-person games

    Lloyd S Shapley. A value for n-person games. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, volume 2 of Annals of Mathematics Studies, 28, pages 307--317. Princeton University Press, 1953 b

    work page 1953

  73. [73]

    Multiagent systems: Algorithmic, game-theoretic, and logical foundations

    Yoav Shoham and Kevin Leyton-Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008

    work page 2008

  74. [74]

    An ellipsoid algorithm for the computation of fixed points

    K Sikorski, Chey-Woei Tsay, and H Wo \'z niakowski. An ellipsoid algorithm for the computation of fixed points. Journal of Complexity, 9 0 (1): 0 181--200, 1993

    work page 1993

  75. [75]

    Internal regret in on-line portfolio selection

    Gilles Stoltz and G \'a bor Lugosi. Internal regret in on-line portfolio selection. Machine Learning, 59 0 (1-2): 0 125--159, 2005

    work page 2005

  76. [76]

    Learning correlated equilibria in games with compact sets of strategies

    Gilles Stoltz and G \' a bor Lugosi. Learning correlated equilibria in games with compact sets of strategies. Games Econ. Behav., 59 0 (1): 0 187--208, 2007

    work page 2007

  77. [77]

    Efficient computation of behavior strategies

    Bernhard von Stengel . Efficient computation of behavior strategies. Games and Economic Behavior, 14 0 (2): 0 220--246, 1996

    work page 1996

  78. [78]

    Extensive-form correlated equilibrium: Definition and computational complexity

    Bernhard von Stengel and Fran c oise Forges. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, 33 0 (4): 0 1002--1022, 2008

    work page 2008

  79. [79]

    Efficient -regret minimization with low-degree swap deviations in extensive-form games

    Brian Hu Zhang, Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm. Efficient -regret minimization with low-degree swap deviations in extensive-form games. In Neural Information Processing Systems (NeurIPS), 2024

    work page 2024

  80. [80]

    Expected variational inequalities

    Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, and Tuomas Sandholm. Expected variational inequalities. arXiv:2502.18605, 2025 a

    work page arXiv 2025

Showing first 80 references.