Abstract
In strategic classification, individuals may manipulate their features to obtain favorable outcomes from algorithmic decision-makers. While previous work assumes full knowledge of the agent's possible actions, this paper investigates robust decision-making under incomplete information. We prove that when a decision-maker only knows a subset of possible strategic actions, a linear decision rule is robustly optimal, maximizing utility in the worst-case scenario across all possible unknown actions.
Introduction
As algorithms increasingly govern high-stakes decisions like credit scoring and university admissions, the "right to explanation" has become a standard requirement. However, transparency allows individuals to strategically alter their behavior—a phenomenon known as "gaming the system." Traditional models of strategic classification assume the decision-maker perfectly understands the costs and actions available to agents. In practice, agents often discover novel ways to manipulate features that the algorithm designer never anticipated. This paper addresses this gap by seeking decision rules that are robust to such unforeseen strategic behaviors.
Problem Formulation
The authors frame the challenge as a robust contract design problem using a max-min optimization framework. The decision-maker designs a rule based on a known set of actions $A_d$. However, the agent may have access to a larger, unknown set of actions $A_a$.
A decision rule is defined as "robust optimal" if it maximizes the decision-maker's utility in the worst-case scenario across all possible action sets $A_a$ that contain the known set $A_d$. This approach ensures that the algorithm remains effective even if the agent employs tactics completely unknown to the designer.
The Robust Optimality of Linear Models
The central theoretical contribution of this work is the proof that linear models are not just simple, but optimally robust. Using the Hyperplane Separation Theorem, the authors demonstrate that for any non-linear decision rule, there exists a linear rule that performs at least as well in the worst-case scenario.
Geometrically, the proof shows that the agent's incentives and the decision-maker's utility can be represented as convex sets. A linear "separating hyperplane" can then be found that provides a robust lower bound on utility. This suggests that the complexity of non-linear models can actually be a liability; complex boundaries create "brittle" points that agents can exploit using unknown actions.
Illustrative Example: Student Evaluation
To ground these theoretical results, the authors present a "Student Evaluation" toy model. In this scenario, a teacher evaluates students based on exam scores ($x_1$) and homework scores ($x_2$).
The teacher knows students can "study" (improving both scores) or "copy" (improving only homework). However, a student might also "hire a tutor"—an action $a_0$ unknown to the teacher. The analysis shows that a simple linear grading scheme is more robust against the "tutor" tactic than a complex, non-linear grading curve that might over-index on specific feature combinations.
Computational Analysis and Tractability
While finding the absolute optimal linear rule is generally NP-hard, the authors identify several tractable cases. By linking strategic behavior to Distributionally Robust Optimization (DRO), they show that strategic manipulation can be treated as a form of uncertainty in the feature distribution. For specific settings, such as ellipsoidal feature spaces and quadratic utilities, the robust optimization problem can be solved efficiently as a Semi-Definite Program (SDP) using tools like the S-Lemma and Schur’s complement.
Conclusion
This research provides a powerful theoretical justification for the use of linear models in strategic environments. Beyond interpretability, linearity serves as a fundamental defense against unforeseen manipulation. Future work may move beyond the pessimistic "worst-case" framework toward Bayesian models or consider the impact of heterogeneous agents with diverse action sets.
Reference: Tang, W., Ho, C.-J., & Liu, Y. (2021). Linear Models are Robust Optimal Under Strategic Behavior. Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS).
Summary updated