On the dimensions of correlated equilibrium polytopes of generic games

Irem Portakal; Jan Draisma; Linda Hoyer

REVIEW 1 major objections 4 minor 20 references

On the dimensions of correlated equilibrium polytopes of generic games

T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read Generic games reduce to full-dimensional subgame polytopes.

desk verdict The reduction idea and balanced-point toolkit are genuinely new, but the main theorem rests on a false induction base: maximal r(p) does not imply strict incentive constraints, so the proof as written is incomplete. read the letter →

arxiv 2608.04924 v1 pith:URRTSYHP submitted 2026-08-05 math.CO

Jan Draisma , Linda Hoyer , Irem Portakal This is my paper · ORCID

classification math.CO MSC 91A1052B1105B35

keywords correlatedequilibriumgenericgamespolytopedimensionorientedmatroidsubgamereductionaffineisomorphismfull-dimensionalgametheory

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

This paper studies the dimension of the correlated equilibrium polytope, the convex set of joint mixed strategies that are stable against unilateral deviations. For generic finite games, it claims that whenever this polytope is not full-dimensional, there is a proper subgame whose correlated equilibrium polytope is full-dimensional and affinely isomorphic to the original. This generalizes a 2024 conjecture for 2×n games. If true, it means the combinatorial shape of a generic game's correlated equilibria is fully captured by the smaller game formed by the strategies that actually appear with positive marginal probability.

What carries the argument

The argument runs on the coefficient matrix $A_G$ of the incentive and nonnegativity constraints and on oriented-matroid genericity: all nonzero maximal minors of $A_G$ are required to be nonzero, so the face poset of $P_G$ is constant on each oriented-matroid stratum. The internal engine is the slice-count function $r(p)$, which counts how many distinct normalized nonzero slices $\pi_{-i,k}(p)$ occur across all players; the proof pushes a correlated equilibrium through convex combinations and small payoff perturbations to raise $r(p)$ until, in the intended base case, all incentive constraints are strict.

What would settle it

Compute the generic Bach–Stravinsky game of Example 3.6 and take the point $p=(2/7,3/7,0,2/7)$: it is a correlated equilibrium with $r(p)=4=\sum_i d_i$, but the player-2 constraint comparing column 2 against column 1 holds with equality, directly refuting the induction's base-case premise that maximal $r(p)$ implies strictness of all incentive constraints.

Watch

Extended reading notes

Core claim

The paper's central claim is that the dimension defect of the correlated equilibrium polytope $P_G$ of a generic game $G$ is concentrated entirely on unused strategies. Let $S_c^{(i)}$ be the set of player $i$ strategies that occur with positive marginal probability in some correlated equilibrium, and let $\tilde G$ be the subgame on these strategy sets. Then $P_G$ is affinely isomorphic to $P_{\tilde G}$, and $P_{\tilde G}$ is either full-dimensional or a singleton. The proof strategy first establishes a sufficient condition: if a generic game has a correlated equilibrium $p$ whose every slice $p_{-i,k}$ is nonzero for all players $i$ and strategies $k$, then $P_G$ is either full-dimensional or a singleton. It then strips away strategies with zero marginal probability and applies this condition to the support subgame.

Load-bearing premise

The argument assumes that a correlated equilibrium whose normalized slices reach the maximum possible count must satisfy every deviation constraint strictly; the paper's own Bach–Stravinsky example has this maximum count yet one constraint holds with equality, so that premise fails as stated.

Editorial extensions

If this is right

For generic 2×n games, the earlier conjecture is settled: every non-full-dimensional correlated equilibrium polytope is affinely isomorphic to the full-dimensional polytope of a smaller 2×~n subgame.
If a generic game has a correlated equilibrium with every slice nonzero, intermediate dimensions are impossible: the polytope is either full-dimensional or a point.
The dimension of $P_G$ is determined by which pure strategies have positive marginal probability in some correlated equilibrium.
The reduction is strictly stronger than the classical dual reduction, because it preserves the entire polytope up to affine isomorphism rather than only one inclusion of equilibrium sets.
The affine-isomorphism statement gives a precise combinatorial meaning to the notion that only actively used strategies matter for the shape of correlated equilibria.

Reading between the lines

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

If the theorem survives repair, a natural next step is to make the reduction constructive, outputting the support subgame and an explicit affine isomorphism; that would provide a practical dimension-reduction routine for correlated-equilibrium computation.
The slice-count function $r(p)$ behaves like a tensor-rank witness, and the proof's technique of raising $r$ by convex combinations suggests an unexplored link between the dimension of $P_G$ and the tensor rank of points inside it.
The proof's base case assumes that maximal $r(p)$ forces all incentive constraints to be strict, but the paper's own Bach–Stravinsky example has a vertex with $r(p)=\sum_i d_i$ and a non-strict constraint, so a corrected argument needs another way to handle the maximal-$r$ case.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague—

The paper is worth a look: it attacks a real conjecture, and the main reduction idea is genuinely cleaner than Myerson's dual reduction. But the central proof has a load-bearing flaw, and I don't think Theorem 2.7/3.13 is established as written.

What's new: the balanced-point notion (Definition 3.3) and the perturbation Proposition 3.5 are original tools, and the paper uses them to propose a reduction to the subgame of essential strategies that is affinely isomorphic—stronger than Myerson's. If the proof goes through, it settles and generalizes the 2024 Brandenburg–Hollering–Portakal conjecture. The exposition is clear and the examples, especially Example 3.14, are helpful. The computational examples and supplementary code are a plus.

The soft spot: Theorem 3.12's induction base. The proof claims that if r(p)=Σd_i, then all incentive constraints at p are strict. That assertion is false. Using the authors' own generic Bach-or-Stravinsky game (Example 3.6), take p=(3/10,1/5,1/5,3/10). All slices in both directions are nonzero and distinct, so r(p)=4=d1+d2. Direct substitution gives H_{2,1}^{(1)}(p_{-1,2}) = -3(1/5)+2(3/10)=0 and H_{1,2}^{(2)}(p_{-2,1}) = 2(3/10)-3(1/5)=0, while the other two incentive slacks are positive. So p is a correlated equilibrium with maximal r(p) and two binding constraints. The base case is exactly the zero-parameter endpoint of the induction, so the induction cannot be closed as written. The gap might be repairable—perhaps by first using Proposition 3.5 to balance p, then arguing that maximal r plus balancedness forces strictness—but that argument is not in the manuscript. Everything downstream (Theorem 3.13, Theorem 2.7) inherits the gap.

The auxiliary lemmas (3.9, 3.10, 3.11) look plausible, and the citation pattern is fine; the paper engages properly with [3], [4], [12], [15]. I don't see a circularity beyond the induction base issue.

Who this is for: people working on correlated equilibrium polytopes, oriented matroid strata, and game-theoretic dimension questions. They will find the ideas worth engaging with, and the conjecture is important enough that a corrected proof would be valuable. I'd send it to a serious referee—this deserves refereeing, not desk rejection—but I would not cite it as a proof yet, and the authors need to fix the base case.

Recommendation: engage, but tell the authors to repair the induction base before you trust Theorem 3.12.

Referee Report

1 major / 4 minor

Summary. The manuscript studies the dimension of correlated equilibrium polytopes for finite normal-form games under an oriented-matroid notion of genericity. Its main results are Theorem 2.7 (restated as Theorem 3.13): for a generic game G, if P_G is not full-dimensional, then some proper subgame \tilde G has full-dimensional correlated equilibrium polytope affinely isomorphic to P_G; and Theorem 3.12: if a generic game has a correlated equilibrium all of whose slices are nonzero, then P_G is full-dimensional or a singleton. The proof strategy is an induction on the number r(p) of distinct normalized slices of a suitably chosen equilibrium, with balancing perturbations from Proposition 3.5 and support-reduction via Corollary 3.10.

Significance. If correct, Theorem 2.7 would settle and generalize a conjecture of Brandenburg, Hollering, and Portakal for 2 x n games, and would give a substantially stronger reduction than Myerson's dual reduction. The paper also contains explicit computational examples, a careful treatment of oriented-matroid genericity, and an interesting sufficient condition for full-dimensionality. However, the central induction has a false base case, so the main theorems are not established as written; the paper's own examples exhibit the failure.

major comments (1)

[Section 3, proof of Theorem 3.12, base case] The assertion that r(p) = sum_i d_i implies all incentive constraints at p are satisfied with strict inequality is false. In the generic Bach-or-Stravinsky game of Example 3.6, the point p = (3/10, 1/5, 1/5, 3/10) lies in P_G; its four slices are all nonzero and the two slices in each player direction are distinct, so r(p) = d_1 + d_2 = 4. Direct substitution gives H_{2,1}^{(1)}(p_{-1,2}) = -3(1/5) + 2(3/10) = 0 and H_{1,2}^{(2)}(p_{-2,1}) = 2(3/10) - 3(1/5) = 0, while the other two incentive slacks are positive. Example 3.14 shows the same phenomenon at maximal r(q) = 6. Since this base case is the starting point of the induction, Theorem 3.12 is not proved, and Theorem 3.13 (and hence Theorem 2.7) is unsupported. The gap is repairable: one should first use Proposition 3.5 and Corollary 3.10 to replace p by a balanced point with all entries positive and r not decreased; then at r = sum_i d_i, balancedness plus pairwise distinctness of all slices forces H_{k,ell}^{(i)}(p_{-i,k}) > 0 for all k != ell, and positivity of all entries gives full-dimensionality. That argument is not what appears in the manuscript, and the present base case also ignores the need for positive entries rather than merely nonzero slices.

minor comments (4)

[Section 3, proof of Theorem 3.12, second case] In the bullet 'if ell = 1 and k > d_k^{(1)}', the condition should read k > d_1^{(1)}; the notation d_k^{(1)} is otherwise undefined in that context.
[Section 3, proof of Theorem 3.12, induction step] After constructing G' with r(p') > r(p), the proof says 'By the induction hypothesis, the theorem then follows'; it should explicitly state that G' is still in the same oriented-matroid stratum as G, so P_{G'} and P_G have the same dimension by Remark 2.6.
[Section 3] There are several typos: 'contraint' in Proposition 3.5, 'aribitrarily' in Proposition 3.11, 'non-emtpy' and 'the the inclusion' in Theorem 3.13, and 'Sagemathscript' in the introduction.
[Example 2.5] The phrase 'using Mathematica[3]' appears to attribute the computation to reference [3], which is a MathRepo entry for correlated equilibria; please clarify the software citation.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation; central proof is self-contained despite a repairable base-case gap in Theorem 3.12.

full rationale

The paper's derivation chain is not circular. Theorem 3.13 reduces to Theorem 3.12, whose proof is an induction on (sum_i d_i) - r(p) using Proposition 3.5, Lemma 3.9, Corollary 3.10, and Proposition 3.11; none of these ingredients is definitionally identical to the target conclusion. The self-citations ([3], [4], [8], [11]) supply the conjecture being settled, the genericity notion, and computational support, but they are not load-bearing in the proof. No fitted parameter is renamed as a prediction, no uniqueness result is imported from the authors' prior work, and no known result is merely relabeled. The only substantive issue is a proof gap, not a circularity: in the proof of Theorem 3.12, the base case asserts that r(p) = sum_i d_i forces all incentive constraints to be strict and hence PG full-dimensional, but this is asserted before Proposition 3.5 is applied and is false for the generic Bach-or-Stravinsky game with p = (3/10, 1/5, 1/5, 3/10), where r(p) = 4 and two incentive constraints are tight. This is an unsupported base case rather than a self-referential reduction, and it appears repairable by applying Proposition 3.5 first, which makes all distinct-slice constraints strict. The score therefore reflects only the presence of minor, non-load-bearing self-citations, not a circular argument.

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

The central claim depends on standard game-theoretic facts (Nash's theorem, density of games with finitely many equilibria) and on the assumption that perturbations preserve the oriented matroid stratum. No free parameters are fitted, and no new entities are invented. The main unstated burden is the false strictness assertion in the base case of Theorem 3.12, which is captured in the red flags.

assumptions (4)

domain assumption Every finite game has at least one Nash equilibrium (Nash 1950).
Used implicitly to ensure P_G is non-empty and in the construction of q from Nash equilibria of subgames in Lemma 3.9 and Theorem 3.12.
domain assumption Games with finitely many Nash equilibria form a dense open set (Harsanyi 1973; Wilson 1971).
Used in Proposition 3.11 to derive a contradiction from the assumption that P_G consists only of Nash equilibria.
standard math The face poset of a polyhedral cone is determined by the oriented matroid of the rows of its coefficient matrix.
Invoked in Remark 2.6 to transfer face lattice and support properties between games in the same oriented matroid stratum.
domain assumption Perturbations of payoffs that are sufficiently small preserve the oriented matroid stratum and hence genericity.
The proofs in Proposition 3.5, Corollary 3.10 and Theorem 3.12 repeatedly perturb payoff tensors and require the game to remain generic; openness is asserted but the required closeness is never quantified.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the dimensions of correlated equilibrium polytopes of generic games." pith.science (2026). https://pith.science/paper/URRTSYHP

@misc{pith2026260804924,
  author       = {Pith},
  title        = {Pith review of: On the dimensions of correlated equilibrium polytopes of generic games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/URRTSYHP}},
  note         = {Machine review of arXiv:2608.04924}
}

read the original abstract

In this paper, we study the dimension of the correlated equilibrium polytope of finite games. Under the oriented-matroid notion of genericity, we prove that if a generic game is not full-dimensional, then there exists a subgame whose correlated equilibrium polytope is affinely isomorphic to that of the original game. This settles and generalizes an earlier conjecture of Brandenburg, Hollering, and Portakal (2024). Moreover, we show that the existence of a correlated equilibrium whose slices are all non-zero implies that the correlated equilibrium polytope is either full-dimensional or a singleton.

Figures

Figures reproduced from arXiv: 2608.04924 by the authors.

**Figure 1.** The subdivision (C X(1) 1 , C X(1) 2 , C X(1) 3 ) of ∆2 and the relative position of the projections π (1) i (q), which are the vertices of the triangle Q. The hyperplane h seperates the vertex w from the other two, which we then use to modify the entries of (X (1) 2,1 , X(1) 2,2 , X(1) 2,3 ) to stabilize q. Consider the triangle Q = conv({π (1) 1 (q), π (1) 2 (q), π (1) 3 (q)}) and let w := π (1) 2 (q). We define t… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 19 canonical work pages

[3]

Brandenburg, B

M.-C. Brandenburg, B. Hollering, and Irem Portakal. Combinatorics of correlated equilibria.https://mathrepo. mis.mpg.de/correlated-equilibrium/, Sept. 2022. Supplementary code and data for the article, MathRepo, Max Planck Institute for Mathematics in the Sciences

work page 2022
[4]

Brandenburg, B

M.-C. Brandenburg, B. Hollering, and I. Portakal. Combinatorics of correlated equilibria.Exp. Math., 34(2):212– 224, 2025

work page 2025
[12]

R. B. Myerson. Dual reduction and elementary games.Games and Economic Behavior, 21(1):183–202, 1997

work page 1997
[15]

Y. Viossat. Elementary games and games whose correlated equilibrium polytope has full dimension. Cahier du ceco, ´Ecole Polytechnique, CECO, 2003

work page 2003
[1]

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

work page 1974
[2]

R. J. Aumann. Correlated equilibrium as an expression of Bayesian rationality.Econometrica, 55:1–18, 1987

work page 1987
[5]

Calv´ o-Armengol

A. Calv´ o-Armengol. The set of correlated equilibria of 2x2 games. Working paper, Universitat Pompeu Fabra,

work page
[6]

Chen and X

X. Chen and X. Deng. Settling the complexity of computing two-player Nash equilibria. InProceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 261–271, 2006

work page 2006

Show all 20 references

[7]

Conitzer and T

V. Conitzer and T. Sandholm. New complexity results about Nash equilibria.Games and Economic Behavior, 63(2):621–641, 2008

2008
[8]

Connelly, V

E. Connelly, V. Galgano, Z. He, G. Maletto, E. Neuhaus, I. Portakal, H. Tillmann-Morris, and C. Zhao. The GameTheory package for Macaulay2.arXiv preprint arXiv:2507.16755, 2025

2025 arXiv
[9]

Daskalakis, P

C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195–259, 2009

2009
[10]

J. C. Harsanyi. Oddness of the number of equilibrium points: a new proof.Int. J. Game Theory, 2:235–250, 1973

1973
[11]

Hoyer, I

L. Hoyer, I. Portakal, and J. Draisma. Supplementary code for ’On the dimensions of correlated equilibrium polytopes of generic games’.https://doi.org/10.5281/zenodo.20323389, 2026

2026 doi
[13]

J. F. Nash Jr. Equilibrium points in n-person games.Proceedings of the national academy of sciences, 36(1):48–49, 1950

1950
[14]

R. Nau, S. Gomez Canovas, and P. Hansen. On the geometry of Nash equilibria and correlated equilibria. Internat. J. Game Theory, 32(4):443–453, 2003

2003
[16]

Viossat.Jeux et dynamique : exemples, g´ en´ ericit´ e et applications

Y. Viossat.Jeux et dynamique : exemples, g´ en´ ericit´ e et applications. Phd thesis,´Ecole Polytechnique, Palaiseau, France, 2005

2005
[17]

Y. Viossat. Is having a unique equilibrium robust?Journal of Mathematical Economics, 44(11):1152–1160, 2008

2008
[18]

von Stengel

B. von Stengel. Computing equilibria for two-person games. In R. J. Aumann and S. Hart, editors,Handbook of Game Theory with Economic Applications, volume 3, pages 1723–1759. North-Holland, Amsterdam, 2002

2002
[19]

R. Wilson. Computing equilibria of n-person games.SIAM Journal on Applied Mathematics, 21(1):80–87, 1971. 14 Mathematical Institute, Sidlerstrasse 5, 3012 Bern, Switzerland Email address:jan.draisma@unibe.ch R WTH Aachen University Email address:linda.hoyer@rwth-aachen.de Max ...

1971
[2003]

Available athttps://bse.eu/sites/default/files/working_paper_pdfs/79.pdf

Pith tools

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

[1] [3]

Brandenburg, B

M.-C. Brandenburg, B. Hollering, and Irem Portakal. Combinatorics of correlated equilibria.https://mathrepo. mis.mpg.de/correlated-equilibrium/, Sept. 2022. Supplementary code and data for the article, MathRepo, Max Planck Institute for Mathematics in the Sciences

work page 2022

[2] [4]

Brandenburg, B

M.-C. Brandenburg, B. Hollering, and I. Portakal. Combinatorics of correlated equilibria.Exp. Math., 34(2):212– 224, 2025

work page 2025

[3] [12]

R. B. Myerson. Dual reduction and elementary games.Games and Economic Behavior, 21(1):183–202, 1997

work page 1997

[4] [15]

Y. Viossat. Elementary games and games whose correlated equilibrium polytope has full dimension. Cahier du ceco, ´Ecole Polytechnique, CECO, 2003

work page 2003

[5] [1]

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

work page 1974

[6] [2]

R. J. Aumann. Correlated equilibrium as an expression of Bayesian rationality.Econometrica, 55:1–18, 1987

work page 1987

[7] [5]

Calv´ o-Armengol

A. Calv´ o-Armengol. The set of correlated equilibria of 2x2 games. Working paper, Universitat Pompeu Fabra,

work page

[8] [6]

Chen and X

X. Chen and X. Deng. Settling the complexity of computing two-player Nash equilibria. InProceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 261–271, 2006

work page 2006