{"id":"6ab57039-4365-42bb-a1bb-dfba0027a2f6","arxiv_id":"1909.01758","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A Q-function value iteration scheme converges to a mean-field equilibrium in discrete-time mean-field games for both discounted and average costs.","lead":"Mean-field games describe many identical agents affecting each other through the aggregate state distribution. This paper constructs a value iteration algorithm whose fixed point is a mean-field equilibrium, under discounted and average costs, and proves contraction so the iteration converges.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The contraction theorem lacks a stated complete metric: W1 is only an extended metric on all of P(X), so Banach fixed point is not formally justified; a P1(X) self-map lemma is needed.","rationale":"The reader's weakest-assumption analysis identifies exactly the gap I find most load-bearing: the contraction theorems are stated on C×P(X) without a defined product metric, and W1 is only an extended metric that does not make P(X) complete for general Polish X. Since the central claim is convergence of value iteration to a fixed point via Banach's theorem, this missing completeness and self-map step directly undermines the formal validity of Theorems 1 and 3. The issue is concrete: to apply Banach, one needs a complete metric space that H actually maps into itself. The most natural candidate is C×P1(X) with metric d = ‖·‖_w + W1, because P1(X) is W1-complete for complete X. Whether H preserves P1(X) is not shown in the paper, although Assumption 1(b) may be sufficient to prove it; this makes the gap fixable rather than destructive. I do not see a more fundamental flaw: the perturbation analysis leading to (8) and the subsequent W1 bound for H2 are plausible, and the construction of the equilibrium from the fixed point in Theorems 2 and 4 follows from standard MDP verification arguments. The algorithm is asymptotic and not demonstrated numerically, as the reader notes, but that is secondary. Because the reader already returned CONDITIONAL and my concern matches the stated weakest assumption, no change to the verdict is warranted.","tokens_in":17563,"tokens_out":14137,"duration_ms":147750,"concrete_test":"Fix x0∈X and define P1(X)={ν∈P(X): ∫ dX(x,x0)ν(dx)<∞}. Equip C×P1(X) with d((Q,µ),(Q̂,μ̂)) = ‖Q-Q̂‖_w + W1(µ,μ̂). Check the two missing lemmas: (i) using Assumption 1(b), prove H2(Q,µ)∈P1(X) for every µ∈P1(X) by bounding ∫ dX(y,x0) H2(Q,µ)(dy) in terms of ∫ dX(x,x0)µ(dx) plus finite constants; (ii) combine inequalities (4) and (9) of Theorem 1 to verify d(H(Q,µ),H(Q̂,μ̂)) ≤ k d((Q,µ),(Q̂,μ̂)). If both hold, replace P(X) by P1(X) in Theorems 1 and 3 and the proof is complete. If (i) fails, exhibit a kernel satisfying Assumption 1 and a measure µ∈P1(X) with H2(Q,µ)∉P1(X); that would show the contraction is not a self-map on any W1-complete subspace and the fixed point step genuinely fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on Theorem 1 (discounted) and Theorem 3 (average cost), which assert that the MFE operators H and L are contractions on C×P(X) and hence have fixed points by Banach's theorem. However, no product metric is defined. The proof bounds the two coordinates separately: (4) bounds ‖H1(Q,µ)-H1(Q̂,μ̂)‖_w and (9) bounds W1(H2(Q,µ),H2(Q̂,μ̂)). To invoke Banach, one must introduce a metric such as d((Q,µ),(Q̂,μ̂)) = ‖Q-Q̂‖_w + W1(µ,μ̂) and show the contracted space is complete and H-invariant. The paper never does this. On the stated space C×P(X), W1 is only an extended metric: it can be infinite, and for a general non-compact Polish X, P(X) is not complete under W1. The natural repair is to restrict the measure component to P1(X), the set of probability measures with finite first moment, which is W1-complete when X is complete. But the paper does not state that H maps P1(X) into itself. This is plausibly derivable from Assumption 1(b) via a reference-point bound, but the derivation is absent. Without this self-map and completeness step, the Banach fixed point argument in Theorems 1 and 3 is not formally valid, so the convergence of the value iteration to a fixed point is not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies infinite-horizon discrete-time mean-field games with Polish state space and compact convex action space, under discounted and average cost criteria. It defines a mean-field equilibrium (MFE) operator H (discounted cost) and L (average cost) acting on pairs of Q-functions and state-measures, proves under Lipschitz, strong-convexity, and drift assumptions that these operators are contractions, invokes Banach's fixed point theorem, and then constructs a mean-field equilibrium from the fixed point as a deterministic policy minimizing the fixed-point Q-function. The paper also sketches the N-agent interpretation and positions the result as the first convergent computational scheme for mean-field games with abstract state spaces.","tokens_in":17895,"tokens_out":12498,"duration_ms":134442,"significance":"If the result holds, this is a useful advance: it gives a concrete value-iteration scheme with a convergence guarantee for discrete-time mean-field games beyond finite-state or linear models, and the use of Q-functions opens the door to model-free extensions. The proofs are largely self-contained, the coordinatewise contraction estimates are explicit, and the construction of the equilibrium policy from the fixed point is standard and plausible. However, the central fixed-point step is missing a formal metric and completeness argument, so the main theorems are not fully justified as written.","major_comments":[{"comment":"The Banach fixed-point step is not formally justified because no metric is defined on C×P(X). The proofs bound the two coordinates separately, using ‖·‖_w for the Q-coordinate and W1 for the measure coordinate, but coordinatewise bounds do not by themselves specify a complete metric on the product. On all of P(X), W1 is an extended metric (it can equal +∞), and for a general non-compact Polish X, P(X) is not complete under W1. To apply Banach's theorem the authors must (i) define a product metric such as d((Q,µ),(Q̂,μ̂)) = ‖Q−Q̂‖_w + γ W1(µ,μ̂) for a suitable γ>0, (ii) restrict the measure component to a W1-complete set, typically P1(X), and (iii) prove that H2 (resp. L2) maps P1(X) into itself and that the iterates starting from the algorithm's initial (Q0,µ0) stay in that set. The self-map and completeness steps are absent; without them Theorems 1 and 3 do not deliver the fixed point, and the convergence claims of Algorithms 1 and 2 are not established.","section":"§3.1, Theorem 1; §3.2, Theorem 3"},{"comment":"The proof that L1(Q,µ)∈M uses the bound ∫ wmax(y) q(dy|x,a,µ) ≤ α w(x,a). This requires an assumption relating the constant b in Assumption 3(b) to ∫ wmax dλ. The \"without loss of generality\" argument in Remark 1 is not written carefully: the function wmax is never defined, and the stated reduction sets b=∫ w dλ even though the expression that enters the proof is built from wmax. Moreover, the proposed operation of increasing α and adding a constant to w changes the data entering Assumption 3(c), so it cannot be swept into a WLOG statement without rechecking κ. As written, Lemma 2's norm bound is incomplete.","section":"§3.2, Lemma 2 and Remark 1"}],"minor_comments":[{"comment":"The loop condition \"(Qn,µn) ≠ (Qn−1,µn−1)\" is not implementable and appears to claim finite termination. The algorithms should state convergence in the limit as n→∞, or use an ε-stopping criterion.","section":"§3.1, Algorithm 1; §3.2, Algorithm 2"},{"comment":"The displayed inequality labeled (1) in the proof of (9) contains a garbled line: the second integrand has an extra outer integral and is missing the intended variables of integration. The subsequent paragraph explains the coupling argument, but the displayed line should be corrected.","section":"§3.1, proof of Theorem 1, Eq. (9)"},{"comment":"In the first displayed estimate, \"Q(dy|x,a,µ)\" should be \"q(dy|x,a,µ)\".","section":"§3.2, Lemma 2"},{"comment":"The notation wmax is used for the wmax-norm, but the function wmax itself is never defined. Please define it explicitly at first use.","section":"Notation, §2"}],"recommendation":"major_revision","confidential_remarks":"The main technical gap is the missing complete product metric and the missing P1-invariance proof. This seems repairable and is not a sign that the central idea is false; the coordinatewise contraction estimates are detailed and likely correct. I would encourage the editor to ask for a revision rather than reject."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: I'd send this out, with a request to patch one technical gap. The paper gives the first convergence guarantee I know for a value-iteration scheme computing mean-field equilibria in discrete-time mean-field games on Polish state spaces, for both discounted and average cost. The contraction theorem is probably correct, and the gap is fixable.\n\nWhat is actually new: prior work [30,35] proved existence but gave no algorithm; [17] studied fictitious play only for finite-state, finite-horizon games under monotonicity. Here the authors define an MFE operator built from Q-functions, prove it is a contraction under Assumptions 1-3, and then construct an equilibrium from its fixed point. The perturbation analysis around the greedy minimizer f (inequality (8)) is the real work, and it is carefully done. The contraction constants are explicit. The citation pattern is fine: self-citations to [30,35] are background existence results, not load-bearing, and the MDP facts from [19,20] are standard.\n\nSoft spots, in proportion. The main one is real: Theorems 1 and 3 state that H and L are contractions on C×P(X), but no product metric is ever defined. The proof bounds the two coordinates separately, in the w-norm and in W1, and then declares the contraction. That is not a contraction argument on C×P(X) as written. Worse, W1 is only an extended metric on all of P(X) and, for a general non-compact Polish X, P(X) is not complete under W1. Banach's fixed point theorem is therefore not formally applicable. The natural repair is to work on measures with finite first moment, P1(X), prove H2 and L2 map P1(X) into itself, and put a metric like d((Q,µ),(Q̂,μ̂)) = ‖Q−Q̂‖w + W1(µ,μ̂) on the product. This is plausibly derivable from Assumption 1(d), but the derivation is absent. So the central convergence claim is not established as written, though it is probably repairable.\n\nA second, smaller issue: in Remark 1 of the average-cost section, the \"without loss of generality\" normalization taking b = ∫w dλ is too quick. Changing α and adding a constant to w changes the weighted norm and the sets C and M; that needs a real justification, not a sentence. Finally, there are no numerical examples and the \"algorithm\" is a conceptual infinite-dimensional fixed-point iteration, so the practical reach is asymptotic. That is acceptable for a theory paper, but worth stating explicitly.\n\nWho this is for: anyone working on computation of mean-field equilibria in discrete time, and people looking for a Q-function route to Q-learning for MFGs. It deserves a serious referee. I recommend sending it out, with the metric/completeness gap and the Remark 1 normalization flagged for revision.","headline":"A genuine first: convergent value iteration for discrete-time mean-field games on Polish spaces, but the contraction proof needs a formally defined complete metric before the Banach step is valid.","tokens_in":18383,"tokens_out":3217,"would_cite":true,"duration_ms":35791,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A16","49N80","90C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a mean-field equilibrium operator is a contraction, so value iteration converges to a fixed point from which a mean-field equilibrium is constructed.","keywords":["mean-field games","value iteration","Q-functions","discounted cost","average cost","contraction mapping","Wasserstein distance","Markov decision processes"],"falsifier":"Run the proposed iteration on a scalar mean-field game with a heavy-tailed transition kernel, such as t-distributed noise, so that some iterates have infinite first moment; if the iterates do not converge in Wasserstein distance, or if two different initial pairs converge to different limits, then the claimed contraction and completeness fail.","tokens_in":17374,"feed_emoji":"🎯","tokens_out":6321,"duration_ms":64862,"temperature":0.7,"pith_summary":"Mean-field games describe a single agent optimizing against a distribution of many identical agents, and an equilibrium is a policy paired with a state distribution that each makes the other correct. This paper claims that, under regularity conditions, a single operator that updates both the Q-function and the state distribution is a contraction. Therefore iterating it from any starting point converges to a unique fixed point, and the greedy policy built from that fixed point's Q-function, together with the fixed point's distribution, is a mean-field equilibrium. This gives the first convergence-guaranteed algorithm for computing mean-field equilibria in discrete-time games with abstract Polish state spaces, for both discounted and average cost.","feed_headline":"Value iteration provably finds mean-field equilibria","feed_subtitle":"Contraction-mapping proof covers discounted and average cost with convergence guarantees.","key_machinery":"The central object is the mean-field equilibrium operator: $H(Q,\\mu)$ updates the Q-function like a Bellman operator and simultaneously updates the state measure by one application of the transition kernel under the unique minimizer $f(x,Q,\\mu)$ of a strongly convex function $F(x,Q_{\\min},\\mu,a)$. The proof's engine is the strong convexity of $F$, which yields a Lipschitz bound on the minimizer in $(Q,\\mu)$, together with Kantorovich-Rubinstein duality to bound the Wasserstein distance between the two distribution components. These bounds combine into the explicit contraction constants $k$ and $\\kappa$, and Banach's fixed point theorem supplies convergence.","core_discovery":"For a discrete-time mean-field game with Polish state space, compact convex action space, and costs and transitions satisfying Lipschitz and strong-convexity assumptions, define the mean-field equilibrium operator $H(Q,\\mu)=(H_1(Q,\\mu),H_2(Q,\\mu))$, where $H_1$ is a Bellman-style update on Q-functions and $H_2$ pushes $\\mu$ forward one step under the greedy policy minimizing $H_1$. The paper proves that $H$ is a contraction with explicit modulus $k$, and that the analogous operator $L$ for average cost is a contraction with modulus $\\kappa$. By Banach's fixed point theorem the iteration $(Q_{n+1},\\mu_{n+1})=H(Q_n,\\mu_n)$ converges to a unique fixed point $(Q^*,\\mu^*)$; Theorem 2 and Theorem 4 then construct a mean-field equilibrium by setting $\\pi^*(a|x)=\\delta_{f^*(x)}(a)$ with $f^*(x)$ minimizing $Q^*(x,\\cdot)$, and verify that $\\pi^*$ is optimal for $\\mu^*$ while $\\mu^*$ is invariant under $\\pi^*$.","pith_inferences":["An extension the paper leaves implicit: the contraction argument might be relaxed by replacing the Wasserstein-1 metric with a metric tailored to the weight function, potentially covering dynamics with heavier tails.","A cautious reading suggests that any practical implementation on a non-compact state space should explicitly restrict to measures with finite first moment, since the completeness of the fixed-point domain is not stated.","The joint contraction on Q and the distribution suggests that asynchronous or approximate updates might still converge if errors decay sufficiently fast, though the paper does not prove this.","The same fixed-point construction could be tested numerically for finite-state or finite-grid approximations to see how the contraction constant degrades as the approximation becomes finer."],"forward_implications":["Mean-field equilibria for this class of games can be computed by repeated application of a Bellman-type operator, with a guaranteed geometric convergence rate dictated by the contraction constant.","Because the iteration uses Q-functions rather than value functions, the same algorithmic structure can be adapted to model-free settings such as Q-learning for mean-field games.","The fixed point yields a deterministic stationary equilibrium policy and an invariant state measure, so the equilibrium is given in closed-loop form.","For average cost, the same construction works under minorization and drift assumptions, giving a value iteration algorithm for ergodic mean-field games.","Combined with known approximate-Nash results for finite-agent games, the algorithm makes equilibrium policies for large finite populations computable in principle."],"supporting_citations":[{"why":"Supplies the existence result for discounted-cost mean-field games with Polish state spaces that this paper turns into a constructive iteration.","marker":"[30]"},{"why":"Supplies the existence result for average-cost mean-field games on compact spaces that the average-cost half of the paper extends to a computable equilibrium.","marker":"[35]"},{"why":"Provides the Bellman optimality equation and average-cost optimality equation facts used to show a fixed point yields an optimal policy.","marker":"[19]"},{"why":"Provides the drift and minorization conditions behind the average-cost contraction and the unbounded-cost stochastic control framework used in the assumptions.","marker":"[20]"},{"why":"Gives the Wasserstein distance definition, the Kantorovich-Rubinstein duality, and the existence of optimal couplings used throughout the contraction proofs.","marker":"[33]"},{"why":"Supplies the perturbation result that controls how the unique minimizer of a strongly convex function changes with the Q-function and the measure.","marker":"[9]"},{"why":"Provides the fixed-point contraction result for the average-cost Bellman operator used to characterize the optimal value for each fixed measure.","marker":"[31]"},{"why":"The prior computational scheme for finite-state mean-field games, which this paper contrasts with its own broader abstract-state treatment.","marker":"[17]"}],"fun_headline_variants":["Contraction proof makes value iteration converge to MFG equilibria","Value iteration hits fixed point for mean-field games","Q-function value iteration solves mean-field games exactly","Algorithm converges to mean-field equilibrium, both cost criteria","Banach fixed point powers value iteration for MFG"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the state-distribution space is complete under the Wasserstein distance used in the contraction proof, which holds only for distributions with finite first moment (or a compact state space) and is never stated in the paper.","fun_headline_variants_meta":{"raw":{"variants":["Contraction proof makes value iteration converge to MFG equilibria","Value iteration hits fixed point for mean-field games","Q-function value iteration solves mean-field games exactly","Algorithm converges to mean-field equilibrium, both cost criteria","Banach fixed point powers value iteration for MFG"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000141,"raw_usage":{"total_tokens":1120,"prompt_tokens":857,"completion_tokens":263,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":473,"completion_tokens_details":{"reasoning_tokens":187}},"tokens_in":473,"tokens_out":263,"duration_ms":2955,"temperature":1.0,"reasoning_tokens":187,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:09:30.381449+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proposed iteration on a scalar mean-field game with a heavy-tailed transition kernel, such as t-distributed noise, so that some iterates have infinite first moment; if the iterates do not converge in Wasserstein distance, or if two different initial pairs converge to different limits, then the claimed contraction and completeness fail.","supporting_citations":[{"cited_title":"Saldi, T","cited_arxiv_id":null,"evidence_quote":"Supplies the existence result for discounted-cost mean-field games with Polish state spaces that this paper turns into a constructive iteration."},{"cited_title":"Discrete-time ergodic mean-field games with avera ge reward on compact spaces","cited_arxiv_id":null,"evidence_quote":"Supplies the existence result for average-cost mean-field games on compact spaces that the average-cost half of the paper extends to a computable equilibrium."},{"cited_title":"Hern´ andez-Lerma and J.B","cited_arxiv_id":null,"evidence_quote":"Provides the Bellman optimality equation and average-cost optimality equation facts used to show a fixed point yields an optimal policy."},{"cited_title":"Hern´ andez-Lerma and J.B","cited_arxiv_id":null,"evidence_quote":"Provides the drift and minorization conditions behind the average-cost contraction and the unbounded-cost stochastic control framework used in the assumptions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Wasserstein distance definition, the Kantorovich-Rubinstein duality, and the existence of optimal couplings used throughout the contraction proofs."},{"cited_title":"Bonnans and A","cited_arxiv_id":null,"evidence_quote":"Supplies the perturbation result that controls how the unique minimizer of a strongly convex function changes with the Q-function and the measure."},{"cited_title":"Saldi, T","cited_arxiv_id":null,"evidence_quote":"Provides the fixed-point contraction result for the average-cost Bellman operator used to characterize the optimal value for each fixed measure."},{"cited_title":"Hadikhanloo and F.J.Silva","cited_arxiv_id":null,"evidence_quote":"The prior computational scheme for finite-state mean-field games, which this paper contrasts with its own broader abstract-state treatment."}],"review_version":1}