{"id":"b4c1c9f9-0c50-47fa-abd3-6de669d92a50","arxiv_id":"2507.11509","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Deciding whether a correlated equilibrium with welfare above a threshold exists is PSPACE-hard for NFCE and NP-complete for EFCE, AFCE, EFCCE, NFCCE, and AFCCE in multiplayer extensive-form games; Nash threshold is ∃R-complete.","lead":"This paper settles the computational difficulty of finding optimal coordinated strategies in sequential games with hidden information: for one major equilibrium concept it is PSPACE-hard, while for several related concepts it is exactly NP-complete. The results answer a 2008 open question and reveal that optimal correlation can be harder than optimal Nash play in these games.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Formula-gadget payoff rule as written in Appendix D.1 contradicts Lemma 5: a satisfied term can still hit payoff 0, so good profiles need not achieve social welfare 3.","rationale":"The central claim is Theorem 1, the PSPACE-hardness of Threshold for NFCE. The reduction's correctness depends on the formula gadget's payoff rule and on Lemma 5's equivalence between good strategy profiles and welfare 3. The reader's weakest_assumption was the gap bound in Lemma 5 via Remark 1. That particular bound is not the problem: the stated lower bound 1/(2n(n+1)) is conservative, since the construction's smallest leaf probability is at least 1/(4n), so the gap argument survives. The real, more load-bearing issue is the payoff rule of the formula gadget as written in Appendix D.1. If that rule is taken literally, a satisfied term can still yield a 0-payoff leaf, so a good profile does not have welfare 3, and the equivalence used by Propositions 5 and 6 fails. This is an internal inconsistency of the proof as presented, not merely a disagreement with prior consensus. The likely correction is a sign/overline fix (pay 0 when the negation of the selected literal is in the chosen term), and with that correction the reduction appears plausibly sound. Because the correction is localized and the surrounding argument is detailed, a conditional accept with a mandate to fix the payoff rule is the appropriate outcome. The paper also has the separate issues noted by the reader: the abstract promises a FixP result that does not appear in the body, and Proposition 1 is only sketched. Those do not directly touch Theorem 1 but should be resolved. No formal verification or reproducible code is provided, so the proof text itself is the only evidence for the main claim.","tokens_in":48488,"tokens_out":30609,"duration_ms":370260,"concrete_test":"Re-derive Lemma 5 using only the payoff rule stated in Appendix D.1, on the smallest formula gadget. For example, take a one-variable formula with term t = x1, assignment θ(x1)=true, and let the formula-player play t. Under the stated rule, node F_x1 yields payoff 0 because x1 ∈ t, so a profile deemed good has expected welfare strictly below 3, contradicting Lemma 5 and Corollary 1. Then check whether the source text's intended rule is '0 iff the negation of the selected literal appears in t'; if the stated rule is taken literally, Propositions 5 and 6 do not establish the claimed welfare-3 equivalence and the main PSPACE-hardness argument cannot be verified.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The PSPACE-hardness proof rests on Lemma 5's characterization of pure profiles with expected social welfare 3. Lemma 5 claims a profile is good exactly when the formula-player's chosen term t_k is satisfied by the assignment and all universal players behave correctly, and that this is equivalent to every reachable leaf having welfare 3. But the payoff rule stated in Appendix D.1 says that playing t_k at node F_ℓ yields payoff 0 if the literal ℓ makes the term false, i.e., 'ℓ ∈ {ℓ_{k,1}, ℓ_{k,2}, ℓ_{k,3}} when ℓ ∈ Z or, z ∈ {ℓ_{k,1}, ℓ_{k,2}, ℓ_{k,3}} when ℓ = z̄.' Under this rule, take a good profile with θσ |= t_k and a positive literal ℓ ∈ t_k that is true under θσ. The reachable leaf F_ℓ gives payoff 0, so E_{δσ}(ω) < 3, contradicting Lemma 5. The illustrative example in Section 3 displays the same problem: it says playing t2 from node x1 is rewarded 0 because the term x1∧x2∧x3 evaluates to false when x1 is true, which is not generally true for a positive term. The intended rule is almost certainly that payoff 0 occurs when the negation of the selected literal appears in t_k; with that corrected rule, the good-profile characterization would go through. But as written, the reduction is internally inconsistent, and the reader's specific worry about the 1/(2n(n+1)) gap bound is not the soft spot: Remark 1's bound is conservative, since the actual minimum leaf probability in the construction is at least 1/(4n).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":48841,"tokens_out":11922,"duration_ms":151598,"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":[{"comment":"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.","section":"Appendix D.1, Lemma 5"},{"comment":"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.","section":"Appendix G, Abstract"},{"comment":"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.","section":"Section 3 / Appendix D, 'Beyond Chance'"}],"minor_comments":[{"comment":"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.","section":"Appendix D.1"},{"comment":"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.","section":"Appendix D.1"},{"comment":"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.","section":"Propositions 5 and 6"},{"comment":"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.","section":"Appendix F.4"},{"comment":"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.","section":"Section 4 and Appendix C"}],"recommendation":"major_revision","confidential_remarks":"The main technical error in the NFCE reduction appears to be a local typo in the payoff rule rather than a flaw in the overall reduction strategy; the corrected rule suggested in the report makes the good-profile characterization coherent. I recommend giving the authors the opportunity to fix this and to complete or clearly attribute the Nash ∃R-completeness and FixP claims, since those claims are part of the advertised contribution. No concerns about citation patterns or novelty disclosure arose in my reading."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, it is a serious complexity paper with results that, if right, redraw the map for equilibrium computation in extensive-form games: PSPACE-hardness for optimal NFCE, NP-completeness for the threshold problem for EFCE, AFCE, and the coarse variants, and ∃R-completeness for the Nash threshold. Second, the write-up of the PSPACE-hardness reduction contains an internal inconsistency that needs fixing before the results can be trusted as stated.\n\nThe genuinely new parts: the PSPACE-hardness construction for NFCE, the matching NP upper bounds via a new relevant-history approach, and the answer to the von Stengel–Forges question about AFCE without chance nodes. The relevant-history technique for n-player games with chance nodes is a real contribution; it also gives a clean Carathéodory argument for why polynomial support suffices for EFCE-style equilibria. The appendices are detailed and the related work is well covered.\n\nThe soft spot is the formula gadget in the QBF reduction (Appendix D.1 and Section 3). The payoff rule as written says the formula player receives 0 when the selected literal appears positively in the chosen term. But in a good profile, the assignment satisfies the term, so a positive literal in that term means the leaf is reached with the assignment making it true—and under that rule it gets payoff 0, contradicting Lemma 5's claim that good profiles have social welfare 3. The example in Section 3 repeats the same confusion: it says t2 from x1 is rewarded 0 because x1∧x2∧x3 evaluates to false when x1 is true. That is backwards. The intended rule—payoff 0 when the negation of the selected literal is in the term—is clear and would make the proof go through, but the current text is not correct. This is a real bug in a load-bearing reduction, not just a typo. The reader's stated worry about the 1/(2n(n+1)) gap is not the problem; that bound is fine.\n\nTwo smaller gaps: the ∃R membership for the Nash threshold is a sketch, and the abstract's FixP claim for computing arbitrary Nash has no supporting section. Both are presentation issues rather than observed errors.\n\nMy take: the paper deserves a serious referee. The NFCE hardness is a major result, and the NP upper bounds look solid. But I would not cite this version until the payoff rule is corrected and the ∃R proof is written out. Reading group: maybe, with the caveat about the bug.","headline":"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.","tokens_in":49376,"tokens_out":8187,"would_cite":false,"duration_ms":81548,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A18","68Q17","91A10","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The threshold problem for normal-form correlated equilibria in multiplayer extensive-form games with perfect recall is PSPACE-hard.","keywords":["extensive-form games","normal-form correlated equilibrium","threshold problem","PSPACE-hard","perfect recall","correlated equilibrium","agent-form correlated equilibrium","support size"],"falsifier":"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.","tokens_in":48311,"feed_emoji":"⚖️","tokens_out":9813,"duration_ms":100844,"temperature":0.7,"pith_summary":"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.","feed_headline":"Optimal correlated play in sequential games is PSPACE-hard","feed_subtitle":"Even a fixed welfare threshold for normal-form correlated equilibrium is PSPACE-hard to check.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces extensive-form and agent-form correlated equilibrium, proves NP-hardness of the threshold problem for NFCE, poses the open question about chance-free AFCE, and supplies the relevant-history and chance-elimination techniques the paper extends.","marker":"[VSF08]"},{"why":"Frames the computational questions about correlated equilibria and the role of succinct representations; the paper's hardness result bears on its open question about computing NFCE in extensive-form games.","marker":"[PR08]"},{"why":"Establishes $\\exists\\mathbb{R}$-completeness for the threshold problem for Nash equilibria in multi-player normal-form games, the comparison point for the paper's $\\exists\\mathbb{R}$-completeness result.","marker":"[BM16]"},{"why":"Shows the threshold problem for correlated equilibria is polynomial-time solvable in normal-form games, the contrast that makes the extensive-form PSPACE-hardness a complexity reversal.","marker":"[GZ89a]"},{"why":"Gives a polynomial-time algorithm for computing any EFCE and leaves open the support-size question for NFCE, which the paper's exponential-support lower bound addresses.","marker":"[HvS08]"},{"why":"Proves realization equivalence of mixed and behavioral strategies in perfect-recall games, used in the $\\exists\\mathbb{R}$ upper bound for threshold Nash.","marker":"[Kuh53]"},{"why":"Contributes the generalized matching-pennies idea that the uncertainty gadget adapts to force uniform mixing by universal players.","marker":"[GP06]"},{"why":"Defines extensive-form coarse correlated equilibrium, proves NP-hardness of its threshold problem, and proposes a pairwise-relevant-history definition that the paper shows can blow up exponentially.","marker":"[FBS20]"},{"why":"Gives polynomial-time optimal EFCE algorithms via relevant histories in triangle-free games, the approach the paper generalizes with honest and deviation histories.","marker":"[FS20]"}],"fun_headline_variants":["Threshold for correlated equilibrium: PSPACE-hard even fixed","Extensive-form: optimal correlated equilibria are PSPACE-hard","Correlated equilibrium complexity reverses in extensive-form games","QBF reduction proves PSPACE-hardness of optimal correlated equilibria","Normal-form correlated equilibrium threshold PSPACE-hard in extensive-form"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Threshold for correlated equilibrium: PSPACE-hard even fixed","Extensive-form: optimal correlated equilibria are PSPACE-hard","Correlated equilibrium complexity reverses in extensive-form games","QBF reduction proves PSPACE-hardness of optimal correlated equilibria","Normal-form correlated equilibrium threshold PSPACE-hard in extensive-form"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00051,"raw_usage":{"total_tokens":2537,"prompt_tokens":1057,"completion_tokens":1480,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":673,"completion_tokens_details":{"reasoning_tokens":1399}},"tokens_in":673,"tokens_out":1480,"duration_ms":13112,"temperature":1.0,"reasoning_tokens":1399,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:06:53.079361+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}