# strategic_classification_made_practical__5fd5f331.pdf

Strategic Classification Made Practical

Sagi Levanon 1 Nir Rosenfeld 1

Strategic classification regards the problem of learning in settings where users can strategically modify their features to improve outcomes. This setting applies broadly and has received much recent attention. But despite its practical significance, work in this space has so far been predominantly theoretical. In this paper we present a learning framework for strategic classification that is practical. Our approach directly minimizes the strategic empirical risk, achieved by differentiating through the strategic response of users. This provides flexibility that allows us to extend beyond the original problem formulation and towards more realistic learning scenarios. A series of experiments demonstrates the effectiveness of our approach on various learning settings.

1. Introduction

Across a multitude of domains from loan approval to online dating to hiring and admissions predictive machine learning models are becoming imperative for informing decisions that affect the lives of humans. But when people benefit from certain predictive outcomes, they are prone to act strategically to improve those outcomes. This has raised awareness as to the idea that standard learning algorithms may not be robust to such behavior, and there is a growing recognition as to the prevalence of this phenomena. Given the breadth of domains in which strategic user behavior is likely, practical tools for learning in strategic settings are of considerable importance.

In this paper we study practical aspects of learning in the setting of strategic classification (Br uckner & Scheffer, 2011; Hardt et al., 2016). In this problem, users respond to a published classifier by strategically modifying their features (at some cost) to improve their predicted outcomes. As a concrete example, consider a bank offering loans. The

1Department of Computer Science, Technion - Israel Institute of Technology. Correspondence to: Nir Rosenfeld <nirr@cs.technion.ac.il>.

Proceedings of the 38 th International Conference on Machine Learning, PMLR 139, 2021. Copyright 2021 by the author(s).

bank would like to approve a loan only if it is likely to be returned, and to aid in decision-making, the bank trains a classifier to predict loan returns. Applicants, however, would like their requests to be approved regardless of their actual credibility. To promote their interests, they can modify their applications (at some cost) to best align with the bank s classification rule. From the bank s perspective, such modifications can invalidate model predictions, and the primary goal in strategic classification is to design learning algorithms that are robust to this form of gaming .

Note that gaming is caused by the model itself, indirectly through how it shapes user incentives, and to its detriment. In this sense, strategic classification exemplifies how machine learning can be amenable to Goodhart s Law, a principle in policymaking stating that when a measure becomes a target, it ceases to be a good measure . Strategic classification thus succinctly captures a natural form of tension that arises between a learning-based system and its users. There has been much recent work on this topic, studying aspects such as generalization (Sundaram et al., 2020; Zhang & Conitzer, 2021), equilibrium and dynamics (Perdomo et al., 2020; Brown et al., 2020; Izzo et al., 2021; Miller et al., 2021), online learning (Dong et al., 2018; Chen et al., 2019; Ahmadi et al., 2020), causality and decision outcomes (Kleinberg & Raghavan, 2019; Rosenfeld et al., 2020; Shavit et al., 2020; Bechavod et al., 2020; Miller et al., 2020), transparency (Ghalme et al., 2021; Bechavod et al., 2021), and social perspectives (Hu et al., 2019; Milli et al., 2019; Chen et al., 2020).

But despite this flurry of recent work, algorithms for strategic classification are not in widespread use. The key reason for this is that work in this space has been predominantly theoretical. This has several practical implications. First, for mathematical tractability, strong assumptions are made (e.g., that the cost function is fixed and known). But the robustness of these methods to violations of their assumptions is not well understood. Second, methods tend to be crafted for very particular learning settings, and do not easily extend beyond the narrow context in which they are originally studied. Third, currently available algorithms lag far behind recent advances in machine learning methodology; they are prone to issues of scale, expressivity, and runtime, and lack the flexibility and modularity that current approaches readily provide (e.g., the ability to seamlessly add a layer or

Strategic Classification Made Practical

change the loss function). Combined, the above limitations indicate a clear need for an approach to learning in strategic classification that is effective and practical. Our work aims to take a first step towards addressing this need.

The core idea of our approach is to encode into the learning objective a response mapping that models how users respond to a given classification rule. By anticipating how inputs will be strategically modified under a given model, our approach optimizes directly for predictive performance under strategic behavior. We refer to this as strategic empirical risk minimization, or SERM. The challenge in optimizing the SERM objective is that models of user response typically involve an argmax operator, which can be nondifferentiable and even discontinuous. Our solution is to replace the argmax operator with a differentiable proxy, and for this we draw on recent advances in differentiable optimization solvers (Amos & Kolter, 2017; Djolonga & Krause, 2017; Agrawal et al., 2019a;b; Berthet et al., 2020; Tan et al., 2020; Agrawal & Boyd, 2020) and adapt them to our purpose. The resulting strategic response layer provides the main building-block of our framework.

Using the flexibility our framework provides, we propose and showcase multiple ways in which the framework can extend beyond the original formulation of strategic classification and towards more realistic learning scenarios. We make use of the modular nature of our approach and the flexibility it provides to explore various extensions aimed at addressing potential practical concerns. These include: supporting complex predictive models (e.g., recursive neural networks), supporting structured cost functions (e.g., constraining movement to a manifold), and relaxing the assumption of a fixed and known cost function (we handle adjustable and unknown costs).

The primary goal in strategic classification is to learn strategically-robust predictive models, but several works have raised concern as to the adverse social outcomes this may entail (Milli et al., 2019; Hu et al., 2019; Chen et al., 2020). This may not be surprising given that learning focuses entirely on optimizing predictive accuracy. To address these concerns, here we argue for a broader perspective that considers the trade-off between system and user interests. Borrowing from welfare economics, we take the perspective of a social planner tasked with balancing between these interests, and show how our approach can extend to target any operating point along the pareto front. To do this, we cast strategic classification as a problem of model selection, and propose novel forms of regularization that promote favorable social outcomes for various notions of social good . Because strategic classification is not a zero-sum game, the incentives of the system and of its users are not entirely antagonistic. As we show, this permits much social benefit to be gained at only a small cost in accuracy.

In summary, our paper makes the following contributions:

Practical framework. We propose a novel learning framework for strategic classification that is practical, effective, and flexible. Our approach allows to differentiate through strategic user responses, thus permitting end-to-end training.

Flexible modeling. We show how the flexibility of our approach allows for learning in diverse strategic settings. We effectively apply our approach to multiple such settings of practical interest.

Socially-aware learning. We propose several forms of regularization that encourage learned models to promote favorable social outcomes. By capitalizing on certain structural aspects of the problem, our regularization effectively balances between system and user interests.

We conduct a series of experiments demonstrating the effectiveness of our approach. With respect to the above points, each of our experiments is designed to study a different practical aspect of learning. The experiments cover a range of learning environments using real and synthetic data. Our results show that learning in strategic classification can be practical, effective, and socially responsible.

One of our main goals in this paper is to motivate and support future empirical research on strategic classification, Towards this end, we make publicly available a code repository with a flexible implementation of our approach, designed to support a wide range of strategic learning settings. Code can be found at https://github.com/ Sagi Levanon1/scmp.

2. Related Work

The literature on strategic classification is growing at a rapid pace. Various formulations of the problem were studied in earlier works (Br uckner & Scheffer, 2009; Br uckner et al., 2012; Großhans et al., 2013), but most recent works adopt the core setup of Hardt et al. (2016), as we do here. Research in this space has mostly been oriented towards theory, with recent work introducing notions similar to SERM and extending PAC theory to this setting (Sundaram et al., 2020; Zhang & Conitzer, 2021). We complement these by placing emphasis on practical aspects of learning.

Several papers consider the social impacts of strategic classification. Milli et al. (2019) study the social burden imposed by optimizing for accuracy. Chen et al. (2020) study the connection between strategically-aware learning and recourse. Hu et al. (2019) focus on fairness and show how classifiers can induce inequitable modification costs that affect utility. Our work ties these together, providing means to control

Strategic Classification Made Practical

the tradeoff between classifier s accuracy and the social outcomes it induces through regularization (see Sec. 3.4).

A parallel line of work studies how learned models affect actual (rather than predictive) outcomes. Some works analyze how models should promote users to invest effort effectively (Kleinberg & Raghavan, 2019; Alon et al., 2020), while others tie learning to the underlying casual mechanisms of the environment (Perdomo et al., 2020; Bechavod et al., 2020; Shavit et al., 2020; Miller et al., 2020). We remain within the original, purely predictive problem formulation, but view the extension of our approach to such settings to be intriguing as future work.

Learning setup. Denote by x X Rd features representing user attributes (e.g., a loan application profile), and by y Y = { 1, 1} their corresponding labels (e.g., loan returned or not). Let p(x, y) be a joint distribution over nonstrategic features and labels. The primary goal in learning is to find a classifier h : X Y from a class H that achieves high expected accuracy. For this, we assume access to a sample set S = {(xi, yi)}m i=1 sampled i.i.d. from p(x, y), on which we train. At test time, however, h is evaluated on data that is prone to modification by users. In strategic classification, users modify their features using the response mapping:

h(x) argmax x X h(x ) c(x, x ) (1)

where c is a known cost function. Test data includes pairs ( h(x), y) where (x, y) p, and the goal in learning is to optimize predictive accuracy under this induced distribution.

As is common, the classifiers we consider will be based on score functions f : X R via the decision rule hf(x) = sign(f(x)), and learning will be concerned with optimizing over a class of parametrized score functions F. We write f to mean hf , and for clarity, omit the notational dependence of the classifier hf on f when clear from context.

Game-theoretic formulation. Strategic classification can be formulated as a Stackelberg game between two players the system and a population of users. First, the system learns from S a classifier h. Then, given h, users respond via h. The payoffs are:

System: P[y = h( h(x))], (2)

Users: E[h( h(x)) c(x, h(x))] (3)

Payoff to the system (Eq. (2)) is the probability of classifying manipulated points correctly. Payoff to the users (as a collective) is their expected utility (Eq. (3)), for which as defined in Eq. (1) is a best-response.

3.1. Strategic Empirical Risk Minimization

A na ıve approach would be to train a classifier to predict well on the (non-manipulated) input data, and use it at test time on manipulated data. The caveat in this approach is that strategic behavior causes a discrepancy between the (marginal) input distributions at train and test time. Strategic classification therefore introduces a form of distribution shift (Quionero-Candela et al., 2009), but with the unique property that shift is determined by the predictive model itself, albeit indirectly through its effect on user responses.

Our approach will be to account for this shift by directly optimizing for the induced distribution. Noting that the system s payoff in Eq. (2) can be rewritten as 1 E[1{y = h( h(x))}], we set our objective to the empirical loss over the strategically-modified training set:

i=1 L( f(xi), yi, f) + λR(f) (4)

where L(z, y, f) = 1{y = hf(z)} and R is an optional regularizer. In practice we replace L with a tractable surrogate (e.g., binary cross-entropy), and we will return to the role of regularization in Sec. 3.4. We refer to optimizing Eq. (4) as strategic empirical risk minimization (SERM). Note that f plays a dual role in the objective: it determines how inputs are modified (via f) and how predictions are made on those modified inputs (via hf).

3.2. Differentiating through strategic responses

A natural way to approach the optimization of Eq. (4) is using gradient methods. The challenge in this approach is that is an argmax operator and can therefore be nondifferentiable. Our solution to this will be to use a differentiable proxy for , drawing inspiration from recent advances in differentibale optimization solvers. Such solvers map parametrized optimization problems to their (approximately) optimal solutions in a manner that is amenable to differentiation, and so can be used as optimization layers integrated into neural architectures.

Our approach will be to implement the response mapping as a differentiable optimization layer. In particular, we make use of convex optimization layers (Agrawal et al., 2019a), but since we seek to maximize, we will construct concave layers. A concave optimization layer g(θ) maps concave optimization problem instances to their argmax: the input to the layer, θ, defines the parameters (and hence the instance) of a template optimization problem, and the output of the layer is the solution under this parameterization. In our model, g will play the role of , and θ will include features x and the learnable parameters of f.

The response mapping as defined in Eq. (1) is not concave, and to apply concave optimization, we construct a

Strategic Classification Made Practical

concave proxy, denoted , as follows. To begin, assume for simplicity that h is linear, i.e., hw(x) = sign fw(x) with fw(x) = w x + b. Next, since sign is discontinuous, we replace it with a smooth sigmoid σ of the following form:

(τ 1z + 1)2 + 1 1

(τ 1z 1)2 + 1

Here τ is a temperature parameter: as τ decreases, σ approaches sign. Our particular choice of sigmoid follows from the fact that σ can be written as a sum of convex and concave functions. This motivates our final step, which is to apply the convex-concave procedure (CCP) (Yuille & Rangarajan, 2003). CCP is an approach to solving convexconcave optimization problems by iterating through a sequence of concave-relaxed problems, a process that guarantees convergence to local maxima. We focus on convex costs (e.g., linear or quadratic) so that CCP can be applied to the entire response function.1 Using CCP, we obtain reliable concave proxies of responses at each input. This gives us our differentiable proxy of the response mapping, which we refer to as a strategic response layer, defined as:

(x) = argmax x X CCP(σ (w x + b)) c(x, x ) (5)

Here CCP denotes the concave proxy obtained at the last iteration of the procedure.

To compute the forward pass, we run the CCP procedure using any standard off-shelf convex solver, and compute the argmax w.r.t. the final proxy.2 For the backward pass, we plug the final proxy into the differentiable convex solver of Agrawal et al. (2019a) to get gradients for w.r.t. w, b.

3.3. Extensions

3.3.1. NONLINEAR CLASSIFIERS

The concave solver can handle only score functions f that are linear in the optimization variables. But f need not be linear in the input features x; rather, it can be linear in any high-dimensional representation of the inputs, z = φ(x), z Z, such as those obtained from the final hidden layers of neural networks. This holds as long as both f and c are defined over this representation (i.e., points move in representation-space).3 The response mapping becomes:

(x) = argmax z Z σ(w z + b) c(φ(x), z ) (6)

More generally, f must be linear in variables over which the cost function c is defined. For example, if c applies only to

1Most of the literature considers convex costs (and linear classifiers). This includes the experimental setting of Hardt et al. (2016). 2There are many such tools available, and for reasonably-sized inputs, the computation overhead is small. 3Cost over representations are sensible, for example, when latent dimensions correspond to meaningful and manipulable realworld properties (e.g., Chen et al. (2016)).

a subset of the original features (for example, if only some features are manipulable), then f must be linear those features, but can be non-linear in all other features. Concretely, if x = (xmanip, xnon) where xmanip Rd1 and xnon Rd2 are the manipulable and non-manipulable features, respectively, then our framework supports the following non-linear representational structure:

(x) = argmax x Rd1 σ(w x +v φ(xnon)+b) c(xmanip, x )

3.3.2. FLEXIBLE COSTS

The core setting of strategic classification assumes costs are fixed. But in some settings, it is reasonable to assume that the system has some control over the cost function.4 We model this as allowing the system to modify an initial cost function c0 to some other cost c C from the class C, with this incurring a penalty of r(c0, c). The goal is now to jointly learn the classifier and the modified cost. Denoting by c f the response mapping for classifier f and cost function c, we can extend the learning objective as follows:

min c C min f F

i=1 L( c f(xi), yi, f) + r(c0, c) (7)

By utilizing its flexibility in choosing c, in this setting the system has the capacity to obtain better predictive performance than when optimizing the objective in Eq. (4).

3.3.3. UNKNOWN COSTS

Strategic classification assumes that the cost function is known, but this may not hold in practice. Here we consider a setting in which the system does not know the true cost c , but has a reasonable estimate c0. We model the system as believing that c lies in some set C C which includes c0 as well as nearby points, and which we view as a design parameter chosen by the learner. To learn in this setting, we propose a worst-case approach in which the system aims to perform well simultaneously on all c C. We propose the following minmax objective:

min f F max c C

i=1 L( c f(xi), yi, f) (8)

3.3.4. MOVING ON A MANIFOLD

The Manifold Hypothesis is a convention stating that highdimensional data tend to lie on or near a low-dimensional manifold. Typically the manifold is unknown; but even if it

4For example, consider a bank offering loans, and assume one of the features is the number of credit cards a user has. If the bank itself issues credit cards, then by determining policies related to credit cards (e.g., eligibility criteria, commissions, rates), the bank achieves some control over costs.

Strategic Classification Made Practical

is known, common cost functions tend to permit arbitrary movement and so cannot account for this structure. Here we show how our approach can incorporate (approximate) manifold constraints into learning. We begin by learning a manifold bundle (M, T) composed of a manifold model M and a tangent function T(x) that returns the subspace tangent to M at x.5 Since tangents T(x) are linear objects that provide a first-order approximation to the manifold at x, our approach is to add them as linear constraints to the optimization of the response mapping (i.e., the argmax in is taken over x T(x)). This ensure points move only on the tangent, thus approximating movement on the manifold.

3.4. Regularizing for social good

Our discussion of strategic classification thus far has been focused on a single objective: predicting accurately in the face of strategic gaming. This promotes a clear interest of the system, but neglects to account for the effects of learning users. Returning to our loans example, note that any predictor inevitably determines the degree of recourse, defined as the ability of users that are denied a service (e.g., a loan) to take reasonable action to reverse this decision (Ustun et al., 2019; Gupta et al., 2019; Joshi et al., 2019; Chen et al., 2020; Karimi et al., 2020b). Recourse is clearly beneficial to users, but in many cases, its facilitation is also beneficial to the system (for discussion see Ustun et al. (2019); Venkatasubramanian & Alfano (2020); Karimi et al. (2020a)).

In this section we show how our framework can be used to train models that are both accurate and promote favorable social outcomes. Relying on the observation that different models can induce very different social outcomes (Heidari et al., 2019), we cast learning as a problem of model selection, where the selection criterion reflects some notion of social good (e.g., recourse). Model selection is implemented through regularization and below we present novel forms of data-dependent regularizers R(f; S) targeting various notions of social good from the literature.

Intuitively, we expect regularization to be useful because strategic classification is not a zero-sum game. In other words, predictive models that provide similar payoff to the system may differ considerably in their payoff to users; we argue that the system has the freedom, as well as the responsibility, to carefully choose between these. Viewing learning from the perspective of a social planner interested in balancing between system and user interests, our regularization approach provides the means to achieve good balance. Varying the amount of regularization λ provides solutions along the Pareto front, with λ = 0 corresponding to the strategic classification equilibrium in Eq. (2).

5Many tools exist for learning bundles; e.g., Rifai et al. (2011a).

Expected utility. Since the payoff to users in Eq. (3) is given by their gained utility, u (x) = h( (x)) c(x, (x)), a straightforward notion of social good is their expected utility, E[u (x)]. Note that is a best-response but it is utility-optimal relative to h, and it is easy to construct an example showing that under the accuracy-optimal predictor utility can be arbitrarily low.6 To encourage models that provide users with high utility, we set:

Rutil(f; S) =

i=1 u (xi) (9)

and plug into the learning objective in (4), where in practice we again replace with and optimize as in Sec. 3.2.

Social burden. In their paper on the social cost of strategic classification, Milli et al. (2019) study social burden, defined to be the minimum cost a positively-labeled user must incur in order to be classified correctly. Within our framework, we can regularize for social burden using:

Rburden(f; S) = X

i:yi=1 min x :f(x ) 0 c(x, x ) (10)

which we can also implement as a convex optimization layer for linear f and convex c (the constraint is linear in x, w).

Recourse. Recourse refers to the capacity of a user who is denied a service to restore approval through reasonable action (in our case, low-cost feature modification). Since is a best-response, we say a user with h(x) = 1 is granted recourse if h( h(x)) = 1. The random variable negating this condition is 1{h(x) = 1 h( h(x)) = 1}, and we regularize using its smoothed approximation:

Rrecourse(f; S) =

i=1 sig ( f(x)) sig ( f( f(x)))

Where sig(z) = 1 1+e z is the standard sigmoid function. We calculate this regularization term using the same CCP approach on f(x), and once again in practice use instead of in training.

4. Experiments

In this section we empirically demonstrate the utility and flexibility of our approach on a diverse set of tasks and settings. Our goal is to demonstrate how our framework supports learning in settings that extend beyond the basic setting of strategic classification, and each experiment extends

6 Consider d = 1, with points ( ϵ, 1) and (ϵ, 1). Let c(x, x ) = |x x |. The classifier h(x) = 1{x 2} causes all positive points (and only positive points) to move. The payoff to negative points is 1 and the payoff to positive points is 1+ϵ.

Strategic Classification Made Practical

0.0 0.2 0.4 0.6 0.8 1.0 mixing parameter (γ)

Linear model on spam data

Benchmark SERM (linear) Blind (linear) Hardt et al. (2016)

1 2 3 4 5 6 suffix length

RNN on financial distress

Benchmark SERM (RNN) Blind (RNN)

fin. distress fraud spam

Accuracy for various datasets and cost scales

Benchmark SERM Blind

Figure 1. A comparison of our SERM approach to a strategy-blind baseline across multiple datasets, predictive models, and settings. Left: A reproduction of the setting of Hardt et al. (2016) on the spam dataset with mixed linear-quadratic cost. Center: Learning RNNs for financial distress time-series data. Right: Comparing across multiple datasets and degrees of gaming (controlled by cost scale t).

the core setting of Hardt et al. (2016) in a way that targets a certain aspect of practical concern. The Appendix includes further details, additional experiments, and illustrations.

Experimental setup. Across all experiments we use four real datasets: (i) spam7, which includes features describing users of a large social network, some of which are spammers (used originally in Hardt et al. (2016)); (ii) credit8, which includes features describing credit card spending patterns, and labels indicating default on payment (we use the version from Ustun et al. (2019)); (iii) fraud9, which includes credit card transactions that are either genuine or fraudulent (Dal Pozzolo et al., 2015); and (iv) financial distress10, which includes time-series data describing businesses over time along with labels indicating their level of financial distress and whether they have gone bankrupt. All datasets include features that describe users and relate to tasks in which users have incentive to obtain positive predictive outcomes. Some experiments use synthetic environments, described below.

We compare our approach (SERM) to a strategy-blind baseline that falsely assumes points do not move, achieved by training on the same model class but using standard, non-strategic ERM. When appropriate, we also compare to the strategic algorithm of Hardt et al. (2016), and to other context-specific variants of our approach (e.g., na ıve or oracle models). All models train on non-strategic data, but are evaluated on strategic data. As a benchmark, we use the strategy-blind model evaluated on non-strategic data (i.e., where points do not move).

7Data can be obtained from the authors of Costa et al. (2014). 8https://github.com/ustunb/ actionable-recourse

9https://www.kaggle.com/mlg-ulb/ creditcardfraud

10https://www.kaggle.com/shebrahimi/ financial-distress

Our focus is mostly on linear classifiers as these are naturally interpretable and hence justify the form of strategic behavior considered in strategic classification. For time-series data, such as in experiment in Sec. 4.3, we use recursive neural networks (RNN). For optimizing our approach we use Adam with randomized batches and early stopping (most runs converged after at most 7 epochs). User responses were simulated using from Eq. (1) with τ = 1 for training and τ = 0.2 for evaluation. Tolerance for CCP convergence was set to 0.01 (most attempts converged after at most 5 iterations). All methods use a 60-20-20 data split, and results are averaged over multiple random splits.

4.1. Core setting

Our first experiment begins with a reproduction of the experimental setting of Hardt et al. (2016). They use the spam dataset and consider linear-separable cost functions cv lin(x, x ) = max{0, v (x x)} with a specific hand-coded v Rd. Their algorithm only supports separable costs, and for linear-separable costs, returns a linear classifier. Linear costs, however, are unstable under evaluation since points can move at zero cost whenever v (x x) 0.11 Hence, they train with cv lin, but evaluate on a mixture cost:

cmix(x, x ; γ, v) = (1 γ) cv lin(x, x ) + γ cquad(x, x )

where cquad = x x 2 2 and γ (0, 1] (they use γ {0.1, 0.3}). Our approach supports general convex costs and so is able to learn using the right cost function (i.e., that is used in evaluation) for any γ.

11Linear costs are unstable at test time in the following way (see Hardt et al. (2016), Fig. 2 caption): if f is not precisely parallel to the cost vector v (i.e., f(x) = v x + b for some b, where c(x, x) = max{0, v (x x)}), then since any movement parallel to v is free, any x can move at zero cost to some x for which f(x) > 0 (and so all modified points are classified positively).

Strategic Classification Made Practical

0.0 0.2 0.4 0.6 0.8 1.0 utility

Expected utility tradeoff

Benchmark SERM

0.0 0.5 1.0 1.5 2.0

social burden (decreasing)

Social burden tradeoff

Benchmark SERM

0.6 0.7 0.8 0.9 1.0 recourse

Recourse tradeoff

Benchmark SERM

Figure 2. Trade-off curves of accuracy vs. various measures of social good: expected utility, social burden, and recourse. Points correspond to varying degrees of regularization (λ). For all measures, mild regularization improves social outcomes at little or no cost to accuracy.

Figure 1 (left) shows performance for increasing γ. Benchmark accuracy on non-strategic data is 81%, but once strategic movement is permitted, performance of the strategyblind model drops to 54% (data is balanced so chance = %50). The algorithm of Hardt et al. (2016) anticipates strategic behavior but (wrongly) assumes costs are linear. Accuracy for γ 0 improves to some extent ( 69%), but remains far below the benchmark. However, as γ increases, performance quickly drops to 50%. In contrast, by correctly anticipating strategic behavior, SERM restores accuracy almost in full for γ 0.2 ( 80%).

Next, we evaluate our method on additional datasets, focusing on quadratic cost (as it does not require hand-coded parameters), and varying the degree of gaming by scaling the cost by a factor of t {0.5, 1, 2}. Figure 1 (right) compares the performance of SERM to the strategy-blind baseline. As can be seen, SERM outperforms the blind model by a significant margin and closely matches the nonstrategic benchmark for all datasets and degrees of gaming.

4.2. Social good regularization

We evaluate our approach of regularizing for social good (Sec. 3.4) on credit, which has been used in a recent paper on recourse by Ustun et al. (2019). Here we study how accuracy and social good trade-off under SERM by varying the amount of regularization λ. Figure 2 shows results for expected utility (left), social burden (center), and recourse (right). Each point in the plots corresponds to a model trained with a different λ. Results show that all three measures of social good exhibit a super-linear tradeoff curve: with mild regularization, a large increase in social good is obtained at little or no cost to accuracy. This highlights three interrelated points: that incentives in strategic classification are not fully discordant; that multiple models can achieve high accuracy; and that of these, our approach to model selection through regularization is effective at selecting models that promote favorable social outcomes.

4.3. Beyond linear models

We apply our approach to time-series data in financial distress and for our predictive model we use non-linear recurrent neural networks (RNN) . Each example in the dataset describes a firm over t time steps using a sequence of feature vectors x = (x(1), . . . , x(t)), where x(k) Rd

describes the firm at time k t and t varies across examples (1 t 14). Labels determine whether the firm has gone bankrupt at time t, and we assume users can modify features only at this final timepoint x(t). This mimics a setting in which the history of the firm is fixed, but its features at the time of arbitration can be manipulated (at some cost). We implement f as a fully-connected RNN with layers:

h(i) = ϕ(Wx(i) + V h(i 1) + a)

where model parameters W, V, a are tied across layers and activations ϕ are sigmoidal for all layers but the last, which is used for prediction. We set the embedded dimension to 10. Plugging into Eq. (1), the response mapping becomes:

(x) = argmax x X sign(w x + v h(t 1) + b) c(x(t), x )

with quadratic cost. This is a special case of Sec. 3.3.1 with φ(x) = (x(t), h(t 1)). Since f is linear in x and c is convex in x , our CCP approach can be applied (Sec. 3.2).

We experiment with varying history lengths by taking suffixes of fixed size k of each x. Figure 1 (center) shows results for increasing suffix lengths k. As can be seen, SERM outperforms a blind RNN by roughly 15% for all k and nearly matches the non-strategic benchmark for k 2.

4.4. Beyond oracle cost functions

In this section we move beyond the assumption of a fixed and known ( oracle ) cost function and study the extensions presented in Sec. 3.3. We use stylized 2D synthetic data that allows us to visually illustrate how our approach behaves in these extended settings. In each setting we compare SERM to appropriate na ıve and oracle baselines, specified below.

Strategic Classification Made Practical

Flexibility

Manifold constraints

benchmark benchmark

Figure 3. An illustrations of various extensions of the role of the cost function c. (Left) Flexibility: cost is linear (arrows show direction) and is initially v0, but the system can invest effort to change it. Learning produces a cost ˆv that is near the optimal v , with which SERM achieves near-optimal accuracy. (Center) Robustness: Cost is quadratic (circles show diameter of maximal movement), but the system has only an estimate v0 of the true cost v . Learning aims to be minmax-optimal with respect to all costs v V near v0 (ring shows the set V ). SERM again learns a near-optimal classifier. (Right) Manifold constraints: Points are allowed to move only on the quadratic manifold that is unknown (and hence not encoded in c). Our approach is to first learn the manifold, and then use derived tangents as constraints in optimizing . This approximates movement within the manifold and allows SERM to learn well.

Flexible cost functions. In this setting we assume that the system can modify an initial cost to some extent. Data is generated by a mixture of two narrow MVN distributions with means µ = [ 0.5, 0] (for y = 1) and µ = [0.5, 0] (y = 1) and diagonal covariances with Σ11 = 0.1 and Σ22 = 1. We use linear-separable cost cv lin (for stability we mix using γ = 0.005) and set the initial cost to v0 = [0.5, 0.5]. The learner has flexibility to choose any v V = {v : v v0 2}. For a na ıve baseline we consider a model that does not modify the cost, i.e., uses v = v0. The oracle baseline uses the optimal v = [2, 0] V .

To learn with flexible costs, we use the approach presented in Sec. 3.3.2 and jointly optimize model parameters w, b and cost parameters v. Results are shown in Figure 3 (left). If no strategic movement is allowed, then the optimal linear classifier having w = [1, 0], b = 0 achieves 100% (non-strategic) accuracy. However, with strategic movement under v0, the strategically-optimal classifier has weights w = [0.5, 0.5], b = 1. These are indeed the weights learned by the na ıve baseline, which achieves 0.72% accuracy. However, for v = [1, 0], the optimal classifier has w = [1, 0], b = 1, and an oracle baseline that has v = [1, 0] learns these weights and achieves 100%. Our flexible approach learns a near-optimal cost (ˆv = [2.3, 0.6]) along with the corresponding optimal model, achieving 97% accuracy.

Unknown cost functions. In this setting we assume that points move according to a ground-truth cost function that is unknown, and that the system has only an rough estimate of this cost. Data is generated by a mixture of two symmetric MVN distributions with means µ = [ 0.6, 0] (for y = 1) and µ = [0.6, 0] (y = 1) and diagonal covariances Σ11 = Σ22 = 0.1. We use an a-symmetric quadratic cost in which

dimensions can differ in scale, cv quad(x, x ) = Pd i=1 vi(xi x i)2, parameterized by v Rd. The ground-truth cost is set to v = (0.5, 0.5) and the initial estimate to v0 = (2, 2). Here the oracle baseline learns using v , and na ıve baseline learns under the false assumption that v0 = v .

To learn under an unknown cost, we use the robust minmax approach presented in Sec. 3.3.3 and train a predictor f to be minmax-optimal w.r.t. a belief set V , which we set to V = {v R2 : v0 v 1.7} (note that v V ). In this setting optimization is simplified since it suffices to maximize v over the reduced set {vmin, vmax} V , where in our case vmin = [0.3, 0.3] and vmax = [3.7, 3.7]. Figure 3 (center) illustrates the results of learning in this setting. The benchmark on non-strategic data is 100%, as is the performance of the oracle model on strategic data. The na ıve model obtains 74% accuracy using v0. SERM optimized using the minmax objective achieves 91% accuracy.

Manifold constraints. In this setting we work with a cost function is known and fixed, but assume that points can move only within a low-dimensional manifold that is unknown to the system. We use a 1D manifold that satisfies x2 = x2 1 and generate data points x = (x1, x2) using x1 U([ 5, 5]) and set x2 according to the manifold constraints. Labels are y = sign(x1) and the cost is quadratic.

To learn under unknown manifold constraints, we follow the approach outlined in Sec. 3.3.4, where in the response function the (unknown) manifold constraints are approximated using (estimated) tangent constraints. Here, manifold tangents have a close form solution, but for completeness we pursue a more general approach and learn them. In particular, we learn the manifold using a contractive autoencoder

Strategic Classification Made Practical

(CAE) (Rifai et al., 2011b) with 2 stacked hidden layers of width 20 and sigmoidal activations. CAEs minimize reconstruction error under a regularization term that penalizes Jacobian absolute values. Balancing between these two forces encourages learned embeddings that permit movement only in directions that are useful for reconstruction, i.e., along the manifold. Jacobians also provide manifold tangents, and we compute these as proposed for manifold tangent classifiers (MTC) in Rifai et al. (2011a).

Figure 3 (right) shows results for this setting. The problem is separable and so optimal non-strategic accuracy is 100%. A na ıve baseline which does not account for manifold constraints wrongly assumes points can move freely across the x1-axis and places all weight on this axis. This false assumption reduces accuracy to 52% much lower than that of a blind baseline, which achieves 89%. Our SERM approach augmented with MTC tangents over an estimated CAE manifold reaches 98% accuracy.

5. Conclusions

In this paper we proposed a practical approach to learning in strategic classification. By differentiating through user responses, our approach allows for effective and efficient learning in diverse settings. Key to our approach were differentiable optimization solvers; we are hopeful that future advances in this field could be utilized within our framework to support more elaborate forms of user responses. Strategic classification has so far been mostly studied under a theoretical lens; our work takes a first step towards making learning practical, with the aim of promoting discussion amongst practitioners, applied researchers, and those interested in social aspects of learning. Our approach to regularization serves as a reminder that strategic classification is a game for two players, and that learning can, and should, aid in promoting the interests of all parties involved. We believe that a responsible approach to applied strategic classification can be beneficial to both systems and the users they serve.

Agrawal, A. and Boyd, S. Differentiating through loglog convex programs. ar Xiv preprint ar Xiv:2004.12553, 2020.

Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Z. Differentiable convex optimization layers. In Advances in neural information processing systems, pp. 9562 9574, 2019a.

Agrawal, A., Barratt, S., Boyd, S., Busseti, E., and Moursi, W. M. Differentiating through a cone program. ar Xiv preprint ar Xiv:1904.09043, 2019b.

Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K. The

strategic perceptron. Available at https://arxiv. org/abs/2008.01710, 2020.

Alon, T., Dobson, M., Procaccia, A. D., Talgam-Cohen, I., and Tucker-Foltz, J. Multiagent evaluation mechanisms. In The Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI), pp. 1774 1781, 2020.

Amos, B. and Kolter, J. Z. Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning, pp. 136 145, 2017.

Bechavod, Y., Ligett, K., Wu, Z. S., and Ziani, J. Causal feature discovery through strategic modification. Available at https://arxiv.org/abs/2002.07024, 2020.

Bechavod, Y., Podimata, C., Wu, Z. S., and Ziani, J. Information discrepancy in strategic learning. Available at https://arxiv.org/pdf/2103.01028. pdf, 2021.

Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J.- P., and Bach, F. Learning with differentiable perturbed optimizers. ar Xiv preprint ar Xiv:2002.08676, 2020.

Brown, G., Hod, S., and Kalemaj, I. Performative prediction in a stateful world. ar Xiv preprint ar Xiv:2011.03885, 2020.

Br uckner, M. and Scheffer, T. Nash equilibria of static prediction games. In Advances in neural information processing systems, pp. 171 179, 2009.

Br uckner, M. and Scheffer, T. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 547 555, 2011.

Br uckner, M., Kanzow, C., and Scheffer, T. Static prediction games for adversarial learning problems. The Journal of Machine Learning Research, 13(1):2617 2654, 2012.

Chen, X., Duan, Y., Houthooft, R., Schulman, J., Sutskever, I., and Abbeel, P. Infogan: Interpretable representation learning by information maximizing generative adversarial nets. In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL https://proceedings. neurips.cc/paper/2016/file/ 7c9d0b1f96aebd7b5eca8c3edaa19ebb-Paper. pdf.

Chen, Y., Liu, Y., and Podimata, C. Learning strategy-aware linear classifiers. ar Xiv preprint ar Xiv:1911.04004, 2019.

Chen, Y., Wang, J., and Liu, Y. Strategic recourse in linear classification. ar Xiv preprint ar Xiv:2011.00355, 2020.

Strategic Classification Made Practical

Costa, H., Merschmann, L. H., Barth, F., and Benevenuto, F. Pollution, bad-mouthing, and local marketing: The underground of location-based social networks. Information Sciences, 279:123 137, 2014.

Dal Pozzolo, A., Caelen, O., Johnson, R. A., and Bontempi, G. Calibrating probability with undersampling for unbalanced classification. In 2015 IEEE Symposium Series on Computational Intelligence, pp. 159 166. IEEE, 2015.

Djolonga, J. and Krause, A. Differentiable learning of submodular models. In Advances in Neural Information Processing Systems, pp. 1013 1023, 2017.

Dong, J., Roth, A., Schutzman, Z., Waggoner, B., and Wu, Z. S. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC), pp. 55 70, 2018.

Ghalme, G., Nair, V., Eilat, I., Talgam-Cohen, I., and Rosenfeld, N. Strategic classification in the dark. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.

Großhans, M., Sawade, C., Br uckner, M., and Scheffer, T. Bayesian games for adversarial regression problems. In International Conference on Machine Learning, pp. 55 63, 2013.

Gupta, V., Nokhiz, P., Roy, C. D., and Venkatasubramanian, S. Equalizing recourse across groups. ar Xiv preprint ar Xiv:1909.03166, 2019.

Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pp. 111 122, 2016.

Heidari, H., Nanda, V., and Gummadi, K. On the long-term impact of algorithmic decision policies: Effort unfairness and feature segregation through social learning. In 36th International Conference on Machine Learning, pp. 2692 2701, 2019.

Hu, L., Immorlica, N., and Vaughan, J. W. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*), pp. 259 268, 2019.

Izzo, Z., Ying, L., and Zou, J. How to learn when data reacts to your model: performative gradient descent. ar Xiv preprint ar Xiv:2102.07698, 2021.

Joshi, S., Koyejo, O., Vijitbenjaronk, W., Kim, B., and Ghosh, J. Towards realistic individual recourse and actionable explanations in black-box decision making systems. ar Xiv preprint ar Xiv:1907.09615, 2019.

Karimi, A.-H., Barthe, G., Sch olkopf, B., and Valera, I. A survey of algorithmic recourse: definitions, formulations, solutions, and prospects. ar Xiv preprint ar Xiv:2010.04050, 2020a.

Karimi, A.-H., von K ugelgen, J., Sch olkopf, B., and Valera, I. Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. Advances in Neural Information Processing Systems, 33, 2020b.

Kleinberg, J. M. and Raghavan, M. How do classifiers induce agents to invest effort strategically? In Proceedings of the 2019 ACM Conference on Economics and Computation, (EC), pp. 825 844, 2019.

Miller, J., Milli, S., and Hardt, M. Strategic classification is causal modeling in disguise. In International Conference on Machine Learning, pp. 6917 6926. PMLR, 2020.

Miller, J., Perdomo, J. C., and Zrnic, T. Outside the echo chamber: Optimizing the performative risk. ar Xiv preprint ar Xiv:2102.08570, 2021.

Milli, S., Miller, J., Dragan, A. D., and Hardt, M. The social cost of strategic classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*), pp. 230 239, 2019.

Perdomo, J. C., Zrnic, T., Mendler-D unner, C., and Hardt, M. Performative prediction. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.

Quionero-Candela, J., Sugiyama, M., Schwaighofer, A., and Lawrence, N. D. Dataset shift in machine learning. The MIT Press, 2009.

Rifai, S., Dauphin, Y. N., Vincent, P., Bengio, Y., and Muller, X. The manifold tangent classifier. Advances in neural information processing systems, 24:2294 2302, 2011a.

Rifai, S., Vincent, P., Muller, X., Glorot, X., and Bengio, Y. Contractive auto-encoders: Explicit invariance during feature extraction. In Icml, 2011b.

Rosenfeld, N., Hilgard, A., Ravindranath, S. S., and Parkes, D. C. From predictions to decisions: Using lookahead regularization. Advances in Neural Information Processing Systems, 33, 2020.

Shavit, Y., Edelman, B., and Axelrod, B. Causal strategic linear regression. In International Conference on Machine Learning, pp. 8676 8686. PMLR, 2020.

Shen, X., Diamond, S., Gu, Y., and Boyd, S. Disciplined convex-concave programming. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 1009 1014. IEEE, 2016.

Strategic Classification Made Practical

Sundaram, R., Vullikanti, A., Xu, H., and Yao, F. Paclearning for strategic classification. ar Xiv preprint ar Xiv:2012.03310, 2020.

Tan, Y., Terekhov, D., and Delong, A. Learning linear programs from optimal decisions. Advances in Neural Information Processing Systems, 33, 2020.

Ustun, B., Spangher, A., and Liu, Y. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 10 19, 2019.

Venkatasubramanian, S. and Alfano, M. The philosophical basis of algorithmic recourse. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 284 293, 2020.

Yuille, A. L. and Rangarajan, A. The concave-convex procedure. Neural computation, 15(4):915 936, 2003.

Zhang, H. and Conitzer, V. Incentive-aware pac learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.