{"id":"e015261a-1cbf-4517-8b51-56a14c0ec8e9","arxiv_id":"2502.01313","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"Randomized classifiers can strictly outperform deterministic ones under label-imbalance conditions on gaming regions, but the claimed SERM generalization bound rests on an unjustified supremum-expectation exchange.","lead":"This paper analyzes randomized classifiers in strategic classification, where agents game a publicly known model. It claims randomized models can never be worse and sometimes beat deterministic ones, with sample-complexity bounds, but a central proof step that swaps a supremum and an expectation is unjustified.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3 relies on Lemma 2, which is false as stated; a two-classifier counterexample shows the sup/expectation interchange fails, so the central generalization bound is unproven.","rationale":"The paper's advertised contribution is the sample-complexity guarantee for SERM over randomized classifiers (Theorem 3). The proof reduces the excess risk to the expected supremum of g(Q,hat{Q}) over Q and then interchanges expectation and supremum. Both premises of that interchange are broken. First, Lemma 2 is asserted with a one-sentence proof that is a non sequitur: the existence of a single Q* dominating g(Q,S) for all S and all Q does not follow from any property of best responses. Second, the lemma is false: the two-classifier example above yields E_S sup_Q g > sup_Q E_S g, the exact opposite of the equality the lemma claims. Third, even if a corrected fixed-Q' lemma existed, the application in Eq. (45) sets Q'=hat{Q}, which depends on S, so the lemma cannot be invoked. Since the main theorem's proof rests entirely on this step, Theorem 3 is unproven as written. The modeling contribution (randomized strategic classification, Theorem 1's sufficient conditions) may survive, and the deterministic bound (Theorem 4) might be provable through a different standard uniform-deviation argument, but these do not rescue the paper's central randomized generalization claim. Our read aligns with the reader's: REJECT with moderate confidence, specifically because of Lemma 2 and its application.","tokens_in":13371,"tokens_out":14928,"duration_ms":120560,"concrete_test":"Implement the finite check: enumerate p∈[0,1] for the two-classifier problem described (X={0,1}, f0,f1 as above, c=1/2 for toggling, Q'=δ_{f0}, D: x=1, P(y=1)=0.9), compute g(Q,S) for S=(1,+1) and S=(1,-1), and verify that E_S sup_Q g = 0.5 > sup_Q E_S g = 0.4. This directly falsifies Lemma 2 and removes the equality used in Eq. (45), so the claimed rate in Theorem 3 does not follow from the supplied argument.","verdict_should_be":"REJECT","load_bearing_attack":"Lemma 2 is the load-bearing step: it claims that for fixed Q' the supremum over Q of g(Q,S)=R_{Δ_Q}(Q')-r_{Δ_Q}(Q') can be pulled through the expectation over S because a single Q* pointwise dominates all Q for every dataset S ('by the definition of the best response'). This domination does not follow and is generally impossible. Finite counterexample: take X={0,1}, F={f0,f1} with f0(0)=1,f0(1)=-1, f1(0)=-1,f1(1)=1, cost c(x,z)=0 if z=x and 1/2 otherwise, Q'=δ_{f0}, and D supported on x=1 with P(y=1)=0.9. Writing p=Q(f0), the best response is Δ_Q(1)=0 iff p>5/8, otherwise Δ_Q(1)=1. For n=1, g(Q,S) is 0.1 on S=(1,+1) and -0.1 on S=(1,-1) when p>5/8, and -0.9 and 0.9 respectively when p<5/8. Hence sup_Q g(Q,(1,+1))=0.1 and sup_Q g(Q,(1,-1))=0.9, but no single Q attains both; indeed E_S sup_Q g=0.5>sup_Q E_S g=0.4, contradicting Lemma 2. The proof of Theorem 3 then applies this lemma with Q'=hat{Q}, a data-dependent quantity, which is outside even the (false) statement's scope. Theorem 3 therefore has no valid proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a strategic classification framework in which the learner commits to a distribution Q over a hypothesis class F rather than to a single deterministic classifier. It claims three main results: (i) under certain sufficient conditions the optimal randomized classifier strictly outperforms the optimal deterministic classifier and never performs worse; (ii) the excess risk of Strategic Empirical Risk Minimisation (SERM) over randomized classifiers is bounded by a Rademacher-complexity term of the same form as in the deterministic setting, yielding the same convergence rate; and (iii) as a byproduct, slightly improved bounds are obtained for the deterministic case. The central technical result is Theorem 3, whose proof is deferred to Appendix B and rests on an exchange of expectation and supremum stated in Lemma 2.","tokens_in":13704,"tokens_out":9513,"duration_ms":75774,"significance":"If the results were correct, the paper would provide a useful statistical foundation for randomized (Gibbs) classifiers in strategic settings, generalizing earlier work that was restricted to specific hypothesis classes or constructed examples. The conceptual contribution of Theorem 1, giving sufficient conditions under which randomisation helps, is interesting and appears plausible. However, the sample-complexity claim, which is the main advertised advantage over prior work, is not supported: Theorem 3 relies on a lemma that is false and on an invalid application of that lemma to a data-dependent quantity. The paper therefore does not currently establish its central technical claim.","major_comments":[{"comment":"The claimed identity E_{S~D^n}[sup_{Q} g(Q,S)] = sup_{Q} E_{S~D^n}[g(Q,S)] is false. Counterexample: let X={0,1}, Y={-1,1}, F={f0,f1} with f0(0)=1, f0(1)=-1, f1(0)=-1, f1(1)=1; let cost c(x,z)=0 if z=x and 1/2 otherwise, fix Q'=delta_{f0}, and let D be supported on x=1 with P(y=1)=0.9. Writing p=Q(f0), the best response Delta_Q(1) is 0 if p>5/8 and 1 otherwise. For n=1, R_{Delta_Q}(Q') is 0.1 when p>5/8 and 0.9 when p<5/8. Hence g(Q,(1,+1)) is 0.1 for p>5/8 and -0.1 for p<5/8, while g(Q,(1,-1)) is -0.9 for p>5/8 and 0.9 for p<5/8. Thus E_S sup_Q g = (0.1+0.9)/2 = 0.5, but for every fixed Q, E_S g(Q,S) = R_{Delta_Q}(Q') - E_S r_{Delta_Q}(Q') = 0, so sup_Q E_S g = 0. This contradicts Lemma 2. The proof's assertion that a single Q* dominates g(Q,S) for all S 'by the definition of the best response' is unjustified; the maximizer of g depends on S.","section":"Appendix B, Lemma 2"},{"comment":"Even if Lemma 2 were correct for a fixed Q', the proof of Theorem 3 applies it with Q'=Q_hat, which is a function of the training set S. Lemma 2 is stated only for a fixed distribution Q' independent of S, and no uniform version is established. Consequently, the first equality in Eq. (45) is not licensed by Lemma 2. This is a separate, load-bearing gap in the proof of the paper's main sample-complexity bound.","section":"Theorem 3 proof, Eq. (45)"}],"minor_comments":[{"comment":"In the displayed equation, the term R_{Delta_{f'}}(f) should presumably be R_{Delta_{f'}}(f') to match the surrounding algebra.","section":"Appendix A, Eq. (33)"},{"comment":"The notation P(F) is used both for the set of probability measures over F and, later, for the probability of an event; using a dedicated symbol such as Prob or Delta(F) for the former would reduce ambiguity.","section":"Section 3.1"},{"comment":"The step in Eq. (27) involving complements would be clearer if the complement operation were written explicitly, since the text alternates between superscript c and set difference notation.","section":"Appendix A, Lemma 1 proof"},{"comment":"The comparison with Theorem 6 claims an improvement by removing the Bu* term, but the two bounds are expressed with different norms and constants; the exact nature and magnitude of the improvement should be stated more carefully.","section":"Section 5.2, Corollary 1"},{"comment":"Theorem 4, described as a byproduct, is stated without a proof; a proof or a reference to a full derivation would strengthen the paper's deterministic-case claim.","section":"Section 5, Theorem 4"}],"recommendation":"reject","confidential_remarks":"The central issue is that Theorem 3, the main sample-complexity contribution, is unproven because Lemma 2 is false and because the proof applies the lemma to the data-dependent Q_hat. The counterexample is simple and should be communicated to the authors. The conceptual Theorem 1 is interesting, but the paper as submitted does not support the advertised learning-theoretic claim. I would be willing to consider a revision that either proves a corrected generalization bound or explicitly narrows the claims to what can be established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is worth knowing about, but not for the reason the authors hope. The setup—strategic classification with the learner choosing a distribution over classifiers—is a natural extension, and the sufficient conditions in Theorem 1 for randomized classifiers to beat the best deterministic one look like a genuine contribution. I also believe the Rademacher framework they build, including Lemma 3 equating the randomized and deterministic loss class complexities, is sound and could be reused.\n\nThe problem is Theorem 3, their main sample-complexity claim. The proof depends on Lemma 2, which claims you can swap the supremum over Q with the expectation over training sets because a single Q* pointwise dominates all other Q for every S. That statement is false, and the stress-test counterexample is convincing: a two-classifier, one-sample example gives E_S sup_Q g = 0.5 > sup_Q E_S g = 0.4, so the asserted equality fails. The one-sentence proof—'by the definition of the best response'—is doing no work. On top of that, the proof of Theorem 3 applies Lemma 2 with Q' equal to the data-dependent empirical minimizer hat{Q}, which is outside the lemma's own statement.\n\nSo the central generalization bound is unsupported. The deterministic analogue, Theorem 4, may have a different route, but the randomized claim needs a new proof or a different technique.\n\nWhere the paper stands: the modeling contribution is real, Theorem 1 appears coherent, and the comparison with prior work is fair. The authors are honest about not having a training algorithm. No code or data, which is fine for theory. The citation pattern looks fine. The conclusion that randomisation has 'no substantial downsides' overstates the case, since the statistical guarantee is exactly what is missing.\n\nWho this is for: anyone working on strategic classification, especially on the role of randomization, would want to know about the setup and Theorem 1. Serious referees should see it, because the paper is worth grappling with even if this version's main theorem doesn't stand. Reject as is, but I'd send it out—the framework is salvageable, and even in its current state it identifies a real modeling direction.","headline":"Novel setup, but the main generalization bound rests on a false lemma—Theorem 3 is unproven as written.","tokens_in":14165,"tokens_out":2116,"would_cite":false,"duration_ms":18851,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a learner who randomises over classifiers in strategic classification—sampling a new classifier for each prediction—can match or beat the best deterministic classifier and learn at the same sample rate as the…","keywords":["strategic classification","randomised classifiers","Gibbs classifiers","strategic empirical risk minimisation","Rademacher complexity","excess risk","Stackelberg games","gaming"],"falsifier":"Fix a finite hypothesis class $F$, a data distribution $D$, and a cost function $c$, and compute both sides of Lemma 2's claimed equality, $\\mathbb{E}_S \\sup_Q g(Q,S)$ and $\\sup_Q \\mathbb{E}_S g(Q,S)$ with $g(Q,S)=R_{\\Delta_Q}(Q')-r_{\\Delta_Q}(Q')$ for some fixed $Q'$. If the two differ on any such instance, the supremum–expectation exchange used to prove Theorem 3 is invalid and the proof's guarantee no longer follows.","tokens_in":13131,"feed_emoji":"🎲","tokens_out":9925,"duration_ms":80295,"temperature":0.7,"pith_summary":"In strategic classification, agents know the deployed classifier and can pay to change their features to game it. This paper argues that the learner should commit not to one deterministic classifier but to a distribution over classifiers—a Gibbs classifier—so agents cannot be sure which classifier to game. It proves that the optimal randomised classifier is never worse than the optimal deterministic classifier, and is strictly better under a stated set of conditions involving points that are expensive to game or gameable only non-simultaneously. It then bounds the excess risk of Strategic Empirical Risk Minimisation over randomised classifiers by the Rademacher complexity of the corresponding deterministic loss class, giving the same convergence rate as the deterministic i.i.d. case.","feed_headline":"Randomised classifiers can beat strategic gaming without extra data","feed_subtitle":"A random choice among optimal classifiers is never worse than the best single classifier, and learns at the same rate.","key_machinery":"The central objects are the strategic risk $R_{\\Delta_Q}(Q) = \\mathbb{E}_{f\\sim Q}\\, \\mathbb{E}_{(x,y)\\sim D}[l(f(\\Delta_Q(x)), y)]$ and its empirical counterpart, where $\\Delta_Q$ is the agents' best response to the distribution $Q$ over classifiers, and the loss class $F^l_{\\Delta_Q} = l \\circ F \\circ \\Delta_Q$ of deterministic losses composed with an optimal response. The argument runs through three mechanisms: Lemma 3 equates the Rademacher complexity of the randomised loss class to that of the deterministic loss class; the standard Rademacher bound of Bartlett and Mendelson transfers the generalisation gap; and Lemma 2 exchanges the supremum over $Q$ with the expectation over training sets, which is the step that produces the same rate for the data-dependent $\\hat{Q}$ as for a fixed classifier.","core_discovery":"The paper establishes two results. First, if the optimal deterministic strategic risk is positive and there exist two optimal classifiers $f$ and $f'$ such that on the set of points that can expensively game one but not the other ($E_f \\oplus E_{f'}$) and on the set gameable by each separately but not jointly ($N_{f,f'}$), negative-class points are at least as likely as positive-class points, with at least one inequality strict, then the uniform mixture over $f$ and $f'$ achieves lower strategic risk than either classifier alone. Second, if $\\hat{Q}$ minimises empirical strategic risk $r_{\\Delta_{\\hat{Q}}}(\\hat{Q})$ and $Q^*$ minimises population strategic risk $R_{\\Delta_{Q^*}}(Q^*)$, then the expected excess risk of $\\hat{Q}$ is at most $\\sup_{Q} 2 R_n(F^l_{\\Delta_Q})$, the Rademacher complexity of the deterministic loss class composed with the best response to $Q$; a high-probability version adds $\\sqrt{\\ln(1/\\delta)/(2n)}$. This makes randomised classifiers learned by SERM converge to the optimal randomised risk at the same rate as deterministic classifiers in the i.i.d. setting.","pith_inferences":["If the missing derivation in Lemma 2 cannot be supplied, Theorem 3 as stated is unproven, but the rate claim might survive through a different proof that avoids the pointwise domination step, so the practical conclusion is not necessarily wrong.","Theorem 1's conditions suggest a design heuristic: deliberately choose two optimal classifiers with disjoint cheap-gaming regions so that no single cheap manipulation games both, and test empirically whether the measured gaming rate falls under the random mixture.","The paper leaves training algorithms for $\\mathcal{P}(F)$ open; a plausible next step is to restrict to a parameterised family of distributions and ask whether the same statistical rate is achievable with a tractable optimisation.","A testable prediction of the theory is that randomisation should disproportionately discourage gaming by negative-class agents, because their expected benefit is diluted by the probability of drawing a classifier they have not gamed."],"forward_implications":["Randomised classifiers are a drop-in statistical replacement: the SERM excess-risk bound for distributions over $F$ is the same Rademacher bound as for deterministic $F$, so no extra data are required to learn a distribution over classifiers rather than a single classifier.","Because the bound is expressed through $F^l_{\\Delta_Q}$, existing analyses of deterministic hypothesis classes apply unchanged to the randomised setting.","Since $Q^*$ may put all its mass on the optimal deterministic classifier, randomised SERM can never do worse in the limit, and under Theorem 1's conditions it does strictly better.","The high-probability bound matches the i.i.d. rate, so strategic gaming does not degrade the statistical convergence rate when the learner randomises."],"supporting_citations":[{"why":"Defines the strategic classification model and the agent best-response game that this paper generalises to randomised classifiers.","marker":"Hardt et al. [2016]"},{"why":"Defines Strategic Empirical Risk Minimisation, the estimator whose excess risk is bounded in Theorem 3.","marker":"Levanon and Rosenfeld [2021]"},{"why":"Supplies the Rademacher complexity bound on the generalisation gap that Theorem 3 builds on.","marker":"Bartlett and Mendelson [2002]"},{"why":"Provides the Gibbs-classifier concept motivating the paper's treatment of a distribution over classifiers as the learner's choice.","marker":"Ng and Jordan [2001]"},{"why":"Provides the strategic VC-dimension baseline and the prior two-dimensional example of randomised linear classifiers that this paper generalises.","marker":"Sundaram et al. [2023]"},{"why":"Gives the corrected strategic hinge-loss bound for linear classifiers that Corollary 1 improves on.","marker":"Rosenfeld and Rosenfeld [2023]"},{"why":"Supplies the Rademacher complexity estimate for linear classes used in the proof of Corollary 1.","marker":"Shalev-Shwartz and Ben-David [2014]"}],"fun_headline_variants":["Randomisation can never hurt strategic classification","Randomized classifiers match deterministic learning rates","Strategic classification benefits from randomisation","Randomized models achieve better or equal strategic accuracy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof needs a single randomised classifier $Q^*$ to dominate the generalisation gap for every possible training set at once, and it uses that domination twice in Theorem 3—once for a fixed distribution and once for the data-dependent $\\hat{Q}$ the learner actually produces—while Appendix B's Lemma 2 states the property only for a fixed $Q'$ and gives no derivation beyond 'by the definition of the best response.'","fun_headline_variants_meta":{"raw":{"variants":["Randomisation can never hurt strategic classification","Randomized classifiers match deterministic learning rates","Strategic classification benefits from randomisation","Randomized models achieve better or equal strategic accuracy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000756,"raw_usage":{"total_tokens":3389,"prompt_tokens":999,"completion_tokens":2390,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":615,"completion_tokens_details":{"reasoning_tokens":2338}},"tokens_in":615,"tokens_out":2390,"duration_ms":17906,"temperature":1.0,"reasoning_tokens":2338,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T15:42:31.591094+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a finite hypothesis class $F$, a data distribution $D$, and a cost function $c$, and compute both sides of Lemma 2's claimed equality, $\\mathbb{E}_S \\sup_Q g(Q,S)$ and $\\sup_Q \\mathbb{E}_S g(Q,S)$ with $g(Q,S)=R_{\\Delta_Q}(Q')-r_{\\Delta_Q}(Q')$ for some fixed $Q'$. If the two differ on any such instance, the supremum–expectation exchange used to prove Theorem 3 is invalid and the proof's guarantee no longer follows.","supporting_citations":[],"review_version":1}