{"id":"00511d83-e6d8-497b-b309-126c749cfb3d","arxiv_id":"2607.06334","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"The Random-Action-Removal algorithm solves n-state, m-action 2-player games in e^{O(√(n ln(m/n)))} time, improving the previous e^{O(√(n ln(m/√n)))} bound by exploiting the hypercube structure of the game.","lead":"This paper improves the analysis of the Random-Action-Removal algorithm for solving 2-player turn-based games on graphs, reducing the complexity bound from e^{O(√(n ln(m/√n)))} to e^{O(√(n ln(m/n)))}. A smart generalist might read it because it tightens the best-known upper bound for a major open problem in algorithmic game theory and combinatorial optimization.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The proof of Theorem 8.2 is correct: the bound $S_k ≤ 1/√N$ follows from a standard inequality on concave functions, and all intermediate steps check out.","rationale":"The reader correctly identifies the bound $S_k ≤ 1/√N$ as the load-bearing step in the proof of Theorem 8.2 — it is the final link that closes the induction. However, upon careful verification, this bound is correctly proved using a standard inequality on square roots ($√x − √(x−c) ≤ √c$), and the prerequisite $Φ ≥ 4α/(1+α)$ is rigorously established in Appendix J.1. I also verified the full chain of inequalities in the proof: the recurrence derivation (Lemma 5.5), the PDE (Lemma 8.4), the concavity (Lemma 8.5), the integral bound (10), the MVT bound (9), and the quadratic evaluation (12). All steps are correct. The paper's central claim — that Random-Action-Removal runs in $e^{O(√{n ln(m/n)})}$ time — is well-supported by a rigorous proof. The reader's ACCEPT verdict with HIGH confidence is appropriate. The correctness risk should be downgraded from 'unknown' to 'low' given the transparent and verifiable proof structure.","tokens_in":30843,"tokens_out":10935,"duration_ms":615149,"concrete_test":"Independently verify the bound $S_k ≤ 1/√N$ by numerically computing $Φ(α)$ via integration of the ODE (6) for a dense grid of $α$ values in $[1, 10^6]$, then checking that $S_k = Φ'(α)/√(nΦ(α))$ satisfies $S_k ≤ 1/√(α(1+α)n)$ at each point. This would confirm the analytic bound computationally across the full parameter range.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I carefully traced the proof of Theorem 8.2, which is the central technical result. The reader correctly identifies the bound $S_k ≤ 1/√N$ as the final link in the chain, but this bound is correctly established. The derivation proceeds as follows: from Lemma 8.3 and the ODE (6), $S_k = (1/(2α√n))(√Φ − √(Φ − 4α/(1+α)))$. The standard inequality $√x − √(x−c) ≤ √c$ for $x ≥ c$ (which holds since $(√x − √(x−c))^2 = 2x − c − 2√{x(x−c)} ≤ c$ iff $x ≥ c$) gives $S_k ≤ (1/(2α√n))√(4α/(1+α)) = 1/√(α(1+α)n) = 1/√(αN) ≤ 1/√N$ since $α ≥ 1$. The condition $Φ ≥ 4α/(1+α)$ is established in Appendix J.1 via the comparison principle with $g(α) = 4α/(1+α)$, verifying $g'(α) ≤ f(α, g(α))$. I also verified the other key steps: (1) the recurrence (1) correctly captures the frozen-states argument from Lemma 5.3, (2) the PDE $(n+k)S_n S_k = 1$ (Lemma 8.4) follows algebraically from the ODE (5), (3) the integral bound (10) correctly uses concavity of $S$ in $n$ and the PDE, (4) the mean-value-theorem bound (9) correctly uses concavity in $k$, and (5) the quadratic in (12) evaluates to $−(√N−1)^2/(2N^2) ≤ 0$ at $S_k = 1/√N$. The induction structure is sound: the base case $k ≤ n$ uses Lemma 7.1, and the inductive step for $0 < n < k$ uses the induction hypothesis on $(n, k−1)$ and $(j, k)$ for $j < n$. The existence, uniqueness, and bounds on $Φ(α)$ in Appendix J use standard ODE techniques (Peano existence, one-sided Lipschitz for uniqueness, comparison principle). I found no gap in the argument.","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","summary":"This paper presents an improved analysis of the Random-Action-Removal algorithm for solving 2-player turn-based stochastic games (2-TBSGs) and, more generally, for finding the sink of an Acyclic Unique Sink Orientation (AUSO) of a non-binary hypercube. The algorithm, a recasting of the dual simplex algorithm of Matoušek, Sharir, and Welzl (MSW), was previously known to run in $e^{O(√{n ln(m/√n)})}$ time for games with $n$ states and $m$ actions. The author exploits the hypercube structure of games—specifically, the partition of actions into states—to derive a tighter bivariate recurrence relation (Definition 5.4). The key innovation is the 'frozen states' argument (Lemma 5.3), which shows that the second recursive call of the algorithm often operates on an AUSO with effectively fewer states. The resulting recurrence is then solved using a discrete WKB (Wentzel–Kramers–Brillouin) method: an ansatz $U(n,k) = (n+k)e^{2√{nΦ(k/n)}}$ is proposed, where $Φ(α)$ satisfies an ODE derived as the eikonal equation. The main theorem (Theorem 8.2) proves $F(n,k) ≤ U(n,k)$ by induction, reducing to the verification of inequality (11), which is established via concavity arguments and the bound $S_k ≤ 1/√N$. The final bound is $e^{O(√{n ln(m/n)})}$, improving the previous result and matching (with better constants) the bound of Hansen and Zwick (STOC 2015) obtained via a more complex algorithm.","tokens_in":31368,"tokens_out":2066,"duration_ms":395493,"significance":"The result is a genuine improvement over the state of the art for a natural and important class of games. The improvement from $e^{O(√{n ln(m/√n)})}$ to $e^{O(√{n ln(m/n)})}$ is especially notable when $m = O(n)$, where the bound drops from $e^{O(√{n ln n})}$ to $e^{O(√n)}$, providing a smooth transition from binary to non-binary games. The paper is commendably self-contained and transparent: the proof of Theorem 8.2 is fully rigorous and verifiable by hand, with all ODE existence/uniqueness/bounds deferred to Appendix J using standard techniques (Peano existence, one-sided Lipschitz, comparison principle). The discrete WKB technique applied to algorithm analysis is interesting in its own right and may find broader use. The author also discloses AI assistance (Gemini, ChatGPT) for heuristic derivation, but the final argument is traditional and checkable. The paper provides falsifiable numerical evidence (Figure 3) consistent with the theoretical bounds.","major_comments":[{"comment":"Theorem 8.2, inequality (7): The induction proof requires $F(n,k) ≤ U(n,k)$ for $k ≤ n$ as the base case, citing Lemma 7.1. However, Lemma 7.1 gives $F(n,k) ≤ e^{2√{n+k}}$, while $U(n,k) = (n+k)e^{2√{nΦ(k/n)}}$ with $Φ(α) = 1+α$ for $α ≤ 1$. This yields $U(n,k) = (n+k)e^{2√{n+k}}$ for $k ≤ n$. The factor $(n+k)$ makes $U(n,k)$ strictly larger than the Lemma 7.1 bound, so the base case does hold. However, the text on p.10 states 'For $k ≤ n$ we already know that the inequality holds, even without the multiplicative $n+k$ factor.' This is correct but the logical flow could be clearer: the reader needs to verify that $e^{2√{n+k}} ≤ (n+k)e^{2√{n+k}}$, which is trivial but should be stated explicitly for completeness of the induction base.","section":null},{"comment":"Section 5, Lemma 5.5, proof: The recurrence (1) sums $F(n-i, k)$ for $i = 1, ..., n$, but in inequality (7) of Theorem 8.2 the sum is $U(j, k)$ for $j = 0, ..., n-1$. These are equivalent under the substitution $j = n - i$, but the indices in the recurrence (1) as stated sum from $i=1$ to $n$, which includes $F(0, k) = 1$. In inequality (7), the sum is $j=0$ to $n-1$, which also includes $U(0, k)$. This is consistent, but the notation switch between $F(n-i, k)$ and $U(j, k)$ could briefly be flagged to avoid confusion.","section":null},{"comment":"Appendix J.1: The comparison principle argument for $Φ(α) ≥ g(α) = 4α/(1+α)$ checks that $g'(α) ≤ f(α, g(α))$. The computation shows $g'(α) = (2/(1+α))^2 = 4/(1+α)^2$ and $f(α, g(α)) = g(α)/(2α) = 2/(1+α)$. The claim that $4/(1+α)^2 ≤ 2/(1+α)$ for $α ≥ 1$ is correct (it reduces to $2 ≤ 1+α$). This is fine, but the intermediate step $f(α, g(α)) = g(α)/(2α)$ should be briefly justified: when $Φ = g(α) = 4α/(1+α)$, the discriminant $Φ^2 - 4αΦ/(1+α) = 0$, so $f(α, g(α)) = g(α)/(2α)$. This is implicit but worth making explicit.","section":null}],"minor_comments":[{"comment":"Title and Abstract: 'theRandom-Action-Removal' — missing space after 'the' in the title line of the full text.","section":null},{"comment":"p.3, 'reachs' should be 'reaches'.","section":null},{"comment":"p.6, 'perfored' should be 'performed' (appears twice: once in the Section 8 heading and once in Theorem 8.2 statement).","section":null},{"comment":"p.9, equation (4): The expression $e^{2q nΦ(k/n)}$ uses 'q' for the square root symbol. This appears to be a rendering issue but should be checked in the source.","section":null},{"comment":"p.9, Lemma 8.1: The bound is stated as $Φ(α) ≤ 2 + ℓ + ln(ℓ+1)$ where $ℓ = ln((1+α)/2)$. The abstract and introduction claim $e^{O(√{n ln(m/n)})}$. The connection between $Φ(α) = O(ln α)$ and the final $O(√{n ln(m/n)})$ bound is made implicitly. A one-line remark after Lemma 8.1 or after Theorem 8.2 explicitly stating 'Since $Φ(k/n) = O(ln(k/n)) = O(ln(m/n))$, the bound is $e^{O(√{n ln(m/n)})}$' would improve readability.","section":null},{"comment":"Figure 3 caption: 'numerical 100( )' appears garbled. Should read something like 'numerical $Φ̃_{100}(α)$' or similar.","section":null},{"comment":"Appendix I, p.22: The heuristic derivation mentions $U(n,k-1)/U(n,k) ≈ e^{-S_k} ≈ 1 - S_k$, but the rigorous proof in Section 8 uses the mean value theorem and concavity to get $(1-1/N)e^{-S_k}$. The transition from heuristic to rigorous could note that the $(n+k)$ prefactor is introduced precisely to supply the $(1-1/N)$ factor.","section":null},{"comment":"References: The citation [GJR08] is listed as 'Gärtner, Morris, and Rüst' in the text but the bibliographic entry uses 'Morris Jr.' — minor inconsistency.","section":null},{"comment":"p.5, Section 3: 'Apositional strategy' should be 'A positional strategy'.","section":null},{"comment":"p.12, proof of Theorem 8.2: 'it is enough to show' appears twice in close succession (once for inequality (12), once for $S_k ≤ 1/√N$). Slight rewording could improve flow.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is by a single author (Uri Zwick) who is a recognized expert in this area. The mathematical content is sound — I traced the full proof of Theorem 8.2 and the appendices, and the argument is correct. The major comments are essentially about presentation clarity in load-bearing steps, not about correctness gaps. The AI disclosure is appropriate and the final proof is independent of AI tools. The paper fits the journal's scope well. I recommend minor revision."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for a careful reading and for three constructive comments, all of which request minor clarifications that we are happy to incorporate. All three points concern presentation rather than correctness.","responses":[{"response":"The referee is correct that the base case verification, while trivial, should be stated explicitly. We will revise the text on p.10 to spell out the chain of inequalities: by Lemma 7.1, F(n,k) ≤ e^{2√(n+k)}; for k ≤ n (i.e., α = k/n ≤ 1), we have Φ(α) = 1+α, so U(n,k) = (n+k)e^{2√(n+k)}; since n+k ≥ 1, we have e^{2√(n+k)} ≤ (n+k)e^{2√(n+k)} = U(n,k), and hence F(n,k) ≤ U(n,k). This makes the induction base fully explicit.","revision_made":"yes","referee_comment":"Theorem 8.2, inequality (7): The induction proof requires F(n,k) ≤ U(n,k) for k ≤ n as the base case, citing Lemma 7.1. However, Lemma 7.1 gives F(n,k) ≤ e^{2√(n+k)}, while U(n,k) = (n+k)e^{2√(nΦ(k/n)}} with Φ(α) = 1+α for α ≤ 1. This yields U(n,k) = (n+k)e^{2√(n+k}} for k ≤ n. The factor (n+k) makes U(n,k) strictly larger than the Lemma 7.1 bound, so the base case does hold. However, the text on p.10 states 'For k ≤ n we already know that the inequality holds, even without the multiplicative n+k factor.' This is correct but the logical flow could be clearer: the reader needs to verify that e^{2√(n+k}} ≤ (n+k)e^{2√(n+k}}, which is trivial but should be stated explicitly for completeness of the induction base."},{"response":"We agree that the change of summation index between recurrence (1) (written as a sum over i = 1, ..., n of F(n-i, k)) and inequality (7) (written as a sum over j = 0, ..., n-1 of U(j, k)) could cause confusion. We will add a brief remark at the point where inequality (7) is introduced, noting that the substitution j = n-i converts the sum in recurrence (1) into the form used in (7), and that the two formulations are equivalent.","revision_made":"yes","referee_comment":"Section 5, Lemma 5.5, proof: The recurrence (1) sums F(n-i, k) for i = 1, ..., n, but in inequality (7) of Theorem 8.2 the sum is U(j, k) for j = 0, ..., n-1. These are equivalent under the substitution j = n - i, but the indices in the recurrence (1) as stated sum from i=1 to n, which includes F(0, k) = 1. In inequality (7), the sum is j=0 to n-1, which also includes U(0, k). This is consistent, but the notation switch between F(n-i, k) and U(j, k) could briefly be flagged to avoid confusion."},{"response":"The referee's observation is correct. When Φ = g(α) = 4α/(1+α), the discriminant under the square root in equation (6) becomes Φ² - 4αΦ/(1+α) = (4α/(1+α))² - 4α·(4α/(1+α))/(1+α) = 16α²/(1+α)² - 16α²/(1+α)² = 0, so the square root vanishes and f(α, g(α)) = g(α)/(2α). We will add this one-line justification to Appendix J.1.","revision_made":"yes","referee_comment":"Appendix J.1: The comparison principle argument for Φ(α) ≥ g(α) = 4α/(1+α) checks that g'(α) ≤ f(α, g(α)). The computation shows g'(α) = (2/(1+α))^2 = 4/(1+α)^2 and f(α, g(α)) = g(α)/(2α) = 2/(1+α). The claim that 4/(1+α)^2 ≤ 2/(1+α) for α ≥ 1 is correct (it reduces to 2 ≤ 1+α). This is fine, but the intermediate step f(α, g(α)) = g(α)/(2α) should be briefly justified: when Φ = g(α) = 4α/(1+α), the discriminant Φ^2 - 4αΦ/(1+α) = 0, so f(α, g(α)) = g(α)/(2α). This is implicit but worth making explicit."}],"tokens_in":31252,"tokens_out":1482,"duration_ms":120088,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"Bottom line: Zwick improves the upper bound on Random-Action-Removal from e^{O(√(n ln(m/√n)))} to e^{O(√(n ln(m/n)))} by exploiting the hypercube structure of games — something the prior MSW analysis ignored for non-binary AUSOs. The improvement is asymptotically modest but meaningful, especially when m = O(n), where the bound drops from e^{O(√(n ln n))} to e^{O(√n)}, giving a clean transition from binary to non-binary games. The same bound was achievable via Hansen-Zwick (STOC 2015) but through a much more complicated algorithm; the point here is that the simple, natural algorithm already achieves it without modification. That is a real contribution. The new ingredient is a tighter bivariate recurrence (Definition 5.4) that tracks frozen states — when improvement steps effectively reduce the number of active states, not just the action count. The frozen-states argument (Lemma 5.3) is clean and convincing. Solving the recurrence requires a discrete WKB ansatz U(n,k) = (n+k)e^{2√(nΦ(k/n))}, where Φ satisfies an ODE with no closed-form solution. The author handles this by working with the implicit solution and deriving rigorous bounds via standard ODE comparison principles. The stress-test note traced the main induction (Theorem 8.2) carefully. The critical link — bounding S_k ≤ 1/√N — follows from the standard inequality √x − √(x−c) ≤ √c, applied to Φ ≥ 4α/(1+α), which is established in Appendix J via comparison with g(α) = 4α/(1+α). I checked the chain: the PDE (n+k)S_n S_k = 1 follows algebraically from the ODE, the concavity bounds are correct, and the quadratic in (12) evaluates to −(√N−1)²/(2N²) ≤ 0. No gaps found. The AI disclosure (Gemini/ChatGPT assisted with the ansatz) is appropriate — the final argument is short, explicit, and verifiable by hand. Soft spots are minor. The (n+k) prefactor in U(n,k) is a proof convenience, not tight; the author notes that (n+k)^{−1/2} would likely work but requires more terms. The lower bound on Φ(α) is somewhat loose, but it does not affect the final asymptotic claim. The paper is for researchers in subexponential algorithm analysis and combinatorial game theory. It is a focused, technically clean result by an expert. It deserves a serious referee — someone who can verify the ODE analysis in the appendices and check the recurrence derivation against the algorithm semantics.","headline":"Solid improvement to the best known bound for Random-Action-Removal on 2-TBSGs. The proof checks out.","tokens_in":31863,"tokens_out":662,"would_cite":true,"duration_ms":162113,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Tighter bound for game-solving algorithm hits e^{O(√n)}","keywords":[],"falsifier":"Compute F(n,k) exactly for moderately large n and k with k > n (say n = 100, k = 500) and check whether F(n,k) exceeds U(n,k) = (n+k)e^{2√(nΦ(k/n))}. Alternatively, construct a specific family of AUSOs where the number of frozen states in the second recursive call is consistently smaller than the analysis assumes, which would make the actual expected path length larger than F(n,k).","tokens_in":31142,"feed_emoji":"🎲","tokens_out":916,"duration_ms":247738,"temperature":0.7,"pith_summary":"This paper proves that the Random-Action-Removal algorithm, a simple randomized strategy-iteration method for solving 2-player turn-based stochastic games and finding sinks of non-binary AUSOs, runs in e^{O(√(n ln(m/n)))} expected time on games with n states and m actions. This improves the previous e^{O(√(n ln(m/√n)))} bound inherited from a 1992 analysis that treated these games as generic LP-type problems. The key insight is that games and AUSOs possess a hypercube structure: actions are partitioned by state, and every strategy picks exactly one action per state. This structure was ignored in prior analyses. Exploiting it yields a tighter bivariate recurrence relation that tracks how frozen states, states whose actions become irrelevant as the algorithm progresses, reduce the effective problem size during the second recursive call. Solving this new recurrence requires a discrete WKB method, an asymptotic technique from mathematical physics, because the standard generating-function approach used for the old recurrence does not apply. The resulting bound is especially significant when m = O(n), the natural sparse regime, where the running time drops from e^{O(√(n ln n))} to e^{O(√n)}, giving a smooth transition between binary and non-binary games. The same e^{O(√(n ln(m/n)))} bound was previously achievable only by a substantially more complicated algorithm with worse constant factors; this paper shows the simple, unmodified Random-Action-Removal algorithm already achieves it.","feed_headline":"Simple game algorithm matches best known bound without modification","feed_subtitle":"Exploiting hypercube structure of stochastic games tightens the analysis of Random-Action-Removal to e^{O(√(n ln(m/n)))}, dropping to e^{O(√","key_machinery":"The argument rests on three components: (1) the notion of frozen states, which explains why the second recursive call is effectively on a smaller AUSO; (2) a bivariate recurrence F(n,k) that captures this state reduction; and (3) a discrete WKB asymptotic analysis of that recurrence, using an ansatz U(n,k) = (n+k)e^{S(n,k)} where S satisfies the PDE (n+k)S_n S_k = 1, which in turn reduces to an ODE for Φ(α) that can be bounded rigorously.","core_discovery":"The central discovery is that the hypercube structure of games and AUSOs, specifically the partitioning of actions into states where each strategy selects exactly one action per state, can be exploited to derive a strictly tighter recurrence for the expected number of improvement steps. When the algorithm removes a random action and recurses, the second recursive call often starts from a vertex where several states are frozen, meaning the effective number of states drops from n to n-i for some i. This yields the recurrence F(n,k) = F(n,k-1) + (1/(n+k)) * sum of F(n-i,k), where k = m - 2n is the excess action count. The solution to this recurrence is bounded by U(n,k) = (n+k) * e^{2√(nΦ(k/n))","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Tighter bound for Random-Action-Removal via game hypercube structure","Game structure sharpens analysis of Random-Action-Removal algorithm","Exploiting state-action partition tightens Random-Action-Removal bound","Simpler algorithm matches Hansen-Zwick bound for stochastic games","Random-Action-Removal achieves e^{O(√(n ln(m/n)))} for turn-based games"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The inductive proof that U(n,k) bounds F(n,k) works by showing that a certain quantity S_k is at most 1/√N (where N = n+k). This bound on S_k is derived from properties of the function Φ(α) and its differential equation. If S_k were to exceed 1/√N for some parameter values, the key inequality in the induction step would fail and the entire bounding argument would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Tighter bound for Random-Action-Removal via game hypercube structure","Game structure sharpens analysis of Random-Action-Removal algorithm","Exploiting state-action partition tightens Random-Action-Removal bound","Simpler algorithm matches Hansen-Zwick bound for stochastic games","Random-Action-Removal achieves e^{O(√(n ln(m/n)))} for turn-based games","Hypercube structure yields sharper recurrence for game-solving algorithm","Randomized strategy iteration bound tightened for 2-player games","Concise analysis improves Random-Action-Removal for stochastic games","Frozen states in recursion tighten expected step count for game algorithm"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":1285,"prompt_tokens":827,"completion_tokens":458,"prompt_tokens_details":null},"tokens_in":827,"tokens_out":458,"duration_ms":29954,"temperature":1.0,"reasoning_tokens":321,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T09:21:45.453012+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"Compute F(n,k) exactly for moderately large n and k with k > n (say n = 100, k = 500) and check whether F(n,k) exceeds U(n,k) = (n+k)e^{2√(nΦ(k/n))}. Alternatively, construct a specific family of AUSOs where the number of frozen states in the second recursive call is consistently smaller than the analysis assumes, which would make the actual expected path length larger than F(n,k).","supporting_citations":[],"review_version":1}