Strategic Classification With Externalities
Authors: Safwan Hossain
Evi Micha
Yiling Chen
Ariel D. Procaccia
Venue: ICLR 2025 Poster (2025)
Keywords: strategic classification
game theory
strategic machine learning
algorithmic game theory
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We study strategic classification when participating agents induce externality, from a theoretical perspective.

Abstract: We propose a new variant of the strategic classification problem: a principal reveals a classifier, and $n$ agents report their (possibly manipulated) features to be classified. Motivated by real-world applications, our model crucially allows the manipulation of one agent to affect another; that is, it explicitly captures inter-agent externalities. The principal-agent interactions are formally modeled as a Stackelberg game, with the resulting agent manipulation dynamics captured as a simultaneous game. We show that under certain assumptions, the pure Nash Equilibrium of this agent manipulation game is unique and can be efficiently computed. Leveraging this result, PAC learning guarantees are established for the learner: informally, we show that it is possible to learn classifiers that minimize loss on the distribution, even when a random number of agents are manipulating their way to a pure Nash Equilibrium. We also comment on the optimization of such classifiers through gradient-based approaches. This work sets the theoretical foundations for a more realistic analysis of classifiers that are robust against multiple strategic actors interacting in a common environment.

Published as a conference paper at ICLR 2025
STRATEGIC CLASSIFICATION WITH EXTERNALITIES
*Safwan Hossain', EEvi Michaa, Viling Chen', Ariel Procaccia'
Harvard University
2 University of Southern California
shossaingg harvard.edu, evi.micha@usc.cm edu
ABSTRACT
We propose a new variant of the strategic classification problem: a principal re- veals classifier, and n agents report their (possibly manipulated) features be classified. Motivated by real-worke applications, our model crucially allows the manipulation of one agent to affect another; that is, it explicitly captures inter- agent externalities. The principal-agent interactions are formally modeled as a Stackelberg game, with the resulting agent manipulation dynamics captured as a simultancous game. We show that under certain assumptions, the pure Nash Equi- librium this agent manipulation game is unique and can be efficiently computed. Leveraging this result, PAC learning guarantees formally, we show that is possible to learn classifiers that minimize loss on the distribution, even when random number of agents are manipulating their way a pure Nash Equilibrium. We also comment on the optimization of such classifiers through gradient-based approaches. This work sets the theoretical foundations for a more realistic analysis of classifiers that are robust against multiple strategic actors interacting a common environment.
established for the learner: in-
INTRODUCTION
Machine learning algorithms are increasingly deployed in high-stakes decision making, including loan applications, school admissions, hiring, and insurance claims (Bejarano Carbo, 2021; Harwell, 2022: Kumar et al., 2022). Relying on past data as a reference, these algorithms use features of candidate to determine their merit for the given task. The interactions in these settings, however, often involve strategic agents who may manipulate their features if doing so yields more favorable outcome. This presents significant challenge the algorithm if it is not trained to anticipate such behavior since the training and test distributions no longer match. Correspondingly, a large and growing literature strategic classification has emerged to understand the dynamics of this behavior and propose strategies for learning in such settings (Hardt et al., 2016).
By and large, the existing literature roughly models the interaction as follows: The learner (or principal) deploys a classifier, and an agent with feature x observes this and may choose to report manipulated feature x' to obtain better outcome. Manipulation is not considered free since it may involve some additional effort or risk. While the classifier may be deployed for any number of agents, agent interactions with the learner are crucially assumed be independent; in other words, one agent's action has no influence on another. We posit that this ignores critical aspect of multi- agent interactions in a shared environment: agents' actions exert externality on one another. This not a new observation: indeed, the notion that agents in system are affected by a common resource has been core component of economic models for over a century (Pigou, 1920; Coase, 1960). has not, however, been formally studied in the strategic classification setting despite its relevance and applicability.
Consider the example Hardt et al. (2016) used to initiate this literature: the number of books in the parent's houschold may be a valid feature for university admissions given its correlation with student success (Evans et al., 2010). Since "books are relatively cheap". this allows parents to game the system by buying "an attic full unread books" et al., 2016). It is immediate, however, that if all parents do this, then the price of books longer stays cheap. This is the externality induced
"Corresooningg Authors; Equal Contribution

---

Published as a conference paper at ICLR 2025
by everyone's actions. Externality, however, not only model demand for lucrative features but also the additional risk or burden associated with manipulation. When a university is deciding which students to accept from high school using a classification algorithm, applicants may report features such as class rank, GPA, volunteering affiliations, and so on. Naturally, only a handful of students can be the top of their class be affiliated with specific organization. If only a handful of students manipulate their features, it may not be statistically discernible. However, if many claim be at the top of their class or work with the same organization, this can stand out and lead the university to audit the applications further. Similarly, few applicants inflating their credit score on loan application may be treated as an anomaly; a large pool of applicants doing so becomes a systematic problem that demands a reexamination of the loan process, causing a burden on all.
The preceding examples illustrate that the demand for books, the risk faced by student, or the burden on the borrower is not solely determined by an individual's action but also influenced by the interactions of others within the same system. This naturally affects how, what, and if an agent manipulates. This phenomenon applies to most settings where strategic classification is pertinent. As such, it imperative to correctly model and understand this phenomenon to ensure that classifiers deployed in sensitive settings act as intended. We specifically study the following questions:
How should we jointly model the strategic interactions between agents alongside those with the learner?
What is the appropriate notion of equilibrium in this setting and what properties does have?
What learning guarantees can be given for classifiers in such settings?
1.1 OUR CONTRIBUTIONS
We study the problem of deploying classifiers in strategic multi-agent settings with inter-agent ex- ternalities from theoretical perspective. Consistent with prior literature, the interaction between the learner and the agents is modeled as a Stackelberg game: the learner first commits to classifier to which agents can respond. The resulting inter-agent interactions are captured as simultaneous game, and the Stackelberg-Nawt Equilibrium is proposed as the solution concept for all interac- tions. We precisely define these aspects of the multi-agent strategic classification game in Section 2. Learning in this setting is challenging, not least due to the possible multiplicity of equilibrium, their computation, and their dynamics due to a changing classifier. Section 3 motivates set of structural assumptions on the cost and externality, under which the inter-agent simultaneous game has a unique pure Nash Equilibrium that efficiently computable. Building on this insight, Section comments on the regularity of the Nash Equilibrium under changing classifiers, and provides probably ap- proximately correct (PAC) learning guarantees for computing the Stackelberg-Naat Equilibrium. Intuitively, it is possible to learn loss- loss-minimizing classifiers that generalize to random number of agents manipulating to achieve Nash Equilibrium. We also differentiate through the equilibrium solution to explicitly characterize the loss gradient, illustrating the feasibility of gradient- hased op- timization algorithms. Section uses our motivating examples to model some externality functions that can be captured by our general framework. Lastly, in Section 7, we discuss some limitations of our work alongside technical and conceptual extensions.
1.2 RELATED WORK
Our work builds on the growing literature on strategic classification (Hardt et al., 2016; Brückner al.. 2012; Brückner& Scheffer, 2009). In the basic setting, a learner seeks to release classi- fier that accounts for the fact that strategic agents may misreport their true features to maximize their utility, which determined by the likelihood of positive outcome and the cost incurred for misreporting.
Recent papers have studied extensions of the basic strategic classification setting. For example, Levanon & Rosenfeld (2022) introduce setting where agents' utility functions capture different in- tentions beyond simply maximizing for the positive outcome. Others aim to account for limited in- formation (Ghalme et al., 2021; Harris et al., 2022; Bechavod et al., 2022), unknown utilities (Dong et al., 2018) and causal effects (Miller et al., 2020; Horowitz & Rosenfeld, 2023). These extensions do not handle externaiities multi-agent behaviour in general.
2

---

Published as a conference paper at ICLR 2025
While motivated by different aspect of strategic classification, the work of Eilat al. (2023), which studies strategic classification in a graph setting, has conceptual similarities with our work. Node classification on graphs naturally depends agents can exploit. While this implicitly models agent interactions as not wholly independent, there several fundamental differences from our work. First, agents in their model are interrelated due to the classifier outcome of one agent depending on neighboring nodes; in contrast, we consider the classifier outcome for an agent to only depend on their feature, with the externality explicitly capturing additional risk or cost to agents due to others also interacting in the system. This better aligns with our motivation to capture classification dynamics in competitive high-stakes settings. Furthermore, they consider agents myopically best responding over a sequence of rounds whereas we consider the performance of a classifier at a Nash Equilibrium.
neighboring nodes' features, which strategic
Further afield, machine learning researchers have investigated the effect of strategic behavior on social welfare (Milli et al., 2019; Haghtalab et al., 2020; Kleinberg Raghavan, 2020) or on dif- ferent groups of agents (Hu et al., 2019). However, none of these papers consider the direct impact that manipulation by others can have on each individual agent. The impact of such externalities has, nonetheless, been studied in computational problems like auctions (Agarwal et al., 2020), data markets (Hossain & Chen, 2024), facility location (Li et al., 2019), and for long-term faireess ac- countability (Heidari al., 2019).
MODEL
Preliminaries: For E N, let [k] (1....,,k] We consider kt strategic agents interacting with learner who releases classifier parametrized by weights w. Using one of our running examples, this corresponds to k students applying for admission to a university, which decides to accept or reject using classifier fw- Let æ; E Rd and y E f-1,+11 denote the feature vector and true class of agent respectively, with (z;, Vt) ~ D. Let X E R denote the & agents' feature matrix, and y E +1]+ the vector of their true class labels', sampled independently from D; we the shorthand
x) ~ D x 2
We use the notation X and X,j to respectively refer to the jth row and jth column of the matrix X, and [X:; X2) to denote two matrices concatenated along rows.
Our focus will be on binary linear classifiers due to their wide-spread practical usage and popularity within the strategic classification literature? (Hardt et al., 2016; Dong et al., 2018; Bechavod et al., 2022); that is, E Ω C d and fx) = (ar, w) denotes the score for positive classification. The learner may use any Lipschitz loss function' to compute the loss and maximize the accuracy of their deployed classifier with respect to the true labels.
Utility and Externality: Following the standard strategic classification model, consider Stackelberg interaction between the learner and the agents (Hardt et al., 2016). That is, the learner first releases classifier fw. and thereafter, agents submit their features to be classified. An agent need not be truthful and may instead submit a manipulated feature vector x to receive a higher score for the positive class. Consistent with the strategic classification literature (Dong et al., 2018; Bechavod et al., 2022), we assume agent utilities are proportional to the score: fa (xx()) ((x;), where g (æ;): nd + RR is an agent specific gain for positive classification".
In line with prior work, assume agent features lie within bounded region (without loss of generality [0, 1]4) and they incur a cost c(x,, x²) in modifying their true feature vector. However, in contrast to these earlier models, also consider agents' decisions causing externality to others. Conceptually, externality is the impact agents' actions have on one another when interacting within a
In general, use hold capital letters refer to matrices, and bold lower case letters refer to vectors.
2Our results can be generalized to multi-class linear classifiers.
2 Thiis includes nearly any reasonable loss function including Hinge Loss, Cross Entropy Loss, MSF, etc. 'It may be common to associate type vector 0, with an agent and express gain in terms of g (0, æ.). This is equivalent to our utility model as the feature vector can include the type. This type of dependence can he extended to our cost and externality functions well.
3

---

Published as a conference paper at ICLR 2025
common system. Formally, the negative externality suffered by agent due agent j is captured by the function t(z;, o/;, 2j, zz)). We use T(2;, x. total externality suffered by agent due to all other participating agents' decision. In summary, the total utility of agent i in reporting z. in our multi-agent strategic classification game is given by:
=وك X')
t(x,, 2//, J, x5)z)) to denote the
(1) The standard literature on strategic classification assumes the principal knows the cost function (Hardt et al., 2016; Milli et al., 2019; Levanon & Rosenfeld, 2021). We extend this assumption to
fw) , fw (xx ( (z,) c(x,, 2!) T(,;, X')
externality functions as well.
Game-There Theoretic Model: Since agent's total utility depends others' reports, the interaction between the agents is naturally modeled as a game. Taking inspiration from prior work on strategic regression (Chen et al., 2018; Hossain & Shah, 2021) and related settings (Nakamura, 2015), model this inter-agent interaction as simultaneous game. Correspondingly, the best response of agent given classifier fw and reports of others is arg maxx;E(0,11 (x X', fw))
For fixed classifier Sw,, the natural solution concept for the agent game is pure Nash Equilibrium (PNE). Formally, a set of reported values X = [ = is PNE if for each agent i and fixing the reported values of others, x! is a best response for agent i. Intuitively, no agent can unilaterally improve their total utility at this equilibrium. Since PNE is not necessarily unique, let NE( (E(X, fw) denote the correspondence from the true features to the set of features reported at an equilibrium under classifier fw- That is: X E NE(X, fw).
Learning Problem:
While the relationship between the i agents corresponds simultaneous game, the principal and agent interactions still induce Stackelberg game since the principal first commits to classifier fw. The Stackelberg equilibrium in the classical setting is with respect to single agent best responding under the released classifier; however, multi-agent setting implies the principal must now react according to the Nash Equilibrium induced by their chosen classifier. Thus, the principal's 's goal is to compute the Stackelberg-Natt Equilibrium (Xu et al., 2016), which corresponds to a classifier that performs optimally when sampled features reach a pure Nash Equilibrium with respect to the chosen classifier.
Since the number of participants in the classification setting (c.g., the number of students applying for admissions) is not fixed, let kmaz denote the maximum number of such participants, and let K. denote a distribution over [kmaa]]- The principal has access to a dataset of n labeled samples S = {(X1, k1, (Xa, In: k.)). where sample j consists of ky K. and (X,,35) D4,, That is, the jth samples consist of the features and labels of the kj participating agents. The principal uses this training set S to learn a classifier that performs well in practice. The optimal classifier is formally defined as follows:
Definition 1. The optimal classifier parameter w in the multi-agent strategic classification game with loss function f, participant distribution K, and data distribution D is given by:
w" arg min Ex (X..) wEft
Σ Su
XvENE(X,Fa
The learning problem in this Stackelberg-Nat game is non-trivial for several reasons. First, it re- quires optimizing over the PNE of the sampled feature vectors. We discuss the efficient computation of this equilibrium in Section 3 under structural assumptions on the cost and externality. Second, we must not only generalize with respect to the equilibrium of sampled agents but also when the number of such agents is random. We address this and the optimization of fw from a dataset S in Section 4.
EQUILIBRIUM PROPERTIES
Core to our problem is computing the PNE achieved by the sampled agents since it informs the loss suffered by the principal under their chosen classifier. Thus, understanding equilibrium properties such existence, uniqueness, and computation is crucial to any learning algorithm. However, such properties cannot be precisely stated without a structured model of the agent utilities, which in our game is largely predicated upon the cost and externality. We formally state assumptions below:
4

---

Published as a conference paper at ICLR 2025
1. The cost is given by the &g norm of the manipulation vector: c(z;, xzi ail 2/
2. Externalities are pairwise symmetric: Vi,j, ((a Ly, 22 25) t( a'y,
Li Di xt)).
3. Total externality faced by any agent i, T(x 2/. X') is smooth and convex in the ma- nipulation variables (zi....,,zk)
Initial work strategic classification, including Hardt et al. (2016), assumed the cost function to be separable, a somewhat restrictive assumption. More recent work models cost as the norm of the manipulation vector ar' as it satisfies natural axioms associated with being metric (Levanon & Rosenfeld, 2022; Horowitz & Rosenfeld, 2023). The most common choice is the f2 norm, which we adopt (our results do hold for a larger class of cost functions see the end of this section).
Structural assumptions on externality models are routine in economic literature. In competitive set- tings, which describe many high-stakes classification tasks, symmetric externalities are natural and commonplace (Goeree et al., 2005; Hossain & Chen, 2024). Settings such as data markets (Agarwal al., 2020) and facility location (Li et al., 2019) further capture externality under linear model, which our model subsumes. To give an example of non-linear but convex externality, consider the loan application setting where a bank (the learner) is screening candidates for approval. The more candidates manipulate their reports, the more likely the bank's s approval process will become stricter, adversely affecting all candidates. The function t(x,, x/ Lj x²)) = (llæ æ; + || - =,,12)², which increases the manipulation increases can model this setting. It is convex since the square of a non-negative convex function is convex. While this is one example, Section 5 contains a more detailed exploration of externality models, and shows that our results hold for broader class of functions, including non-convex ones.
Returning to the PNE analysis of the manipulation game, first show in Theorem (proof in Appendix B) that when exteralities are pairwise symmetric, the resulting interactions can be char- acterized by potential game". Such games use single function, the potential function & to encapsulate the difference in utility to any agent due to their unilateral change in action (Monderer & Shapley, 1996). We formally define this below for convenience.
Definition 2. An n player simultaneous game is a potential game if there exists a : A + E mapping from joint action space to the reals such that for any agent i: u,(a,, a-;) un (a a = D(a;, a-i) +(al, a-i), where un is the 8t agent's 's utility.
Theorem 1. For any classifier Swo if the externalities are pairwise symmetric (Condition 2), the agent interactions constitute potential game with the potential function:
X', fw(()))) (xx) Σ x(
x4)
ΣΣ E
t(0 2 2,,z)))
Since all player incentives map to the potential function, PNE strategies exactly correspond to local maxima of the potential function (Roughgarden, 2010). Indeed, if agent could improve their util- ity by modifying their action, the value of the potential function at this updated action also increases. This has several implications. First, finding an equilibrium equivalent to finding such local max- ima, and second, properties of local maxima of & directly inform the multiplicit/uniqqemnn the equilibria. Lastly, suppose agents sequentially play their best response from any starting point. In that case, the potential function value is strictly increasing, giving simple local algorithm for arriving at a PNE.
of
Our next result shows that the potential function is strictly concave under our set of assumptions. For such functions, any local optimum is also the global optimum, such an optimum unique, and the PNE must be at this optimum (Neyman, 1997). Correspondingly. the Nash Equilibrium is unique and can be written as the outcome of a convex optimization problem". We present this formally below (proof in the Appendix B):
Theorem 2. Under Conditions 1, 2 and the potential function specified in Theorem strictly concave. Further, the Nash Equilibrium unique and is given by the function, arg max x' o(X,X', sw)-
"Appendix B also shows type of global externality can also be modeled as a potential game. 'In this setting, local maxima refers to a point that is optimal with respect to changes in any one direction. Maximizing concave objective under convex constraints, is convex optimization problem.
5

---

Published as a conference paper at ICLR 2025
This implies that NE(X, fw) is now function mapping true value to the unique PNE. This resolves the ambiguity of learning in the presence of multiple equilibria. Further, this function is the outcome of parameterized convex optimization problem (in terms of the classifier fw).
The result above hinges on the strict concavity of the potential function. While our stated conditions imply this, we note that Conditions 1 and 3 can be replaced with weaker one:
1' Σ, c(z; x() + Ei Ejz t(a,, o F3, z')), is smooth and strictly convex
We denote this as the cumulative impact of manipulation - total cost and the sum of all com- binations of externality. Due our pairwise symmetry condition, >. Eisn t(x, o Ly x²)) Ei=1 T(x; x/ X, X'); since convexity is preserved through summation, for any strictly convex cost (i.e. Condition 1, l2 norm squared cost) and any externality where Tæx, a.j. X, X') is con- vex (Condition 3) the updated condition above is immediately satisfied. This condition however is more general and allows us to capture a larger class of possibly non-convex externality within our framework. We have a detailed discussion of some of these richer models in Section
4 LEARNING AND GENERALIZATION
We now tackle the problem of learnability in our setting. Broadly speaking, the learner's goal is to ensure that a classifier trained on a finite dataset to anticipate agents misreporting to an equilibrium, performs well on the broader population distribution which exhibits similar behaviour. A unique aspect of our setting is the number of agents participating in a given instance need not be fixed. Taking university admissions as an example, the number of applicants in given year is not constant but rather random variable. Our generalization result should accommodate this variability in the number of players in each instance, alongside the equilibrium they reach.
Recall from Section 2 that kmaz denotes the largest number of simultaneous participants with K., a distribution over [fmaz]] and D, the data distribution that we sample from, i.e., (Iz, ys) ~ D. The learner has access to a training dataset of instances, where each instance involves sample k ~ IC, and then &; independent samples from the distribution D. Observe that the following is an equivalent sampling procedure: sample k; K. draw kmna independent samples from D, and then only consider the first k; elements. We use this latter procedure for the generalization result; formally, we define a joint distribution D D x.....x xK. The learner has access to n samples
Kmaz
from this distribution, representing their training set: S = {(X1, y1. k1, .... (Xn, Yny kn) where X₁ E Rmaas xd y: E Rmmur, and & E [kmaz] I. Note that each sample/instance in this dataset can be seen as holding the attributes of k; individuals.
For any chosen classifier fw. the participating agents reach a PNE and the classifier suffers a re- sulting loss based on this. In the preceding section, we show this equilibrium to be the solution of a convex optimization problem. To provide formal learning guarantees, however, it is important to understand how the outcome of this optimization (i.e. the PNE) behaves the classifier changes. Indeed, if the PNE drastically changes due to small changes in w, learning can be challenging.
Let NE(X, fw. 18 Xd x IRd [kmaa] + hm where the first k rows of the output correspond to the cquilibrium solution when k agents are participating. We prove in the following result that the potential function optimum (and thus the PNE strategy) is Lipschitz continuous in w. The theorem statement treats inputs to O and NE as vectors. This is without loss of generality since our X IR Amaz xd feature matrix is equivalent to a x E Ridhmaz vector, with the vector & norm ||æ||2 equivalent to the matrix Frobenius norm ||X||] ||F.
Lemma 1. Let ((x, x', fw) be the potential function for kmaz agents (æ, x' E Radkmas) Then for (bx x', fw)ll+1 n 2. where = mina' (Amin (22 2 (x, x', fw))) and maxa' w V the function NE(x, fw. k)) is Lipscchit in w (under the
norm) for any k.
The proof (deferred to the Appendix C) is technical and in fact shows the Lipschitz continuity for a general class of parametrized convex optimization problems. Noting that local Lipschitz- ness suffices, we lower bound the difference between an optimal and sub-optimal solution using properties of strict concavity and smoothness of the potential function. The remainder of the proof leverages the continuity of the objective in both x' and w along with the insights above to establish

---

Published as a conference paper at ICLR 2025
the Lipschitz-ness ness of the maximizer of @. To relate this to NE(X, fw.k), define the optimization objective as summing the potential function over only the first participants with a trivial function involving the remaining agents.
Next, for a loss function (x;), y1) defined on classifying an individual's reported features, the average loss sample consisting of le participating strategic agents is given by L(X,, y: fw, k)
E (NE( Jm, k)):).))))))))))) y;) We now define the standard learning theory notions using this: Definition 3. For a classifier Jux. the true risk R(Jw) on distribution D and the empirical risk R(Sw) on a dataset S consisting of n independent samples from is given respectively by:
R(fw) = L(
and R((w)
n L(X yo. Sw. k.).
We want to show that classifier chosen to minimize the risk finite dataset S, denoted by fws will be close in a PAC sense, to the true risk minimizer of the population, denoted by fü Recall that we focus on linear classifiers and such, our function class is the set of norm-constrained linear functions: {Ww, æ.) s.t. ||س|| S r). We denote Ω = (w s.t. ||lس| S r) as the corresponding parameter space. We now give our generalization guarantee:
Theorem 3. For any A-Liscchitz loss function f, linear function class = {w s.t. || S r), agent dynamics captured by a strictly concave potential function (xx, x', fw), and > 0. 8 > 0:
s.t.
(16(>(d + +
n
In + d'nn
P ((R(fw) - R( 5
where n is the Lipschitz constart from Lemma
The proof (deferred to the Appendix C), notes that the average loss on the sample (X, y, k:) is a scalar regardless of the randomness of the number of participants. Further, due to the Lipschitz-ness of the NE function, the loss changes predictably due to a changing classifier. This allows us to apply a covering argument and bound the discretization error. While the sample complexity itself does not directly depend on kmna (due mainly to the sample loss being scaled by the number of participants !) does depend on the Lipschitz constant r7. This constant defined with respect to the potential function over the maximum number of kmaz participants (see Lemma 1). Sample complexity, thus, has an implicit dependence on kmaz.
4.1 MINIMIZING EMPIRICAL RISK
While we have shown PAC learning is possible in multi-agent strategic classification game, cornerstone of learning is minimizing the empirical risk; that is, finding a classifier that minimizes loss incurred on the training set S. Even for convex loss function l and linear classifier fur minimizing this across the samples of S is non-trivial since the NE function is the solution to an optimization problem. In general, there is no closed-fore forem expression for the NE function and cannot hope for this loss minimization problem to be convex.
Machine learning nonetheless has vast literature optimizing nonconvex loss functions; these, however, are largely gradient-based and require computing the loss gradient with respect to the learning parameter w. This loss is computed with respect the equilibrium outcome/score of participating agent i: (NE(X, f=)..)" When fw is linear, this is simply (NB(X, ww) We now show when and how this gradient can be explicitly computed.
Let 0 NE(X, fw)s; and 2; fw (NE(X, X, fw)):) = f(e,, for i E [k]. noting that 2, E R and 2 E Rdd The loss gradient given as follows:
ae
V (.L(a,y,s)) = W(([/NE(X fw), w),
V (
Van
Oz
& Oe
V.. fa) + Vwl k Oz
*The notation NE(X, fw); denotes the equilibrium report of the 1 agent. Since are concerned with the loss sample, we assume k kinaz and drop the dependence k.
7

---

Published as a conference paper at ICLR 2025
We use the chain rule here, with Tw representing the Jacobian with respect to of the loss with respect to the score, a feature the loss function. Further, the gradients V and w depend only on the function class we are learning. Indeed, for a linear function class, the desired gradient is given by:
á is the derivative 0z;
de 2z [wo ILE((,, Sw))) + NE(x, sw)c]
Va (ww
The remaining and crucial term is the Jacobian of the outcome of the PNE optimizer with respect to the weights: Iw (NE( f.)..) The theorem below proves exactly when this Jacobian exists, and explicitly characterizes it. Once again, for ease of exposition interpret the input and output of the NE function as a vector.
arg ma D(x', x. fw) where & is strictly concave and smooth, let X and Ie denote the dual variables corresponding the upper and lower bound con- straints. Then xi((w (w) NE(x,, Jw) is differentiable with respect to w everywhere except possibly if there exists an x. (w) E {0, with the corresponding dual variable set to O: i.e., if there exists such that (z) = A X 0) V (If(w) = 0 μ¹ 0).
Theorem 4. For NE(x,WW)
The proof (deferred to Appendix C) introduces primal and dual slack variables to capture the KKT conditions, which are necessary and sufficient in the optimization above, in an implicit equation. We show that the Jacobian of a slightly modified but representative version of this implicit function has full rank except possibly at the specified points. Aside from these degenerate points, implicit function theorem to explicitly compute the gradient. With this hand, the learner is free to use standard gradient descent based algorithms to solve the empirical risk minimization problem.
the
We also note that this result may be insightful for settings even when the potential function may be non-concave. As we have affine constraints, the KKT conditions still necessary at local optima (Boyd & Vandenberghe, 2004). Since our approach relies on implicitly characterizing the KKT conditions, we can still use this compute the derivative local optima, provided we can find them effectively. Game-theoretically, this would correspond to local Nash Equilibrium (Balduzzi al., 2018).
MODELS OF EXTERNALITY
The presented results leverage the strict concavity of the potential function to assert that the PNE is unique, efficiently computable, and PAC learning guarantees possible for the learning problem. Sec- tion 3 concluded by noting more general Condition (1') on the cost and externality ensure this. This allows to capture possibly non-convex externality; we give two such examples motivated by the settings we highlighted.
Proportional Externality: Externality in strategic classification can model an increased risk in de- tection/audit due to others also manipulating. our admissions example, the risk of the university (classifier) suspecting something is amiss is much higher when many students wrongfully claim to be top of their class, as opposed to a handful. As such, manipulation increases proportional to the extent to which others in the system also manipulate. We express the externality suffered by agent such a setting as:
natural that one's externality due to
d
ta0l,, Fi, Di, 211) k-1
Σ (akee - x 2 xTE)2
We scale by A --1 since each agent pays a single cost c(-) but suffers externality from k agents; this allows a (the scale constant for the cost) and 33 to be on the same scale. Next, observe that for individuals who do not manipulate, the total externality they incur is O. This consistent with one interpretation of the university admissions setting: even if many claim to be top of their class, those who truly are, have nothing to fear. We note this externality pairwise symmetric and we show below that it satisfies the updated condition (proof in Appendix D)).
Proposition 1. Under the cost c(x, x²) = al|= - x'1 the cumulative impact of manipulation under the proportional externality model is smooth and strictly convex for B a.
8

---

Published as a conference paper at ICLR 2025
Congestion Externality: In many decision crriiiinnmmainng scenarios. reported features map to real resources and have downstream consequences beyond classification. Externality can thus model an increased cost for manipulated features due to demand from others. Many countries, for example, deploy immigration policies that favour candidates who pledge to settle in under-populated areas (Picot influx of applicants may report such intentions and initially move to
al., 2023). Naturally, these areas (with many reneging on this soon after and relocating ) this can significantly increase housing and living costs for new immigrants in these underpopulated communities. such cases, individuals suffer from others manipulating even if they are being honest. Externalities of this nature can be modelled follows:
t( 2z)) 3
Σ exp(-(x'/e -
Under this externality, when reported values (regardless of their veracity) become more similar, indicating usage of common resources, the externality to agents increases, with the exponential function ensuring this is smooth. Again, it pairwise symmetric and satisfies our updated convexity condition (proof in Appendix D).
Proposition 2. Under cost c(æ, x') ail - 12, the cumulative impact of manipulation under the congestion externality model is smooth and strictly convex
/2'
We note that while these functions capture the spirit of each setting, they are by no means definitive. Indeed there may be other representations for these settings that satisfy our desiderata. Choosing the right model for the right context is an important design goal of the decision-maker.
EXPERIMENTS
[a 0.1,8 0.5)
0,2,5
0.3, 1.5)
BCELas (lt St
4.0
4.0
1.6-
1.8
1.0
Lown Mul Thiiske!
0.7-
0.7
10
30
13
21
30
40
20
40
1.6
BCEL
0.7
0.7
0.3
11.
10
30
13
20
30
20
4.0
4.1
1.0
BCEL (A- 13)
0.7
0.
0.
0.8
0.1
112
10
30
13
20
Epochs
Ezochs
Epochs
Figure Strategic training (red), corresponding strategic validation losses (blue), and strategic validation loss of baseline classifier trained with truthful/non-straee strategic reporting (green). We plot the mean losses over random datasets (with 90% confidence interval) training epochs.
We experimentally validate the possibility of training classifiers to be strategy-aware with respect to k agents misreporting to PNE. We use 2-class synthetic dataset generated by scikit-leare and use the layers library to compute PNE and update gradients (Pedregosa et al., 2011;
Canada such policy and reported provincial retention low as 39% (Picot al., 2023).

---

Published as a conference paper at ICLR 2025
Agrawal et al., 2019). We use linear classifier that returns the probability of assigning the positive class. Agent utilities are computed as per Equation (1), and we use the &2 norm square for the cost c(x, 2/) al| [z; 2/112 and the convex externality discussed in Section 3: t( z/. 2j )z,z()
- || -xy =myl22² l|2²², with T(æ;, ar x') = - Σ ((x; tt,, æ; æd}); we normalize by (k-1) to make the 3 term interpretable since each agent face externality from (k- k--)) others. During training, we sample a set of k agents from the training set, compute their PNE under the current classifier, use these PNE features to determine the outcome and loss, and then update gradients. We denote this as strategic training, and the corresponding loss curve is in red in figure 2. After each epoch, we run our model on the validation/test dataset, wherein we carry out the same procedure: sample k agents, compute PNE, and then classify. The resulting loss is plotted in blue in Figure 2. We ablate this experiment over different values of k and different strengths of cost and externality.
Given that the training and validation curves are decreasing in lockstep, our experiments indicate that the model is indeed generalizing. Further, the generalization error seems to decrease the intensity of the cost and externality increase. As a baseline to compare against, we train a truthful/non- strategic classifier optimality and consider the implications of using this classifier at test-time where agents are strategic (captured in the green curve). This is meant to simulate the deployment of non-strategy-awann classifiers in strategic setting. We note that for nearly all configurations, this baseline performs poorly, as expected. That said, while it is exceedingly poor for lower intensities of cost and externalities, as the intensity increases, the bascline performance relatively improved. This trend is somewhat expected since at higher intensities, the negative impact of manipulation is higher, incentivizing many to stay close to their true reports. More interestingly, we note that as k increases, the non-strategic baseline performance also improves. While this is less intuitive, as increases, any single agent's 's influence on total externality diminishes, and this quantity becomes an average over larger set of values. This has stabilizing effect on the externality experiences which may lead to more moderate equilibrium strategies. Nonetheless, it would be intriguing future work to better understand how aggressively the equilibrium reports shift from true values as k grows larger. In Appendix E, we compare against another baseline where the model is trained only considering cost and not externality, mimicking the classic setup of Hardt et al. (2016).
agent
DISCUSSION
This paper studies a fundamental question within the strategic classification paradigm: what is the effect of inter-agent externalities on both the agents and the classifier? It is no longer reasonable to assume agents simply best respond the classifier; rather, the Nash Equilibrium of the induced game becomes the natural solution concept, and we provide a set of conditions whereupon this equilibrium unique and efficiently computable. The classifier, on the other hand, must learn an optimal model with respect to such an induced equilibrium. We show that this Stackelberg- -ash Equilibrium can be learned in a PAC sense and its loss gradients computable. This paper shows the possibility of deploying loss-minimizing classifiers robust against rich manipulation dynamics.
limitation of our work the structural assumptions on externality. Their pairwise nature gives rise to potential game, and the convexity assumption ensures this is efficiently computable and satisfies Lipschitz regularity conditions. This leads to an intriguing open question: what learning guaran- tees. if any, can be given for non-concave potential functions where equilibria may not be unique or well-behaved? Can we precisely specify the necessary conditions (our results give a set of sufficient conditions) on externality to ensure both leamability and robustness? Understanding this is both technically and practically interesting. Another important direction is assuming the learner does not know the cost and externality model and must learn them by observing equilibrium reports over mul- tiple interactions. This closely parallels the literature on online strategic classification (Dong et al., 2018; Chen et al., 2020) and learning in games "Cesa-Bianchi & Lugosi, 2006). Given the high stakes, characterizing the welfare properties of multi-agent strategic interaction is also imperative. This can involve parametrizing the price of anarchy (Roughgarden, 2010) in terms of a given clas- sifier or simultaneously optimizing for welfare alongside robustness. In settings with transferrable utility, it may also be pertinent to consider coalition dynamics within the strategic model. Lastly, engaging with pertinent stakeholders to accurately capture real costs and externality and experimen- tally validate our model is necessary. This paper lays the groundwork for these important questions that arise when deploying classifiers in strategic multi-agent settings.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Ariel Procaccia was partially supported by the National Science Foundation under grants IIS- 2147187 and IIS-222988I; by the Office of Naval Research under grants N00014-24-1-274 and N00014-25-1- 1112251-2155 1-2153; and by grant from the Cooperative AI Foundation. Yiling Chen was partially supported by Amazon and the National Science Foundation under grant IIS-2147187.
REFERENCES
Anish Agarwal, Munther Dahleh, Thibaut Horel, and Maryann Rui. Towards data auctions with externalities. arXiv preprint (tti::200000034444 2020.
A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and Z. Kolter. Differentiable convex opti- mization layers. In Advances in Neural Information Processing Systems, 2019.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Grae- pel. The mechanics of n-player differentiable games. In International Conference Machine Learning. pp. 354-363, 2018.
Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani. Information discrepancy in strategic learning. International Conference on Machine Learning, pp. 1691-1715, 2022.
Maria Patricia Bejarano Carbo. Machine learning applications in the united states criminal justice system: critical content analysis of the compas recidivism risk assessment. 2021.
Claude Berge. Topological spaces. Oliver & Boyd, 1963.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Michael Brückner and Tobias Scheffer. Nash equilibria of static prediction games. Advances in neural information processing systems, 22, 2009.
Michael Brückner, Christian Kanzow, and Tobias Scheffer. Static prediction games for adversarial learning problems. The Journal of Machine Learning Research, 13(1):26172254, 2012.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Yiling Chen, Chara Podimata, Ariel D Procaccia, and Nisarg Shah. Strategyproof linear regression in high dimensions. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 9-26, 2018.
Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy- aware linear classifiers. Advances in Neural Information Processing Systems, 10211526-152770 21526,,0200 2020.
RH Coase. The problem of social cost. Journal of Law and Economics, pp. 1-44, 1960.
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strate- gic classification from revealed preferences. Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 55-70, 2018.
Itay Bilat, Ben Finkelshtein, Chaim Baskin, and Nir Rosenfeld. Strategic classification with graph neural networks. In Proceeding of the 11-th International Conference on Learning Representa- tions (ICLR), 2023.
Mariah DR Evans, Jonathan Kelley, Joanna Sikora, and Donald J Treiman. Family scholarly culture and educational success: Books and schooling in 27 nations. Research in social stratification and mobility, 28(2): 2010.
Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam Talgam-Cohen, and Nir Rosenfeld. Strategic classi- fication the dark. In In Proceeding of the 24th International Conference on Machine Learning (ICML), pp. 3672-3681, 2021.
11

---

Published as a conference paper at ICLR 2025
Jacob K Goeree, Emiel Maasland, Sander Onderstal, and John L Turner. How (not) to raise money. Journal of Political Economy, (13(4):977-913 2005.
Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z. Wang. Maximizing welfare with incentive-aware evaluation mechanisms. In Proceeding of the 26-th International Joint Confer- ence on Artificial Intelligence (IJCAI), pp. 160-166, 2020.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classifica- tion. In Proceedings of the 2016 ACM conference innovations in theoretical computer science, pp. 111-122, 2016.
Keegan Harris, Dung Daniel Ngo, Logan Stapleton, Hoda Heidari, and Steven Wu. Strategic instrumental variable regression: Recovering causal relationships from strategic responses. In International Conference on Machine Learning, pp. 8502-8522, 2022.
Drew Harwell. A face-scanning algorithm increasingly decides whether you deserve the job. In Ethics of Data and Analytics, pp. 206-211. Auerbach Publications, 2022.
Hoda Heidari, Vedant Nanda, and Krishna P Gummadi. On the long-term impact of algorithmic de- cision policies: Effort unfaimess and feature segregation through social learning. In International Conference on Machine Learning, pp. 2692-2701, 2019.
Guy Horowitz and Nir Rosenfeld. Causal strategic classification: A tale of two shifts. In Interna- tional Conference on Machine Learning, pp. 13233-13253, 2023.
Safwan Hossain and Yiling Chen. Equilibrium of data markets with externality. In International Conference on Machine Learning, 2024.
Safwan Hossain and Nisarg Shah. The effect of strategic noise in linear regression. Autonomous Agents and Multi-Agent Systems, 35(2):21, 2021.
Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic ma- nipulation. In Proceedings of the 2nd Conference on Fairness, Accountability, and Transparency (FAceT), pp. 09992662222 2019.
Meena Jagadeesan, Celestine Sendler-Dünnee and Moritz Hardt. Alternative microfoundations for strategic classification. In International Conference Machine Learning, pp. 4687-4697, 2021.
Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? ACM Transactions on Economics and Computation (TEAC), 8(4):1-23, 2020.
I Elizabeth Kumar, Keegan Hines, and John P Dickerson. Equalizing credit opportunity in algo- rithms: Aligning algorithmic faimess research with us fair lending regulation. In Proceedings of the 2022 AAAI/ACM Conference on AI, Ethics, and Society, pp. 357-368, 2022.
Sagi Levanon and Nir Rosenfeld. Strategic classification made practical. In International Confer- ence on Machine Learning, pp.
2021.
Sagi Levanon and Nir Rosenfeld. Generalized strategic classification and the case of aligned incen- tives. In International Conference on Machine Learning, pp. 12593-12618, 2022.
Minming Li, Lili Mei, Yi Xu, Guochuan Zhang, and Yingchao Zhao. Facility location games with externalities. In Proceedings the 18th International Conference on Autonomous Agents and Multiagent Systems, pp. 1451-1451, 2019.
John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In Proceedings of the 21st International Conference Machine Learning (ICML), pp. 6917- 6926, 2020.
Smitha Milli, John Miller, Anca Dragan, and Moritz Hardt. The social cost of strategic classifica- tion. In Proceedings of the Conference Fairness, Accountability, and Transparency (FAceT), pp. 230-239, 2019.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124- 143, 1996.
12

---

Published as a conference paper at ICLR 2025
Tomoya Nakamura. One-leader and nultiple-follower stackelberg games with private information. Economics Letters, 127:27-30, 2015.
Abraham Neyman. Correlated equilibrium and potential games. International Journal of Game Theory, 26(2):223-227, 1997.
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer, 1999.
Elinor Ostrom. Tragedy of the commons. The new palgrave dictionary of economics, 2:1-4, 14,, 2008.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Coumnaeaa, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
WG Picot, Eden Crossman, and Feng Hou. The Provincial Nominee Program: Retention in Province of Landing. Statistics Canada= Statistique Canada, 2023.
AC Pigou. The economics of welfare. 1920.
Tim Roughgarden. Algorithmic game theory. Communications of the ACM. 53(7):78-86, 2010.
Georg Still. Lectures parametric optimization: An introduction. Optimization Online, pp. 2. 2018.
Stephen J Wright and Benjamin Recht. Optimization for data analysis. Cambridge University Press, 2022.
Tian Xie and Xueru Zhang. arXiv:2405.01810, 2024.
Non-linear welfare-aware strategic learning.
arXiv preprint
Jiuping Xu, Zongmin Li, Zhimiao Tao, Jiuping Xu, Zongmin Li, and Zhimiao Tao. Methodology from an equilibria viewpoints. Random-Like Bi-level Decision Making, pp. 365-386, 2016
13

---

Published as a conference paper at ICLR 2025
A IMPERFECT INFORMATION SETTING
Our model considers the agent interaction induced by a classifier as a simultaneous game with the Pure Nash Equilibrium (PNE) solution concept. general, PNE are defined for complete informa- tion settings since the agent needs to evaluate their best-response for them to verify an equilibrium. Nonetheless, recent literature on strategic classification literature has considered settings wherein agents have uncertainty about some relevant information (Jagadeesan et al., 2021; Bechavod et al., 2022: Xie Zhang, 2024).
In this vein, we show interesting relationship between our complete information PNE and the equilibrium under such uncertainty. More formally, consider a variant of our model where each agent i does not exactly know the true features X-; of the remaining agents, but instead has an estimate X-; about the features of the remaining agents, with X-; X_,+ + b,, with b, capturing the bias/error of the estimate"! " Then each agent computes their utility with respect to this possibly biased estimate and evaluates joint strategy based this. Formally:
u. (2 2/ X X fw) fm (x()g (xx) c(æ,, xe)) T(x,, L X- x'-)l
We note that only the externality term is affected by the uncertainty. We now show that at the com- plete information PNE X (=f...... ................................ xx{) strategy, agent can improve their biased/imperfect utility by more than e. Moreover this linearly depends on the bias/error b.
Proposition At the complete information PNE strategy X (z,,...,, x.)), no agent believes they can increase their biased/imperfect utility (equation 3) by more than 2X bill, where X is the Lipschitz constant for the externality function.
Proof. We recall this total externality function T; is smooth (twice differentiable) and since the domain of features is bounded, this function is also X-lipschitz, for some À 2 0. Formally, for any fixed value of æ; 2/1, X":
(T L X XL,) T: X X., - X
X ball2
(4)
Next, suppose that X (z). (2i....,.0 2t) is the complete information PNE strategy. Then by definition, the following holds for any o/:
fw (x )g (x,))-((z, c(x,, TTx,, 27. X XL,) 2 fo
T(xx, 2/,, x,,, x1,
Using the relations established in equations 4, we have that:
(=(x))) (ax)) - c(x;, - T(x;, x X_1, x2 + A|bbil1 2
fu(x)) (x::) c(x,, x T (x;, 2/., X X 2||b:l12
The inequality above implies that a PNE, agent cannot gain by more than bx|lb:1/2 with respect to their biased/imperfect utility function.
For simplicity, it is casier think of X-, and X-; of size (A- 1)d.
14

---

Published as a conference paper at ICLR 2025
SECTION 3 PROOFS B
Proof of Theorem
Proof. A potential function encapsulates the change in utility to any agent i due to their unilateral deviation. For us to claim that the proposed function & as potential function, the following must hold:
Vi u. (X, at), fw) (x, (x", 2 fw) o(x, (X"s af), fw)
(XX,1X x I.
Observe that the expression on the left is given by:
(a() fnr (oo")))) - [c(acf, mi) c(x=' a.))
Σ a0 By xg) - 1( xx', Fy x.)))
j#
We claim this is equivalent to (X,, [X', a1l ( |X", xh) fw). Since only x changes to x" terms involving gain and cost in the potential function difference match the above. Simi- larly, all externalities terms not involving x remain the same and only the externalities involving agent remain. There are exactly k such terms and due to symmetry, this is equivalent to Enzt Ma,, a/ Fj rr)) (a., an Fj sr))).
A note on global externality:
There scenarios wherein the externality suffered by agent is global and cannot be fac- torized a pairwise fashion. For a set of reported values X' = (z',...,, , let ('X denote the externality suffered by any agent due to the global/total set of decisions of everyone. This sort of externality is spiritually akin to a tragedy of the commons scenario (common in modeling pollution, public health, etc) where all agents equally suffer due the combined actions of the whole (Ostrom, 2008). For such settings, the agent dynamics can be captured by the following potential function:
X X' = Σ fa(l)))
Σ cla, 24) - T'X,
(5)
Indeed, any agent i shifting their reported value from x' to x" observes change in utility exactly equal to: f
(x;
|c(
(., x.) c(x, x.)] - [X' xX', - [X",; (X,, [XL; " As such, insofar
is immediate that this is equal to ((X, [X_ x fw) T(X, X') convex and smooth (the assumptions made at the start of section 3) all results in the paper hold for this global model of externality.
Proof of Theorem
X, Proof. Due to the pairwise symmetry condition, we know that Σ T(x,, X,,
2 2 Eysi (1.,, o/ Tz, Hence if each T( a/, X. X') is convex, then the last term in mz, a²)) is also convex. Combined with the l2 norm
the potential function, Σx_ Ej>s (w,, arl, my square cost, which is strictly convex, and fa which is linear, it immediately follows that that the potential function strictly concave. The optimization program for the Nash Equilibrium follows immediately from this.
For concave optimization problems, any local optima is a global optima. Suppose by contradiction there are global optima X', X" with Φ(X, X', fw] $(X,X" fw) m. Then strict
concavity implies: 6XXXXX' + (1 x)
X X X', (l (1-1111@p XX, fw) m.
Since the feasible region convex, the points on the X.X' + (1-1) are feasible and thus neither X' or X" could be maximizers.
15

---

Published as a conference paper at ICLR 2025
C
SECTION 4 PROOFS
Proof of Lemma
Proof. We begin by proving the Lipschitz continuity of the maximizer of the following generic optimization problem:
x (w) arg max (x) 2'E..t
(6)
where V is strictly concave in x' for any w E S2 and X' is convex. We know there is always a unique well-defined function. We also note that our
maximizer, and thus the optimal value x² x'(w) optimization problem satisfies the conditions of Berge's Maximum Theorem (Berge, 1963). Thus, we can immediately conclude that the correspondence from any w to the set of maximizers is upper- hemicontinuous. Since our maximizer is unique- i.e. the set is a singleton it suffices to observe that any set-valued map that is singleton is upper-hemicontinos if and only if the corresponding function is continuous.
Let (ww refers to an open ball of radium e centered at w. For Lipschitz-ness, we first note that since Ωi is bounded and compact, it suffices to prove this locally. That is, we wish to show that for any w. there exists constants L, Ew > 0 such that for all w E Be_, ||0 (w) z'(w)ll I L - w wll2- Indeed, this means that for any two w', w" ft we can consider sequence of distinct point w1 w', W2, Wn-1, W., = w" lying on the line aw' + (1 a)w" such that I|,; - wi-1ll2 222 I 6w Then we have the following, which means it suffices to focus local Lipschitz-ness:
||a"" x=" (w')ll2 S Σ T.ll wi T.ll"" w'll2
We next prove a property that holds for the maximizer of our problem under any w. Fix a w, and let x² be the maximizer. Next, consider a Taylor expansion of v at x². One formulation of this presented in Chapter 2 of Wright & Recht (2022) states for some y E (0, 1), we have (the dependence on w is dropped for now as it is unchanged):
(a', (x=", (x' x=) 2x (xx"
2 (x' - x-) "
V2 1T 7xx' x²), x²)
va',,) S (a )) + 1a' - x =='" 42 (n 7(x' x² x²), )a' (a''((a')) -x))
where the second line follows from Lemma 2.7 in Still (2018), which states that at for any x' E X, Ve Ve (xx", w) (a' x²) < 02 We also note that V2 (a', is the Hessian matrix which is (1) always symmetric and (2) consists of all strictly negative eigenvalues since (x
always strictly concave. Since any symmetric matrix can be diagonalized as QAQT, where Q is the matrix of orthonormal eigenvectors and the A the eigenvalues, we have that (define p x' x²)):
a
2 + 7ax xx),, x²) = Q=Q'='= p Σ xOFT)2
where v, is the ,th eigenvector. Since we have strictly negative eigenvalues and Q is an orthonor- mal matrix and thus does not affect the norm of vector it matrix multiplies, we have (where the Amin ( V Vi returns the minimum eigenvalue of the Hessian across w E Ω and x' E X):
(xr' V (x + 720 xx" (xx -x") Amin (V2 V) 212 Amin (V 1)
v(x', S (a=",)) Amin VV. V | - x
Since Amin must be strictly negative, it is evident that there is a strictly positive constant c, namely = 1 Amin (V2 vD z min, - (>(V2 V(a',, ((),ww)) such that:
(x w) - v(x' w) 2 el|æ' x111
We now turn back to local Lipschitz-ness. Fix a T E Ω and denote the unique maximizer by x= (w)) z. From the relation derived above (Equation C), there exist constants ò1 c > O, such that:
(æ w) V () 2 c|| x
Væ X, | x0|2 < 61
12 Technically the lemma is for convex functions with 2, but it be easily massaged for concave functions
16

---

Published as a conference paper at ICLR 2025
Let - (, )) denote the optimal value at w. For d such that 0 < 5 < 81, let 2a ming' -al|a=='|||d (Tz w) - (< ()). Since T' is the global and strict optimizer at w. it holds that 2a > 0. Therefore, we have that:
V(x' w) S V 20 Val such that || - =212= = 5
We now leverage the continuity of ()) with respect to w at x W) For a chosen value a there must
exist an e such that for all E Beg (w), we have that | w) v w) < 9. Similarly, the
continuity of V with respect to w at (w, æ²) such that ||ae 2: 22 8, implies that for any such
æ' and chosen value 3. there exists ex/ such that for all w E Be_. (w), we have that (w),
M (xx', ww]l < ş. Letting min(E1, 1/m Ewt), the following holds:
AW E (w)), .: (T) E (v= a V + )
V(T,w) 2 Vp a
(9)
2
2
Yo E (w) x s.t ||æc - क = o: Vada w) E (w w))
a V( w)
+ a
(10)
2
2
Combining Equations 8 and 10 we have that for any w E Be(w)) and any x' such that |x'
S 8:
u( w) < V w) + 2 V'' -2x + S va
(11)
Fix a Wp E (w) We aim to show Lipschitz continuity between w and wp. and follow a similar structure as Theorem 6.2a in Still (2018). We know from Equation 9 that Vi (zr, wo) 2 v² -. We also know from Equation 11 that for any x' on the boundary of the Bx(z) ball, V('',w)) < 1/* -a.
Since (() is concave in x', this implies that the = -e- á super-level set of y (<x', (wo) (for fixed
w)) must lie within this B& ()) ball. In other words, the maximizer at wos x (wo) _ zo satisfies
||a5 2|22 S 6. Noting that V (ā, wa) (100 wa) O, we have that:
Ir (x: w) - ( w)) = [T w) (a wo)] - [V w) - V wo)] + [V( - (2 woll
[ (x; w) V wo)l - [V w) u (( wo)]
Consider next the function v (x', w) Var' wa) A g(æ²). Consider g(æ²) between ær and æn-
Indeed g(z)- - g(zo) = A - B 2 Va w) (x w) By the mean value theorem, there exists a a [0, such that:
(TT ()) (x و)) S ( - g( = V T 2 a (20 x). V - x), wo)] - xo)
Recall that for a differentiable function fww,, we can approximate it near a value ت using the gradi- ent: f(w) = f()) + f (w w) + of wIl). So for any x' E cl (x)) (cl denotes the closure), define h(w) = V Va', w).. Thus, we have that:
h(wn) h())) Vah(T)( wa) a w (2)
V Va wo) V Va= w)) V2 (a ( wo) + o[1||w w112)
V x V(a' ( - Va'', wo)l = Varw (ar x ( wo) + w wl12)
Going back to (( [) - v (wo, w) we have the following:
V(z, - v V(zO, w) S V n' ( + axoo x), w) V + ar x) wo)] (x xx))
< max
V [1''' ( w))l (x- xz)
(a)
max
V War V(x' R||l2 + 1) || well2 | zu 12-
x (x)
Letr= maxe' w |/ wx 0( w) la + 1. Then using the relation outlined in Equation 7, and noting
the fact that 20 E B 2)), we have that:
x xol12 < Viz w) v (xo, w) S | -woll || xol 2
æol12 - 2 - wp 2|
17

---

Published as a conference paper at ICLR 2025
To relate this to the Nash Equilibrium of arbitrary l participants, observe that the following is characterization of the NE(x, fw: k) function (again we treat a as Rddmuu dimensional vector):
kmaz
NE k))
arg max xt o'E(0.1)dkmar
( Locks fw)
The first term, the potential function, fits the function signature of y (see the objective in equation 6) since æ (the true features) is simply constant. Second, we note that the optimization problem here separable since the potential function only uses the first & feature vectors and the sum of norms only involves the remaining kmar & feature vectors. Further, the latter is independent of and will always be set to z'J- = zj for l < j S kmaz in the maximization program. Thus, we can appeal to the result above for the maximization of and claim the function NE(x, sw k) be lipschitz above but for the largest possible value of ki which is kmaz.
continuous where
O
18

---

Published as a conference paper at ICLR 2025
Proof of Theorem 3
Proof. Let {(k); X1, v1).... (Kn; xn: yn)} be the training set where X; E TR Xd and Yi E R Kmazz Let L(X,, Ye: fwr k2) denote the loss the i-th sample, where ( Yi, fwyki) 1. E ((f((NE(X, ;, fwo (.))))))))))) Note that the following holds where the expectation is over R
samples from D:
R(Sw)
n Σ
11 yi,
yc, kt) B(R(SW)] = - Σ [ y, Ju, b)] R(Sw)
"
(12)
Our goal is to show the following generalization: | R( 2 & with low probability. To that end, we use the fact that uniform convergence implies generalization. Formally:
- R(f)) - [R(fW) -(ff)) + (R([Z) R(()) S 2 sup [R((w) R(fw)l (13)
LWEF
where the second inequality follows from the triangle inequality and that R((fww R(fw) < 0.
Since the function space continuous, we will fix (-cover N of the parameter space Q. That is, for any w E Ω2 there exists a w' E NN such that || ( w'll S Ç. Since our parameter space is dimensional ball of norm r, is well known that such a covering can be achieved with [WS] S
2ryd For sample i in our dataset, let z; denote the vector of scores received. That is, Zij (NE(X; i, fw: k:) w) and let z/y denote the score on this sample when classifier for is used. Since our loss function is X-Lipschitz in the score Zij, we have that:
1 he
((x,, y/s ks) - yI.
yi fwr, =
elay vos)
El<gg May)
S
21111
Next, by making use of the triangle inequality, we have the following:
X
|| 2/il1
(NE(X;, fwo ke)g., - (NE(X;; Swos ki)ss,
k:
Av
(NE(X,, Jwi ki)s: Ju, - NE((,, Jwr, ke)s:, - -(NE(Xi, Swis ki)ss w')l
(NE(X,, fwr: ke)s: (w -w')) fw - NE(X,, fwr, kk)):
h INE(X,, fwr, ki)g:11 11(w -w)ll1 + k;
(N fws kt);: NE(X,, fw' ks)s;
<Ad]I(w - w')ll
A (N fwo NE(X,, fwr ki))
Ks
where the last incquality follows from the assumption that the feature vectors are bounded in the region [0, 1| Next, we make use of the following relations that hold for any matrix V and vector E Rd. (1) ||w||| < ||wس|| & v | |2. (2) submultiplicavity of matrix norms ||Vwlla s ||V||||l|2 and (3) [Vll I [[V| where |Vlle denotes the matrix Frobenius norm:
[[NE(XX, k.) - NE(X,, fwr, k:))w(1
S [[] X,, Sw. As) NE( swr, ;k;))wwll
S (NE( fwo k.) NE(X,, fwr, (urk),))le [r)))
Srv Ki ((NEE((,, - NE(X,, fwr, k:))le
19

---

Published as a conference paper at ICLR 2025
Next, appeal to theorem which establishes the 1ÿ Lippschhitz continuity of the NE function in under the || norm to state the following:
(X,, k.) - NE wollkwkkk k)))lle Strv ki || w'll2
Thus in combining the results here, we can state the following, where the last inequality follows from the definition of a covering:
[L(X;, yi, fur ka) L(X,, yi, Swi, ki)l S Ad] w w'll +
h; N. 1p / w w'll S A(d my)
This essentially bounds the change in empirical and true risk due to using classifier parameters from using parameters in the finite covering NS.. Formally, we expand Equation 13 state the following (wo is the closest element in A& to w):
sup [R((w)) R(fwwl sup R(fw') R(fww)) R((w) R(fw() R(fwr) R(fw)l
WEn
wen
I max [R(fw') - R(fw-)) + 2N(d 4r)). W'ENT
By choosing Ç ax(d+rr)y' we get that
sup [R(ww) R(fw) 2 SP max W'ENS [R(fwr) R(fw))
WEl
Lastly, can apply Hoeffding's inequality due to Equation 12 and using union bound over No the right-hand side of the inequality above, we have that
NE²
P max [R(w') - R(fw))) )1 2 $ 22NV exp w ENS
8
16A(d+ m/1)7
- -
exp
8
and the theorem follows by choosing n accordingly.
Proof of Theorem 4
Proof. Note that NE is the solution a strictly convex optimization problem. Let z kd. We express the Lagrangian of this problem as follows, with the À E IR denoting the dual variables for the upper bound constraint and y E IR,,, the duals for the lower bound (recall our feasible region a box (0, 1]=):
C('', A. 2( x x. fw) Σn 1)+
Σ piok
Since feasible region is always strictly satisfiable, Slater's condition is always satisfied. When our objective is concave, as modeled throughout the paper, the KKT conditions are both suffi- cient and necessary for the optimal solution xx NB( w). Since the constraints are affine, in non-concave setting, the KKT conditions are necessary at local optimum. Define vectors Su+ E - 8n- R SA R² Sp. R= which will be used to denote the primal and dual slacks. We now define the following implicit function G(-) : 7 IR?
V L(x' X, n, w) x - 1 8 att Vi [m] x s2_,, Vi [m]
G( X, 8z- 8--, 8x, 8x,
diaa(()((
x') (1'1
(2))
x x Vie im] #4 n. Vi [m]
20

---

Published as a conference paper at ICLR 2025
Let G(.) O. Under this implicit equation, the first row of equations corresponds to the KKT stationarity conditions. The second two rows equations enforce each z is less than and greater than 0 respectively the KKT primal feasibility conditions. The fourth and fifth rows of equations correspond to the complementary slack constraints. The last two rows of equations enforce that the dual variables positive, the KKT dual feasibility condition. Thus, when G(-) KKT conditions are satisfied, and with a concave objective this also implies the solution is optimal.
it means the
Similarly, for any optimal X , ,4" since it is feasible, can always find the corresponding slacks as to satisfy G(-) = 0. Therefore, solutions to this implicit equation fully characterizes the optimal solution.
Let (x', A, $2. 8p) and we can simplify our equation to G(p, () 0. Any p that satisfies this is the optimal solution for w. We aim to use the Implicit Function Theorem and to that end, we first compute the Jacobian (=') as follows (the columns represent the derivative with respect to x', X, ,e, 8 8A, 8,))
V2 (( xr, fw) s
I
0
0
0
I
0
0
diag(2)ss.:
8
0
0
I
0
0
0
diag(-2) 2)8 8
0
0
Jz(G)=
AA
Ix
0
0
0
0
diag (M)
0
-
Ix
0
0
0
0
0 0
diag(- (
0
0
I
0
diag( -2)
We note that the first m columns are always linearly independent owing to the block of identity matrices in the second and third rows of block matrices. Similarly, the second and third sets of m columns are linearly independent owing to the identity in the first row. The remaining columns correspond to slack variables, which we now address. constraint is active x; E {0, 1}. Under
the KKT conditions, the Lagrange multiplier for inactive constraints must be 0. Let I S [2m]
denote set of active constraints. Let I(w) = {il=; (w) 0} (i (w) =1. We define
the inverse mapping (I) as follows: (I)) {w ( I}. It is immediate that the set
(w VI E [2m]] is a partition of the parameter space Q
Fix an I and without loss of generality, let i constraints from À and constraints from μ be active. ie the dual variables corresponding to the active constraints since the others will be 0 under KKT complementary slackness condition. Similarly, we need only consider the slacks for the inactive constraints since those are the only ones free. Thus for E (I)
Then for w E w(Z), it suffices to consider X; E R' and μ4 E R iie
simplify the general function G to function G' IR 3m3++sts x Rd R3m+++t by focusing only on the inactive primal slacks and the active dual variables and their corresponding slack.
We note that by definition, the primal slack for inactive constraints cannot be 0 by definition (oth- erwise those constraints would be active). Hence the columns corresponding those are also inde- pendent. Thus, if the dual slacks for the active constraints are non non-zero, then the Jacobian for G' has full rank. This allows us to apply the implicit function theorem and state the following:
Tw (NE(æ, fw)) ONE(æ, fw)
dw
If however some of these dual slacks zero, then it suggests that some of these constraints redundant and the Jacobian of G' may not be invertible. This is formally equivalent to:
3i (zj = 1AX = 0) v (zf = 0 μ4 =0)
Indeed, this is a degenerate situation known strict complementary failure (Nocedal & Wright, 1999) and represents the threshold or boundary of the w(Z) region where one set of constraints is becoming active and another inactive.
21

---

Published as a conference paper at ICLR 2025
D
SECTION 5 PROOFS
Proof of Proposition
Proof. We express the cumulative impact of manipulation under the stated conditions follows:
(I xxe) 2 x2t
t=1
t=
(1 - m
Σ 1=1 J2i
(1/ - -x) =E
Since the sum of strictly convex functions convex, it suffices show that each inner summand is strictly convex. For a fixed E, we observe that since since there are exactly k(k-1) pairs satisfying j >> and in each feature æ; appears in exactly (k 1) of these pairs, the inner summand can be written as follows:
Ve: ΣΣ 1 2a)²
8 2 (a 2z2e² + - 2 =z)1)
(14)
Again since convexity is preserved summation, we only need to show strong convexity with respect to the summands, each of whom is function of two variables (I'e and z'ze since a; and æj constants). For arbitrary summand index by (i, let
(I/z 1or-xag -it) and u, (x/ee- [tie-zap zze). Then the Hessian (upon multiplying Equation 14 by k - 1, which does not affect convexity), is:
2a - 2G 43u,uy 4Bu,u
2a + 2,3u
The determinant of this Hessian, when simplified, given by:
det
4a² 4aBrr 4a 12,8 u²u
Since we wish to show the determinant strictly positive, a² a,3 + aBB > 3.32 As feature vectors are bounded, u4 uy E [-1, 1]. and our condition is a 3, the following holds:
a aBu + az > 8 uu Bug uu, 8 + Bzu
2 8 + 23
+ u, = u.
where the second last transition the fact that 2ufuz ni + un in the feature vector range.
Proof of Proposition 2
Proof. We express the cumulative impact of manipulation under the stated conditions follows:
(I xz0)²
exp( -1//e - x2
j>i
h
( Tut
exp( - - 25p)
Since the sum of strictly convex functions convex, it suffices show that each inner summand is strictly convex. For a fixed f, we observe that since since there are exactly k(k-1) pairs satisfying
j > and in each feature an appears in exactly (A: of these pairs, the inner summand can be written as follows:
(2/)
za)² _ exp(-(2'4 22,0))) + - - -x,1)²
(15)
22

---

Published as a conference paper at ICLR 2025
Again, since convexity is preserved in summation, we only need to show strong convexity with respect to the summands, each whom is a function of two variables (z/gz and z'ye). For an arbitrary summand index by (i,j), let u = (1/22 =zee). Then the Hessian (upon multiplying Equation 15 by - 1, which does not affect convexity) is given by:
[2a + 2Be x² 2 12n² 1
2 1² 23e- - 2u
V2 de 24
2.e-"
u² 2n²)
2a 2.3
2. [2n 223
1]-
A positive definite matrix is equivalent to matrix with all positive principal minors. When & < v2 < a, we note the the (0, 0) index (and thus the first principal minor) is positive. The second principal minor is the determinant, which for our 2 x matrix above is given by:
det V syp 4a 16a3e =² u² 45-e 2n 14u 2].
Note that the middle term is always positive. The last term is the most negative when u = 0, which results in it being -8,2. It is evident that can well compensated for by the first term since using
our relation between 3 and a, we have that: 862 < 8
4a
E ADDITIONAL. EXPERIMENTS
0.1,8 U.3)
1.0)
4.-
8.0
400
18imt Triisia))
BCELoss (b-
Sinel Volial Tow (Caiisely Thiiinng)
1.6
1.6
1.5
0.7
0.7
0.7
0.3
0.3
1133
10
BOB Lose (0)
4.0
1.6
0.7
0.7
0.7
012
10
30
10
20
BCEL Lose (A- 12)
400
1.5
1.5
0.7
0.7
012
0.8
0.1
02
10
30
10
20 Epochs
Epochs
Epochs
Figure Strategic training (red), corresponding strategic validation losses (blue), and strategic validation loss of classifier trained only considering cost (gray). We plot the mean losses over 15 random datasets (with 90% confidence interval) vs training epochs.
We also consider comparing our experimental results against cost-only baseline. During the train- ing of this classifier, the agents manipulate their features only considering the cost (and not the externality). In this setting, agents have a dominant strategy since the cost does not depend on the reports of the others. The grey curve plots the strategic validation loss of this classifier, wherein agents manipulate considering both cost and externality and reach a PNE. This baseline is essen- tially trying to capture the performance of a classifier trained in the classical model of Hardt et al. (2016) (which considers only cost) when deployed in settings with externality.
than the classifier trained with both cost and externality considerations. This is naturally expected since at validation manipulation occurs considering both. That said, this baseline performs relatively better when the intensity of the cost
We first note that the cost-only baseline performs
23

---

Published as a conference paper at ICLR 2025
and externality are low. This is intuitive since at low intensities, the agents relatively free to misreport to increase gain, a dynamic captured by both classifiers. As intensities both cost and externality increase, the cost-only classifier only captures part of the story, ignoring the relatively large negative impacts of manipulation arising from externality. This likely leads the cost-only trained model to anticipate more extreme misreporting than what happens in practice, leading to relatively worse validation performance at these higher intensities. Lastly, we note that & does not seem to have any meaningful effect the performance of this cost-only baseline.
24


Reviews:
[{"review_id": "RPTkHhWjtm", "reviewer": "Reviewer_mGwb", "summary": "The study a generalization of strategic classification where the game between the principal and agents is Stackelberg, but the game between the agents itself is simultaneous. The principal's goal is to compute the Stackelberg-Nash equilibrium to maximize its utility.\n\nThey show:\n\nUnder some assumption the PNE of this game is unique and can be computed efficiently.\n\nPAC learning results for the principal.\n\nAnd they show ERM results through gradient-based methods.", "questions": "They assume that the number of agents that participate in the game is not fixed, but comes from the distribution. However, this assumption does not impact the PAC learning result. This assumption is mostly interesting from the modeling point, but are there scenarios where this assumption leads to different outcomes compared to a fixed number of agents?\n\nLine 196, shouldn't it be f_{\\omega}(x') instead of x inside the parentheses? If this is correct, then you may want to double-check it throughout the paper, in case it appears in other equations or explanations.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I think the writing of the paper is fantastic!\nAlso, the problem formulation is interesting.", "weaknesses": "Besides their novel formulation, their main result is their sample complexity result, but that seems to me to just be using a standard covering argument to bound the discretization error. Do you think you can get tighter bounds using other techniques like Rademacher complexity etc.?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qlNWvbLrgG", "reviewer": "Reviewer_T5xz", "summary": "The paper introduces a new variant of strategic classification that explicitly models how one agent's feature manipulation can affect other agents' utilities, a form of externalities. The authors model this multi-agent interaction as a Stackelberg game between the classifier (leader) and agents (followers). The paper contains several results under this model:\n- Under certain conditions, the agent manipulation game has a unique Pure Nash Equilibrium (PNE)\n- The PNE can be efficiently computed under certain technical conditions\n- A PAC learning guarantees for learning the optimal classifier\n- Some characterization of the optimization problem for learning the classifier\n- Two concrete externality models (that can be special cases of their general model): proportional externality and congestion externality.", "questions": "- Since the authors set up the downstream game as a potential game, perhaps they can make the point that the agents can reach NE through simple best-response dynamics? \n\n- The authors did a good job surveying recent related work on strategic classification, but perhaps missed the following:\n** On the Long-term Impact of Algorithmic Decision Policies: Effort Unfairness and Feature Segregation through Social Learning, ICML 2019. This paper models the \"information externality\" of some agents over others in settings like strategic classification.\n** Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses, ICML 2022. This paper also accounts for causal effects in strategic classification.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "In my opinion, the primary strength of the paper is modeling externality in strategic classification. I believe this aspect of externality has been missing in the long literature of strategic classification. \n\nThe authors also did a good job at identifying a clean set of technical conditions (ell_2 norm costs, pairwise symmetric externalities, and convex total externality) for a unique Pure Nash Equilibrium. In particular, the conditions lead to a potential game formulation, enabling the use of well-established game theoretic tools.\n\nThese technical conditions also lead to a clean analysis of their PAC learning guarantees. The Lipschitzness condition of NE in Lemma 1 seems quite nice and certainly facilitates the analysis for generalization error.", "weaknesses": "The paper's main weakness lies in its treatment of optimization. While the authors elegantly establish the existence and uniqueness of equilibria, they essentially punt on the crucial question of how to actually find the optimal classifier. Their argument - that gradient-based methods often work well for non-convex problems - feels particularly thin in this context. After all, we're not dealing with standard non-convexity here, but rather with a nested optimization where agents are reaching equilibrium inside the classifier's optimization loop.\n\nWhile the authors derived gradients through the equilibrium, they stopped short of showing these gradients are actually useful. A simple set of experiments on synthetic data or semi-synthetic data would have been useful here. For instance, does gradient descent reliably find good classifiers? How does the convergence behavior change with the number of agents or the strength of externalities? The field of strategic classification has evolved. Recent papers have routinely complemented their theoretical results with experimental validation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wDwcY978tI", "reviewer": "Reviewer_fMjo", "summary": "This paper considers agents being classified by a classifier $f_{\\omega}$ in a setup where these agents can manipulate their features in order to increase their utility in the classification task. Their utility also depends on the cost they incur to modify their features: the more they modify, the more they pay. Such phenomena naturally arise in tasks such as classifying students for admission at university (you - an agent - would like to manipulate your features to be better classified and get a better university). \n\nThe paper brings externalities to the model, which means that one agent's manipulations can affect the outcomes or incentives of others.\n\nThe paper frames the interactions as a Stackelberg game, where the principal (the classifier) commits to a strategy first, and is followed by agents responding simultaneously. Beyond theoretical contributions that study the arising equilibria, the paper establishes PAC learning guarantees for classifiers trained in these strategic multi-agent environments. It ends with several considerations on various models of externalities.", "questions": "The externality of an agent $j$ suffered by agent $i$ is modeled as $t(x_i, x_i’, x_j, x_j’)$. However, I would intuitively say that externalities are global: the externality suffered by an agent due to a group $J$ might not be factorized as a sum over elements from $J$. Is it possible to have more explanations about your choice?\n\nAt the PNE, the agents cannot increase their utility by changing their responses. However, I would be very interested in a discussion about what a coalition of agents could achieve. I feel like a lot of setups involve agents that could behave together and this question is not studied at all in the paper. How would the equilibrium be affected?\n\n“To give an example of a non-linear but convex externality, consider the loan application setting where a bank (the learner) is screening candidates for approval. The more adversely affecting all candidates.” The general setup and this example from your paper in particular remind me the setup of “Strategic Apple Testing”, Harris et al., 2023 (with agents arriving sequentially and manipulating their type). A discussion could be interesting.\nThe inter-agent externalities explain the whole inter-agent dynamics but I would be interested in a discussion about how the agents could find other ways to interact together, such as through contracting for instance (which is essential in Coase’s theory).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "I think that the problem tackled is very important and relevant. It is nice to see a problem arising from real-world concerns that is studied through a Econ-ML lens.\n\nBy combining Stackelberg/Nash game theory concepts with externalities, the authors create a framework that captures both the principal-agent and multi-agent dynamics in a unified model. This approach positions the principal as a leader setting a classifier policy, followed by agents interacting with both the classifier and one another, which is a complex yet analytically tractable setup. Then, based on the first results, they interestingly show that PAC learning is achievable.\n\nThe paper is well-written, with a lot of content and interesting theoretical results.", "weaknesses": "I think that the assumption of pairwise symmetric externalities is very limiting. Of course, it helps to obtain a model which exhibits nice results and gives Theorem 1 but it seems a bit far from a lot of real-world issues to me. “Equilibrium of Data Markets with Externality” is mentioned as a reference to justify this assumption but does not provide any material to motivate it. “How (Not) to Raise Money”, Goeree et al. is the other reference to justify this assumption, although they only mention symmetry for a very specific case of lottery. I think that more motivation is needed. Removing the assumption would be even better.\n\nMore discussion could be provided on the social optimality of the equilibria studied in the paper, for the players as a whole.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wvNpAW47yV", "reviewer": "Reviewer_soro", "summary": "This paper serves as the first framework to consider externalities in a multi-agent strategic classification (SC) game. The SC game is still a Stackelberg game with the externality modeled as an extra cost term $T(x_i, x_i', \\mathbf{X}, \\mathbf{X}')$. Assuming the externalities are pairwise symmetric and *the total cost and the sum of all combinations of externality* is smooth and strictly convex, the authors proved that a unique Nash Equilibrium ($NE$) exists for the post-manipulate features of $k$ agents. Based on this, the authors then characterized the conditions for $NE$ to be Lipschitz in the model parameter and further proved the sample complexity to guarantee the generalization error of the decision policy ($f_\\omega$)  in PAC learning. Finally, the authors explored the differentiability of $NE$ w.r.t. model parameter $\\omega$, proving the plausibility of using gradient-based algorithms to perform empirical risk minimization.", "questions": "1. Is it reasonable to assume each agent knows the full $\\mathbf{X}$?\n2. Could you elaborate more on the symmetric externality function in the admission example? Specifically, why the agents who do not manipulate will not impose externality on other agents who manipulate? Am I missing something?\n3. Given that you still have one page of space, could you provide at least one set of case studies?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Considering externalities in SC settings is well-motivated and the university admission example is quite natural. \n2. The paper is well-written and easy to follow. As a purely theoretical work, the authors provided both the PAC learning bound and discussed empirical risk minimization using gradient methods.\n3. The technical parts seem to be solid and mostly make sense to me.\n4. The paper is situated well in the previous literature. The discussion of [Eilat et al., 2023] is necessary.", "weaknesses": "Overall, I do believe the work has some merit and will enrich SC literature. But the paper can still benefit from some more comprehensive discussions.\n\n> Assumptions:\n\n1. the paper assumes a \"full-information\" SC setting where the decision policy is linear and all strategic agents know the decision policies, cost functions, and externality functions. The authors claimed to adhere to previous literature. However, recent works on SC questioned the plausibility of the assumptions, and a number of them are trying to relax the full information setting (e.g., [1,2,3]). I believe it is at least beneficial to discuss the assumption a bit more. \n\n2. It seems that assuming each agent knows the exact externality $T$ can be more problematic. Each agent has to know the features of all other agents to calculate its utility, and NE is a function of $\\mathbf{X}$. Is this realistic in practice and how can each agent know the full $\\mathbf{X}$ matrix? At least the authors should make this assumption clear.\n\n3. In Section 5 the authors present some examples of symmetric externality functions, but I still have some confusion. Consider the proportional externality in the admission example. Assume there are 2 agents $i,j$ with $1$-d feature $x_i, x_j$ and they rank $1,2$. Then $j$ seems to be able to manipulate $x_j$ at no externality if $i$ does not manipulate $x_i$.\n\n\n> Experiments\n\nWhile most of the theoretical results are clear, I believe the paper can still be improved by adding experiments. It would be great to see the optimal policies under some real datasets (e.g., Give me some credit, ACSIncome) with more practical externality functions. The experiments can demonstrate the sample complexity and the optimization procedure using gradient descent. They can also compare the settings with/without externalities.\n\n[1] Jagadeesan, Meena, Celestine Mendler-Dünner, and Moritz Hardt. \"Alternative microfoundations for strategic classification.\" International Conference on Machine Learning. PMLR, 2021.\n\n[2] Bechavod, Yahav, et al. \"Information discrepancy in strategic learning.\" International Conference on Machine Learning. PMLR, 2022.\n\n[3] Xie, Tian, and Xueru Zhang. \"Non-linear Welfare-Aware Strategic Learning.\" arXiv preprint arXiv:2405.01810 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)