# strategic_classification_with_unknown_user_manipulations__26b495b4.pdf

Strategic Classification with Unknown User Manipulations

Tosca Lechner 1 Ruth Urner 2 Shai Ben-David 1 3

In many human-centric applications for Machine Learning instances will adapt to a classifier after its deployment. The field of strategic classification deals with this issue by aiming for a classifier that balances the trade-off between correctness and robustness to manipulation. This task is made harder if the underlying manipulation structure (i.e. the set of manipulations available at every instance) is unknown to the learner. We propose a novel batch-learning setting in which we use unlabeled data from previous rounds to estimate the manipulation structure. We show that in this batch-learning setting it is possible to learn a close to optimal classifier in terms of the strategic loss even without knowing the feasible manipulations beforehand. In line with recent advances in the strategic classification literature, we do not assume a best-response from agents but only require that observed manipulations are feasible.

1. Introduction

Consider the following scenario: a college or university has large amounts of records of students who at some point applied to the school, got admitted and then either succeeded or failed at obtaining a degree. Based on these records, the university sets (and publishes) admission criteria with the intent to admit students that are likely to successfully graduate. It then receives a set of applications for admission for the next year, some of which will lead to admission. In the next year (and upcoming years), the university will need to set and publish admission criteria again, its aim still being to attract and admit students that are likely to succeed. This scenario differs from a classic (statistical) decision-making setup in several ways: first, the entities

1Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada 2Lassonde School of Engineering, EECS Department, York University, Toronto, Ontario, Canada 3Vector Institute, Toronto, Ontario, Canada. Correspondence to: Tosca Lechner <tlechner@uwaterloo.ca>.

Proceedings of the 40 th International Conference on Machine Learning, Honolulu, Hawaii, USA. PMLR 202, 2023. Copyright 2023 by the author(s).

that decisions are to be made for are human beings, and as such may actually adapt their application materials (as best as they can) to fit the published admission criteria. The decision maker may not know in advance in what ways the applicants can modify their credentials to get accepted. In addition, when it is time to publish a decision rule for the next round, the decision maker does not have feedback on the quality of last year s admission yet (since students usually take several years before they graduate or leave school without a degree). Thus the only information about the results from the last published decision rule was the set of (potentially strategically modified) applications.

Many human-centric real-life applications of machine learning, such as decisions on loan applications or bail recommendations, share characteristics with the above sketched scenario: there is a need for transparent classification and therefore a need (or maybe even a legal requirement) of publishing the decision rule to be used. This requirement for transparency, while in most scenarios well justified, has the effect that individuals might use this knowledge to adapt to or game the rules, i.e. they might change their feature vectors strategically in order to receive a desired outcome from the published classifier. However, this change of features often does not correspond to a change in their ground-truth label. Such feature manipulations then yield a loss in accuracy of the learned classifier after its publication. Moreover, often by the time the next round of decision making is due, the outcomes from the previous rounds are not known yet. That is, in addition to some labelled data to start with, a learner has access only to unlabelled data that potentially contains manipulated features in subsequent rounds.

The field of strategic classification, first proposed by Hardt et al (Hardt et al., 2016), studies the phenomenon of learning classifiers which are robust to strategic manipulations. The goal in strategic classification is to design a decision rule which is accurate as well as designed to withstand feature manipulations. There are two main motivations for discouraging such feature changes: either manipulated instances will be misclassified after the manipulation (resulting in false positives) or true positive instances are forced to misrepresent themselves in order to be classified correctly. This second consideration is also known as social burden (Milli et al., 2019) as individuals typically face a cost for this.

Strategic Classification with Unknown User Manipulations

It is a common assumption in the strategic classification literature, that the manipulation structure is known in terms of either a cost-of-manipulations function or a manipulation graph (the set of possible manipulations for each instance) and considers the strategic classification setup as a one-time decision making problem. However such knowledge of the feature manipulation capabilities is not always available, in particular not with exact accuracy. Furthermore, in most decision making setups where a decision rule (classifier) is learned from available data, the decision making is not a one-time event, but rather the learned decision rule is to be repeatedly employed over a long time, and ideally updated to adapt to potential changes in the data generation. In this work, we focus on the scenario where such changes are (only) the result of strategic feature adaptations to the published decision rules.

We propose a novel formalization of this batch-learning setting for strategic classification. In our framework, learning and data-generation proceed in rounds. Initially, the learner receives a labeled sample S0 from some underlying (unmanipulated) distribution. Given this sample of labeled data, the learner decides on (and publishes) a classifier h0. From then on, in each round t, the learner receives an unlabeled sample from the same data distribution, with the caveat that the features were strategically manipulated in response to ht 1. The learner then decides on classifier ht, based on labeled data sample S0 and unlabeled samples S1, S2, . . . St 1. While the learner does not have access to the underlying feature manipulation capabilities of the instances, we assume that the true manipulation structure is a member of a class of possible such structures (graphs). We show that by exploiting the observed distribution shift in this batch-learning setting it is possible to learn the optimal classifier in terms of the so-called strategic loss (Lechner & Urner, 2022) even without knowing the underlying manipulation capabilities. For a wide range of combinations of hypothesis classes H and manipulation graph classes G, we provide first positive results and analysis in this learning setup. More specifically, we derive bounds on sufficient sample sizes as well as the number of rounds for the learner to produce a classification rule with low loss. We focus in particular on graph classes which are totally ordered by inclusion, which captures the case in which it is unknown how manipulation costs compare to the value of being classified with the desired label. We show that in these cases batch-learning is possible if the VC-dimension of the lossclass of (G H) is finite. Roughly, the finiteness of the VC-dimension of the loss class, makes it possible to successfully estimate the distribution shift caused by a deployed hypothesis. The total order on the manipulation graphs allows to use this information to do a binary search on a discretized version of the hypothesis class.

Lastly, we show that for totally ordered G and H with finite

VC-dimension it is possible to successfully improperly learn H with respect to G in the robustly realizable case with only access to unmanipulated data. In order to achieve this last result, we introduce a new paradigm, called maximally robust empirical risk minimization (MRERM) and use it to recreate the compression argument from (Montasser et al., 2019). MRERM picks a hypothesis that is robust with respect to the maximal graph that allows for robust realizability of the sample, in case such a maximal graph exists. However, such a maximal graph may not exist in some finite VC classes. We use the set-theoretic concept of ultrafilters to define an extension of the hypothesis class that is guaranteed to have an MRERM for every realizable sample and has the same VC dimension as our original class.

1.1. Related Work

The concern that learning outcomes might be compromised when agents adapt their feature vectors in response to published classification rules was first pointed out over a decade ago (Dalvi et al., 2004; Br uckner & Scheffer, 2011). The area has received substantial interest from the research community in recent years, both in the context of adversarial robustness (Feige et al., 2015; Cullina et al., 2018; Montasser et al., 2019; 2021) and robustness to strategic feature manipulations. Hardt et al. formally introduced the setup where agents aim to improve their decision outcomes and termed it strategic classification (Hardt et al., 2016). In addition to the cost of induced misclassification, previous work has pointed out that changes to the decision boundary aiming to prevent false positives, may force true positive instances to manipulate their features for retaining their positive classification. This (also undesirable) effect has been summarized under the concept of social burden (Milli et al., 2019; Jagadeesan et al., 2021). It has also been shown that the cost of social burden might be disproportionately paid by underrepresented or disadvantaged sub-groups of a population (Milli et al., 2019; Hu et al., 2019). Recent work on strategic classification has pointed out that strategic feature modification can also be a positive effect, for example when applicants respond by studying better for tests and learning specific skills (Haghtalab et al., 2020), and addressed this phenomenon through a causality lense (Miller et al., 2020; Tsirtsis & Rodriguez, 2020; Shavit et al., 2020). Some recent works have further explored this interplay between gaming and improvement (Chen et al., 2021) and aligned incentives (Levanon & Rosenfeld, 2022).

While many previous studies in this area have taken a game theoretic perspective, some recent work has analyzed strategic classification in a PAC learning framework (Zhang & Conitzer, 2021; Sundaram et al., 2021; Lechner & Urner, 2022). Similarly, our work follows a new trend of not requiring agents to be cost-minimizing agents (Jagadeesan et al., 2021; Chen et al., 2020), as there is a potential limit

Strategic Classification with Unknown User Manipulations

of the rationality of agents (Jagadeesan et al., 2021). In the PAC learning setting, the consideration of irrational agents is modelled by capturing the sets of possible manipulations in the manipulation graph (Zhang & Conitzer, 2021), which only distinguishes between feasible and infeasible manipulations. Using this notion of manipulation graph the objectives of discouraging strategic manipulations for the sake of avoiding misclassification and avoiding contributions to social burden have been jointly modelled in a loss function, the strategic loss (Lechner & Urner, 2022). We adopt this notion of loss and frame our learning goals in terms of the strategic loss function.

There has been some recent work on learning with respect to unknown manipulation structures in an online setting (Dong et al., 2018). The first results in this line of research was given in form of regret bounds for linear classifiers under the assumption that only instances of one label would manipulate (Dong et al., 2018). Similarly, Ahmadi et al introduce a version of the perceptron algorithm which takes possible feature manipulations into account (Ahmadi et al., 2021). They show finite mistakes bounds for their algorithm for both known and unknown cost functions under a linear separability assumptions, which is akin to our strategically robust realizability assumption. Both works (Dong et al., 2018; Ahmadi et al., 2021) do not require any knowledge of unmanipulated data in their setting but assume immediate label feedback for each (possibly manipulated) classified instance. Thus their results are complementary to our results in the strategic realizable case where we achieve robustness without having access to manipulated data. Furthermore, both works assume that agents are cost-minimizing, i.e., best-response. We also note that the notion of loss in those settings is slightly different, as they do not incorporate the notion of social burden into their success criterion. In the strategic PAC learning setting, there are known sufficient conditions for the strategic loss to be robust with respect to inaccuracies on the assumed manipulation structure (Lechner & Urner, 2022). Furthermore, PAC-learnability guarantees been shown with respect to an unknown manipulation (or perturbation) structure in both strategic classification (Lechner & Urner, 2022) and in adversarially robust classification (Montasser et al., 2021) with the assumption of an additional oracle. Both of these works require an oracle access that might be unrealisitic in real-world settings. While the oracle in the latter is more realistic and no further assumptions on the perturbation sets are needed, these learning guarantees additionally require the Littlestone dimension of the hypothesis class being used to be finite. This assumption is not fulfilled by most classes we consider in this paper (e.g., the simple class of thresholds classifiers as well as general finite VC-classes).

Finally, our framework bears some similarities with the setting of lifelong learning (Pentina & Lampert, 2014; Pentina

& Ben-David, 2015; Balcan et al., 2015; Pentina & Urner, 2016; Balcan et al., 2020). In lifelong learning, a learning algorithm aims to perform well and adapt to a stream of related, but not identical learning tasks. Our setup distinguishes itself from standard lifelong learning goals in that the changes in input data are actually induced by the published decision rules from the previous round, while the actual target task remains the same.

1.2. Overview on our results

We consider a novel strategic batch-learning problem in which the manipulation graph is learned alongside the classification rule in order to achieve optimal classification (Definition 2.5). Importantly, we only assume prior knowledge of a graph class G which contains the true manipulation graph, but not exact knowledge of the true manipulation graph. We propose a formal learning protocol (Definition 2.2) and success criterion (Definition 2.5) for this setup and show that learning in this setting is possible for a wide variety of hypothesis classes H and graph classes G.

In Section 3 we present possibility results for proper learning under the strategic batch learning protocol. As a warmup, and to illustrate the intuition behind our techniques for a simple class, we start in Subsection 3.1 with presenting an algorithm (Algorithm 3.1) for the hypothesis class of thresholds and the class of manipulation graphs which allow manipulations within a fixed radius (while the radius of the underlying true manipulation graph is not known). We then show that this algorithm has sample complexity O( log( 1

δ ) ϵ2 ) and round complexity O(1) in the (robustly) re-

alizable case, as well sample complexity O( log( 1

δϵ ) ϵ2 ) round complexity O(log( 1

ϵ )) in the agnostic case (Observation 3.1 and Theorem 3.2).

In Subsection 3.2, we then move on to analyse proper strategic batch learning for general VC-classes. First, we show that if the joint loss class of some G H with respect to the manipulation loss ℓmani (Definition 2.4) is finite, we can learn the manipulation structure for a particular hypothesis from H (Lemma 3.6 and Observation 3.7). We then use this to show a general learnability result for the strategic batch setting for classes with finite VC((G H)ℓmani) and finite VC(H). We furthermore give a generalization of Algorithm 3.1 in Algorithm 3.2 that works for arbitrary hypothesis classes H (with finite VC((G H)ℓmani) = d1 and finite VC(H) = d2) and totally ordered graph classes G. We show

that this algorithm has sample complexity O( d1+d2+ 1

δ ϵ2 ) and round complexity O(1) in the realizable case (Observation 3.10) and sample complexity O( d1+d2+ 1

δϵ ϵ2 ) and round complexity O(log( 1

ϵ )) in the agnostic case (Theorem 3.11).

Finally, we also explore a more general, non-proper learning setup for cases where VC((G H)ℓmani) is not necessarily

Strategic Classification with Unknown User Manipulations

finite. In Section 4, we note that there are classes H of finite VC-dimension for which this VC((G H)ℓmani) is not finite despite G being totally ordered and which cannot be learned with respect to such G by any proper learner. Extending techniques from the literature on learning under adversarial perturbations (Montasser et al., 2019), we show that every H with finite VC-dimension can be improperly learned with respect to any totally ordered graph class G in the realizable setting (Theorem 4.2), even if the actual underlying manipulation structure is not available to the learner.

Due to space limitations, we defer all technical proofs to the Appendix.

Basic learning theoretic notions We start by providing some general notation. We adopt standard notation and terminology for machine learning concepts (Shalev-Shwartz & Ben-David, 2014). We consider a classification task given by an unknown ground-truth distribution P over X {0, 1}. We use the notation PX to denote the marginal of P over the feature space X. We denote the set of all finite sequences of feature vectors (eg. samples from P m X ) by X , and the set of all finite sequences of labeled feature vectors (eg. samples from P n) by (X {0, 1}) . As is standard in PAC-type learning guarantees the learner is evaluated with respect to a fixed hypothesis class H F = {0, 1}X . The performance of a hypothesis is evaluated by means of a loss function ℓ: H X {0, 1} R, and the goal is to learn a hypothesis h with small expected loss LP (h) = E(x,y) P [ℓ(h, x, y)]. The approximation error of H with respect to loss ℓon distribution P is opt P (H) = infh H LP (h), and it indicates how suitable class H is for task P. We use superscripts to identify specific loss functions. The standard (binary) classification loss is denoted as ℓ0/1 (and L0/1 P (h) denotes the corresponding expected loss). A (standard) learner is a function A : (X {0, 1}) {0, 1}X that takes in a labelled sample and outputs a hypothesis. The requirement for learnability of a class H with loss function ℓin the PAC framework (Valiant, 1984) is the existence of function m : (0, 1)2 N, and a learner A such that, for all ϵ, δ (0, 1), and all m m(ϵ, δ) we have

PS P m[LP (A(S)) opt P (H) + ϵ] 1 δ.

It is well known, that a binary hypothesis class is PAClearnable with respect to loss ℓ0/1 if and only if its VCdimension is finite (Blumer et al., 1989; Vapnik & Chervonenkis, 1971). Learnability in the realizable setting refers to the above guarantee under the additional condition that opt P (H) = 0. And a learner A is called a proper learner for H if A(S) H for all samples S (X {0, 1}) .

Strategic classification In strategic classification, individuals (modelled as the members of the domain X) will try to receive a preferred label (here y = 1) by manipulating their feature vectors according to some admissible manipulation. We model the set of admissible feature manipulations as a manipulation graph g = (X, Eg), where a manipulation from x to x is admissible if and only if the (directed) edge (x, x ) exists in Eg. We will denote the neighborhood set of a point x X according to graph g by Bg(x) = {x X : (x, x ) Eg}. We will denote the true manipulation graph by g . We do not assume this graph to be known during the learning process. Rather, we assume the learner has prior knowledge of some graph class G such that g G. The class of all manipulation graphs will be denoted by Gall.

We assume, that if an admissible manipulation for the preferred label (i.e. the label 1) is available to an instance x given a published classifier h, then some manipulation to a positively labeled instance will occur. However, we do not assume that this is necessarily a best-response manipulation, in the sense that the instance will move as far as possible . The following definition formalizes this notion of classifier induced manipulations for a sample of instances.

Definition 2.1 (Classifier induced manipulation of a sample). Let g be a manipulation graph and h be a hypothesis. We say π : X X is a (g, h)-induced manipulation if

= x if h(x) = 1 or Bg(x) h 1(1) = Bg(x) h 1(1) if h(x) = 0 and Bg(x) h 1(1) =

Now for a labeled sequence S = ((x1, y1), . . . , (xm, ym)) of instances and sequence Π = (π1, . . . , πm) of (g, h)-induced manipulations π1, . . . , πm, we define the Π-manipulated sample SΠ = ((π1(x1), y1), . . . (πm(xm), ym)). Similarly for an unlabeled sample S = (x1, x2, . . . xm), the Π-manipulated sample is defined by SΠ = (π1(x1), . . . πm(xm)).

Note that the above definition allows for repeated feature vectors xi = xj (with i = j) in the sequence S to move to differing manipulated instances πi(xi) = πj(xj). For simplicity, we will often just refer to the sequence Π as a (g, h)-induced manipulation without specifically referring to its components π1, . . . , πm.

To model repeated decision-making scenarios (such as the university admission task outlined in the introduction), we introduce a formal batch-learning protocol. In our protocol, a learner receives one non-manipulated labelled sample from the distribution, publishes an initial hypothesis ˆh0, and then, in each round t, successively observes strategically

Strategic Classification with Unknown User Manipulations

manipulated (but unlabeled) samples in response to the last published hypothesis ˆht 1. Recall that we denote the true underlying manipulation graph by g .

Definition 2.2 (Strategic batch-learning protocol). Let (mi)i N be a sequence of sample sizes, mi N.

Round 0: The learner receives a labeled sample S P m0 and, in response, publishes classifier ˆh0 : X {0, 1}.

Round t for t 1: The learner receives an unlabeled sample S = SΠ X mt, which is a Π-manipulated version of some an unlabeled sample S P mt X , where Π is a (g , ˆht 1)-induced manipulation. In response, the learner publishes classifier ˆht.

We call a learner A that operates according to the above protocol, a strategic batch learner. Note that the learner receives only one labeled sample from the data-generating process, in the first round. And the only information about the underlying manipulation structure g it receives, are the unlabeled, manipulated samples in the subsequent rounds.

The goal is to output a hypothesis with low strategic loss:

Definition 2.3 (Strategic Loss (Lechner & Urner, 2022)). For a given manipulation graph g, the strategic loss ℓg : F X Y {0, 1} is defined by

ℓg(h, x, y) =

1 if h(x) = y 1 if h(x) = 0 and Bg(x) h 1(1) = 0 otherwise.

That is, a classifier h suffers strategic loss 1, if it misclassifies an instance (x, y), or if it assigns label 0 to x while there exists an admissible manipulation x for x with h(x ) = 1. The following loss captures the second condition only:

Definition 2.4 (Manipulation Loss). The manipulation loss ℓmani : Gall F X {0, 1} is defined by

ℓmani(g, h, x) =

1 if h(x) = 0 and Bg(x) h 1(1) = 0 otherwise

We note that for a fixed manipulation graph g, the manipulation loss ℓmani(g, , ) corresponds to the strategic component loss defined in (Lechner & Urner, 2022). Moreover, ℓg(h, x, y) ℓmani(g, h, x) + ℓ0/1(h, x, y).

We now define our success criterion for a strategic batch learner:

Definition 2.5. A strategic batch learner A is said to learn hypothesis class H under graph class G with sample complexity m G,H : (0, 1)2 N and round complexity

TG,H : (0, 1)2 N, if for every ϵ, δ 0, and every P over X {0, 1} and every true manipulation graph g G, after T = T(ϵ, δ) many rounds, A outputs hypothesis h T satisfying Lg

P (h T ) infh H Lg

P (h ) + ϵ, with probability at least (1 δ) over the sample generation.

We say a learner A is a successful strategic batch learner in the realizable case with sample complexity mreal G,H and round complexity T real G,H, if it satisfies the above criterion for all distributions P P , where P denotes the set of all distributions over X {0, 1} with infh H Lg

P (h ) = 0.

We call the learner A proper for a hypothesis class H if it only outputs hypotheses ht H from the class H (in every round t).

3. Proper Batch Learning

3.1. Class of Thresholds

We start by showing that learning with respect to an unknown manipulation graph for the hypothesis class of thresholds with a simple graph class is possible. Consider X = R. The class of thresholds is defined as Hthres = {ha,0 : R {0, 1} : ha,0(x) = 1 iff x > a} {ha,1 : R {0, 1} : ha,1(x) = 1 iff x a}. We now look at the graph class consisting of fixed-radius manipulation graphs gr, which for any x has outgoing edges to every x with x x r, i.e. Gf.r. = {gr = (R, Er) : (x, x ) Er iff x x + r}.

We show that for this simple class there can be indeed a successful strategic batch-learner. We first note that under the robust realizability assumption, the learner only needs one round to learn a close to optimal classifier and does not require access to any manipulated samples.

Observation 3.1. The Strategic Batch-Learning for Thresholds Algorithm (Algorithm 1) is a proper learner for the strategic-batch learning problem for Hthres and Gf.r. in the realizable case with sample complexity mreal H,G = O( log( 1

δ ) ϵ2 ) and round complexity T real H,G = 1.

Next, we show that there also is an algorithm that solves the strategic-batch learning problem for these classes in the agnostic case.

Theorem 3.2. The Strategic Batch-Learning for Thresholds Algorithm (Algorithm 1) is a proper learner for the strategic-batch learning problem for Hthres and Gf.r. in the hypothesis-agnostic case with sample complexity m H,G =

δϵ ) ϵ2 ) and round complexity TH,G = O(log( 1

This is achieved by Algorithm 1 (formal proofs are provided in the appendix). In the first step the algorithm uses the labelled sample S0 to generate candidate graphs (which are stored as an ordered list G0), in such a way that the sample losses on S0 for the corresponding optimal hypotheses in-

Strategic Classification with Unknown User Manipulations

Algorithm 1 Strategic Batch-Learning for Thresholds

1: Input: parameters ϵ, ϵ

2: receive sample S0 P m

3: L0/1 0 infh Hthres L0/1 S0 (h ) 4: for i = 0, . . . , 1

5: ri max{r : infh Hthres Lgr S0(h ) = L0/1 0 + i ϵ} 6: end for 7: G0 [gr0, gr1, . . . , gr 1

8: ˆh0 argminh Hthres L gr0 S0 (h )

9: publish ˆh0

10: receive sample S1, where S 1 P m and S1 = SΠ1 1 for some sequence of (g , ˆh0)-induced manipulations Π1. 11: rmax max{r : gr G0 and Lmani S1 (gr, ˆh0) = 0}

12: rmin min{r : gr G0 and Lmani S0 (gr, ˆh0) Lmani S0 (grmax, ˆh0) ϵ and Lmani S1 (g, ˆh0) = 0} 13: G1 {gr G0 : r [rmin, rmax]}

14: k1 = |G1|

2 15: ˆg1 G1[k1], where G[k] refers to the k-th element of G 16: ˆh1 arg minh H Lˆg1

S0(h) 17: for rounds t = 2, . . . , T do 18: publish ˆht 1

19: receive sample St, where S t P m and St = SΠt t for some sequence of (g , ˆht 1)-induced manipulations Πt. 20: Gt {g Gt 1 : Lmani St (g, ˆht 1) = 0}

21: Gt 0 {g Gt : Lmani S0 (g, ˆht 1) maxg Gt Lmani S0 (g , ˆht 1) ϵ } 22: if ˆgt 1 Gt 0 then 23: Gt [Gt[0], . . . , Gt[kt 1]] Gt 0 24: else 25: Gt Gt 0 26: end if 27: kt |Gt|

2 28: ˆgt Gt[kt]

29: ˆht minh H Lˆgt

S0(h) 30: end for

creases in ϵ-steps. Choosing an appropriate sample size, we can guarantee that S0 is ϵ-representative in terms of strategic loss ℓg for all g Gf.r.. That is, the observed sample losses on S0 are ϵ-close to the corresponding expected losses according to distribution P. This then guarantees that optimizing the sample loss for one of the generated candidates yields a close-to-optimal hypothesis on the ground-truth distribution.

We further use the fact, that for any h Hthres, any distribution P over X {0, 1} any sample S and any radii r1 r2, we have that L gr1 P (h) L gr2 P (h) as well as L gr1 S (h) L gr2 S (h). Now let gt 1 = gr be the current candidate graph. Then the algorithm publishes a hypothesis ht 1 = argminh Hthres Lgt 1

S0 . There are two possibilities: (1) Lg

S0 (ht 1) and Lg

P (ht 1) are significantly higher than

S0 (ht 1). Therefore we have r < r . Furthermore, with high probability, we will observe a manipulated sample St which was manipulated more than gt 1 would predict. Thus, gt 1 would not be in the updated sets of candidate graphs Gt 0 consistent with the observed St. Similarly graphs gr with r < r are eliminated from the candidate set. (2) Lg

S0 (ht 1) and Lg

P (ht 1) are not significantly higher than

S0 (ht 1). In this case, the observed sample St would be consistent with the current gt 1. In this case all candidate graphs gr with r < r are eliminated from the candidate set. In the case in which r > r , this obviously does not pose a problem. Now consider the case in which r < r . Then for h = arg minh Hthres Lg (h) we have that Lgr P (h ) Lgr P (h ). Now assuming that S0 is ϵ - representative for P with respect to Hthres and loss ℓg for every g Gg.r., then Lgr P (ht 1) Lgr S0(ht 1) + ϵ Lgr S0(h ) + ϵ Lgr P (h ) + 2ϵ Lg

P (h ) + 2ϵ . Thus, in this case, despite r < r , the selected hypothesis is still close to optimal in terms of ℓg . Thus, the elimination of graphs with radius greater than r does not hinder success. Thus, the distinction of the two cases can be exploited by the algorithm to do a binary search on the candidate set.

We also note that the way the candidate hypotheses are picked, we always pick the maximal radius for a given sample loss. This leads to corresponding maximally robust hypotheses, allowing for the first hypotheses to be successful in the realizable case as shown in Observation 3.1.

3.2. General VC-Classes

We will now show that similar learning guarantees in our strategic batch learning setup are possible for more general hypothesis classes and graph classes. We start by addressing the problem of estimating the manipulation graph from two unlabeled samples, an un-manipulated and a manipulated sample, from the marginal distributions. To this aim, we define the loss class of the Cartesian product of a hypothesis

Strategic Classification with Unknown User Manipulations

class H and a graph class G.

Definition 3.3. The loss class of G H with respect to ℓmani is defined as

(G H)ℓmani =

{{x X : ℓmani(g, h, x) = 1} : g G and h H}

Furthermore for a fixed h let the class Gℓmani,h be defined as

Gℓmani,h = {{x X : ℓmani(g, h, x) = 1} : g G}

We will define VC(Gℓmani,H) = suph H VC(Gℓmani,h).

Observation 3.4. The VC-dimension of (Gf.r. Hthres)ℓmani is 2.

Let Hhalf = {hw : w Rd : hw(x) = 1 iff x T w 0} the hypothesis class of linear half spaces and Gd f.r. = {gr = (X, Egr) : (x, x ) Egr iff ||x x ||2 r} be the class of fixed-radius balls in Rd. Then the VC dimension of (Gd f.r. Hhalf)ℓmani is at most 2d.

We can now use this definition to derive a sample complexity bound for estimating the region of manipulation for any particular h H from one manipulated and one un-manipulated sample. We use the following notion of disagreement between two manipulation graphs:

Definition 3.5. Given a distribution D over a domain set X (a.k.a. a marginal distribution), a classifier h and two manipulation graphs, g, g

Dis(D,h)(g, g ) =

D[{x X : ℓmani(g, h, x) = ℓmani(g , h, x)}]

Lemma 3.6. Let G, H be such that VC(Gℓmani,H) = d. Let Agraph : X X H 2G be a learner following the Empirical Manipulation Estimation Paradigm (as defined in Algorithm 2 ). Then Agraph has the following success guarantee for learning the manipulation graph:

For every marginal distribution PX , every g G, every h H and every sequence of (g , h)-induced manipulations Π, and every ϵ, δ (0, 1),

if m C d+log( 1

δ ) ϵ2 (for some universal constant C) with probability at least (1 δ), over samples S1 P m X , S2 P m X , for every ˆg Agraph(S1, SΠ 2 , h),

Dis(PX ,h)(g , ˆg) ϵ.

and g Agraph(S1, SΠ 2 , h).

The key tool for proving the above lemma is the notion of a sample S1 being ϵ-representative with respect to (G H)ℓmani. For any g G and h H the empirical manipulated loss over such a sample is ϵ-close to its true loss. Standard uniform convergence theory (see, e.g., (Shalev Shwartz & Ben-David, 2014) Chapter 4) shows that, given a class of finite VC-dimension, for any data generating distribution, a large enough sample will be ϵ-representative with respect to that class.

Observation 3.7. If an un-manipulated sample S1 is ϵrepresentative with respect to (G H)ℓmani, then it can be indefinitely re-used by Agraph for any hypothesis h H and any manipulated ϵ-representative samples SΠ 2 . Thus if VC(G H)ℓmani = d, then m C d+log( 1

δ ) ϵ2 (for some universal constant C) , implies that with probability 1 δ any S1 P m is repeatedly reusable by Agraph to guarantee ϵ-success as in the Lemma above. This allows us to reuse the initial unmanipulated sample in all subsequent steps.

Algorithm 2 Empirical Manipulation Estimation (realizable)

Input: graph class G, hypothesis h, input samples S1 and SΠ 2 ,parameter ϵ Output set of candidate manipulation graphs Gc Lmax maxg G Lmani S1 (g, h) s.t. Lmani S2 (g, h) = 0 Gc {g G : Lmani S1 (g, h) [Lmax ϵ, Lmax]}

To generalize the above algorithms to richer classes and higher data dimensions, will now define a partial order for the graph class. We will then show that if a graph class is totally ordered with respect to this partial order, we can give a similar algorithm to the one in the threshold case with a similar guarantee.

Definition 3.8. For a hypothesis class H, let the ℓmani Hinduced partial order H on manipulation graphs be defined by: g1 H g2, if and only if for every h H and every x X, we have ℓmani(g1, h, x) ℓmani(g2, h, x). A graph class G is totally ordered with respect to H if for every distinct g1, g2 G, we have that either g1 H g2 or g2 H g1. For a subset A G of a totally ordered graph class, we define max H as the graph g A with g g for all g A.

Observation 3.9. A graph class G is totally ordered with respect to the class of all hypotheses F if and only if for every distinct g1, g2 G either g1 is a subgraph of g2 or g2 is a subgraph of g1.

For H1 H2 and two graphs g1, g2 g1 H2 g2 implies g1 H1 g2. Thus, if a graph class G is totally ordered with respect to H2 it is also totally ordered with respect to H1.

If G is totally ordered with respect to H, then VC(Gℓmani,H) = 1.

Strategic Classification with Unknown User Manipulations

There are G and H, such that VC(H) = d and G is totally ordered with respect to H, but VC((H G)ℓmani) = .

We can now generalize our threshold algorithm to an algorithm for totally ordered graph classes (Algorithm 3). This algorithm essentially works in the same way: It first identifies the maximal graph g0 for which there is a hypothesis with maximum accuracy that is still robust with respect to g0. The corresponding optimal hypothesis is the first hypothesis ˆh0 published by the algorithm. For the robust-realizable case, this is sufficient to guarantee success (see Observation 3.10), as we get uniform convergence of H both in terms of ℓm with respect to G and in terms of 0/1-loss, which is sufficient to guarantee uniform convergence in terms of the strategic loss. For the agnostic case other candidate graphs are generated in a similar fashion. The upper bound on the strategic loss is increased by ϵ-steps, and for each such increment the maximal graph gi, which allows for a classifier h H with corresponding loss Lgi S0(h) to be smaller than that bound, is identified. For these 1

ϵ many candidate graphs {g0, . . . , g 1

ϵ } we can then perform a kind of binary search by always publishing the optimal classifier with respect to the current median classification graph. We can then update the set of candidate graphs in each round by observing the manipulations caused by the published classifiers. We are guaranteed to always observe manipulations if robustness was under-estimated, giving the algorithm sufficient feedback for the binary search to terminate successfully. This yields the guarantee in Theorem 3.11.

Observation 3.10. Let VC(H G)ℓmani = d1 and VC(H) = d2. Furthermore let G be totally ordered with respect to H. Then Algorithm 3 is a successful proper strategic batch learner in the realizable case with sample complexity mreal H,G(ϵ, δ) = O( (d1+d2) log(d1+d2)+ 1

δ ϵ2 ) and round complexity T real H,G(ϵ, δ) = 1.

Theorem 3.11. Let VC(H G)ℓmani = d1 and VC(H) = d2. Furthermore, let G be totally ordered with respect to H. Then Algorithm 3 is a successful proper strategic batch learner with sample complexity m H,G(ϵ, δ) = O( (d1+d2) log(d1+d2)+log( 1

δϵ ) ϵ2 ) and round complexity TH,G(ϵ, δ) = O(log( 1

4. Improper Learning

As noted in Observation 3.9, it can be the case that VC(H) and VC(G)ℓmani,H are finite, but VC(G H)ℓmani is still infinite. In particular, this is the case for any G that contains a g G such that VC(Hℓg) is infinite, where Hℓg is the loss class of H with respect to the strategic loss ℓg. Furthermore, it has been shown that there are hypothesis classes H with finite VC-dimension but infinite VC-dimension of the loss class Hℓg, which are not properly strategically robust learn-

Algorithm 3 Strategic Batch-Learning for totally ordered graph classes

1: Input: parameters ϵ, ϵ , hypothesis class H, graph class G 2: receive sample S0 P m

3: L0/1 0 infh H L0/1 S0 (h ) 4: for i = 0, . . . , 1

5: gi max H{g : infh H Lg S0(h ) = L0/1 0 + i ϵ} 6: end for 7: set G0 = [g0, g1, g2, . . . , g 1

8: ˆh0 arg minh H Lg0 S0(h)

9: publish ˆh0

10: receive sample S1, where S 1 P m and St = SΠt t for some sequence of (g , h0)-induced manipulations Π1. 11: gmax max H{g G0 : Lmani S1 (g, ˆh0) = 0}

12: gmin min H{g G0 : Lmani S0 (g, ˆh0) Lmani S0 (g, ˆh0) ϵ and Lmani S1 (g, ˆh0) = 0} ] 13: G1 {g G0 : g H gmax and gmin H g}

14: k1 = |G1|

2 15: ˆg1 G1[k1]

16: ˆh1 arg minh H Lˆg1

S0(h) 17: for rounds t = 2, . . . , T do 18: publish ˆht 1

19: receive sample St, where S t P m and St = SΠt t for some sequence of (g , ht 1)-induced manipulations Πt. 20: Gt {g Gt 1 : Lmani St (g, ˆht 1) = 0}

21: Gt 0 {g Gt : Lmani S0 (g, ˆht 1) maxg Gt Lmani S0 (g , ˆht 1) ϵ } 22: if ˆgt 1 Gt 0 then 23: Gt [Gt[0], . . . , Gt[kt 1]] Gt 0 24: else 25: Gt Gt 0 26: end if 27: kt |Gt|

2 28: ˆgt Gt[kt]

29: ˆht minh H Lˆgt

S0(h) 30: end for

Strategic Classification with Unknown User Manipulations

able by any learner (Lechner & Urner, 2022). The following observation is a corollary of these results from the literature.

Observation 4.1. There are classes H of finite VCdimension and graph classes G which are totally ordered with respect to H, such that there is no proper successful batch-learner for H and G for any finite sample and round complexity, not even in the realizable case.

However, in the PAC-learning setting with a fixed hypothesis class it has been shown that any class of finite VC dimension can be improperly strategically robustly learned (Montasser et al., 2019; Lechner & Urner, 2022). We can generalize these positive results in the realizable case to a setting where the manipulation graph is unknown, but the learner is given the prior knowledge that the true manipulation graph comes from a known, totally ordered graph class. We exploit the fact that here we assume realizability in the strategically robust sense and that therefore any sample will be robustly realizable with probability 1. Now let G be a totally ordered graph class and H a hypothesis class. We define the maximally robust graph in G with respect to a sample S and class H as

MGH,G(S) = max H {g G : min h H Lg S(h) = 0}.

In cases where this maximum does indeed exist, we then define a maximally robust empirical risk minimizer (MRERM) with respect to H and G as the hypothesis in H minimizing the strategically robust loss with respect to MGH,G(S), i.e.,

MRERMH,G(S) arg min h H LMGH,G(S) S (h).

In cases where the maximum graph does not exist, we need to instead pick a hypothesis hmax S that is simultaneously robust with respect to every graph in G for which S is Hrealizable to achieve our guarantee. Such a hypothesis might not always exist within H. However, we can extend H to a class H , with VC(H ) = VC(H) and such that for every finite sample S X the class H contains a hypothesis hmax S . In order to define such a hypothesis class and general MRERM rigorously we need to use the set-theoretic concept of ultrafilters. For an explanation and proof that such H and MRERM always exist, we refer the reader to the appendix.

We note that in the realizable setting, the maximal graph used for the estimation here will always overestimate the robustness of the true manipulation graph g . We use this fact to define a successful improper learner and prove the following theorem based on techniques from the literature on PAC learning with respect to adversarial perturbations (Montasser et al., 2019).

Theorem 4.2. Let VC(H) be finite and let G be totally ordered with respect to H. Then there is a strategically robust (improper) PAC-learner (i.e., a PAC-learner with

respect to ℓgto-loss) which is successful for every g G in the strategically robustly realizable case (i.e. when infh H Lg

P (h) = 0).

Note that the learner is successful, even without knowing the true manipulation graph g and without receiving any local perturbation sets as input.

5. Ethics discussion

As machine learning applications seem to be infiltrating all aspects of society as well as individual people s lives, it becomes increasingly important to develop tools and frameworks to analyze and provide performance and safety guarantees for diverse settings beyond the standard one-time supervised learning task from iid data. We view our work in line with studies that aim to provide solid foundations for non-standard learning settings and make such foundations applicable to more realistic application scenarios. We believe that developing a more thorough understanding and dependable theory will ultimately benefit machine learning practitioners as well as policymakers that need to shape the legal landscape in which machine learning practitioners operate.

While our work does not include implementations of algorithms or algorithmic frameworks (and as such can not be abused directly ), we do believe that the algorithms we develop will be beneficial in scenarios of repeated learning and decision-making tasks with strategic agents. Whether such an application is morally commendable highly depends on the actors and objects of the application (as it does in any decision-making scenario that involves or affects human lives). We acknowledge that (as has been pointed out in the literature (Hu et al., 2019)) policies that are designed to discourage or prevent strategic responses to decision rules, might disproportionately affect underrepresented and/or disadvantaged segments of society. Developing mechanisms to address (and potentially counteract) such effects is an important complementary task to our study, which is however not a part of this submission.

Acknowledgements

We would like to thank Vinayak Pathak and Alex Bie for helpful discussions. Tosca Lechner was supported by a Vector Research Grant and a Waterloo Apple Ph D Fellowship in Data Science and Machine Learning. Ruth Urner is also a faculty affiliate member of Toronto s Vector institute. The last two authors research is supported through NSERC discovery grants.

Strategic Classification with Unknown User Manipulations

Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K. The strategic perceptron. In Bir o, P., Chawla, S., and Echenique, F. (eds.), EC 21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, pp. 6 25. ACM, 2021.

Balcan, M., Blum, A., and Vempala, S. S. Efficient representations for lifelong learning and autoencoding. In Proceedings of The 28th Conference on Learning Theory, COLT, pp. 191 210, 2015.

Balcan, M., Blum, A., and Nagarajan, V. Lifelong learning in costly feature spaces. Theor. Comput. Sci., 808:14 37, 2020.

Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M. K. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929 965, 1989.

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

Chen, Y., Liu, Y., and Podimata, C. Learning strategy-aware linear classifiers. In Proceedings of the 34th International Conference on Neural Information Processing Systems, Neur IPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.

Chen, Y., Wang, J., and Liu, Y. Linear classifiers that encourage constructive adaptation, 2021.

Cullina, D., Bhagoji, A. N., and Mittal, P. Pac-learning in the presence of adversaries. In Advances in Neural Information Processing Systems, pp. 230 241, 2018.

Dalvi, N. N., Domingos, P. M., Mausam, Sanghai, S. K., and Verma, D. Adversarial classification. In Proceedings of the Tenth ACM International Conference on Knowledge Discovery and Data Mining SIGKDD, pp. 99 108, 2004.

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

Feige, U., Mansour, Y., and Schapire, R. Learning and inference in the presence of corrupted inputs. In Conference on Learning Theory, pp. 637 657, 2015.

Haghtalab, N., Immorlica, N., Lucier, B., and Wang, J. Z. Maximizing welfare with incentive-aware evaluation mechanisms. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI, pp. 160 166, 2020.

Hardt, M., Megiddo, N., Papadimitriou, C. H., and Wootters, M. Strategic classification. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS, pp. 111 122, 2016.

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

Jagadeesan, M., Mendler-D unner, C., and Hardt, M. Alternative microfoundations for strategic classification. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, pp. 4687 4697, 2021.

Lechner, T. and Urner, R. Learning losses for strategic classification. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, pp. 7337 7344, 2022.

Levanon, S. and Rosenfeld, N. Generalized strategic classification and the case of aligned incentives. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 12593 12618. PMLR, 17 23 Jul 2022.

Miller, J., Milli, S., and Hardt, M. Strategic classification is causal modeling in disguise. In Proceedings of the 37th International Conference on Machine Learning, ICML, pp. 6917 6926, 2020.

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

Montasser, O., Hanneke, S., and Srebro, N. VC classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, COLT, pp. 2512 2530, 2019.

Montasser, O., Hanneke, S., and Srebro, N. Adversarially robust learning with unknown perturbation sets. In Conference on Learning Theory, COLT 2021, pp. 3452 3482, 2021.

Pentina, A. and Ben-David, S. Multi-task and lifelong learning of kernels. In Algorithmic Learning Theory - 26th International Conference, ALT, pp. 194 208, 2015.

Pentina, A. and Lampert, C. H. A pac-bayesian bound for lifelong learning. In Proceedings of the 31th International Conference on Machine Learning, ICML, pp. 991 999, 2014.

Pentina, A. and Urner, R. Lifelong learning with weighted majority votes. In Advances in Neural Information Processing Systems 29, NIPS, pp. 3612 3620, 2016.

Strategic Classification with Unknown User Manipulations

Shalev-Shwartz, S. and Ben-David, S. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.

Shavit, Y., Edelman, B. L., and Axelrod, B. Causal strategic linear regression. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 8676 8686. PMLR, 2020.

Sundaram, R., Vullikanti, A., Xu, H., and Yao, F. Paclearning for strategic classification. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, pp. 9978 9988, 2021.

Tsirtsis, S. and Rodriguez, M. G. Decisions, counterfactual explanations and strategic behavior. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems Neur IPS, 2020.

Valiant, L. G. A theory of the learnable. Commun. ACM, 27 (11):1134 1142, 1984.

Vapnik, V. N. and Chervonenkis, A. Y. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264 280, 1971.

Zhang, H. and Conitzer, V. Incentive-aware PAC learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI, pp. 5797 5804, 2021.

Strategic Classification with Unknown User Manipulations

A. Note on the maximally robust ERM paradigm

The proof of Theorem 4.2, employs the notions of a maximal graph within G and maximal ERM hypothesis within the class H. Recall the definitions from Section 4:

MGH,G(S) = max H{g G : minh H Lg S(h) = 0}

MRERMH,G(S) argminh HLMGH,G(S) S (h)

However, in general, these do not necessarily exist in these classes. In this section, we show that we can always embed the original classes G and H in such a way that the above notions are well-defined.

Consider a fixed sample S = ((x1, y1), . . . , (xm, ym)) that is realizable with respect to the strategic loss for some g G. Then the set GS = {g G : min h H Lg S(h) = 0} G

is not empty, and we can define a new manipulation graph MGH,G(S) by taking the union of all edge sets of graphs in GS as the new edge set for this maximal graph. Now, if the set

argminh HLMGH,G(S) S (h)

is not empty, then we can choose any element in this set to define a maximally robust ERM hypothesis MRERMH,G(S). Note that this is always the case if the graph class G (and therefore the set GS) is finite.

Thus we now focus on the case where GS induced by some S is infinite and the set argminh HLMGH,G(S) S (h) is empty. We will use the concept of an ultrafilter to define a maximal hypothesis hmax S for the sample S. Finally, we will show that adding all possible (over all labelled samples S) such maximal hypotheses yields a hypothesis class H with H H and VC(H ) = VC(H).

Definition A.1 (Filter). Let Z be some set and let F 2Z be a collection of subsets of Z. We call F a filter if the following conditions are satisfied:

F is upwards inclusion closed: if A F and A B, then B F

F is closed under finite intersections: if A F and B F, then (A B) F.

A filter F is an ultrafilter if for every domain subset C Z, either C or its complement C is a member of F.

It can be shown (using Zorn s lemma) that every filter F can be extended to an ultra-filter. That is, there always exists an ultrafilter e F with F e F.

We will start by defining a filter over GS. Note that GS is totally ordered. A final segment G GS is a subset such that g G and g g implies g G. Now consider the collection F 2GS defined by:

F = {G GS | G contains a final segment of GS}.

It is not difficult to see that F is indeed a filter. Let e F denote an ultra-filter extending if (that is, F e F).

Recall that for every g GS there exists at least one h H such that Lg S(h) = 0. Let τ : GS H be a function that assigns every manipulation graph g GS such a hypothesis hg = τ(g). The image of τ is thus a subset HS H of the hypothesis class of empirical risk minimizers corresponding to the graphs in GS:

HS = {hg | g GS}.

Strategic Classification with Unknown User Manipulations

We can consider the set HS as indexed by GS and therefore inheriting the order of GS (and we can thus refer to final segments of HS etc). Note that, if for some x X, and y {0, 1}, there exists a final segment of HS, in which all functions assign x the same label y, then the set {g GS | hg(x) = y} F

is an element of the filter F (since the filter is upward inclusion closed). For such cases, the limit function hmax S will assign this label y to x.

Observe that for every x, the set {g GS | hg(x) = y} is the complement (in GS) of the set {g GS | hg(x) = 1 y}, and thus exactly one of these sets is a member of the ultrafilter e F that contains F. We can thus define the limit function on the whole domain X by

hmax S (x) =

( 1 if {g GS | hg(x) = 1} e F 0 else.

That is, for every x X, y {0, 1}, we have hmax S (x) = y if and only if {g GS | hg(x) = y} e F. The ultra-filter e F serves to define a tie-breaker label for all domain elements x that are not eventually assigned the same label - x s for which every final segment of GS contains both g s with hg(x) = 0 and g s with hg(x) = 1.

It remains to show that this so-defined limit function hmax S (x) has empirical strategic loss 0 on S for all graphs in GS and that adding all such limit functions to the hypothesis class H will not increase its VC-dimension.

For the first property, consider some g GS and some (x, y) S. If y = 0, then all functions hg for g g assign 0 to all points in Bg(x) (since each hg is an empirical risk minimizer for the empirical strategic loss Lg

S ). If y = 1, then all these functions assign label 1 to x. Since the set {g GS | g g } is a member of F and therefore a member of e F, the first case implies that hmax S (x ) = 0 for all x Bg(x) and the second case implies that hmax S (x) = 1. In both cases ℓg(hmax S , (x, y)) = 0, and since this holds for all (x, y) S and all g GS, we have

Lg S(hmax S (x)) = 0.

Now we consider the extended hypothesis class

H = H {hmax S {0, 1}X | S (X {0, 1}) }

where we added the limit functions (as defined above) for all possible labeled samples S over X {0, 1}. In order to show that H has the same VC-dimension as H, we argue that any finite set that is shattered by H is already shattered by H.

Consider domains points x1, x2, . . . , xd, shattered by H , and some labels y1, y2, . . . yd. Assume this labeling is realized by a limit function hmax S (that came from some labeled sample S), that is hmax S (xi) = yi for all i [d]. Note that hmax S (xi) = yi implies that for each i the set {g GS | hg(xi) = yi} e F

Since ultra-filters are closed under finite intersections, the set

{g GS | hg(xi) = yi for all i [d]}

is also a member of the ultrafilter e F, and therefore not empty. Thus, there exists a g GS and corresponding ERM function hg HS H with hg(xi) = yi for all i [d]. Thus, any labeling on a finite set of points that is realized by some limit function, is also already realized by a hypothesis from H. Therefore, VC(H ) = VC(H), and we can use the larger class H to define the maximally robust ERM hypothesis, we set

MGH,G(S) = (X, E) with E = S

{g G:minh H Lg S(h)=0} Eg

MRERMH,G(S) =

( h argminh HLMGH,G(S) S (h) if this set is not empty hmax S as defined above, otherwise.

Strategic Classification with Unknown User Manipulations

Definition B.1. Let ℓstr : Gall F X {0, 1} be the loss defined by

ℓstr(g, h, x, y) = max{ℓ0/1(h, x, y), ℓmani(g, h, x)}.

The loss class of G H with respect to ℓstr is defined by

(G H)ℓstr =

{{(x, y) X {0, 1} : ℓstr(g, h, x, y) = 1}} : h H, g G}.

Claim B.2. Let d = VC((G H)ℓmani) + VC(H). Then, VC((G H)ℓstr) d log(d).

Proof. We follow the same argument as in (Lechner & Urner, 2022). Let us denote (g, h)ℓmani = {(x, y) X {0, 1} : ℓmani(g, h, x) = 1} and hℓ0/1 = {(x, y) X {0, 1} : ℓ0/1(h, x, y) = 1}. Lastly, let (g, h)ℓstr = {(x, y) X {0, 1} : ℓstr(g, h, x, y) = 1}. We can easily see that (g, h)ℓstr(g, h) = (g, h)ℓmani hℓ0/1. Thus, (G H)ℓstr = {A B : A Hℓ0/1, B (G H)ℓmani}. Thus, by standard arguments about VC-classes (e.g. exercises in (Shalev-Shwartz & Ben-David, 2014)), we get the claimed result.

B.1. Proper Batch Learning

B.1.1. CLASS OF THRESHOLDS

Observation 3.1. The Strategic Batch-Learning for Thresholds Algorithm (Algorithm 3.1) is a proper learner for the strategic-batch learning problem for Hthres and Gf.r. in the realizable case with sample complexity mreal H,G = O( log( 1

δ ) ϵ2 ) and round complexity T real H,G = 1.

Proof. This is a special case of Observation 3.10, as the graphs in Gf.r. are totally ordered with respect to F (and thus also with respect to Hthres.

Theorem 3.2. The Strategic Batch-Learning for Thresholds Algorithm (Algorithm 1) is a proper learner for the strategicbatch learning problem for Hthres and Gf.r. in the agnostic case with sample complexity m H,G(ϵ, δ) = O( log( 1

δϵ ) ϵ2 ) and round complexity TH,G(ϵ, δ) = O(log( 1

Proof. We note that the graphs in Gf.r. are totally ordered with respect to F (and thus also with respect to Hthres. We also find that (Gf.r. Hthres)ℓmani) is the class of intervals over the real line and thus C VC((Gf.r. Hthres)ℓmani) = 2. Therefore we can treat this Theorem as a special case of Theorem 3.11 (and refer the reader to the proof of that theorem).

B.1.2. GENERAL VC-CLASSES

Observation 3.4

The VC-dimension of (Gf.r. Hthres)ℓmani is 2.

Let Hhalf = {hw : w Rd : hw(x) iff x T w 0} the hypothesis class of linear half spaces and Gd f.r. = {gr = (X, Egr) : (x, x ) Egr iff ||x x ||2 r} be the class of fixed-radius balls in Rd. Then the VC dimension of (Gd f.r. Hhalf)ℓmani is at most 2d.

Proof. We note that the elements of (Gf.r. Hthres)ℓmani correspond exactly to the class of intervals over the real line. The VC-dimension of that class is known to be 2 (Shalev-Shwartz & Ben-David, 2014).

We note, that the elements of (Gd f.r. Hhalf)ℓmani are sets Cw,r = {x Rd : r x T w 0}. Now if we take any set C of 2d + 1 points, then there is one point x C such that x is in the convex hull of the remaining points, i.e., x conv(C \ {x}). Now it is impossible for any Cw,r to achieve Cw,r C = {x}. Thus the set C cannot be shattered by (Gd f.r. Hhalf)ℓmani. Therefore VC((Gd f.r. Hhalf)ℓmani) 2d.

Strategic Classification with Unknown User Manipulations

Lemma 3.6. Let G, H be such that VC(Gℓmani,H) = d. Then any Empirical Manipulation Estimation learner (such as Algorithm 3.2 below) has the following success guarantee for learning the manipulation graph:

For every marginal distribution PX , every g G, every h H and every sequence of (g , h)-induced manipulations Π, and every ϵ, δ (0, 1),

if m C d+log( 1

δ ) ϵ2 (for some universal constant C) with probability (1 δ), over samples S1 P m X , S2 P m X , for every ˆg Agraph(S1, SΠ 2 , h),

Dis(PX ,h)(g , ˆg) ϵ.

g Agraph(S1, SΠ 2 , h).

Proof. We note it is sufficient to show that there is a constant C, such that for i.i.d P samples S1 and S2 of size m C d+log( 1

δ ) ϵ2 with probability 1 δ, we have Lmani S1 [Lmax ϵ

2, Lmax], to guarantee that if we run Agraph with parameter ϵ 2, we get:

Dis(PX ,h)(g , g) ϵ for all g Agraph(S1, SΠ 2 , h).

and g Agraph(S1, SΠ 2 , h).

First we note, that for any samples S1 and S2 and the true manipulation graph g , we have Lmani SΠ 2 (g , h) = 0, as the sequence of mappings Π replaces every sample point which can be manipulated in S2 (i.e., all sample points with ℓ(g , h) = 1), with a sample point x with h(x ) = 1 (i.e., a sample point with ℓmani(g , h, x ) = 0). From g G, it follows that we have g {g G : Lmani SΠ 2 (g, h) = 0}. Then this implies

Lmax = max{Lmani S1 (g, h) : g G, Lmani SΠ 2 (g, h) = 0}

Lmani S1 (g , h).

Now from VC-theory, we know that there exists a universal constant C, such that a sample size of m d+log( 1

δ ) ϵ2 guarantees that with probability 1 δ

2 we have that a sample S P m is ϵ

8-representative with respect to Gℓmani,h.

Now let S1 and S2 be ϵ

8-representative with respect to (G {h})ℓmani). We want to show that Lmax ϵ

2 Lmani S1 (g , h). We note that there exists gmax G, such that Lmax = Lmani S1 (gmax, h) and Lmani SΠ 2 (gmax, h) = 0.

Because of the ϵ

8-representativeness of both samples, we get for every g G, we have

|Lmani S1 (g, h) Lmani S2 (g, h)|

|Lmani S1 (g, h) Lmani PX (g, h)| + |Lmani S2 (g, h) Lmani PX (g, h)| ϵ

Furthermore we note, that for any manipulation graph g, |Lmani SΠ 2 (g, h) Lmani S2 (g, h)| 1 |S2||{x S2 : x SΠ 2 }| =

Lmani S2 (g , h).

It now follows that:

Lmax = Lmani S1 (gmax, h)

|Lmani S1 (gmax, h) Lmani S2 (gmax, h)|

Strategic Classification with Unknown User Manipulations

+|Lmani S2 (gmax, h) Lmani SΠ 2 (gmax, h)|

4 + Lmani S2 (g , h)

2 + Lmani S1 (g , h).

Putting everything together, we have Lmani S1 (g , h) [Lmax 1

ϵ , Lmax]. This concludes our proof.

Observation 3.7 If an un-manipulated sample S1 is ϵ-representative with respect to (G H)ℓmani, then it can be indefinitely re-used by Agraph for any hypothesis h H and any manipulated ϵ-representative samples SΠ 2 . Thus if VC(G H)ℓmani = d, then

m C d+log( 1

δ ) ϵ2 (for some universal constant C) , implies that with probability 1 δ any S1 P m is repeatedly reusable by Agraph to guarantee ϵ-success as in the Lemma above, This allows us to reuse the initial unmanipulated sample in all subsequent steps.

Proof. We note that in order for sample S1 to guarantee success in Lemma 1 we only required it to be ϵ

4-representative with

respect to Gℓmani,h. If VC((H G)ℓmani) = d, then there exists a sample size m C d+log( 1

δ ) ϵ2 that with probability 1 δ over the sample generation S1 P m, we have that S1 is ϵ

4-representative with respect to (G H)ℓmani. This implies that with probability 1 δ, S1 is ϵ

4-representative w.r.t. Gℓmani,h for all h H simultaneously, proving the obervation.

Observation 3.9.

A graph class G is totally ordered with respect to the class of all hypotheses F if and only if for every distinct g1, g2 G either g1 is a subgraph of g2 or g2 is a subgraph of g1.

For H1 H2 and two graphs g1, g2 g1 H2 g2 implies g1 H1 g2. Thus, if a graph class G is totally ordered with respect to H2 it is also totally ordered with respect to H1.

If G is totally ordered with respect to H, then VC(Gℓmani,H) 1.

There are G and H, such that VC(H) = d and G is totally ordered with respect to H, but VC((H G)ℓmani) = .

Proof. : Let G be totally ordered with respect to F. This means for any two graphs g1, g2 G, we have either g1 F g2 or g2 F g1. Without loss of generality, assume g1 F g2. We want to show that this implies that g1 is a subgraph of g2. For the purpose of contradiction, assume the opposite. This means that there exists an edge (x, x ) Vg1, such that (x, x ) Vg2. Now consider any function f F with f(x) = 0 and f(x) = 1. Then ℓmani(g1, f, x) = 1 0 ℓmani(g2, f, x), which contradicts g1 F g2.

Let G such that for every two graphs g1, g2 G, we have either Eg1 Eg2 or Eg2 Eg1. Without loss of generality, assume Eg1 Eg2. We want to show that this implies g1 F g2. For the sake of contradiction, we assume the opposite. This means that there exists an f F and a x X, such that ℓmani(g1, f, x) = 1 and ℓmani(g2, f, x) = 0. ℓmani(g1, f, x) = 1 implies that f(x) = 0 and that there is an x X such that f(x ) = 1 and such that (x, x ) Eg1. Now this implies that (x, x ) Eg2 as well. From f(x) = 0 and f(x ) = 1 it follows that ℓmani(g2, f, x) = 1, contradicting our assumption.

This follows directly from the definitions. If for g1 and g2, we have g1 H2 g2 then for all h H2 and all x X, we have ℓmani(g1, h, x) = 1 implies ℓmani(g2, h, x) = 1. Since H1 H2 for all h H1 we thus have ℓmani(g1, h, x) = 1 implies ℓmani(g2, h, x) = 1. Thus g1 H1 g2.

Strategic Classification with Unknown User Manipulations

Take any h H and any {x1, x2} = C X. Assume that C was shattered by Gℓmani,h. Then there is some g1, such that ℓmani(g1, h, x1) = 1 and ℓmani(g1, h, x2) = 0. We know that G is totally ordered with respect to H. Thus we know that for any g2 G, we either have g1 H g2, which implies that ℓmani(g2, h, x1) = 1 or g2 H g1 which implies ℓmani(g2, h, x2) = 0. Thus there is no g2 G with ℓmani(g2, h, x1) = 0 and ℓmani(g2, h, x2) = 1, contradicting that C is shattered by Gℓmani,h. Thus VC(Gℓmani,h) 1. Since h H was picked arbitrarily we have VC((G)ℓmani,H) = suph H(VC(Gℓmani,h)) 1.

For VC((H G)ℓmani) to be infinite it is sufficient to find one g and a hypothesis class H such that VC(H {g})ℓmani = . In Theorem 5 in (Lechner & Urner, 2022), we have seen that there are classes H with VC(H) = 1 and manipulation graphs g, such that VC(H {g})ℓmani = . Lastly we note that if we pick G = {g}, then G is trivially totally ordered with respect to H.

Observation 3.10. Let VC(H G)ℓmani = d1 and VC(H) = d2. Furthermore let G be totally ordered with respect to H. Then Algorithm 3.2 is a successful proper strategic batch learner in the realizable case with sample complexity mreal H,G(ϵ, δ) = O( (d1+d2) log(d1+d2)+log( 1

δ ) ϵ2 ) and round complexity T real H,G(ϵ, δ) = 1.

Proof. We assume to be in the realizable case, i.e. infh H Lg

P (h) = 0. Thus with probability 1, the sample S0 will be realizable under Lg as well. This implies infh H L0/1 S0 (h) = 0. Therefore, in line 3 of Algorithm 3, we set L0/1 0 to 0. We then determine g0 to be the maximal graph according to H to yield infh H Lg0 S0(h) = 0 (line 5). From this and the realizability assumption, if follows that g H g0. In line 8, we now define ˆh0, to be arg minh H Lg0 S0(h). From

g H g0, it follows that Lg

S0 (ˆh0) = 0 as well. Now, we can choose a sample size m O( (d1+d2) log(d1+d2)+log( 1

δ ) ϵ2 ), large enough to guarantee ϵ

8-representativeness with respect to Hℓg , (G H)ℓmani as well as (G H)ℓstr simultaneously with probability at least 1 δ

2. Now with probability 1 δ, S0 P m and S 1 P m are both such ϵ

8-representative samples. First we note, that this guarantees that Lg

8 with probability 1 δ

This implies that an ϵ

8-representative sample S 1 at most a fraction of ϵ

4 can be manipulated by a (g , ˆh0)-induced manipulation. We now assume that the parameter ϵ in the algorithm, is the same as the ϵ in our sample complexity analysis (our algorithm lets us set this parameter. We can assume that we know in advance what the size of the first sample will be.). Now if S 1 is ϵ

8-representative with respect to ℓg , then for g1 (as chosen in line 5), we have Lg1 S 1(ˆh0) Lg1 S0(ˆh0) ϵ

infh H Lg1 S0(ˆh0) ϵ

4 . Since L0/1 S0 (ˆh0) = 0, we have L0/1 S 1 (ˆh0) ϵ

4. Thus Lmani S 1 (g1, ˆh0) 3ϵ

noticed before that only at most a fraction of ϵ

4 samples in S 1 get replaced in S1. Thus g1 does not fulfill Lmani S 1

g1(ˆh0) = 0.

Therefore G1 = {g0}. Which means that for all consecutive rounds t, we get ˆht = infh H Lg0 S0(h), which yields the guarantee Lg

P (ˆht) Lg0 P (ˆht) ϵ

Theorem 3.11.

Let VC(H G)ℓmani = d1 and VC(H) = d2. Furthermore let G be totally ordered with respect to H. Then Algorithm 3.2 is a successful proper strategic batch learner with sample complexity m H,G(ϵ, δ) = O( (d1+d2)(log(d1+d2))+ 1

δϵ ϵ2 ) and round complexity TH,G(ϵ, δ) = O(log( 1

Proof. We will first argue that among the candidate graphs G0 we pick in round 0, there is a candidate graph gi, which yields a close-to-optimal hypothesis h, given some amount of ϵ-representativeness and for certain choices of parameters.

Assume we have a sample S0 which is ϵ 16-representative with respect to (G H)ℓstr. Then S0 is ϵ 16-representative with respect to Hℓg for every g G. Now let us run the algorithm with the parameter ϵ set as ϵ

4. Let G0 be defined as in the algorithm (line 7). Furthermore for every gi G0, define hi = arg minh H Lgi S0(h) and H = {h0, . . . , h 4

ϵ }. Now let h

denote the optimal hypothesis h = arg minh H LP (g )(h). Now let j = 4(Lg

S0 (h ) L0/1 0 ) ϵ +1. Now we compare h to hj from the candidate set H . By definition of gj and hj, we know that jϵ

4 + L0/1 0 = Lgj S0(hj) Lgj S0(h ). Furthermore, we

Strategic Classification with Unknown User Manipulations

know that Lg

S0 (h ) + ϵ

16 ( (j 1)ϵ

4 + L0/1 0 ) + ϵ

4 + L0/1 0 . Thus g Hthres gj. Therefore, Lg

4 + L0/1 0 + ϵ

16 = (j 2)ϵ)

4 + L0/1 0 + 9ϵ

S0 (h ) + 9ϵ

P (h ) + 10ϵ

16 . This shows that there is indeed a hypothesis in our candidate-set that is close to optimal.

We now note that the graph elimination that happens in lines 13 to 15 and lines 20 to 21 is equivalent to the estimation of Algorithm 2, which we know to keep the optimal graph if the samples encountered are ϵ

8 -representative. We further note that the update in line 23 only occurs, if the sample St = S Π t was not significantly manipulated according to ˆht 1. Thus gt 1 already sufficiently accounted for all possible manipulation caused by g , which means that eliminating candidate graphs g with gt 1 H g will not cause a miss-estimation of g that causes more that 2ϵ difference in strategic loss. Thus the elimination of graphs will yield an approximately optimal hypothesis. Furthermore this is a kind of binary search which eliminates half the candidates in each step (as the algorithm always picks the median candidate in line 15 and line 26 respectively and the elimination either eliminates all graphs smaller or all graphs greater to the current candidate.) Therefore the algorithm needs at most O(log( 1

ϵ )) rounds.

Lastly, we note that a sample size of m = O( (d1+d2) log(d1+d2)+log( log( 1

ϵ ) δ ) ϵ2 ) is sufficient to guarantee that in each of the O(log( 1

ϵ )) rounds, the probability of receiving an ϵ 16-representative sample is at least 1 δ log( 1

ϵ ). Thus via union bound the

sample size of m = O( (d1+d2) log(d1+d2)+log( log( 1

ϵ ) δ ) ϵ2 ) is sufficient to guarantee (ϵ, δ)-learning success.

B.2. Improper Learning

Observation 4.1. There are classes H of finite VC-dimension and graph classes G which are totally ordered with respect to H, such that there is no proper successful batch-learner for H and G for any finite sample and round complexity, not even in the realizable case.

Proof. This follows directly from Theorem 4 of (Lechner & Urner, 2022) (which is an adaptation of Theorems 1 and 4 of (Montasser et al., 2019) for the strategic loss). The theorem states that there exists a class H and a fixed manipulation graph g of VC-dimension 1 which cannot be properly PAC-learned with respect to strategic loss by any proper learner. If we now consider this H and the graph class G = {g}, then it is easy to see that G is totally ordered with respect to H (as it only has one element). Furthermore H was picked to have VC dimension 1. Furthermore if proper batch-learning was possible for H and G, then proper PAC-learning would be possible for H with respect to ℓg, which we know to be impossible. This proves the theorem.

Theorem 4.2. Let VC(H) be finite and let G be totally ordered with respect to H. Then there is a strategically robust (improper) PAC-learner which is successful for every g G in the strategically robustly realizable case (i.e. when infh H Lg

P (h) = 0).

Proof. This is an adaptation of Theorem 4 from (Montasser et al., 2019) (and its adaptation to strategic loss in (Lechner & Urner, 2022)). The main difference here is that those theorems focus on the robustness with respect to a fixed (and known) manipulation graph, whereas in our setting we want to guarantee robustness with respect to an unknown element of a totally ordered graph class G. Thus we cannot use any knowledge of this graph in the learning process, which makes it impossible to use robust empirical risk minimization (RERM) with respect to the true manipulation graph. However, we can use the realizability assumption and define Maximally Robust Empirical Risk Minimization(MRERM) with respect to a totally ordered graph class G. First let us define gmax(S, H, G) =

max H {g G : for all h RERMg,H(S) : Lg S(h) = 0}.

The set of maximally robust empirical risk minimizers with respect to G and H is then defined by MRERMG,H(S) = RERMgmax(S,H),H(S). We can now replace all use of the fixed deterministic RERMg,H algorithm for a fixed manipulation graph (or pertubation sets) in the proof of Theorem 4 of (Montasser et al., 2019) by a fixed deterministic MRERMG,Halgorithm.

We note that for any S S, we have gmax(S, H, G) H gmax(S , H, G). Furthermore, we note that under the realizability assumption, we have gmax(S, H, G) g and thus Lg

S (MRERMG,H(S)) = 0 with probability 1 over the sample

Strategic Classification with Unknown User Manipulations

generation. We can now follow the proof of (Montasser et al., 2019) with some modified definitions, mainly replacing RERM with MRERM and replacing the inflated sample according to the true manipulation graph (which we don t know) with an inflated sample according to the gmax(S, H, G): For a training sample S = {(x1, y1), . . . , (xm, ym)}, we can now define the inflated sample according to the maximal graph that still allows realizability according to H: Let the inflated (potentially infinite) sample Sgmax be defined as Sgmax = S (S

i {1,...,m}:yi=0{(x, 0) : x Bgmax(S,H,G)(xi)}). We now want to define a discretized version of this inflated sample. From standard PAC-learning theory we know that there is a positive integer n O(VC(H)) that guarantees for any distribution D over X {0, 1} with infh H L0/1 D (h) = 0, for n i.i.d. D-distributed samples S = {(x 1, y 1), . . . , (x n, y n)}, with nonzero probability, every h H satisfying L0/1 S (h) = 0 also LD(h) 1

3. Now let ˆH = {MRERMG,H(L) : L S and |L| = n}. We note that | ˆH| |{MRERMG,H(L) : L S and |L| = n}| ( em

n )n. Now consider the dual space W of function w(x,y) : H {0, 1} defined by w(x,y)(h) = 1[[] h(x) = y] and every (x, y) Sgmax. The VC-dimension of W is now at most the dual VC-dimension of H, which is known to be upper-bounded by VC 2VC(H)+1. We now define ˆSgmax to be a subset of Sgmax which includes exactly one element (x, y) gmax for each distinct classification {w(x,y)(h)}hin ˆ H of ˆH realized function of w(x,y) W. By the Sauer lemma

we have | ˆSgmax| ( e| ˆ H| VC (H))VC (H), which for m > 2VC(H) is at most ( e2m VC(H))VC(H)VC (H). We can now note that for

any T N and any h1, . . . , h T ˆH if 1

T PT t=1 1[ht(x) = y] > 1

2 for every (x, y) ˆSgmax, then 1

T PT t=1 1[ht(x) = y] >

1 2 for every (x, y) Sgmax as well, which would then imply Lgmax(S,G,H) S (Majority(h1, . . . , h T )) = 0, which implies Lg

S (Majority(h1, . . . , h T )) = 0. We can now find these functions h1, . . . , h T in exactly the same way as in (Montasser et al., 2019)(via using the α-Boost algorithm). The resulting classifier ˆh = Majority(h1, . . . , h T ) satisfies Lg

S (ˆh) = 0. Furthermore we note that each of the classifiers ht is the result of MRERMG,H(Lt) for some Lt S with |Lt| = n. Thus, the classifier ˆh is representable as the value of an (order-dependent) reconstruction function of set size

n T = O(VC(H) log(| ˆSgmax|))

= O(VC(H)2VC (H) log( m VC(H)).

Thus invoking Lemma 11 of (Montasser et al., 2019)1 with respect to Lg if m > c VC(H)2VC (H) log(VC(H)VC (H)) (for a sufficiently large numerical constant c), we have that with probability at least 1 δ,

O(VC(H)2VC (H)) log( m VC(H)) log(m) + 1

This concludes our proof.

1We need a slight adaptation from adversarial loss to strategic loss here, but the proof for this goes through exactly as is for strategic manipulation loss as argued in (Lechner & Urner, 2022).