{"id":"c0493519-be94-48ac-8f5c-41fbbe75b869","arxiv_id":"2601.05965","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For fixed n≥3, the large-k connected fraction of generic games with a pure Nash equilibrium is asymptotically 1−ζ_n, with ζ_n explicit and tending to 0 rapidly in n.","lead":"This paper proves an exact asymptotic limit for the fraction of random many-action games whose best-response graph is connected. It shows that a simple adaptive dynamic will find a pure Nash equilibrium in almost all games that have one, despite worst-case impossibility results.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Lemma 11's constant is load-bearing but supported by the written argument.","rationale":"The reader's weakest_assumption correctly identifies Lemma 11's constant as the most load-bearing part of the proof: if the probability of a good cycle in a slice were o(1), the high-probability connectivity argument in Theorem 4 would collapse. However, I find the proof of Lemma 11 adequate: it establishes a constant lower bound through a birthday-problem argument and a Markov bound on the number of cycles, with explicit constants. I also checked the surrounding steps—Theorem 7's coupling, Lemmas 12–14, and the Poisson deduction—and found no critical gap. The only real omission is a short justification that bad sinks are unreachable from every non-sink; that follows from the basin size bound and the abundance of non-sinks, so it does not change the verdict. Therefore the reader's ACCEPT verdict should stand unchanged.","tokens_in":34162,"tokens_out":46040,"duration_ms":388701,"concrete_test":"Run a Monte Carlo check of Lemma 11 for, say, k=10^4: generate 10^5 independent random 2D slices of #»L(3,k), and for each record whether it contains a directed cycle of length ≥√k whose in-slice basin has size ≥k²/(800 log k). If the empirical probability is not at least about 0.01 with a small standard error, the good-cycle scaffolding fails; otherwise the central concern is settled.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I reviewed the central scaffold for Theorem 4: Theorem 7's Poisson approximation for good/bad sinks, Lemma 11's good-cycle ubiquity, Lemmas 12–14 connecting good cycles to sinks, and the final identification of good/bad sinks with reachable/unreachable sinks. The most delicate step is Lemma 11's claim that a slice contains a good cycle with probability at least 1/100. The proof gives E[vertices in basins of long cycles] ≥ k²/9, bounds the total number of long cycles by O(log k), and combines these to obtain the constant bound; the chosen constants δ=1/20 and λ=34200/929 are consistent. The Poisson approximation in Theorem 7 is supported by the method-of-moments argument with coupling error o(1). For the identification step, the paper asserts without detail that bad sinks are exactly the sinks not reachable from every non-sink; this is fillable because a bad sink has at most k^{ε+1} vertices in its basin while there are ~kⁿ non-sinks w.h.p., so the omission is minor and not load-bearing. I did not find an internal inconsistency or a reliance on an unsupported external assumption that would threaten the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the typical connectivity of generic n-player k-action games. A game is connected if it has a pure Nash equilibrium and every non-equilibrium action profile has a best-response path to every pure Nash equilibrium. For fixed n≥3 and k→∞, the paper claims (Theorem 1) that the fraction of generic games with a pure Nash equilibrium that are connected tends to 1−ζ_n, where ζ_n is an explicit positive constant decreasing rapidly in n. It also claims (Theorem 2) that as n→∞ this fraction tends to 1 uniformly over all k≥2. The technical engine is a random subdigraph model L(n,k) of the directed Hamming graph, in which each line independently has a uniformly chosen winner. Theorem 4 states that, for n≤k^{1/2−ε}, the number X of sinks reachable from every non-sink and the number Y of sinks not reachable from every non-sink are asymptotically independent Poisson random variables with means 1−p and p, where p=(η_{n−1})^n and η_x is the extinction probability of a Galton–Watson process with offspring distribution Poi(x). The proof uses a branching-process approximation for good/bad sinks, a 'good-cycle' scaffold to find a large strongly connected component, and several union-bound estimates. The paper also derives an adaptive-dynamics consequence (Proposition 3).","tokens_in":34429,"tokens_out":25608,"duration_ms":240307,"significance":"If the results hold, this is a significant contribution to the random-games and adaptive-dynamics literature. The paper resolves the previously open many-action regime, gives an explicit constant ζ_n, and complements the authors' earlier many-player result. The probabilistic technique—combining branching-process extinction with good-cycle ubiquity in 2-dimensional slices—is novel and likely to be useful beyond this setting. The paper is careful in connecting the random-graph model to generic games and in stating the implications for simple adaptive dynamics. The proofs are long and structured, and several estimates (Lemmas 11–14, 27–35) are plausible and checkable. However, two gaps in the written proofs of Theorems 4 and 5 need attention before the paper is fully convincing.","major_comments":[{"comment":"The proof fixes ε=1/10 and invokes Theorem 7. Theorem 7 requires n≤k^{ε}/log k, i.e. n≤k^{1/10}/log k. The hypothesis of Theorem 4 only gives n≤k^{1/2−δ} for some δ>0, which allows n(k) to grow like k^{1/5}; such functions do not satisfy n≤k^{1/10}/log k. Thus the proof as written does not cover the full stated range of Theorem 4. This is load-bearing for Theorem 4 as a statement about growing n. A simple fix is to split the proof: for fixed n (the case needed for Theorem 1), Theorem 7 applies for large k; for n(k)→∞, p→0 and Lemma 8 (or a direct branching-process bound) implies that bad sinks are o(1) in probability, while the total number of sinks is asymptotically Poi(1), giving the stated limit. Please clarify this case.","section":"§3, Proof of Theorem 4"},{"comment":"In the case k≤δ√(n/log n), the proof claims: 'By Theorem 15, with probability at least 1−2^{−cn}, every non-sink can reach every sink.' This inference is not immediate from the stated Theorem 15, which only gives a dichotomy: every vertex is either reached from at most N_B(1+ε)k log k vertices or from every non-sink. A sink in the first category would violate the desired event. The proof should explicitly rule out the first category for sinks in this regime. The missing observation is that every sink has at least n(k−1)+1 vertices in its basin (all vertices on the n lines through the sink, since the sink wins each such line), and in the regime k≤δ√(n/log n) this is ≫ N_B(1+ε)k log k for large n. This is likely what the assumption n≥2√(n log n) is for, but it is not stated. Please add this argument.","section":"§3, Proof of Theorem 5"}],"minor_comments":[{"comment":"The displayed formula for ζ_n is ambiguous as typeset: 'ζ_n = 1 − e^{−λ_n}(1−e^{λ_n−1})/(1−e^{−1})' should read ζ_n = (1−e^{−λ_n})/(1−e^{−1}), or at least include parentheses around the numerator. The current layout can confuse the reader.","section":"§1.2, Theorem 1"},{"comment":"Lemma 8 is stated for all n,k≥2, but its derivation in Section 5 relies on Lemma 27, which is stated only for n≤k^{ε}/log k. The coupling argument actually works for n≤k^{ε} when ε<1/2 (the error is then O(k^{2ε−1})), and for n≥k^{ε} there are no ε-bad sinks. The manuscript should state this extension so the reader can verify the unconditional form of Lemma 8.","section":"§5, Lemma 8"},{"comment":"The exploration process starting from a point implicitly assumes the starting point has an outgoing horizontal edge; if the point wins its horizontal line, the process cannot start. This occurs with probability 1/k per starting point, so the constant 1/9 is unaffected asymptotically, but the proof should mention this negligible conditioning issue.","section":"§6, Lemma 11 proof"},{"comment":"The line 'Suppose also that n is large enough that n≥2√(n log n)' is confusing as written; for large n this is equivalent to n≥C log n for a constant C. The intended use is to ensure n(k−1)+1 ≫ k log k in the small-k case, and this implication should be spelled out.","section":"§3, Proof of Theorem 5"}],"recommendation":"major_revision","confidential_remarks":"The paper makes a strong contribution and the gaps identified above are local and repairable. I recommend major revision rather than rejection. In particular, the proof of Theorem 4 needs a clear treatment of the growing-n range, and the proof of Theorem 5 needs the missing argument ruling out small-basin sinks in the k≤δ√(n/log n) regime. The reader's report was more favorable, but these points are genuine and should be addressed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this paper actually resolves the large-k regime that their 2023 paper left open, and it does so with new machinery rather than a minor tweak. For fixed n ≥ 3, the fraction of generic n-player k-action games with a pure Nash equilibrium that are connected tends to 1 − ζ_n, with ζ_n explicit and tiny. The proof gives a Poisson approximation for the numbers of sinks reachable and not reachable from every non-sink, and the limiting constants come from extinction probabilities of Poisson Galton-Watson processes. That is a real result, and the paper's Theorem 2 and Proposition 3 put it together sensibly with their earlier many-player result and with best-response dynamics with inertia.\n\nWhat is good: the paper is honest about its debts. Theorem 2 leans on Theorem 15 from Johnston-Savery-Scott-Tarbush 2023, and that is a cited external theorem with an independent proof, not a circular step. The new large-k proofs are structured and the key estimates are laid out in enough detail that a patient referee can check them. The stress-test note's concern about Lemma 11's 1/100 constant being load-bearing is fair, but the written proof gives a real argument for it: expectation of vertices in long-cycle basins is at least k^2/9, and the cycle-count bound is O(log k). The constants are ugly but consistent.\n\nSoft spots, in proportion: the proof is long and dense, and a lot of the heavy lifting sits in estimates (Lemmas 11–14, 27–35) that are easy to miss. The identification of bad sinks with sinks not reachable from every non-sink is asserted briefly; the missing detail is fillable because a bad sink has at most k^{ε+1} vertices in its basin while there are ~k^n non-sinks w.h.p. That is a minor gap, not a fatal one. The arbitrary constants in Lemma 11 (δ=1/20, λ=34200/929) are inelegant but not suspicious. The paper also correctly notes that the n=2 case behaves differently and cites the existing results. I did not find a load-bearing flaw.\n\nWho is this for: random game theorists and probabilistic combinatorists working on best-response graphs and adaptive dynamics. The typical-case guarantee for a simple adaptive dynamic, set against Hart-Mas-Colell, is worth having.\n\nRecommendation: send it to peer review. It deserves careful referees, and with minor tightening of the bad-sink identification and the long estimate chain, it should be publishable.","headline":"This is a serious, mostly sound paper that fills the large-k gap left open by the authors' earlier work, with a genuinely new explicit limiting constant and quite intricate proof machinery; it deserves a real referee.","tokens_in":34895,"tokens_out":1289,"would_cite":true,"duration_ms":17748,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A06","91A26","60J80","05C80","05C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that for a fixed number of players n≥3, the fraction of many-action generic games with a pure Nash equilibrium that are connected tends to the explicit constant 1−ζ_n as the number of actions grows, where ζ_n is small and v","keywords":["game connectivity","adaptive dynamics","best-response graphs","pure Nash equilibrium","random games","Galton-Watson branching processes","Hamming graphs","Poisson approximation"],"falsifier":"Simulate the random directed Hamming subgraph L(3,k) for large k (e.g., k=10^6), count the sinks reachable from every non-sink and those not reachable from every non-sink, and test whether their joint distribution converges to independent Poisson variables with means 1−p and p, where p=(η_2)^3≈0.0132. Also simulate random generic 3-player k-action games and estimate the connected fraction among those with a pure Nash equilibrium; if it does not approach 1−ζ_3, the theorem is false.","tokens_in":34057,"feed_emoji":"🎲","tokens_out":5609,"duration_ms":51861,"temperature":0.7,"pith_summary":"The paper studies generic n-player k-action games (no indifferences) and asks: among those that have a pure Nash equilibrium, what fraction are 'connected' — meaning from every action profile that is not an equilibrium, best-response dynamics can reach every equilibrium? In the many-actions regime (k large, n fixed), the answer is not 1: the fraction tends to 1 − ζ_n, where ζ_n is an explicit positive constant. For n≥3 this constant is small (ζ_3 ≈ 0.0132, ζ_4 ≈ 0.00002) and decays rapidly with n, so almost all many-player-many-action games are connected. The paper proves this by analysing random best-response graphs as random subgraphs of directed Hamming graphs, showing the numbers of 'good' and 'bad' sinks are asymptotically independent Poisson variables. As a consequence, a simple adaptive dynamic (best-response with inertia) converges to a pure Nash equilibrium in all but a vanishingly small fraction of generic games that have one.","feed_headline":"Most many-action games are connected — with an explicit exception","feed_subtitle":"For n≥3 players, the tiny gap ζ_n vanishes rapidly; simple best-response dynamics almost always find equilibrium.","key_machinery":"The central object is the random subdigraph of the directed Hamming graph, where for each line (a set of action profiles differing in one coordinate) a winner is chosen uniformly and all edges not ending at the winner are deleted; sinks correspond to pure Nash equilibria. The argument identifies 'good' sinks, reachable from many lines, and 'bad' sinks, reachable from few, and shows their counts are asymptotically independent Poisson variables. The probability p that a sink is bad is controlled by the extinction probability of a Galton-Watson branching process with offspring distribution approximating Poi(n−1). Connectivity is established via 'good cycles' in 2-dimensional slices: directed cy","core_discovery":"For fixed n≥3, as k→∞, the fraction of generic n-player k-action games with a pure Nash equilibrium that are connected tends to 1 − ζ_n, with ζ_n = 1 − (e^{−λ_n}(1 − e^{λ_n−1}))/(1 − e^{−1}), where λ_n is the smallest positive solution to x^{1/n} = e^{(n−1)(x^{1/(n−1)})}. Equivalently, in the random directed Hamming graph L(n,k) in which each line selects a uniform winner, the number of sinks reachable from every non-sink and the number not reachable from every non-sink are asymptotically independent Poisson random variables with means 1−p and p, p=(η_{n−1})^n, giving connected fraction (e^{−p}−e^{−1})/(1−e^{−1}) = 1−ζ_n. Thus a small but non-vanishing constant fraction of many-action games","pith_inferences":["The explicit ζ_n links a purely game-theoretic prevalence question to the extinction probability of a Poisson branching process; this suggests the 'hard' games in the large-action regime are precisely those where a backwards exploration from a Nash equilibrium dies out after seeing few lines.","The Poisson-independence structure of good/bad sinks suggests that, for fixed n, the distribution of the number of equilibria reachable from all non-equilibria obeys a simple law; one could numerically test the predicted Poi(1−p) and Poi(p) counts in simulated random games.","The contrast between n=2 (fraction → 0) and n≥3 (fraction → 1−ζ_n) indicates a phase transition in best-response connectivity as the number of players crosses 3; this may guide intuition for which games are amenable to decentralized learning.","The proof techniques — good cycles in slices and branching-process approximations — might extend to other random structures on Hamming graphs, such as best-response dynamics in games with correlated payoffs or with heterogeneous action sets."],"forward_implications":["For fixed n≥3, as k→∞, the connected fraction tends to 1−ζ_n; for n=3 this is about 0.9868, for n=4 about 0.99998.","As n→∞, the connected fraction tends to 1 uniformly over k (Theorem 2), so the many-player and many-action regimes together give connectedness in the double limit.","A simple adaptive dynamic — best-response with inertia — converges almost surely to a pure Nash equilibrium in all but a vanishingly small fraction of generic games that have one (Proposition 3).","For n=2, the connected fraction tends to 0, so the n≥3 behavior is special.","The iterated limits lim_{n→∞}lim_{k→∞} and lim_{k→∞}lim_{n→∞} both give connected fraction 1."],"fun_headline_variants":["Many-action games: explicit gap in connectivity shrinks as players grow","Connectivity in many-action games: rare exceptions vanish for n≥3","Non-connected many-action games: constant fraction for fixed n, then fades","Best-response paths nearly always exist in many-action games with many players","Game connectivity: a tiny constant fraction of exceptions disappear as players increase"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof of Theorem 4 and hence Theorem 1 depends on the claim that, with probability at least 1/100, each 2-dimensional slice of the random Hamming subgraph contains a 'good cycle' of length at least √k with a basin of k^2/(800 log k) vertices (Lemma 11); if this probability were o(1), the strong-connectivity argument would fail and the constant ζ_n would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Many-action games: explicit gap in connectivity shrinks as players grow","Connectivity in many-action games: rare exceptions vanish for n≥3","Non-connected many-action games: constant fraction for fixed n, then fades","Best-response paths nearly always exist in many-action games with many players","Game connectivity: a tiny constant fraction of exceptions disappear as players increase"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000243,"raw_usage":{"total_tokens":1418,"prompt_tokens":850,"completion_tokens":568,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":594,"completion_tokens_details":{"reasoning_tokens":474}},"tokens_in":594,"tokens_out":568,"duration_ms":6566,"temperature":1.0,"reasoning_tokens":474,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T11:30:00.514032+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the random directed Hamming subgraph L(3,k) for large k (e.g., k=10^6), count the sinks reachable from every non-sink and those not reachable from every non-sink, and test whether their joint distribution converges to independent Poisson variables with means 1−p and p, where p=(η_2)^3≈0.0132. Also simulate random generic 3-player k-action games and estimate the connected fraction among those with a pure Nash equilibrium; if it does not approach 1−ζ_3, the theorem is false.","supporting_citations":[],"review_version":1}