# paclearning_for_strategic_classification__b95ae733.pdf

Journal of Machine Learning Research 24 (2023) 1-38 Submitted 10/21; Revised 11/22; Published 6/23

PAC-learning for Strategic Classification

Ravi Sundaram r.sundaram@northeastern.edu Khoury College of Computer Science Northeastern University Boston, MA 02115, USA

Anil Vullikanti vsakumar@virginia.edu Department of Computer Science, Biocomplexity Institute University of Virginia Charlottesville, VA 22904, USA

Haifeng Xu haifengxu@uchicago.edu Department of Computer Science University of Chicago Chicago, IL 60637, USA

Fan Yao fy4bc@virginia.edu Department of Computer Science University of Virginia Charlottesville, VA 22904, USA

Editor: Vahab Mirrokni

The study of strategic or adversarial manipulation of testing data to fool a classifier has attracted much recent attention. Most previous works have focused on two extreme situations where any testing data point either is completely adversarial or always equally prefers the positive label. In this paper, we generalize both of these through a unified framework by considering strategic agents with heterogenous preferences, and introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. SVC provably generalizes the recent concept of adversarial VC-dimension (AVC) introduced by Cullina et al. (2018). We instantiate our framework for the fundamental strategic linear classification problem. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) its computational tractability by pinning down the complexity of the empirical risk minimization problem. Interestingly, the SVC of linear classifiers is always upper bounded by its standard VC-dimension. This characterization also strictly generalizes the AVC bound for linear classifiers in (Cullina et al., 2018). Finally, we briefly investigate the power of randomization in our strategic classification setup. We show that randomization may strictly increase the accuracy in general, but will not help in the special case of adversarial classification with zero-manipulation-cost.

Keywords: Strategic classification, PAC-learning, strategic VC-dimension, linear classifier, strategic empirical risk minimization

. Corresponding author; Work done while this author is at the University of Virginia. . Corresponding author

2023 Ravi Sundaram, Anil Vullikanti, Haifeng Xu and Fan Yao.

License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v24/21-1250.html.

Sundaram, Vullikanti, Xu and Yao

1. Introduction

In today s increasingly connected world, it is rare that an algorithm will act alone. When a machine learning algorithm is used to make predictions or decisions about others who have their own preferences over the learning outcomes, it is well known (e.g., Goodhart s law) that gaming behaviors may arise these have been observed in a variety of domains such as finance (Tearsheet), online retailing (Hannak et al., 2014), education (Hardt et al., 2016) as well as during the ongoing COVID-19 pandemic (Bryan and Crossroads; Williams and Haire). In the early months of the pandemic, simple decision rules were designed for COVID-19 testing (COVID) by the CDC. However, people had different preferences for getting tested. Those with work-from-home jobs and leave benefits preferred to get tested in order to know their true health status whereas some of the people with lower income, and without leave benefits preferred not to get tested with fears of losing their income (Williams and Haire). Policy makers sometimes prefer to make classification rules confidential (Citron and Pasquale, 2014) to mitigate such gaming. However, this is not fool-proof in general since the methods may be reverse engineered in some cases, and transparency of ML methods is sometimes mandated by law, e.g., (Goodman and Flaxman, 2016). Such concerns have led to a lot of interest in designing learning algorithms that are robust to strategic gaming behaviors of the data sources (Perote and Perote-Pe na, 2004; Dekel et al., 2010; Hardt et al., 2016; Chen et al., 2018; Dong et al., 2018; Cullina et al., 2018; Awasthi et al., 2019); the present work subscribes to this literature.

This paper focuses on the ubiquitous binary classification problem, and we look to design classification algorithms that are robust to gaming behaviors during the test phase. We study a strict generalization of the canonical classification setup that naturally incorporates data points preferences over classification outcomes (which leads to strategic behaviors as we will describe later). In particular, each data point is denoted as a tuple (x, y, r) where x X and y { 1, +1} are the feature and label, respectively (as in classic classification problems), and additionally, r R is a real number that describes how much this data point prefers label +1 over 1. Importantly, we allow r to be negative, meaning that the data point may prefer label 1. For instance, in the decision rules for COVID-19 testing, individuals who prefer to get tested have r > 0, while those who prefer not to be tested have r < 0. The magnitude |r| captures how strong their preferences are. For example, in the school choice matching market, students have heterogeneous preferences over universities (Pathak, 2017; Roth, 2008) and may manipulate their application materials during the admission process. Let set R R denote the set of all possible values that the preference value r may take. Obviously, the trivial singleton set R = {0} corresponds to the classic classification setup without any preferences. Another special case of R = {1} corresponds to the situation where all data points prefer label +1 equally. This is the strategic classification setting studied in several previous works (Hardt et al., 2016; Hu et al., 2019b; Miller et al., 2019). A third special case is R = { 1, 1}. This encompasses the classification under evasion attacks (Biggio et al., 2013; Goodfellow et al., 2015; Li and Vorobeychik, 2014; Cullina et al., 2018; Awasthi et al., 2019), where any test data point (x, y) prefers the opposite of its true label y, i.e., the adversarial assumption.

Our model considers any general preference set R. As we will show, this much richer set of preferences may sometimes make learning more difficult, both statistically and com-

PAC-learning for Strategic Classification

putationally, but not always. Like Hardt et al. (2016); Dong et al. (2018); Goodfellow et al. (2015); Cullina et al. (2018), our model assumes that manipulation is only possible to the data features and happens only during the test phase. Specifically, the true feature of the test data may be altered by the strategic data point. The cost of masking a true feature x to appear as a different feature z is captured by a cost function c(z; x). Therefore, the test data point s decision needs to balance the cost of altering feature and the reward of inducing its preferred label captured by r. As is standard in game-theoretic analysis, the test data point is assumed a rational decision maker and will choose to alter to the feature z that maximizes its quasi-linear utility [r I(h(z) = 1) c(z; x)]. This naturally gives rise to a Stackelberg game (Von Stackelberg, 2010). We aim to learn, from i.i.d. drawn (unaltered) training data, the optimal classifier h that minimizes the 0-1 classification loss, assuming any randomly drawn test data point (from the same distribution as testing data) will respond to h strategically. Notably, the data point s strategic behavior will not change its true label. Such behavior is referred to as strategic gaming, which crucially differs from strategic improvement studied recently (Kleinberg and Raghavan, 2019; Miller et al., 2019).

1.1 Overview of Our Results

The Strategic VC-Dimension. We introduce the novel notion of strategic VC-dimension SVC(H, R, c) which captures the learnability of any hypothesis class H when test data points strategic behaviors are induced by cost function c and preference values from any set R R.

We prove that any strategic classification problem is agnostic PAC learnable by the empirical risk minimization paradigm with O ϵ 2[d + log(1

δ))] samples, where d =SVC(H, R, c). Conceptually, this result illustrates that SVC correctly characterizes the learnability of the hypothesis class H in our strategic setup.

Our SVC notion generalizes the adversarial VC-dimension (AVC) introduced in (Cullina et al., 2018) for adversarial learning with evasion attacks. Formally, we prove that AVC equals precisely SVC(H, R, c) for R = { 1, 1} when data points are allowed to move within region {z; c(z; x) 1} in the adversarial learning setup. However, for general preference set R, SVC can be arbitrarily larger than both AVC and the standard VC dimension. Thus, complex strategic behaviors may indeed make the learning statistically more difficult. Interestingly, to our knowledge, this is the first time that adversarial learning and strategic learning are unified under the same PAC-learning framework.

We prove SVC(H, R, c) 2 for any H and R when c is any separable cost function (introduced by Hardt et al. (2016)). Invoking our sample complexity results above, this also recovers a main learnability result of (Hardt et al., 2016) and, moreover, generalizes their result to arbitrary agent preferences.

Strategic Linear Classification. As a case study, we instantiate our strategic classification framework in perhaps one of the most fundamental classification problems, linear classification. Here, features are in Rd linear space. We assume the cost function c(z; x) for any x is induced by arbitrary seminorms of the difference z x. We distinguish between

Sundaram, Vullikanti, Xu and Yao

two crucial situations: (1) instance-invariant cost function which means the cost of altering the feature x to x + is the same for any x; (2) instance-wise cost function which allows the cost from x to x + to be different for different x. Our results show that the more general instance-wise costs impose significantly more difficulties in terms of both statistical learnability and computational tractability.

Statistical Learnability. We prove that the SVC of linear classifiers is for instance-wise cost functions even when features are in R2; in contrast, the SVC is at most d+1 for any instance-invariant cost functions and any R when features are in Rd. This later result also strictly generalizes the AVC bound for linear classifiers proved in (Cullina et al., 2018), and illustrates an interesting conceptual message: though SVC can be significantly larger than AVC in general, extending from R = { 1, 1} to an arbitrary strategic preference set R does not affect the statistical learnability of strategic linear classification.

Computational Tractability. We show that the empirical risk minimization problem for linear classifier can be solved in polynomial time only when the strategic classification problem exhibits certain adversarial nature. Specifically, an instance is said to have adversarial preferences if all negative test points prefer label +1 (but possibly to different extents) and all positive test points prefer label 1. A strictly more relaxed situation has essentially adversarial preferences i.e., any negative test point prefers label +1 more than any positive test point. We show that for instanceinvariant cost functions, any essentially adversarial instance can be solved in polynomial time whereas for instance-wise cost functions, only adversarial instances can be solved in polynomial time. These positive results are essentially the best one can hope for. Indeed, we prove that the following situations, which goes slightly beyond the tractable cases above, are both NP-hard: (1) instance-invariant cost functions but general preferences; (2) instance-wise cost functions but essentially adversarial preferences.

Randomization in Strategic Classification. We examine the power and limits of randomization in our strategic classification setting. It is well-known that randomization does not improve classification accuracy in the non-strategic case (see, e.g., (Braverman and Garg, 2020)). We observe that this ceases to be true in strategic classification there are examples where randomized linear classifiers can achieve strictly better accuracy than any deterministic linear classifier.1 Interestingly, however, we prove that randomization does not improve accuracy for classification with zero-manipulation-cost adversaries, by leveraging the special properties of the cost function in adversarial classification.

1.2 Related Works

(Br uckner and Scheffer, 2011) is one of the first to consider the Stackelberg game formulation of strategic classification, motivated by spam filtering; however they do not study generalization bounds. Zhang and Conitzer (2021) provide the sample complexity result for

1. Similar result has been observed by Braverman and Garg (2020), but their work has focused on on one-dimensional feature space

PAC-learning for Strategic Classification

strategic PAC-learning under the homogeneous preference setting and in particular study the case under the incentive-compatibility constraints, i.e., subject to no data points will misreport features. Both works assume the positive labels are always and equally preferred. There has also been work on understanding the social implications of strategically robust classification (Akyol et al., 2016; Milli et al., 2019; Hu et al., 2019b); these works show that improving the learner s performance may lead to increased social burden and unfairness. Dong et al. (2018); Chen et al. (2020); Ahmadi et al. (2021) extend strategic linear classification to an online setting where the data points come in an online manner. These online learning setups do not have the notion of training and testing sets. Instead, all their data points are contaminated. Our setting however is in the more canonical PAClearning setup but with more general agent preferences and thus crucially differs from them in multiple aspects: (1) we assume access to uncontaminated training data whereas testing data are contaminated (like classic strategic classification setups as in (Hardt et al., 2016; Hu et al., 2019b; Zhang and Conitzer, 2021)); (2) data points in our setups have arbitrary preferences and manipulation cost functions whereas these online learning setups all assume homogeneous agent preferences and typically special class of cost functions like l2 distances (Ahmadi et al., 2021) or positive homogeneous functions (Dong et al., 2018). Finally, all these online setups have so far examined only linear classification whereas our strategic PAC learning framework is general albeit with linear classification as an important case study. To our knowledge, recent work by Tsirtsis et al. (2019) is the only work that considers heterogeneous data point preferences. However, their work focuses purely on the computational problem of computing the optimal classification policy. Moreover, their study a very different classification model with exponentially large discrete feature spaces, and thus their complexity results are not comparable to ours. All these aforementioned works, including the present work, consider gaming behaviors. A relevant but quite different line of recent works study strategic improvements where the manipulation does really change the inherent quality and labels (Kleinberg and Raghavan, 2019; Miller et al., 2019; Ustun et al., 2019; Bechavod et al., 2020; Shavit et al., 2020). The question there is mainly to design incentive mechanisms to encourage agents efforts or improvements. Most relevant to ours is perhaps the strategic classification model studied by Hardt et al. (2016) and Zhang and Conitzer (2021), where Hardt et al. (2016) formally formulated the strategic classification problem as a repeated Stackelberg game and Zhang and Conitzer (2021) studied the PAC-learning problem and tightly characterized the sample complexity via incentiveaware ERM . However, their model and results all assume homogeneous agent preferences, i.e., all agents equally prefer label +1. Our model strictly generalizes the model of (Hardt et al., 2016; Zhang and Conitzer, 2021) by allowing agents heterogeneous preferences over classification outcomes. Besides the modeling differences, the research questions we study are also quite different from (Hardt et al., 2016). Their positive results are derived under the assumption of separable cost functions or its variants, which appear too restrictive and somewhat unrealistic. For example, one consequence of separable cost functions is that for any two features x, z, the manipulation cost from either x to z or from z to x must be 0.2

2. A cost function c(z; x) is separable if there exists two functions c1, c2 : X R such that c(z; x) = max{c2(z) c1(x), 0}. Since c(x; x) = 0, we have c2(x) c1(x) for any x. Therefore, c2(x) + c2(z) c1(x) c1(z) 0. Consequently, either c2(x) c1(z) 0 or c2(z) c1(x) 0, yielding either c(z; x) = 0 or c(x; z) = 0.

Sundaram, Vullikanti, Xu and Yao

This appears unrealistic in reality. For example, a high-school student with true average math grade 80 and true average literature grade 95 is likely to incur cost if she/he wants to appear as 95 for math and 80 for literature, and vice versa. This is because different students are good at different aspects. Our model imposes less assumptions on the cost functions by allowing any cost functions induced by seminorms. Our characterization of SVC equaling at most 2 under separable cost functions implies the PAC-learnability result of (Hardt et al., 2016), which serves more as our case study. One of our main contribution is the study of the novel concept of SVC, which does not appear in previous works. Moreover, we study the efficient learnability of linear classifiers with cost functions induced by seminorms. This broad and natural class of cost functions is not separable, and thus the results of (Hardt et al., 2016) does not apply to this case. Our model also generalizes the setup of adversarial classification with evasion attacks, which has been studied in numerous applications, particularly deep learning models (Biggio et al., 2013, 2012; Li and Vorobeychik, 2014; Carlini and Wagner, 2017; Goodfellow et al., 2015; Jagielski et al., 2018; Moosavi-Dezfooli et al., 2017; Mozaffari-Kermani et al., 2015; Rubinstein et al., 2009); however, most of these works do not yield theoretical guarantees. Our work extends and strictly generalizes the recent work of (Cullina et al., 2018) through our more general concept of SVC and results on computational efficiency. In a different work, Awasthi et al. (2019) studied computationally efficient learning of linear classifiers in adversarial classification with l -norm-induced δ-ball for allowable adversarial moves. Our computational tractability results generalize their results to δ-ball induced by arbitrary seminorms.3

Strategic classification has been studied in other different settings or domains or for different purposes, including spam filtering (Br uckner and Scheffer, 2011), online learning (Dong et al., 2018; Chen et al., 2020), and understanding the social implications (Akyol et al., 2016; Milli et al., 2019; Hu et al., 2019b). A relevant but quite different line of recent works study strategic improvements (Kleinberg and Raghavan, 2019; Miller et al., 2019; Ustun et al., 2019; Bechavod et al., 2020; Shavit et al., 2020). Finally, going beyond classification, strategic behaviors in machine learning has received significant recent attentions, including in regression problems (Perote and Perote-Pe na, 2004; Dekel et al., 2010; Chen et al., 2018), distinguishing distributions (Zhang et al., 2019a,b), and learning for pricing (Amin et al., 2013; Mohri and Munoz, 2015; Vanunts and Drutsa, 2019). These works are similar in spirit to ours, but study a completely different set of problems using different techniques. Their results are not comparable to ours.

Basic Setup. We consider binary classification, where each data point is characterized by a tuple (x, y, r). Like classic classification setups, x X is the feature vector and y {+1, 1} is its label. The only difference of our setup from classic classification problems is the additional r R R, which is the data point s (positive or negative) preference/reward of being labeled as +1. The data point s reward for label 1 is, without loss of generality, normalized to be 0. A classifier is a mapping h : X {+1, 1}. Our model is essentially

3. (Awasthi et al., 2019) also studied computational tractability of learning other classes of classifiers, e.g., degree-2 polynomial threshold classifiers, which we do not consider.

PAC-learning for Strategic Classification

the same as that of (Hardt et al., 2016; Miller et al., 2019), except that the r in our model can be any real value from set R whereas the aforementioned works assume r = 1 for all data points. Notably, we also allow r to be negative, which means some data points prefer to be classified as label 1. This generalization is natural and very useful because it allows much richer agent preferences. For instance, it casts the adversarial/robust classification problem as a special case of our model as well (see discussions later). Intuitively, the set R captures the richness of agents preferences. As we will prove, how rich it is will affect both the statistical learnability and computational tractability of the learning problem.

Figure 1: Example illustration of our setup. The line is a linear classifier. Points x3, x4 have incentive to cross the boundary whereas x1, x2 do not. The dotted cycles contain all manipulated features which have moving cost exactly 1 and they can be different for different points (i.e., instance-wise costs).

The Strategic Manipulation of Test Data. We consider strategic behaviors during the test phase and assume that the training data is unaltered/uncontaminated. An illustration of the setup can be found in Figure 1. A generic test data point is denoted as (x, y, r). The test data point is strategic and may shift its feature to vector z with cost c(z; x) where c : X X R 0. In general, function c can be an arbitrary non-negative cost function. In our study of strategic linear classification, we assume the cost functions are induced by seminorms. We will consider the following two types of cost functions, with increasing generality.

1. Instance-invariant cost functions: A cost function c is instance-invariant if there is a common function l such that c(z; x) = l(z x) for any point (x, y, r).

2. Instance-wise cost functions: With instance-wise cost functions, each data point is allowed to possess its own loss function. To capture this situation, we need to augment each data point s representation from (x, y, r) to (x, y, r, l), where l is a function depending on x such that c(z; x) = l(z x) for some semi-norm l. For notational convenience, we often refer to function l associated with this data point as lx though we emphasize that this is a slight abuse of notation because lx is determined not just by the data point s feature x but rather by the data point itself.4

4. The only places where this notational discrepancy needs to be recognized are the proof of Theorem 10 and the second situation of Theorem 14, during which we will point out this to avoid confusion.

Sundaram, Vullikanti, Xu and Yao

Both cases have been considered in previous works. For instance, the separable cost function studied in (Hardt et al., 2016) is instance-wise, and the cost function induced by a seminorm as assumed by the main theorem of (Cullina et al., 2018) is instance-invariant. We shall prove later that the choice among these two types of cost functions will largely affect the efficient learnability of the problem. Given a classifier h, the strategic test data point (x, y, r) may shift its feature vector to z and would like to pick the best such z by solving the following optimization problem:

Data Point Best Response: c(x, r; h) = arg max z X I(h(z) = 1) r c(z; x) . (1)

where I(S) is the indicator function and [I(h(z) = 1) r c(z; x)] is the quasi-linear utility function of data point (x, y, r). We call c(x, r; h) the manipulated feature. When there are multiple best responses, we assume the data point may choose any best response and thus will adopt the standard worst-case analysis. Note that the test data s strategic behaviors do not change its true label. Such strategic gaming behaviors differ from strategic improvements (see (Miller et al., 2019) for more discussions on their differences). We also point out that the preference r is assumed to be known for any training data (though no need to be known for testing data). While this may appear a strong assumption at the first glance, we believe this parameter can be estimated in real applications (e.g., how much it matters to someone for being admitted to a university, for receiving a loan or for being tested COVID positive). An interesting future direction may be to understand how robust the strategic classifier is to the estimation error of r in the training data.

2.1 The Strategic Classification (Stra C) Problem

A Stra C problem is described by a hypothesis class H, the set of preferences R and a manipulation cost function c. We thus denote it as Stra C H, R, c . Adopting the standard statistical learning framework, the input to our learning task is n uncontaminated training data points (x1, y1, r1), , (xn, yn, rn) drawn independently and identically (i.i.d.) from distribution D. Given these training data, we look to learn a classifier h H which minimizes the basic 0-1 loss, defined as follows:

Strategic 0-1 Loss of classifier h :

Lc(h; D) = Pr (x,y,r) D

h( c(x, r; h)) = y) . (2)

Notably, the classifier h in the above loss definition takes the manipulated feature c(x, r; h)) as input and, nevertheless, looks to correctly predict the true label y. For notational convenience, we sometimes omit c when it is clear from the context and simply write (x, r; h) and L(h; D).

2.2 Notable Special Cases

Our strategic classification model generalizes several models studied in previous literature, which we now sketch.

Non-strategic classification. When R = {0} and c(z; x) > 0 for any x = z, our model degenerates to the standard non-strategic setting.

PAC-learning for Strategic Classification

Strategic classification with homogeneous preference. When R = {1}, our model degenerates to the strategic classification model studied in prior work (Hardt et al., 2016; Hu et al., 2019b; Milli et al., 2019) here all data points have the same incentive of being classified as +1.

Adversarial Classification. When R = {1, 1} (or {δ, δ},δ = 0), our model encompasses the adversarial classification problem (Cullina et al., 2018; Awasthi et al., 2019), where each data point can adversarially move to induce the opposite of its true label within the ball of radius 1 induced by cost function c. Our Proposition 6 provides formal evidence for this connection.

Generalized Adversarial Classification. An interesting generalization of the above adversarial classification setting is that r < 0 for all data points with true label +1 and r > 0 for all data points with true label 1. This captures the situation where each point has different power (decided by |r|) to play against the classifier. To our knowledge, this generalized setting has not been considered before. Our results yield new efficient statistical learnability and computational tractability for this setting.

3. VC-Dimension for Strategic Classification

In this section, we introduce the notion of strategic VC-dimension (SVC) and show that it properly captures the behaviors of a hypothesis class in the strategic setup introduced above. We then show the connection of SVC with previous studies on both strategic and adversarial learning. Before formally introducing SVC, we first define the shattering coefficients in strategic setups.

Definition 1 (Strategic Shattering Coefficients) The n-th shattering coefficient of any strategic classification problem Stra C H, R, c is defined as

σn(H, R, c) = max (x,r) X n Rn |{(h( c(x1, r1; h)), , h( c(xn, rn; h)) : h H}|,

where c(xi, ri; h) defined in Eq. (1) is a best response of data point (xi, yi, ri) to classifier h under cost function c.

That is, σn(H, R, c) captures the maximum number of classification behaviors/outcomes (among all choices of data points) that classifiers in H can possibly induce by using manipulated features as input. Like classic definition of shattering coefficient, the σn(H, R, c) here does not involve the labels of the data points at all. In contrast, in the shattering coefficient definition for adversarial VC-dimension of (Cullina et al., 2018), the max is allowed to be over data labels as well. This is an important difference compared to our setting. Given the definition of the strategic shattering coefficients, the definition of strategic VC-dimension is standard.

Definition 2 The Strategic VC-dimension (SVC) for strategic classification problem Stra C H, R, c is defined as

SVC(H, R, c) = sup{n N : σn(H, R, c) = 2n}. (3)

Sundaram, Vullikanti, Xu and Yao

We show that the SVC defined above correctly characterizes the learnability of any strategic classification problem Stra C H, R, c . We consider the standard Empirical risk minimization (ERM) paradigm for strategic classification, but take into account training data s manipulation behaviors. Specifically, given any cost function c, any n uncontaminated training data points (x1, y1, r1), , (xn, yn, rn) drawn independently and identically (i.i.d.) from the same distribution D, the strategic empirical risk minimization (SERM) problem computes a classifier h H that minimizes the empirical strategic 0-1 loss in Eq. (2). Formally, the SERM for Stra C H, R, c is defined as follows:

SERM : argminh H Lc(h, {(xi, yi, ri)}n i=1) =

i=1 I h( c(xi, ri; h)) = yi (4)

where Lc(h, {(xi, yi, ri)}n i=1) is the empirical loss (compared to the expected loss Lc(h, D) defined in Eq. (2)). Unlike the standard (non-strategic) ERM problem and similar in spirit to the incentive-aware ERM in (Zhang and Conitzer, 2021), classifiers in the SERM problem take each data point s strategic response c (xi, ri; h) as input, while not the original feature vector xi. Given the definition of strategic VC-dimension and the SERM framework, we state the sample complexity result for PAC-learning in our strategic setup:

Definition 3 (PAC-Learnability) In a strategic classification problem Stra C H, R, c , the hypothesis class H (X {+1, 1}) is Probably Approximately Correctly (PAC) learnable by an algorithm A if there is a function m H,R,c : (0, 1)2 N such that (δ, ϵ) (0, 1)2, for any n m H,R,c(δ, ϵ) and any distribution D for (x, y, r), with at least probability 1 δ, we have Lc(h , D) ϵ where h is the output of the algorithm A with n i.i.d. samples from D as input. The problem is agnostic PAC learnable if Lc(h , D) infh H Lc(h, D) ϵ.

Theorem 4 Any strategic classification instance Stra C H, R, c is agnostic PAC learnable with sample complexity m H,R,c(δ, ϵ) Cϵ 2[d + log(1

δ)] by the SERM in Eq. (4), where d = SV C(H, R, c) is the strategic VC-dimension and C is an absolute constant.

Proof Let Y = {+1, 1}. Define another binary hypothesis class H = {κc(h) : h H}, where κc : (X Y) (X R Y) is a mapping such that κc(h)(x, r) = h( c(x, r; h)), (x, r) X R. Note that the input of classifier κc(h) consists of both the feature vector x and the preference r. By the definition of SVC, we have VC( H) =SVC(H, R, c) = d. Given any distribution D, cost function c, and h H, the strategic 0-1 loss of h is Lc(h, D) = E(x,y,r) D h I κc(h)(x, r) = y i = L(κc(h), D), where L( h, D) is the standard

expected risk of the newly defined h H under the distribution D in the non-strategic setting. Therefore, studying the PAC sample complexity upper bound for H under the strategic setting R, c is equivalent to studying the sample complexity for H in the nonstrategic setting. The latter problem can be addressed by employing the standard PAC learning analysis. From the Fundamental Theorem of Statistical Learning (Theorem 6.8 in (Shalev-Shwartz and Ben-David, 2014)), we know H is agnostic PAC learnable with sample complexity O(ϵ 2(VC( H) + log 1

δ)), meaning that there exists a constant C such that for

PAC-learning for Strategic Classification

any (δ, ϵ) (0, 1)2 and any distribution D for (x, y, r), as long as n C ϵ 2(VC( H)+log 1

δ), with at least probability 1 δ, we have

L( h , D) inf h H L( h, D) ϵ,

where h is the solution of ERM with n i.i.d. samples from D as input. Let h be the solution of the corresponding SERM conditioned on the same n i.i.d. samples from D. By the definition of H and Lc, we have Lc(h , D) = L( h , D), and infh H Lc(h, D) = inf h H L( h, D). Therefore, with probability 1 δ, we have

Lc(h , D) inf h H Lc(h, D) ϵ,

which implies Stra C H, R, c is agnostic PAC learnable with sample complexity O(ϵ 2[d+ log(1

δ)]) by the SERM.

Next, we illustrate how SVC connects to previous literature, particularly the two most relevant works by (Cullina et al., 2018) and (Hardt et al., 2016).

3.1 SVC generalizes Adversarial VC-Dimension (AVC)

We show that SVC generalizes the adversarial VC dimension (AVC) introduced by (Cullina et al., 2018). We give an intuitive description of AVC here, and refer the curious reader to Appendix 6 for its formal definition. At a high level, AVC captures the behaviors of binary classifiers under adversarial manipulations. Such adversarial manipulations are described by a binary nearness relation B X X and (z; x) B if and only if a data point with feature x can manipulate its feature to z. Note that there is no direct notion of agents utilities or costs in adversarial classification since each data point simply tries to ruin the classifier by moving within the allowed manipulation region (usually an δ-ball around the data point). Nevertheless, our next result shows that AVC with binary nearness relation B always equals to SVC as long as the set of strategic manipulations induced by the data points incentives is the same as B. To formalize our statement, we need the following consistency definition.

Definition 5 Given any binary relation B and any cost function c, we say B, c are rconsistent if B = {(z; x) : c(z; x) r}. In this case, we also say B [resp. c] is r-consistent with c [resp. B].

By definition any cost function c is r-consistent with the natural binary nearness relation it induces Bc = {(z; x) : c(z; x) r}. Conversely, any binary relation B is r-consistent (for any r > 0) with a natural cost function that is simply an indicator function of B defined as follows

c B(z; x) =

( , if (z; x) B 0, if (z; x) B . (5)

Note that, B and c may be r-consistent for infinitely many different r, as shown in the above example with B and c B.

Sundaram, Vullikanti, Xu and Yao

Proposition 6 For any hypothesis class H and any binary nearness relation B, let AVC(H, B) denote the adversarial VC-dimension defined in (Cullina et al., 2018). Suppose B and c are r-consistent for some r > 0, then we have AVC(H, B) =SVC(H, {+r, r}, c).

For readability, we defer the complete proof for some of the results to the appendix, while only provide their proof sketches in the main paper. The full proof of Proposition 6 is deferred to Appendix A.1. To reveal this relationship, we directly examine the definitions of AVC and SVC and demonstrate that the former captures a special case of the latter. As a corollary of Proposition 6, we know that SVC is in general larger than or at least equal to AVC when the strategic behaviors it induces include B. This is formalized in the following statement.

Corollary 7 Suppose a cost function c is r-consistent with binary nearness relation B and r R, then we have

SV C(H, R, c) AV C(H, B).

Corollary 7 illustrates that for any cost function c, the SVC with a rich preference set R is generally no less than the corresponding AVC under the natural binary nearness relation that c induces. One might wonder how large their gap can be. Our next result shows that for a general R the gap between SVC and AVC can be arbitrarily large even in natural setups. The intrinsic reason is that a general preference set R will lead to different extents of preferences (i.e., some data points strongly prefer label 1 whereas some slightly prefers it). Such variety of preferences gives rise to more strategic classification outcomes and renders the SVC larger than AVC, and sometimes significantly larger, as shown in the following proposition.

Proposition 8 For any integer n > 0, there exists a hypothesis class H with point classifiers, an instance-invariant cost function c(z; x) = l(z x) for some metric c and preference set R such that SV C(H, R, c) = n but V C(H) = AV C(H, Bc(r)) = 1 for any r R where Bc(r) = {(x, z) : c(z; x) r} is the natural nearness relation induced by c and r > 0.

In the proof we construct an instance with a universe set X = [n] S where [n] = {1, 2, , n} is the set of n elements and S be the power set of [n]. The hypothesis class H is the set of all the point classifiers with points from S. We then design an instance-invariant cost function which leads to the desired VC dimension bounds. The detailed proof can be found in Appendix A.3.

3.2 SVC under Separable Cost Functions

Not only restricting the set R of preference values can reduce the SVC. This subsection shows that restricting to special classes of cost functions can also lead to a small SVC. One special class of cost functions studied in many previous works is the separable cost functions (Hardt et al., 2016; Milli et al., 2019; Hu et al., 2019a). Formally, a cost function c(z; x) is separable if there exists function c1, c2 : X R such that c(z; x) = max c2(z) c1(x), 0 .

PAC-learning for Strategic Classification

The following Proposition 9 shows that when the cost function is separable, SVC is at most 2 for any hypothesis class H and any class of preference set R.5 Therefore, separable cost function essentially reduces any classification problem to a problem in lower dimension. Together with Theorem 4, Proposition 9 also recovers the PAC-learnability result of (Hardt et al., 2016) in their strategic-robust learning model (specifically, Theorem 1.8 of (2016)) and, moreover, generalizes their learnability from homogeneous agent preferences to the case with arbitrary agent preference values.

Proposition 9 For any hypothesis class H, any preference set R satisfying 0 R, and any separable cost function c(z; x), we have SVC(H, R, c) 2.

The key idea of the proof is to show that the manipulation regions A, B, C of three arbitrary points can be ordered so that they must without loss of generality satisfy A B C. Consequently, these points cannot be shattered. We defer the full proof to appendix A.4. The assumption 0 R implies that each agent must strictly prefer either label +1 or 1. This assumption is necessary since if 0 R, SVC will be at least the classic VC dimension of H and thus Proposition 9 cannot hold. We remark that the above SVC upper bound 2 holds for any hypothesis class H. This bound 2 is tight for some classes of hypothesis, e.g., linear classifiers.

4. Strategic Linear Classification

This section instantiates our previous general framework in one of the most fundamental special cases, i.e., linear classification. We will study both the statistical and computational efficiency in strategic linear classification. Naturally, we will restrict X Rd in this section. Moreover, the cost functions are always assumed to be induced by seminorms.6 A linear classifier is defined by a hyperplane w x + b = 0; feature vector x is classified as +1 if and only if w x + b 0. With slight abuse of notation, we sometimes also call (w, b) a hyperplane or a linear classifier. Let Hd denote the hypothesis set of all d-dimensional linear classifiers. For linear classifier (w, b), the data point s best response can be more explicitly expressed as:

c(x, r; w, b) = arg max z I(w z + b 0) r c(z; x) .

4.1 Strategic VC-Dimension of Linear Classifiers

We first study the statistical learnability by examining the strategic VC-dimension (SVC). Our first result is a negative one, showing that SVC can be unbounded in general even for linear classifiers with features in R2 (i.e., X R2) and with simple preference set R = {+1, 1}.

5. The model of (Hardt et al., 2016) corresponds to the case R = {1} in our model. For that restricted situation, the proof of Proposition 9 can be simplified to prove SVC = 1 when R = {1}. It turns out that arbitrary preference set R only increases the SVC by at most 1. 6. A function l : X R 0 is a seminorm if it satisfies: (1) triangle inequality: l(x + z) l(x) + l(z) for any x, z X; and (2) homogeneity: l(λx) = |λ|l(x) for any x X, λ R.

Sundaram, Vullikanti, Xu and Yao

Theorem 10 Consider strategic linear classification Stra C Hd, R, c . There is an instancewise cost function c(z; x) = lx(z x) where each lx is a norm, such that SV C(Hd, R, c) = even when X R2 and R = {1}.

Proof Let X = R2, and consider the linear hypothesis class on X: H = {h = sgn(w x + b) : (w, b) R3, x X}. We show that for any n Z+ and R = {+1}, there exist n points {xi}n i=1 X n and corresponding cost functions {ci}n i=1, such that the n th shattering coefficients σn(H, R, {ci}n i=1) = 2n (see Definition 1 for σn). Note that the cost function is instance-wise. Note that our construction here will use different cost functions even though each data point i is at the same location (0, 0). Let xi = (0, 0), i [n] be the set of data points. The main challenge of the proof is a very careful construction of the cost function for each data point. To do so, we first pick a set of 2n different points S = {sj}2n j=1 lying on the unit circle, i.e., S {(x, y) : x2+y2 = 1}. The number 2n is not arbitrarily chosen indeed, we will map each point sj to one of the 2n subsets of [n] in a bijective manner so that each sj corresponds to a unique subset of [n]. What are these 2n different points will not matter to our construction neither it matters which point is mapped to which subset so long as it is a bijection. Since we have the freedom to pick the locations of elements in S, we will pick any S such that S S = , where S = {( x, y) : (x, y) S} is the set that is origin-symmetric to S. We emphasize that S is chosen to symmetrize our construction in order to obtain a norm and it does not need to have any interpretation. For any xi, we now define its cost function ci through the following steps :

1. Let Si = {s [n] : i s} S contain all the 2n 1 subsets of [n] that include the element i.

2. Let Si = {( x, y) : (x, y) Si} S be the set that is origin-symmetric to Si.

3. Let Gi be the convex, origin-symmetric polygon with the vertex set being Si Si.

4. The cost function of xi is defined as ci(z; x) = x z Gi, where Gi = inf{ϵ R 0 : x ϵGi} is a norm derived from polygon Gi (note the origin-symmetry of Si Si and thus Gi).

Next we show that for any label pattern L {+1, 1}n, there exists some linear classifier h H2 such that (h( c1(x1, +1; h)), , h( cn(xn, +1; h))) = L. With slight abuse of notation, let s L = {i [n] : Li = +1} S be the point in S that corresponds to the set of the indexes of L with Li = 1. Let h L be any linear classifier whose decision boundary intersects the unit circle centered at xi and strictly separates s L from all the other elements in S S. We will use h L to denote both the linear classifier and its decision boundary (i.e., a line in R2) interchangeably. Due to the convexity of Gi, such h L must exist. We further let h L give prediction result +1 for the half plane that contains s L and 1 for the other half plane. Figure 2 illustrates the geometry of this example. We now argue that h L induces the given label pattern L for instances {(xi, 1, ci)}n i=1. To see this, we examine h L( ci(xi, 1; h)) for each i:

PAC-learning for Strategic Classification

Figure 2: Left: If i s L, h L intersects with Gi, and xi can manipulate its feature within Gi to cross h L. Right: If i / s L, h L and Gi are disjoint; xi cannot manipulate its feature within Gi to cross h L. Given any label pattern L {+1, 1}n, Gi is the convex, origin-symmetric polygon associated with xi s cost function. The linear classifier h L is chosen to separate s L from all other elements in S S and classifies s L as +1. The left/right panel shows the two situations, depending on i s L or i s L.

1. If i s L, then s L Si and xi can move to s L with cost ci(s L; xi) < 1. This is because Gi is convex and there exists a point x i on h L such that ci(x i; xi) < ci(s L; xi) = 1 = ri (e.g., choose x i as the intersection point of the segment [xi, s L] and h L). Therefore, h L will classify xi as positive. This case is shown in the left panel of Figure 2.

2. If i / s L, then s L / Si and Gi does not intersect h L. In this case, h L(x) = 1, and moving across h L always induces a cost strictly larger than 1. Therefore, the best response for xi is to stay put and h L will classify xi as negative. This case is shown in the right panel of Figure 2.

Now we have shown that the n th shattering coefficients σn(H, {+1, 1}, {ci}n i=1) = 2n. Since n can take any integer, we conclude the strategic VC-dimension in this case is + .

In the study of adversarial VC-dimension (AVC) by (Cullina et al., 2018), the feature manipulation region of each data point is assumed to be instance-invariant. As a corollary, Theorem (10) implies that AVC also becomes for linear classifiers in R2 if each data point s manipulation region is allowed to be different. It turns out that the -large SVC above is mainly due to the instance-wise cost functions. Our next result shows that under instance-invariant cost functions, the SVC will behave nicely and, in fact, equal to the AVC for linear classifiers despite the much richer data point manipulation behaviors. This result also strictly generalizes the characterization of AVC by (Cullina et al., 2018) for linear classifiers and shows that linear classifiers will be no harder to learn statistically despite allowing richer manipulation preferences of data points.

Sundaram, Vullikanti, Xu and Yao

Theorem 11 Consider an instance of strategic linear classification Stra C Hd, R, c . For any instance-invariant cost function c(z; x) = l(z x) where l is a seminorm, we have SVC(Hd, R, c) = d + 1 dim(Vl) for any bounded R, where Vl is the largest linear space contained in the ball B = {x : l(x) 1}. In particular, if l is a norm (i.e., l(x) = 0 iff x = 0), then dim(Vl) = 0 and SVC(H, R, c) = d + 1.

Proof The following lemma is well-known in algebra and will be useful for our analysis.

Lemma 12 For any seminorm l : Rd R 0, and the cost function c(z; x) = l(z x) induced by l, the minimum manipulation cost for x to move to the hyperplane w x + b = 0 is given by the following:

min x {c(x ; x) : w x + b = 0} = |w x + b|

where l (w) = supz B{w z} R 0 {+ }, and B = {z : l(z) 1} is the unit ball induced by l.

The proof has the following two parts. The first part is the more involved one.

Proof of SVC(Hd, R, c) d + 1 dim(Vl):

It suffices to show that for any n > d + 1 dim(Vl) and n data points (xi, ri) Rd R, i = 1, , n, there exists a label pattern L {+1, 1}n, such that for any h Hd it cannot induce L, i.e.,

(h( c(x1, r1; h), , h( c(xn, rn; h))) = L.

The first step of our proof derives a succinct characterization about the classification outcome for a set of data points. For any seminorm l, it is known the set B = {x : l(x) 1} is nonempty, closed, convex, and origin-symmetric. Let l (w) = supz B{w z}. We have l (w) > 0 for all w = 0 since 0 is an interior point of B. According to Lemma 12, for any x Rd and any linear classifier h = (w, b) Hd, the minimum manipulation cost for x to move to the decision boundary of h is |w x + b|/l (w). Note that we may w.l.o.g. restrict to w s such that l (w) = 1 since the sign function sgn(w x + b) does not change after re-scaling. For any data point (x, r) X R and linear classifier h Hd, we define the signed manipulation cost to the classification boundary as

δ(h, x) = h(x) |w x + b|

l (w) = w x + b,

using the condition l (w) = 1. We claim that h( c(x, r; h)) = 2I(w x + b r) 1. This follows a case analysis:

1. If r 0, then h( c(x, r, h)) = 1 if and only if h(x) = 1 and x cannot move across the decision boundary of h within cost |r| = r. This implies h( c(x, r; h)) = 2I(w x + b r) 1.

PAC-learning for Strategic Classification

2. If r > 0, then h( c(x, r, h)) = 1 if and only if h(x) = 1 and x cannot move across the decision boundary of h within cost r. In this case, h( c(x, r; h)) = (2I( (w x + b) > r) 1) = 2I(w x + b r) 1. Note that the first inequality holds strictly because we assume h always gives +1 for those x on the decision boundary.

For a set of samples (X, r) where X = (x1, , xn), r = (r1, , rn), define the set of all possible vectors (over the choice of linear classifiers (w, b) Hd) of signed manipulation costs as D(Hd, X) = {(w x1 + b, , w xn + b) : h Hd}, (6)

there is a h Hd that achieves a label pattern L on (X, r) if and only if there exists an element in D(Hd, x) + r with the corresponding sign pattern L. Recall that a linear classifier is described by (w, b) Rd+1. The second step of our proof rules out trivial linear classifiers under strategic behaviors, and consequently allows us to work with only linear classifiers in a linear space of smaller dimension. Let B = {x : l(x) 1} and Vl be the largest linear space contained in B. We argue that it suffice to consider only linear classifiers (w, b) with w Vl. This is because for any w that is not orthogonal to the subspace Vl, we can find z Vl such that c( z; x) = 0 and w z since Vl is a linear subspace. This means any data point can induce its preferred label sgn(r) with 0 cost, by moving to z if sgn(r) = + and z otherwise. Any such linear classifier will result in the same label pattern, simply specified by sgn(r). As a consequence, we only need to focus on linear classifiers (w, b) with w Vl. Let Hd = {(w, b) : w Vl} denote all such linear classifiers. Next, we argue that when restricting to the non-trivial class of linear classifiers Hd, the D( Hd, X) defined in Equation (6) lies in a linear subspace with dimension at most d + 1 dim(Vl). Consider the linear mapping GX : Hd Rn determined by the data features X, defined as

GX(w, b) = (w x1 + b, , w xn + b), (w, b) Hd.

Since w Vl, w is from a linear subspace of d dim(Vl). Linear mapping will not increase the dimension of the image space, therefore D( Hd, X) lies in a space with dimension at most d + 1 dim(Vl). Finally, we prove that there must exist label patterns that cannot be induced by linear classifiers whenever the number of data points n > d + 1 dim(Vl). Let span D( Hd, X)

denote the smallest linear space that contains D( Hd, X). Since span D( Hd, X) has dimension at most d + 1 dim(Vl) < n but span D( Hd, X) Rn, there must exist a non-zero vector u Rn such that: (1) u = 0; (2) u span D( Hd, X) (i.e., u v = 0, v span D( Hd, X) ); and (3) u r 0 (if u r 0, simply takes its negation). Note that this implies u v 0, v span D( Hd, X) + r. We argue that the sign pattern of the vector u, denoted as sgn( u), and the sign pattern of all negatives (L = ( 1, , 1)) cannot be achieved simultaneously by Hd. Suppose sgn( u) can be achieved by Hd, then there must exist v1 span(D( Hd, X)) + r such that sgn( u) = sgn(v1) and u v1 0. Since sgn( u) = sgn(v1) also implies u v1 0, we thus have u v1 = P j=1 ujv1 j = 0. We claim that there must exist j such that uj > 0. First of all, we cannot have uj < 0 for any j since that implies v1 j < 0 (only strictly less v1 j s

Sundaram, Vullikanti, Xu and Yao

will be assigned 1 pattern due to our tie breaking rule) and consequently, u v1 < 0, a contradiction. Also note that u = 0, so there exists j [n] such that uj > 0. Utilizing the above property of u, we show that the sign pattern L = ( 1, , 1) cannot be achieved by Hd. Suppose, for the sake of contradiction, that this is not true. Then there exists another v2 = (v2 1, , v2 n) span D( Hd, X) + r with all its elements being strictly negative. Now consider v = v1 v2 span(D( Hd, X)), we have u v = u v1 u v2 = 0 u v2 > 0. Here the inequality holds because uj 0, v2 j < 0 for all j and there exists some j such that uj > 0. Therefore, we draw a contradiction to the fact that u v = 0 for any v span(D( Hd, X)). Now we proved that sgn( u) and L = ( 1, , 1) cannot be achieved simultaneously by non-trivial classifiers Hd, and the only achievable sign pattern for trivial classifiers is sgn(r). Note that r span D( Hd, X) + r, sgn(r) is thus also achievable by Hd. Therefore, the trivial classifier has no contributions to the shattering coefficient, and we conclude at least one of sgn( u) and L = ( 1, , 1) cannot be achieved by Hd.

Proof of SVC(Hd, R, c) d + 1 dim(Vl):

The second step of the proof shows SVC(H, R, c) d+1 dim(Vl) by giving an explicit construction of (X, r) that can be shattered by Hd. Let x0 = 0, and (x1, , xt) be a basis of the subspace orthogonal to Vl, (xt+1, , xd) be a basis of the subspace Vl, where t = d dim(Vl). We claim that the t + 1 = d + 1 dim(Vl) data points in {0, 1, , t} can be shattered by Hd. In particular, for any given subset S {0, 1, , t}, consider the linear system

xi w S + b S = 1, if i S xi w S + b S = 1, if i t, and i / S xi w S = 0, t + 1 i d.

Because (x1, , xd) has full rank, the solution (w S, b S) must exist. Therefore, the half-plane h = w S x + b S separates S and {x0, , xd}/S. Now consider the case when each xi has a strategic preference ri R. Since w S is chosen to be orthogonal to Vl, w S xi is bounded when xi {z : c(z; xi) ri}. Let δS = max0 i t{sup{w S (z xi) : c(z; xi) ri}}, and δ = max(1, 2δS). Then the data set {δx0, , δxt} can be shattered by Hd for any given c, R, because the classifier (δw S, δb S) separates the subset S and the other points regardless their strategic responses.

4.2 The Complexity of Strategic Linear Classification

In this subsection, we turn our attention to the computational efficiency of learning. The standard ERM problem for linear classification to minimize the 0-1 loss is already known to be NP-hard in the general agnostic learning setting (Feldman et al., 2012). This implies that agnostic PAC learning by SERM is also NP-hard in our strategic setup. Therefore, our computational study will focus on the more interesting realizable PAC-learning case, that is, assuming there exists a strategic linear classifier that perfectly separates all the

PAC-learning for Strategic Classification

data points. In the non-strategic case, the ERM problem can be solved easily by a linear feasibility problem. It turns out that the presence of gaming behaviors does make the resultant SERM problem significantly more challenging. We prove essentially tight computational tractability results in this subsection. Specifically, any strategic linear classification instance can be efficiently PAC-learnable by the SERM when the problem exhibits some adversarial nature . However, the SERM problem immediately becomes NP-hard even when we go slightly beyond such adversarial situations. We start by defining what we mean by adversarial nature of the problem.

Definition 13 (Essentially Adversarial Instances) For any strategic classification problem Stra C H, R, c , let

min = min{r : (x, y, r) with y = 1} and

max+ = max{r : (x, y, r) with y = +1} (7)

be the minimum reward among all 1 points and the maximum reward among all +1 points, respectively. We say the instance is adversarial if min 0 max+ and is essentially adversarial if min max+.

In other words, an instance is adversarial if each data point would like to move to the opposite side of its label though with different magnitudes of preferences, and is essentially adversarial if any negative data point has a stronger preference to move to the positive side than any positive data point. Many natural settings are essentially adversarial, e.g., all the four examples in Subsection 2.2. Our first main result of this subsection (Theorem 14) shows that when the strategic classification problem exhibits the above adversarial nature, linear strategic classification can be efficiently PAC-learnable by SERM. The second main result Theorem 15 shows that the SERM problem becomes NP-hard once we go slightly beyond the adversarial setups identified in Theorem 14. These results show that the computational tractability of strategic classification is primarily governed by the preference set R. Interestingly, this is in contrast to the statistical learnability results in Theorem 10 and 11 where the preference set R did not play much role.

Theorem 14 Any separable strategic linear classification instance Stra C Hd, R, c is efficiently PAC-learnable by the SERM in polynomial time in the following two situations:

1. The problem is essentially adversarial (min max+) and cost function c(z; x) = l(z x) is instance-invariant and induced by a seminorm l.

2. The problem is adversarial (min 0 max+) and the instance-wise cost function c(z; x) = lx(z x) is induced by seminorms {lx}.

Proof For any data point (x, y, r), let the manipulation cost for the data point be c(z; x) = lx(z x) where lx is any seminorm. Since the instance is separable, there exists a hyperplane h : w x + b = 0 that separates the given n training points (x1, y1, r1), , (xn, yn, rn) under strategic behaviors. The SERM problem is thus a feasibility problem, which we

Sundaram, Vullikanti, Xu and Yao

now formulate. Utilizing Lemma 12 about the signed distance from xi to hyperplane h under cost function c(z; xi) = lxi(z xi), we can formulate the SERM problem under the separability assumption. Concretely, we would like to find a hyperplane h : w x + b = 0 such that it satisfies the following for any (xi, yi, ri):

1. If yi = 1 and ri 0, we must have either w xi + b 0 or w xi + b 0 and (w x+b)

l xi(w) ri;

2. If yi = 1 and ri 0, we must have w x+b

l xi(w) ri (this implies w xi + b 0);

3. If yi = 1 and ri 0, we must have either w xi + b 0 or w xi + b > 0 and w x+b l xi(w) < ri;

4. If yi = 1 and ri 0, we must have (w x+b)

l xi(w) > ri (this implies w xi + b < 0);

Note that we classify any point on the hyperplane as +1 as well, which is why the strict inequality for Case 3 and 4. Case 1 can be summarized as w x+b

l xi(w) ri. Similarly, Case 3

can be summarized as w x+b

l xi(w) < ri. To impose the strict inequality for Case 3 and 4, we

may introduce an ϵ slack variable. These observations lead to the following formulation of the SERM problem.

find w, b, ϵ > 0 subject to w xi+b

l xi(w) ri, for points (xi, yi, ri) with yi = 1.

l xi(w) ri ϵ, for points (xi, yi, ri) with yi = 1. (8)

We now consider the two settings as described in the theorem statement. We first consider Situation 1, i.e., the essentially adversarial case with min max+ and an instance-invariant cost function induced by the same seminorm l, i.e., c(z; x) = l(x z) for any x. In this case, System (8) is equivalent to the following

find w, b, ϵ > 0 subject to w xi + b ri, for points (xi, yi, ri) with yi = 1. w xi + b (ri + ϵ), for points (xi, yi, ri) with yi = 1. l (w) = 1

This system is unfortunately not a convex feasibility problem. To solve System (9), we consider the following optimization program (OP), which is a relaxation of System (9) by relaxing the non-convex constraint l (w) = 1 to the convex constraint l (w) 1.

maximize ϵ subject to w xi + b ri, for points (xi, ri) with label 1. w xi + b ri ϵ, for points (xi, ri) with label -1. l (w) 1

Note that OP (10) is a convex program because the objective and constraints are either linear or convex. Therefore, OP (10) can be efficiently solved in polynomial time.7 Note

7. Note that without additional assumptions on the objective and constraints, convex programs can only be solved up to precision ϵ in poly(1/ϵ) time (Nesterov et al., 2018). In this case, we simply say it can be solved efficiently.

PAC-learning for Strategic Classification

that this relaxation is not tight in general as we will show later that solving System (9) is NP-hard in general. Our main insight is that under the assumption of min max+, the above relaxation is tight i.e., there always exists an optimal solution to the above problem with l (w) = 1. This solution is then a feasible solution to System (9) as well, thus completing our proof. Concretely, given any optimal solution (w , b , ϵ ) to OP (10), we construct another solution ( w, b, ϵ) as follows:

α 1)min + max+

α , where α = l (w ) 1.

We claim that the constructed solution above remains feasible to OP (10). Note that for data point with label 1, we have: (1) min + max+

2 ri by assumption ri max+ min ; (2) xi w + b ri by the feasibility of (w , b , ϵ ). Therefore

α 1)min + max+

xi w + b ri

This proves that the constructed solution is feasible for data points with label 1. Similar argument using the inequality min + max+

2 ri for any negative label data point shows that it is also feasible for negative data points. It is easy to see that the solution quality is as good as the optimal solution ϵ since α 1. This proves the optimality of the constructed solution. Finally, we consider the Situation 2 where the instance is adversarial, i.e, min 0 max+. In this case, ri in the first constraint of System (8) is always non-positive whereas ri in the second constraint is always non-negative. After basic algebraic manipulations, the SERM problem becomes the following optimization problem.8

find w, b, ϵ > 0 subject to w xi + b ( ri) l xi(w), for points (xi, yi, ri) with ri 0. (w xi + b) (ri + ϵ) l xi(w), for points (xi, yi, ri) with ri 0. (11)

This is again not a convex feasibility problem due to the non-convex term (ri+ϵ) l xi(w), however for any fixed ϵ > 0 both constraints are convex. Moreover, if the system is feasible for some ϵ0 > 0 then it is feasible for any 0 < ϵ ϵ0. Therefore, we can determine the feasibility of the (convex) system for any fixed ϵ and then binary search for the feasible ϵ. Therefore, the feasibility problem in System (8) can be solved in polynomial time.

Our next result shows that the positive claim in Theorem (14) are essentially the best one can hope for. Indeed, the SERM immediately becomes NP-hard if one goes slightly beyond the two tractable situations in Theorem (14). Note that our results did not rule out the possibility of other computationally efficient learning algorithms other than the SERM. We leave this as an intriguing open problem for future works.

8. The l xi function in the program should be viewed as depending on the data point while not just the feature xi. However, this will not affect the proof correctness.

Sundaram, Vullikanti, Xu and Yao

Theorem 15 Suppose the strategic classification problem is linearly separable, then the SERM Problem for linear classifiers is NP-hard in the following two situations:

1. Preferences are arbitrary and the cost function is instant-invariant and induced by the standard l2 norm, i.e., c(z; x) = x z||2.

2. The problem is essentially adversarial (min max+) and the cost function is instance-wise and induced by norms.

Proof We start with Situation 1, i.e., the preferences are arbitrary but the cost function is c(z; x) = x z||2 2. We will show later that the second situation can be reduced from the first. In the first situation, the feasibility problem is System (9) with l as the l2 norm. Our reduction starts by reducing this system to the following optimization problem (OP)

maximize ||w||2 2 subject to xi w + b ri, for points (xi, ri) with label +1. xi w + b ri ϵ, for points (xi, ri) with label 1. ||w||2 2 1

Formally, we claim that for any fixed ϵ, system (9) is feasible if and only if OP (12) has optimal objective value 1. The if direction is simple. That is, if OP (12) has optimal objective value 1, then the optimal solution (w , b ) is automatically a feasible solution to System (9) because ||w ||2 = 1. For the only if direction, let ( w, b) be any feasible solution to System (9), then it is easy to verify w = w ||w||2 and b = b ||w||2 must also be feasible to System (9). Moreover, it is an optimal solution to OP (12) with objective value 1, as desired. We now prove that determining whether the optimal objective value of OP (12) equals 1 or not is NP-complete. We reduce from the following well-known NP-complete problem called the partition problem:

Given d positive integers c1, , cd, decide whether there exists a subset S [d] such that P i S ci = P i S ci

We now reduce the above partition problem to solving OP (12). Given any instance of partition problem, construct the following SERM instance.

The Constructed Hard SERM Instance for Situation 1: We will have n = 2d + 3 data points with feature vectors from Rd. For convenience, we will use ei to denote the basis vector in Rd whose entries are all 0 except that the i th is 1. For each i [d], there is a data point (x, y, r) = (2

d ei, 1, 4) as well as a data point (

d ei, 1, 1 ϵ). The remaining three data points are (c, 1, 2), data point (2c, 1, 2 ϵ), and data point (3c, 1, 2). We claim that OP (12) instantiated with the above constructed instance has an optimal objective value 1 if and only if the answer to the given partition problem is Yes. We first prove the if direction. If the partition problem is a Yes instance, then there exists an S such that P i S ci P i S ci = 0. We argue that the following construction is an optimal solution to OP (12) with optimal objective value 1:

b = 2, wi = 1

d i S, wi = 1

PAC-learning for Strategic Classification

Clearly, ||w ||2 2 = 1. We only need to prove feasibility of (w , b ). For any label 1 point (x, r) = (2

d ei, 4), we have x w +b = 2

dei w 2 = 4 r, as desired. Similarly, for any label 1 point (x, r) = (

d ei, 1 ϵ), we have x w +b =

dei w 2 = 1 r ϵ. The feasibility of point (c, 2) with label 1 is argued as follows: x w +b = c w 2 = r. Feasibility of (2c, 2 ϵ) and (3c, 2) are similarly verified. We now prove the only if direction. In particular, we prove that that if OP (12) has some optimal solution (w , b) with ||w ||2 2 = 1, then the partition instance must be Yes. Let us first examine the feasibility of OP (12).

1. By the constraints with respect to positive-label data points (2

d ei, 4), we have 2

dei w + b 4 or equivalently wi

2. By the constraints with respect to negative-label data points (

d ei, 1 ϵ), we have

dei w + b 1 or equivalently wi

3. By the constraints with respect to data point (c, 2) with label 1, we have c w+b 2, or equivalently 2 b c w.

4. By the constraints with respect to data point (2c, 2 ϵ) with label -1, we have 2c w + b 2, or equivalently 2 b 2c w.

5. By the constraints with respect to data point (3c, 2) with label 1, we have 3c w +b 2, or equivalently 2 b 3c w.

Point 3 5 implies 2c w 2 b min{c w, 3c w}. This must imply c w = 0 as any non-zero c w cannot satisfy 2c w min{c w, 3c w}. As a consequence, the only feasible b value is b = 2. Plugging b = 2 into Point 1 and 2, we have

Since the optimal objective value is 1 = Pd i=1(w i )2, it is easy to see that this optimal objective is achieved only when each w i equals either 1

d. Now define S = {i :

d} to be the set of i such that w i is positive. It is easy to verify that S will be a solution to the partition problem, implying that it is a Yes instance. This proves the NP-hardness for Situation 1 stated in the theorem. Finally, we consider Situation 2 which can be reduced from the first situation. In particular, the constructed hard instance above has reward preferences all being positive (in fact, drawn from only three possible values {1, 2, 4}), but do not satisfy the essentially adversarial condition. However, if we are allowed to use instant-wise cost functions, we can simply scale down the reward preference for point with label 1 but propositionally scale down its cost function so that the right-hand-side of the first constraint in System (9) remains the same. Concretely, we now modify our constructed instance above to be the follows.

The Constructed Hard SERM Instance for Situation 2: We still have n = 2d+3 data points with feature vectors from Rd. For each i [d], there is a data point (x, y, r) = (2

d ei, 1, 0.5) with cost function c(z; x) = 1

8 z x||2 2 as well as a data point (

d ei, 1, 1 ϵ)

Sundaram, Vullikanti, Xu and Yao

with cost function c(z; x) = z x||2 2. The remaining three data points are: (1) data point (c, 1, 0.5) with cost function c(z; x) = 1

4 z x||2 2; (2) data point (2c, 1, 2 ϵ) with cost function c(z; x) = z x||2 2; (3) data point (3c, 1, 0.5) with cost function c(z; x) = 1

4 z x||2 2. It is easy to verify that the above instance satisfy situation 1 in the theorem statement and is equivalent to the instance we constructed for the second situation and thus is also NP-hard.

Remark 16 Theorem 11, Theorem 14 and Theorem 15 together imply that for strategic linear classification: (1) the problem is efficiently PAC-learnable (both statistically and computationally) when the cost function is instance-invariant and preferences are essentially adversarial; (2) SERM can be solved efficiently but SVC is infinitely large when the cost function is instance-wise and preferences are adversarial; (3) the problem is efficiently PAC learnable in a statistical sense, but SERM is NP-hard when the cost function is instance-invariant and preferences are arbitrary.

5. The Power and Limits of Randomization

It is well-known that randomization over the classifiers does not contribute to a strictly smaller loss in standard classification. Interestingly, it turns out that randomization can be helpful in strategic classification, which is reported by Braverman and Garg (2020). However, their entire work was based on a simplified setting in the sense that they only considered one-dimensional feature space and homogeneous strategic preference. In this section, we study the power and limits of randomized linear classifiers in our generalized strategic setting. First, we define randomized classifiers as follows.

Definition 17 (Randomized Binary Classifiers) A binary classifier H is called a randomized classifier over any hypothesis class H (not necessarily linear classifiers) if there exists a set of deterministic classifiers {h1, . . . , hk} H, and a probability vector p = {p1, . . . , pk} with P j pj = 1, such that for any input feature x, H(x) = hj(x) with probability pj.

The capital H notation distinguishes randomized classifiers from deterministic ones and can be viewed as a random variable. Since we always focus on binary classification, we simply say randomized classifiers henceforth. Note that randomized classifiers should not be confused with classification methods like logistic regression or ensemble methods (e.g., random forest), which ultimately still output a deterministic label. The following proposition, whose proof is deferred to Appendix B.1, shows that randomization can help in strategic linear classification. We remark that an interesting question is whether each data point can efficiently identify its best response against a general randomized (even linear) classifier in polynomial time. Due to the combinatorial nature of different possible responses, this is a non-trivial open question. However, its answer shall not affect our following result since our constructed classifier only randomizes over two linear classifiers, to which the best response is straightforward to compute.

PAC-learning for Strategic Classification

Proposition 18 There are strategic classification instances that are perfectly separable by a randomized linear classifier but not by any deterministic linear classifier. This claim is valid even when all data points have the same reward value r.

We remark that the constructed example for Proposition 18 is in the 2-dimension Euclidean space. If the same preference r is not required, there exist simpler examples in 1-d (see Appendix B.2), though it is interesting to figure out whether there is a 1-d example satisfying the full statement of Proposition 4. The advantages of randomized classifiers over deterministic classifiers fundamentally come from the strategic data points tradeoff between two factors: (a) manipulation cost; (b) the gain from classification outcomes. Interestingly, if any of these two factors is absent, randomization will not be beneficial. First, if there is no gain from the classification outcome (i.e., r = 0 for any data point), the data points naturally have no benefit to move and thus will stay put. This is precisely the classic classification setup. Second, our following result shows that if data points have no moving cost, randomization does not help either in the separable case. Formally, we consider a special type of strategic classification where each data point is constrained to move within a designated region which can be arbitrary (even can be unconnected) and has no moving cost, i.e., c(z; x) = 0 for any feasible move. We term this the zero-manipulation-cost strategic classification. Note that the adversarial or robust classification setup falls into this case (Cullina et al., 2018; Awasthi et al., 2019). The following proposition shows that under the zero-manipulation-cost case, randomization over classifiers does not help that much.

Proposition 19 Consider zero-manipulation-cost strategic classification. For any hypothesis class H, if there is a randomized classifier over H that perfectly separates the positive points from the negative (i.e., achieving 0 loss), then there must exist a deterministic classifier in H that achieves so as well.

Proof Consider any strategic classification instance Stra C H, R, c where the cost function is a zero-manipulation cost function, i.e., each data point has a designated feasible region to move around with cost 0. Let D be any distribution over data points and suppose randomized classifier H, defined by H(x) = hj(x) H with probability pj for any j = 1, , k, achieves perfectly separates the positive points from the negative. Assume a classifier h that randomizes over k hyperplanes h1, , hk and achieves zero loss. We claim that any deterministic classifier hj will also achieve zero loss and thus the randomization is not needed. Consider any data point (x, y, r) D. Given H, let c(x, r; H) denote the optimal manipulated feature that the data point will be moving to. By assumption of zero loss, we know that for any j [k], hj will classify c(x, r; H) correctly, meaning hj( c(x, r; H)) equals the true label of y. This however did not prove our result yet since after deploying the deterministic classifier hj, the optimal manipulated feature should have been c(x, r; hj) while not the c(x, r; H). We now prove hj( c(x, r; hj)) = hj( c(x, r; H)) = y. Suppose, for the sake of contradiction, that hj( c(x, r; hj)) = y. Since both c(x, r; hj), c(x, r; H) are feasible moves for the data point, the reason that the data point now strictly prefers c(x, r; hj) over c(x, r; H) must because hj( c(x, r; hj)) = sgn(r) and hj( c(x, r; H)) = sgn(r), which

Sundaram, Vullikanti, Xu and Yao

equals y. Since H achieves perfect classification, all hj s must classify c(x, r; H) as the same label sgn(r). That means, the move of the data point s feature from x to c(x, r; H) leads to the data point being classified as the label sgn(r) that it does not prefer. This however conflicts with the assumption that c(x, r; H) is an optimal manipulated feature since moving to c(x, r; hj) instead would at least lead to the data point being classified as sgn(r) by hj. Therefore, we must have hj( c(x, r; hj)) = hj( c(x, r; H)) = y for any j, concluding the proof.

In adversarial classification, it is usually assumed that each data point can move within a δ-ball around it with no cost. An immediate corollary of Theorem 19 is the following.

Corollary 20 Randomization does not help in any perfectly separable adversarial classification problems.

We remark that perfectly separable assumption in Theorem 19 is necessary. That is, even for zero-manipulation-cost strategic classification problem, there are non-separable examples where randomized linear classifier can achieve strictly larger accuracy than any deterministic linear classifier, as shown in the following proposition with proof deferred to Appendix B.3.

Proposition 21 There exists zero-manipulation-cost non-separable strategic classification instances in R2 where the minimum risk of any deterministic linear classifier is strictly larger than some randomized linear classifier.

In this work, we propose and study a general strategic classification setting where data points have different preferences over classification outcomes and different manipulation costs. We establish the PAC-learning framework for this strategic learning setting and characterize both the statistical and computational learnability result for linear classifiers. En route, we generalize the recent characterization of adversarial VC-dimension (Cullina et al., 2018) as well as computational tractability for learning linear classifiers by (Awasthi et al., 2019). Our conclusion reveals two important insights. First, the additional intricacy of having different preferences harms the statistical learnability of general hypothesis classes, but not for linear classifiers. Second, learning strategic linear classifiers can be done efficiently only when the setup exhibits some adversarial nature and becomes NP-hard in general. Our learnability result for linear classifiers applies to cost functions induced by seminorms. A future direction is to generalize the theory to cost function induced by asymmetric seminorms or even any metrics. We also note that the strategic classification model we consider is under the full-information assumption, i.e., the cost function and the strategic preferences are transparent. This is analogous to the evasion attack in the adversarial machine learning literature, where the training data is supposed to be uncontaminated and the manipulation only happens during testing. What if we cannot observe the strategic preferences during training or do not know the adversaries cost function? This can be reformulated as online learning through repeated Stackelberg games and has been studied in

PAC-learning for Strategic Classification

(Dong et al., 2018), but it does not apply to classifiers with 0-1 loss. It is still interesting to understand the behavior of the optimal classifier in the partial information strategic setting. We also find that the randomization over linear classifiers can strictly enhance the accuracy compared to deterministic ones. This observation is interesting because simple randomization over a set of classifiers is not helpful in standard classification problems in general. It might suggest that the difficulties of learning under standard and strategic settings differ by nature. Another interesting follow-up question is how we can efficiently compute the optimal randomized linear classifier for strategic classification. It is challenging because it is unclear how to compute the best response of a data point against such a randomized classifier. We identify it as an intriguing future direction.

Acknowledgement

We would like to thank the editor and the anonymous reviewers for their insightful comments that helped greatly improved the paper. H. Xu is supported by a GIDI award from the UVA Global Infectious Diseases Institute and a Google Faculty Research Award. A. Vullikanti is supported by NSF grants IIS-1931628, CCF-1918656, NSF IIS-1955797, and NIH grant R01GM109718. R. Sundaram is supported by NSF grants CNS-1718286 and IIS-2039945.

Appendix A. Omitted Proofs from Section

A.1 Proof of Proposition 6

Proof The adversarial VC-dimension defined in (Cullina et al., 2018) relies on an auxiliary definition of corrupted classifier h = κR(h) of any classifier h for the standard nonadversarial setting such that h(x) = h(x) if all the points in N(x) have the same label as x and otherwise, h(x) = . Recall that N(x) = {z X : (z; x) B} = {z X : c(z; x) r} denotes the set of all possible adversarial features x can move to. Given this auxiliary definition, the adversarial VC-dimension is defined as AVC(H, B) = sup{n : σn(F, B) = 2n}, where

σn(F, B) = max (x,y) X n {+1, 1}n |{(f(x1, y1; h), . . . , f(xn, yn; h)) : h H}| (13)

is the shattering coefficient, and f(xi, yi) = I( h(xi) = yi) is the loss function of the corrupted classifier h = κR(h). Since B and c are r-consistent, we have B = {(z; x) : c(z; x) r}. Let R = {+r, r}. We now prove the proposition by arguing

sup{n N : σn(H, R, c) = 2n} = sup{n : σn(F, B) = 2n}. (14)

1. If sup{n N : σn(H, R, c) = 2n} = n, by Definition 1, there exists (x i, r i) X R, i = 1, , n such that |{(h( c(x 1, r 1; h)), , h( c(x n, r n; h)) : h H}| = 2n. Since Definition 1 does not rely on the true labels of x i, we may let the true labels of x i be y i = r i/r for any i. In this case, each x i s strategic preference is against its true label, which corresponds to the loss function f in Equation (13) for the adversarial

Sundaram, Vullikanti, Xu and Yao

setting. Therefore, taking (xi, yi) = (x i, y i) in Equation (13) gives σn(F, B) = 2n. This implies sup{n N : σn(H, R, c) = 2n} sup{n : σn(F, B) = 2n}.

2. Conversely, if sup{n : σn(F, B) = 2n} = n, from Equation (13), there exists (xi, yi) X R, i = 1, , n such that |{(f(x1, y1), . . . , f(xn, yn)) : f F}| = 2n. Similarly, taking ri = ryi R gives σn(H, R, c) = 2n, which implies sup{n N : σn(H, R, c) = 2n} sup{n : σn(F, B) = 2n}.

Therefore, we have AVC(H, B) =SVC(H, {+r, r}, c) for any r-consistent pair (B, c).

A.2 Proof of Corollary 7

Proof Since {+r, r} B, we have σn(H, R, c) σn(H, {+r, r}, c) by Definition 1. As a result, SVC(H, R, c) SVC(H, {+r, r}, c). Then by applying Proposition 6 we have SVC(H, R, c) SVC(H, {+r, r}, c) =AVC(H, B).

A.3 Proof of Proposition 8

Given any positive integer n, let [n] denotes {1, 2, , n}, and S be the power set of [n], i.e., the set that contains all the subsets of [n]. Let X = [n] S be the sample space of size n + 2n, and the hypothesis class H is the set of all the point classifiers with points from S, i.e., H = {hs : s S}, where point classifier hs only classifies the point s S as positive. The cost function c(z; x) is a metric defined as follows. Since metric is symmetric, i.e., c(z; x) = c(x; z), we will use the notation c(x, z) instead throughout this proof.

x, if x [n], z S, x z x + 1, if x [n], z S, x / z c(z, x), if x S, z [n] x + z, if x, z [n], x = z 1, if x, z S, x = z 0, if x = z,

and R is set to be [ n, 1] [1, n]. First, we verify that c( , ) is indeed a metric. Given definition (15), it is easy to see that c(x, z) = 0 iff x = z, and c(x, z) = c(z, x), x, z X. It remains to check the triangle inequality, i.e., for any x, y, z X, c(x, y) + c(y, z) c(x, z). Consider the case when x, y, z are different elements in X. By enumerating all the possibility that whether each x, y, z is in [n] or S, it suffices to discuss the following 8(= 23) cases:

1. if x, y, z [n], c(x, y) + c(y, z) = x + y + y + z > x + z = c(x, z).

2. if x, y, z S, c(x, y) + c(y, z) = 2 > 1 = c(x, z).

3. if x, z [n], y S, then c(x, y) x, c(y, z) z. = c(x, y) + c(y, z) x + z = c(x, z).

PAC-learning for Strategic Classification

4. if x, y [n], z S, we need to show that c(x, y) c(x, z) c(y, z). Conditioned on the relationship between x, y and set z, the maximum value of c(x, z) c(y, z) is x y +1 when y z, x / z. Therefore, c(x, y) = x + y x y + 1 c(x, z) c(y, z).

5. if x, z S, y [n], then c(x, y) + c(y, z) y + y > 1 c(x, z).

6. if x, y S, z [n], then the maximum value for c(x, z) c(y, z) is z + 1 z = 1 when z / x, z y. Therefore, c(x, y) 1 c(x, z) c(y, z).

7. if x S, y, z [n], it is equivalent to case 4.

8. if y, z S, x [n], it is equivalent to case 6.

Next, we show VC(H) = 1, AVC(H, Bc(r)) = 1, and SVC(H, R, c) n. Observe that VC(H) = 1 follows easily since no point classifier hs H can generate the label pattern (+1, +1) for any pair of distinct data points. Next we prove AVC(H, Bc(r)) = 1. We first show AVC(H, Bc(r)) 1 by arguing that under binary nearness relation Bc(r) = {(z; x) : c(z, x) r} with r 1, any two elements x1, x2 in X cannot be shattered by H.

1. If at least one of r1, r2 equals r, e.g., r1 = r, we show that x1 can never be classified as +1 by contradiction. Suppose some hs H classifies (x1, r) as +1: if x1 = s, since r1 = r < 0, x1 will not manipulate its feature and be classified as 1; if x1 = s, x1 can move to any z S with cost 1 r, and will also be classified as 1. Therefore, (x1, x2) can not be shattered.

2. If r1 = r2 = r, consider the following two cases:

(a) If at least one of x1, x2 belongs to S, e.g., x1 S, then x1 can move to any s S as c(x1, s) = 1 r for any s S. Therefore x1 can never be classified as 1 by any point classifier in H.

(b) if x1, x2 [n], we may w.l.o.g. assume x1 < x2, i.e., x1 + 1 x2. Observe that when r < x1, any hs H will classify x1 as -1 because c(x1, s) = x1 > r, s S; when r x1 + 1, any hs H will classify x1 as +1 because c(x1, s) = x1 + 1 r, s S. Therefore, in order to shatter (x1, x2), r must lie in the interval [x1, x1 + 1) [x2, x2 + 1) = , which draws the contradiction.

To see that AVC(H, Bc(r)) 1, for any x [n] with r > 0, it can be classified as either +1 or 1 as long as r [x, x + 1). We thus have AVC(H, c) = 1. Finally, we prove that SVC(H, R, c) = n. Consider the subset [n] X of size n, with each element i equipped with a strategic preference ri = i. For any label pattern L {+1, 1}n, let s L = {i [n] : Li = +1} be an element in S. We claim that hs L H gives exactly the label pattern L on [n]. To see this, consider any i [n]:

1. If i s L, i will move to s L S and be classified as +1, as the cost c(i, s L) = i ri = i.

2. If i / s L, i will not move to s L S and be classified as 1, as the cost c(i, s L) = i + 1 > ri = i.

Sundaram, Vullikanti, Xu and Yao

Therefore, any label pattern L {+1, 1}n can be achieved by some hs L H. This implies SVC(H, R, c) n. On the other hand, it s easy to see H cannot shatter n + 1 points, because any subset of size n + 1 must contain an element s0 in S, and no matter what strategic preference s0 has, it will either be classified as +1 by all hs H, or be classified as +1 by only one classifier in H, i.e., hs0. Either case renders the shattering for n + 1 points impossible.

A.4 Proof of Proposition 9

Proof Define the adversarial region for an adversary (x, r) as N(x, r) = {z X : c2(z) c1(x)+|r|} {x}. Since staying with the same feature has no cost, this implies c(x; x) = 0 or equivalently c2(x) c1(x) for any x X. Then, the best response function for (x, r) can be characterized by

1. if h(x) = sgn(r), then h( (x, r; h)) = sgn(r);

2. if h(x) = sgn(r), then

h( (x, r; h)) =

( sgn(r), z N(x, r) : h(z) = sgn(r) sgn(r), z N(x, r) : h(z) = sgn(r) (16)

Suppose there are three points {(xi, ri)}3 i=1 that can be shattered by H. Let bi = c1(xi) + ri and w.l.o.g. let b1 b2 b3. From b1 b2 b3, we have N(x1, r1) N(x2, r2) N(x3, r3). By Pigeonhole principle, there must exists two elements in {r1, r2, r3} which have the same sign. Suppose these two elements are r1, r2 and consider the following two cases:

1. r1 > 0, r2 > 0. From Equation 16, for any h H, h( (x2, r2; h)) = 1 means h(z) = 1, z N(x2, r2). Note that N(x1, r1) N(x2, r2), we also have h(z) = 1, z N(x1, r1). As a result, h( (x1, r1; h)) = 1, meaning the sign pattern {+, } cannot be achieved by any h H for {(x1, r1), (x2, r2)}.

2. r1 < 0, r2 < 0. From Equation 16, for any h H, h( (x2, r2; h)) = 1 means h(z) = 1, z N(x2, r2). Similarly, from N(x1, r1) N(x2, r2) we conclude h(z) = 1, z N(x1, r1) and h( (x1, r1; h)) = 1, meaning the sign pattern { , +} cannot be achieved by any h H for {(x1, r1), (x2, r2)}.

Therefore, {(xi, ri)}3 i=1 cannot be shattered by H, which implies SVC(H, R, c) 2.

Appendix B. Omitted Proofs in Section 5

B.1 Proof of Proposition 18

Consider an example with data points as depicted in Figure 3. Both plots show exactly the same strategic classification instance. Here, all solid points have positive labels, whereas

PAC-learning for Strategic Classification

all other points have negative labels. Three data points are of interest in our analysis, i.e., point A, B, C, and they are on the same line. The left plot draws the optimal deterministic classifier, and the right plot draws a randomized classifier that picks hyperline h1, h2 uniformly at random. The cost function here is the Euclidean distance c(z; x) = x z 2. Let r =

2 for all the data points. Under the squared Euclidean distance cost function and the condition that r =

2 is the same for all data points, any deterministic linear classifier is strategically equivalent to another linear classifier in the following sense: the classification outcome for linear classifier h in the strategic setup is identical to the classification outcome for linear classifier h in the non-strategic setup where h is obtained by shifting h towards the negative direction by r =

2. It is easy to see that no linear classifier can strictly separate the positive points from the negatives in the truthful setting, and thus this impossibility also holds in the strategic setting. As a result, the best deterministic linear classifier makes at least one mistake. One such optimal deterministic linear classifier is the hyperplane h as depicted in the left plot of Figure 3 which is parallel to line ABC but just above line ABC by 1.5. As a result, to move to the positive side of the classifier, point A, B, C need to suffer a cost 1.5 >

2 which does not balance the benefit they gain. Therefore, all data points will remain truthful, and the classifier makes one mistake at data point A.

Figure 3: A strategic classification instance where randomized linear classifier beats any deterministic classifier. Cost function c(z; x) = x z 2 is the Euclidean distance. Left: an optimal deterministic classifier. Right: a randomized classifier with perfect precision which picks hyperplane h1, h2 uniformly at random.

Next, we show that the optimal randomized classifier makes no mistakes and thus is strictly better. The randomized classifier is depicted in the right plot of Figure 3 with carefully chosen parameters r, α and it randomizes over h1, h2 uniformly at random. The geometry of the constructed randomized classifier is as follows. Data points A, B, C lie on the same line, and the length of segment AB and AC both equal d. The angle between line ABC and line h1 is α and h1 is tangent to the circle centered at point A with radius l. Note that these two conditions uniquely determine the position of the line h1. The parameters d, α, ρ will be determined later. Similarly, line h2 also rotates from line ABC with angle α and is tangent to the same circle. h1 and h2 intersect at point D. Note that D is outside

Sundaram, Vullikanti, Xu and Yao

the circle. The projection of point B to line h1 is E whereas the projection of point C to h1 is F. We start with some geometric calculation. First, the angle between ABC and h1 is α. Therefore, their normal vectors must also have angle α, which is precisely the angle between AD and the normal vector of h1, as depicted in the left plot. As a consequence, the length |AD| equals ρ cos α. Since |AB| = |AC|, we know that |BE|+|CF| = 2ρ. Moreover, |CF| |BE| = 2d sin α. This yields |BE| = ρ d sin α and |CF| = ρ + d sin α. For our construction, we will select parameters to satisfy the following conditions

|AD| = ρ cos α <

|BE| = ρ d sin α >

|CF| = ρ + d sin α >

There are many ways to pick the parameters to satisfy Equation (17). For example, it can be verified that ρ = 1.38, α = 0.05π and d = 2.23 will satisfy all these constraints. We now claim that the randomized classifier with any parameters satisfying the above constraints will make a perfect prediction. In particular, point A has the incentive to manipulate its feature to point D (or slightly beyond) because the point suffers a cost less than

2 by the first constraint in Equation (17), but now is able to make both classifiers to predict it with a positive label, increasing the prediction utility by

2. Moreover, point B does not have any incentive to manipulate its feature. This is due to the following reason. To get one of the classifiers to classify B with label 1, the manipulation cost is at least |BE|, which is strictly greater than

2/2 whereas the expected utility from prediction is

2/2 since only half of the time the randomized classifier will classify B as 1. On the other hand, to get the randomized classifier to always classify B as positive, the manipulation cost of B is at least the distance of B from h2, which equals |CF| >

2 by symmetry, whereas the benefit from classification outcome is only

2. As a consequence, point B does not have any incentive to manipulate its feature. Similarly, point C will not manipulate its feature as well. Overall, the randomized classifier makes a perfect prediction due to the manipulation of point A.

B.2 An Additional 1-d Example for Proposition 18

Now we present an additional example in 1-d without the requirement of the same r. We have four data points A = 1.0, B = 0.8, C = 0.8, D = 1.0 as depicted in Figure 4. Let r = 0 for B, C, r = 1.2 for A, and r = 1.2 for D. The cost function here is the Euclidean distance c(z; x) = |x z|. Both plots show exactly the same strategic classification instance, and all solid points have positive labels, whereas all other points have negative labels. The left plot draws the optimal deterministic classifier h = 2I[x 0] 1, and the right plot draws a randomized classifier that picks hyperline h1 = 2I[x 0.3] 1, h2 = 2I[x 0.3] 1 uniformly at random. First of all, we argue that any deterministic classifier cannot perfectly separate {A, B, C, D}. Otherwise, there exists an h that makes no mistake, which implies that it must have the form h = 2I[x θ] 1, θ ( 0.8, 0.8], as it can separate B and C perfectly. However, when

PAC-learning for Strategic Classification

θ ( 0.8, 0.8], the distance between h s decision boundary and one of A and D is at most 1.0 < r = 1.2. Therefore, at least one point in {A, D} wants to move across the decision boundary of h and the classification result cannot be perfect.

Figure 4: A strategic classification instance where randomized linear classifier beats any deterministic classifier. Cost function c(z; x) = |x z| is the Euclidean distance. Left: an optimal deterministic classifier. Right: a randomized classifier with perfect precision which picks hyperplane h1, h2 uniformly at random.

Next, we show that the randomized classifier {(h1, 0.5), (h2, 0.5)} shown in the right panel of Figure 4 makes no mistakes and thus is strictly better. First, it is obvious that {(h1, 0.5), (h2, 0.5)} outputs the true labels for data points B, C who do not have any incentive to deviate. For points A, D, their situations are symmetric when facing the classifier so we only need to show that A does not have enough incentive to manipulate its feature without loss of generality. In order to gain a positive utility, A needs to move across at least one decision boundary of the randomized classifier. However, since the distance between 0.3 and A = 1.0 exceeds 1.2, A can only move across 0.3. When A move across 0.3, it yields an expected utility of 0.6 = 0.5 1.2 which is less than the minimum moving cost 0.7 = 0.3 ( 1.0). As a result, A will stay put and accept the true classification result.

B.3 Proof of Proposition 21

The problem instance is constructed as follows. There are five labeled data points on R2, defined as (x0, x1, x2, x3, x4) = ((0, 0), (1, 1), ( 1, 1), ( 1, 1), (1, 1)), (y0, y1, y2, y3, y4) = ( 1, +1, +1, 1, 1). x1, x2, x3, x4 are non-strategic while x0 prefers to be labeled as +1 and can move within the region B = {(x, y) : x { 2, 2}, y [ 2, 1]}, as shown in Figure 5. First, we prove that any h H that perfectly separate {(xi, yi)}4 i=1 must incorrectly classify x0, so that the minimum empirical risk on H is at least 1

5. Suppose h = 2I(ax+by+ c 0) 1 is a linear classifier that perfectly separate {(xi, yi)}4 i=1. Since x1, x4 and x2, x3 both have opposite labels, ax + by + c = 0 must intersect with both segments [x1, x4) and [x2, x3) (with a slight abuse of notation, we use the notation [xi, xj) to represent the segment formed by endpoints xi, xj with xj excluded). Assume the two intersection points are (1, p) and ( 1, q), where p, q ( 1, 1]. Thus, h can be written as 2I((p q)x 2y +p+q 0) 1 and h intersects the two lines x = 2, x = 2 at z1 = ( 2, p+3q

2 ) and z2 = (2, 3p q

2 ). We claim that at least one of z1, z2 lies in B, because:

1. p, q ( 1, 1], we have p+3q

2 > 2, 3p q

2. note that p+3q

2 = p + q 2, at least one of p+3q

2 is not greater than 1.

Sundaram, Vullikanti, Xu and Yao

Thus, at least one of p+3q

2 falls in ( 2, 1], meaning at least one of z1, z2 lies in B. Suppose z1 B, as shown in Figure 5a. Consequently, x0 can always move to z1 and be classified as +1 against its true label. Therefore, any h H makes at least one mistake on the data set {(xi, yi)}4 i=0, and we conclude that the minimum empirical risk on H is at least 1

Next, we construct a randomized classifier H H and show that H attains an empirical risk smaller than 1

5. Let h1 = 2I(4x+7y 2 0) 1, h2 = 2I( 4x+7y 2 0) 1, and H = {(h1, 0.5), (h2, 0.5)}, as shown in Figure 5b. It s easy to see that H still perfectly separates x1, x2, x3, x4, and x0 can manipulate its feature to mislead either h1 or h2. However, since the region {(x, y) : h1(x, y) = 1, h2(x, y) = 1} does not intersect with B, x0 cannot alter its feature to mislead both h1 and h2. This implies H will correctly classify x0 as 1 with probability 0.5. Thus, the empirical risk of H is 1

5, which concludes the proof.

(a) Any deterministic linear classifier that perfectly separates {x1, x2, x3, x4} must intersect with x0 s manipulation region B. As a result, x0 can always move to a point in B and thus be misclassified.

(b) We can construct a randomized classifier H = {(h1, 0.5), (h2, 0.5)} such that H not only correctly separates x1, x2, x3, x4 but also classifies x0 to its true label (+1) with probability 0.5.

Figure 5: A zero-manipulation-cost strategic classification instance where a randomized classifier beats all deterministic classifiers. Data points x1, x2 have true label +1 and x0, x3, x4 have true label 1. x0 is the only strategic point and its manipulation region B contains two segments marked with dashed lines. Left: any deterministic classifier incurs an empirical risk at least 1

5. Right: there exists a randomized classifier that obtains a better empirical risk 1 10.

Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 6 25, 2021.

Emrah Akyol, Cedric Langbort, and Tamer Basar. Price of transparency in strategic machine learning. ar Xiv, pages ar Xiv 1610, 2016.

PAC-learning for Strategic Classification

Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. In Advances in Neural Information Processing Systems, pages 1169 1177, 2013.

Pranjal Awasthi, Abhratanu Dutta, and Aravindan Vijayaraghavan. On robustness to adversarial examples and polynomial optimization. In Advances in Neural Information Processing Systems, pages 13737 13747, 2019.

Yahav Bechavod, Katrina Ligett, Zhiwei Steven Wu, and Juba Ziani. Causal feature discovery through strategic modification. ar Xiv preprint ar Xiv:2002.07024, 2020.

Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML 12, page 1467 1474, Madison, WI, USA, 2012. Omnipress. ISBN 9781450312851.

Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pages 387 402. Springer, 2013.

Mark Braverman and Sumegha Garg. The role of randomness and noise in strategic classification. In 1st Symposium on Foundations of Responsible Computing (FORC 2020). Schloss Dagstuhl-Leibniz-Zentrum f ur Informatik, 2020.

Michael Br uckner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 547 555, 2011.

Miles Bryan and Keystone Crossroads. Coronavirus unemployment benefits are high, putting workers and employers at odds. https://whyy.org/articles/coronavirusunemployment-benefits-are-high-putting-workers-and-employers-at-odds/.

N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pages 39 57, 2017.

Yiling Chen, Chara Podimata, Ariel D. Procaccia, and Nisarg Shah. Strategyproof linear regression in high dimensions. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC 18, page 9 26, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450358293. doi: 10.1145/3219166.3219175. URL https://doi.org/10.1145/3219166.3219175.

Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers. Advances in Neural Information Processing Systems, 33, 2020.

Danielle Keats Citron and Frank A. Pasquale. The scored society: Due process for automated predictions. 2014.

COVID. Covid-19 testing overview. https://www.cdc.gov/coronavirus/2019ncov/symptoms-testing/testing.html.

Sundaram, Vullikanti, Xu and Yao

Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 230 241. Curran Associates, Inc., 2018.

Ofer Dekel, Felix Fischer, and Ariel D Procaccia. Incentive compatible regression learning. Journal of Computer and System Sciences, 76(8):759 777, 2010.

Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC 18, page 55 70, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450358293. doi: 10.1145/3219166. 3219193. URL https://doi.org/10.1145/3219166.3219193.

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu. Agnostic learning of monomials by halfspaces is hard. SIAM Journal on Computing, 41(6):1558 1590, 2012.

Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR 2015 : International Conference on Learning Representations 2015, 2015.

Bryce Goodman and Seth Flaxman. EU regulations on algorithmic decision-making and a right to explanation , 2016. URL http://arxiv.org/abs/1606.08813. Presented at 2016 ICML Workshop on Human Interpretability in Machine Learning (WHI 2016), New York, NY.

Aniko Hannak, Gary Soeller, David Lazer, Alan Mislove, and Christo Wilson. Measuring price discrimination and steering on e-commerce web sites. In Proceedings of the 2014 conference on internet measurement conference, pages 305 318, 2014.

Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS 16, page 111 122, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450340571. doi: 10.1145/2840728.2840730. URL https://doi.org/10.1145/2840728.2840730.

Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 259 268, 2019a.

Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* 19, page 259 268, New York, NY, USA, 2019b. Association for Computing Machinery. ISBN 9781450361255. doi: 10.1145/3287560.3287597. URL https://doi.org/10.1145/3287560.3287597.

PAC-learning for Strategic Classification

Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. 2018 IEEE Symposium on Security and Privacy (SP), pages 19 35, 2018.

Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 825 844, 2019.

Bo Li and Yevgeniy Vorobeychik. Feature cross-substitution in adversarial classification. In Advances in neural information processing systems, pages 2087 2095, 2014.

John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. ar Xiv, pages ar Xiv 1910, 2019.

Smitha Milli, John Miller, Anca D. Dragan, and Moritz Hardt. The social cost of strategic classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* 19, page 230 239, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450361255. doi: 10.1145/3287560.3287576. URL https://doi.org/10.1145/3287560.3287576.

Mehryar Mohri and Andres Munoz. Revenue optimization against strategic buyers. In Advances in Neural Information Processing Systems, pages 2530 2538, 2015.

S. Moosavi-Dezfooli, A. Fawzi, O. Fawzi, and P. Frossard. Universal adversarial perturbations. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 86 94, 2017.

M. Mozaffari-Kermani, S. Sur-Kolay, A. Raghunathan, and N. K. Jha. Systematic poisoning attacks on and defenses for machine learning in healthcare. IEEE Journal of Biomedical and Health Informatics, 19(6):1893 1905, 2015.

Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.

Parag A Pathak. What really matters in designing school choice mechanisms. Advances in Economics and Econometrics, 1:176 214, 2017.

Javier Perote and Juan Perote-Pe na. Strategy-proof estimators for simple regression. Math. Soc. Sci., 47:153 176, 2004.

Alvin E Roth. What have we learned from market design? Innovations: Technology, Governance, Globalization, 3(1):119 147, 2008.

Benjamin I.P. Rubinstein, Blaine Nelson, Ling Huang, Anthony D. Joseph, Shing-hon Lau, Satish Rao, Nina Taft, and J. D. Tygar. Stealthy poisoning attacks on pca-based anomaly detectors. SIGMETRICS Perform. Eval. Rev., 37(2):73 74, October 2009. ISSN 0163-5999. doi: 10.1145/1639562.1639592. URL https://doi.org/10.1145/1639562. 1639592.

Sundaram, Vullikanti, Xu and Yao

Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.

Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. In Hal Daum e III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8676 8686, 2020.

Tearsheet. Gaming the system: Loan applicants are reverse engineering the online lending algorithms. https://tearsheet.co/data/gaming-the-system-online-loan-applicants-arereverse-engineering-the-algorithms/.

Stratis Tsirtsis, Behzad Tabibian, Moein Khajehnejad, Adish Singla, Bernhard Sch olkopf, and Manuel Gomez-Rodriguez. Optimal decision making under strategic behavior. ar Xiv preprint ar Xiv:1905.09239, 2019.

Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 10 19, 2019.

Arsenii Vanunts and Alexey Drutsa. Optimal pricing in repeated posted-price auctions with different patience of the seller and the buyer. In Advances in Neural Information Processing Systems, pages 939 951, 2019.

Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010.

Jane Williams and Bridget Haire. Why some people don t want to take a covid-19 test. https://theconversation.com/why-some-people-dont-want-to-take-a-covid-19-test141794.

Hanrui Zhang and Vincent Conitzer. Incentive-aware pac learning. AAAI 2021, 2021.

Hanrui Zhang, Yu Cheng, and Vincent Conitzer. Distinguishing distributions when samples are strategically transformed. In Advances in Neural Information Processing Systems, pages 3193 3201, 2019a.

Hanrui Zhang, Yu Cheng, and Vincent Conitzer. When samples are strategically selected. In International Conference on Machine Learning, pages 7345 7353, 2019b.