# One-Shot Strategic Classification Under Unknown Costs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 39 references that are in the map.
- First posted on arXiv 5 Nov 2023.

## Builds on (most cited first, 26 of 26)

- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [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)
- [On the Value of Out-of-Distribution Testing: An Example of Goodhart's Law](https://mlsanity.com/paper/2005.09241/) (2020)
- [Domain-Adjusted Regression or: ERM May Already Learn Features Sufficient for Out-of-Distribution Generalization](https://mlsanity.com/paper/2202.06856/) (2022)
- [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021)
- [Stochastic optimization with decision-dependent distributions](https://mlsanity.com/paper/2011.11173/) (2020)
- [Strategic Classification Made Practical](https://mlsanity.com/paper/2103.01826/) (2021)
- [PAC-Learning for Strategic Classification](https://mlsanity.com/paper/2012.03310/) (2020)
- [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020)
- [Information Discrepancy in Strategic Learning](https://mlsanity.com/paper/2103.01028/) (2021)
- [Alternative Microfoundations for Strategic Classification](https://mlsanity.com/paper/2106.12705/) (2021)
- [Anticipating Performativity by Predicting from Predictions](https://mlsanity.com/paper/2208.07331/) (2022)
- [Generalized Strategic Classification and the Case of Aligned Incentives](https://mlsanity.com/paper/2202.04357/) (2022)
- [An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization](https://mlsanity.com/paper/2102.13128/) (2021)
- [Strategic Classification under Unknown Personalized Manipulation](https://mlsanity.com/paper/2305.16501/) (2023)
- [Over-Optimization of Academic Publishing Metrics: Observing Goodhart's Law in Action](https://mlsanity.com/paper/1809.07841/) (2018)
- [Learning Losses for Strategic Classification](https://mlsanity.com/paper/2203.13421/) (2022)
- [Plug-in Performative Optimization](https://mlsanity.com/paper/2305.18728/) (2023)
- [Linear Classifiers that Encourage Constructive Adaptation](https://mlsanity.com/paper/2011.00355/) (2020)
- [(Almost) Provable Error Bounds Under Distribution Shift via Disagreement Discrepancy](https://mlsanity.com/paper/2306.00312/) (2023)
- [Strategic Classification with Graph Neural Networks](https://mlsanity.com/paper/2205.15765/) (2022)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)

## Built on by (most cited first, 13 of 13)

- [Classification Under Strategic Self-Selection](https://mlsanity.com/paper/2402.15274/) (2024)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [Incentive-Aware Machine Learning; Robustness, Fairness, Improvement & Causality](https://mlsanity.com/paper/2505.05211/) (2025)
- [Strategic Classification with Randomised Classifiers](https://mlsanity.com/paper/2502.01313/) (2025)
- [Strategic Classification with Non-Linear Classifiers](https://mlsanity.com/paper/2505.23443/) (2025)
- [Adversaries With Incentives: A Strategic Alternative to Adversarial Robustness](https://mlsanity.com/paper/2406.11458/) (2024)
- [Practical Performative Policy Learning with Strategic Agents](https://mlsanity.com/paper/2412.01344/) (2024)
- [Learning Classifiers That Induce Markets](https://mlsanity.com/paper/2502.20012/) (2025)
- [Strategic PAC Learnability via Geometric Definability](https://mlsanity.com/paper/2605.13426/) (2026)
- [Off-Policy Evaluation with Strategic Agents via Local Disclosure](https://mlsanity.com/paper/2606.07308/) (2026)
- [Ambiguous Strategic Classification](https://mlsanity.com/paper/2606.10137/) (2026)
- [Non-Linear Strategic Classification Made Practical](https://mlsanity.com/paper/2606.28204/) (2026)
- [Robust Strategic Classification under Decision-Dependent Cost Uncertainty](https://mlsanity.com/paper/2606.30136/) (2026)

## Abstract (arXiv)

The goal of strategic classification is to learn decision rules which are robust to strategic input manipulation. Earlier works assume that these responses are known; while some recent works handle unknown responses, they exclusively study online settings with repeated model deployments. But there are many domainsunicodex2014particularly in public policy, a common motivating use caseunicodex2014where multiple deployments are infeasible, or where even one bad round is unacceptable. To address this gap, we initiate the formal study of one-shot strategic classification under unknown responses, which requires committing to a single classifier once. Focusing on uncertainty in the users' cost function, we begin by proving that for a broad class of costs, even a small mis-estimation of the true cost can entail trivial accuracy in the worst case. In light of this, we frame the task as a minimax problem, aiming to minimize worst-case risk over an uncertainty set of costs. We design efficient algorithms for both the full-batch and stochastic settings, which we prove converge (offline) to the minimax solution at the rate of tildeO(T^-frac12). Our analysis reveals important structure stemming from strategic responses, particularly the value of dual norm regularization with respect to the cost function.