{"id":"de796613-9b9d-444d-9926-6acb49c76f8b","arxiv_id":"2506.07186","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Value-set iteration computes (epsilon,delta)-optimal correlated equilibria in infinite-horizon stochastic games, with polynomial time for constant player counts and matching inapproximability bounds.","lead":"The paper gives an algorithm to compute near-optimal correlated equilibria in infinite-horizon, multi-player stochastic games where coordination signals are history-dependent. It runs in time that is polynomial for a constant number of players, and it proves matching limits showing why the approximation slack is necessary.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 18's δ-CE proof only bounds Q-differences for agents active in the current meta-state; the λ-step small-error argument does not apply to inactive agents, so Lemma 17 is not established for c-turn-based games.","rationale":"The reader's stated weakest assumption (spurious LP solutions from zero-probability actions and unbounded vertex counts) does not identify the main weak spot. The z-substitution in Lemma 14 is sound: for ¯π(a)=0 the constraints force z(a,b,s′)=0, and any feasible y for the original formulation is recovered; the 'arbitrary distribution' choice for zero-probability actions only affects terms multiplied by zero. Vertex counts in the general algorithm are bounded by the number of grid points, (1/ξ+2)^{n+1}, so the general-case Theorem 15 is supported. The c-turn-based extension, however, has a genuine proof gap. Lemma 17's Q-value bound is stated with an ∞-norm but its only justification applies to agents in I_{x_t^0}; for other agents the relaxed neighborhood permits arbitrarily large (up to 1+ξ) subsidy errors in the very next step. Since the CE condition applies at every history, including states where the agent is inactive, the proof does not establish that the constructed policy is a δ-CE. The vertex-representation issue is related but secondary: in c-turn-based games V(x) is cylindrical over the box in inactive dimensions, so a standard vertex representation has exponentially many vertices in n; Lemma 14's poly(L) bound does not by itself give poly(n) without a compact product-representation argument that the paper does not supply. None of this shows the theorem is false, but it means the headline c-turn-based result is currently unproven as written. The verdict remains conditional acceptance, with the required revision being a complete treatment of inactive agents and the compact polytope representation in Section 5.","tokens_in":31197,"tokens_out":29349,"duration_ms":332042,"concrete_test":"Analytical check: instantiate Lemma 17 for the smallest c=1 game with n=2 where agent 2 never belongs to any I_s (only the principal and agent 1 act). Follow the proof's subsidy bound for a deviation by agent 2 at a state where agent 2∉I_x. If the first λ terms cannot be bounded by ξ′ in coordinate 2, the displayed inequality fails; attempt to repair it with an argument that IC for inactive agents holds even with large subsidy errors. Computational check: implement Algorithm 2 for this game using the final fixed point V of bΦTB, enumerate histories up to length T >> λ/(1−γ), and evaluate Eq. (3) for agent 2; a violation exceeding δ would refute the theorem, and even a pass would not validate the current proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 17, the comparison between the original and subsidized games claims ||Q^{π,ρ} − Q^{π,ρ,tilde r}||_∞ ≤ Σ_{ℓ=t+1}^{t+λ} γ^{ℓ−t} ξ′ + Σ_{ℓ=t+λ+1}^{∞} γ^{ℓ−t}(1+ξ). The first sum is justified only for agents i ∈ I_{x_t^0}: such agents remain in I_{x_ℓ} for the next λ meta-states, so the relaxed neighborhood gives |tilde v_{ℓ,i} − v_{ℓ,i}| ≤ ξ′. For any agent j not in I_{x_t^0}, neigh^{I_x}_{ξ′} relaxes coordinate j to the full box, so the subsidy error at time t+1 can already be of order 1+ξ, not ξ′. Definition 1 requires the obedience inequality at every history (σ; s, a), including states where j does not act; a deviation by an inactive agent changes the observed actual action and thus the future correlation signals. The proof supplies no separate bound for such agents. Consequently, the δ-CE assertion of Lemma 17—and hence Theorem 18's polynomial-in-n result—is not supported by the written argument. This gap is independent of the LP substitution issue raised in the review: the zero-probability substitution is handled correctly by z(a,b,s′)=0 when bar π(a)=0, and vertex counts in the general algorithm are bounded by grid points; the problem is specific to the relaxed neighborhood in the c-turn-based construction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies computation of optimal extensive-form correlated equilibria in infinite-horizon discounted multi-player stochastic games. It introduces value-set iteration, a fixed-point algorithm based on inducible value sets, and proves that with a bi-criterion approximation—value within epsilon and incentive violation at most delta—an (epsilon, delta)-optimal CE can be computed in time polynomial in the game size and (1/(epsilon*delta*(1-gamma)))^(n+1) (Theorem 15), and in time polynomial in the number of players for c-turn-based games (Theorem 18). It also presents two inapproximability results: restricting policies to rational probabilities can arbitrarily degrade the value (Theorem 1), and computing an (epsilon, delta)-optimal stationary CE is NP-hard under the resource-augmentation benchmark (Theorem 2). The central fixed-point characterization, the convergence analysis, and the LP membership test are laid out in detail; the main weakness I identify concerns the c-turn-based extension, where the proof of Lemma 17 does not control the incentive error for inactive agents and the complexity argument does not account for the full-dimensional vertex representation of the cylinder-shaped value sets.","tokens_in":31427,"tokens_out":24447,"duration_ms":276895,"significance":"If correct, the results are significant: they give the first general algorithmic treatment of optimal history-dependent CEs in infinite-horizon stochastic games, with a clean fixed-point characterization and matching hardness results that justify the bi-criterion relaxation. The general constant-n algorithm appears sound: the value-set iteration converges by monotonicity to the greatest fixed point, the finite-grid approximation is parameter-free after choosing xi, and Lemma 14's LP substitution is valid, including the case where pi-bar(a) = 0. The advertised c-turn-based polynomial-in-n result is, however, not established by the current proofs; fixing Lemma 17 and the vertex-representation issue are necessary before the main claim can be accepted.","major_comments":[{"comment":"The proof of Lemma 17 does not establish the delta-CE property for agents that are not in the acting set of the current meta-state. In the displayed comparison of Q^{pi,rho} and Q^{pi,rho,tilde r}, the first sum Sum_{ell=t+1}^{t+lambda} gamma^{ell-t} xi' is justified only for agents i in I_{x_t^0}; for any j not in I_{x_t^0}, the neighborhood neigh^{I_x}_{xi'} relaxes coordinate j to the whole box, so the subsidy error at ell=t+1 can already be 1+xi, not xi'. Since Definition 1 requires the incentive constraint at every history (sigma; s, a), including histories where j does not act, and a deviation by j changes the recorded action and hence the future correlation signals, the conclusion that pi is a delta-CE is not supported by the written argument. This gap is load-bearing for Theorem 18's polynomial-in-n claim.","section":"Section 5.2, Lemma 17 (Appendix A.3)"},{"comment":"The complexity bound for c-turn-based games does not follow from the representation used in the manuscript. Lemma 16 counts only the grid points in the active dimensions I_x and concludes that the number of grid points per meta-state is (2/xi+2)^{(lambda+1)c}; however, the value set V(x) is a cylinder over the inactive coordinates, so its vertex representation as a polytope in R^{n+1} has 2^{n+1-|I_x|} vertices multiplied by the active vertices. Lemma 14, which Theorem 18 invokes, explicitly assumes a vertex representation and its LP has one variable per vertex, so a direct application has cost exponential in n. The paper does not provide the alternative polynomial-size H-representation or separation-oracle version of Lemma 14 needed to make the polynomial-in-n claim follow.","section":"Section 5.2, Lemma 16 and Theorem 18"}],"minor_comments":[{"comment":"The principal's reward at each x_i is r_max, so the discounted value in the yes case is gamma^2 * r_max (not gamma^2), and the threshold in the no case and the constant epsilon should be scaled by r_max. The reduction is unaffected because r_max is a constant for fixed gamma, but the displayed numbers should be corrected.","section":"Appendix A.1, proof of Theorem 2"},{"comment":"The sentence 'The fact that V = bPhi_TB(V) and V subset of V* follows the same argument there' reverses the inclusion asserted by the lemma; it should be V supset of V*.","section":"Appendix A.3, proof of Lemma 16"},{"comment":"The statement 'Since lambda is a constant' is not accurate when gamma and xi are part of the input, because lambda = log(xi/4)/log gamma depends on the accuracy and discount parameters. Theorem 18 should state explicitly that the bound is polynomial in the listed arguments with lambda fixed, or the dependence on 1/xi and 1/(1-gamma) should be tracked.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The main open question for this submission is whether the c-turn-based proof can be repaired. The general constant-agent result alone may already justify publication in a theory venue; if the authors can close the Lemma 17 gap and clarify the representation and tractability issue, I would be willing to support acceptance. The issues are technical rather than a matter of novelty or scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear X,\n\nThe paper makes a real step: it gives the first formal value-set iteration scheme for optimal extensive-form correlated equilibria in infinite-horizon stochastic games, with finite-time termination and explicit bounds, plus matching inapproximability results. The main general algorithm looks sound to me: the fixed-point characterization is due to Murray-Gordon, but the grid approximation, the LP membership test, and the resource-augmentation framework are new, and the proof of Theorem 15 hangs together.\n\nThe hard part is the c-turn-based speedup. The stress-test note is right: Lemma 17's proof only bounds subsidy differences for agents who are active at the current meta-state. For an agent who is not in I_{x_t^0}, the relaxed neighborhood can already put the subsidy at t+1 at order 1+ξ, and the written argument supplies no separate bound for such agents. Since Definition 1 requires obedience at every history, the δ-CE conclusion does not follow. That is a load-bearing gap for Theorem 18, not a minor typo. The idea of using λ-memory to truncate influence is plausible, and the gap might be fixable with a sharper accounting of which coordinates are actually relaxed, but as written the polynomial-in-n result is not established.\n\nTwo smaller things: Theorem 2's proof writes the principal's value as γ^2 where it should be γ^2·rmax, and Lemma 16's proof text reverses the inclusion V ⊆ V* (should be V ⊇ V*). Both are easy to repair, but they confirm the reading that the proofs were not machine-checked.\n\nWho gets value: someone working on algorithms for stochastic games, or on EFCE computation, will want the general method and the hardness results. The c-turn-based section needs a serious fix before it's usable.\n\nMy recommendation: send it to review. The general algorithm and the inapproximability bounds are significant enough to warrant referee time, and the gap in Theorem 18 is the kind of thing a good reviewer can pin down. The authors should be asked to either fix Lemma 17 or weaken Theorem 18.","headline":"Solid general algorithm with a real gap in the c-turn-based speedup; worth reviewing and fixing.","tokens_in":32034,"tokens_out":2175,"would_cite":true,"duration_ms":23670,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A15","91A68","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"In infinite-horizon stochastic games, an $(\\epsilon,\\delta)$-optimal correlated equilibrium can be computed in time polynomial in the game size and in $(1/(\\epsilon\\delta(1-\\gamma)))^{n+1}$, and for $c$-turn-based games, in time…","keywords":["correlated equilibrium","stochastic games","infinite horizon","value-set iteration","extensive-form correlated equilibrium","resource augmentation","turn-based games","approximation algorithms"],"falsifier":"Take the two-agent game from Theorem 1, whose only high-value correlated equilibrium uses an irrational probability, feed it to value-set iteration with a fine rational grid, and explicitly simulate all one-step deviations of the returned policy: if the policy violates a deviation constraint by more than $\\delta$ or its principal value is more than $\\epsilon$ below the optimal exact CE value, the approximation theorem is false.","tokens_in":30907,"feed_emoji":"🎲","tokens_out":9247,"duration_ms":100500,"temperature":0.7,"pith_summary":"The paper tackles the problem of computing optimal correlated equilibria in infinite-horizon, multi-player stochastic games, where a coordinator privately recommends actions at each step and agents must be incentivized to follow them. It establishes that an $(\\epsilon,\\delta)$-optimal correlated equilibrium — within $\\epsilon$ of the best exact-equilibrium value while allowing incentive constraints to slip by at most $\\delta$ — can be computed in time polynomial in the game size and in $(1/(\\epsilon\\delta(1-\\gamma)))^{n+1}$, and that for $c$-turn-based games the running time is polynomial in the number of agents. The approach works by replacing policies with the sets of values they induce, thereby avoiding the blow-up in histories that plagues history-dependent equilibria. The paper also proves that rational-only policies can be arbitrarily far from optimal and that no polynomial-time algorithm can find an $(\\epsilon,\\delta)$-optimal stationary correlated equilibrium unless P equals NP.","feed_headline":"Near-optimal correlated equilibria now computable in infinite horizons","feed_subtitle":"A fixed-point method over sets of inducible values makes optimal history-dependent play tractable.","key_machinery":"The load-bearing object is the inducible value set $V^\\star(s)$, the set of all payoff vectors a correlated equilibrium can induce from state $s$, together with the update map $\\Phi$ that expands a candidate value-set function by forcing a Bellman-like decomposition, an incentive-compatibility constraint, and the requirement that all continuation values lie inside the candidate sets. $\\Phi$ is monotone, so Tarski's fixed-point theorem yields a greatest fixed point, which is shown to be $V^\\star$. The algorithmic version replaces $\\Phi$ with a grid approximation $\\hat{\\Phi}$ whose values are convex hulls of grid points near $\\Phi$, and reduces membership checks to a linear program obtained by substituting $z(a,b,s') = \\bar{\\pi}(a) \\cdot y(a,b,s')$ for the product of a first-step action distribution and a convex-combination weight on a polytope vertex.","core_discovery":"The central discovery is that the set of all values inducible at a state by a correlated equilibrium — the inducible value set — is exactly the greatest fixed point of a monotone operator $\\Phi$ acting on value-set functions. Value-set iteration, starting from the hypercube of all possible values, converges to this greatest fixed point, and a grid-discretized version reaches an approximate fixed point in finitely many iterations. Every point in that approximate fixed point is shown to be $(\\epsilon,\\delta)$-inducible, so picking the point with the best principal value yields an $(\\epsilon,\\delta)$-optimal correlated equilibrium whose policy can be queried on demand for any history in polynomial time. For $c$-turn-based games, a $\\lambda$-memory meta-game construction keeps the relevant value sets low-dimensional, giving polynomial dependence on the number of players.","pith_inferences":["The greatest-fixed-point view of inducible value sets likely transfers to other history-dependent solution concepts, such as extensive-form communication equilibria, where compact value-based representations could bypass explicit history enumeration in the same way.","The paper's on-the-fly policy generation suggests a natural online implementation: rather than materializing a strategy, an agent could run the LP-based query procedure at each time step, which may be especially useful when the game is learned rather than fully specified in advance.","The parameter $\\lambda = \\log(\\xi/4)/\\log\\gamma$ reveals a concrete trade-off: as the discount factor approaches 1, the memory depth needed for the turn-based speedup grows, so the polynomial-in-$n$ guarantee degrades as $\\gamma \\to 1$; a direct test would be to measure the running time on the same $c$-turn-based instance under increasing $\\gamma$.","The LP substitution $z = \\bar{\\pi} \\cdot y$ suggests that similar linearization may handle other bilinear incentive constraints that arise when a coordinator and agents interact over time, providing a template beyond correlated equilibria."],"forward_implications":["For any fixed number of agents, an $(\\epsilon,\\delta)$-optimal correlated equilibrium can be computed in polynomial time, and the resulting policy can be executed by generating its action distribution on the fly for any queried history.","For $c$-turn-based games, the running time is polynomial in the number of agents, since the $\\lambda$-memory meta-game keeps the effective value-space dimension constant.","The $\\delta$ allowance in the incentive constraints is not merely a convenience: the paper proves that without such resource augmentation, even a constant-factor approximation of the optimal stationary correlated equilibrium is NP-hard, and that rational-probability policies can lose arbitrarily relative to irrational ones.","The same algorithm readily computes a correlated equilibrium (not necessarily optimal) in time exponential in the number of agents, and the paper leaves open whether that dependence can be removed for succinctly represented games.","The bi-criterion formulation lets the algorithm compare against the best exact correlated equilibrium while only ever needing to produce a $\\delta$-CE, matching the inapproximability results that rule out stronger guarantees."],"supporting_citations":[{"why":"introduced the fixed-point characterization of correlated equilibria in stochastic games that this paper extends to the infinite-horizon setting with full convergence and approximation analysis.","marker":"(Murray and Gordon, 2007)"},{"why":"supplies the lattice fixed-point theorem used to conclude that the monotone update map has a greatest fixed point, which is exactly the inducible value set.","marker":"(Tarski, 1955)"},{"why":"founded the stochastic-game model and noted that exact solutions may require irrational numbers, which motivates the resource-augmented $(\\epsilon,\\delta)$ objective.","marker":"(Shapley, 1953)"},{"why":"provides the GAP 3-SAT inapproximability result behind the NP-hardness proof for stationary correlated equilibria.","marker":"(Håstad, 2001)"},{"why":"defines the extensive-form correlated equilibrium concept with step-by-step private recommendations that the paper adopts as its correlated-equilibrium notion.","marker":"(von Stengel and Forges, 2008)"},{"why":"supplies the succinct-representation perspective and the one-shot tractability result that frames the open question about computing a single CE efficiently.","marker":"(Papadimitriou and Roughgarden, 2008)"},{"why":"earlier approximate value-set algorithm whose polytope-approximation idea the LP feasibility formulation in Lemma 14 builds upon.","marker":"(MacDermed et al., 2011)"},{"why":"contributes the substitution $z(a,b,s') = \\bar{\\pi}(a) \\cdot y(a,b,s')$ that linearizes the bilinear constraints in the membership test.","marker":"(Gan et al., 2023)"}],"fun_headline_variants":["Value-set iteration computes near-optimal correlated equilibria","Fixed point of value sets yields near-optimal correlated equilibria","Infinite-horizon correlated equilibria via value-set iteration","Near-optimal correlated equilibria in stochastic games via fixed-point iteration"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole fixed-point and complexity analysis rests on the linear program that tests membership in the $\\xi$-neighborhood of $\\Phi(V)(s)$ being exact even when the recommended action has probability zero, and on the number of vertices of each value set staying within the grid-derived bound; if either fails, the computed policy may not be a $\\delta$-CE and the stated running time would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Value-set iteration computes near-optimal correlated equilibria","Fixed point of value sets yields near-optimal correlated equilibria","Infinite-horizon correlated equilibria via value-set iteration","Near-optimal correlated equilibria in stochastic games via fixed-point iteration"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00147,"raw_usage":{"total_tokens":5936,"prompt_tokens":998,"completion_tokens":4938,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":4868}},"tokens_in":614,"tokens_out":4938,"duration_ms":38271,"temperature":1.0,"reasoning_tokens":4868,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:42:10.481290+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the two-agent game from Theorem 1, whose only high-value correlated equilibrium uses an irrational probability, feed it to value-set iteration with a fine rational grid, and explicitly simulate all one-step deviations of the returned policy: if the policy violates a deviation constraint by more than $\\delta$ or its principal value is more than $\\epsilon$ below the optimal exact CE value, the approximation theorem is false.","supporting_citations":[],"review_version":1}