# The Strategic Perceptron

arXiv: https://arxiv.org/abs/2008.01710 · HTML: https://mlsanity.com/paper/2008.01710/

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2020.

## Built on by (most cited first, 30 of 48)

- [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021)
- [Strategic Classification Made Practical](https://mlsanity.com/paper/2103.01826/) (2021)
- [Who Leads and Who Follows in Strategic Classification?](https://mlsanity.com/paper/2106.12529/) (2021)
- [Information Discrepancy in Strategic Learning](https://mlsanity.com/paper/2103.01028/) (2021)
- [Stateful Strategic Regression](https://mlsanity.com/paper/2106.03827/) (2021)
- [Causal Strategic Classification: A Tale of Two Shifts](https://mlsanity.com/paper/2302.06280/) (2023)
- [On classification of strategic agents who can both game and improve](https://mlsanity.com/paper/2203.00124/) (2022)
- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (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)
- [One-Shot Strategic Classification Under Unknown Costs](https://mlsanity.com/paper/2311.02761/) (2023)
- [Bayesian Strategic Classification](https://mlsanity.com/paper/2402.08758/) (2024)
- [Non-linear Welfare-Aware Strategic Learning](https://mlsanity.com/paper/2405.01810/) (2024)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [Automating Data Annotation under Strategic Human Agents: Risks and Potential Solutions](https://mlsanity.com/paper/2405.08027/) (2024)
- [The Double-Edged Sword of Behavioral Responses in Strategic Classification: Theory and User Studies](https://mlsanity.com/paper/2410.18066/) (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)
- [Setting Fair Incentives to Maximize Improvement](https://mlsanity.com/paper/2203.00134/) (2022)
- [Algorithmic Decision-Making under Agents with Persistent Improvement](https://mlsanity.com/paper/2405.01807/) (2024)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025)
- [How Strategic Agents Respond: Comparing Analytical Models with LLM-Generated Responses in Strategic Classification](https://mlsanity.com/paper/2501.16355/) (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)
- [Strategyproof Decision-Making in Panel Data Settings and Beyond](https://mlsanity.com/paper/2211.14236/) (2022)

## Abstract (arXiv)

The classical Perceptron algorithm provides a simple and elegant procedure for learning a linear classifier. In each step, the algorithm observes the sample's position and label and updates the current predictor accordingly if it makes a mistake. However, in presence of strategic agents that desire to be classified as positive and that are able to modify their position by a limited amount, the classifier may not be able to observe the true position of agents but rather a position where the agent pretends to be. Unlike the original setting with perfect knowledge of positions, in this situation the Perceptron algorithm fails to achieve its guarantees, and we illustrate examples with the predictor oscillating between two solutions forever, making an unbounded number of mistakes even though a perfect large-margin linear classifier exists. Our main contribution is providing a modified Perceptron-style algorithm which makes a bounded number of mistakes in presence of strategic agents with both ℓ2 and weighted ℓ1 manipulation costs. In our baseline model, knowledge of the manipulation costs (i.e., the extent to which an agent may manipulate) is assumed. In our most general model, we relax this assumption and provide an algorithm which learns and refines both the classifier and its cost estimates to achieve good mistake bounds even when manipulation costs are unknown.