In traditional machine learning, we treat data points as passive observers. However, when machine learning models are deployed in high-stakes social domains—such as credit scoring, college admissions, or content recommendation—the data points become active agents. These agents strategically alter their features to obtain a more favorable classification.
To protect a model against this kind of gaming, the foundational framework of strategic classification, introduced by Moritz Hardt et al., models the interaction as a Stackelberg game. The institution (the principal) deploys a classifier, and the individuals (the agents) respond by modifying their features to maximize their utility. An agent will modify their true features $x$ to manipulated features $x'$ if the benefit of receiving a positive classification outweighs the cost of the modification:
$$\text{Utility} = \text{Gain}(\text{Classifier}(x')) - \text{Cost}(x \to x')$$
If the principal knows the exact function $\text{Cost}(x \to x')$, they can perfectly anticipate how agents will react and construct a classifier that remains accurate even after agents game the system.
But here lies the fatal flaw: in the real world, a principal rarely knows an agent's private manipulation costs. As highlighted by Sagi Levanon et al. and Saba Ahmadi et al., these cost functions are latent, complex, and highly variable across individuals. If a bank assumes it takes significant effort to artificially boost a credit score, but a new online service makes it cheap and effortless, the bank's classifier will be flooded with unexpected, low-quality applicants.
To build systems that withstand real-world deployment, recent research shifts away from assuming perfect cost information, focusing instead on how to learn or remain robust under manipulation cost uncertainty.
The Core Challenge: Why Cost Misestimation Breaks Models
When a classifier is built on a flawed assumption of what it costs agents to change their features, its predictive power degrades rapidly.
Imagine a linear classifier separating qualified and unqualified applicants. If the principal shifts the decision boundary to account for an assumed manipulation cost $c$, they expect only qualified applicants to find the effort worthwhile. However, if the actual cost is much lower than $c$, unqualified agents will easily cross the boundary. Conversely, if the cost is higher, even qualified agents might be discouraged from updating their features.
This problem is compounded by population heterogeneity. As Tianrun Zhao et al. and Yiling Chen et al. point out, agents do not possess a uniform manipulation budget or capability. Treating a diverse population as a monolith leads to severe estimation errors.
Furthermore, this uncertainty introduces critical fairness issues. Vijay Keswani et al. demonstrate that the real-world social and economic effort required to alter features often varies by demographic group. When a decision-maker lacks accurate cost functions for different groups, they risk deploying a model that places an unequal "social burden" on marginalized communities, forcing them to expend far more effort to achieve the same classification outcomes.
Learning Costs through Revealed Preferences
If the cost function is unknown, how can a principal optimize a classifier? One powerful approach is to learn the cost function over time by observing how agents react to different models—a concept known in economics as revealed preferences.
In this setup, the principal treats the agents' behavioral responses as a feedback signal. Aaron Roth et al. formalized this as an online learning problem. By deploying a sequence of classifiers and observing only the resulting manipulated data, the principal can iteratively deduce the boundaries of the agents' private cost constraints. The authors proved that even without knowing the costs upfront, a learner can achieve low Stackelberg regret, eventually converging to the optimal strategic classifier.
[Deploy Classifier] ---> [Agents Respond based on Private Costs]
^ |
| v
[Update Cost Estimate] <--- [Observe Manipulated Data Distribution]
This online framework has been expanded to handle more realistic, messy environments. For instance, Tianrun Zhao et al. developed algorithms for settings where the principal only receives partial feedback (e.g., only learning the true label if an applicant is accepted) and faces noisy observations. By continuously probing the environment, the principal implicitly maps out the latent utility functions of a heterogeneous population.
Robustness in One Shot: Dual Norm Regularization
Probing the population over multiple rounds is a luxury that many real-world systems cannot afford. If a medical board or a university admissions office gets only one shot to deploy a model, they cannot afford to learn from trial and error. How do you design a strategic classifier when costs are completely unknown and you cannot experiment?
Elan Rosenfeld et al. solved this problem by framing it as a robust optimization challenge. Instead of trying to guess the exact cost function, the authors assumed the cost function belongs to a broad family of norms, but its specific parameters remain unknown.
The mathematical intuition behind their solution relies on a beautiful duality: the maximum vulnerability of a linear classifier to feature manipulation is directly bounded by the mathematical dual norm of its weight vector.
If an agent manipulates their features $x \to x + \Delta$, subject to some cost constraint $\|\Delta\| \le \delta$, the change in the classifier's score is bounded by the dual norm of the weights, $\|w\|_*$. By applying strict dual norm regularization during training, the principal can systematically penalize the model's sensitivity to any potential feature shifts. The authors proved that this single-shot regularization strategy provides a distribution-free guarantee, ensuring the classifier remains robust against the worst-case scenario of unknown agent manipulation costs.
Beyond Classification: Incentives, Externalities, and Steering
The challenge of latent cost functions extends far beyond simple binary classification. It cuts across any system where a principal attempts to shape agent behavior through incentives.
- Content Recommendation: In recommendation systems, Itay Eilat et al. study how to incentivize content creators to produce diverse material. Because creators have highly individual, latent effort costs for changing their content style, recommendation algorithms must be designed to be strategically aware of these hidden trade-offs to avoid collapsing content variety.
- Contract Design: When designing contracts with safety inspections, Alireza Fallah et al. demonstrate that a principal faces deep uncertainty regarding an agent's operational capabilities and economic trade-offs, requiring mechanisms that balance monetary payouts with random audits to guarantee safety compliance.
- Market Externalities: In real-world settings, one agent's gaming behavior affects another's. Safwan Hossain et al. introduced externalities to strategic classification—such as when an agent's manipulation increases the audit risk for everyone else. They show that even when these complex social externality functions are entirely unknown, robust classifiers can still be learned using Probably Approximately Correct (PAC) frameworks.
- Agent Steering: Moving into dynamic environments, Jiawei Huang et al. look at how a mediator can "steer" a population of learning agents toward a social optimum (like resolving a coordination deadlock). Even when the mediator is completely blind to the internal learning rates and update rules of the agents, they show that reinforcement learning can resolve this model uncertainty through strategic interaction.
Whether through sequential learning or robust regularization, accounting for unknown manipulation costs transitions strategic classification from an elegant mathematical theory into a practical, resilient tool for engineering human-centric AI systems.
Key Foundational Work
Strategic Classification (2015) — contributed 1 concept elements to this direction.
Algorithmic rationality: adding cost of computation to game theory (2011) — contributed 1 concept elements to this direction.