{"id":"00601b9f-086b-47f6-ab8a-41402c078434","arxiv_id":"2412.20291","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Linear correlated equilibria can be computed and learned in polynomial time in general convex games, given oracle access to the players' strategy sets.","lead":"This paper gives efficient algorithms for a stronger-than-coarse equilibrium notion, linear correlated equilibrium, in any convex game with oracle access to players' strategy sets. It also shows a learner can minimize linear swap regret against adversarial losses, opening a new frontier of tractable equilibria beyond coarse correlated equilibrium.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.4's proof invokes the EAH framework on a non-full-dimensional Y and uses an incorrect bound ∥x^T A∥≤√N; the appendix fixes the former but the main-text proof is incomplete.","rationale":"I read the paper in good faith and found the overall algorithmic machinery believable: the semi-separation oracle, Shell Ellipsoid, and the generalized EAH framework are coherent, and the appendix provides weak-oracle versions that address several precision issues. The reader's identified weakest assumption, Assumption 5.2, is genuinely load-bearing for Theorem 5.4 because the GER responses require computing x^T A, which needs the expected utility gradients g_i(x_-i). I partially agree with that concern. However, I found a more immediate proof-level gap: the strong Theorem 5.4 applies Theorem 5.1 to a set Y that is not full-dimensional, so the ball-containment hypothesis fails as stated. The appendix F.2 explicitly notices this and fixes it by inflating the first coordinate, but the main text never connects that fix to Theorem 5.4. Additionally, the bound ∥x^T A∥2 ≤ √N is incorrect because the ∅ column sums utilities over all n players; a concrete three-player example shows the entry can be 3, exceeding √7. Since the appendix's weak theorem already uses a more careful treatment and since n ≤ Σ d_i, these gaps do not appear to invalidate the central claim, but they do mean the main text's proof is not self-contained. I therefore keep the reader's CONDITIONAL verdict unchanged, while flagging the precise places where the proof needs adjustment.","tokens_in":42294,"tokens_out":28522,"duration_ms":293142,"concrete_test":"Compute the exact value of ∥x^T A∥2 for the 3-player game with d_i=1, P_i=[0,1], u_i(s)=1 for every profile, and x the uniform distribution over pure profiles; verify that the entry (x^T A)_∅ equals 3, exceeding √N=√7, so the claimed B=√N bound in Theorem 5.4 is false. Then check Section 5.2 for any argument showing how the non-full-dimensional Y satisfies the ball-containment hypothesis of Theorem 5.1; absent the inflation used in Appendix F.2, the strong proof has a missing step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main computation result relies on Theorem 5.1, whose Condition 2 requires a Euclidean ball inside the Deviator set Y. In Section 5.2, however, Y = {1} × Φ(P1) × ... × Φ(Pn) lies in the affine hyperplane where the first coordinate is fixed to 1, so Y has empty interior in R^N and contains no ball. The proof of Theorem 5.4 invokes the EAH algorithm without repairing this, and the necessary inflation Y' = [1−γ,1+γ] × Φ(P1,δ) × ... × Φ(Pn,δ) appears only in the weak-oracle appendix F.2, not in the strong theorem. Separately, the proof asserts that |ui(s)|≤1 implies ∥x^T A∥2 ≤ √N. This is false: the column j=∅ of A is defined as Σ_i U_i[k], so (x^T A)_∅ = Σ_i E[u_i(s)], which can be as large as n. For example, with n=3, each d_i=1, P_i=[0,1], and u_i≡1, the entry is 3 while √N=√7≈2.65. The correct bound is B = n√N, still polynomial in the input since n ≤ Σ_i d_i. Both issues are fixable and the appendix's Theorem F.3 suggests the intended repairs, but as written the proof of Theorem 5.4 does not establish the stated polynomial-time guarantee.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computation and online learning of linear correlated equilibria (LCE) in general convex games, i.e., games in which each player's strategy set is an arbitrary compact convex set given by oracle access. The main contributions are: (i) a no-regret algorithm that achieves O(d^4 sqrt(T)) linear swap regret against adversarial linear losses for a convex action set P (Theorem 4.5), and (ii) an oracle-polynomial-time algorithm for computing an epsilon-approximate LCE under the polynomial utility gradient property (Theorem 5.4). The technical engine is a new \"semi-separation oracle\" for the set of linear endomorphisms of a convex set, together with shell-ellipsoid methods and an extension of the Ellipsoid Against Hope framework. The appendices provide weak-oracle variants of both results, addressing precision issues.","tokens_in":42587,"tokens_out":8888,"duration_ms":89099,"significance":"If the main claims hold, this is a meaningful advance: LCE is identified as the tightest known equilibrium notion that is simultaneously polynomially computable and efficiently learnable for general convex games, and the paper answers an open question about whether regret minimization is possible without a separation oracle over the deviation set. The semi-separation concept is a genuine technical contribution, and the regret side (Theorem 4.5) appears coherent. The computation side, however, currently has two load-bearing proof gaps in the main text; both are localized and the weak-oracle appendix contains the likely intended repair. The paper is also explicit that the equilibrium-computation result depends on Assumption 5.2 (polynomial utility gradient property), which is correctly identified as a structural assumption rather than a hidden free parameter.","major_comments":[{"comment":"Theorem 5.1's Condition 2 requires a Euclidean ball B^N(r_y) contained in Y. In the equilibrium construction, Y = {1} × Φ(P_1) × ... × Φ(P_n) lies in the affine hyperplane y_1 = 1, so Y has empty interior in R^N and contains no such ball. The proof of Theorem 5.4 invokes Algorithm 5 / Theorem 5.1 without repairing this. The intended repair -- replacing Y by the inflated full-dimensional set Y' = [1-gamma,1+gamma] × Φ(P_1,delta) × ... × Φ(P_n,delta) -- appears only in the weak-oracle appendix, in the proof of Theorem F.3, and is absent from the strong theorem. As written, the proof of Theorem 5.4 does not establish the stated polynomial-time guarantee.","section":"§5.2, proof of Theorem 5.4"},{"comment":"The assertion that ||x^T A||_2 ≤ sqrt(N) is false. By the definition of A, the column j = ∅ is A_{k,∅} = Σ_i U_i[k], so (x^T A)_∅ = Σ_i E_{s∼x}[u_i(s)], which can be as large as n. For example, with n = 3, each d_i = 1, P_i = [0,1], and u_i ≡ 1, this entry is 3 while sqrt(N) = sqrt(7) ≈ 2.65. The same incorrect bound is used in Appendix F.2, where B is set to sqrt(N). The correct bound is B = n sqrt(N), which is still polynomial in the input since n ≤ Σ_i d_i. The proof must be updated in both the strong theorem and the weak-oracle theorem; the subsequent runtime conclusions are unaffected once this correction is made.","section":"§5.2, proof of Theorem 5.4; Appendix F.2, proof of Theorem F.3"}],"minor_comments":[{"comment":"The statement says \"it is possible to construct an efficient membership oracle for P,\" but this is tautological given the existing oracle access; the intended statement is clearly a membership oracle for Φ(P).","section":"§3, Corollary 3.3"},{"comment":"In the sentence \"we have that ⟨φ(p) − x, u⟩ > 0 for all p ∈ P,\" the symbol x should be p; the correct expression is ⟨φ(p) − p, u⟩ > 0.","section":"§4.1, proof of Lemma 4.1"},{"comment":"The proof refers to \"Algorithm 10\" and \"Algorithm 1\" when invoking the Ellipsoid Against Hope routine; the main text's algorithm is Algorithm 5. These cross-references should be corrected.","section":"§5.2, final paragraph of Theorem 5.4 proof"},{"comment":"The abstract contains a typo: \"strenghtening\" should be \"strengthening.\"","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The two major issues are localized and likely fixable: the non-full-dimensional Y can be handled by the inflation already present in Appendix F.2, and the norm bound can be repaired with B = n√N without changing the asymptotic claims. The authors should be asked to promote the inflation argument into the strong theorem or explicitly derive Theorem 5.4 from the weak-oracle theorem, and to correct the norm bound in both the main text and Appendix F.2. The regret result (Theorem 4.5) does not appear affected by these issues."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does something real: it shows that linear correlated equilibrium can be computed and learned in general convex games with only oracle access to the strategy sets, and it introduces a semi-separation oracle and a shell-ellipsoid framework to get there. That is a genuine advance over prior work that needed polyhedral structure or explicit separation over the deviation set. The regret result (Theorem 4.5) looks solid, and the hardness result for membership in the endomorphism set (Theorem 3.4) is a nice counterpart that explains why the semi-separation notion is necessary. The appendix treatment with weak oracles is careful and shows the authors are aware of precision issues.\n\nThe soft spots are concentrated in the proof of the equilibrium computation theorem, Theorem 5.4. As written, the proof applies Theorem 5.1 to the set Y = {1} × Φ(P1) × ... × Φ(Pn), but that set is not full-dimensional in R^N and contains no Euclidean ball. Theorem 5.1 explicitly requires a ball inside Y, so the application is invalid. The appendix's Theorem F.3 repairs this by inflating the first coordinate to an interval, but the main text never mentions this fix, so Theorem 5.4 as stated is not actually proven. There is also a simpler numerical slip: the claim that |u_i(s)| ≤ 1 implies ∥x^T A∥ ≤ √N is false, because the ∅ column of A sums the n utilities and can be as large as n. The correct bound is n√N, which is still polynomial, so this is not a serious problem, but it should be corrected.\n\nNeither issue looks load-bearing. The inflation trick is standard, and replacing B with n√N does not change the polynomial runtime. I would expect a revision to fix these without changing the main conclusions. Assumption 5.2 (polynomial utility gradient property) is load-bearing for the computation result, but it is the same assumption used in prior work and is clearly flagged.\n\nWho should read this: anyone working on equilibrium computation, Φ-regret, or oracle-efficient learning in games. The techniques will be reused. I would send this to peer review: the core ideas are original and the proofs are coherent modulo the stated gaps, which are addressable.","headline":"Genuinely new algorithmic techniques and likely the right answer, but the main-text proof of Theorem 5.4 has a non-full-dimensionality gap and a wrong norm bound, both fixable.","tokens_in":43141,"tokens_out":2726,"would_cite":true,"duration_ms":30555,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A10","91A26","68Q25","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that linear correlated equilibrium — the tightest known tractable refinement of coarse correlated equilibrium — can be computed in polynomial time and learned by efficient no-regret dynamics in every convex game.","keywords":["linear correlated equilibrium","convex games","linear swap regret","Φ-regret minimization","no-regret learning","Ellipsoid Against Hope","semi-separation oracle","extensive-form games"],"falsifier":"One concrete disproof would be a convex game presented through polynomial oracles that satisfies the polynomial utility gradient property yet whose every $\\epsilon$-approximate linear correlated equilibrium requires super-polynomially many product distributions to represent, contradicting the paper's succinct mixture representation; another would be a well-bounded convex set $P$ given by a polynomial separation oracle and adversarial linear losses on which every oracle-polynomial algorithm incurs linear rather than $O(\\sqrt{T})$ linear swap regret.","tokens_in":42080,"feed_emoji":"🎲","tokens_out":16920,"duration_ms":162918,"temperature":0.7,"pith_summary":"Equilibrium computation asks which solution concepts in games can be obtained in polynomial time or learned by no-regret dynamics. In general convex games — where each player's strategy set is an arbitrary compact convex body, possibly encoding exponentially many pure strategies as in extensive-form games — coarse correlated equilibrium is tractable but weak, while correlated equilibrium is a major open problem. This paper establishes that an intermediate notion, linear correlated equilibrium, in which a player may deviate to any affine linear image of their strategy set, is both polynomial-time computable and efficiently learnable given only oracle access to the strategy sets. The enabling idea is a new primitive, the semi-separation oracle, which replaces the provably intractable separation oracle over the set of deviations, together with adaptively maintained convex \"shell\" sets of deviations. A further consequence resolves an open question about classical $\\Phi$-regret algorithms: fixed-point computation remains necessary, but efficient separation over the deviation set is not.","feed_headline":"A tighter equilibrium is now computable for every convex game","feed_subtitle":"Linear correlated equilibrium beats coarse correlated equilibrium while staying polynomial-time and learnable.","key_machinery":"The load-bearing objects are the semi-separation oracle and the shell sets. The semi-separation oracle minimizes the convex function $\\|\\phi(p) - p\\|^2$ over $P$ for a candidate affine map $\\phi$; if the minimum is zero it returns a fixed point of $\\phi$ in $P$, and otherwise the residual direction $u = \\phi(p^*) - p^*$ yields the linear constraint $\\langle \\phi'(p_u), u \\rangle \\le \\langle p_u, u \\rangle$ that every true endomorphism $\\phi'$ of $P$ satisfies but that $\\phi$ violates, giving a genuine separating hyperplane from $\\Phi(P)$. This oracle is what the classical $\\Phi$-regret framework lacked, since full separation over $\\Phi(P)$ is provably intractable from oracle access alone. The shell machinery maintains a convex superset $\\tilde\\Phi$ of $\\Phi(P)$, defined by polynomially many half-spaces, and refines it each round: Shell Ellipsoid shrinks the shell until it either finds a transformation with a fixed point in $P$ or cuts the shell away from $\\Phi(P)$, and Shell Projection guarantees that the projected transformation still has a fixed point in $P$, so that the dual-regret reduction — playing a fixed point of each played transformation, making primal and dual regret equal — goes through. For equilibrium computation, the same fixed-point-based responses serve as the good-enough-response oracle inside a generalized Ellipsoid Against Hope for general convex sets.","core_discovery":"The central claim is that, for every convex game — $n$ players with compact convex strategy sets $P_i \\subset \\mathbb{R}^{d_i}$ and multi-linear utilities, accessed only through membership, separation, or optimization oracles — an $\\epsilon$-approximate linear correlated equilibrium can be computed in time polynomial in the dimensions and in $\\log(1/\\epsilon)$, and can be learned by efficient no-linear-swap-regret dynamics. The regret result holds against an adversarial sequence of linear losses over a single convex set $P$, achieving $O(d^4\\sqrt{T})$ linear swap regret after $T$ rounds. Both algorithms operate in a regime where no efficient separation oracle for the set $\\Phi(P)$ of linear endomorphisms of $P$ can exist, a hardness the paper proves by showing that distinguishing the ball from a capped ball requires exponentially many membership queries. The resolution is the semi-separation oracle: for any affine map $\\phi$, it either finds a fixed point of $\\phi$ inside $P$ or produces a hyperplane that genuinely separates $\\phi$ from $\\Phi(P)$, and this weaker primitive turns out to be sufficient for both the shell-based regret minimizer and a generalization of the Ellipsoid Against Hope method to non-polyhedral strategy sets. On this basis the paper identifies linear correlated equilibrium as the tightest known notion of equilibrium that is simultaneously polynomial-time computable and efficiently learnable for general convex games.","pith_inferences":["I would take the semi-separation recipe to be the paper's transferable lesson: any deviation class admitting an efficient fixed-point test but no tractable separation could be plugged into the same shell-based regret minimizer and Ellipsoid Against Hope extension, possibly generalizing the result beyond affine linear maps.","The paper leaves open the boundary question of whether linear correlated equilibrium is literally the strongest polynomial-time notion, or merely the strongest known: a sharper statement would require proving that every $\\Phi$ strictly between constant deviations and all linear endomorphisms is either computable or provably hard.","A natural next target is welfare-optimal linear correlated equilibrium: the oracle model plus the polynomial utility gradient property may suffice to optimize over the linear correlated equilibrium polytope, even though the paper computes one equilibrium rather than the best one.","Because the learner-side result holds against adversarial linear losses, I would expect it to transfer beyond equilibrium computation, for example to designing learners that resist strategic manipulation in Bayesian games, where this protection was previously available only in restricted game classes."],"forward_implications":["In any convex game with oracle access to the strategy sets and the polynomial utility gradient property, an $\\epsilon$-approximate linear correlated equilibrium can be computed in oracle-polynomial time and represented as a mixture of polynomially many product distributions.","A learner with oracle access to a convex strategy set $P$ can keep linear swap regret at $O(d^4\\sqrt{T})$ after $T$ rounds against adversarial losses, and using such learners as players in a convex game drives the joint play toward a linear correlated equilibrium.","Every previously known polynomial-time result for linear swap regret and linear correlated equilibria, which was confined to extensive-form games, now extends to all convex games, including Bayesian games, routing games, and resource-allocation games.","The classical $\\Phi$-regret algorithm required two subroutines, fixed-point computation and separation over $\\Phi$; with fixed points known to be necessary, the paper's result shows the sufficient and load-bearing ingredient is the semi-separation oracle, not separation.","For convex sets given by small explicit H- or V-representations, efficient membership oracles for the endomorphism set follow directly from the paper's lemmas, so the shell machinery is only needed for the fully general oracle-access setting."],"supporting_citations":[{"why":"Supplies the classical $\\Phi$-regret minimization framework and its reduction of $\\Phi$-regret to dual external regret over the deviation set, which this paper extends to settings where the deviation set cannot be separated over.","marker":"Gordon et al. [2008]"},{"why":"Introduces the Ellipsoid Against Hope technique for computing correlated equilibria in games of polynomial type; this paper generalizes that approach to general convex sets without separation oracles for the deviation set.","marker":"Papadimitriou and Roughgarden [2008]"},{"why":"Generalizes Ellipsoid Against Hope to polyhedral games of non-polynomial type and defines the polynomial utility gradient property (Assumption 5.2) that the equilibrium computation here relies on.","marker":"Farina and Pipis [2024a]"},{"why":"Establishes polynomial-time linear swap regret minimization in extensive-form games; the baseline result that this paper subsumes and extends to all convex games.","marker":"Farina and Pipis [2024b]"},{"why":"Proves that fixed-point computation is necessary for $\\Phi$-regret minimization, leaving separation as the only possibly unnecessary ingredient and framing the open question this paper answers.","marker":"Hazan and Kale [2007]"},{"why":"Develops improper $\\phi$-regret minimization over transformations that merely have fixed points, which justifies the paper's relaxation from endomorphisms to fixed-point-containing transformations.","marker":"Dann et al. [2024]"},{"why":"Provides the standard equivalences among weak membership, separation, and optimization oracles along with ellipsoid-based weak optimization tools used throughout the algorithm.","marker":"Grötschel et al. [1993]"}],"fun_headline_variants":["Polynomial-time linear correlated equilibrium for convex games","Convex games: efficient equilibrium computation and learning","Semi-separation oracle unlocks convex-game equilibria","Tighter equilibrium now polynomial-time and learnable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The equilibrium-computation result rests on the assumption that each player's expected utility gradient against any product distribution of opponents' strategies can be computed in polynomial time; if that is not possible, the algorithm's fixed-point-based responses cannot be constructed, while the regret-minimization result needs only oracle access to the strategy set.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time linear correlated equilibrium for convex games","Convex games: efficient equilibrium computation and learning","Semi-separation oracle unlocks convex-game equilibria","Tighter equilibrium now polynomial-time and learnable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00066,"raw_usage":{"total_tokens":3069,"prompt_tokens":1046,"completion_tokens":2023,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":662,"completion_tokens_details":{"reasoning_tokens":1963}},"tokens_in":662,"tokens_out":2023,"duration_ms":17515,"temperature":1.0,"reasoning_tokens":1963,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:24:11.514033+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One concrete disproof would be a convex game presented through polynomial oracles that satisfies the polynomial utility gradient property yet whose every $\\epsilon$-approximate linear correlated equilibrium requires super-polynomially many product distributions to represent, contradicting the paper's succinct mixture representation; another would be a well-bounded convex set $P$ given by a polynomial separation oracle and adversarial linear losses on which every oracle-polynomial algorithm incurs linear rather than $O(\\sqrt{T})$ linear swap regret.","supporting_citations":[],"review_version":1}