Strategic classification studies how a decision maker should choose a classifier when the agents being classified can adjust their features in response to it. In existing models, the classifier is the only instrument available to the decision maker, and therefore a feature that is predictive but easy to fake can only be down-weighted or discarded. However, in many settings the decision maker can also verify: lenders verify income, admissions offices check documents, and tax authorities audit returns. In this paper, we propose a model of strategic classification in which the firm jointly designs a linear classifier and an audit profile, which assigns to each fakeable feature a probability of detection and a penalty when caught. We show that under linear costs, the classifier affects the audit problem only through the distribution of gaming rents it induces, so that the joint design problem decomposes into the choice of a score rule and an audit allocation problem. We use this decomposition to characterize the optimal audit allocation, to identify when the allocation problem is tractable and when it is NP-hard (namely, when agents can game through overlapping features under an inspection cap), and to bound the regret of a firm that has to learn the rents by auditing. We further show that audit intensity is a quantity to be tuned rather than maximized: welfare is single-peaked in it, and a firm and a social planner disagree on the mix of detection and penalty that delivers a given level of deterrence. Notably, two populations with identical costs and causal structure can game in one domain and improve in the other, a difference that a cost-only model cannot account for. Together, our findings highlight that whether a feature is ``gameable'' depends on the institution's verification policy as much as on the feature itself.
Figures & tables
Figure 1: Robustness of the price-and-audit result to the three idealizations the model isolates, measured by the audit dividend (optimal welfare with audit minus the best cost-only design) in a fixed-seed heterogeneous Stackelberg simulation. (a) Audits that wrongly flag honest applicants at rate αp : firm value and welfare are single-peaked in audit intensity; the dotted line is the best cost-only design, the shaded areas are gaming mass and wrongful flags, and the firm’s optimum sits above the welfare optimum. (b) Magnitude-dependent detection with sensitivity 1/β : the dividend persists and fakes diversify from singleton (support-based regime, left) to multi-channel, collapsing only when detection is blind to large fakes (right). (c) Causal leakage ρ : the dividend is largest at pure fakeability and shrinks as faking the signal increasingly converts gamers into qualified agents, while the signal stays priced throughout.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
§ 4 agent
§ 5 firm
§ 6 comput.
§ 8 welfare
§ 9 tuning
Committed, observed, support-based audit
∙
∙
∙
∙
∙
(Lin)
Thm. 4.1 (last part), Lem. 4.2
Thm. 5.4
∙
∙
∙
(SC)
shared-coordinate mix
–
–
–
–
(W > 0)
∙
∙
∙
∙
∙
Finitely many types
–
–
∙
–
–
Continuum of rents or risk types
–
Thms. 5.1 , 5.3
–
Thm. 8.1
–
Appendix
Table 1: Which conditions are in force where. A dot means the condition is assumed in every result of that section.
Figure 2: Shared-coordinate mixing. On an active shared coordinate, convex costs create an interior improve/fake mix; audit changes the active support and can drop the fake coordinate discontinuously.
Figure 3: Audit-induced domain separation in a heterogeneous population. The classifier, costs, budgets, and causal structure are fixed. Low audit creates a dense gaming ridge on the acceptance boundary; high audit removes gaming and leaves honest improvement plus exclusion. The lower panels show that the behavioral split is governed by the deterrence product pΔ , and that changing audit moves the same classifier along a new TP/FP frontier.
Figure 4: Detection and punishment are behavioral substitutes but welfare complements. Along the frontier pΔ=D , deterrence is fixed; private firm value drifts toward maximal punishment, while social welfare peaks at an interior mix.
Figure 5: Diagnostic over-penalization trap in the scalar model. Accuracy and welfare peak at the deterrence-binding audit. Below that point, gamers enter; above that point, there are no additional gamers to deter and false positives begin to chill qualified agents.
Fraud can pose a challenge in many resource allocation domains, including social service delivery and credit provision. For example, agents may misreport private information in order to gain benefits or access to credit. To mitigate this, a principal can design strategic audits to verify claims and penalize misreporting. In this paper, we introduce a general model of audit policy design as a principal-agent game with multiple agents, where the principal commits to an audit policy, and agents collectively choose an equilibrium that minimizes the principal's utility. We examine both adaptive and non-adaptive settings, depending on whether the principal's policy can be responsive to the distribution of agent reports. Our work provides efficient algorithms for computing optimal audit policies in both settings and extends these results to a setting with limited audit budgets.
Strategic classification studies the problem where self-interested individuals or agents manipulate their response to obtain favorable decision outcomes made by classifiers, typically turning to dishonest actions when they are less costly than genuine efforts. Prior works have demonstrated a fundamental inability to get out of this conundrum by only focusing on the design of a classifier. We note that prior work also heavily focuses on either one-shot settings or repeated interaction with the same classifier. Real-world decision making is often multi-stage, involving a sequence of potentially different classifiers as an agent progresses. This paper introduces a sequential, stochastic, multi-stage model of strategic classification, by capturing how agents adapt their behavior, through improvement actions (enhancing both observable features and true attributes) and gaming actions (enhancing only observable features), over multiple levels of classification with increasing difficulty as well as reward. For each level, we adopt a selective classifier that can abstain from making a prediction at low confidence. Consequently, a positive (resp. negative) outcome leads to promotion (resp. demotion) of the agent to the next higher (resp. lower) level, while abstention keeps the agent at the same level. We fully characterize the agent's optimal instantaneous action under selective classifiers and compare the long-term properties and utility of the agent repeatedly following an optimal myopic policy of either no-improvement (never choose the improvement action) or no-gaming (never choose the gaming action). We further examine design principles over the sequence of classifiers that yield higher long-term utility for the latter policy, thereby effectively incentivizing genuine effort in the long run.
Ziyuan Huang, Lina Alkarmi, Mingyan Liu
Department of Electrical and Computer Engineering University of Michigan Ann Arbor, MI 48105
Humans facing algorithmic decision systems have been found to ``game'' them by altering their input data (at a cost to them) in order to favorably change the algorithmic outcomes they receive (at a cost to the algorithm). The growing literature on strategic classification seeks to develop robust machine learning algorithms that account for, and reduce, unwanted strategic behavior. A limitation of these existing works is that they assume the cost of strategic behavior to be fixed and independent of the classifier's decision. In practice, however, manipulation costs evolve and depend on past algorithmic decisions: today's decisions influence tomorrow's costs. This paper proposes and analyzes a two-stage robust optimization framework with a decision-dependent uncertainty set to capture such dependencies. We highlight that awareness of policy-dependent costs not only reduces uncertainty, but also better curtails gaming of the algorithmic system over time.
Sura Alhanouti, Güzin Bayraksan, Parinaz Naghizadeh
Department of Integrated Systems Engineering, The Ohio State University, Ohio, USA · Department of Industrial Engineering, Jordan University of Science and Technology, Irbid, Jordan · Department of Electrical and Computer Engineering, University of California, San Diego, USA