{"id":"80f70c8e-751a-40b7-a8fe-852b7ec08fe4","arxiv_id":"2501.14916","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Under DMMF, fixed threshold strategies may admit no pure Nash equilibrium, while a win-rate matching dynamic threshold yields an approximate equilibrium in which symmetric agents achieve at least a 1-1/e fraction of their ideal utility.","lead":"This paper studies how selfish agents behave when a shared resource is repeatedly allocated to the agent that has received it least so far, a rule called Dynamic Max-Min Fairness (DMMF). It shows that fixed threshold request rules can have no Nash equilibrium, and then designs a data-driven request rule that makes following it an approximate equilibrium while improving welfare.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exact knowledge of p* in Algorithm 2 is load-bearing: any misspecification of the distribution-dependent target makes the claimed equilibrium collapse to a lower-welfare state, while a fixed-threshold deviation to the true p* becomes strictly profitable.","rationale":"I read Theorem 4.5 as a conditional statement: if the agents are handed the correct p*, the proof strategy of combining Lemma 4.3 and Lemma 4.4 is plausible and the welfare conclusions of Theorem 4.6 follow. The weakest point is the gap between that conditional statement and the paper's framing as a simple data-driven, distribution-agnostic equilibrium result. The p* issue is more fundamental than the restriction to fixed-threshold deviations: even for the narrow class of deviations the theorem considers, a wrong p* (from estimation error, misspecification, or lack of distribution knowledge) moves the all-follow equilibrium to a suboptimal symmetric profile and makes a deviation to the true p* strictly profitable. This is exactly the reader's weakest assumption, and it justifies a conditional acceptance pending a concrete estimation or distribution-free implementation of p*. I do not see an internal inconsistency in the main proofs, and the state-space collapse characterization appears to be a genuine technical contribution, which is why the verdict should remain conditional rather than being rejected outright.","tokens_in":52974,"tokens_out":5969,"duration_ms":77402,"concrete_test":"Simulate D=U[0,1], n=5, T=10^5 using Algorithm 2 with target p*+delta for delta in {0.02, 0.05, 0.1} and compare against the target p* case. Compute average utilities for (i) all agents using Win-Rate Matching and (ii) one agent deviating to fixed threshold p*. Use both direct simulation and the closed-form utility expression from Theorem 5.8. If the deviator's utility exceeds the all-follow utility by more than o(1) for any delta>0, Theorem 4.5 requires exact p* and the missing estimation procedure is load-bearing. An analytic version: derive the fixed-point equations M -> p*+delta under all-follow and M -> p* under one deviator, then show U_i(p*) - U_i(p*+delta) > 0 for arbitrarily small delta.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 2 takes as input p* = argmax_p U_i(p,...,p), which depends on the common value distribution D. The paper bills Win-Rate Matching as a 'data-driven' policy and contrasts it with distribution-aware mechanisms, but no estimation or learning procedure for p* is given; if agents do not know D, the drift term eta(t)*p* cannot be evaluated and Theorem 4.5 does not apply. The dependence is not merely cosmetic. Suppose the target is p*+delta for a misspecified or estimated p*. When all agents use Win-Rate Matching, the same argument as Lemma 4.3 makes M_{eta,zeta}[t] converge to the target p*+delta, so the symmetric outcome is U_i(p*+delta,...,p*+delta). If one agent instead fixes threshold p*, Lemma 4.4 makes the others' request rate converge to p*, so the deviator's utility tends to U_i(p*,...,p*). Since p* is the unique maximizer of the symmetric welfare U_i(p,...,p), the deviator gains a constant gap whenever delta is small but nonzero. Thus exact knowledge of p* is a necessary condition for the equilibrium conclusion, and the paper neither supplies p* as a primitive of a distribution-agnostic model nor provides an estimator with a convergence guarantee. The theorem is internally consistent if p* is taken as given, but the claimed 'data-driven' character of the mechanism is unsubstantiated without such a procedure.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies repeated allocation of an indivisible resource under the Dynamic Max-Min Fair (DMMF) mechanism, where in each round the resource is given to the requesting agent with the fewest prior allocations. The authors first provide a characterization of the long-run behavior of DMMF under fixed threshold strategies: Theorem 3.3 gives necessary and sufficient conditions for global state-space collapse, and Theorem 5.8 gives a full decomposition into stable subgroups with distinct win rates. They then prove that the natural class of fixed threshold strategies admits no pure Nash equilibrium even for two symmetric agents with a two-point value distribution (Theorem 4.1). As a remedy, they propose the Win-Rate Matching strategy (Algorithm 2), in which each agent chooses a request probability that matches the historical aggregate request rate, with a vanishing drift toward p*, the request probability maximizing symmetric welfare. Lemma 4.3 shows that if all agents follow this strategy, the request rate converges to p*; Lemma 4.4 shows that if one agent deviates to a fixed threshold p̂, the remaining agents' request rate converges to p̂. Theorem 4.5 concludes that no agent can improve her utility by deviating to a fixed threshold strategy, up to o(t). Theorem 4.6 gives welfare guarantees of 1-1/e for arbitrary identical distributions and 1-O(log n/n) for uniform distributions, improving on the prior robust 1/2 and 1-O(1/sqrt n) guarantees.","tokens_in":53322,"tokens_out":5492,"duration_ms":52917,"significance":"The paper makes a substantial technical contribution to the analysis of a simple dynamic allocation mechanism. The subgroup state-space collapse characterization (Theorems 3.3 and 5.8) is a complete and nontrivial description of the long-run win rates under arbitrary threshold profiles, and the drift-based stochastic approximation arguments used to establish Lemmas 4.3 and 4.4 are likely to be of independent interest. The counterexample in Theorem 4.1 is concrete and worked out in Appendix C with explicit parameters. The welfare guarantees in Theorem 4.6 improve on the existing robustness results, and the proof structure is internally consistent once p* is taken as given. However, the paper overstates the scope of its equilibrium result in two respects that matter for its main claim: Algorithm 2 requires p* as an input, so the policy is not distribution-free despite being billed as data-driven; and Theorem 4.5 only rules out deviations to fixed threshold strategies, not to history-dependent dynamic strategies. These issues are load-bearing for the paper's advertised conclusions and should be addressed before the results can be accepted at face value.","major_comments":[{"comment":"Algorithm 2 takes p* = argmax_p U_i(p,...,p) as input, and Lemma 4.3 proves convergence to p* only when the drift term uses the true welfare-maximizing rate. Since p* depends on the common value distribution D, the Win-Rate Matching strategy is not distribution-free. The paper describes the policy as 'data-driven' in the Abstract and Section 1.1, and motivates it as a step for distribution-agnostic mechanisms, but no estimation or learning procedure for p* is provided. A misspecified target p*+delta would make the symmetric request rate converge to p*+delta by the same argument as Lemma 4.3, while a fixed-threshold deviation to p* would give the deviator utility U_i(p*,...,p*) against followers whose rate converges to p*, yielding a constant gain. Thus exact knowledge of p* is necessary for Theorem 4.5, and the current manuscript does not supply it within the claimed data-driven model. The authors should either provide a convergent estimator for p* from observable histories, or explicitly restate the results as requiring distributional knowledge and remove or qualify the 'data-driven' claims.","section":"Section 4.2, Algorithm 2, Lemma 4.3"},{"comment":"The equilibrium statement is restricted to unilateral deviations to fixed threshold strategies: Theorem 4.5 only compares U_i(WRM,...,WRM) with U_i(WRM,...,Thr_p,...,WRM). The paper nonetheless refers to this as an approximate Nash equilibrium in the abstract and in Section 1.1. Since Proposition 2.1 shows that arbitrary strategies are dominated by history-dependent dynamic threshold strategies, and Theorem 4.5 does not rule out profitable dynamic deviations, the claim as advertised is stronger than what is proved. The authors should either extend the result to a broader class of deviations or consistently describe the theorem as an equilibrium against fixed-threshold deviations.","section":"Theorem 4.5 and Section 1.1"}],"minor_comments":[{"comment":"The last sentence of the proof says '|M_{eta,zeta}[t] - p^*| = (1+o(1))|Z[t]| -> 0', but Z[t] is defined with p̂; this should be |M_{eta,zeta}[t] - p̂|.","section":"Lemma 4.4 proof, Appendix D"},{"comment":"The caption states that the experiment uses zeta(t)=1 and an eta(t) that decays linearly to 0.05, which differs from the schedules zeta(t)=1-t^{-1/4} and eta(t)=1/log(t)^{1/2-epsilon} used in Theorem 4.5. This is acknowledged, but the experimental section would be clearer if it explained whether the displayed behavior is expected to persist under the theorem's parameter schedules.","section":"Figure 2 caption"},{"comment":"The error bound is written as 'o(t) <= O(sqrt(t log t)) if C_i satisfies the stability criterion strictly'; this mixes o(t) and O(sqrt(t log t)) notation. The intended meaning is that the remainder is O(sqrt(t log t)) under the strict condition, and the presentation should be adjusted.","section":"Theorem 5.8"},{"comment":"There is a typo: 'wide variery of applications' should be 'wide variety of applications'.","section":"Section 1.3"}],"recommendation":"major_revision","confidential_remarks":"The technical core of the paper is solid and the characterization results are likely publishable. The main obstacle is the gap between the advertised 'data-driven, approximate-Nash' narrative and what is actually proved: p* is an input that depends on the value distribution, and only fixed-threshold deviations are excluded. I would encourage the editor to request a revision that either supplies a learning procedure for p* or honestly reframes the contribution as a mechanism-with-advice result with a known distribution. The restricted deviation class also needs to be transparent in the abstract and introduction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe headline result is the Win-Rate Matching policy: a simple dynamic threshold rule that, if all agents use it, is an approximate Nash equilibrium against fixed-threshold deviations, and achieves a 1-1/e fraction of ideal utility, beating the robust 1/2 guarantee. The supporting characterization of DMMF under threshold strategies — state-space collapse into stable subgroups with explicit win rates — is the real contribution and looks technically solid. The no-pure-equilibrium result for fixed thresholds is a clean negative that motivates the construction.\n\nI think the reader's conditional verdict is right, but I would push back on calling this a \"competitive equilibrium\" in any strong sense. The equilibrium is only against fixed-threshold deviations; arbitrary dynamic deviations are not covered. Proposition 2.1 does not close that gap because it converts an arbitrary strategy into a dynamic threshold strategy, not a fixed one, and the WRM convergence lemmas only handle fixed deviations. The paper is honest about this scope, but the title overpromises a bit.\n\nThe stress-test concern about p* is real and more serious than the paper acknowledges. Algorithm 2 takes p* as an input, and p* depends on the common distribution D. The abstract and intro say \"data-driven\" and contrast with distribution-aware mechanisms; that is overstated. If agents know D, they can compute p* themselves, but then \"data-driven\" just means the principal does not need D. If they do not know D, there is no estimation procedure and Theorem 4.5 does not apply. The misspecification argument in the stress-test note is correct: if the target is p*+delta, a deviator to p* gains a constant gap. So exact knowledge of p* is load-bearing for the approximate equilibrium. I would treat this as a moderate weakness: the theorem is internally correct, but the framing needs to be walked back and an estimator or sensitivity analysis added.\n\nMinor: the experiment in Fig. 2 does not use the proven parameter schedules (zeta=1 and eta decaying to 0.05 versus the theorem's zeta=1-t^{-1/4} and eta=log(t)^{-1/2+eps}), so it is illustrative, not confirmatory.\n\nWho should read it: mechanism design and algorithmic game theory folks working on no-money repeated allocation. The state-space collapse theorem will be cited. I would send it to peer review; conditional accept is the right call. The main revision asks are to sharpen the \"data-driven\" claim and to either extend the equilibrium analysis to richer deviations or scope it clearly.\n\nBest,\n[Your name]","headline":"A solid mechanism-design paper: the subgroup state-space collapse theorem is the real contribution, while the 'data-driven' claim needs to be walked back because Algorithm 2 requires exact knowledge of p*.","tokens_in":53791,"tokens_out":2739,"would_cite":true,"duration_ms":37086,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A10","91B32","60J20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Win-Rate Matching gives dynamic max-min fairness an approximate equilibrium and near-optimal welfare.","keywords":["dynamic max-min fairness","public goods allocation","Nash equilibrium","threshold strategies","Win-Rate Matching","state-space collapse","welfare guarantee","competitive equilibrium"],"falsifier":"Simulate DMMF with $n$ agents drawing values from a chosen distribution, run all agents on Win-Rate Matching with the paper's $\\eta(t)$ and $\\zeta(t)$, and let a single agent deviate to a fixed threshold $p$ different from $p^*$. Theorem 4.5 predicts the deviator's utility exceeds her conforming utility by at most $o(T)$; a simulation showing a positive linear gain over a long horizon would refute it.","tokens_in":52820,"feed_emoji":"⚖️","tokens_out":5434,"duration_ms":45095,"temperature":0.7,"pith_summary":"The paper studies repeated allocation of a single public resource under Dynamic Max-Min Fairness (DMMF), where in each round among requesting agents the one with fewest past wins receives the item. It establishes that the natural class of fixed threshold strategies has no pure Nash equilibrium, even for two symmetric agents with values on two points. It then proposes a data-driven policy, Win-Rate Matching, in which agents request with a probability that tracks the historical allocation rate plus a vanishing drift toward the welfare-optimal symmetric request probability $p^*$. The main theorem states that if all agents follow this policy, no agent can gain more than $o(t)$ over $t$ rounds by deviating to any fixed threshold strategy, so the profile is an approximate Nash equilibrium. The same policy improves the per-agent utility guarantee from the robust half of ideal utility to at least $1-1/e$ for arbitrary identical distributions, and to $1-O(\\log n/n)$ for uniform distributions.","feed_headline":"A data-driven policy restores equilibrium to fair allocation","feed_subtitle":"Under dynamic max-min fairness, Win-Rate Matching yields 1-1/e of ideal utility for all agents and near-optimal welfare for uniform values.","key_machinery":"The central object is the DMMF allocation process $X_i[t]=W_i[t]/\\alpha_i - K[t]$, together with the subgroup stability condition: every subset $R$ of a stable group $S$ must satisfy $\\left(1-\\prod_{k\\in R}(1-p_k)\\right)/\\sum_{k\\in R}\\alpha_k \\ge \\left(1-\\prod_{k\\in S}(1-p_k)\\right)/\\sum_{k\\in S}\\alpha_k$. This condition is exactly what links state-space collapse of normalized allocations to the request probabilities and fair shares: when it holds for the full set, every agent wins her fair share of requested rounds up to sub-linear error, and when it fails, agents split into ordered subgroups with distinct win rates. The Win-Rate Matching algorithm is the mechanism that uses this characterization: its request probability $M_{\\eta,\\zeta}[t]$ tracks the observed aggregate win rate through the inverse $\\Phi^{-1}$ of the probability that at least one agent requests, while $\\eta(t)$ injects a vanishing drift toward $p^*$ and $\\zeta(t)$ keeps the process away from the absorbing rate $1$. The convergence lemmas for $M_{\\eta,\\zeta}[t]$ are what turn the static characterization into an equilibrium statement.","core_discovery":"On the paper's own terms, the central finding is that strategic behavior in DMMF is governed by a complete characterization of long-run win rates, and that characterization makes possible a simple equilibrium-inducing policy. For any fixed threshold profile, the agents split into stable subgroups; within each subgroup normalized win rates are mean-reverting about a common line, so each agent's long-run utility is an explicit function of the request probabilities and fair shares. Using this, the paper shows that no pure Nash equilibrium exists among fixed thresholds. The remedy is Win-Rate Matching: each round agents set their request probability to $(1-\\eta(t))\\Phi^{-1}(\\zeta(t) K[t-1]/(t-1)) + \\eta(t) p^*$, where $\\Phi(p)=1-(1-p)^n$. With $\\eta(t)=1/\\log(t)^{1/2-\\epsilon}$ and $\\zeta(t)=1-t^{-1/4}$, when everyone follows the policy the request rates converge almost surely to $p^*$; when one agent deviates to a fixed threshold $\\hat{p}$, the rates converge almost surely to $\\hat{p}$, which makes the deviation unprofitable up to $o(t)$. Consequently, the equilibrium outcome is welfare-superior to the robust threshold play, giving each agent at least $1-1/e$ of her ideal utility in the worst case and $1-O(\\log n/n)$ for uniform values.","pith_inferences":["The algorithm's dependence on $p^*$ means the policy is only partially distribution-agnostic; a natural extension is to replace $p^*$ with an estimator learned from realized values and to check whether the approximate-equilibrium and welfare guarantees survive with high probability.","The mechanism-with-advice reading suggests a principal could recommend the Win-Rate Matching threshold while agents keep the freedom to deviate; if the theorem is right, rational agents have little incentive to disobey the recommendation, so the policy can be viewed as a cheap way to implement the welfare-optimal symmetric outcome.","The subgroup state-space collapse decomposition is a general tool for loss-network-like allocation processes, and it may transfer to pseudo-market mechanisms or other dynamic priority rules with different service disciplines."],"forward_implications":["Fixed threshold strategies, despite their robustness guarantees, cannot serve as a model of equilibrium play under DMMF; the paper proves this already for two symmetric agents with a two-point value distribution.","Following the Win-Rate Matching policy is an approximate Nash equilibrium: unilateral deviations to any fixed threshold gain at most $o(t)$.","The equilibrium outcome guarantees every agent at least $1-1/e$ of her ideal utility for arbitrary identical value distributions, improving on the robust $1/2$ guarantee.","For uniform value distributions the guarantee becomes $1-O(\\log n/n)$, improving on the robust $1-O(1/\\sqrt{n})$ bound.","The characterization of long-run win rates extends to asymmetric DMMF with exogenous fair shares, so the analytical core is not limited to symmetric agents."],"supporting_citations":[{"why":"Supplies the DMMF robust threshold baseline and the ideal-utility guarantees that Win-Rate Matching improves upon.","marker":"[13]"},{"why":"Introduces the ideal utility benchmark and the 1/2 robust guarantee for repeated Fisher markets that motivates threshold strategies.","marker":"[19]"},{"why":"Extends robust guarantees to reusable resources, establishing the prior robustness framework under DMMF-like mechanisms.","marker":"[2]"},{"why":"Provides the negative-drift moment bound used in the sufficient side of the state-space collapse characterization.","marker":"[29]"},{"why":"Gives existence of mixed Nash equilibria in the threshold game, clarifying why the pure-Nash question is the relevant one.","marker":"[17]"}],"fun_headline_variants":["Win-Rate Matching: a data-driven equilibrium for fair allocation","Data-driven policy finds equilibrium where fixed thresholds fail","No equilibrium for fixed thresholds, but a data-driven policy fixes it","A data-driven policy restores equilibrium and improves welfare in fair allocation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every agent knows $p^*$, the request probability maximizing symmetric welfare, which is a function of the common value distribution and is not estimated or learned by the algorithm.","fun_headline_variants_meta":{"raw":{"variants":["Win-Rate Matching: a data-driven equilibrium for fair allocation","Data-driven policy finds equilibrium where fixed thresholds fail","No equilibrium for fixed thresholds, but a data-driven policy fixes it","A data-driven policy restores equilibrium and improves welfare in fair allocation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000962,"raw_usage":{"total_tokens":4200,"prompt_tokens":1152,"completion_tokens":3048,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":768,"completion_tokens_details":{"reasoning_tokens":2978}},"tokens_in":768,"tokens_out":3048,"duration_ms":35224,"temperature":1.0,"reasoning_tokens":2978,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T14:47:08.848840+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate DMMF with $n$ agents drawing values from a chosen distribution, run all agents on Win-Rate Matching with the paper's $\\eta(t)$ and $\\zeta(t)$, and let a single agent deviate to a fixed threshold $p$ different from $p^*$. Theorem 4.5 predicts the deviator's utility exceeds her conforming utility by at most $o(T)$; a simulation showing a positive linear gain over a long horizon would refute it.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the ideal utility benchmark and the 1/2 robust guarantee for repeated Fisher markets that motivates threshold strategies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Extends robust guarantees to reusable resources, establishing the prior robustness framework under DMMF-like mechanisms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the negative-drift moment bound used in the sufficient side of the state-space collapse characterization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives existence of mixed Nash equilibria in the threshold game, clarifying why the pure-Nash question is the relevant one."}],"review_version":1}