Strategic Classification with Non-Linear Classifiers
Authors: Benyamin Trachtenberg
Nir Rosenfeld
Venue: NeurIPS 2025 poster ()
Keywords: strategic classification
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We extend the study of strategic classification to non-linear classifiers and study how behavior in this regime affects the shape of classifiers and expressivity of model classes.

Abstract: In strategic classification, the standard supervised learning setting is extended to support the notion of strategic user behavior in the form of costly feature manipulations made in response to a classifier. While standard learning supports a broad range of model classes, the study of strategic classification has, so far, been dedicated mostly to linear classifiers. This work aims to expand the horizon by exploring how strategic behavior manifests under non-linear classifiers and what this implies for learning. We take a bottom-up approach showing how non-linearity affects decision boundary points, classifier expressivity, and model class complexity. Our results show how, unlike the linear case, strategic behavior may either increase or decrease effective class complexity, and that the complexity decrease may be arbitrarily large. Another key finding is that universal approximators (e.g., neural nets) are no longer universal once the environment is strategic. We demonstrate empirically how this can create performance gaps even on an unrestricted model class.

Strategic Classification with Non-Linear Classifiers
Benyamin Trachtenberg, Nir Rosenfeld
Technion Israel Institute of Technology
Haifa, Israel {benyamint, nirr} @cs. Sechnion.aan ac.
Abstract
In strategic classification, the standard supervised learning setting is extended to support the notion of strategic user behavior in the form of costly feature ma- nipulations made in response to classifier. While standard learning supports a broad range of model classes, the study of strategic classification has, so far, been dedicated mostly to linear classifiers. This work aims to expand the horizon by exploring how strategic behavior manifests under non-linear classifiers and what this implies for learning. We take bottom-up approach showing how non-linearity affects decision boundary points, classifier expressivity, and model class complexity. Our results show how, unlike the linear case, strategic behavior may either increase or decrease effective class complexity, and that the complexity decrease may be arbitrarily large. Another key finding is that universal approximators (e.g., neural nets) are no longer universal once the environment is strategic. We demonstrate em- pirically how this can create performance gaps even unrestricted model class.
Introduction
Strategic classification considers learning in a setting where users modify their features in response deployed classifier obtain positive predictions [3, 4, 16]. This setting aims capture a natural tension that can arise between system aiming to maximize accuracy and its users who seek favorable outcomes. Such tension is well-motinn motivatee across diverse applications, including loan approval, university admission, job hiring, welfare and education programs. and medical services. The field has drawn much attention since its introduction, leading advances along multiple learning fronts such as generalization [6, 33, 36), optimization [25], loss functions [24, 26), and extensions [11, 14, 18, 30].
However, despite focused on linear classification. Due to the inherent challenges of strategic learning, this focus has been reasonable, given that linearity has the benefit of inducing a simple form of strategic behavior that permits tractable analysis. Yet, since many realistic applications-incll above-make regular of non-linear models, we believe that it important establish better un- derstanding of how non- non-lincarity shapes strategic behavior, and how behavior in turn affects learning. Our paper therefore aims to extend the study of strategic classification the non non-linear regime.
decade of effort, research in strategic classification remains predominantly
those mentioned
Our first observation is that non-linear classifiers induce qualitatively different behavior than linear ones in the strategic setting. Consider first the structure induced by standard linear classifiers. Generally, users in strategic classification are assumed to best-respond to the classifier by modifying their features in a way that maximizes utility (from prediction) minus costs (from modification). For a linear classifier / coupled with the common choice of an & cost, modifications x + zh manifest projection of onto the línear decision boundary of h long it incurs less than unit cost. This simple form has several implications. First, note that all points 'move' in the same direction, making strategic behavior, in effect, one-dimensional. Second, the region of points that move forms band of unit distance on the negative side of h. This means that the set of points classified as positive
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

forms a halfspace, which implies that the "effective classifier', given by (a(2) == h(2²), is also linear. Third, and as a result, the induced effective model class remains linear.
Together, the above suggest that for linear classifiers coupled with l2 costs, the transition from the stan- dard, non-strategic setting to a strategic one requires anticipating which points move, but otherwise remains similar. One known implication is that the strategic and non-strategic VC dimension of linear classifiers are the same [33]. Furthermore, the Bayes-optimal strategic classifier can be derived by tak- ing the optimal non-strategic classifier and simply increasing its bias term by one [29]. Note that this means that any linearly separable problem remains separable, and that strategic classifiers can, in prin- ciple, attain the same level of accuracy as their non-strategic counterparts. Thus, while perhaps chal- lenging to solve in practice the intrinsic difficulty of strategic linear classification remains unchanged.
The above, however, is unlikely to hold for non-linear classifiers: once the decision boundary is non-linear, different points will move in different directions. This lends the possible distortion of the shape of a given classifier, which in turn can change the effective (i.e., strategic) model class. Such changes can have concrete implications on expressivity, generalization, optimization, and attainable accuracy. This motivates the need to explore how strategic responses shape outcomes in non- non-linear strategic classification, which we believe is crucial as a first step towards developing future methods. Our general approach is to caamine-througee analysis, examples, and experiments-hop objects in the original non-strategic task map to corresponding objects in the induced strategic problem instance. Initially, our conjecture was that strategic behavior acts as a 'smoothing' operator on the original decision boundary, but as we show, the actual effect of strategic behavior turns out to be more involved.
To build an intuition of the mechanisms at play, we take a bottom-up approach and study three mappings between (i) individual points, (ii) classifiers, and (iii) model classes. For points, we begin by showing that the mapping is not necessarily bijective. As a result, some points on the original decision boundary become 'wiped out', while others are 'expanded" to become intervals (ares for le costs) on the induced boundary. We demonstrate several mechanisms that can give rise to both phenomena. For classifiers, we show how the effects on individual points aggregate modify the entire decision boundary. A key finding is that certain decision boundaries are impossible to express under strategic behavior. We give several examples of reasonable classifier types that cannot exist under strategic behavior, and show that some effective classifiers hA can be traced back to (infinitely) many original classifiers h. The main takeaway is that universal approximators, such as neural networks or RBF kernels, are no longer universal in a strategic environment.
Our main contribution lies in our analysis of model classes, where our results build on the observation that the mapping from original to effective classifiers within a class is not necessarily bijective. In particular, because many h can be mapped to the same ha, the VC dimension of the induced model class can shrink even from co down to O, causing model classes that were not learnable in the standard setting to become learnable in the strategic one. That said. the VC dimension of the induced class can generally either grow or shrink. We highlight some conditions that guarantee either of these outcomes, and, in particular, provide an upper bound on the strategic complexity increase for the expressive family of piecewise-lineat model classes (e.g., ReLU networks). Our analysis yields several practical takeaways for learning, model selection, and future method development (see Appendix C.) We conclude with experiments that shed light on how strategic behavior may alter the effective complexity and maximum accuracy of the learned model class in practice.
2 Related work
Our work focuses on the common setting of supervised binary classification, where non-linear models are highly prevalent in general. This follows the original formulation of strategic classification [3, 16), which has since been extended also to online settings [1. 5, 8] and regression [2, 31]. As noted, linear models have thus far been at the forefront of the field, with many works relying (explicitly or implicitly) on their properties or induced structure [5, 10, 18, 25, 29J. Even for works with results that are agnostic to model class selection, linear classifiers remain the focus of special-case analyses, examples, and empirical evaluation [20, 26, 371, and their generality does not shed light on the impact of non-linearity. Other works offer only tangential results, such as welfare analysis in the non-linear setting [35], but do not paint a picture of the general learning problem. Our low-level analysis makes use of ideas from the field of offset curves from computational geometry [12, 21). Whereas this field mostly concerned with the approximation and analytical properties of individual offset curves, we are
2

---

4
Figure 1: (Left) Original non-linear classifter h. (Middle) Strategic response to original classifier. (Right) Resulting effective classifier ha (different from h)) after accounting for strategic responses.
interested in the effects on class complexity and what this implies for learning. In terms of theory, both [33, 36] apply PAC analysis strategic classification, the latter providing VC bounds for the linear class. Most relevant to us is [6], who study the general learnability of strategic learning under different feedback models. While not restricted to partieular classes, their analysis considers graph costs, where users can move only to finite set of possible points, and their results depend crucially on the cardinal- ity of this set. Our work tackles the more pervasive setting of continuous cost functions, which imply continuous modifications. The above works focus primarily on statistical hardness; while this is also one of our aims, we are interested in establishing a broader understanding of the non-linear regime.
3 Preliminaries
We work in the original supervised setting of strategic classification [3, 16). Let x = IRd denote user features, y E y {0. 1} their corresponding label, and assume pairs (z, y) are drawn iid from some unknown joint distribution D. Given a training set T = {(2, ): ~ D learning aims for the common goal of finding classifier h H that maximizes the expected predictive accuracy, where H is some chosen model class. The unique aspect of strategic classification is that at test time, users modify their features maximize gains in response to the learned h via the best-response mapping
x = (x) = argmax argmax c(x, x')
(I)
where a determines their utility from obtaining a positive prediction ý h(x), and c is a function governing modification costs. We assume w.l.o.g. that the user gains no utility from a negative prediction. Like most works, we focus mainly on the lg cost, i.c., c(2, xx' = || x' [|2, but discuss other costs in a subset of our results (see Appendix C.1 for discussion on how our results generalize to other cost functions). Because no rational user will pay more than a to obtain a positive prediction, x will always be contained in the ball of radius around x, denoted Bx = (x' c(x, S a). It will also be useful to define the corresponding sphere, (x) = {x' c(z,2') = a}.
Given the above, the learning objective is to maximize the expected strategic accuracy, defined
argmax En (y = h(AM()))) BEW
(2)
1ff(x) Levels of analysis. We assume w.l.o.g. that classifiers are of the form h(x) 1(x)=1{f(>>>>> 0} for some scalar score function f. and that the decision boundary is then the surface of points for which fxx = 0. Our analysis takes a 'bottom-up' approach which we first consider changes to individual points on the boundary, then ask how such local changes aggregate to affect given classifier h. and finally, how these changes impact the entire model class H. will therefore be useful to consider three mappings between original and corresponding strategic objects. For points, the mapping is z + (=) = {o (2 Z A c(x, = a). i.e., the set of points æ that, in response to h, move to maximal cost. For classifiers, we define the effective classifier as ha (x) == h(Ax(z) (see Fig. 1). and consider the mapping h + ha- Since both and ha are defined w.r.t. raw (unmodified) inputs x, this allows to compare the original decision boundary of to the 'strategic decision boundary' of its induced h For model classes, we consider the mapping H + HA* = (ha h H}. and refer HA the effective model class.
The linear case. As noted, most works strategic classification consider H be the class of linear classifiers, h(z)= = 1 fw" x 2 b}. A known result is that A (z) can be expressed in closed form as
3

---

Figure 2: Types of point mappings. From left to right: one-to-one (case #1), direct wipeoul (case #2), indirect wipeout (case #2), expansion (case #3), and collision (case #4). Black lines show original h, dashed gray lines indicate has gold arrows show Vn(2). and dotted circles show (x)
conditional projection operator: z moves Prooj - w TT==b w if h(x)) and (Tro)) I a. || and otherwise remains at x [9]. Note that all points that move do so in the same direction, i.e., orthogonally to w. Furthermore, each x on the decision boundary of is mapped to a single, unique point on the decision boundary of ha at an orthogonal distance (or cost) of exactly a. Considering this for all boundary points, we get that ha simply shifts the decision boundary by a, which gives ha(z) (z) = [(w" x 2 b a}. Thus, HA remains the set of all linear classifiers, and so HA* H.
The non-linear case: first steps. Informally stated, the main difference in the non-linear case is that points no longer move in the same direction (see Fig. 1). Note that while points still move to the 'closest' point on the decision boundary, the projection operator is no longer nicely defined. As a result, the shape of the decision boundary of / may not be preserved when transitioning to ha- Moreover, as we will show, some points on the decision boundary of h will 'disappear" and have no effect on the induced has while other points may be expanded to affect a continuum of points on ha- final observation is that directionality is important in the strategic setting: because points always move towards the positive region, the shape of ha for some h may be very different than that of the same classifier but with "inverted" predictions, hx)))
hzz). This lack of symmetry means that we cannot take for granted that the induced HA will include both ha and 1 ha, even if H does.
4 Underlying Mechanisms
Due to the added complexity the non-linear setting, we first present some basic results and observations related to the underlying mechanisms of the non-linear setting in order to build the necessary intuition for our higher-level results. We begin by examining the point mapping H> (=()) and then turn to investigate how strategic behavior affects the classifier mapping h + ha.
4.1 Point mapping
To gain an understanding of what determines the shape of ha of general h. begin by considering a single point on the decision boundary of h and examining how (and if) it maps to corresponding point(s) on the decision boundary of h& through the point mapping 2 + Vn(z). We identify and discuss four general cases, illustrated in Fig. 2:
Case #1: One-to-one. For linear h, the point mapping is always one-to-one. For non-linear h, the mapping remains one-to-one as long as h is 'well-behaved' around z. We consider this the 'typical' case and note that each is mapped to its a-offset point z w.r.t. h (see Appendix 1) A necessary condition for one-to-one mapping is that is smooth at z, but smoothness is not sufficient, as the following cases depict.
amg, where n is the unit normal at
Case #2: Wipeout. Even ht is smooth at 2, in some cases the point mapping will be null: 2 ++ Ø. We refer to this phenomenon wipeout, and identify two types. Direct wipeout occurs when the signed curvature x at z is negative and sufficiently large magnitude; this is defined formally in Sec. 4.2. Intuitively, this results from strategic behavior obfuscating any rapid changes in the decision boundary of h. Indirect wipeout occurs when the set of points (x(2) is contained in B, (x') for some other x' the decision boundary. For both types, the result is that B, (2) is entirely contained in the positive region of ha and such 2 have no effect on ha (see Appendix B.2).
Case #3: Expansion. When the decision boundary of h at is not smooth (i.e., a kink corner), z can be mapped continuum of points on the effective boundary of has This, however, occurs only when the decision boundary is locally convex towards the positive region. The set of mapped

---

points (2(2) are those on (2) which do not intersect with any other (z') for any other x' on the boundary of h. Thus, the shape of the induced 'artifact' is partial to a ball. Partial expansion may occur if some of the expansion artifact is discarded through indirect wipeout (Appendix C.2).
Case #4: Collision. A final case is when a of points (21...Zn) } the boundary of h are all mapped to the same single point z on ha, i... (=(=)= = (x'=)) = x for all 2' in the set. Typically, this happens at the transitions between well-behaved decision boundary segments and wiped-out regions, Collision often results in non-smooth kinks on ha, even if all source points were smooth on h.
4.2 Curvature
Building up to the level of classifiers, it is first useful to examine what happens to boundary points in terms of how h behaves around them. We make use of the notion of signed curvature, denoted K, which quantifies how much the decision boundary deviates from being linear at a certain point x. For d = 2, curvature is formally defined 6 = 1/r, where r is the radius of the circle that best approximates the curve at æ. For d > 2, we use x = sup(K), (K), where K includes all directional curvatures at æ (see Appendix 1). The sign of и measures whether the decision boundary bends (i.e.. is convex) towards the positive region (x > 0), the negative region (x < 0), or is locally linear (x- = 0).
Let z be typical point on the decision boundary of h which satisfies the one-to-one mapping detailed in Sec. 4.1. We borrow a classic result from the field of offset curves [12] to calculate the effective signed curvature of h at z, denoted KA, function of the curvature of h at
Proposition 1. Let be point on the decision boundary of h with signed curvature k. 2 -1/a. The effective curvature of the corresponding x on the boundary of ha is given by:
KA = =x((1++ + ax)
(3)
When d >> 2, each x E K is mapped as in Eq. 3 to form Ks = {*/(111 + ax) K E K), and K follows. See Appendix B.3 for proof and illustration of how this impacts the shape of ha. Prop. entails several interesting properties. First, strategic behavior preserves the direction of curvature, i.e,, K KA 2 0 always. In particular, remain linear. Second, the effective curvature KA is monotonically increasing in K, concave, and sub-linear. This implies that for x > 0 the effective positive curvature decreases, while for 0 the effective negative curvature increases. Thus, strategic behavior acts as a directional smoothing operator, i.e., the boundaries' rate of change is expected to decrease but only in the positive direction.
entails A = which explains why linear functions
Finally, in the positive direction, K& is bounded from above, approaching 1/a as K - cc. This gives: Observation 1. No effective classifier ha can have positive curvature KA greater than 1/a.
When d 2, Obs holds for each curvature K E K and can be summarized as n² S 1//a. Though Prop. 1 only implies Obs. 1 at points on ha that are typical, we will show in Sec. 4.4 that it is also true at any point on ha- The above holds irrespective of the shape and curvature of the original h. In particular, non-smooth points on h (i.e., with x. -> oo), such as an edge or vertex at the intersection of halfspaces, become smooth on ha, Conversely, in the negative direction, KA approaches 0o as x -> 1/a. Thus, negative curvature can grow arbitrarily large, and at =-::==--eeee -1/a maps to a non-smooth "kink" in has KA is no longer defined when x crosses the asymptote at -1/a because such points are wiped out and have no corresponding on the boundary of ha. This is the exact case of indirect wipeout in Sec. 4.1 (see Appendix B.2 for proof and Appendix C.10 for practical use in learning).
Observation 2. Any point z on the decision boundary of h with curvature K < <-1aa has no influence on ha. In higher dimensions, this is true for any point x with in) < -1/a.
4.3 Containment
Because the decision boundary is a level set of some (non-linear) score function f. contained regions are not only possible, but realistic. Consider a given classifier where the decision boundary forms some bounded connected negative region C C Rd where h(x)) = 0 Vix E C. Strategic behavior dictates that negative areas shrink, and so only subset of C will still be classified as negative in ha. If C' is sufficiently small, then it will disappear completely leaving hs I Vz E C.
Observation 3. Any negative region C fully contained in some (x(2²) will become positive in h
5

---

Figure 3: Types of impossible effective classifiers. From left right: small positive region, narrow positive strip, large positive curvature, piecewise (hyper)linear convex towards the positive region.
The fact that positive areas grow and negative areas shrink also implies that there is minimum positive region size that can exist in any ha- This idea will be formalized and generalized later in Sec. 4.4. One implication of Obs. is that when negative regions wiped out, two or more positive regions may merge, leading to a less expressive decision boundary. On the other hand, the strategic setting can also split a negative region, creating more expressive decision boundary (see Appendix C.3).
Observation 4. Strategic behavior merge positive regions and split negative regions thereby either increasing or decreasing the number of connected regions (either positive or negative).
4.4
Impossible Effective Classifiers
Based on the above, we derive two general statements about effective classifiers that cannot exist. Each statement considers some candidate classifier g. and shows that if g satisfies certain property, then there is no classífier & for which is its induced effective classifier, i.e., * ha for any h. We first require some additional notation. Given h, define the set of negatively classified points as (h) (x h(()) = 0}. For a set A C X, we say point x is reachable from Eod E A c(x, ((x,x') S a. Proposition 2. Let be candidate classifier. If there exists point x the decision boundary of such that all points x' E (z(z) are reachable from some point in Xo(g), then there is no h such that g h2-
The intuition behind Prop. is that no can simultancously strategically classify as positive while all E (g) as negative. Full proof in Appendix B.4. As stated in Prop. 3, when is smooth at I, Prop. can be simplified to require that only a single point be checked instead of all of (x.).. Proposition& 3. Let be a candidate classifier. If there exists a point x on the decision boundary of where (i) g is smooth, and (ïi) the offset point i on is reachable by some other x' (o(g) then there is no h such that g has
The intuition behind Prop. 3 is the same as for Prop. 2. except that when is smooth at x, the only point in (x) that may not be reachable by some x' Xo(g) is the a-offset (see Appendix B.5).
Examples. The implication of Props. 2 and 3 is that there exist decision boundaries that are generally realizable, but are longer realizable effective classifiers in the strategic setting. Note that because it only takes a single decision boundary point to render an entire effective classifier infeasible, each of these examples broad categories and pose meaningful restrictions the set of possible effective classifiers. As illustrated in Fig. 3, we highlight four types of impossible effective decision boundaries:
1. Classifiers with a small positive region that can be enclosed by a ball of radius a.
2. Classifiers with a narrow positive region which points are a-close to the decision boundary.
3. Classifiers with large positive signed curvature anywhere on the decision boundary.
4. Classifiers with any locally convex piecewise linear or hyperlinear segments.
All proofs are in Appendix C.4, and either build on Obs. 1-4, show the conditions of Props. 2 or hold. From these four examples, we note the following observation.
Observation 5. The mapping h + ha is not bijective, with many candidate ha having no corre- sponding h and many h mapped to the same ha.
In Appendix C.5 we show that there are actually infinite that map to nearly all possible ha- Furthermore, Obs. 5 will be important for proving Thm. I and Cor. 1.

---

Figure 4: (Left) Example of increasing VC. (Right) Example of dataset with limited strategic accuracy. Any ha which correctly classifies the gold-rimmed point must err on a negative point.
Class-level analysis
On the classifier level, the strategic setting is clearly more restrictive than the regular setting. Indeed, in Sec. 5.2 we extend this idea into the model class level by analyzing the impacts on universality and optimal accuracy. However, than the classifier mapping since complexity can actually increase as a result of strategic behavior.
show in Sec. 5.1, the model class mapping is more nuanced
5.1 Class complexity
Recall that for linear classes, Ha remains linear, and so H + HA H. Although this equivalence not unique the class linear classifiers (see examples in Appendix C.6). typically, we can expect strategic behavior to alter the complexity of the induced class. Here, we use VC analysis to shed light on this effect by examining the possible relations between VC(H) and VC(Ha).
Complexity reduction. Since our results so far point out that effective classifiers are inherently constrained, a plausible guess is that effective complexity should decrease. Indeed, there are some natural classes where the VC cannot increase. For example:
Proposition Let Q be the class of negative-inside k-vertex polytopes bounded by radius of s, then VC(Q.) 2 VC(QE,a). Moreover, if oc, then VC(Q!) VC(Q", as implied by Thm.
The proof for Prop. can be found in Appendix B.7. Curiously, in some extreme cases, the VC reduction spans the maximum extent.
Theorem 1. There exist several model classes H where VC(H) co, but VC(Ha) = 0.
The proof for Thm. can be found in Appendix B.&. See Appendix C.7 for other examples where VC strictly decreases but does not diminish completely. Thm. carries concrete implications for strategic learning:
Corollary Some model classes that are not learnable become learnable strategic environments.
Complexity increase. Though a lower effective VC is indeed possibility, a more plausible outcome is for it to stay the same or increase. As an intuition for how the VC might increase, consider the simple example in Fig. 4 (left). Here, H includes four non-overlapping classifiers (each color separate classifier) with VC(H) 1. Yet, with strategic behavior, the effective classifiers (dashed curves) overlap, increasing the shattering capacity to 2. This case can be generalized to give V VC(HA) 0(d (H) (see Appendix C.8). We next identify simple generic sufficient condition for the effective complexity of any learnable class to be non non-decreasing.
Theorem 2. If H is closed under input scaling and VC(H) < oc, then VC(H) S VC(HA).
The proof for Thm. can be found in Appendix. B.9. Thm. applies to many common classes, including polynomials, piecewise linear functions, and most neural networks. See Appx. C.10 for implications model selection.
Because Thm. suggests that the effective VC can increase, but does not state by how much one concern would be that this increase can be unbounded, which would deem the effective class unlearnable. Our next result shows that this not the case even for the common and highly expressive class of lineea classifiers (with bounded number of segments), which includes neural
'Thi aligns with the notion of strategic VC used in [22, 33), i.e., SVC(H) vC(Ha).
7

---

networks with ReLU activations (of fixed size) as special case, and is often used in studies on neural network approximation [e.g.. 19, 28).
Theorem 3. Let Hm.k be a class of piecewise-linear classifiers with at most m segments and intersections of linear segments. Then VC(H = O (d log(m) + +vp k klog(k)), where vp is the VC of the class of lp norm balls, and is (dd) for 1,2,00. 20.
The proof for Thm. is in Appendix B.10. We also prove that VC(Hm.,)) = O(d (m)). )))) suggesting that the effective VC dimension can increase, but only limited extent. The main implication of Thm. 3 is therefore that under these conditions, strategic behavior maintains learnability: for any H that can be expressed (or approximated by) piecewise- -inear functions, if H (or its approximation) is learnable, then HA is also learnable. We conjecture that this relation remains true for general H; see Appendix A.3 for discussion on the challenges of the general case and connections to [6]. For the special case of positive-inside polytopes - a subset of the piecewise-lineal class the effective VC dimension even maintains the same order of magnitude.
Theorem 4. Consider either the l,, ly. or toe costs and let H S pk where pk is the set of all k-vertex polytopes in R and has VC(Pk) (dd² k log [33] Then VC(Ha) = O(d k log k).
The proof for Thm. 4 is in Appendix. B.11. Note that for the l and foo costs, the effective class remains within the polytope family, but potentially with additional vertices (see Appendix B.6). For the l2 cost, the bound still holds despite HA no longer including only polytopes (since corners in can become "rounded" in h
5.2 Universality and approximation
Our results in Sec. 4.4 show four 'types' of decision boundaries that cannot be attributed any effective classifier, though others may exist. This implies that several basic classifiers are not realizable in the strategic setting and cannot be approximated well. This drives our principal conclusion:
Corollary 2. Any universal approximator class H. is no longer universal under strategic behavior:
In other words, there exists classifier g for which no effective class HA can include g member, even for H that are universal approximators in the non-strategic setting. Common examples of universal approximator classes include polynomial thresholds [32], RBF kernel machines [27], many classes of neural networks [c.g., 17], and gradient boosting machines [13]. In the strategic setting, these classes are no longer all all-aancopasinng like in the standard setting.
Approximation gaps. Cor. implies that even if the data is in itself realizable, and even without any limitations on the hypothesis class, the learner may already start off with bounded maximum training accuracy simply by learning in the strategic setting. Fig. 4 (right) depicts one such example dataset where the maximum attainable accuracy drops from 1 to 0.96. This is because strategic behavior makes it impossible to generally approximate intricate functions, e.g., by using fast-changing curvature (via increased depth) many piecewise-lineds segments (with ReLUs). Another result is that the common practice of interpolating the data using highly expressive over wverpaarmeerrized models (e.g., s. as in deep learning) is no longer viable approach. On the upside, it may be possible for the strategic responses to prevent unintentional overfitting, allowing for better generalization.
In extreme cases, the gap between the maximum standard accuracy and the maximum strategic accuracy can be quite large. Our next result demonstrates that there are distributions in which, despite a maximum standard accuracy of 1, the maximum strategic accuracy falls to the majority class rate.
Proposition 5. For all d, there exist (non-degenerate) distributions on Rd that are realizable in the standard setting, but whose maximum strategic accuracy is the majority class rate, max,, p(y)..
In one dimension, the distribution can be constructed by placing a negative point the left and right of each positive point. In higher dimensions, negative points can be arranged in an Rd simplex around each positive point. The full proof is in Appendix 1.... Prop. 6 extends this idea show that there is distribution whose maximum strategic accuracy approaches 1/2 as increases. The general proof given Appendix B.1
Proposition 6. There exists a distribution that is realizable in the standard setting, but whose accuracy under any hy is at most 0.5 + [[a+I].
8

---

Effective Polynomial
Original vs. Effective Decison Boundarie
Strategic Performance Gap
1.00
12
2
0.95
26
Moximum Actunny
0.90
Stratagic Degras
8- 40
0.85
6-
0.80
0.75
Berchmaak
0.65
Banchmark
0
Original Degrue (0)
Class Separation GAL Hil)
Figure 5: (Iefft) Expressivity. For random polynomial classifiers of degree k. results show the smallest degree k' that captures the effective decision boundary. (Center) An instance showing positive curvature decreasing (A), negative curvature increasing (B), and wipeout (C). (Right) Ap- proximation. As data becomes more entangled (low separation), strategic approximation degrades.
In practice we expect the accuracy gap to depend on the distribution. We explore this gap experi- mentally See. 6. An interesting observation that in certain non-realizable settings, the maximum strategic accuracy can exceed the maximum standard accuracy. (see Appendix C.9).
6 Experiments
To complement our theoretical results, we present two experiments that empirically demonstrate the effects of strategic behavior on non-linear classifiers. The code for both experiments is available at https:// //gi thub. com/ TetM--TTeccniioo/cnnniiii
6.1 Expressivity
Following our results from Sec. 5.1 on the change in hypothesis class expressivity, we experimentally test whether the ia of a given random h belongs to a more or less expressive class than itself. In particular, we focus on degree-k polynomial classifiers and compare the degree k of l to the degree ka of the polynomial approximation of ha.² Because user features are often naturally bounded, we assume that x E X = R² and that x is bounded by |xr < 100. See Appendix D.1 for full details.
Fig. 5 (left) shows results for varying E [1, 10] and for a E [2, 40). When small, we find that ka 23 k. meaning that strategic behavior has little impact on expressivity. However, as a increases, ka becomes larger than k, suggesting that ha is more complex than This is due to the fact that as increases, point mapping collisions (see Sec. 4.1) become more likely, causing non-smooth cusps which are more complex than basic polynomials - form the decision boundary (Fig. (center)). When a is quite large, we see that KA is still larger for low k, but drops considerably for higher k. This can attributed to the fact that tightly-emeedded higher-dimension polynomials and increased strategic reach from large as are both causes of indirect wipeout (see Sec. 4.1) because they increase the reachability of (z) by other decision boundary points. As such, much of the original decision boundary is wiped out, leaving behind lower complexity effective decision boundary.
6.2 Approximation
As seen in Sec. 5.2, the lack of universality in the strategic setting can impose a limitation on the maximal attainable strategic accuracy. To demonstrate the practical implications of this effect, we upper bound the maximum strategic accuracy of any HA on a set of synthetic data by experimentally calculating the maximum strategic accuracy of the unrestricted effective hypothesis class H We compare the results to two benchmarks: (i) the standard accuracy of the regular unrestricted hypoth- esis class H* (which is always 1), and (ii) the strategic (and standard) accuracy of the linear effective hypothesis class lin = lin, The first benchmark measures the extent to which the strategic setting
Though the ha of polynomial h is not necessarily a polynomial, we can compare the expressivity of h and ha by finding the lowest degree-ks polynomial g that well-approximates hs.

---

hinders the learner, while the second measures the extent to which the learner can benefit from non-linearity, even in the strategic world. We generate data by sampling points from class-conditional Gaussians Nyju,, 1), and aim to find an h that obtains an optimal fit. The parameter serves to show how Ha compares to our two baselines under data that ranges from well-separated (large J1) to more "interleaved" and harder to classify by restricted classes (small μr). Details in Appendix D.2.
Fig. 5 (right) shows results for increasing class separation (p). As μ decreases and the classification problem becomes more difficult, the maximum strategic accuracy of H diverges from the upper H' baseline, with performance deteriorating as strategic behavior intensifies (i.e., larger a). Because any actual HA can only have worse performance than the ideal H this indicates that strategic behavior can become a significant burden in more difficult tasks, such as classification in non linearly- separable setting. Nonetheless, when is small, H significantly outperforms the lower H" bascline, signaling that non-linearities still improve accuracy the strategic setting despite any strategic effects.
7 Discussion
This work sets out to explore the interplay between non-linear classifiers and strategic user behavior. Our analysis demonstrates that non-linearity induces behavior that is both qualitatively different than the linear case and also non-apparent by simply studying it. Simply put, the strategic setting is fundamentally limited, though has few potential advantages. Our results show how such behavior can impact classifiers by morphing the decision boundary and model classes by increasing or decreasing complexity. Although prior work has made clear the importance of accounting for strategic behavior in the learning objective, our work suggests that there is a need for additional broader considerations throughout the entire learning pipeline from the choices we make initially (such as which model class to use) to setting our final expectations (such as the accuracy levels we may aspire to achieve). We detail practical takeaways for learning and model class selection in Appendix C.10. This motivates future theoretical questions, as well as complementary work on practical aspects such as optimization (i.e., how to solve the learning problem), modeling (i.e., how to capture true human responses), and evaluation (i.e., on real humans and in the wild).
Acknowledgments
The authors are grateful to Shay Moran and Nadav Dym for thoughtful discussions and suggestions. This work is supported by the Israel Science Foundation grant no. 278/22.
References
[1] Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Compulation, pages 6-25, 2021.
[2] Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani. Information discrepancy in strategic learning. In International Conference on Machine Learning, pages 1691-1715. PMIR, 2022.
[3] Michael Brückner, Christian Kanzow, and Tobias Scheffer. Static prediction games for ad- versarial learning problems. The Journal of Machine Learning Research, 13(1):2617-264,, 2012.
[4] Michael Brückner and Tobias Scheffer. Nash equilibria of static prediction games. In Advances in nearal information processing systems, pages 171-179, 2009.
[5] Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers. Ad- vances in Neural Information Processing Systems, 33:15265-15276, 2020.
[6] Lee Cohen, Yishay Mansour, Shay Moran, and Han Shao. Learnability gaps of strategic classification. 247:1223-1259, 2024. Publisher Copyright: @ 2024 L. Cohen, Y. Mansour, S. Moran and H. Shao.; 37th Annual Conference on Learning Theory, COLT 2024 Conference date: 20224 Through 03-07-2024.
10

---

[7] Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of evasion adversaries. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 228-239, Red Hook, NY, USA, 2018. Curran Associates Inc.
[8] 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, pages 55-70, 2018.
[9] Itay Eilat, Ben Finkelshtein, Chaim Baskin, and Nir Rosenfeld. Strategic classification with graph neural networks. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
[10] Itay Eilat and Nir Rosenfeld. Performative recommendation: incentives. In International Conference on Machine Learning, pages 9082-9103, PMLR, 2023.
diversifying content via strategic
[11] Andrew Estomell, Sanmay Das, Yang Liu, and Yevgeniy Vorobeychik. Group-fair classification with strategic agents. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, FAceT '23, page 389-399, New York, NY, USA, 2023. Association for Computing Machinery.
[12] R. T. Farouki and C. A. Neff. Analytic properties of plane offset curves. Comput. Aided Geom. Des., 7(1-4):83-99, June 1990.
[13] Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pages 1189-1122, 2001.
[14] Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohent and Nir Rosenfeld. Strategic classification in the dark. In International Conference on Machine Learning, pages 3672-3681.
PMLR, 2021.
[15] Alirio Gómez Gómez and Pedro L. Kaufmann. On the Vapnik-Chervonenkis dimension of products of intervals in Rdd arXiv e-prints, page arXiv:2104.07136 April 2021.
[16] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classi- fication. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 11 111-122 2016.
[17] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
[18) Safwan Hossain, Evi Micha, Yiling Chen, and Ariel Procaccia. Strategic classification with externalities. The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2023, 2025.
[19] Changcun Huang. Relu networks are universal approximators via piecewise linear or constant functions. Neural Computation, 32(1 22:224:24922255 2020.
[20] Meena Jagadeesan, Celestine Mendler-Düinner, and Moritz Hardt. Alternative microfoundations for strategic classification. In International Conference on Machine Learning, pages 4687-4697. PMLR, 2021.
[21] Soo Won Kim, Ryeong Lee, and Young Joon Ahn. A method approximating offset curve by bézier curve using parallel derivative curves. Computational and Applied Mathematics, 37(2):2053 2064, 2018. Cited by: 3.
[22] Anilesh K Krishnaswamy, Haoming Li, David Rein, Hanrui Zhang, and Vincent Conitzer. Classification with strategically withheld data. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5514-5522, 2021.
[23] Andrey Kupavskii. The ve-dimension of k-vertex d-polytopes. Combinatorica, 406)) December 2020.
[24] Tosca Lechner and Ruth Urner. Learning losses for strategic classification. Thirty-Sixth AAAI Conference Artificial Intelligence, AAAI, pages 7337-7344. AAAI Press, 2022.

---

[25] Sagi Levanon and Nir Rosenfeld. Strategic classification made practical. In International Conference on Machine Learning, pages 6243 6253. PMLR, 2021.
[26] Sagi Levanon and Nir Rosenfeld. Generalized strategic classification and the case of aligned incentives, In Proceedings of the 39th International Conference Machine Learning (ICML), 2022.
[27] Park and I. W. Sandberg. Universal approximation using dedial-basis-functie networks. Neural Computation, (2):246-257, 1991.
[28] Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep relu neural networks. Neural Networks, 108:296-330, 2018.
[29] Elan Rosenfeld and Nir Rosenfeld. One-shot strategic classification under unknown costs, In Forty-first International Conference on Machine Learning, 2024.
[30] Han Shao, Avrim Blum, and Omar Montasser. Strategic classification under unknown per- sonalized manipulation. In Advances in Neural Information Processing Systems, volume 36, 2023.
[31] Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. In International Conference on Machine Learning, pages 8676-8686. PMLR, 2020.
[32] Marshall Stone. The generalized weierstrass approximation theorem. Mathematics Magazine, 21(5):237-254, 1948.
[33] Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. PAC-learning for strategic classifi- cation. International Conference on Machine Learning, pages 9978-9988, PMLR, 2021.
[34] Aad Vaart and Jon Wellner. A note on bounds for ve dimensions. Institute of Mathematical Statistics collections, 5:103-107, 01 2009.
[35] Tian Xie and Xueru Zhang. linerr welfare-aware strategic learning. Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, 7:1660-1671, 10 2024.
[36] Hanrui Zhang and Vincent Conitzer. Incentive-aware PAC learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5797-5804, 2021.
[37] Tijana Zrnic, Eric Mazumdar, Shankar Sastry, and Michael Jordan. Who leads and who follows in strategic classification? Advances in Neural Information Processing Systems, 34:15257-
1 15269, 2021.
12

---

A Background
A.1 Signed Curvature
Our analysis makes use of the notion of signed curvature - a signed version of the normal curvature to quantity shape alteration. Because there an inherent notion of direction due the binary nature of class labels, we can define curvature as being positive if the curvature normal vector points in the direction of the positive region and negative if points in the direction of the negative region. Though in IR² this defines single value, we must instead define curvature value for each 'direction' in higher dimensions. More formally, for each tangent vector in the tangent hyperplane T5 at we define the curvature value Kj as the signed curvature boundary with the plane L containing f and the normal vector Ωg. Defining K = {NT: E E'E T as the set of all such curvatures, our analysis will focus on x* sup(K) in R and above.
on the curve obtained by intersecting the decision
A.2
Bounded/Unboundee Input Domain
At a high level, our results in Sec. 5 do not require an unbounded input space, but rather some input space that is larger than X. In particular, if we assume that raw inputs, æ, bounded by | S B, then for the problem to generally be well-defined, we must allow this space to expand at the minimum to B a accommodate for strategic input modifications. More generally, we must ensure that (x) < ((x) holds for all r and any h, for some expansion B(a) 2 B, where the exact form of ((a) depends both on the cost function and on H.
Other than Thm. 2, our results simply require the minimal expansion be satisfied and are therefore not dependent
unbounded input domain. Likewise, Thm. 2 does not require an unbounded input domain since for any given learnable H, there exists some finite B(aa) for which the result holds. However, since the statement is generic (i.e., applies to all learnable H that are closed to scaling), do not have a closed-form expression for (aa) that applies simultaneously to all such H.
A.3 General Upper Bound on VC Increase
In Thm. 3, we provide upper bound the strategic VC dimension of classes of seccewsse-liner classifiers, though note that a general upper bound remains an open question. A key difficulty in finding a general upper bound in the strategic setting is that points will move differently when facing different h from the same H. Thus, reasoning about the shattering of an arbitrary set must account for how points move under all possible h E H, though not simultaneously, which proved to be highly challenging in the general, unstructured case. This is why we have included results that exploit common structures like the upper bound based on piecewise linearity (Thm. 3) and lower bound based on H that are closed to scaling (Thm. 2).
That said, conjecture that Thm. 3 holds for general H, proven by Cohen et al. [6] in the special case of finite manipulation graphs. In particular, they show that VC(H&a) O(VC(H) log k) where is the degree of the manipulation graph. Note that the bound is not transferable to our case since is vacuous for k oc, and the proof technique does not apply to continuous graphs
B Proofs
Lemma 1. In R22 if the curvature K. at I is positive, then the radius Tinse of the maximum inscribed circle at x is no bigger than the radius Vosc = - of the osculating circle at x (the circle that best approximates the curve at x and has the same curvature). As a corollary, if curvature K at x is negative, then the radius Tesc of the maximum escribed circle x is no bigger than the radius of the osculating circle at x.
Tosc = =
Proof. Note that both the osculating circle and the inscribed circle have their centers along the normal line to the curve at r (and on the same side of h), and that the osculating circle may cross the curve at æ. If does, then any circle which has a larger radius and center on the same side of along the normal line to the curve will also cross the decision boundary at Jr so the radius of the inscribed circle (which strictly does not cross the curve) strictly smaller than the radius of the osculating circle. If the osculating circle does not cross the curve, then it must be the largest strictly tangent
13

---

circle at 2, or else it would not be the best circular approximation to the curve at z. As such, the largest inscribed circle, which must be both tangent the curve also intersect it anywhere else, must have radius that is no larger than Tose.
B.1 One-to-One Mapping
Claim: In the one-to-one mapping, the point z on the decision boundary of h is mapped to the point = oo the decision boundary of hig
Proof. Note that all points the decision boundary of ha must be the maximum cost away from h2, so (z(z)= C (z). Additionally, for each & E Vx(z), the ball B, (x), which is the set of points that x move to, must intersect the decision boundary of h (or else it would not be maximum cost away) and must furthermore be strictly tangent to the decision boundary of at 2. Given that the decision boundary of h is smooth 2, this means that the normal to the curve must along the radius of Ba (x) from z to implying that I = 2 + angz Because of the inherent directionality of is defined point in the positive direction. This means that only
the setting, the normal vector the point x = añt would seek to move to to gain positive classification, as r = z ant is either already labeled positive or can move closer point. Therefore, Vn = {2 -onz) in the one-to-one case.
B.2 Wipeout Mapping
Claim: Points on the decision boundary of that are 'wiped out do not affect the effective decision boundary of has
Proof. In the case of indirect wipeout, this follows directly from the definition: if x is contained in Ba(x') for some other x' on the decision boundary of h (or in the union of several B, (z')), then none of the points in (2) are at maximum cost away from h, and are therefore not on the decision boundary of ha-
In the case of direct wipeout, the normal one-to-one mapping fails because the point x = 2 - art is no longer at the maximum cost away from h. Specifically, because the curvature < -1/a" 4 the ball (x) now intersects h, which means that æ less than a away from and therefore not on the decision boundary of ha- For IR22, Lemma proves that the radius of the maximum escribed circle at < Therefore, there is no
is less than the radius of the osculating circle, so Tesc S Toee circle of radius that is strictly tangent (on the negative side), (z must intersect h.
For higher dimensions (see Appendix A. there is no longer a single normal curvature. Instead, we define the set K of curvatures in each plane p E P defined by the normal vector and some tangent vector at z. Note that Bx(x) will intersect h if any of its projections onto each E P (a circle) intersects the curve obtained by intersecting the decision boundary with the plane Since each of these cases are in IR2 B, (Ir) will intersect h inf(K) < -1/a.
B.3 Proof of Proposition
Let be a point on the decision boundary of with signed curvature k. 2 -1/a. The effective curvature of the corresponling x the boundary of has is given by:
Proposition 1:
x/ + ak)
(3)
Proof. While an equivalent form of Prop. has already been proven in the field offset curves [12]. we nonetheless reprove it here offer some intuition behind In the normal, one-to-one mapping. because both the center of curvature and (x(2) lie on the normal line to h at z (see Appendix B.
Otherwise, æ would not be points adjacent to can also strategically move to achieve a positive classification. orr inf -1/a for d > 2. See See. 4.2 and Appendix A.1 for curvature definitions
boundary positive and negative classification by ha because of the
14

---

curvature Mapping ia
-3
Уйрeout
-5
<1gg
1/b
Figure (Top) Graph of Eq. 3 with asymptotes represented as dashed lines. (Bottom) Depictions of curvature mappings for increasing
strategic movement can be seen as increasing the signed radius of curvature, Toses by a (where we will define the radius of curvature as negative if the curvature is negative 2). In higher dimensions, this is equivalent to increasing each of the radii of curvature by a (see Appendix A.1). We therefore have:
Tosc, = Tose + a
KA
Tosc,
Tosc + a
+
+ ak
Fig. shows the graph of Eq. as well as examples of curvature mappings for various K. Note that Eq. has horizontal asymptote KΛ = 1/ox because the effective curvature cannot exceed 1/a (see Sec. 4.4). Additionally, Eq. 3 has a vertical asymptote at -1/ox because any point with lower curvature has effect ha (see Appendix B.2). When x. -1/a, mapped non-smooth kink of infinite curvature.
B.4 Proof of Proposition
Proposition 2: Let g be candidate classifier: If there exists point the decision boundary of g such that all points x' E Sa(x) are reachable from some point in Xo(g), then there is no such that g ha-
Proof. In order for to be the effective classifier the regular classifier h, we must have:
1. For each point that is positively classified by g, there must be point g' E Ba(g) which is classified as positive by h. other words, q must be able to acquire positive label by staying in place strategically moving within (g)
2. For each point that is negatively classified by g, there cannot be any points q' E Ba which are classified as positive by h. other words, q must not be able to acquire a positive label by staying in place strategically moving within (xx
Assume there exists point & on the decision boundary of g such that all points a' E (x) are reachable from X (g) and that there exists h such that h&. Since is on the decision boundary
15

---

Figure 7: (Left) Each face of negative-inside polytope is mapped to a new linear face, though the resulting ha may be a polytope with fewer faces and vertices due to wipeout. (Right) Each face of desitive-inside polytope is also mapped to a new linear face, though each vertex will have to expand to fill the gap between these faces.
of g. there exists a point x + 6, + that is negatively classified by g. For requirements and 2 to hold, there must be point z' S {qg
(z), &f Ba + +)} that is positively classified by h. Since C So (z), we can expand the claim to say that there must be point x' E (.))) that is positively classified by h. However, if all points x' E (x:) are reachable by some point q that is negatively classified by g. then none of the points x' E (x) can be positively classified by (by requirement 2). Therefore, if there exists point x on the decision boundary of g for which every point on the sphere S. (x) is reachable by some point that is negatively classified by g. then cannot be a possible effective classifier.
B.5 Proof of Proposition 3
Proposition 3:
Let g be a candidate classifier. there exists a point x on the decision boundary of 9 where (i) g smooth, and (ii) the offset point i añ, is reachable by some other x' No((9). then there is no h such that g = ha-
Proof. By Prop. for each point on the decision boundary of g, there must be point x' on S. (ar) that is classified positively by h and also not reachable by any point negatively classified by g. As a result, the ball (x.), which is the set of points that can move to x', must not intersect the decision boundary and must furthermore be strictly tangent to the decision boundary at x. Given that the decision boundary smooth at x, this means that the normal to the curve at x must run along the radius of Ba (x') from æ to x', implying that x' = x + att.. Because the strategic movement is in the direction of positive classification, the only possible option is for move x'
aft. However, if z' = + añ is reachable by some point that is negatively classified by ha, then the associated h would not have classified z' positive, would not have been a positively classified point by hs.
B.6 Effective Class of Polytope Family
Each polytope is simply combination of n linear faces. As such, when polytope has a negative inside, each face will be mapped to a new linear face (with some wipeout of part or all of the face) leading to hA that is a smaller-radius polytope, albeit with potentially fewer faces and edges (see Fig. (Left)). Although the faces of a positive-inside polytope also map to new linear faces, each vertex will have to expand to fill the gap between these new faces. As such, ha now a larger polytope whose corners are partial to a ball (see Fig. 7 (Right)). For the l and too costs, ha therefore remains a polytope since the E and foo balls are piecewise-lines now a polytope with rounded corners. In either case, the decision boundary of each p E Ph can be seen as the intersection of a radius-scaled p and & balls centered at each vertex of p².
themselves. For the E2 cost, ha is
B.7 Proof of Proposition
Proposition 4: Let Q+ be the class of negative-inside k-vertex polytopes bounded by radius of then VC(Q.) 2 VC(Q) Moreover, if s = cc, then VC(Q.) VC(Q) >) as implied by Thm. 2.
Proof. As noted in Appendix B.6, negative-inside polytopes map to smaller-radius negative-inside polytopes with potentially fewer faces and vertices. As such Q* A C Q so VC(Q) S VC(Q?).
16

---

Figure 8: Example h from class H where VC(H) co, but VC(Ha) = 0. The gray dashed curve the ha of any like the one above. Each such has the same small gap where the decision boundary remains above the dotted purple curve.
However, = oc, the class O is closed to input scaling leading to VC(Q),)) VC(Q.) by Thm. 2, so we must have that VC(Q),)) VC(Q.).
B.8
Proof of Theorem
Theorem 1:
There exist several model classes H where VC(H) oc, but VC(Ha) = 0.
Proof. We provide two examples. For the first example, fix a and consider the class of R classifiers H {hg S 2²) where hg 1(x (s) Vs E S). Each classifier in this model class contains small, non-overlapping negative regions centered lattice points. Thus, the negative regions of all h E H will disappear under strategic movement, leaving (x) vh E H. Despite the fact that H shatters 2² (and therefore has (C(H) = oo), HA cannot shatter a single point (and therefore has VC(Ha) 0).
Another example where مa perhaps more natural can be seen in Fig. 8. In this case, H is the class of classifiers with narrow gaps whose decision boundaries can be written as
1
|x 2
2 0 k. x2 f((1)
k,
hy (2((
[1 <
(4)
0
else
where some constant less than and each function (x1) satisfies f((11) 2 / x.
Va² - 12 for all -k < #1 S k (i.c., f((x) lies above the radius-a are between (-k, 0) and (k, 0)). In this case, the decision boundary points in the gap will get wiped out on all h E H. leaving the exact same has Because is nearly unrestricted in the range -k S I1 & k. it is capable of shattering infinite points that lie in this range and has infinite VC dimension. On the other hand, because |H = 1, we get A =
B.9 Proof of Theorem 2
Definition 1. A hypothesis class H said to be closed to input scaling for all M(x) E H and for all O, we have that h2 (x) h((x) E If as well.
Note that the families of polynomials and polytopes are clearly closed to input scaling. Furthermore, most classes of neural networks are as well since h(az) can be realized by scaling the first weight vector by a.
Theorem 2: If H is closed under input scaling and VC(H) < cx, then VC(H) S VC(HA).
Proof. Intuitively, the reason that the VC dimension cannot decrease that for any with a VC of dimension l that is closed to input scaling, we can find set S of k points that can be shattered by H. where none of the points E S strategically move under any of the h E used to shatter S. As result, HA will also shatter S, its VC dimension is at least k.
17

---

Let (C(H)= = k and G C H be a set of 2 classifiers that shatters some set S of & points. Define Cp s. g) as the minimum strategic cost necessary for point to obtain positive classification from classifier I and define (S, G) as the minimum strategic cost for any S to obtain positive classification from a classifier g E that classifies negatively:
Creg (S, (n
min sES, gEC, gEG, g(e)=0 (DB(s.g)
(5)
Since both S and G are finite sets and negative points face strictly positive cost to obtain positive classification, we get that there exists unique value Cney (S, G) 0. Additionally, because the VC dimension indifferent input scaling'. if we scale both the classifiers and the points, then G' = {g(az) g(x) E G} will shatter S" ={az z E S} with Cneg (ne G') that because H is closed to input scaling, G" C H as well. Furthermore, if we choose
Gney () N Note a+ GS)
Note that if (Seg(S', G > a, no point E S' will move strategically under any g' E G', meaning that s' (s') 9 (s') Vg' E G, s' E S", As a result, G will also shatter S' so (C(G)) 2 |5"| k. Since GA C HA. we get that
then Cneg (S', G') = a
VC(HA) 2 VC(GA) === VC(H)
B.10 Proof of Theorem 3
Theorem 3: Let mm.k be a class of piecewise-linear classifiers with at most m segments and k intersections of linear segments. Then VC (d log(m) + up k log()))), where vp is the VC of the class of norm balls, and is ((d) for = 1,2,
Proof. We will make of the following known results:
Lemma 2 (Gómez and Kaufmann (2021)). Let H Ball be the class of all Ep balls in Rd, Then H Ball has VC dimension BClH = ((d) for = 1,2, or oc [15].
Lemma 3 (Vaart and Wellner (2009)). Let classes C1 C2 have VC dimensions V1, V2, Vn and V Σ/= Vr, Let Cu Lyy= C₁ = 1 : hy E C₁h, and let C₁ = =m = {0 hy hy E Cj}. Then both Cū and C₁ have VC dimension upper bounded by O(V log(k)) [34].
We note that by combining Lemmas and 3, the class Helll of the union of up to f, balls has a VC dimension of O², k log(k)), which becomes O(d k log(k)) in the case of either the é,, f2, or lx norm cost functions. Additionally, the class H HLin of piecewise linear models with up to m segments has a VC dimension of Old m log(m)).
Because linear classifiers map to new shifted linear classifiers, all we have to do to determine the effective classifier a piecewise-linear i is to combine (take the union of) the effective segments of each linear segment in h and the potential fp ball artifacts around each intersection. Note that, as seen in Fig. (Left), some of the effective segments may be wiped out in this process, and, as seen in Fig. 7 (Right), only intersections that open to the positive region will induce Ep ball artifacts in Aa- Therefore, the ha of a piecewise linear with m segments and i intersections will be the intersection of a piecewise linear classifier with up m segments and up to l: Ep ball artifacts. As result, we can write HA G n HBaall where G C Hiin Therefore:
'Input scaling only changes the distance between points, but does not change their relative positions, so the class H and its input-scaled class H' will have the same VC dimension.
"Note that combining the two technically proves the bounds for the classes of the union of exactly k balls and exactly m segments, respectively, though we can easily expand them to the classes of up to & balls and up to segments by recognizing that some of the balls/segments from classes C1, Ca,... may be the exact same.
18

---

VC(Ha) VC(G n H
O(VC(G)+ + ))(H)
S <O(VC(Um + va(H)all)
= =((dmlog(m) + up &o (k)(k:)
Consequently, if H is learnable, then HA is too.
B.11 Proof of Theorem 4
Theorem 4:
Consider either the f,, &z, or loo costs and C pk, where pk is the set of all k-vertex polytopes in R and has VC(P*) O(d k log k)(33). Then VC(HA) = O log k).
Proof. As seen in Appendix B.6, the effective classifier of a k-vertex polytope the intersection of larger radius (or smaller for negative inside polytopes) k-vertex polytope and k Ep balls centered at each of the vertices. Therefore, HA C Pk n H by Lemmas 2 and 3 (and the VC dimension of Hhall derived in Appendix B.10):
VC(H&) & VC(pk n ( =(CC(PP) + VC(H)all)
Old klog(k)) + O(d k log(k))
Odd k klog(k))
B.12 Proof of Proposition 5
Proposition 5: For all d, there exist (non-degenerate) distributions on Rd that are realizable in the standard setting, but whose maximum strategic accuracy is the majority class rate, max, ply).
Proof. Fix d and choose any arbitrary set of positive points X1. When = 1, the set of negative points Xy can be constructed by placing a negative point 8 to the left and right of each positive point. When d >> 1, this generalizes to selecting d + points around each positive point æ E Xi that form an Rd simplex (z)² In this case, the classifier h(x) 1 (x X₁ achieves perfect standard accuracy, and the classifier that classifies all points as negative will achieve a strategic accuracy of d+1 Note that for each point in space to which x E X can strategically move, there exists at least d+2
one x' (x)))) that
well. Therefore, for each positive point X that achieves correct positive classification by strategically moving to q (g can be the same as x. it doesn't move), there unique negative point x' (x)) that achieves incorrect negative classification by strategically moving to so the strategic accuracy does not benefit from correctly classifying any positive points. As result, the maximum strategic accuracy is achieved by correctly classifying each negative point and incorrectly classifying each positive point, which gives the majority class rate.
B.13 Proof of Proposition 6
There exists a distribution that realizable in the standard setting, but whose accuracy under any ha is at most 0.3 + [2a+1]'
Proposition 6:
"We can assume without loss of generality that N xxE,, (x) Ø Var, E X, since there are infinite options for each 2zl and can just pick ones that do not overlap.
19

---

Proof. Consider the set of lattice points in R' with alternating labels. Although f(z) sin(TT) achieves perfect standard accuracy on this distribution, we will show that the maximum strategic accuracy for any model class is 0.5 + [2x++TT which approaches 0.5 as a + x. Note that in Rt, the minimum length of positive interval is 2o. Additionally, for each positive interval I of length k, I will contain either [A] or [K] + points and include at most one more positive point than negative points. Therefore, each interval will, at best, be correct | out of [K] points, which is optimized for = 2a (i.e., the minimum possible value of k). Furthermore, because the negative intervals may also only have at most one more negative point than positive points, the negative intervals are optimized when they include only a single negative point. As such, an optimal strategic classifier h consists of repeated positive intervals that include [2a] points, followed by a negative interval that includes one negative point. For each positive and negative interval group, h correctly
classifies at most |2a +1
1 out of 2a + 1J points correctly for an overall maximum accuracy of
[2 +1 [2++1] = 0.5 + [2+1]]
C
Additional results
C.1 Other Cost functions
Our low-level analysis (Sec. 4) begins with a focus on the fz-norm cost, both because it is the most popular choice in the literature, and because we found offer the best intuition. Nonetheless, most of our results hold more broadly, and in particular, all theorems and propositions in Sec. 5 generalize to any lp (p 1) norm:
Prop. 4 applies generally, since negative-inside polytopes are still mapped to smaller negative-inside polytopes under general l, cost functions.
Thm. 1, Cor. 1, and the example in Fig. of increasing VC dimension remain under minor tweaks to the constructions that take into account the differences in shapes of lp balls for different values of p 2 1.
Thm. 2 holds for any cost function under which the maximum Euclidean distance any user can strategically move bounded by a constant. This holds not only for lp norms, but also for most reasonable cost functions.
Thm. 3 is already stated for general lp norms.
Thm. 4 is stated for L,, f2, and f However, a more general result can be stated with dependence on the VC dimension of the cost function balls (i.e., the set C {c(x, I Vr E P.) The bound would then be O(d k klo(()) VC(C)) ), and would support any plug-in in results for VC(C).
Prop. 5 and Prop. 6 also remain under minor tweaks to the constructions that take into account the differences in shapes of f, balls for different values of p 2 1.
. Obs. 3, 4, 5, and Cor. 2 hold for fp norms in general as well, since they are not shape dependent, but rather results of movement within a ball.
Thus, our claims regarding the fact that non-learnable classes can become learnable, the loss of universality, and the limits approximation all hold more generally.
In terms of asymmetric norms such as the Mahalanobis norm, while these norms would complicate the curvature analysis (and subsequent impossibility results that build off them), all results in Sec. 5 would still hold. This is because while the shape of balls changes (like with other Ep balls), fundamental properties like lines mapping to other lines do not. As such, the results in Sec. 5 would still hold for the exact same reasons as delineated above for Ep balls.
As for ceature-dependent (also known as "instance-wise") costs, these are qualitatively different from the conventional global costs, a way that can make the claims become irrelevant or even degenerate. For example, Sundaram et al. [33] show that on the one hand, even for linear H, instance-wise cost function can cause VC(Ha) = xc, and on the other hand, for separable costs (which are instance-wise) it holds that VC(HA) < 2 for any H.
20

---

Decision Boundary
Effective Boundary
Figure 9: (Left): Partial expansion. (Right): Regions merging/splitting
C.2 Partial Expansion
As seen in Fig. 9 (Left), partial expansion may occur if part of the expansion artifact is discarded through indirect wipeout. In the figure, part of the artifact (gold) is within a of the upper positive region and therefore does not become part of the decision boundary.
C.3 Merging/Splitting Regions
As seen in Fig. 9 (Right), two positive regions can merge together when they are separated by narrow pass in h. If the narrow pass is part of larger negative region, the region will be split into two, which can potentially increase the complexity of the decision boundary (for example, in Fig. (Left)).
C.4 Types of Impossible Effective Classifiers
As stated in Sec. 4.4, we identify four "types" of classifiers g that cannot exist as effective classifiers. Formally, these classifiers are ones which include either:
1. A small continuous region of positively classified points C' where Eq E Rd such that E (g) Vr C.
2. A narrow continuous region C' where all points are classified as positive and are a-close to the decision boundary.
3. A smooth point the decision boundary which has signed curvature λ > 1/a (or x² > 1/a when 2).
4. A locally convex intersection of piecewise linear or hyperlinear segments.
Note that the first case is just special of the second case. Nonetheless, have separated them to emphasize that the impossible positive regions can either be fully or partially contained.
Cases 1 and 2: Small/Narrow Positive Regions
Let C be some point in small positive region in g. For be classified positive, there must be a point x' E B, (z) which is classified positively by and not reachable by any E (h)h) (see requirements and in Appendix B.4). However, any point x' (x) C is reachable by X (h) and any point æ' E B,, (z) n C is also reachable by (o( since it is closer to some E (h) than x. Therefore, there are no points x' (x(x) which are not reachable by any q E Xo()), so cannot be an effective classifier.
Case 3: Large positive curvature
will show that any y with directional curvature greater than 1/a anywhere on the decision boundary will fail Prop. 3. In other words, if the directional curvature at point is greater than 1/a, then the point x ar, will reachable by some point that is negatively classified by g. In order for the point + añ to be reachable by z but not any point negatively classified by g. the
21

---

Figure 10: Diagram for proof of case 4.
ball B, + ar.z) which is the set of points that can strategically move to x + añg must not intersect y and must also be strictly tangent to it at However, if the curvature point is greater than 1/a, then the maximum radius Tinse of a ball that is strictly tangent to x less than a, so g does not meet Prop. 3.
In R22 Lemma 1 proves that the radius rinec of the maximum inscribed circle at æ is no bigger than the radius T Doee 1 of the osculating circle at x. We therefore have that Tinse S Tose = < a. In higher dimensions (see Appendix A. there is no longer a single normal curvature. Instead, we define the set K" of curvatures in each plane p E P defined by the normal vector and some tangent vector at x. Note that Ba (2 + añz) is only strictly tangent to the decision boundary at if it's intersection with each p E P (a circle) is strictly tangent at x to the curve obtained by intersecting the decision boundary with the plane p. Since each of these cases are in R², each one will only hold if the curvature at in is no more than 1/a. Therefore, if x* sup(K) > 1/a for any on the decision boundary, then the maximum radius of a ball that is strictly tangent to æ is less than a, so does not meet Prop. 3.
Case 4: Piecewise Linear Segments
Lemma 4. The set of points that reachable by point but not point + 86 for unit vector T and 8 + 0 all satisfy 0- <
Proof (Lemma 4). Define an orthonormal basis 61, U2 with 01 v. For any point q such that J. q > 0, the vector connecting x and q can be written as a1 + 02 + agus while the vector connecting z + òū and g can be written as (a1 8)v; + 0202... + agtig. Since 0 << 8 < a1 (note that q > 0 so a1 > 0), q is closer to x + 8ō than æ. Therefore, any point that is reachable by æ and not by + 50 must satisfy U. F.r 0.
Proof (Case 4). As depicted in Fig. 10. let L1 and L2 be two Rdd hyperplane segments that intersect on the decision boundary of at the Rd hyperplane segment I, and let be some point on I. Let 0 < A < æ be the angle between L1 and L2 on the positive side. Let i be the unit vector in L₁ that runs through x and is orthogonal to I; Th be the unit vector in L2 that runs through x and is orthogonal
to I; and Tc = 6.+6 Note that for 5 + 0 the points x1 = + 80, and x22 = I + dō2 are on +
the decision boundary while the point 212 classified as negative. Additionally, if we define JA as the the result of i, being rotated 0 < < H-6 around / away from the positive region and üß as the result of Th being rotated around away from the positive region, then both AA= + òū and ZB
5üG is classified positive and 2e
80c is
+ ōūg classified negative.
Assume that there exists classifier h associated with the effective classifier g. Therefore, there exists point q that is reachable by æ but not by IA EB, se (which are classified as negative by g). By Lemma 4, any point q that is reachable under strategic movement by point but not Z IB. ze must at least satisfy 9 UA < O, q UB < 0, and q 0c S 0. However, because JA + Up and therefore the opposite direction of To: - we must have that y vec 0 and q (TΛ + Ün) = O, which implies that both q q = 0 and g ēn = 0. However, this implies that the vector q is orthogonal to both A and ÜB which can only happen if g lies I or if the angle between T and Üp is either 0 or In the former case, q is then reachable
points in the same direction as 0 + 02
22

---

Figure 11: Example of VC decreasing from 2 to 1. Each color represents different classifier (drawn together to illustrate shattering capacity), and the dashed curves represent the corresponding effective classifiers. Though the black points can be shattered by H, none of the ha overlap so VC(Ha) = 1.
by the negatively classified point that is just over the decision boundary from it. The latter case is also not an option because the angle between AA and üB is 0AB = 0 + 26, and we have ensured that < + 2e < + _ л. In either case, it is impossible for to classify x as positive while classifying FA, Tp. and Te as negative, so there is no h such that g hA.
C.5 Non-bijectiveness of Classifier Mapping
In Sec. 4.4, we show that the mapping ++ ha is not surjective by showing that there are many potential ha with associated h. Here, will show that h - hS is also not injective since many classifiers map to the same effective classifier. Furthermore, we show that there are actually infinite that map nearly all possible ha- Though there many more interesting examples, the simplest case of non-injectiveness can be seen by considering an that includes a continuous positive region C' with an infinite number of points. Define the classifier h the classifier that is identical to h except that Λ classifies x E C as negative instead of positive. Because the point will achieve positive classification through strategic movement, h is unaffected by and is the same as ha- Moreover, 4% ha is true of any x E C, so as long as any that maps to l contains a positive region with infinite points, then h will have infinite that all map map to positive radius-a balls in h.s any ha with positive region C such that Ex (z(z) c C will have infinite that all map it. Note that since all positive regions in la have minimum size requirement Zx (x) C C, the aforementioned requirement covers all but the ha with absolute minimum- size positive regions.
Because positive points in
C.6 Classes with H = HA
Though H * HA for most classes H. there are a few rather simple H other than the class of linear functions where H H.. For example, under any lp norm cost, an f, ball with a positive inside will grow by radius of while an lp ball with negative inside will shrink by radius of a (at least until the radius hits 0). Therefore, many model classes of the subsets of the lp balls - including the class of all negative-inside balls and the class of balls with a radius that is multiple of all have H HA for any fixed a.
Additionally, since each line segment and fp arc maps to another line segment or lp arc, many piecewise-linear or piecewise fp are classes will also have H = HA. For example, any concave linear intersection will be mapped to shifted concave linear intersection, so the class of concave linear intersections satisfies H HA.
C.7
Classes with VC(H) > VC(HA) >
There are couple of mechanisms that can lead to a decrease in VC dimension. In the first mechanism, multiple different à have the same hi leading to smaller and less expressive HA. Two such cases shown in Appendix B.8 to prove that the VC may decrease even from co to 0. In similar fashion,
23

---

we can build an H where only some (instead of all) of the h E H have the same has which would decrease the VC dimension to non-zero effective VC dimension.
In the second mechanism, the VC can change due to effective classifiers gaining or losing overlap from strategic movement. As the dual Fig. 4 (Left) where the VC increases from I to 2 due this mechanism, Fig. 11 presents an example where the VC decreases from 2 to 1. Here, H includes four overlapping classifiers with VC(I)) 2. Yet, under strategic behavior, the effective classifiers cease to overlap, decreasing the shattering capacity to I.
C.8
Example of HA with VC(Ha) - (dd- (VC(H))
Claim: There exists class H with VC(Ha) = (VC(H))
Proof. For simplification of notation, we build on the case shown in Fig. 4 (Left) using classifiers that classify some ball as positive and all other points as negative. Note that a similar proof can be built based construction since classifiers that classify only a single point as positive are quite unrealistic. Let set S= -2 - {00) + {-8d} be the set of 23 lattice points with the point {0o) replaced by the point }- Consider the case where balls around the points in S. Because the radius of positive balls expand by a under strategic movement, we get that HA {2)
class H of point classifiers [7], but have decided to include the following
0.75 and H = { (Bu.2 (z) x S} is the class of radius-O.22
S}. Note that because none of the balls in H overlap, VC(H) = 1. On the other hand, the balls in HA do overlap, allowing HA to shatter the set d one-hot points F- = {e; i E [1...d]], where e; denotes the point with 1 in the ith coordinate and 0's elsewhere. Note that for each E S--(-4 (-8"), J. the ball Bi (x) E HA classifies E according to the sign pattern œ. Additionally, the ball (- does not classify any point in E as positive, so HA covers all 2d sign patterns of E. As such, VC(Ha) 2 d. However, since HA C. B = (z) : E Rd). we get that VC(H^) S VC(B) + 1 [15] giving VC(Ha) = O(d (VC(H)).
C.9 Example of Strategic Accuracy Exceeding Standard Accuracy
Claim: In the unrealizable setting, the maximum strategic accuracy can exceed the maximum standard accuracy.
Proof. In the unrealizable setting. the maximum strategic accuracy exceed the maximum standard accuracy when strategic movement helps correct the incorrect classification of positive points. For example, consider basic setup where a X {(-1,0) 0). (2, 0), (-3, (-3,0)) Y = (1, 1, and H = ( (x) = sign (#1 + x2), h2(2)) = sign(x1 I2 - 1)}- In the standard case, both hn and ha correctly classify the second and third points, but not the first point, so the maximum accuracy is 2 However, in the strategic setting, the first point is able to obtain a positive classification under /i
by moving to 1. 2) (and the third point still cannot get positive prediction), so the maximum strategic accuracy is 1.
C.10 Practical Takeaways
Given the challenge of optimization in strategic batch learning (even in simpler settings), our paper aims to first establish an understanding of the challenges inherent to non-linear strategic learning (in particular in relation to the linear case), with the hope that our results and conclusions can help guide the future design of learning algorithms, as well as set expectations for what is achievable and what is not. The difficulty of designing principled algorithm for the general non-lincar case is underscored by the fact that existing works rely on strong assumptions to enable optimization. For example, the original paper of Hardt et al. [16] provides algorithm, but requires assumptions on the cost function that reduce the problem to a one- mee-dimeniionll learning task, and their algorithm is essentially line search. Levanon and Rosenfeld [25] differentiate through A, but this relies strongly on this operation being a linear projection, which applies only to linear classifiers. Neither of the above naturally extend to the non-linear case.
Towards the goal of practical learning in the general strategic setting, we provide here some examples of how our results can be used as practical takeaways for effective learning:
24

---

1. Learning via inversion: One implication of our function-level analysis is that for any classifier h with strategic accuracy aCCstrar (h), the classifier h' such that h + ha h' has regular (i.e., non-strategic) accuracy ace(h') = acCstrat (h). Thus, one approach to optimizing strategic accuracy is via reduction: (i) train h'' E H' to maximize non-strategic accuracy using any conventional approach for some choice of H', and then (ii) apply the inverse function mapping (which may not be 1-to-1) 1) to obtain a non-strategic classifier h, whose effective decision boundary is that of h'. This approach requires the ability to solve the 'inverse' problem (which may not be I-to- 1) to find the effective classifier. We discuss cases where this would and wouldn's 't work in Sec. 4.4.
2. Regularizing curvature: A sufficient condition for a pre-image strategic h to exist for a given con-strategic h is that the function mapping is 1-to-1. Rather than restrict learning to only invertible classes H' a priori, an alternative approach is to work with general H' but regularize against those h' E H' that do not have an inverse. Prop. 1 implies that one way to promote this is by encouraging ht' that are smooth, since low-curvature classifiers are less prone to direct wipeout, and therefore more likely to permit inversion.
3. Finding the interpolation threshold:
The interpolation threshold - the point in which the number of model parameters (or model complexity more generally) attains minimal training error- is key for learning in practice: marks the extreme point of overfitting (in the classic underparametrized regime) and the beginning of benign overfitting (in the modern overparametrized regime, e.g., of deep neural nets). In non-strategic learning, this point is easily identified as that where the training error is zero. In contrast, our results show that in strategic learning, the minimal training error be strictly positive. This makes it unclear when (and if) the threshold has been reached. Fortunately, our procedure for our approximation experiment in Sec. 6.2 can be used generally to compute the minimal attainable strategic training error, independently of the chosen model class. This provides a tool that can be used in practice to measure interpolation.
In terms of model class selection, our results Sec. offer insight into potential upsides and downsides to certain classes. One implication of our results is that strategic behavior can generally either increase or decrease the complexity of the chosen model class. However, Thm. 2 ensures that the VC dimension can only increase for any class that is closed to input scaling, which includes many common classes used in practice. Thus, a learner who chooses such classes is guaranteed that the potential expressivity of the learned classifier will not be deteriorated by strategic behavior. Additionally, Prop. 4, Thm. 4, and Thm. all give upper bounds on the SVC of particular classes (e.g., ReLU neural networks). The implication is that a learner choosing to work with such H is guaranteed that if H is learnable, then the induced HA is also learnable. Finally, Obs. 5 and Thm. 1 both point the fact that several non-strategic classifiers h can be mapped the exact same effective classifier h If class H includes many such cases, then it has significant redundancy, which can have negative implications on the process of choosing a good h E H via learning (e.g.. in terms of generalization. optimization, or the effectiveness of proxy losses). Ideally, the learner should be cautious of classes in which this is prevalent, for example, classes that permit high curvature or small negative areas.
D Experimental details
D.I Experiment #1: Expressivity
In Sec. 6.1, we experimentally demonstrate how the strategic setting affects classifier expressivity. In this experiment, we first randomly sample a degree-k polynomial h, then determine the set of points S that make up the decision boundary of ha (i.e., are directly adjacent to it). and finally find the best approximate polynomial fit of S 8 Because user features are often naturally bounded, we assume that x E X = R² and that all are bounded by |ar S 100 (see Appendix A.2 for a discussion on how our theoretical results hold under bounded input domains). We report average values and
'ecaase we are concerned specifically with the polynomial of ha we label the points in fine grid both regularly and then strategically, and use the strategic labels to get polynomial fit. In this way, we do not directly compute the effective classifier (which would be difficult). but approximate it well enough to get the polynomial fit as well visualize it.
25

---

standard error confidence intervals of 100 instances of the setup for each a E {2, 4, 8, 16, 24, 40, and & E [1, 10). The instances were divided among 100 CPUs to speed up computation.
To randomly sample polynomials of degree k; we leverage the fact that the number of points needed to uniquely determine a degree-k polynomial over R2 is (== Therefore, for each instance, we randomly choose (*+²)) points and labels, and use SVM polynomial fitter to find the best fitting degree-k polynomial fit to these points. To ensure that the generated polynomial is indeed a full- degree polynomial, we construct grid G' of points over [-100, 100]², label each point g E G using h to get labels Y. and verify that the SVM best-fitting degree-k polynomial achieves near-perfect accuracy on (G, Y), while the best (A 1)-degree polynomial achieves low accuracy on (G, Y).
To find the set of points S that make up the decision boundary of has we first strategically label each g E G by checking if 9 can reach any point g' that is classified as positive by h. To determine the points that make up the decision boundary of ha, we select only the points g E G where g and at least one of its direct neighbors are labeled differently by hA-
Finally, we again use an SVM polynomial fit to determine the best approximate polynomial degree of has Because the ha of polynomial is not necessarily polynomial itself, we set k' to be the lowest degree of the polynomial whose fit on S passes a set tolerance threshold. Empirical tests showed that a tolerance of 0.9 was high enough to ensure good fit all of G. but not so high that the SVM fit algorithm needlessly increased the degree just to get a complete overfit to S.
D.2 Experiment #2: Approximation
In Sec. 6.2, we experimentally demonstrate the effects of non-universality on the maximum strategic accuracy. This experiment consists of (i) sampling synthetic data and (ii) calculating the maximum linear accuracy and strategic accuracy on each dataset instance. We report average values and standard error confidence intervals of 20 instances of the setup for each a E (0.5, 1, 2} and μ E [o. 5]. The instances were divided among 100 CPUs to speed up computation.
For each instance, we generate synthetic R² data by sampling points from class-conditional Gaussians I ~ (BJ,, 1). where μ is the separation between the centers of each class. Because we were unable to find a polynomial were drawn from each class (denote the full dataset X¹). Though this setup may not reflect all possible data distributions, it does represent how the strategic environment behaves under increasing data separability.
algorithm to calculate the maximum accuracy of H exactly 25 points
To calculate the maximum linear accuracy in each instance, we first note that there exists optimal linear classifier that runs through (or infinitesimally close to for negative points) exactly two dataset points. This is because for any optimal classifier h that runs through exactly one dataset point x X, h may be rotated until it runs through another x' E X' without changing any of the labels. For any optimal classifier h that runs through x E X, h can be shifted until it runs through one (or two collinear) x E X and then rotated appropriately. Because all data points are random, we assume that no three points are collinear. Therefore, the maximum lincar accuracy on X' can be calculated by taking the maximum accuracy over the (?) classifiers that run through each pair of x, x' E Xx" 9.
When calculating the maximum strategic accuracy, we note that the minimum size of positive region in ha is the ball Ba, so any strategic classifier can be represented by the intersection of multiple B., We therefore calculate the set S of all possible subsets X' that any B, classifies as positive, and find the intersection sses'gs 8 with the highest accuracy. To find all s E S, we iterate through the circles centered at each point on a fine-grained grid over the range of the datasct (padded by a on all sides) and check which points E X each circle includes. To find the best intersection of these circles, we iterate through each of the subsets of Z C Xo 10 and then s E S to find the maximum number of positive points that can be classified as positive if we allow ourselves mistakenly classify the negative points in Z.
Because points on the decision boundary are labeled as positive, we manually define that negative points used define the linear classifier are accurately labeled to reflect the fact that the optimal classifier does not through the point, but infinitely close to it. "ubsets are traversed in size order with early stopping once the size of the subset is large enough that the accuracy will be worse than the current best accuracy, even if all positive points are correctly classified.
26

---

1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the
paper's contributions and scope?
Answer: [Yes]
Justification: All claims in the abstract and introduction based on the results in the main body of the paper and put into perspective based on the most recent results in the field.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Results that are based on strong assumptions are clearly noted and extensions to more general cases are discussed.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
27

---

All assumptions and proof' are clearly set forth in either the main body of the paper or referenced supplemental material.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All information needed to reproduce the experiments are clearly stated the corresponding appendix sections of each experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
28

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The full set code used to run the experiments attached in the supplemental works.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ httppsscccppbccccceeeeceeecc gww.//ui/s/////eu CoodeSubmis ssi aasionPolicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All hyperparameter details are included in the appropriate appendix sections discussing the experimental setup.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Standard error confidence intervals reported all figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
29

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computer resources are delineated along with experimental setups.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that NeurlPS Code of Ethics https://neuuips: wttpippp.pcpppbbpep htw.olii/Ethiiscudeeeliiiie
didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer:
[Yes]
Justification:
The research was conducted using ethical practices in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is fully theoretical and as such does not pose any positive or negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
30

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: No real data or models were used this work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No outside assets were used in this paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi twwode..coo..... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
31

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
32

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: Core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https //tprr//eeu../eeeee Ceeeurips.cc/ooofeeeeee /LLM) for what should or should be described.
33


Reviews:
[{"review_id": "aIrfyoVLru", "reviewer": "Reviewer_YJeu", "summary": "They study Strategic Classification (SC) in a non-linear setting. Unlike SC in a linear setting, when the decision boundary is non-linear, datapoints move in different directions, and hence the effective decision boundary would get distorted. Their results are in 3 different categories: 1)points, 2)classifiers 3)model classes in a non-linear setting. \n\nSection 4 describes what would happen to points, how a point on h gets mapped to corresponding points in the effective decision boundary h_{\\delta}, cases 1-4 describe 4 possibilities in this case, there might be a 1-1 mapping, wipeout, expansion, or collission.\n\nSection 5 demonstrates what would happen to individual classifiers, in terms of their curvature and containment (number of positive regions in some sense).\n\nSection 6 explains what would happen to the VC dimension of the model classes; they might increase or decrease.", "questions": "Eq 1, shouldn't it be h(x')?\n\nLines 114 - 117, confusing since you are using x as a modified point in line 114 and then as an original point in line 117.\n\n\nFigure 2 needs more explanation. I do not understand what all the colors represent. It seems like you are addressing 4 categories, but there\nare 5 figures. It is very hard to understand what is going on.\n\nObs3 for what points x? The ones on the decision boundary?\n\nConfused about the wording of section 6.1. Do you mean that in some cases, the  VC-dimension of the effective classifier sometimes decreases, and sometimes it increases?\n\n\nWhat does line 292 mean?  For what point x?\n\nIn your experiments, how do you compute the effective decision boundary?", "limitations": "Although it is very important to study SC in non-linear setting, my biggest complain about this work is that it is mostly structural results, it does not give any algorithms for learning in non-linear settings.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Although it is very important to study SC in non-linear setting, my biggest complain about this work is that it is mostly structural results, it does not give any algorithms for learning in non-linear settings.", "was_revised": true, "final_justification": "I agree that learning in a non-linear setting is quite challenging; however, after going through other responses, I decided to keep my score.", "rebuttal": "Thank you for your careful review and detailed comments. Please see our response below. \n\n**\"[The work] does not give any algorithms for learning in non-linear settings.”**  \nWe certainly agree that this would give added value, but note that optimization in strategic batch learning is quite challenging even in simpler settings, and so the design of a principled algorithm for the general non-linear case is a difficult ask. Existing works rely on strong assumptions to enable optimization. For example, the original paper of Hardt et al. [2016] provides an algorithm, but requires assumptions on the cost function which reduce the problem to a uni-dimensional learning task, and their algorithm is essentially a line search. Levanon and Rosenfeld [2021] differentiate through $\\Delta$, but this relies strongly on this operation being a linear projection – which applies only to linear classifiers. Neither of the above naturally extend to the non-linear case. Levanon and Rosenfeld [2022] propose the generalized strategic hinge, which does apply to non-linear classifiers, but requires solving a generally intractable nested argmin objective (which can be even harder than solving the original nested argmax objective). \n\nGiven this difficulty, our paper aims to first establish an understanding of the challenges inherent to non-linear strategic learning, and in particular in relation to the linear case. We hope our results and conclusions can help guide the future design of learning algorithms, as well as set expectations for what can be achievable, and what cannot.\n\nTowards this, and motivated by your review, **we provide here some examples of how our results can be used as practical take-aways for effective learning**, which we will add to the paper as a new section and with further discussion using the extra page:\n\n1. **Learning via inversion**: One implication of our function-level analysis is that for any classifier $h$ with strategic accuracy $s-acc(h)$, any effective classifier $h’$ s.t. $h \\mapsto h_\\Delta=h’$ has regular (i.e., non-strategic) accuracy $acc(h’) = s-acc(h)$. Thus, one approach to optimizing strategic accuracy is via reduction: (i) train $h’ \\in H’$ to maximize *non-strategic* accuracy using any conventional approach for some choice of $H’$, and then (ii) apply the *inverse* function mapping (which may not be 1-to-1) to obtain a non-strategic classifier $h$, whose effective decision boundary is that of $h’$. This approach requires the ability to solve the “inverse” problem (which may not be 1-to-1) to find the effective classifier. We discuss cases where this would and wouldn’t work in Sec. 5.3.\n\n2. **Regularizing curvature**: A sufficient condition for a pre-image strategic $h’$ to exist for a given non-strategic $h$ is that the function mapping is 1-to-1. Rather than restrict learning to only invertible classes $H’$ a-priori, an alternative approach is to work with general $H’$ but regularize against those $h’ \\in H’$ which do not have an inverse. Prop. 1 implies that one way to promote this is by promoting the smoothness of $h’$, since low-curvature classifiers are less prone to direct wipe-out, and therefore more likely to permit inversion.\n\n3. **Finding the interpolation threshold**: The interpolation threshold – the point in which the number of model parameters (or model complexity more generally) attains minimal training error – is key for learning in practice: it marks the extremal point of overfitting (in the classic underparametrized regime) and the beginning of benign overfitting (in the modern overparametrized regime, e.g., of deep neural nets). In non-strategic learning, this point is easily identified as that in which the training error is zero. In contrast, our results show that in strategic learning, the minimal training error can be strictly positive. This makes it unclear when (and if) the threshold has been reached. Fortunately, our procedure for our approximation experiment in Sec. 7.2 can be used generally to compute the minimal attainable strategic training error, independently of the chosen model class. This provides a tool that can be used in practice to measure interpolation.\n\nPlease also see our response to Rev. qnCe regarding practical implications of our results in Sec. 6, which we also plan to incorporate into the new section on take-aways. We believe that these additions will strengthen our paper – thank you for this suggestion!\n\n\n\n**Minors:** \n\n> Eq 1, shouldn't it be h(x')?  \n\nYes, that is correct. We found this mistake a few days after the deadline and have since corrected it.\n\n>Lines 114 - 117, confusing since you are using x as a modified point in line 114 and then as an original point in line 117.  \n\nOur intention was to use x in line 114 to represent the points on the original decision boundary, but we see where this might create confusion so we will update the notation.\n\n\n> Figure 2 needs more explanation.  \n\nApologies for the confusion. There are indeed four categories, but the wipeout category has two “sub-types”, giving a total of five cases. From left to right we present: one-to-one (case #1), direct wipeout (case #2a), indirect wipeout (case #2b), expansion (case #3), and collision (case #4). We will edit the caption to clarify this. In terms of colors, the original classifiers ($h$) are drawn in black and the effective classifiers ($h_\\Delta$) are dashed and grey. We signify the positive and negative regions of the original classifier with blue and red respectively.\n\n> Obs3 for what points x? The ones on the decision boundary?  \n\nNo, this is talking about entire contained regions of points including those not on the decision boundary. Any negative region C in h that is fully contained in some $\\alpha$-ball centered at some x will become positive in $h_\\Delta$.\n\n> Confused about the wording of section 6.1. Do you mean that in some cases, the VC-dimension of the effective classifier sometimes decreases, and sometimes it increases?  \n\nYes, the VC dimension may increase or decrease.\n\n>What does line 292 mean? For what point x?   \n\nThe intention is for any arbitrary x. The classifier is one that classifies some radius 0.9α ball centered at some x as positive and is negative elsewhere.\n\n\n>In your experiments, how do you compute the effective decision boundary?  \n\nThe effective decision boundary was only computed in the first experiment. Because we are concerned specifically with the polynomial fit of $h_\\Delta$, we label the points in a fine grid G over $[-100, 100]^2$ both regularly and then strategically and use the strategic labels to get a polynomial fit. In this way we don’t directly compute the effective classifier (which would be difficult), but approximate it well enough to get the polynomial fit as well as visualize it."}, {"review_id": "l4Hwdrv0vt", "reviewer": "Reviewer_4VxQ", "summary": "This paper investigates strategic classification under non-linear models, extending prior work that largely focuses on linear classifiers. In strategic settings, users manipulate their input features to receive favorable outcomes, which fundamentally alters the learning problem. The authors make a bottom-up analytical and empirical approach to study how non-linear decision boundaries, classifier expressivity, and model class complexity behave in strategic environments. An interesting insight is that universal approximators like neural networks lose their universality when faced with strategic agents. The authors support their analysis with theoretical characterizations.", "questions": "1. Could the non-universality of neural networks under strategic manipulation be quantified more rigorously?\n\n2. How sensitive are your findings to the assumption of optimal best-response from agents? Would bounded rationality change the picture?", "limitations": "See weakness", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. Strategic classification is relevant in high-stakes applications, and extending its understanding beyond linear classifiers is both novel and necessary.\n\n2. The insight that universal approximators are no longer universal under strategic manipulation is intellectually significant and well-motivated.\n\n3. The paper rigorously analyzes the effects of strategic behavior at three levels: individual inputs, decision boundaries, and model classes.\n\n4. The exposition is clear and logical. Definitions, examples, and motivations are carefully laid out.\n\n**Weaknesses**\n\n\n1. The analysis focuses primarily on $l_2$ cost; broader conclusions might require considering other realistic cost structures (e.g., non-Euclidean, asymmetric, feature-dependent).\n\n2. While the claim that neural networks are no longer universal is well-motivated and empirically observed, a more formal characterization  would strengthen the main claim.\n\n3. The paper focuses on theoretical behavior but gives limited discussion on how this insight could influence real-world tasks in strategic settings.", "was_revised": true, "final_justification": "The rebuttal addresses my concerns. I recommend the acceptance.", "rebuttal": "Thank you for your positive review and useful comments, we appreciate the effort and time spent in providing us with helpful feedback. Please see our detailed response and answers to your questions below.\n\n**”The analysis focuses primarily on L2 cost; broader conclusions might require considering other realistic cost structures (e.g., non-Euclidean, asymmetric, feature-dependent).”**  \n\nIndeed, our low-level analysis begins with focus on the L2-norm cost, both because it is the most popular choice in the literature, and because we found it to offer the best intuition. Nonetheless, **most of our results hold more broadly**, and in particular, all theorems and propositions in Sec. 6 generalize to any $ L_p $ norm:\n\n1. Prop. 4 applies generally, since negative-inside polytopes are still mapped to smaller negative-inside polytopes under general $L_p$ cost functions.\n2. Thm. 1, Cor. 1, and the example in Figure 4 of increasing VC dimension remain under minor tweaks to the constructions that take into account the differences in shapes  of $L_p$ balls for different values of $p \\ge 1$.\n3. Thm. 2 holds for any cost function under which the maximum distance any user can strategically move is bounded by a constant. This holds not only for $L_p$ norms but also for most reasonable cost functions.\n4. Thm. 3 is stated for $L_1, L_2$, and $L_\\infty$. However, a more general result can be stated with dependence on the VC dimension of the cost function artifacts (i.e. the set C = { $c(x,x’) \\leq \\alpha \\\\ \\\\ \\forall x \\in R^d $ }  ). The bound would then be $O(kd^2 \\\\ logk + VC(C))$, and would support any plug-in results for $VC(C)$.\n5. Prop. 5, and Prop. 6 also  remain under minor tweaks to the constructions that take into account the differences in shapes  of $L_p$ balls for different values of $p \\ge 1$.\n6. Obs. 3-5, Cor. 2, hold for $L_p$ norms in general as well since they are not shape dependent, but rather results of movement within a ball.\n\nThus, our claims regarding the fact that non-learnable classes can become learnable, the loss of universality, and the limits to approximation all hold more generally.\n\nIn terms of asymmetric norms such as the Mahalanobis norm, while these norms would complicate the curvature analysis (and subsequent impossibility results that build off them), all results in Sec. 6 would still hold. This is because while the shape of balls changes (like with other $L_p$ balls), fundamental properties like lines mapping to other lines do not. As such, the results in Sec. 6 would still hold for the exact same reasons as delineated above for $L_p$ balls.\n\nAs for feature-dependent (also known as “instance-wise”) costs, these are qualitatively different from the conventional global costs, in a way which can make the claims become irrelevant or even degenerate. For example, Sundaram et al. [2021] show that on the one hand, even for linear $H$, instance-wise cost function can cause $VC(H_\\Delta) = \\infty$, and on the other hand, for separable costs (which are instance-wise) it holds that $VC(H_\\Delta) \\le 2$ for *any* $H$.\n\n\n**”While the claim that neural networks are no longer universal is well-motivated and empirically observed, a more formal characterization would strengthen the main claim.”**  \nThank you for this suggestion. Our notion of non-universality states that there exists a classifier $h$ for which no effective class $H_\\Delta$ can include $h$ as a member. We will gladly add this to the paper.\n\n**”Could the non-universality of neural networks under strategic manipulation be quantified more rigorously?”**  \nThis is an interesting idea. While we chose to work with a rigid definition, it is also possible to define (non)-universality in a more quantifiable manner based on approximation, as is common in the expressivity literature. However, and to the best of our knowledge, this literature focuses predominantly on regression, and approximation is defined with respect to the actual values of the functions considered (typically w.r.t. the infinity norm). Such definitions therefore do not carry over to classification where values are binary, and we are unaware of any standard notion of universality for decision boundaries. One suggestion for an adaptation of the existing definition to the classification setting is the following:\n\nLet $X$ be some input domain, and let $\\Omega =$ {$g : X \\to R$ } be a collection of scalar functions on $X$. Define $h_g(x)=sign(g(x))$. Let $F=${$f : X \\to R$} be a class of scalar functions, and define the corresponding hypothesis class as $H=H_F=${$h_f:f \\in F$}. Then $H$ is a universal approximator w.r.t. $\\Omega$ if the following holds:  \n\n$\\forall g \\in \\Omega \\\\ \\\\ \\forall \\epsilon>0 \\\\ \\\\ \\exists f \\in F$ s.t. $h_f(x)=h_g(x) \\\\ \\\\ \\forall x \\in X$ with $|g(x)|>\\epsilon$.\n\n\nIntuitively, this states that $H$ is universal if for every ground truth $h^* = h_g$ there is some $h=h_f \\in H$ that agrees with $h^* $ on all inputs $x$, except possibly on those that are $\\epsilon$ - close to the decision boundary of $h^*$, for arbitrarily small $\\epsilon$.\n\n\n**“The paper focuses on theoretical behavior but gives limited discussion on how this insight could influence real-world tasks in strategic settings.”**  \nThank you for pointing this out. Given this and similar comments by other reviewers, **we will add a section on practical take-aways from our results in the next revision using the extra page.** This section will include:\n* General guidelines for a potential inversion-based learning approach, with benefits and challenges\n* An idea for regularizing based on curvature\n* A method for computing the interpolation threshold, which in a strategic setting can occur at strictly positive training error\n* Insights on how to choose model classes, and which classes are best avoided\n* Observations on how to set expectations regarding sample size, possible expressivity, and attainable strategic accuracy\nFor a more detailed description of these points please see our responses to Rev. YJeu and Rev. qnCe.\n\n\n**“How sensitive are your findings to the assumption of optimal best-response from agents? Would bounded rationality change the picture?.”**  \nThis is an interesting question. The answer likely depends on how rationality is broken. For example, if users are simply loss averse, then the shape of the cost is retained, and all results should still apply. We believe this would hold also for users that operate under partial information; for example, if they are Bayesian, then as long as the prior is smooth, the posterior should also be smooth, and outcomes will be similar. If however users are computationally bounded (i.e., cannot solve the argmax in $\\Delta$ exactly), then this can be more difficult to model because it requires understanding how their approximation of $\\Delta_h(x)$ alters the shape of the cost function artifact. Some cases might be tractable, for example if users move according to the gradient of an underlying score function $f(x)$ (where $h(x)=sign(f(x))$) or if they move w.r.t. a local linear approximation of the decision boundary of $h$. Other less-structured cases however are likely to be much more challenging to work with."}, {"review_id": "CUL3cCRXTL", "reviewer": "Reviewer_UkjG", "summary": "This paper studies strategic classification, where agents can intentionally modify their input features (while incurring an L-2 cost) to receive favorable outcomes from a classifier (e.g. in credit approval). This paper explores the implications of non-linear classifiers in such a setting.\n\nThanks to the assumption that the L-2 cost is the same for all agents, Sec 4, 5 and 6.2 effectively reduces the problem to study the behavior of offset curves/surfaces in the context of classification.\n\nSec 6.1 studies the behavior of offset curves in the language of VC dimension.\n\nEdit: Author's response to reviewer YJeu has made me feel more positive about the paper. I'm raising my score to a 3.", "questions": "See weaknesses", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Pros:\n\nThe paper is extremely well-written, with intuitions and/or illustrations provided for almost every proposition and proof. The analysis is well-structured and engaging.\n\nCons:\n\nThe paper makes connection to the study of offset curves, yet largely dismiss it as it \"does not convey direct implications for learning\". However, I feel that the paper could have used more direct connection to and terminology from offset curves, e.g. self-intersections, tangent vectors, instead of reinventing terminology. It is a connection that should be highlighted and celebrated.\n\nEvery claim that is made up to (and include) Theorem 1 is somewhat immediate once the reader understand the basic mechanism of offset curves.", "was_revised": true, "final_justification": "Author's response to reviewer YJeu has made me feel more positive about the paper. I'm raising my score to a 4. Overall I still feel negative about the paper, as there is a lack of technical insight besides those derived from offset curves. The claimed application to the practical learning is questionable as well. I am unsure how they can be implemented.", "rebuttal": "Thank you for your constructive review, we appreciate your expertise and point of view. We would however like to take the opportunity and present a broader perspective for why we believe our paper can be of interest to the community. The contribution of our paper lies not in any particular result or technique, but in the overall story it tells of strategic learning in the non-linear setting. Our goal was to raise awareness to the non-trivial implications of non-linearity which, by focusing predominantly on the linear case, the community has so far mostly assumed away (surveying many papers on strategic classification and their reviews, it was rare to find a paper which was *not* scrutinized for the exclusive focus on linear classifiers). We do not feel that this aim necessitates complex claims but rather a strong foundational understanding of the setting, which we believe our paper delivers. By the request of other reviewers, we will add a section on practical implications and take-aways of our results, which should promote our original goal and therefore strengthen the paper (for a detailed description please see our responses to Rev. YJeu and Rev. qnCe). We therefore kindly ask that you be willing to reconsider our paper, and whether it makes a sufficient contribution to the strategic learning literature, under this perspective. \n\nWe now turn to address your particular concerns in detail.\n\n**”The paper makes connection to the study of offset curves, yet largely dismiss it as it \n‘does not convey direct implications for learning’”**  \nPlease note that our intent was not to *dismiss* the connection – we did not mean for this to be implied in our writing, and apologize if this was the case. Rather, our intent was to depict offset curves as a useful idea for reasoning about certain aspects of strategic learning that proved useful in the context of our work. While we agree that the connection might extend beyond what we have presented (and that this is an interesting avenue to pursue), our targeted focus was intentional and aimed to support our own goals. \n\nIn particular, and as Reviewer qnCe notes, our paper’s primary contribution is the class-level analysis in Sec. 6. To the best of our knowledge, such analysis lies outside the domain of offset curve theory, which concerns mostly point- and curve-level properties. We are unaware of results that connect curvature to the complexity of a function class or its VC dimension (nor do we believe that such connections are trivial). This is what we meant by “does not convey direct implications for learning”. Additionally, while our low-level analysis begins with focus on the L2-norm cost, both because it is the most popular choice in the literature, and because we found it to offer the best intuition, most of our results generalize beyond the L2 nor cost (please see our response to Rev. 4VxQ).\n\n\n**”I feel that the paper could have used more direct connection to and terminology from offset curves, e.g. self-intersections, tangent vectors, instead of reinventing terminology.”**  \nWhile our results make use of ideas from offset curves, we do not see why they require a more direct connection than presented; our bottom-up construction ensures that we make use of the minimal set of notions necessary for our purposes. However, if this turned out to appear as “reinventing terminology”, then this was entirely unintentional, and we would be happy to make the required corrections and adjustments. Please let us know if you have any specific requests or suggestions and we will gladly accommodate them in the next revision.\n\n**”Every claim that is made up to (and include) Theorem 1 is somewhat immediate once the reader understand the basic mechanism of offset curves.”**  \nSecs. 4 and 5 are intended to build intuition and a strong foundation towards Sec. 6. With the common reader in mind, we felt that a detailed exposition was imperative – even if this resulted in a somewhat easy read for the more familiar audience.  \nHowever, and while our earlier results are indeed observations (and are stated as such), we respectfully disagree that all results that follow are “immediate”. An observation or result that is simple (in hindsight) does not mean it cannot be useful to the community. In fact, we view it as a strength that our paper makes use of simple observations to derive a meaningful description of a complex learning task. Given that this showcases the potential for using offset curves for this purpose, we are unsure why you view this as a limitation.  \nThe contribution of our work lies not in any individual claim but in the story it tells of non-linear strategic learning as a whole: for example, that strategic learning cannot be universal, that class complexity can either increase or decrease, and that some points have no effect on learning outcomes. We believe such conclusions can be of interest to the strategic learning community, and of value towards future work."}, {"review_id": "QgO4nkxbkI", "reviewer": "Reviewer_qnCe", "summary": "This paper studies strategic classification in the offline geometric setting where the true underlying classifier is nonlinear. The authors take a \"bottom up\" approach that first considers changes to individual points on the boundary, then aggregate them to the effective classifier under manipulation and subsequently the effective model class. For individual points $x$, they discussed four cases of the mapping from $x$ to the set of points that manipulate to $x$ at maximum cost: one-to-one, wipeout, expansion and collision. For the effective classifiers, they identified two mechanisms that can limit their expressivity --- curvature and containment --- and derive some conditions about effective classifiers that cannot exist. The authors then move on to the model class level and compares the strategic VC dimension and the original one, and show that universal approximators may fail to capture the samples after manipulation.", "questions": "Could you comment on how the results in section 6 help the learner to choose model classes in practice?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe authors systematically study strategic classification with nonlinear classifiers in the continuous geometric setting where agents can move in a bounded radius ball. In contrast, existing work either studies non-linear classifiers in a discrete setting via manipulation graphs, or exclusively focus on linear classifiers in the geometric spaces. The paper is clearly written, nicely builds up intuition via a bottom-up approach, and comprehensively study the structure and complexity of this problem.\n\nWeaknesses:\n\n1. Limited technical depth. While the paper presents many results, most of them feel like simple observations that have been written down formally, rather than deep technical insights. Since the paper takes a bottom-up approach, the results about individual points and classifiers are mostly just listing observations and examples --- this does help build intuition but doesn't really tell us anything new. The most interesting part is the model class-level results in Section 6 (which I consider to be the meat of this paper) where they quantitatively study the complexity and expressivity of the effective model class versus the original ones. But this analysis is incomplete since they only make a conjecture about the VC gap in the general case, but did not provide a satisfactory answer. \n\n2. The authors study both VC dimension/sample complexity and universality of model classes, but these results feel mostly pessimistic and do not provide clear guidance on how to select model classes or design learning algorithms in practice. The experimental results in section 7.2 are also somewhat unsurprising: showing improved accuracy with bigger separation between positive and negative examples and smaller manipulation radius, with H^{lin} being a lower bound. Overall, the practical implications and takeaways from this paper is a bit unclear.", "was_revised": true, "final_justification": "The rebuttal has addressed my concerns about limited model class-level results by providing a new characterization for piecewise linear functions, and a detailed discussion of the practical implications for selecting hypothesis classes under strategic manipulations. Overall, I appreciate the contributions and decided to raise my score from 3 to 4.", "rebuttal": "Thank you for your thorough review, we appreciate your constructive feedback. Based on your review, we have added (i) a list of practical take-aways based on our analysis, to be added as a new section, and (ii) a new result that extends Thm. 3 to show our conjecture holds for classes of piece-wise linear functions (e.g., ReLU networks). We hope these and our answers to your questions help address your concerns.\n\n\n**”While the paper presents many results, most of them feel like simple observations that have been written down formally, rather than deep technical insights.”**  \nThe primary goal of Secs. 4 and 5 is to build intuition towards the class-level analysis in Sec. 6 (which, as you note, includes the core of our results). Nonetheless, we believe that our results in the these earlier sections, albeit simple, still hold value in their own right: the non-universality of strategic learning, the fact that some points have no influence on the learned classifier, the ability of strategic behavior to both promote and suppress complexity, and the mechanisms underlying these phenomena and structural claims are all fundamental to understanding the non-linear strategic setting.  \nOur goal in this work was to provide a compelling story of how non-linear strategic learning can be qualitatively different from the linear case. We are aware that in this sense our paper deviates from the structure of a conventional theory paper (where emphasis is typically on the depth of technical results). Nonetheless, we believe our results can still be of interest to the community and of value towards future research. We do not see why their simplicity takes away from their significance.  \nAt the same time, and after reading your review and others, we agree that showing how our results transfer to concrete implications for learning can help better establish the value of our results. **We will therefore add to the paper a new section on practical take-aways** in the next revision using the extra page. We detail such implications in regards to Sec. 6 in our response to your question below. Please also see our response to Rev. YJeu for detailed practical take-aways from other parts of the paper.\n\n**”The most interesting part is the model class-level results in Section 6… But this analysis is incomplete since they only make a conjecture about the VC gap in the general case.”**\nThe gap remains a conjecture not for lack of trying (we have thought long and hard about this), but because a generic result has proven to be quite elusive to prove (or disprove). A key reason is that in a strategic setting points will move differently when facing different $h$ from the same $H$. Thus, reasoning about the shattering of an arbitrary set must account for how points can move under *all possible* $h \\in H$, though not simultaneously – which proved to be highly challenging in the general, unstructured case. This is why we have included two results that exploit structure: the explicit upper bound on polytopes (Thm. 3), and a lower bound for any $H$ that is closed to scaling (Thm. 2), which includes many common classes used in practice.  \nWhile closure to scaling did not provide us sufficient structure for an upper bound, in response to your concern, **we add here a new result that extends Thm. 3 to show our conjecture holds for any class of piecewise-linear classifiers with a bounded number of segments** – a large and highly expressive set of classes, which includes neural networks with ReLU activations (of fixed size) as a special case, and is often used in studies on neural network approximation. The proof technique is similar to that of Thm. 3 where each linear segment maps to a new linear segment and each intersection can map to a partial to the cost function shape. Each classifier $h_\\Delta \\in H_\\Delta$ is therefore the intersection of a new piecewise linear classifier $g \\in H$ (with the same number of segments as the original $h$, but each segment is shifted away by $\\alpha$) and a finite (and bounded) number of $L_p$ balls. Note that H has finite VC because each $h \\in H$ is the union of $m$ linear classifiers (see Thm. 1.1  in Vaart and Wellner [2009] VC bound of unions) and $H_k^{Ball} $, the class of all classifiers that are the union of the union up to $k$ $L_p$ balls, does too as shown in the proof for Thm. 3. By lemma 3, this means that $H_\\Delta$ will also have finite VC so the learnability of $H$ implies the learnability of $H_\\Delta$.  \nIn light of your question, we will add a more detailed explanation of the difficulties of finding a general bound as well as our new result above to the final version of the paper. \n\n**״Could you comment on how the results in section 6 help the learner to choose model classes in practice?״**  \nCertainly, here are some examples: \n1. One implication of our results is that strategic behavior can generally either increase or decrease the complexity of the chosen model class. However, Thm. 2 ensures that VC can *only increase* for any class that is closed to input scaling, which includes many common classes used in practice. Thus, a learner that chooses such classes is guaranteed that the potential expressivity of the learned classifier will not be deteriorated by strategic behavior.\n2. Prop. 4, Thm.3, and our new result detailed above all give upper bounds on the SVC of particular classes (e.g., ReLU neural networks). The implication is that a learner choosing work with such H is guaranteed that if H is learnable, then the induced $H_\\Delta$ is also learnable. \n3. Obs. 5 and Thm. 1 both point to the fact that several non-strategic classifiers $h$ can be mapped to the exact same effective classifier $h_\\Delta$. If a class $H$ includes many such cases, then it has significant redundancy, which can have negative implications on the process of choosing a good $h \\in H$ via learning (e.g., in terms of generalization, optimization, or the effectiveness of proxy losses). Ideally the learner should be cautious of classes in which this is prevalent, for example classes that permit high curvature.\n\nAs noted, we will add these conclusions and others in a new section in the next revision.\n\n**”The experimental results in section 7.2 are also somewhat unsurprising: showing improved accuracy with bigger separation between positive and negative examples and smaller manipulation radius, with H^{lin} being a lower bound.”**\n\nThe idea of this experiment was not to show how the maximum strategic accuracy improves with class separation and smaller manipulation radius, but rather to show how this trend compares with the non-strategic and linear baselines. This experiment ultimately demonstrates two things: \n\n1. That the limited accuracy phenomenon detailed in Sec. 6.2 has a noticeable effect on practical cases and not just edge cases. This is evident by the noticeable deviation of $H_\\Delta^* $ from the upper baseline of $H^*$.\n2. That non-linearities in the strategic setting still greatly improve performance (which also serves as a justification for further study of non-linear classifiers in strategic classification). This is evident by the noticeable deviation of $H_\\Delta^* $ from the upper baseline of $H^{lin}$.\n\nAs such, the class separation and manipulation radius are varied not to point out an inferable trend, but rather to quantify both of the above conclusions."}]

Author rebuttal:

Meta-review: This paper investigates strategic classification in non-linear settings, extending prior work that has largely focused on linear models. In strategic classification, agents deliberately modify their input features, typically incurring an l2 cos to obtain favorable outcomes (e.g., in credit approval). Unlike the linear case, where all points shift in the same direction, non-linear decision boundaries induce heterogeneous movements of datapoints, leading to distortions in the effective boundary. The authors take a bottom-up analytical and empirical approach to examine the implications of non-linearity across three levels: individual points, classifiers, and model classes. A key insight is that universal approximators such as neural networks lose their universality when faced with strategically responding agents. Their findings are supported by theoretical characterizations and empirical analysis.

The reviewers agreed that this non-linear extension and the technical results are exciting. Though most of the presented results are structured results, I believe this result will motivate future studies and discussions on this important topic.
Decision: Accept (poster)