Pith. sign in

REVIEW 3 major objections 5 minor 53 references

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The threshold problem for normal-form correlated equilibria in multiplayer extensive-form games with perfect recall is PSPACE-hard.

desk verdict Serious paper with a real bug in the NFCE reduction's payoff rule; results are probably right after a fix, but the current write-up is internally inconsistent. read the letter →

arxiv 2507.11509 v2 pith:WZZZEM2M submitted 2025-07-15 cs.GT cs.CC

Vincent Cheval , Florian Horn , Soumyajit Paul , Mahsa Shirmohammadi This is my paper · ORCID
classification cs.GTcs.CC MSC 91A1868Q1791A1068Q25
keywords extensive-formgamesnormal-formcorrelatedequilibriumthresholdproblemPSPACE-hardperfectrecallagent-formsupportsize
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper settles a central open question about correlated equilibria in sequential games: it proves that deciding whether there is a normal-form correlated equilibrium (NFCE) with social welfare above a given threshold is PSPACE-hard, even for a fixed threshold value, in multiplayer extensive-form games with perfect recall. This means that, unless P = PSPACE, no polynomial-time algorithm can find optimal NFCE in such games, and there exist polynomial-size games whose optimal equilibria require exponentially large correlation plans. The result is surprising because in normal-form games the identical threshold problem is polynomial-time solvable for correlated equilibria; the paper shows the complexity order reverses in extensive-form games. The paper also completes the complexity picture for other correlated equilibrium concepts, showing that the threshold problem is NP-complete for extensive-form, agent-form, and coarse correlated equilibria, and that it is NP-hard for agent-form correlated equilibrium even in two-player games without chance nodes, answering an open question posed in the literature.

What carries the argument

The key mechanism is a family of gadgets built into the game tree: an uncertainty gadget and a knowledge gadget for each universally quantified variable. The uncertainty gadget pays the universal player 2 for correctly guessing the assignment to that variable, 0 for a wrong guess, and 1 for playing the safe check action, so any correlation plan is an equilibrium only if, conditioned on everything that player knows, the two truth values are equally likely. The knowledge gadget pays the formula player 3 when the universal player correctly guesses an earlier variable's assignment, so that in any welfare-3 equilibrium each universal player must know all earlier assignments. Together these gadgets force the correlation plan to be uniform over exactly the assignments that respect the quantifier prefix, which links the game's equilibria to the truth of the quantified formula. The correctness proof rests on the gap lemma: any non-good pure strategy profile has expected welfare at most $3 - 1/(2n(n+1))$, which follows from a lower bound of $1/(2n(n+1))$ on the probability of reaching any leaf.

What would settle it

Run the reduction on a specific false quantified Boolean formula (for example $\forall y_1 \exists x_1 \, (x_1 \land \neg x_1)$) and compute, by exhaustive search for small $n$, the maximum social welfare over all NFCE of the constructed game; if an NFCE achieves welfare 3 for a false formula, the reduction's correctness (Proposition 6) fails. Alternatively, verify the gap lemma's leaf-probability lower bound $\mathrm{PC}(v) \ge 1/(2n(n+1))$ by enumerating all leaves of the constructed game and checking the minimum product of chance probabilities; if any leaf has probability below that bound, the lemma fails.

Watch

Extended reading notes

Core claim

The central discovery is a polynomial-time reduction from the Quantified Boolean Formula (QBF) problem to the Threshold problem for normal-form correlated equilibria (NFCE) in multiplayer extensive-form games with perfect recall: the constructed game has an NFCE with expected social welfare 3 if and only if the quantified formula is true. The construction uses uniformly random chance moves together with an assignment player, a formula player, and one universal player per universally quantified variable; the equilibrium incentives force the universal players to be indifferent between guessing true or false, which in turn forces the correlation plan to be uniform over assignments consistent with the quantifier prefix. Any strategy profile that is not good in the sense of the reduction has expected welfare at most $3 - 1/(2n(n+1))$, so a welfare of exactly 3 is achievable only by good profiles, and those exist precisely when the QBF is true. A consequence is that optimal NFCE can require exponential support, and thus cannot always be represented succinctly.

Load-bearing premise

The load-bearing assumption is the gap bound: every non-good strategy profile has social welfare at most $3 - 1/(2n(n+1))$; if that bound failed for any game in the reduction, a mixture of non-good profiles could reach welfare 3 and break the equivalence with the truth of the quantified formula.

Editorial extensions

If this is right

  • Unless P = PSPACE, the Threshold problem for normal-form correlated equilibria in multiplayer extensive-form games has no polynomial-time algorithm, even for fixed thresholds.
  • There exist polynomial-size extensive-form games in which every optimal NFCE requires a correlation plan with exponential support, so optimal NFCE cannot be represented succinctly in general.
  • Combined with the result that Threshold-Nash is $\exists\mathbb{R}$-complete in this setting, optimal NFCE is provably harder than optimal Nash in extensive-form games (unless $\exists\mathbb{R} = $ PSPACE), reversing the complexity order that holds in normal-form games.
  • The Threshold problem is NP-complete for extensive-form correlated equilibrium (EFCE), extensive-form coarse correlated equilibrium (EFCCE), normal-form coarse correlated equilibrium (NFCCE), agent-form correlated equilibrium (AFCE), and agent-form coarse correlated equilibrium (AFCCE), each with a polynomial-size support representation.
  • The Threshold problem for AFCE and AFCCE is NP-hard even in two-player extensive-form games without chance nodes, answering a long-standing open question in the literature.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the PSPACE-hardness extends to two-player or constant-player games, the Threshold problem for NFCE would be PSPACE-hard in essentially the same range where the Any problem is still open, strengthening the suspicion that computing any NFCE is hard in general.
  • The exponential-support result suggests that approximate or regret-based algorithms for NFCE in extensive-form games face a representational barrier: any method that outputs a compact correlation plan cannot in general reach the exact optimum.
  • The gap of $1/(2n(n+1))$ implies that distinguishing welfare 3 from welfare $3 - 1/(2n(n+1))$ is already PSPACE-hard, so even additive approximation within that gap is intractable unless P = PSPACE.
  • The NP upper bounds for EFCE, EFCCE, NFCCE, AFCE, and AFCCE rely on Carathéodory's theorem to guess a small support; this suggests that only the normal-form variant, with its exponential-support lower bound, escapes polynomial-size representability among the correlated equilibrium concepts studied.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies the Threshold problem (does there exist an equilibrium with social welfare above a given value) for several correlated-equilibrium concepts in multiplayer extensive-form games with perfect recall. Its central contribution is a PSPACE-hardness result for normal-form correlated equilibria (NFCE) via a polynomial-time reduction from Quantified Boolean Formulas, together with a claimed matching-context result that the Threshold problem for Nash equilibria in this setting is ∃R-complete. The paper also gives NP-completeness classifications for EFCE, EFCCE, NFCCE, AFCE, and AFCCE by introducing a unified framework of leaf-based relevant histories and applying Carathéodory's theorem to bound equilibrium support size. A separate reduction answers an open question of von Stengel and Forges by showing NP-hardness for AFCE and AFCCE in two-player games without chance nodes.

Significance. If the results hold, the paper substantially advances the complexity landscape for equilibrium computation in extensive-form games: it resolves the open AFCE/AFCCE threshold question, provides the first PSPACE-hardness lower bound for optimal NFCE, and gives a clean, uniform technique for polynomial-size relevant histories that yields NP upper bounds for several equilibrium concepts. The Carathéodory-based support-size argument and the layered uncertainty/knowledge gadgets in the QBF reduction are original and reusable technical ideas. The paper also explicitly derives a consequence of independent interest: there are polynomial-size extensive-form games in which every optimal NFCE requires exponentially large support. These are significant contributions. However, the central NFCE reduction as written contains an internal inconsistency in the formula-gadget payoff rule that contradicts the main lemma of the reduction, and the claimed ∃R-completeness and FixP results are not fully supported in the manuscript. Both issues are fixable in revision, but they must be addressed before the paper can be accepted.

major comments (3)
  1. [Appendix D.1, Lemma 5] The payoff rule for the formula gadget is written incorrectly and contradicts Lemma 5. The text says that playing action t_k from node F_ℓ yields payoff 0 'if the literal ℓ makes the term t_k false, i.e. ℓ ∈ {ℓ_{k,1}, ℓ_{k,2}, ℓ_{k,3}} when ℓ ∈ Z or, z ∈ {ℓ_{k,1}, ℓ_{k,2}, ℓ_{k,3}} when ℓ = z̄.' Under the first disjunct, a positive literal that belongs to t_k always yields payoff 0. Take a good strategy profile σ with a positive literal ℓ ∈ t_k that is true under θσ; the play reaches F_ℓ and the φ-player is recommended t_k, so the leaf payoff is 0 rather than 3. Hence E_{δσ}(ω) < 3, contradicting Lemma 5 and Corollary 1, which are the basis of Propositions 5 and 6 and therefore of Theorem 1. The same mistake appears in the illustrative example in Section 3, where the term t2 = x1∧x2∧x3 is said to be falsified by x1 = true. The intended rule is presumably that payoff 0 occurs when the complementary literal appears in t_k, i.e. z̄ ∈ {ℓ_{k,1}, ℓ_{k,2}, ℓ_{k,3}} when ℓ = z and z ∈ {ℓ_{k,1}, ℓ_{k,2}, ℓ_{k,3}} when ℓ = z̄. With that correction, the good-profile characterization in Lemma 5 goes through, but as written the reduction is internally inconsistent and must be corrected, along with the example in Section 3.
  2. [Appendix G, Abstract] Proposition 1 is stated as a complete ∃R-completeness result, but Appendix G contains only a sketch of the membership direction. The ∃R-hardness is not proved or reduced in the manuscript; it is only attributed to the normal-form result [BM16] in Figure 1, without spelling out the embedding of normal-form games into extensive-form games or the handling of the number of players. Moreover, the abstract asserts that computing an arbitrary Nash equilibrium in extensive-form games lies in FixP, but no statement, proof, or section in the body supports this assertion. Since the paper's 'complexity reversal' narrative relies on the exact complexity of the Nash Threshold problem, both claims need to be supported either by full proofs or by explicit statements that they are inherited with a precise reduction, or the abstract claims should be qualified.
  3. [Section 3 / Appendix D, 'Beyond Chance'] The paragraph 'Beyond Chance: from Stochastic to Non-Stochastic Games' describes a transformation that removes chance nodes by generalizing a gadget of von Stengel and Forges, but no formal theorem is stated for the resulting deterministic setting and no correctness proof is given. If the authors intend Theorem 1 or a separate theorem to cover games without chance nodes, the construction and its proof must be made precise; if not, the paragraph should be clearly marked as informal or removed.
minor comments (5)
  1. [Appendix D.1] There is a typo in the definition of the assignment player's actions: 'Az ⊤− →Cz and Az ⊤− →Cz' should have one ⊤ and one ⊥, and the notation for the two chance successors C_z and C_{z̄} should be introduced consistently.
  2. [Appendix D.1] The reduction assumes a fully alternating prefix ∃x1∀y1...∃xn∀yn, but arbitrary QBF formulas are not necessarily of this form; a sentence explaining that every QBF can be normalized to this form in logarithmic space (e.g., by adding dummy quantifiers) is needed.
  3. [Propositions 5 and 6] The notation E_{µP}(U_{i+2} | α) and E_{µP}(U_{i+2} | α ⇝ β) appears in places where the intended plan is µ, not a plan indexed by P; this should be corrected for readability.
  4. [Appendix F.4] Proposition 10 refers to the set (C3(S, RAFCE)) but the intended relevant-history set is RAFCCE, and the statement contains a duplicated phrase 'There exists a correlation plan µ in AFCCE with' that should be removed.
  5. [Section 4 and Appendix C] The description of the relevant histories for EFCE in the main text would benefit from a short statement that the size bound |REFCE| ∈ O(n · |V| · |L| · |A|) is with respect to the game tree; as written, the bound is stated only in Appendix C.1.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main PSPACE-hardness, NP-hardness, and NP-membership proofs reduce to external benchmarks (QBF, 3SAT, Carathéodory) and do not rely on fitted parameters or load-bearing self-citation.

full rationale

I walked the derivation chain for each headline claim. Theorem 1 is a QBF-to-game reduction whose correctness is argued through Lemma 4 (minimal explicit proofs), Lemma 5 (good profiles characterize social welfare 3), and Propositions 5 and 6; none of these steps defines its conclusion into its premise. The game construction is explicit and the equilibrium verification is done from the formal NFCE constraints, not from an assumed representation. Lemma 5's gap bound is derived from Remark 1, which is a direct lower bound on chance-edge products. The NP upper bounds (Theorem 2 and Propositions 4, 7-10) use Carathéodory's theorem to bound support and then solve explicit polynomial-size linear systems; this is a standard external argument, not a renaming of the answer. The AFCE/AFCCE 3SAT reduction (Section 5, Appendix E) is similarly self-contained, with equilibrium conditions checked directly. Self-citations by M. Shirmohammadi ([KMS+20], [Shi23], [KMST25]) appear only in the introduction as background on strategy complexity and are not used in any proof. Separately, I note a genuine internal inconsistency in Appendix D.1: the formula-gadget payoff rule as written ('ℓ ∈ {ℓ_{k,1}, ℓ_{k,2}, ℓ_{k,3}} when ℓ ∈ Z') makes a positive literal appearing in a term yield payoff 0, contradicting Lemma 5 and the illustrative example in Section 3; this is a correctness defect in the reduction as written, not a circularity, and belongs under correctness rather than under circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities. The central claims rest on standard complexity-theoretic assumptions and game-theoretic definitions; the paper's constructions are reductions rather than empirical models.

assumptions (5)
  • standard math QBF is PSPACE-complete
    Used as the source problem for the NFCE PSPACE-hardness reduction in Section 3 and Appendix D.
  • standard math 3SAT is NP-complete
    Used as the source problem for the AFCE and AFCCE NP-hardness reduction in Section 5 and Appendix E.
  • standard math Carathéodory's theorem on convex hulls
    Used in Appendix C.3 to bound the support size of an optimal correlation plan by the number of relevant histories plus one.
  • standard math Kuhn's theorem on realization equivalence of mixed and behavioral strategies in perfect-recall games
    Used in Appendix G to encode Nash equilibria with behavioral strategies for the ∃R upper bound.
  • domain assumption Perfect recall
    The paper's equilibrium definitions and relevant-history construction assume players remember their own past actions and observations; stated in Section 2 and Appendix A.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games." pith.science (2026). https://pith.science/paper/WZZZEM2M

@misc{pith2026250711509,
  author       = {Pith},
  title        = {Pith review of: On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WZZZEM2M}},
  note         = {Machine review of arXiv:2507.11509}
}
read the original abstract

A major open question in algorithmic game theory is whether normal-form correlated equilibria (NFCE) can be computed efficiently in succinct games such as extensive-form games. Motivated by this question, we study the associated Threshold problem: deciding whether there exists a correlated equilibrium whose value exceeds a given threshold. We prove that this problem is PSPACE-hard for NFCE in multiplayer extensive-form games with perfect recall, even for fixed thresholds. To contextualize this result, we also establish the complexity of the Threshold problem for Nash equilibria in this setting, showing it is ER-complete. These results uncover a surprising complexity reversal: while optimal correlated equilibria are computationally simpler than optimal Nash in normal-form games, the opposite holds in extensive-form games, where computing optimal correlated equilibria is strictly harder unless ER is equal to PSPACE. We also address a related question by von Stengel and Forges, who introduced the notions of extensive-form correlated equilibrium (EFCE) and agent-form correlated equilibrium (AFCE). They asked how difficult the Threshold problem is for AFCE; we answer this question by proving that it is NP-hard, even in two-player games without chance nodes. Complementing our hardness results, we establish tight complexity classifications for the Threshold problem across several correlated equilibrium concepts - including EFCE, AFCE, normal-form coarse, extensive-form coarse, and agent-form coarse correlated equilibria. For each of these solution concepts in multiplayer stochastic extensive-form games with perfect recall, we prove NP-completeness by providing matching NP upper bounds to the previously known hardness results. Finally, we also place the problem of computing arbitrary Nash Equilibria in extensive-form games in FixP, matching its complexity in normal-form games.

Figures

Figures reproduced from arXiv: 2507.11509 by the authors.

Figure 1
Figure 1. Overview of known complexity results and our contributions (highlighted in green). [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Schematic view of the game G constructed in the coNP-hardness reduction from the formula φ over variables {x1, x2, x3}, given by ( x1 ∧ x2 ) | {z } term t1 W ( x1 ∧ x2 ∧ x3) | {z } term t2 W ( x2 ∧ x3 ) | {z } term t3 . The chance nodes are shown as triangles and the successors are chosen uniformly at random. The social welfare of the optimal correlated equilibrium in G is 3 if and only if φ is a tautology. x1 x1 x1… view at source ↗
Figure 3
Figure 3. Our newly defined family of relevant histories is tailored to the equilibrium concept under [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Schematic view of the game Gφ constructed in the NP-hardness reduction from the formula φ = x |{z} clause c1 V ( ¯x ∨ y) | {z } clause c2 V ( ¯x ∨ y¯) | {z } clause c3 deviation has occurred, the spoiler must follow the recommended strategy for the remainder of the gam…
Figure 5
Figure 5. Figure 5: Schematic view of the game G constructed in the PSPACE-hardness reduction from the formula Φ = ∃x1∀y1∃x2∀y2 ( x1 ∧ y¯2 ) | {z } term t1 W ( y1 ∧ x2 ∧ x1) | {z } term t2 W ( y1 ∧ x2 ) | {z } term t3 . The chance nodes are shown as triangles and the successors are chosen…
Figure 6
Figure 6. Figure 6: A Schematic view of how to remove the chance node in the game [PITH_FULL_IMAGE:figures/full_fig_p040_6.png]
Figure 7
Figure 7. Figure 7: Schematic view of the game Gφ constructed in the NP-hardness reduction from the formula φ = x |{z} clause c1 V ( ¯x ∨ y) | {z } clause c2 V ( ¯x ∨ y¯) | {z } clause c3 spoiler as player 1 and the φ-player as player 2. The game has a root node R that belongs to spoiler …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 51 canonical work pages

  1. [1]

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

    work page 1974

  2. [2]

    A catalog of exists-r-complete decision problems about nash equilibria in multi-player games

    Vittorio Bil \` o and Marios Mavronicolas. A catalog of exists-r-complete decision problems about nash equilibria in multi-player games. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orl \' e ans, France , volume 47 of LIPIcs , pages 17:1--17:13. Schloss Dags...

    work page 2016

  3. [3]

    Jean R. S. Blair, David Mutchler, and Michael van Lent. Perfect recall and pruning in games with imperfect information. Comput. Intell. , 12:131--154, 1996

    work page 1996

  4. [4]

    Computing optimal ex ante correlated equilibria in two-player sequential games

    Andrea Celli, Stefano Coniglio, and Nicola Gatti. Computing optimal ex ante correlated equilibria in two-player sequential games. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems , AAMAS '19, page 909–917, Richland, SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems

    work page 2019

  5. [5]

    Settling the complexity of two-player nash equilibrium

    Xi Chen and Xiaotie Deng. Settling the complexity of two-player nash equilibrium. In FOCS , volume 6, pages 261--272, 2006

    work page 2006

  6. [6]

    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

    work page 2006

  7. [7]

    Learning to correlate in multi-player general-sum sequential games

    Andrea Celli, Alberto Marchesi, Tommaso Bianchi, and Nicola Gatti. Learning to correlate in multi-player general-sum sequential games. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alch\' e -Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems , volume 32. Curran Associates, Inc., 2019

    work page 2019

  8. [8]

    Finding correlated equilibrium of constrained markov game: A primal-dual approach

    Ziyi Chen, Shaocong Ma, and Yi Zhou. Finding correlated equilibrium of constrained markov game: A primal-dual approach. Advances in Neural Information Processing Systems , 35:25560--25572, 2022

    work page 2022

Show all 53 references
  1. [9]

    New complexity results about nash equilibria

    Vincent Conitzer and Tuomas Sandholm. New complexity results about nash equilibria. Games and Economic Behavior , 63(2):621--641, 2008

    2008

  2. [10]

    On the complexity of approximating a nash equilibrium

    Constantinos Daskalakis. On the complexity of approximating a nash equilibrium. ACM Transactions on Algorithms (TALG) , 9(3):1--35, 2013

    2013

  3. [11]

    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 Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1216--1222, 2024

    2024

  4. [12]

    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. To Appear in STOC , 2025

    2025

  5. [13]

    Papadimitriou

    Constantinos Daskalakis, Alex Fabrikant, and Christos H. Papadimitriou. The game world is flat: The complexity of nash equilibria in succinct games. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd Inter...

    2006

  6. [14]

    The complexity of computing a nash equilibrium

    Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. Communications of the ACM , 52(2):89--97, 2009

    2009

  7. [15]

    On the complexity of nash equilibria and other fixed points

    Kousha Etessami and Mihalis Yannakakis. On the complexity of nash equilibria and other fixed points. SIAM Journal on Computing , 39(6):2531--2597, 2010

    2010

  8. [16]

    Coarse correlation in extensive-form games

    Gabriele Farina, Tommaso Bianchi, and Tuomas Sandholm. Coarse correlation in extensive-form games. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth ...

    2020

  9. [17]

    Connecting optimal ex-ante collusion in teams to extensive-form correlation: Faster algorithms and positive complexity results

    Gabriele Farina, Andrea Celli, Nicola Gatti, and Tuomas Sandholm. Connecting optimal ex-ante collusion in teams to extensive-form correlation: Faster algorithms and positive complexity results. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conf...

    2021

  10. [18]

    Five legitimate definitions of correlated equilibrium in games with incomplete information

    Fran c oise Forges. Five legitimate definitions of correlated equilibrium in games with incomplete information. Theory and Decision , 35(3):277--310, 1993

    1993

  11. [19]

    Polynomial-time linear-swap regret minimization in imperfect-information sequential games

    Gabriele Farina and Charilaos Pipis. Polynomial-time linear-swap regret minimization in imperfect-information sequential games. Advances in Neural Information Processing Systems , 36:28255--28280, 2023

    2023

  12. [20]

    The complexity of pure nash equilibria

    Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The complexity of pure nash equilibria. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , pages 604--612, 2004

    2004

  13. [21]

    Polynomial-time computation of optimal correlated equilibria in two-player extensive-form games with public chance moves and beyond

    Gabriele Farina and Tuomas Sandholm. Polynomial-time computation of optimal correlated equilibria in two-player extensive-form games with public chance moves and beyond. NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc

    2020

  14. [22]

    Bayes correlated equilibria and no-regret dynamics

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

    2023 arXiv

  15. [23]

    Garey and David S

    Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, 1979

    1979

  16. [24]

    Goldberg and Christos H

    Paul W. Goldberg and Christos H. Papadimitriou. Reducibility among equilibrium problems. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing , STOC '06, page 61–70, New York, NY, USA, 2006. Association for Computing Machinery

    2006

  17. [25]

    Goodfellow, Jean Pouget - Abadie, Mehdi Mirza, Bing Xu, David Warde - Farley, Sherjil Ozair, Aaron C

    Ian J. Goodfellow, Jean Pouget - Abadie, Mehdi Mirza, Bing Xu, David Warde - Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advan...

    2014

  18. [26]

    Nash and correlated equilibria: Some complexity considerations

    Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior , 1(1):80--93, 1989

    1989

  19. [27]

    Finding equilibria in games of no chance

    Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and Troels Bjerre S rensen. Finding equilibria in games of no chance. In Guohui Lin, editor, Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings , volume 4...

    2007

  20. [28]

    Computing an extensive-form correlated equilibrium in polynomial time

    Wan Huang and Bernhard von Stengel. Computing an extensive-form correlated equilibrium in polynomial time. In International Workshop on Internet and Network Economics , pages 506--513. Springer, 2008

    2008

  21. [29]

    Polynomial-time computation of exact correlated equilibrium in compact games

    Albert Xin Jiang and Kevin Leyton - Brown. Polynomial-time computation of exact correlated equilibrium in compact games. Games Econ. Behav. , 91:347--359, 2015

    2015

  22. [30]

    u cken, Germany (Virtual Conference) , volume 168 of LIPIcs , pages 3:1--3:18. Schloss Dagstuhl - Leibniz-Zentrum f \

    Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke, and Dominik Wojtczak. How to play in infinite mdps (invited talk). In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, J...

    2020

  23. [31]

    Strategy complexity of B üchi objectives in concurrent stochastic games

    Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Patrick Totzke. Strategy complexity of B üchi objectives in concurrent stochastic games. 2025. To appear in EC 2025

    2025

  24. [32]

    Efficient computation of equilibria for extensive two-person games

    Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel . Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior , 14(2):247--259, 1996

    1996

  25. [33]

    Auction theory

    Vijay Krishna. Auction theory . Academic press, 2009

    2009

  26. [34]

    H. W. Kuhn. 11. Extensive Games and the Problem of Information , pages 193--216. Princeton University Press, Princeton, 1953

    1953

  27. [35]

    A decentralized parallel algorithm for training generative adversarial nets

    Mingrui Liu, Wei Zhang, Youssef Mroueh, Xiaodong Cui, Jarret Ross, Tianbao Yang, and Payel Das. A decentralized parallel algorithm for training generative adversarial nets. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria - Florina Balcan, and Hsuan - Tien Lin, ed...

    2020

  28. [36]

    Dustin Morrill, Ryan D'Orazio, Marc Lanctot, J. R. Wright, Michael H. Bowling, and Amy Greenwald. Efficient deviation types and learning for hindsight rationality in extensive-form games. ArXiv , abs/2102.06973, 2021

    2021 arXiv

  29. [37]

    Hindsight and sequential rationality of correlated play

    Dustin Morrill, Ryan D’Orazio, Reca Sarfati, Marc Lanctot, James R Wright, Amy R Greenwald, and Michael Bowling. Hindsight and sequential rationality of correlated play. Proceedings of the AAAI Conference on Artificial Intelligence , 35(6):5584--5594, May 2021

    2021

  30. [38]

    Moulin and J

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

    1978

  31. [39]

    Roger B. Myerson. Multistage games with communication. Econometrica , 54(2):323--358, 1986

    1986

  32. [40]

    The bitcoin lightning network: Scalable off-chain instant payments

    Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable off-chain instant payments. https://lightning.network/lightning-network-paper.pdf, 2016

    2016

  33. [41]

    Computing correlated equilibria in multi-player games

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

    2008

  34. [42]

    Modern applications of game-theoretic principles (invited paper)

    Catuscia Palamidessi and Marco Romanelli. Modern applications of game-theoretic principles (invited paper). In Igor Konnov and Laura Kov \' a cs, editors, 31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference...

    2020

  35. [43]

    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 Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1223--1234, 2024

    2024

  36. [44]

    Towards a Game-Theoretic Security Analysis of Off-Chain Protocols

    Sophie Rain, Georgia Avarikioti, Laura Kovacs, and Matteo Maffei. Towards a Game-Theoretic Security Analysis of Off-Chain Protocols . In 2023 IEEE 36th Computer Security Foundations Symposium (CSF) , pages 107--122, Los Alamitos, CA, USA, July 2023. IEEE Computer Society

    2023

  37. [45]

    A beginner's tutorial on strategy complexity in stochastic games: Can the king cautiously eliminate robin hood? ACM SIGLOG News , 9(4):27--43, 2023

    Mahsa Shirmohammadi. A beginner's tutorial on strategy complexity in stochastic games: Can the king cautiously eliminate robin hood? ACM SIGLOG News , 9(4):27--43, 2023

    2023

  38. [46]

    The computational complexity of nash equilibria in concisely represented games

    Grant R Schoenebeck and Salil Vadhan. The computational complexity of nash equilibria in concisely represented games. ACM Transactions on Computation Theory (TOCT) , 4(2):1--50, 2012

    2012

  39. [47]

    Computational complexity of correlated equilibria for extensive games

    Bernhard von Stengel. Computational complexity of correlated equilibria for extensive games. Technical report, Citeseer, 2001

    2001

  40. [48]

    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(4):1002--1022, 2008

    2008

  41. [49]

    Towards a bayesian network game framework for evaluating ddos attacks and defense

    Guanhua Yan, Ritchie Lee, Alex Kent, and David Wolpert. Towards a bayesian network game framework for evaluating ddos attacks and defense. In Proceedings of the 2012 ACM Conference on Computer and Communications Security , CCS '12, page 553–566, New York, NY, USA, 2012. Associ...

    2012

  42. [50]

    Efficiently solving turn-taking stochastic games with extensive-form correlation

    Hanrui Zhang, Yu Cheng, and Vincent Conitzer. Efficiently solving turn-taking stochastic games with extensive-form correlation. In Proceedings of the 24th ACM Conference on Economics and Computation , EC '23, page 1161–1186, New York, NY, USA, 2023. Association for Computing Machinery

    2023

  43. [51]

    Optimal correlated equilibria in general-sum extensive-form games: Fixed-parameter algorithms, hardness, and two-sided column-generation

    Brian Hu Zhang, Gabriele Farina, Andrea Celli, and Tuomas Sandholm. Optimal correlated equilibria in general-sum extensive-form games: Fixed-parameter algorithms, hardness, and two-sided column-generation. In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The ...

    2022

  44. [52]

    Game theory meets network security: A tutorial

    Quanyan Zhu and Stefan Rass. Game theory meets network security: A tutorial. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security , CCS '18, page 2163–2165, New York, NY, USA, 2018. Association for Computing Machinery

    2018

  45. [53]

    Polynomial-time optimal equilibria with a mediator in extensive-form games

    Brian Hu Zhang and Tuomas Sandholm. Polynomial-time optimal equilibria with a mediator in extensive-form games. In Proceedings of the 36th International Conference on Neural Information Processing Systems , NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc

    2022

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.