PAC-learning for Strategic Classification

Ravi SundaramAnil VullikantiHaifeng XuFan Yao

article2023JMLR52 citations

Establishes a unified PAC-learning framework for strategic classification under heterogeneous agent preferences by introducing the strategic VC-dimension and fully characterizing both the statistical and computational limits of linear classifiers.

Listen

When machine learning systems are deployed in consequential domains like lending, college admissions, and public health screening, individuals frequently alter their reported information to secure favorable outcomes. Prior research has typically assumed that either all individuals share the exact same preference for a positive outcome or that every data point acts as a pure adversary. In reality, individuals have diverse preferences and varying manipulation costs, creating a critical need for learning systems that are statistically reliable and computationally viable under realistic gaming behaviors.

The article develops a unified mathematical framework for classification under strategic manipulation, explicitly characterizing when and how models can be reliably learned from data when agents have heterogeneous preferences.

The authors conducted a formal theoretical analysis using the Probably Approximately Correct (PAC) learning framework, which mathematically bounds the amount of training data needed for accurate generalization. They introduced the Strategic Vapnik-Chervonenkis (SVC) dimension to measure statistical model complexity and evaluated Empirical Risk Minimization algorithms, specifically focusing on linear classifiers under different cost functions and preference structures.

The analysis established several key findings. First, strategic classification is statistically learnable using a sample size directly bounded by the newly defined SVC dimension, which strictly unifies standard learning and adversarial evasion settings. Second, statistical learnability depends heavily on how manipulation costs are structured: for instance-invariant costs (where modifying features costs the same regardless of the baseline), the complexity of linear classifiers remains well-behaved and bounded by their dimension plus one; however, under instance-wise costs (where manipulation costs vary per individual), the SVC dimension becomes infinite even in two dimensions. Third, computational tractability depends primarily on preferences: strategic empirical risk minimization for linear classifiers is solvable in polynomial time if preferences are essentially adversarial, but becomes computationally intractable (NP-hard) under general preferences. Finally, randomizing classifier decisions can strictly improve accuracy over any deterministic model, though this advantage vanishes when manipulation incurs zero cost.

These findings demonstrate that organizations cannot treat gaming robustness purely as a statistical problem; deploying strategy-aware algorithms involves distinct trade-offs between data requirements and computational feasibility. While linear models remain statistically robust under uniform cost structures, computing optimal models under diverse individual preferences is computationally hard, meaning decision-makers cannot simply rely on standard risk minimization solvers.

Organizations developing automated evaluation systems should identify whether applicant manipulation costs are uniform or user-specific before deploying models. When preferences exhibit adversarial patterns, decision-makers can implement tractable convex optimization routines. Additionally, practitioners can explore randomized decision boundaries to deter strategic gaming, provided the regulatory and compliance context permits probabilistic decision rules.

The primary limitation of this work is its assumption of full information during training, requiring the learner to know manipulation cost functions and preference values upfront. While the mathematical proofs provide high confidence in the theoretical limits, applying these insights in practice requires caution, particularly because user preference values and manipulation costs must be accurately estimated from real-world data.

Biocomplexity Institute Department of Computer Science Northeastern University University of Chicago University of Virginia avc classification models data points strategic classification PAC learning strategic VC-dimension

arXiv: 2012.03310

Paper: Evasion Attacks against Machine Learning at Test Time, Battista Biggio et al. (2013). Read this account of test-time evasion first to understand the adversarial manipulation setting that the source unifies with strategic classification.

No sufficiently relevant recommendations were found.

Cover for PAC-learning for Strategic Classification

Abstract

The study of strategic or adversarial manipulation of testing data to fool a classifier has attracted much recent attention. Most previous works have focused on two extreme situations where any testing data point either is completely adversarial or always equally prefers the positive label. In this paper, we generalize both of these through a unified framework by considering strategic agents with heterogenous preferences, and introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. SVC provably generalizes the recent concept of adversarial VC-dimension (AVC) introduced by Cullina et al. (2018). We instantiate our framework for the fundamental strategic linear classification problem. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) its computational tractability by pinning down the complexity of the empirical risk minimization problem. Interestingly, the SVC of linear classifiers is always upper bounded by its standard VC-dimension. This characterization also strictly generalizes the AVC bound for linear classifiers in (Cullina et al., 2018). Finally, we briefly investigate the power of randomization in our strategic classification setup. We show that randomization may strictly increase the accuracy in general, but will not help in the special case of adversarial classification with zero-manipulation-cost.

Topics

avc classification models data points support vector machine

Keywords

strategic classification PAC learning strategic VC-dimension strategic empirical risk minimization Strategic Shattering Coefficients adversarial classification statistical learnability agnostic PAC learning optimal deterministic classifier linear classifiers

1. Introduction
1.1 Overview of Our Results
1.2 Related Works
2. Model
2.1 The Strategic Classification (StraC) Problem
2.2 Notable Special Cases
3. VC-Dimension for Strategic Classification
3.1 SVC generalizes Adversarial VC-Dimension (AVC)
3.2 SVC under Separable Cost Functions
4. Strategic Linear Classification
4.1 Strategic VC-Dimension of Linear Classifiers
4.2 The Complexity of Strategic Linear Classification
5. The Power and Limits of Randomization
6. Summary
Acknowledgement
Appendix A. Omitted Proofs from Section
A.1 Proof of Proposition 6
A.2 Proof of Corollary 7
A.3 Proof of Proposition 8
A.4 Proof of Proposition 9
Appendix B. Omitted Proofs in Section 5
B.1 Proof of Proposition 18
B.2 An Additional 1-d Example for Proposition 18
B.3 Proof of Proposition 21
References

Knowls

Knowl 1 — Strategic classification with heterogeneous preferences
model/method
A data point is a triple $(x,y,r)$ , where $x\in\mathcal X$ is its feature, $y\in\{-1,+1\}$ is its true label, and $r\in\mathcal R\subseteq\mathbb R$ is its reward for receiving label $+1$ ; its reward for label $-1$ is normalized to $0$ . A classifier $h:\mathcal X\to\{-1,+1\}$ is deployed before test points respond. A test point with original feature $x$ can report a feature $z$ at nonnegative cost $c(z;x)$ and chooses a best response
$\Delta_c(x,r;h)\in\arg\max_{z\in\mathcal X}\left[r\,\mathbf 1\{h(z)=+1\}-c(z;x)\right].$
If multiple features maximize utility, the analysis allows the point to take any best response and uses worst-case loss. Manipulation changes the feature, not the true label. For a distribution $D$ over $(x,y,r)$ , the strategic classification risk is $L_c(h;D)=\Pr_{(x,y,r)\sim D}[h(\Delta_c(x,r;h))\ne y]$ . Training examples are i.i.d. samples from $D$ and are unmanipulated; their preference values are observed.
Knowl 2 — Strategic VC-dimension
definition
For a hypothesis class $\mathcal H$ of binary classifiers, preference set $\mathcal R$ , and manipulation cost $c$ , the strategic shattering coefficient at integer $n\ge 1$ is
$\sigma_n(\mathcal H,\mathcal R,c)=\max_{(x_i,r_i)_{i=1}^n\in(\mathcal X\times\mathcal R)^n}\left|\left\{\big(h(\Delta_c(x_i,r_i;h))\big)_{i=1}^n:h\in\mathcal H\right\}\right|.$
It counts the distinct vectors of strategic classification outcomes that classifiers in $\mathcal H$ can induce on selected features and preferences; the true labels are not part of the maximization. The strategic VC-dimension is $\mathrm{SVC}(\mathcal H,\mathcal R,c)=\sup\{n\in\mathbb N:\sigma_n(\mathcal H,\mathcal R,c)=2^n\}$ .
Knowl 3 — Agnostic PAC learning by strategic empirical risk minimization
theoretical result
Let $D$ be any distribution over triples $(x,y,r)$ , and let $d=\mathrm{SVC}(\mathcal H,\mathcal R,c)$ . Strategic empirical risk minimization (SERM) returns a classifier minimizing the training sample's strategic error, $\sum_{i=1}^n\mathbf 1\{h(\Delta_c(x_i,r_i;h))\ne y_i\}$ . When $d$ is finite, for every $\epsilon,\delta\in(0,1)$ , an absolute constant $C$ gives the agnostic excess-risk guarantee
$n\ge C\epsilon^{-2}\left(d+\log\frac1\delta\right) \quad\Longrightarrow\quad \Pr\left[L_c(\hat h;D)-\inf_{h\in\mathcal H}L_c(h;D)\le\epsilon\right]\ge 1-\delta,$
where $\hat h$ is an SERM minimizer based on $n$ i.i.d. unmanipulated training examples. Thus SVC supplies the VC-dimension term in the standard agnostic PAC sample-complexity bound for this strategic setting.
Knowl 4 — Relationship between SVC and adversarial VC-dimension
theoretical result
Let $B\subseteq\mathcal X\times\mathcal X$ specify allowed adversarial moves, with $(z,x)\in B$ meaning a point at $x$ may move to $z$ . A cost $c$ is $r$ -consistent with $B$ when $B=\{(z,x):c(z;x)\le r\}$ , for $r>0$ . For any binary hypothesis class $\mathcal H$ , the adversarial VC-dimension under $B$ equals $\mathrm{SVC}(\mathcal H,\{+r,-r\},c)$ . Consequently, if $\{+r,-r\}\subseteq\mathcal R$ , then $\mathrm{SVC}(\mathcal H,\mathcal R,c)\ge\mathrm{AVC}(\mathcal H,B)$ .

The gap can be arbitrarily large: for every positive integer $n$ , there are a hypothesis class of point classifiers, an instance-invariant metric cost, and a preference set $\mathcal R=[-n,-1]\cup[1,n]$ for which $\mathrm{SVC}=n$ , while the ordinary VC-dimension and the adversarial VC-dimension for the cost-induced allowed-move relations are both $1$ .
Knowl 5 — Separable costs bound strategic VC-dimension
theoretical result
Suppose the manipulation cost has the separable form $c(z;x)=\max\{c_2(z)-c_1(x),0\}$ for functions $c_1,c_2:\mathcal X\to\mathbb R$ , and the preference set excludes zero: $0\notin\mathcal R$ . Then, for every binary hypothesis class $\mathcal H$ , $\mathrm{SVC}(\mathcal H,\mathcal R,c)\le 2$ . The bound is tight for some hypothesis classes, including linear classifiers. The exclusion of zero preference matters: allowing $r=0$ can make SVC at least the ordinary VC-dimension of $\mathcal H$ .
Knowl 6 — Exact SVC for linear classifiers with instance-invariant seminorm costs
theoretical result
Let features lie in $\mathbb R^d$ , let $\mathcal H_d$ be the class of all affine linear binary classifiers, and let every point use the same instance-invariant cost $c(z;x)=l(z-x)$ , where $l$ is a seminorm. For bounded preference sets $\mathcal R$ , define the unit ball $B=\{u\in\mathbb R^d:l(u)\le1\}$ and let $V_l$ be the largest linear subspace contained in $B$ . Then
$\mathrm{SVC}(\mathcal H_d,\mathcal R,c)=d+1-\dim(V_l).$
In particular, if $l$ is a norm, its unit ball contains no nonzero linear subspace, so the SVC is exactly $d+1$ .
Knowl 7 — Instance-wise costs can make linear SVC infinite
theoretical result
For linear classifiers on $\mathbb R^2$ , allowing each data point to have its own norm-induced manipulation cost can make strategic VC-dimension infinite, even when every point has the same preference $r=+1$ . More specifically, for every integer $n$ , one can choose $n$ examples with the same original feature and assign them different norms so that affine linear classifiers induce all $2^n$ strategic outcome patterns. Thus instance-wise costs can destroy finite-dimensional statistical learnability measures for linear classification, unlike the instance-invariant case.
Knowl 8 — Polynomial-time SERM in two adversarial regimes
theoretical result
Consider realizable strategic linear classification: the training examples can be perfectly classified after strategic responses, and each point's cost is induced by a seminorm. For a finite sample, write $\min_- =\min\{r_i:y_i=-1\}$ and $\max_+=\max\{r_i:y_i=+1\}$ . SERM can be solved in polynomial time in either of these cases:
- Instance-invariant costs and essentially adversarial preferences: all points share a seminorm cost $c(z;x)=l(z-x)$ , and $\min_-\ge\max_+$ . A convex optimization formulation maximizes a positive separation slack subject to affine constraints on the training features and a unit-bound constraint on the dual seminorm. Under the preference ordering, the relaxation used by this formulation is tight.
- Instance-wise costs and adversarial preferences: each point has its own seminorm cost, and $\min_-\ge0\ge\max_+$ . For each fixed positive separation slack, the feasibility constraints involving the per-point dual seminorms are convex; feasibility is monotone in the slack, so binary search finds a feasible value.
Here the dual seminorm associated with $l_i$ is $l_i^*(w)=\sup\{w\cdot u:l_i(u)\le1\}$ . The polynomial-time claim is in the convex-optimization sense of solving to the required precision.
Knowl 9 — SERM is NP-hard just beyond the tractable regimes
theoretical result
Even for realizable strategic linear classification, the SERM optimization problem is NP-hard in each of two settings: (1) preferences are arbitrary and all points use the instance-invariant Euclidean cost $c(z;x)=\|z-x\|_2$ ; or (2) preferences are essentially adversarial, meaning $\min_-\ge\max_+$ , and costs are instance-wise and induced by norms. These hardness results show that the polynomial-time cases do not extend to these broader settings; they establish hardness for SERM, not impossibility of every alternative learning algorithm.
Knowl 10 — Randomized linear classifiers can strictly improve strategic accuracy
theoretical result
There are strategic classification instances in two-dimensional Euclidean feature space for which a randomized linear classifier achieves zero error, while every deterministic linear classifier makes at least one error. This remains true when all points have the same reward, specifically $r=\sqrt{2}$ , and the manipulation cost is Euclidean distance. The exhibited randomized classifier chooses uniformly between two linear decision boundaries: because a point evaluates the expected classification reward against its movement cost, randomization can change its best response and produce a classification outcome unavailable to any deterministic boundary.
Knowl 11 — Limits of randomization with zero-cost manipulation
theoretical result
In zero-manipulation-cost strategic classification, each point may move within a designated feasible region at no cost. If a randomized classifier drawn from a hypothesis class achieves zero risk on a distribution, then a deterministic classifier in that class also achieves zero risk. In particular, randomization cannot improve perfect separability in adversarial classification with zero-cost allowed moves.

Zero cost does not rule out a benefit from randomization on nonseparable data. For example, take five points in $\mathbb R^2$ with $x_0=(0,0)$ and labels $y_0=-1$ , $y_1=y_2=+1$ , and $y_3=y_4=-1$ , where $x_1=(1,1)$ , $x_2=(-1,1)$ , $x_3=(-1,-1)$ , and $x_4=(1,-1)$ . Points $x_1,\ldots,x_4$ are nonstrategic; point $x_0$ prefers $+1$ and can move at zero cost within $B=\{(a,b):a\in\{-2,2\},\ b\in[-2,1]\}$ . Every deterministic linear classifier has empirical risk at least $1/5$ , whereas the equal-probability mixture of $h_1(a,b)=2\mathbf 1\{4a+7b-2\ge0\}-1$ and $h_2(a,b)=2\mathbf 1\{-4a+7b-2\ge0\}-1$ has risk $1/10$ .

Coverage note — No substantial contributed result was omitted; proof details and the full geometric construction for the randomized-improvement example were left out because the stated results capture their contribution.

References

1.Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 6–25, 2021.
2.Emrah Akyol, Cedric Langbort, and Tamer Basar. Price of transparency in strategic machine learning. arXiv, pages arXiv–1610, 2016.
3.Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. In Advances in Neural Information Processing Systems, pages 1169–1177, 2013.
4.Pranjal Awasthi, Abhratanu Dutta, and Aravindan Vijayaraghavan. On robustness to adversarial examples and polynomial optimization. In Advances in Neural Information Processing Systems, pages 13737–13747, 2019.
5.Yahav Bechavod, Katrina Ligett, Zhiwei Steven Wu, and Juba Ziani. Causal feature discovery through strategic modification. arXiv preprint arXiv:2002.07024, 2020.
6.Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML’12, page 1467–1474, Madison, WI, USA, 2012. Omnipress. ISBN 9781450312851.
7.Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pages 387–402. Springer, 2013.
8.Mark Braverman and Sumegha Garg. The role of randomness and noise in strategic classification. In 1st Symposium on Foundations of Responsible Computing (FORC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
9.Michael Brü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.
10.Miles Bryan and Keystone Crossroads. Coronavirus unemployment benefits are high, putting workers and employers at odds. https://whyy.org/articles/coronavirus-unemployment-benefits-are-high-putting-workers-and-employers-at-odds/.
11.N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pages 39–57, 2017.
12.Yiling Chen, Chara Podimata, Ariel D. Procaccia, and Nisarg Shah. Strategyproof linear regression in high dimensions. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18, page 9–26, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450358293. doi: 10.1145/3219166.3219175. URL https://doi.org/10.1145/3219166.3219175.
13.Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers. Advances in Neural Information Processing Systems, 33, 2020.
14.Danielle Keats Citron and Frank A. Pasquale. The scored society: Due process for automated predictions. 2014.
15.COVID. Covid-19 testing overview. https://www.cdc.gov/coronavirus/2019-ncov/symptoms-testing/testing.html.
16.Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 230–241. Curran Associates, Inc., 2018.
17.Ofer Dekel, Felix Fischer, and Ariel D Procaccia. Incentive compatible regression learning. Journal of Computer and System Sciences, 76(8):759–777, 2010.
18.Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18, page 55–70, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450358293. doi: 10.1145/3219166.3219193. URL https://doi.org/10.1145/3219166.3219193.
19.Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu. Agnostic learning of monomials by halfspaces is hard. SIAM Journal on Computing, 41(6):1558–1590, 2012.
20.Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR 2015 : International Conference on Learning Representations 2015, 2015.
21.Bryce Goodman and Seth Flaxman. EU regulations on algorithmic decision-making and a “right to explanation”, 2016. URL http://arxiv.org/abs/1606.08813. Presented at 2016 ICML Workshop on Human Interpretability in Machine Learning (WHI 2016), New York, NY.
22.Aniko Hannak, Gary Soeller, David Lazer, Alan Mislove, and Christo Wilson. Measuring price discrimination and steering on e-commerce web sites. In Proceedings of the 2014 conference on internet measurement conference, pages 305–318, 2014.
23.Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS ’16, page 111–122, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450340571. doi: 10.1145/2840728.2840730. URL https://doi.org/10.1145/2840728.2840730.
24.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, 2019a.
25.Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* ’19, page 259–268, New York, NY, USA, 2019b. Association for Computing Machinery. ISBN 9781450361255. doi: 10.1145/3287560.3287597. URL https://doi.org/10.1145/3287560.3287597.
26.Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. 2018 IEEE Symposium on Security and Privacy (SP), pages 19–35, 2018.
27.Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 825–844, 2019.
28.Bo Li and Yevgeniy Vorobeychik. Feature cross-substitution in adversarial classification. In Advances in neural information processing systems, pages 2087–2095, 2014.
29.John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. arXiv, pages arXiv–1910, 2019.
30.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, FAT* ’19, page 230–239, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450361255. doi: 10.1145/3287560.3287576. URL https://doi.org/10.1145/3287560.3287576.
31.Mehryar Mohri and Andres Munoz. Revenue optimization against strategic buyers. In Advances in Neural Information Processing Systems, pages 2530–2538, 2015.
32.S. Moosavi-Dezfooli, A. Fawzi, O. Fawzi, and P. Frossard. Universal adversarial perturbations. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 86–94, 2017.
33.M. Mozaffari-Kermani, S. Sur-Kolay, A. Raghunathan, and N. K. Jha. Systematic poisoning attacks on and defenses for machine learning in healthcare. IEEE Journal of Biomedical and Health Informatics, 19(6):1893–1905, 2015.
34.Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
35.Parag A Pathak. What really matters in designing school choice mechanisms. Advances in Economics and Econometrics, 1:176–214, 2017.
36.Javier Perote and Juan Perote-Peña. Strategy-proof estimators for simple regression. Math. Soc. Sci., 47:153–176, 2004.
37.Alvin E Roth. What have we learned from market design? Innovations: Technology, Governance, Globalization, 3(1):119–147, 2008.
38.Benjamin I.P. Rubinstein, Blaine Nelson, Ling Huang, Anthony D. Joseph, Shing-hon Lau, Satish Rao, Nina Taft, and J. D. Tygar. Stealthy poisoning attacks on pca-based anomaly detectors. SIGMETRICS Perform. Eval. Rev., 37(2):73–74, October 2009. ISSN 0163-5999. doi: 10.1145/1639562.1639592. URL https://doi.org/10.1145/1639562.1639592.
39.Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
40.Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8676–8686, 2020.
41.Tearsheet. Gaming the system: Loan applicants are reverse engineering the online lending algorithms. https://tearsheet.co/data/gaming-the-system-online-loan-applicants-are-reverse-engineering-the-algorithms/.
42.Stratis Tsirtsis, Behzad Tabibian, Moein Khajehnejad, Adish Singla, Bernhard Schölkopf, and Manuel Gomez-Rodriguez. Optimal decision making under strategic behavior. arXiv preprint arXiv:1905.09239, 2019.
43.Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 10–19, 2019.
44.Arsenii Vanunts and Alexey Drutsa. Optimal pricing in repeated posted-price auctions with different patience of the seller and the buyer. In Advances in Neural Information Processing Systems, pages 939–951, 2019.
45.Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010.
46.Jane Williams and Bridget Haire. Why some people don’t want to take a covid-19 test. https://theconversation.com/why-some-people-dont-want-to-take-a-covid-19-test-141794.
47.Hanrui Zhang and Vincent Conitzer. Incentive-aware pac learning. AAAI 2021, 2021.
48.Hanrui Zhang, Yu Cheng, and Vincent Conitzer. Distinguishing distributions when samples are strategically transformed. In Advances in Neural Information Processing Systems, pages 3193–3201, 2019a.
49.Hanrui Zhang, Yu Cheng, and Vincent Conitzer. When samples are strategically selected. In International Conference on Machine Learning, pages 7345–7353, 2019b.

Citation

MLA

Sundaram, R., et al. “PAC-Learning for Strategic Classification”. arXiv, 2020, http://arxiv.org/abs/2012.03310v4.

APA

Sundaram, R., Vullikanti, A., Xu, H., & Yao, F. (2020). PAC-Learning for Strategic Classification. arXiv. http://arxiv.org/abs/2012.03310v4

Chicago

Sundaram, R., A. Vullikanti, H. Xu, and F. Yao. 2020. “PAC-Learning for Strategic Classification”. arXiv. http://arxiv.org/abs/2012.03310v4.

Harvard

Sundaram, R. et al. (2020) “PAC-Learning for Strategic Classification”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2012.03310v4.

Vancouver

1. Sundaram R, Vullikanti A, Xu H, Yao F (2020) PAC-Learning for Strategic Classification. arXiv

BibTeX

@article{sundaram2020pac,
  title = {PAC-Learning for Strategic Classification},
  author = {Sundaram, Ravi and Vullikanti, Anil and Xu, Haifeng and Yao, Fan},
  year = {2020},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2012.03310v4},
  eprint = {2012.03310}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

PAC-learning for Strategic Classification

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Strategic classification with heterogeneous preferences

Knowl 2 — Strategic VC-dimension

Knowl 3 — Agnostic PAC learning by strategic empirical risk minimization

Knowl 4 — Relationship between SVC and adversarial VC-dimension

Knowl 5 — Separable costs bound strategic VC-dimension

Knowl 6 — Exact SVC for linear classifiers with instance-invariant seminorm costs

Knowl 7 — Instance-wise costs can make linear SVC infinite

Knowl 8 — Polynomial-time SERM in two adversarial regimes

Knowl 9 — SERM is NP-hard just beyond the tractable regimes

Knowl 10 — Randomized linear classifiers can strictly improve strategic accuracy

Knowl 11 — Limits of randomization with zero-cost manipulation

References

Citation

BibTeX

Access the Paper