{"id":"c9b84c39-c463-4ec8-94fd-eb8be983e4b7","arxiv_id":"2412.05636","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"FedPCS uses a Stackelberg game and mean-field estimation to set client sampling probabilities and rewards from privacy budgets, claiming a bounded price of anarchy and better federated learning accuracy.","lead":"This paper proposes FedPCS, a game-theoretic framework that lets a federated learning server sample clients according to their differential-privacy budgets while paying them rewards. It models the server-client interaction as a two-stage Stackelberg game and claims improved model accuracy with a bounded price of anarchy.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's mean-field fixed-point convergence is not established: Appendix E's contraction proof compares two different clients from the same iterate, not two iterates of the map, so the SNE and PoA claims rely on a strategy profile that may never be reached.","rationale":"I agree with the reader's weakest-assumption identification. The fixed-point gap is more load-bearing than the (also real) PoA algebra problems because it invalidates the object whose efficiency is later measured. Without a convergence guarantee for Algorithm 1, phi(t) is not known to equal N^{-1} sum_i rho_i^t, so Theorem 1's 'given phi(t)' optimum is not the client's best response in the actual game, and the SNE in Theorem 2 may simply be a strategy of an auxiliary mean-field game. The empirical Fig. 3 cannot repair a universal proof claim. I would therefore keep the REJECT verdict unchanged.","tokens_in":37691,"tokens_out":13707,"duration_ms":128229,"concrete_test":"Direct analytical counterexample to Eq. (67): take N=3, rho_1=rho_2=0.01, rho_3=12, phi=4.0067, and any admissible alpha_1 != alpha_2 (e.g., from Eq. (21) with phi_1=0.1, phi_2=0.9). Then Eq. (20) gives rho'_1 - rho'_2 = (alpha_2 - alpha_1)(phi - 0.01) != 0, so Gamma(Theta_1(rho_1), Theta_2(rho_2)) > 0 while ||rho_1 - rho_2|| = 0, contradicting Eq. (67). For the actual iteration, recompute the sup-norm Lipschitz constant of phi_{m+1} = Psi(phi_m) over [0.01,12]^N for N=2, T=3 using Eq. (21); if any ratio exceeds 1, the Banach argument cannot be repaired.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3 is the linchpin of the paper: Theorem 1 gives the client's optimal correction factor only for a known mean-field term phi(t), Lemma 2 and Theorem 2 build the optimal reward and SNE on the resulting alpha*, and Theorem 6 evaluates PoA at that profile. If Algorithm 1 does not converge to the fixed point of phi(t), the announced 'optimal strategy profile' is not actually obtained. Appendix E's proof of Theorem 3 is invalid. Banach's theorem requires a bound on Gamma(Theta(rho), Theta(rho')) for two inputs/iterates of the same map, but Eq. (67) bounds Gamma(Theta_i(rho_i), Theta_j(rho_j)), i.e., the next budgets of two different clients computed from the same current vector. The step ||alpha_i rho_i - alpha_j rho_j|| <= sqrt(nu)||rho_i - rho_j|| is asserted with sqrt(nu) never derived from Eq. (21); it can exceed 1, and the preceding term dropped from the norm can increase it. The 'contraction coefficient' is not a Lipschitz constant of the iteration. Brouwer only gives existence of some fixed point; it says nothing about the convergence of the specific iteration in Algorithm 1. Hence the convergence claim in Theorem 3 is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes FedPCS, a two-stage Stackelberg game for privacy-aware client sampling in federated learning under ρ-zCDP. The server chooses rewards and sampling probabilities to minimize a cost combining accuracy loss and reward payments, while each client chooses a correction factor that adapts its privacy budget. A mean-field estimator is introduced to approximate the average privacy budget, and the paper claims to establish existence and convergence of its fixed point, a Stackelberg Nash equilibrium, convergence bounds for the FL model, a price-of-anarchy comparison showing bounded efficiency loss for FedPCS versus arbitrarily large loss for random sampling, and an extension to adaptive sampling ratios under dynamic privacy constraints. The claims are supported by derivations in Appendices A–H and by experiments on six datasets.","tokens_in":37993,"tokens_out":8939,"duration_ms":84662,"significance":"If the theoretical claims were correct, the paper would make a useful contribution to federated learning by jointly modeling incentive design and privacy-aware client sampling, and the mean-field approach to decentralized strategy design is a sensible idea. The experimental section is broad, covering six datasets, IID/Non-IID partitions, multiple sampling rates, and several strong baselines, with means and standard deviations reported. However, several load-bearing theoretical steps are not established as written: the central convergence result for the mean-field fixed point is proven by an invalid contraction argument, the accuracy-loss bound in Proposition 2 does not depend on the sampling probabilities it is claimed to analyze, and the PoA upper bound in Theorem 6 relies on an unjustified inequality and an unmodeled worst-case assumption. These gaps concern the core claims of the paper, so the contribution is not currently realized.","major_comments":[{"comment":"The claimed accuracy-loss bound for privacy-aware client sampling contains no sampling probabilities x_i^t and no sampled-set size K; Appendix B derives it from the full-participation perturbed global gradient (Eq. (B.47)). The server's Stage I cost in Eq. (13) sums only over K sampled clients, while the accuracy-loss term inherited from Proposition 2 is a sum over all N clients. The optimization objective in Eq. (13) is therefore not the quantity bounded in Proposition 2, and the derivation of the optimal reward in Lemma 2 and Theorem 2 is not grounded in the stated convergence result.","section":"§III-D, Prop. 2, Eq. (12)"},{"comment":"The proof that the mean-field fixed point is attainable by Algorithm 1 is invalid. Eq. (67) bounds Γ(Θ_i^t(ρ_i^t), Θ_j^t(ρ_j^t)), namely the distance between the next privacy budgets of two different clients computed from the same current vector, whereas Banach's contraction theorem requires a bound on the distance between two iterates of the same map. The coefficient √ν is asserted rather than derived, can exceed 1, and the term (1/N)(α_i^t Σ_k ρ_k^t − α_j^t Σ_k ρ_k^t) is dropped from the norm without justification. Brouwer's theorem gives existence of some fixed point but says nothing about convergence of the specific iteration in Algorithm 1. Since Theorem 1, Lemma 2, Theorem 2, and Theorem 6 all evaluate the strategy profile at this fixed point, the convergence gap undermines the equilibrium and PoA claims.","section":"§IV-B, Theorem 3, Appendix E, Eq. (67)"},{"comment":"The upper bound on PoA(pri) is not established. The inequality labeled (a) relies on N Σ_t R_t ≤ (T+1) Σ_i φ_i, which is not a consequence of any stated assumption and can fail for large rewards. Moreover, as ρ_H → ∞, the denominator N ρ_H Σ_t R_t − (T+1) ρ_H² Σ_i φ_i becomes negative for fixed rewards and φ_i, so the claimed limit PoA(pri) ≤ R_max/(2N) Σ_i 1/φ_i does not follow. The proof also asserts without derivation that the worst-case Stackelberg Nash equilibrium has ρ_i^t → ρ_H for all clients; this must be computed from the clients' best responses in Eq. (14), not assumed.","section":"§VI-C, Theorem 6, Eq. (37)"},{"comment":"The random-sampling PoA lower bound is derived under an unmodeled behavioral assumption: it simply states that egocentric clients set ρ_i^t = ρ_L at the Nash equilibrium, with no derivation from the utility in Eq. (14). In addition, the social welfare function in Eq. (30) omits the sampling-probability term (1−(1−x_i^t)^K) and the correction-factor cost (1−φ_i)(α_i^t)² that appear in the clients' actual utilities. The comparison between random sampling and privacy-aware sampling is therefore not carried out within the game defined in Sections III and IV.","section":"§VI-B, Prop. 4"},{"comment":"Equation (21) is presented as the closed-form optimal correction factor, but its right-hand side contains future correction factors α_r^i for r ≥ t+1 and S(t+1) depends on α_{t+1}; at best this is a backward recursion rather than a closed-form expression. In the proof of Theorem 2, the cost function U_t is said to be 'strictly concave' while the displayed second derivative in Eq. (61) is positive, which proves strict convexity. The existence of the optimal reward may be salvageable from the stated limits, but the proof as written is internally inconsistent, and no uniqueness or global-optimality argument is supplied for the response R_t^*.","section":"§IV-A, Theorem 1, Eq. (21); Theorem 2"}],"minor_comments":[{"comment":"The global update with sampling probabilities uses the estimator θ_i/(K x_i^t) over the sampled set K_t, but the paper does not state the expectation over the K-times-without-replacement sampling or verify unbiasedness of this estimator; this should be made explicit.","section":"§III-C, Eq. (4)"},{"comment":"The stopping criterion computes ϵ = ϕ_est^m(t) − ϕ_est^{m−1}(t) for each t, but the algorithm does not specify how the vector-valued difference is reduced to a scalar or how a single m is used across all t; presumably a norm over t is intended.","section":"§IV-B, Algorithm 1"},{"comment":"The proof differentiates the Lagrangian with respect to K_t even though K_t is an integer-valued subset size; a discrete optimization argument or a continuous relaxation with integrality justification is needed.","section":"§VII, Theorem 7"},{"comment":"The displayed second derivative ∂²H(t)/∂(α_i^t)² contains an extra factor α_i^t; the sign conclusion is unchanged because (1−φ_i) > 0 and the sampling probability is positive, but the displayed formula is incorrect.","section":"Appendix C, Eq. (50)"},{"comment":"The bounds contain the factor [(N−1)ρ_H + ρ_L]/Kρ_L but no step-size condition is stated to ensure that the contraction factor 1 − ψη[(N−1)ρ_H + ρ_L]/Kρ_L remains positive; such a condition should be included.","section":"§V, Theorem 4, Eqs. (25)-(26)"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the FedPCS combination—Stackelberg reward design plus privacy-budget-based sampling plus mean-field estimation—is a genuinely new mashup, and the experimental campaign is broad. But the theoretical spine is not load-bearing. I agree with the reader's reject verdict. Proposition 2's accuracy-loss bound has no sampling probabilities in it, so it doesn't do the work the paper claims; the bound is just the full-participation noisy-SGD bound. Theorem 2's proof says the server cost is strictly concave with a positive second derivative, which is a minimum, not a maximum, and the adjacent limits point to a root but not to the claimed optimum. Theorem 3 is the linchpin: Algorithm 1's fixed-point iteration is what produces the strategy profile the rest of the paper evaluates, and Appendix E's contraction argument compares two different clients at the same iterate rather than two iterates of the same map. The coefficient sqrt(nu) is asserted, not derived, and can apparently exceed 1. That is not a Banach contraction; Brouwer only gives existence of a fixed point, not convergence of this particular iteration. Theorem 6's PoA bound is built on a social welfare function that drops the sampling probabilities and correction-factor costs that are present in the clients' actual utilities, so the comparison is not against the game that was defined.\n\nWhat the paper does well: the problem is real, the framework is clearly laid out, the experiments are extensive (six datasets, IID and Non-IID, three sampling rates), and the authors don't engage in citation-padding or circularity. The mean-field fixed point is a standard consistency condition. The empirical numbers are consistent with the intuition that sampling clients with larger privacy budgets helps.\n\nWhere I'd push back on the reader: the gaps are serious, but I wouldn't call the paper a pure rehash. The adaptive sampling ratio section and the PoA comparison are interesting even if the bounds are wrong; with better proofs or a reframed 'heuristic with empirical support' claim, the core idea is salvageable.\n\nFor peer review: this deserves a serious referee, not a desk reject, because the flaws are technical and fixable in principle and the problem is well-motivated. A referee should demand either corrected proofs for the three named theorems or a substantial reframing of what is proven vs. conjectured. No code is provided, which the authors should remedy. I would not cite it in its current form.","headline":"A plausible mechanism with a heavy new-claim load, but the proofs as written don't support the equilibrium, convergence, or PoA results.","tokens_in":38483,"tokens_out":2055,"would_cite":false,"duration_ms":20138,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A65","91A80","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A two-stage Stackelberg game over privacy budgets yields a bounded price of anarchy for federated client sampling.","keywords":["federated learning","client sampling","differential privacy","Stackelberg game","price of anarchy","mean-field estimator","incentive mechanism","zero-concentrated differential privacy"],"falsifier":"Run Algorithm 1 on a small instance, for example $N=2$, $T=3$, $\\rho_L=1$, $\\rho_H=12$, $\\alpha_L=0.1$, $\\alpha_H=0.9$, from several initial choices of $\\phi_0(t)$, and check whether the iterates converge to a common fixed point; a single divergent trajectory or an initial-condition-dependent limit would refute Theorem 3's contraction claim and undermine the guarantee that the Stackelberg equilibrium strategies are actually computed.","tokens_in":37447,"feed_emoji":"🔒","tokens_out":5532,"duration_ms":50744,"temperature":0.7,"pith_summary":"The paper proposes a federated learning scheme, FedPCS, in which a central server samples clients with probability proportional to their privacy budget and pays them rewards, while each client chooses a correction factor that adjusts its own privacy budget over time. The authors model this interaction as a two-stage Stackelberg game and claim that the resulting optimal strategies form a Stackelberg Nash equilibrium. They further claim that the mean-field estimator used to approximate the average privacy budget has a fixed point reachable by iteration, and that the privacy-aware sampling strategy keeps the price of anarchy bounded by a constant, unlike uniform random sampling whose price of anarchy can grow arbitrarily large. If these claims hold, federated learning servers could jointly set sampling probabilities and rewards to keep efficiency loss under control while accommodating selfish, privacy-sensitive clients.","feed_headline":"Reward-based sampling bounds federated learning's efficiency loss","feed_subtitle":"A Stackelberg game sets sampling odds and rewards so selfish clients raise privacy budgets instead of degrading model quality.","key_machinery":"The central objects are the sampling probability $x_i^t = \\rho_i^t/(N\\phi(t))$, the mean-field estimator $\\phi(t) = \\frac{1}{N}\\sum_{i=1}^N \\rho_i^t$, the client's correction factor $\\alpha_i^t$ used in the recurrence $\\rho_i^{t+1} = (1-\\alpha_i^t)\\phi(t) + \\alpha_i^t\\rho_i^t$, and the server's reward $R_t$. The two-stage Stackelberg game connects them: clients choose $\\alpha_i^t$ to maximize sampling probability and reward minus quadratic privacy and adjustment costs, while the server chooses $R_t$ to balance model accuracy loss against reward payout. The price-of-anarchy comparison between random sampling and the privacy-aware sampling strategy is the metric that carries the efficiency claim, and the mean-field fixed point is what makes the decentralized strategy profile computable in closed form.","core_discovery":"The paper's central claim is that in federated learning with $\\rho$-zCDP noise, the interaction between a cost-minimizing server and utility-maximicking clients can be modeled as a two-stage Stackelberg game, and the optimal strategies—time-dependent rewards $R_t^*$ and per-client correction factors $\\alpha_i^{t*}$—form a Stackelberg Nash equilibrium. The equilibrium is computed through a mean-field estimator $\\phi(t)$ that approximates the average privacy budget, and the paper proves existence and convergence of its fixed point via a contraction argument. The paper further claims that the price of anarchy under uniform random sampling becomes arbitrarily large as the lower privacy budget $\\rho_L$ approaches zero, whereas the privacy-aware sampling strategy achieves $\\mathrm{PoA} \\le \\frac{R_{\\max}}{2N}\\sum_{i=1}^N \\frac{1}{\\varphi_i}$ in the limit $\\rho_H \\to +\\infty$. Experiments on six image datasets report that FedPCS outperforms the considered baselines in accuracy, social welfare, and server cost under both IID and Non-IID settings.","pith_inferences":["If the mean-field fixed point is not actually reached, the equilibrium and price-of-anarchy claims do not apply to the deployed system; the paper's contraction proof compares outputs for two different clients rather than successive iterates of the same mapping, so convergence of Algorithm 1 is the first thing to test in practice.","The bound $\\mathrm{PoA} \\le R_{\\max}/(2N)\\sum_i 1/\\varphi_i$ shrinks with the number of clients $N$, suggesting the scheme becomes more efficient as the client population grows, which fits cross-device federated learning at scale.","The same two-stage game machinery could be repurposed for other strategic client-controlled resources, such as local computation effort, communication bandwidth, or data quality, with the price-of-anarchy analysis carried over.","A controlled experiment that drives $\\rho_L$ toward zero while measuring social welfare under random sampling would directly test the predicted unbounded price of anarchy in a real training system."],"forward_implications":["The server can precompute a mean-field estimate and then set time-dependent rewards and sampling probabilities so that no client can improve its utility by deviating, provided the fixed point is actually reached.","Under uniform random sampling, efficiency loss can blow up without bound as the minimum allowed privacy budget tends to zero; under the proposed privacy-aware sampling, the price of anarchy stays bounded by a constant that depends only on the maximum reward, the number of clients, and the cost weights.","The convergence bounds give explicit learning-rate conditions under which privacy-preserving federated learning with this sampling scheme provably converges for both convex and non-convex global losses.","The adaptive extension yields closed-form expressions for the optimal sampling ratio and reward when the total privacy budget of sampled clients varies over time.","Across six image datasets and three sampling rates, the framework reports higher accuracy and lower server cost than the random, AOCS, Fed-CBS, and DELTA baselines under IID and Non-IID data splits."],"supporting_citations":[{"why":"Defines the FedAvg baseline and the uniform client sampling convention that FedPCS compares against.","marker":"[8]"},{"why":"Introduces concentrated differential privacy, the noise model whose privacy budget is the strategic variable in the game.","marker":"[15]"},{"why":"Supplies the adaptive client sampling formulation and aggregation weights that the paper adapts to privacy-aware probabilities.","marker":"[9]"},{"why":"Provides the client sampling variance bound used in the one-round progress and convergence analyses.","marker":"[6]"},{"why":"Gives the Polyak-Lojasiewicz-based accuracy-loss bound that Proposition 2 builds on.","marker":"[51]"},{"why":"Supplies the price-of-anarchy definition used to compare random and privacy-aware sampling.","marker":"[39]"},{"why":"Provides the quadratic privacy-cost model used in the clients' utility functions.","marker":"[36]"},{"why":"Supplies the discrete-time linear-quadratic optimal control machinery used to derive the optimal correction factor.","marker":"[52]"}],"fun_headline_variants":["Stackelberg game tunes privacy budgets in federated learning","Reward-based sampling beats random in federated privacy","Game-theoretic client sampling cuts federated learning's efficiency loss","Privacy-aware sampling bounds price of anarchy in FL","Mean-field estimator yields equilibrium for privacy-aware FL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence proof for the mean-field estimator in Theorem 3 asserts a contraction coefficient $\\sqrt{\\nu} < 1$ without deriving it and compares outputs for two different clients rather than successive iterates of the same mapping, so the claim that Algorithm 1 converges to the fixed point is the load-bearing support for the equilibrium strategy profile.","fun_headline_variants_meta":{"raw":{"variants":["Stackelberg game tunes privacy budgets in federated learning","Reward-based sampling beats random in federated privacy","Game-theoretic client sampling cuts federated learning's efficiency loss","Privacy-aware sampling bounds price of anarchy in FL","Mean-field estimator yields equilibrium for privacy-aware FL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000913,"raw_usage":{"total_tokens":3989,"prompt_tokens":1078,"completion_tokens":2911,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":694,"completion_tokens_details":{"reasoning_tokens":2815}},"tokens_in":694,"tokens_out":2911,"duration_ms":20476,"temperature":1.0,"reasoning_tokens":2815,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:31:37.290927+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a small instance, for example $N=2$, $T=3$, $\\rho_L=1$, $\\rho_H=12$, $\\alpha_L=0.1$, $\\alpha_H=0.9$, from several initial choices of $\\phi_0(t)$, and check whether the iterates converge to a common fixed point; a single divergent trajectory or an initial-condition-dependent limit would refute Theorem 3's contraction claim and undermine the guarantee that the Stackelberg equilibrium strategies are actually computed.","supporting_citations":[{"cited_title":"Concentrated differential privacy: Simplifications, extensions, and lower bounds,","cited_arxiv_id":null,"evidence_quote":"Introduces concentrated differential privacy, the noise model whose privacy budget is the strategic variable in the game."},{"cited_title":"Tackling system and statistical heterogeneity for federated learning with adaptive client sampling,","cited_arxiv_id":null,"evidence_quote":"Supplies the adaptive client sampling formulation and aggregation weights that the paper adapts to privacy-aware probabilities."},{"cited_title":"Adaptive heterogeneous client sampling for federated learning over wireless networks,","cited_arxiv_id":null,"evidence_quote":"Provides the client sampling variance bound used in the one-round progress and convergence analyses."},{"cited_title":"Algorithms, games, and the internet,","cited_arxiv_id":null,"evidence_quote":"Supplies the price-of-anarchy definition used to compare random and privacy-aware sampling."},{"cited_title":"Incentive mechanism for spatial crowdsourcing with unknown social-aware workers: A three-stage stackelberg game approach,","cited_arxiv_id":null,"evidence_quote":"Provides the quadratic privacy-cost model used in the clients' utility functions."},{"cited_title":"Discrete lq optimal control with integral action: A simple controller on incremental form for mimo systems,","cited_arxiv_id":null,"evidence_quote":"Supplies the discrete-time linear-quadratic optimal control machinery used to derive the optimal correction factor."}],"review_version":1}