{"id":"5f231b19-6b46-4b63-9d5e-87e75620dd46","arxiv_id":"2608.08017","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every finite recursive game has near-optimal stationary strategies that are simple monomials in the accuracy epsilon, and for fixed state count these can be computed exactly in polynomial time.","lead":"Finite games that can loop forever still have near-optimal strategies that come in one simple package: for every small accuracy, each action's probability is either zero or a constant times a power of the accuracy. This paper proves that directly and gives an exact algorithm that computes such strategies for rational games with a fixed number of states.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The recursion rests on Lemma 4.12's unverified recurring-kernel derivative claim; if the imported Shapley–Snow property fails over an ordered algebraic field, the carrier invariant collapses.","rationale":"The existence result of Section 3 is elementary and appears sound; my concern is confined to the algorithmic construction. Lemma 4.12 is the first place where an imported algebraic property guarantees that raw coordinate candidates pin down a unique irreducible carrier, and every later reconstruction, degree bound, and branch-selection step inherits from it. The cited proposition concerns multiparameter eigenvalue problems, so it is not self-evident that the derivative-nonvanishing conclusion transfers to the Oliu-Barton auxiliary matrix over an arbitrary ordered algebraic field after denominator clearing. This is not an identified contradiction, and I found no specific error in Sections 3 or 4. Because no machine-checked proof or implementation is supplied, the correctness of Theorem 4.2 remains dependent on this single unverified step. The reader's weakest assumption already names exactly this dependency, and the proposed check would either resolve the concern or reveal a genuine gap; absent such evidence, the ACCEPT verdict with moderate confidence remains appropriate.","tokens_in":39402,"tokens_out":24146,"duration_ms":283199,"concrete_test":"Extract the exact statement and hypotheses of Attia–Oliu-Barton [4, Proposition 5.3.1]; verify that they hold for the Oliu-Barton auxiliary matrices W_k^lambda(a) after clearing denominators over any ordered algebraic number field K, and re-derive Lemma 4.12(i) from it with the claimed degree and height bounds. Additionally, run a brute-force probe over all small rational recursive games with N=2 or N=3 and values in Q(sqrt(2)): enumerate Shapley–Snow kernels at a sequence of discounts and check that at each sampled branch point at least one raw candidate remains nonzero in the value variable and vanishes at the selected value; a counterexample would refute the invariant.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing point is Lemma 4.12's coordinate-event envelope. The recursive invariant is sound only if, at every point of the inherited branch, at least one raw Shapley–Snow coordinate candidate remains a nonzero polynomial in the value coordinate after specialization and vanishes at the selected coordinate. The proof of this property uses a recurring-kernel argument in which, for discounted values a_n converging to a0, some kernel determinant has nonzero a-derivative at each a_n, via the 'cofactor sum is nonzero' assertion imported from Attia and Oliu-Barton [4, Proposition 5.3.1]. The paper does not state the hypotheses of that proposition, nor does it prove that the Oliu-Barton auxiliary matrices W_k^lambda(a) satisfy them after clearing denominators over an arbitrary ordered algebraic field K, nor that the first nonzero lambda-coefficient after specialization has positive degree in a at every branch point. If this property fails, the raw candidate family may fail to certify a single irreducible carrier, the matched-fiber reconstruction in Lemma 4.3 could select the wrong component, and the entire recursion in Theorem 4.2 breaks. I found no concrete error in the surrounding exposition; this is the unverified hinge of the correctness proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper has two parts. Section 3 gives an elementary proof of the Frederiksen–Miltersen regularity theorem: every finite recursive game has, for each player, a stationary monomial family that is ε-optimal from all states for all sufficiently small ε>0. The proof starts from a sequence of points in Everett's region C1 converging to the value, expresses absorption probabilities of pure stationary replies as quotients of directed-forest polynomials, and uses a polyhedral compression lemma to replace the finitely many asymptotic scales by one monomial parameter. Section 4 presents a deterministic exact algorithm for rational games with a fixed number N of active states that computes such a monomial family, with all algebraic coefficients in one ordered common real-univariate representation, and claims running time and output length at most L^{(N+1)^{O(N)}}. The algorithm maintains the represented data on one selected real plane-curve branch over an ordered algebraic number field, reconstructs the carrier from matched fibers, and extracts stable local strategies via Newton–Puiseux expansions.","tokens_in":39593,"tokens_out":14330,"duration_ms":163117,"significance":"The elementary proof in Section 3 is a genuine contribution and, if correct, repairs the earlier flawed Frederiksen–Miltersen proof while avoiding semialgebraic selection and Puiseux series. The algorithmic result, if correct, answers an open question from Frederiksen's thesis and gives the first exact polynomial-time-in-L algorithm (for fixed N) for monomial families. The paper is explicit about degree and height bookkeeping and states deterministic complexity bounds, which is a strength. No code is shipped, but the algorithm is described in enough detail that the claimed size recurrences can in principle be audited. However, the algorithmic proof rests on several imported exact-algebraic results whose hypotheses are not always stated; at least one of these dependencies is load-bearing and needs to be resolved before the algorithmic claim can be regarded as established.","major_comments":[{"comment":"The recursive invariant of Theorem 4.2 is sound only if Lemma 4.12(i) holds: at every point of the inherited branch, at least one raw Shapley–Snow coordinate candidate has positive degree in the value coordinate and vanishes at the selected coordinate. The proof of (i) imports a 'recurring-kernel' derivative claim from Attia and Oliu-Barton [4, Proposition 5.3.1], but the manuscript does not state the hypotheses of that proposition, nor does it show that the auxiliary matrices W_k^lambda(a) satisfy them after clearing denominators over an arbitrary ordered algebraic number field K. In particular, the argument requires that the cofactor sum in the Shapley–Snow formula be nonzero at each lambda_n and at the limit point, that the coefficient of the queried value have entries of one strict sign in the ordered field, and that the first nonzero lambda-coefficient P_{K,nu0}(a) after specialization be a nonzero polynomial of positive degree in a. If any of these fails, the candidate family may not pin down the correct branch, the matched-fiber reconstruction in Lemma 4.3 could select a wrong component, and the nested reduction in Theorem 4.2 would break. This is the central unverified hinge of the algorithmic part. I ask the authors to give a self-contained proof of the recurring-kernel property for ordered algebraic fields, or to state the imported proposition in full and verify its hypotheses explicitly.","section":"Section 4.5, Lemma 4.12"},{"comment":"The exact-value computation at every recursive level relies on Lemma 4.4's transfer of the Oliu-Barton limiting-sign argument to an ordered algebraic field. As written, the proof asserts that the sign of val W_k^lambda(a) is constant on (0, lambda*] using only the Shapley–Snow determinant cover and exclusion of roots of field norms, but it does not fully justify two steps: it does not establish that the kernel formula's denominator (the cofactor sum) remains nonzero on the interval, and it does not spell out how degenerate cases are handled when the selected kernel's numerator is identically zero but another kernel determines the value. Since Proposition 4.6 invokes this lemma at every fiber of the recursive construction, the proof should either be completed within the paper or reduced line-by-line to the cited proposition with an explicit statement of the hypotheses being verified.","section":"Section 4.3, Lemma 4.4 and Proposition 4.6"}],"minor_comments":[{"comment":"The cross-references to 'theorem 3.1' actually point to Lemma 3.1 (the pure stationary reply lemma); the numbering or labels should be corrected throughout.","section":"Sections 2 and 3.4"},{"comment":"The dual region C2 is described in words but never displayed; displaying its explicit definition would help the reader check the symmetric arguments.","section":"Section 1.1, Eq. (2)"},{"comment":"The bound in (17) uses m, the number of ambient coordinate differences, but m is not defined before the statement of the lemma; it is only introduced inside the proof.","section":"Section 4.2, Lemma 4.3"},{"comment":"The notation D_{r+1} for the strict gap conflicts with the forest denominator D_beta used in Section 3; renaming the gap (for example, Delta_{r+1}) would avoid confusion.","section":"Section 4.4, Eq. (18)"}],"recommendation":"major_revision","confidential_remarks":"The Section 3 existence proof is strong and could support publication on its own. My recommendation is driven by the algorithmic part: the correctness of Theorem 4.2 depends on Lemma 4.12's recurring-kernel property, whose imported justification is not verified over ordered algebraic fields. If the authors supply a complete proof of that property, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick summary: the genuine contribution here is Section 3—a clean, elementary proof of Frederiksen–Miltersen's monomial-family existence theorem, with explicit exponent bounds. The algorithm in Section 4 is the other headline: for fixed N, exact monomial families in time L^{(N+1)^{O(N)}}, all coefficients in one ordered RUR. That is a substantial claim and, as far as I can tell, not in the prior literature.\n\nSection 3 holds up well. The forest-denominator lemma is proved cleanly, the monomial-compression lemma is careful, and the quantitative bound in Prop. 3.4 is a nice extra. Section 2 is an honest, specific repair of the authors' own earlier proof—that is self-citation, but the repairs are concrete and the new proof is independent. I don't see circularity.\n\nThe soft spot is exactly where the reader and the stress-test put it: Lemma 4.12. The correctness of the recursive invariant depends on a 'recurring-kernel' argument imported from Attia and Oliu-Barton, Prop. 5.3.1, and the paper does not state that proposition's hypotheses nor prove they survive clearing denominators over an arbitrary ordered algebraic field. The one-paragraph proof in Lemma 4.12 asserts the derivative argument applies, but the 'cofactor sum is nonzero' claim is not derived. If that fails, the raw candidates may not certify the branch and the matched-fiber reconstruction could select the wrong component. I did not find a concrete counterexample, and the rest of the algorithm is laid out in impressive detail, but this is a genuine gap in exposition, possibly in proof, and it is load-bearing. A referee must check it before the algorithmic theorem can be accepted as proved.\n\nThe complexity ledger in Section 4.7/A is coarse but looks consistent; I did not spot an arithmetic error.\n\nWho is this for: people working on recursive games, exact algorithms for stochastic games, and semialgebraic/Puiseux techniques. For them it is worth serious referee time. Outside the subfield, significance is moderate. My recommendation: send it to a strong referee with specific instructions to verify Lemma 4.12 and its use of Attia–Oliu-Barton over ordered fields. This should not be desk-rejected.","headline":"Solid elementary existence proof; the claimed polynomial-time algorithm is real but leans on one unverified algebraic-geometry lemma (4.12) that a referee must check.","tokens_in":40128,"tokens_out":2125,"would_cite":true,"duration_ms":24075,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A15","91A68","68W30"],"pacs":[],"model":"deepseek-v4-flash","headline":"For rational recursive games with a fixed number of states, one finite monomial formula encodes ε-optimal strategies for all sufficiently small ε, and a deterministic polynomial-time algorithm computing it exists.","keywords":["recursive games","stochastic games","monomial strategy families","exact symbolic algorithms","real univariate representations","Puiseux series"],"falsifier":"Run the algorithm on a rational recursive game with two or three active states, then compare the recovered carrier branch at the dyadic sample points against an independent high-precision numerical continuation of the value curves; any divergence inside the certified $\\varepsilon_0$-interval would falsify the reconstruction claim. A more targeted test looks for an ordered algebraic field and a discounted matrix family in which the same covering determinant recurs along a sequence of discounts tending to zero, its derivative along the value coordinate vanishes at the limit point, and yet the value still changes — exactly the configuration that would break Lemma 4.12's coverage of coordinate candidates.","tokens_in":39160,"feed_emoji":"🎲","tokens_out":11427,"duration_ms":118554,"temperature":0.7,"pith_summary":"The paper sets out to show that the regular pattern behind near-optimal play in finite recursive games is not only true but explicitly computable. Its first contribution is an elementary existence proof: every finite recursive game admits, for each player and all sufficiently small accuracies $\\varepsilon>0$, a single stationary monomial family — a finite object in which, at each state, all but one action probability are constants times integer powers of $\\varepsilon$ and which therefore specifies an $\\varepsilon$-optimal strategy for every small $\\varepsilon$ at once. Its second contribution is an algorithm: for rational games with a fixed number $N$ of active states, a deterministic procedure computes such a family exactly, returning all algebraic coefficients in one ordered common real univariate representation, in time and output length at most $L^{(N+1)^{O(N)}}$ for input length $L$. If the algorithmic claim is correct, it settles a question left open in the doctoral thesis that contained the earlier, partly flawed proof of the existence result, and it replaces that proof's semialgebraic machinery with finite Markov-chain and polyhedral arguments.","feed_headline":"A single monomial formula yields near-optimal play for all small ε","feed_subtitle":"Fixed-state rational games now admit one exact, polynomial-time-computable strategy family for all fine accuracies.","key_machinery":"The central object is the monomial family: a stationary strategy in which, at every state, all but one action probability are of the form $c\\varepsilon^d$ with $c\\ge 0$ and integer $d\\ge 0$, while one distinguished action takes the remaining probability, so a finite list of coefficients and exponents defines a legal strategy for every sufficiently small accuracy $\\varepsilon$. Two mechanisms carry the argument. The first is the directed-forest quotient formula: once the support of a strategy sequence is fixed, every absorption probability against a fixed pure reply is a quotient of two polynomials whose expanded terms are nonnegative monomials in the action probabilities and which share one positive denominator; the paper proves the formula by direct determinant expansion, which also exposes the exact numerators and signs needed later. The second is the finite monomial-ratio compression lemma: it replaces finitely many competing asymptotic scales by one integer exponent vector and, crucially, reproduces the limiting values of all finite positive term ratios exactly — not merely their orders — which matters because terminal rewards may be signed. Around these, the algorithmic proof builds a recursive state reduction in which all exact data live on one selected irreducible real plane-curve branch over an ordered algebraic number field; after each state removal the branch is reconstructed by interpolation from finitely many matched fibers at dyadic parameter values, and the final algebraic coefficients are packaged in one ordered common real univariate representation, which records the joint conjugate pairing of all coefficients.","core_discovery":"The paper's central discovery is a complete, exact description of the near-optimal strategy asymptotics of recursive games. The existence claim is that the value vector can be approached through the Player-I one-sided region by stationary strategies whose supports are eventually fixed, and that with supports fixed every absorption probability against any pure stationary reply is a quotient of directed-forest polynomials with nonnegative coefficients and a common positive denominator. A polyhedral compression lemma then shows that the finitely many asymptotic scales of these forest monomials can be collapsed into a single integer weight vector without changing any limiting ratio, so a monomial curve in the accuracy parameter produces strategies that are $\\varepsilon$-optimal from every state for all sufficiently small $\\varepsilon$ — this re-proves the existence theorem with elementary means and gives an explicit bound on the exponents. The algorithmic claim is that, for rational games with a fixed number $N$ of active states, a deterministic algorithm computes such a family for both players: it removes states one at a time while preserving all strict inequalities, represents the evolving value data as rational functions on one selected real plane-curve branch over an ordered number field, recovers that branch at each level by matched-fiber interpolation from exactly computed dyadic values, extracts the leading rational-exponent terms of the stable local strategies, and certifies the result with an exact two-sided sign check. The output is one ordered common real univariate representation of all coefficients plus a positive dyadic endpoint $\\varepsilon_0$, with running time and output length at most $L^{(N+1)^{O(N)}}$.","pith_inferences":["Beyond the paper, the finite monomial-ratio compression lemma should transfer to any parametrized finite Markov decision problem whose payoffs are quotients of positive polynomials, such as concurrent reachability games, giving leading-term approximations without semialgebraic machinery.","Beyond the paper, the matched-fiber carrier-reconstruction template — certify one selected irreducible curve by interpolation at exactly evaluated dyadic fibers — suggests a general recipe for exact parametric value computation in games, with the state count appearing only in the exponent.","Beyond the paper, the exact two-sided certificate from the paper can be reused as a standalone verifier: run any approximate solver on a rational game, plug its output into the sign-polynomial check, and get a certified dyadic interval or a rejection.","Beyond the paper, a natural next question is the tightness of $L^{(N+1)^{O(N)}}$: whether the fixed-state exponent must grow doubly exponentially in $N$, or whether the algebraic coefficients can be kept in fields of degree exponential rather than doubly exponential in $N$."],"forward_implications":["The open question of whether monomial families can be computed exactly in polynomial time for each fixed number of active states is answered affirmatively, with explicit bounds on degree, height, exponent size, and running time.","The earlier existence theorem is re-proved without semialgebraic selection or rational-exponent series, replacing them with finite Markov-chain and polyhedral arguments, and an explicit bound on the monomial exponents is obtained.","The output object is verifiable: an exact two-sided symbolic certificate decides, from the game and the two formulas, whether the families are $\\varepsilon$-optimal on a stated interval, so the computed families can be checked independently.","For every rational game with a fixed number of states, the same symbolic object gives a single strategy for all sufficiently small accuracies, so no separate strategy needs to be recomputed per $\\varepsilon$.","If the complexity bound is sound, it gives a concrete, uniform guarantee: doubling the input length never costs more than a fixed state-dependent polynomial in the input length, even though the algebraic coefficients may live in large number fields."],"supporting_citations":[{"why":"defines recursive games and supplies the one-sided regions and fixed-point value theory that the whole construction starts from.","marker":"[9]"},{"why":"states the prior monomial-family existence theorem whose proof this paper repairs and whose construction Section 3 replaces; it is the baseline the new proof must match.","marker":"[13]"},{"why":"is the thesis containing the earlier flawed proof and posing the question of polynomial-time computation that Theorem 4.2 answers.","marker":"[12]"},{"why":"supplies the strict reduced-state gap lemma and the Lipschitz bound used in the state-reduction recursion.","marker":"[14]"},{"why":"gives the undiscounted stochastic-game value algorithm that is adapted to ordered algebraic fields for exact value computation at fibers.","marker":"[21]"},{"why":"provides the determinant-cover representation of matrix-game values and the recurring-kernel property on which Lemma 4.12's branch stability rests.","marker":"[4]"},{"why":"supplies the deterministic algorithm for rational-exponent expansions used to extract the leading terms on the final branch.","marker":"[8]"}],"fun_headline_variants":["Monomial curve yields all near-optimal strategies for small ε","Exact monomial family for recursive games in polynomial time","One formula covers every fine accuracy in recursive games","Single weight vector encodes ε-optimal play for all small ε","Elementary proof plus fast algorithm for monomial strategies"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction assumes that removing one state at a time keeps the exact value data on one single irreducible real algebraic curve branch over an ordered number field, and that this branch is always recoverable from finitely many exactly computed sample points.","fun_headline_variants_meta":{"raw":{"variants":["Monomial curve yields all near-optimal strategies for small ε","Exact monomial family for recursive games in polynomial time","One formula covers every fine accuracy in recursive games","Single weight vector encodes ε-optimal play for all small ε","Elementary proof plus fast algorithm for monomial strategies"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000357,"raw_usage":{"total_tokens":2023,"prompt_tokens":1123,"completion_tokens":900,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":739,"completion_tokens_details":{"reasoning_tokens":819}},"tokens_in":739,"tokens_out":900,"duration_ms":9584,"temperature":1.0,"reasoning_tokens":819,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:35:09.747581+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the algorithm on a rational recursive game with two or three active states, then compare the recovered carrier branch at the dyadic sample points against an independent high-precision numerical continuation of the value curves; any divergence inside the certified $\\varepsilon_0$-interval would falsify the reconstruction claim. A more targeted test looks for an ordered algebraic field and a discounted matrix family in which the same covering determinant recurs along a sequence of discounts tending to zero, its derivative along the value coordinate vanishes at the limit point, and yet the value still changes — exactly the configuration that would break Lemma 4.12's coverage of coordinate candidates.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines recursive games and supplies the one-sided regions and fixed-point value theory that the whole construction starts from."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"states the prior monomial-family existence theorem whose proof this paper repairs and whose construction Section 3 replaces; it is the baseline the new proof must match."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"is the thesis containing the earlier flawed proof and posing the question of polynomial-time computation that Theorem 4.2 answers."},{"cited_title":"Exact Algorithms for Solving Stochastic Games","cited_arxiv_id":"1202.3898","evidence_quote":"supplies the strict reduced-state gap lemma and the Lipschitz bound used in the state-reduction recursion."},{"cited_title":"Attia and M","cited_arxiv_id":null,"evidence_quote":"provides the determinant-cover representation of matrix-game values and the recurring-kernel property on which Lemma 4.12's branch stability rests."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the deterministic algorithm for rational-exponent expansions used to extract the leading terms on the final branch."}],"review_version":1}