# On classification of strategic agents who can both game and improve arXiv: https://arxiv.org/abs/2203.00124 ยท HTML: https://mlsanity.com/paper/2203.00124/ ## Key facts - Cited by 27 papers in the map (data through 14 Oct 2026). - Builds on 12 of its 23 references that are in the map. - First posted on arXiv 28 Feb 2022. ## Builds on (most cited first, 12 of 12) - [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015) - [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017) - [The Social Cost of Strategic Classification](https://mlsanity.com/paper/1808.08460/) (2018) - [Strategic Classification is Causal Modeling in Disguise](https://mlsanity.com/paper/1910.10362/) (2019) - [How Do Classifiers Induce Agents To Invest Effort Strategically?](https://mlsanity.com/paper/1807.05307/) (2018) - [The Disparate Effects of Strategic Manipulation](https://mlsanity.com/paper/1808.08646/) (2018) - [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020) - [Maximizing Welfare with Incentive-Aware Evaluation Mechanisms](https://mlsanity.com/paper/2011.01956/) (2020) - [The Role of Randomness and Noise in Strategic Classification](https://mlsanity.com/paper/2005.08377/) (2020) - [Stateful Strategic Regression](https://mlsanity.com/paper/2106.03827/) (2021) - [Gaming Helps! Learning from Strategic Interactions in Natural Dynamics](https://mlsanity.com/paper/2002.07024/) (2020) - [Optimal Common Contract with Heterogeneous Agents](https://mlsanity.com/paper/1911.04146/) (2019) ## Built on by (most cited first, 27 of 27) - [Causal Strategic Classification: A Tale of Two Shifts](https://mlsanity.com/paper/2302.06280/) (2023) - [Strategic Classification under Unknown Personalized Manipulation](https://mlsanity.com/paper/2305.16501/) (2023) - [Fundamental Bounds on Online Strategic Classification](https://mlsanity.com/paper/2302.12355/) (2023) - [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024) - [Strategic Classification with Graph Neural Networks](https://mlsanity.com/paper/2205.15765/) (2022) - [Clickbait vs. Quality: How Engagement-Based Optimization Shapes the Content Landscape in Online Platforms](https://mlsanity.com/paper/2401.09804/) (2024) - [Non-linear Welfare-Aware Strategic Learning](https://mlsanity.com/paper/2405.01810/) (2024) - [Sequential Strategic Screening](https://mlsanity.com/paper/2301.13397/) (2023) - [Learning under Imitative Strategic Behavior with Unforeseeable Outcomes](https://mlsanity.com/paper/2405.01797/) (2024) - [Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification](https://mlsanity.com/paper/2407.11619/) (2024) - [Incentivizing Desirable Effort Profiles in Strategic Classification: The Role of Causality and Uncertainty](https://mlsanity.com/paper/2502.06749/) (2025) - [Algorithmic Decision-Making under Agents with Persistent Improvement](https://mlsanity.com/paper/2405.01807/) (2024) - [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025) - [Incentive-Aware Machine Learning; Robustness, Fairness, Improvement & Causality](https://mlsanity.com/paper/2505.05211/) (2025) - [Should Decision-Makers Reveal Classifiers in Online Strategic Classification?](https://mlsanity.com/paper/2506.01936/) (2025) - [The Limitations of Model Retraining in the Face of Performativity](https://mlsanity.com/paper/2408.08499/) (2024) - [Policy Learning with Competing Agents](https://mlsanity.com/paper/2204.01884/) (2022) - [Operationalizing Counterfactual Metrics: Incentives, Ranking, and Information Asymmetry](https://mlsanity.com/paper/2305.14595/) (2023) - [Anticipating Gaming to Incentivize Improvement: Guiding Agents in (Fair) Strategic Classification](https://mlsanity.com/paper/2505.05594/) (2025) - [Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning](https://mlsanity.com/paper/2506.05252/) (2025) - [The Disparate Effects of Partial Information in Bayesian Strategic Learning](https://mlsanity.com/paper/2506.00627/) (2025) - [Strategic Filtering for Content Moderation: Free Speech or Free of Distortion?](https://mlsanity.com/paper/2507.20061/) (2025) - [Multi-Level Strategic Classification: Incentivizing Improvement through Promotion and Relegation Dynamics](https://mlsanity.com/paper/2602.11439/) (2026) - [Revealing Positive and Negative Role Models to Help People Make Good Decisions](https://mlsanity.com/paper/2603.02495/) (2026) - [On Randomized Algorithms in Online Strategic Classification](https://mlsanity.com/paper/2602.06257/) (2026) - [Sequential Strategic Classification with Multi-Stage Selective Classifiers](https://mlsanity.com/paper/2605.04202/) (2026) - [Linear Strategic Classification with Endogenous Improvements](https://mlsanity.com/paper/2606.01198/) (2026) ## Abstract (arXiv) In this work, we consider classification of agents who can both game and improve. For example, people wishing to get a loan may be able to take some actions that increase their perceived credit-worthiness and others that also increase their true credit-worthiness. A decision-maker would like to define a classification rule with few false-positives (does not give out many bad loans) while yielding many true positives (giving out many good loans), which includes encouraging agents to improve to become true positives if possible. We consider two models for this problem, a general discrete model and a linear model, and prove algorithmic, learning, and hardness results for each. For the general discrete model, we give an efficient algorithm for the problem of maximizing the number of true positives subject to no false positives, and show how to extend this to a partial-information learning setting. We also show hardness for the problem of maximizing the number of true positives subject to a nonzero bound on the number of false positives, and that this hardness holds even for a finite-point version of our linear model. We also show that maximizing the number of true positives subject to no false positive is NP-hard in our full linear model. We additionally provide an algorithm that determines whether there exists a linear classifier that classifies all agents accurately and causes all improvable agents to become qualified, and give additional results for low-dimensional data.