Pith. sign in

REVIEW 2 major objections 5 minor 29 references

Strategic Classification with Randomised Classifiers

T0 review · 2 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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…

desk verdict Novel setup, but the main generalization bound rests on a false lemma—Theorem 3 is unproven as written. read the letter →

arxiv 2502.01313 v2 pith:36FY4AWU submitted 2025-02-03 cs.LG stat.ML

Jack Geary , Henry Gouk This is my paper · ORCID
classification cs.LGstat.ML MSC 68Q3268T05
keywords strategicclassificationrandomisedclassifiersGibbsempiricalriskminimisationRademachercomplexityexcessStackelberggamesgaming
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.'

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [Appendix B, Lemma 2] 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.
  2. [Theorem 3 proof, Eq. (45)] 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.
minor comments (5)
  1. [Appendix A, Eq. (33)] In the displayed equation, the term R_{Delta_{f'}}(f) should presumably be R_{Delta_{f'}}(f') to match the surrounding algebra.
  2. [Section 3.1] 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.
  3. [Appendix A, Lemma 1 proof] 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.
  4. [Section 5.2, Corollary 1] 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.
  5. [Section 5, Theorem 4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is self-contained; the suspected Lemma 2 issue is a correctness gap, not a circular step.

full rationale

The central generalization bound (Theorem 3) is derived from a Rademacher-complexity argument: it uses the minimizer property of \hat Q, a sup/expectation exchange (Lemma 2), the standard uniform-deviation bound (Theorem 2, Bartlett-Mendelson), and a comparison between randomized and deterministic Rademacher complexities (Lemma 3). None of these steps defines its conclusion in terms of its premise, fits a parameter and then reports it as a prediction, or imports a uniqueness theorem from the authors' own prior work. The suspect step, Lemma 2, asserts a pointwise domination 'by the definition of the best response'; even if that assertion is false or unproven (as a reviewer's counterexample suggests), the failure is a mathematical soundness flaw, not circularity, because the lemma is not established by assuming the theorem it supports. There is no load-bearing self-citation: the paper cites no prior work of its own as the justification for the main bound, and the external results cited (Bartlett-Mendelson Rademacher bounds, Mohri's VC-dimension corollaries, Rosenfeld-Rosenfeld strategic hinge bound) are used as standard tools or for comparison, not to assume Theorem 3. The sufficient-condition theorem for randomisation (Theorem 1) is also proved by direct decomposition of the risk difference, with the stated inequalities making the final expression non-negative; that is a legitimate algebraic derivation rather than a circular redefinition. Hence no circular step can be exhibited, and the appropriate score is 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

No experimental fitting or invented physical entities. The only hand-tuned analysis constants are the cost thresholds; the main load-bearing unproved premise is Lemma 2 and its extension to random Q_hat.

free parameters (1)
  • Cost thresholds 1 and 2 = 1 and 2
    Definitions of C_f, E_f, G_f in Section 4.1 use hand-chosen constants <1 and <2 to separate cheap, expensive, and feasible gaming. Theorem 1's sufficient conditions are stated relative to these thresholds; no data fitting is involved.
assumptions (4)
  • domain assumption Agents are rational, share a known cost function c, and always seek the positive class.
    Standard strategic classification setup inherited from Hardt et al.; the randomized-agent objective in Eq. (8) assumes expected utility maximization.
  • domain assumption For each Q, a best response Delta_Q exists and is measurable.
    The paper does not state regularity conditions on X, F, or c ensuring the argmax in Eq. (8) is well-defined and measurable; required for the Rademacher bounds.
  • ad hoc to paper Lemma 2: for fixed Q' a single Q* in P(F) satisfies g(Q,S) <= g(Q*,S) for all S.
    Unproved, likely false, and load-bearing; the proof cites 'definition of best response' without a derivation.
  • ad hoc to paper The supremum-expectation exchange in Lemma 2 applies when the inner classifier is the data-dependent Q_hat.
    Lemma 2 is stated for a fixed Q', but Theorem 3 applies it to the empirical minimizer, which depends on S; no argument justifies this.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strategic Classification with Randomised Classifiers." pith.science (2026). https://pith.science/paper/36FY4AWU

@misc{pith2026250201313,
  author       = {Pith},
  title        = {Pith review of: Strategic Classification with Randomised Classifiers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/36FY4AWU}},
  note         = {Machine review of arXiv:2502.01313}
}
read the original abstract

We consider the problem of strategic classification, where a learner must build a model to classify agents based on features that have been strategically modified. Previous work in this area has concentrated on the case when the learner is restricted to deterministic classifiers. In contrast, we perform a theoretical analysis of an extension to this setting that allows the learner to produce a randomised classifier. We show that, under certain conditions, the optimal randomised classifier can achieve better accuracy than the optimal deterministic classifier, but under no conditions can it be worse. When a finite set of training data is available, we show that the excess risk of Strategic Empirical Risk Minimisation over the class of randomised classifiers is bounded in a similar manner as the deterministic case. In both the deterministic and randomised cases, the risk of the classifier produced by the learner converges to that of the corresponding optimal classifier as the volume of available training data grows. Moreover, this convergence happens at the same rate as in the i.i.d. case. Our findings are compared with previous theoretical work analysing the problem of strategic classification. We conclude that randomisation has the potential to alleviate some issues that could be faced in practice without introducing any substantial downsides.

Figures

Figures reproduced from arXiv: 2502.01313 by the authors.

Figure 1
Figure 1. Comparing gaming behaviour for two deterministic classifiers, [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 10 canonical work pages

  1. [1]

    The scored society: Due process for automated predictions

    Danielle Keats Citron and Frank Pasquale. The scored society: Due process for automated predictions. Wash. L. Rev., 89: 0 1, 2014

    work page 2014

  2. [2]

    The social cost of strategic classification

    Smitha Milli, John Miller, Anca D Dragan, and Moritz Hardt. The social cost of strategic classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 230--239, 2019

    2019

  3. [3]

    Strategic classification

    Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111--122, 2016

    2016

  4. [4]

    Strategic classification made practical

    Sagi Levanon and Nir Rosenfeld. Strategic classification made practical. In International Conference on Machine Learning, pages 6243--6253. PMLR, 2021

    2021

  5. [5]

    Adversarial classification

    Nilesh Dalvi, Pedro Domingos, Mausam, Sumit Sanghai, and Deepak Verma. Adversarial classification. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 99--108, 2004

    2004

  6. [6]

    Stackelberg games for adversarial prediction problems

    Michael Br \"u ckner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 547--555, 2011

    2011

  7. [7]

    Strategic classification is causal modeling in disguise

    John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In International Conference on Machine Learning, pages 6917--6926. PMLR, 2020

    2020

  8. [8]

    Strategic classification with graph neural networks

    Itay Eilat, Ben Finkelshtein, Chaim Baskin, and Nir Rosenfeld. Strategic classification with graph neural networks. arXiv preprint arXiv:2205.15765, 2022

    arXiv 2022

Show all 29 references
  1. [9]

    Incentive-aware pac learning

    Hanrui Zhang and Vincent Conitzer. Incentive-aware pac learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5797--5804, 2021

    2021

  2. [10]

    Learning losses for strategic classification

    Tosca Lechner and Ruth Urner. Learning losses for strategic classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7337--7344, 2022

    2022

  3. [11]

    Strategic classification with unknown user manipulations

    Tosca Lechner, Ruth Urner, and Shai Ben-David. Strategic classification with unknown user manipulations. In International Conference on Machine Learning, pages 18714--18732. PMLR, 2023

    2023

  4. [12]

    Strategic classification in the dark

    Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen, and Nir Rosenfeld. Strategic classification in the dark. In International Conference on Machine Learning, pages 3672--3681. PMLR, 2021

    2021

  5. [13]

    Bayesian strategic classification

    Lee Cohen, Saeed Sharifi-Malvajerdi, Kevin Stangl, Ali Vakilian, and Juba Ziani. Bayesian strategic classification. arXiv preprint arXiv:2402.08758, 2024

    2024 arXiv

  6. [14]

    The role of randomness and noise in strategic classification

    Mark Braverman and Sumegha Garg. The role of randomness and noise in strategic classification. arXiv preprint arXiv:2005.08377, 2020

    2005 arXiv

  7. [15]

    Pac-learning for strategic classification

    Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. Pac-learning for strategic classification. Journal of Machine Learning Research, 24 0 (192): 0 1--38, 2023

    2023

  8. [16]

    Randomization matters how to defend against strong adversarial attacks

    Rafael Pinot, Raphael Ettedgui, Geovani Rizk, Yann Chevaleyre, and Jamal Atif. Randomization matters how to defend against strong adversarial attacks. In International Conference on Machine Learning, pages 7717--7727. PMLR, 2020

    2020

  9. [17]

    A theory of the learnable

    Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27 0 (11): 0 1134--1142, 1984

    1984

  10. [18]

    Pac-learning in the presence of adversaries

    Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. Advances in Neural Information Processing Systems, 31, 2018

    2018

  11. [19]

    Marktform und gleichgewicht

    Heinrich von Stackelberg. Marktform und gleichgewicht. (No Title), 1934

    1934

  12. [20]

    Generalized strategic classification and the case of aligned incentives

    Sagi Levanon and Nir Rosenfeld. Generalized strategic classification and the case of aligned incentives. In International Conference on Machine Learning, pages 12593--12618. PMLR, 2022

    2022

  13. [21]

    Ng and Michael I

    Andrew Y. Ng and Michael I. Jordan. Convergence rates of the Voting Gibbs classifier, with application to Bayesian feature selection. In Proceedings of the Eighteenth International Conference on Machine Learning , 2001

    2001

  14. [22]

    Statistical decision theory and Bayesian analysis

    James O Berger. Statistical decision theory and Bayesian analysis. Springer Science & Business Media, 2013

    2013

  15. [23]

    Game theory

    Michael Maschler, Shmuel Zamir, and Eilon Solan. Game theory. Cambridge University Press, 2020

    2020

  16. [24]

    The disparate effects of strategic manipulation

    Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 259--268, 2019

    2019

  17. [25]

    Fair decisions despite imperfect predictions

    Niki Kilbertus, Manuel Gomez Rodriguez, Bernhard Sch \"o lkopf, Krikamol Muandet, and Isabel Valera. Fair decisions despite imperfect predictions. In International Conference on Artificial Intelligence and Statistics, pages 277--287. PMLR, 2020

    2020

  18. [26]

    Bartlett and Shahar Mendelson

    Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian Complexities : Risk Bounds and Structural Results . Journal of Machine Learning Research, 3 0 (Nov): 0 463--482, 2002

    2002

  19. [27]

    Foundations of machine learning, 2018

    Mehryar Mohri. Foundations of machine learning, 2018

    2018

  20. [28]

    One-shot strategic classification under unknown costs

    Elan Rosenfeld and Nir Rosenfeld. One-shot strategic classification under unknown costs. arXiv preprint arXiv:2311.02761, 2023

    2023 arXiv

  21. [29]

    Understanding Machine Learning: From Theory to Algorithms

    Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132

    2014

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.