Strategic Classification With Externalities

## Abstract

Abstract We propose a new variant of the strategic classification problem: a principal reveals a classifier, and n 𝑛 n italic_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.

## 1 Introduction

Machine learning algorithms are increasingly deployed in high-stakes decision making, including loan applications, school admissions, hiring, and insurance claims (Bejarano Carbo, ; Harwell, ; Kumar et al., ). Relying on past data as a reference, these algorithms use features of a 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 a more favorable outcome. This presents a significant challenge to 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 on *strategic classification* has emerged to understand the dynamics of this behavior and propose strategies for learning in such settings (Hardt et al., ).

By and large, the existing literature roughly models the interaction as follows: The learner (or principal) deploys a classifier, and an agent with feature $\bm{x}$ observes this and may choose to report a manipulated feature $\bm{x}^{\prime}$ to obtain a 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 to be independent; in other words, one agent’s action has no influence on another. We posit that this ignores a critical aspect of multi-agent interactions in a shared environment: their actions exert *externality* on one another. This is not a new observation: indeed, the notion that agents in a system are affected by a common resource has been a core component of economic models for over a century (Pigou, ; Coase, ). It has not, however, been formally studied in the strategic classification setting despite its relevance and applicability.

Consider the example Hardt et al. () used to initiate this literature: the number of books in the parent’s household may be a valid feature for university admissions given its correlation with student success (Evans et al., ). Since “books are relatively cheap”, this allows parents to game the system by buying “an attic full of unread books”(Hardt et al., ). It is immediate, however, that if all parents do this, then the price of books no longer stays cheap. This is the externality induced by everyone’s actions. Externality, however, can 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 a 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 in the top of their class or be affiliated with a specific organization. If only a handful of students manipulate their features, it may not be statistically discernible. However, if many claim to 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, a few applicants inflating their credit score on a 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 a 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 is 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:

- $\bullet$
How should we jointly model the strategic interactions between agents alongside those with the learner?
- $\bullet$
What is the appropriate notion of equilibrium in this setting and what properties does it have?
- $\bullet$
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 externalities from a 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 a classifier to which agents can respond. The resulting inter-agent interactions are captured as a simultaneous game, and the *Stackelberg-Nash Equilibrium* is proposed as the solution concept for all interactions. 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 a set of structural assumptions on the cost and externality, under which the inter-agent simultaneous game has a unique pure Nash equilibrium that is efficiently computable. Building on this insight, Section 4 comments on the regularity of the Nash equilibrium under changing classifiers, and provides probably approximately correct (PAC) learning guarantees for computing the Stackelberg-Nash equilibrium. Intuitively, it is possible to learn loss-minimizing classifiers that generalize to a random number of agents manipulating to achieve a Nash Equilibrium. We also differentiate through the equilibrium solution to explicitly characterize the loss gradient, illustrating the feasibility of gradient-based optimization algorithms. Section 5 uses our motivating examples to model some externality functions that can be captured by our general framework. Lastly, in Section 6, 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., ; Brückner et al., ; Brückner & Scheffer, ). In the basic setting, a learner seeks to release a classifier that accounts for the fact that strategic agents may misreport their true features to maximize their utility, which is determined by the likelihood of a positive outcome and the cost incurred for misreporting.

Recent papers have studied extensions of the basic strategic classification setting. For example, Levanon & Rosenfeld () introduce a setting where agents’ utility functions capture different intentions beyond simply maximizing for the positive outcome. Others aim to account for limited information (Ghalme et al., ; Bechavod et al., ), unknown utilities (Dong et al., ) and causal effects (Miller et al., ; Horowitz & Rosenfeld, ). These extensions do not handle externalities or multi-agent behaviour in general.

While motivated by a different aspect of strategic classification, the work of  Eilat et al. (), which studies strategic classification in a graph setting, has conceptual similarities with our work. Node classification on graphs naturally depends on neighboring nodes’ features, which strategic agents can exploit. While this implicitly models agent interactions as not wholly independent, there are 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.

Further afield, machine learning researchers have investigated the effect of strategic behavior on social welfare (Milli et al., ; Haghtalab et al., ; Kleinberg & Raghavan, ) or on different groups of agents (Hu et al., ). 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., ), data markets (Hossain & Chen, ), and facility location (Li et al., ).

## 2 Model

#### Preliminaries:

For $k\in\mathbb{N}$, let $[k]=\{1,\dots,k\}$. We consider $k$ strategic agents interacting with a learner who releases a classifier parametrized by weights $\bm{\omega}$. 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 $f_{\bm{\omega}}$. Let $\bm{x}_{i}\in\mathbb{R}^{d}$ and $y_{i}\in\{-1,+1\}$ denote the feature vector and true class of agent $i$ respectively, with $(\bm{x}_{i},y_{i})\sim\mathcal{D}$. Let $\bm{X}\in\mathbb{R}^{k\times d}$ denote the $k$ agents’ feature matrix, and $\bm{y}\in\{-1,+1\}^{k}$ the vector of their true class labels(^2^22In general, we use bold capital letters to refer to matrices, and bold lower case letters to refer to vectors.), sampled independently from $\mathcal{D}$; we use the shorthand

$$ $(\bm{X},\bm{y})\sim\underbrace{\mathcal{D}\times\dots\times\mathcal{D}}_{k} \triangleq\mathcal{D}^{k}.$ $$

We use the notation $\bm{X}_{i:}$ and $\bm{X}_{:j}$ to respectively refer to the $i^{th}$ row and $j^{th}$ column of the matrix $\bm{X}$, and $[\bm{X}_{1};\bm{X}_{2}]$ 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(^3^33Our results can be generalized to multi-class linear classifiers.) (Hardt et al., ; Dong et al., ; Bechavod et al., ); that is, $\bm{\omega}\in\Omega\subseteq\mathbb{R}^{d}$ and $f_{\bm{\omega}}(\bm{x})=\langle\bm{x},\bm{\omega}\rangle$ denotes the score for positive classification. The learner may use any Lipschitz loss function(^4^44This includes nearly any reasonable loss function including Hinge Loss, Cross Entropy Loss, MSE, etc.) 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, we consider a Stackelberg interaction between the learner and the agents (Hardt et al., ). That is, the learner first releases a classifier $f_{\bm{\omega}}$, and thereafter, agents submit their features to be classified. An agent need not be truthful and may instead submit a manipulated feature vector $\bm{x}^{\prime}_{i}$ to receive a higher score for the positive class. Consistent with the strategic classification literature (Dong et al., ; Bechavod et al., ), we assume agent utilities are proportional to the score: $f_{\bm{\omega}}(\bm{x}^{\prime}_{i})g^{+}(\bm{x}_{i})$, where $g^{+}(\bm{x}_{i}):\mathbb{R}^{d}\rightarrow\mathbb{R}$ is an agent specific gain for positive classification(^5^55It may be common to associate a type vector $\theta_{i}$ with an agent and express gain in terms of $g^{+}(\theta_{i},\bm{x}_{i})$. This is equivalent to our utility model as the feature vector can include the type. This type of dependence can be extended to our cost and externality functions as well.).

In line with prior work, we assume agent features lie within a bounded region (without loss of generality $[0,1]^{d}$) and they incur a *cost* $c(\bm{x}_{i},\bm{x}^{\prime}_{i})$ in modifying their true feature vector. However, in contrast to these earlier models, we also consider agents’ decisions causing externality to others. Conceptually, externality is the impact agents’ actions have on one another when interacting within a common system. Formally, the negative externality suffered by agent $i$ due to an agent $j$ is captured by the function $t(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{x}_{j},\bm{x}^{\prime}_{j})$. We use $T(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{X},\bm{X}^{\prime})=\sum_{j\neq i}{t(\bm{
x}_{i},\bm{x}^{\prime}_{i},\bm{x}_{j},\bm{x}^{\prime}_{j})}$ to denote the total externality suffered by agent $i$ due to all other participating agents’ decision. In summary, the total utility of an agent $i$ in reporting $\bm{x}^{\prime}_{i}$ in our multi-agent strategic classification game is:

$$ $u_{i}(\bm{X},\bm{X}^{\prime},f_{\bm{\omega}})=f_{\bm{\omega}}(\bm{x}^{\prime}_ {i})g^{+}(\bm{x}_{i})-c(\bm{x}_{i},\bm{x}^{\prime}_{i})-T(\bm{x}_{i},\bm{x}^{ \prime}_{i},\bm{X},\bm{X}^{\prime})$ $$

The standard literature on strategic classification assumes the principal knows the cost function (Hardt et al., ; Milli et al., ; Levanon & Rosenfeld, ). We extend this assumption to externality functions as well.

#### Game-Theoretic Model:

Since an agent’s total utility depends on others’ reports, the interaction between the agents is naturally modeled as a game. Taking inspiration from prior work on strategic regression (Chen et al., ; Hossain & Shah, ) and related settings (Nakamura, ), we model this inter-agent interaction as a simultaneous game. Correspondingly, the *best response* of agent $i$ given classifier $f_{\omega}$ and reports of others is:

$$ $\operatorname*{arg\,max}_{\bm{x}^{\prime}_{i}\in[0,1]^{d}}{u_{i}(\bm{X},\bm{X} ^{\prime},f_{\bm{\omega}})}$ $$

For a fixed classifier $f_{\bm{\omega}}$, the natural solution concept for the agent game is a *pure Nash Equilibrium* (PNE). Formally, a set of reported values $\bm{X}^{q}=[\bm{x}^{q}_{i};\dots;\bm{x}^{q}_{i}]$ is a PNE if for each agent $i$ and fixing the reported values of others, $\bm{x}_{i}^{q}$ 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 $\text{NE}(\bm{X},f_{\bm{\omega}})$ denote the correspondence from the true features to the set of features reported at an equilibrium under classifier $f_{\bm{\omega}}$. That is: $\bm{X}^{q}\in\text{NE}(\bm{X},f_{\bm{\omega}})$.

#### Learning Problem:

While the relationship between the $k$ agents corresponds to a simultaneous game, the principal and agent interactions still induce a Stackelberg game since the principal first commits to a classifier $f_{\bm{\omega}}$. The Stackelberg equilibrium in the classical setting is with respect to a single agent best responding under the released classifier; however, our multi-agent setting implies the principal must now react according to the Nash Equilibrium induced by their chosen classifier. Thus, the principal’s goal is to compute the *Stackelberg-Nash equilibrium* (Xu et al., ), 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 (e.g., the number of students applying for admissions) is not fixed, let $k_{max}$ denote the maximum number of such participants, and let $\mathcal{K}$ denote a distribution over $[k_{max}]$. The principal has access to a dataset of $n$ labeled samples $\mathcal{S}=\{(\bm{X}_{1},\bm{y}_{1},k_{1}),\dots,(\bm{X}_{n},\bm{y}_{n},k_{n})\}$, where sample $j$ consists of $k_{j}\sim\mathcal{K}$ and $(\bm{X}_{j},\bm{y}_{j})\sim\mathcal{D}^{k_{j}}$. That is, the $j^{th}$ samples consist of the features and labels of the $k_{j}$ participating agents. The principal uses this training set $\mathcal{S}$ to learn a classifier that performs well in practice. The optimal classifier is formally defined as follows:

###### Definition 1 .

The optimal classifier parameter $\bm{\omega}^{*}$ in the multi-agent strategic classification game with loss function $\ell$, participant distribution $\mathcal{K}$, and data distribution $\mathcal{D}$ is given by:

$$ $\bm{\omega}^{*}=\operatorname*{arg\,min}_{\bm{\omega}\in\Omega}{\mathbb{E}_{k \sim\mathcal{K}}\mathbb{E}_{(\bm{X},\bm{y})\sim\mathcal{D}^{k}}}\max_{\bm{X}^{ q}\in\mathrm{NE}(\bm{X},f_{\bm{\omega}})}{\left[\sum_{i=1}^{k}\ell(y_{i},f_{ \bm{\omega}}(\bm{x^{q}}_{i}))\right]}.$ $$

The learning problem in this Stackelberg-Nash game is non-trivial for several reasons. First, it requires 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 $f_{\bm{\omega}}$ from a dataset $\mathcal{S}$ in Section 4.

###### Definition 1 .

## 3 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 as 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 our assumptions below:

- 1.
The cost is given by the $\ell_{2}$ norm of the manipulation vector: $c(\bm{x}_{i},\bm{x}_{i})=\alpha||\bm{x}_{i}-\bm{x}^{\prime}_{i}||_{2}^{2}$
- 2.
Externalities are pairwise symmetric: $\forall i,j,\ t(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{x}_{j},\bm{x}^{\prime}_{j})
=t(\bm{x}_{j},\bm{x}^{\prime}_{j},\bm{x}_{i},\bm{x}^{\prime}_{i})$.
- 3.
Total externality faced by any agent $i$, $T(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{X},\bm{X}^{\prime})$ is smooth and convex in the manipulation variables $(\bm{x}^{\prime}_{1},\dots,\bm{x}^{\prime}_{k})$.

Initial work on strategic classification, including Hardt et al. (), assumed the cost function to be separable, a somewhat restrictive assumption. More recent work models cost as the norm of the manipulation vector $\bm{x}^{\prime}-\bm{x}$ as it satisfies natural axioms associated with being a metric (Levanon & Rosenfeld, ; Horowitz & Rosenfeld, ). The most common choice is the $\ell_{2}$ 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 settings, which describe many high-stakes classification tasks, symmetric externalities are natural and commonplace (Goeree et al., ; Hossain & Chen, ). Settings such as data markets (Agarwal et al., ) and facility location (Li et al., ) further capture externality under a linear model, which our model subsumes. 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 candidates manipulate their reports, the more likely the bank’s approval process will become stricter, adversely affecting all candidates. The function $t(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{x}_{j},\bm{x}^{\prime}_{j})=(||\bm{x}^{
\prime}_{i}-\bm{x}_{i}||_{2}+||\bm{x}^{\prime}_{j}-\bm{x}_{j}||_{2})^{2}$, which increases as 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 a broader class of functions, including non-convex ones.

Returning to the PNE analysis of the manipulation game, we first show in Theorem 1 that when externalities are pairwise symmetric, the resulting interactions can be characterized by a potential game. Such games use a single function, the potential function $\Phi$, to encapsulate the difference in utility to any agent $i$ due to their unilateral change in action (Monderer & Shapley, ). We formally define this below for convenience.

###### Definition 2 .

An $n$ player simultaneous game is a *potential game* if there exists a *potential* function $\Phi:\mathcal{A}^{n}\rightarrow\mathbb{R}$ mapping from joint action space to the reals such that for any agent $i$: $u_{i}(a_{i},\bm{a}_{-i})-u_{i}(a^{\prime}_{i},\bm{a}_{-i})=\Phi(a_{i},\bm{a}_{
-i})-\Phi(a^{\prime}_{i},\bm{a}_{-i})$, where $u_{i}$ is the $i^{th}$ agent’s utility.

###### Theorem 1 .

For any classifier $f_{\bm{\omega}}$, if the externalities are pairwise symmetric (Condition 2), the agent interactions constitute a potential game with the potential function:

$$ $\Phi(\bm{X},\bm{X}^{\prime},f_{\bm{\omega}})=\sum_{i=1}^{k}{f_{\bm{\omega}}( \bm{x}^{\prime}_{i})g^{+}(\bm{x}_{i})}-\sum_{i=1}^{k}{c(\bm{x}_{i},\bm{x}^{ \prime}_{i})}-\sum_{i=1}^{k}\sum_{j>i}{t(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{x} _{j},\bm{x}^{\prime}_{j})}.$ $$

###### 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 $\Phi$ as a potential function, the following must hold:

$$ $\forall i:u_{i}(\bm{X},[\bm{X}^{\prime}_{-i};\bm{x}^{\prime}_{i}],f_{\bm{ \omega}})-u_{i}(\bm{X},[\bm{X}^{\prime}_{-i};\bm{x}^{\prime\prime}_{i}],f_{\bm {\omega}})=\Phi(\bm{X},[\bm{X}^{\prime}_{-i};\bm{x}^{\prime}_{i}],f_{\bm{ \omega}})-\Phi(\bm{X},[\bm{X}^{\prime}_{-i};\bm{x}^{\prime\prime}_{i}],f_{\bm{ \omega}})$ $$

Observe that the expression on the left is given by:

$$ $[f_{\bm{\omega}}(\bm{x}^{\prime}_{i})-f_{\bm{\omega}}(\bm{x}^{\prime\prime}_{i })]g^{+}(\bm{x}_{i})-[c(\bm{x}^{\prime}_{i},\bm{x}_{i})-c(\bm{x}^{\prime\prime }_{i},\bm{x}_{i})]-\sum_{j\neq i}{t(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{x}_{j}, \bm{x}^{\prime}_{j})-t(\bm{x}_{i},\bm{x}^{\prime\prime}_{i},\bm{x}_{j},\bm{x}^ {\prime}_{j})}$ $$

We claim this is equivalent to $\Phi(\bm{X},[\bm{X}^{\prime}_{-i};\bm{x}^{\prime}_{i}],f_{\bm{\omega}})-\Phi(
\bm{X},[\bm{X}^{\prime}_{-i};\bm{x}^{\prime\prime}_{i}],f_{\bm{\omega}})$. Since only $\bm{x}^{\prime}_{i}$ changes to $\bm{x}^{\prime\prime}_{i}$, terms involving gain and cost in the potential function difference match the above. Similarly, all externalities terms not involving $\bm{x}^{\prime}_{i}$ remain the same and only the externalities involving agent $i$ remain. There are exactly $k-1$ such terms and due to symmetry, this is equivalent to $\sum_{j\neq i}{t(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{x}_{j},\bm{x}^{\prime}_{j}
)-t(\bm{x}_{i},\bm{x}^{\prime\prime}_{i},\bm{x}_{j},\bm{x}^{\prime}_{j})}$.
∎

Since all player incentives map to the potential function, PNE strategies exactly correspond to local maxima of the potential function (Roughgarden, ).(^6^66In this setting, a local maxima refers to a point that is optimal with respect to changes in any one direction.) Indeed, if an agent could improve their utility by modifying their action, the value of the potential function at this updated action also increases. This has several implications. First, finding an equilibrium is equivalent to finding such local maxima, and second, properties of local maxima of $\Phi$ directly inform the multiplicity/uniqueness of 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 a simple local algorithm for arriving at a PNE.

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 is unique, and the PNE must be at this optimum (Neyman, ). Correspondingly, the Nash Equilibrium is unique and can be written as the outcome of a convex optimization problem(^7^77Since we are maximizing a concave objective under convex constraints, this is a convex optimization problem.). We present this formally below:

###### Theorem 2 .

Under Conditions 1, 2 and 3 the potential function specified in Theorem 1 is strictly concave. Further, the Nash Equilibrium is unique and given by $\operatorname*{arg\,max}_{\bm{X}^{\prime}\in[0,1]^{k\times d}}{\Phi(\bm{X},\bm
{X}^{\prime},f_{\bm{\omega}}).}$

###### Proof.

Due to the pairwise symmetry condition, $\sum_{i=1}^{k}T(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{X},\bm{X}^{\prime})=2\sum_{
i=1}^{k}\sum_{j>i}{t(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{x}_{j},\bm{x}^{\prime}
_{j})}$. Hence if each $T(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{X},\bm{X}^{\prime})$ is convex, then $\sum_{i=1}^{k}\sum_{j>i}{t(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{x}_{j},\bm{x}^{
\prime}_{j})}$, the last term in the potential function, is also convex. Combined with the $\ell_{2}$ norm square cost, which is strictly convex, and $f_{\bm{\omega}}$ which is linear, it immediately follows that that the potential function is 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 two global optima $\bm{X}^{\prime},\bm{X}^{\prime\prime}$, with $\Phi(\bm{X},\bm{X}^{\prime},f_{\bm{\omega}})=\Phi(\bm{X},\bm{X}^{\prime\prime}
,f_{\bm{\omega}})=m$. Then strict concavity implies: $\Phi(\bm{X},\lambda\bm{X}^{\prime}+(1-\lambda)\bm{X}^{\prime\prime},f_{\bm{
\omega}})>\lambda\Phi(\bm{X},\bm{X}^{\prime},f_{\bm{\omega}})+(1-\lambda)\Phi(
\bm{X},\bm{X}^{\prime\prime},f_{\bm{\omega}})=m$. Since the feasible region is convex, the points on the $\lambda\bm{X}^{\prime}+(1-\lambda)\bm{X}^{\prime\prime}$ are feasible and thus neither $\bm{X}^{\prime}$ or $\bm{X}^{\prime\prime}$ could be maximizers.
∎

This implies that $\text{NE}(\bm{X},f_{\bm{\omega}})$ is now a 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 a parameterized convex optimization problem (in terms of the classifier $f_{\bm{\omega}}$).

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 a weaker one:

- *1’.*
*$\sum_{i}{c(\bm{x}_{i},\bm{x}^{\prime}_{i})}+\sum_{i}\sum_{j>i}{t(\bm{x}_{i},
\bm{x}^{\prime}_{i},\bm{x}_{j},\bm{x}^{\prime}_{j})}$, is smooth and strictly convex*(^8^88By strict convexity, we mean the Hessian is positive definite.).

We denote this as the *cumulative impact of manipulation* — total cost and the sum of all combinations of externality. Due to our pairwise symmetry condition, $\sum_{i}\sum_{j>i}{t(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{x}_{j},\bm{x}^{\prime}
_{j})}=\tfrac{1}{2}\sum_{i=1}^{n}T(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{X},\bm{X
}^{\prime})$; since convexity is preserved through summation, for any strictly convex cost (i.e. Condition 1, $\ell_{2}$ norm squared cost) and any externality where $T(\bm{x}_{i},\bm{x}^{\prime}_{i},\bm{X},\bm{X}^{\prime})$ is convex (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 5.

###### Definition 2 .

###### Theorem 1 .

###### Proof.

###### Theorem 2 .

###### Proof.

## 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 a given year is not constant but rather a 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 $k_{max}$ denotes the largest number of simultaneous participants with $\mathcal{K}$, a distribution over $[k_{max}]$, and $\mathcal{D}$, the data distribution that we sample from, i.e., $(\bm{x}_{i},y_{i})\sim\mathcal{D}$. The learner has access to a training dataset of $n$ instances, where each instance involves a sample $k_{i}\sim\mathcal{K}$, and then $k_{i}$ independent samples from the distribution $\mathcal{D}$. Observe that the following is an equivalent sampling procedure: sample $k_{i}\sim\mathcal{K}$, draw $k_{max}$ independent samples from $\mathcal{D}$, and then only consider the first $k_{i}$ elements. We use this latter procedure for the generalization result; formally, we define a joint distribution

$$ $\mathfrak{D}=\underbrace{\mathcal{D}\times\dots\times\mathcal{D}}_{k_{max}} \times\mathcal{K}.$ $$

The learner has access to $n$ samples from this distribution, representing their training set: $\mathcal{S}=\{(\bm{X}_{1},\bm{y}_{1},k_{1}),\dots,(\bm{X}_{n},\bm{y}_{n},k_{n})\}$, where $\bm{X}_{i}\in\mathbb{R}^{k_{max}\times d}$, $\bm{y}_{i}\in\mathbb{R}^{k_{max}}$, and $k_{i}\in[k_{max}]$. Note that each sample/instance in this dataset can be seen as holding the attributes of $k_{i}$ individuals.

For any chosen classifier $f_{\bm{\omega}}$, the participating agents reach a PNE and the classifier suffers a resulting 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 as the classifier changes. Indeed, if the PNE drastically changes due to small changes in $\bm{\omega}$, learning can be challenging.

Let $\text{NE}(\bm{X},f_{\bm{\omega}},k):\mathbb{R}^{k_{max}\times d}\times\mathbb{
R}^{d}\times[k_{max}]\rightarrow\mathbb{R}^{k_{max}\times d}$, where the first $k$ rows of the output correspond to the equilibrium 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 $\bm{\omega}$. The theorem statement treats inputs to $\Phi$ and NE as vectors. This is without loss of generality since our $\bm{X}\in\mathbb{R}^{k_{max}\times d}$ feature matrix is equivalent to a $\bm{x}\in\mathbb{R}^{dk_{max}}$ vector, with the vector $\ell_{2}$ norm $||\bm{x}||_{2}$ equivalent to the matrix Frobenius norm $||\bm{X}||_{F}$.

###### Lemma 1 .

Let $\Phi(\bm{x},\bm{x}^{\prime},f_{\bm{\omega}})$ be the potential function for $k_{max}$ agents ($\bm{x},\bm{x}^{\prime}\in\mathbb{R}^{dk_{max}}$). Then for $\eta=\tfrac{\gamma}{c}$, where $c=\tfrac{1}{2}\min_{\bm{x}^{\prime},\bm{\omega}}(\lambda_{min}(\nabla^{2}_{\bm
{x}^{\prime}}\Phi(\bm{x},\bm{x}^{\prime},f_{\bm{\omega}})))$ and $\gamma=\max_{\bm{x}^{\prime},\bm{\omega}}{||\nabla^{2}_{\bm{\omega}\bm{x}^{
\prime}}\Phi(\bm{x},\bm{x}^{\prime},f_{\bm{\omega}})||}+1$, the function $\text{NE}(\bm{x},f_{\bm{\omega}},k)$ is $\eta$-Lipschitz in $\bm{\omega}$ (under the $||\cdot||_{2}$ norm) for any $k$.

The proof (deferred to the Appendix) 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 $\bm{x}^{\prime}$ and $\bm{\omega}$ along with the insights above to establish the Lipschitz-ness of the maximizer of $\Phi$. To relate this to $\text{NE}(\bm{X},f_{\bm{\omega}},k)$, we define the optimization objective as summing the potential function over only the first $k$ participants with a trivial function involving the remaining agents.

Next, for a loss function $\ell(f_{\bm{\omega}}(\bm{x}_{i}),y_{i})$ defined on classifying an individual’s reported features, the average loss on a sample consisting of $k$ participating strategic agents is given by $L(\bm{X},\bm{y},f_{\omega},k)=\tfrac{1}{k}\sum_{i=1}^{k}{\ell(f_{\bm{\omega}}(
\text{NE}(\bm{X},f_{\bm{\omega}},k)_{i:}),y_{i})}$(^9^99The notation $\text{NE}(\bm{X},f_{\bm{\omega}})_{i:}$ denotes the equilibrium report of the $i^{th}$ agent.). We now define the standard learning theory notions using this:

###### Definition 3 .

For a classifier $f_{\bm{\omega}}$, the *true risk* $R(f_{\omega})$ on distribution $\mathfrak{D}$ and the empirical risk $\hat{R}(f_{\omega})$ on a dataset $\mathcal{S}$ consisting of $n$ independent samples from $\mathfrak{D}$ is given respectively by:

$$ $R(f_{\omega})=\mathbb{E}_{(\bm{X},\bm{y},k)\sim\mathfrak{D}}{L(\bm{X},\bm{y},f _{\omega},k)}\quad\text{and}\quad\hat{R}(f_{\omega})=\frac{1}{n}\sum_{i=1}^{n} {L(\bm{X}_{i},\bm{y}_{i},f_{\omega},k_{i})}.$ $$

We want to show that a classifier chosen to minimize the risk on a finite dataset $\mathcal{S}$, denoted by $\hat{f_{\bm{\omega}}}$, will be close in a PAC sense, to the true risk minimizer of the population, denoted by $f_{\bm{\omega}}^{*}$. Recall that we focus on linear classifiers and as such, our function class is the set of norm-constrained linear functions: $\{\langle\bm{\omega},\bm{x}_{i}\rangle\text{ s.t. }||\bm{\omega}||\leq r\}$. We denote $\Omega=\{\bm{\omega}\text{ s.t. }||\bm{\omega}||_{2}\leq r\}$ as the corresponding parameter space. We now give our generalization guarantee below. To sketch the proof, it notes that the average loss on the sample $(\bm{X},\bm{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 $k_{max}$ (due mainly to the sample loss being scaled by the number of participants $\tfrac{1}{k}$) it does depend on the Lipschitz constant $\eta$. This constant is defined with respect to the potential function over the maximum number of $k_{max}$ participants (see Lemma 1). Sample complexity, thus, has an implicit dependence on $k_{max}$.

###### Theorem 3 .

For any $\lambda$-Lipschitz loss function $\ell$, linear function class parametrized by $\Omega=\{\bm{\omega}\text{ s.t. }||\bm{\omega}||_{2}\leq r\}$, agent dynamics captured by a strictly concave potential function $\Phi(\bm{x},\bm{x}^{\prime},f_{\bm{\omega}})$, and any $\varepsilon>0$ and $\delta>0$:

$$ $\displaystyle n\geq\frac{8}{\varepsilon^{2}}\ln\left(\frac{e}{\gamma}\right)+d \ln\left(\frac{16(\lambda(d+\eta r)\gamma}{\varepsilon}\right)\implies \operatorname{\mathbb{P}}\left({|R(\hat{f_{\bm{\omega}}})-R(f_{\bm{\omega}}^{* })|}\geq\varepsilon\right)\leq\delta$ $$

where $\eta$ is the Lipschitz constant from Lemma 1.

###### Proof.

Let $\mathcal{S}=\{(k_{1},\bm{X}_{1},\bm{y}_{1}),\dots,(k_{n},\bm{X}_{n},\bm{y}_{n})\}$ be the training set where $\bm{X}_{i}\in\mathbb{R}^{k_{max}\times d}$ and $\bm{y}_{i}\in\mathbb{R}^{k_{max}}$. Let $L(\bm{X}_{i},\bm{y}_{i},f_{\omega},k_{i})$ denote the loss on the $i$-th sample, where $L(\bm{X}_{i},\bm{y}_{i},f_{\omega},k_{i})=\frac{1}{k_{i}}\sum_{j=1}^{k_{i}}{
\ell(f_{\omega}(\text{NE}(\bm{X}_{i},f_{\bm{\omega}},k_{i})_{j:}),y_{ij})}$. Note that the following holds where the expectation is over samples from $\mathfrak{D}$:

$$ $\hat{R}(f_{\bm{\omega}})=\frac{1}{n}\sum_{i=1}^{n}{L(\bm{X}_{i},\bm{y}_{i},f_{ \omega},k_{i})}\quad\mathbb{E}[\hat{R}(f_{\bm{\omega}})]=\frac{1}{n}\sum_{i=1} ^{n}\mathbb{E}[L(\bm{X},\bm{y},f_{\omega},k)]=R(f_{\bm{\omega}})$ (1) $$

Our goal is to show the following generalization: $|R(\hat{f_{\bm{\omega}}})-R(f_{\bm{\omega}}^{*})|\geq\varepsilon$ with low probability. To that end, we use the fact that uniform convergence implies generalization. Formally:

$$ $R(\hat{f_{\bm{\omega}}})-R(f_{\bm{\omega}}^{*})\leq|\hat{R}(\hat{f_{\bm{\omega }}})-R(\hat{f_{\bm{\omega}}})|+|\hat{R}(f_{\bm{\omega}}^{*})-R(f_{\bm{\omega}} ^{*})|\leq 2\sup_{f_{\bm{\omega}}\in\mathcal{F}}|\hat{R}(f_{\bm{\omega}})-R(f_ {\bm{\omega}})|$ (2) $$

where the second inequality follows from the triangle inequality and that $\hat{R}(\hat{f_{\bm{\omega}}})-R(\hat{f_{\bm{\omega}}})\leq 0$. Since the function space is continuous, we will fix a $\zeta$-cover $\mathcal{N}^{\zeta}_{\bm{\omega}}$ of the parameter space $\Omega$. That is, for any $\bm{\omega}\in\Omega$, there exists a $\bm{\omega}^{\prime}\in\mathcal{N}^{\zeta}_{\bm{\omega}}$ such that $||\bm{\omega}-\bm{\omega}^{\prime}||\leq\zeta$. Since our parameter space is $d$ dimensional ball of norm $r$, it is well known that such a covering can be achieved with $|\mathcal{N}^{\zeta}_{\bm{\omega}}|\leq\left(\frac{2r\sqrt{d}}{\zeta}\right)^{d}$. For a sample $i$ in our dataset, let $\bm{z}_{i}$ denote the vector of scores received. That is, $z_{ij}=\langle\text{NE}(\bm{X}_{i},f_{\bm{\omega}},k_{i})_{j:},\bm{\omega}\rangle$, and let $z^{\prime}_{ij}$ denote the score on this sample when classifier $f_{\bm{\omega}^{\prime}}$ is used. Since our loss function $\ell$ is $\lambda$-Lipschitz in the score $z_{ij}$, we have that:

$$ $\displaystyle|L(\bm{X}_{i},\bm{y}_{i},f_{\bm{\omega}},k_{i})-L(\bm{X}_{i},\bm{ y}_{i},f_{\bm{\omega}^{\prime}},k_{i})|=\left|\frac{1}{k_{i}}\sum_{j=1}^{k_{i} }{\ell(z_{ij},y_{ij})-\ell(z^{\prime}_{ij},y_{ij})}\right|\leq\frac{\lambda}{k _{i}}||\bm{z_{i}}-\bm{z^{\prime}_{i}}||_{1}$ $$

Next, by making use of the triangle inequality, we have the following:

$$ $\displaystyle\frac{\lambda}{k_{i}}||\bm{z_{i}}-\bm{z^{\prime}_{i}}||_{1}$ $\displaystyle=\frac{\lambda}{k_{i}}\sum_{j=1}^{k_{i}}{|\langle\text{NE}(\bm{X} _{i},f_{\bm{\omega}},k_{i})_{j:},\bm{\omega}\rangle-\langle\text{NE}(\bm{X}_{i },f_{\bm{\omega}^{\prime}},k_{i})_{j:},\bm{\omega}^{\prime}\rangle|}$ $\displaystyle=$ $\displaystyle\frac{\lambda}{k_{i}}\sum_{j=1}^{k_{i}}{|\langle\text{NE}(\bm{X}_ {i},f_{\bm{\omega}^{\prime}},k_{i})_{j:},\bm{\omega}\rangle+\langle\text{NE}( \bm{X}_{i},f_{\bm{\omega}},k_{i})_{j:}-\text{NE}(\bm{X}_{i},f_{\bm{\omega}^{ \prime}},k_{i})_{j:},\bm{\omega}\rangle-\langle\text{NE}(\bm{X}_{i},f_{\bm{ \omega}^{\prime}},k_{i})_{j:},\bm{\omega}^{\prime}\rangle|}$ $\displaystyle\leq$ $\displaystyle\frac{\lambda}{k_{i}}\sum_{j=1}^{k_{i}}{|\langle\text{NE}(\bm{X}_ {i},f_{\bm{\omega}^{\prime}},k_{i})_{j:},(\bm{\omega}-\bm{\omega}^{\prime}) \rangle|+|\langle\text{NE}(\bm{X}_{i},f_{\bm{\omega}},k_{i})_{j:}-\text{NE}( \bm{X}_{i},f_{\bm{\omega}^{\prime}},k_{i})_{j:},\bm{\omega}\rangle|}$ $\displaystyle\leq$ $\displaystyle\frac{\lambda}{k_{i}}\sum_{j=1}^{k_{i}}{||\text{NE}(\bm{X}_{i},f_ {\bm{\omega}^{\prime}},k_{i})_{j:}||_{1}\cdot||(\bm{\omega}-\bm{\omega}^{ \prime})||_{1}}+\frac{\lambda}{k_{i}}\sum_{j=1}^{k_{i}}{|\langle\text{NE}(\bm{ X}_{i},f_{\bm{\omega}},k_{i})_{j:}-\text{NE}(\bm{X}_{i},f_{\bm{\omega}^{\prime }},k_{i})_{j:},\bm{\omega}\rangle|}$ $\displaystyle\leq$ $\displaystyle\lambda d||(\bm{\omega}-\bm{\omega}^{\prime})||_{1}+\frac{\lambda }{k_{i}}{||(\text{NE}(\bm{X}_{i},f_{\bm{\omega}},k_{i})-\text{NE}(\bm{X}_{i},f _{\bm{\omega}^{\prime}},k_{i}))\bm{\omega}||_{1}}$ $$

where the last inequality follows from the assumption that the feature vectors are bounded in the region $[0,1]^{d}$. Next, we make use of the following 3 relations that hold for any matrix $\bm{V}$ and vector $\bm{\omega}\in\mathbb{R}^{d}$: (1) $||\bm{\omega}||_{2}\leq||\bm{\omega}||_{1}\leq\sqrt{d}||\bm{\omega}||_{2}$, (2) submultiplicavity of matrix norms $||V\bm{\omega}||_{2}\leq||V||||\bm{\omega}||_{2}$ and (3) $||V||_{2}\leq||V||_{F}$, where $||V||_{F}$ denotes the matrix Frobenius norm:

$$ $\displaystyle||(\text{NE}(\bm{X}_{i},f_{\bm{\omega}},k_{i})-\text{NE}(\bm{X}_{ i},f_{\bm{\omega}^{\prime}},k_{i}))\bm{\omega}||_{1}\leq$ $\displaystyle\sqrt{k_{i}}||(\text{NE}(\bm{X}_{i},f_{\bm{\omega}},k_{i})-\text{ NE}(\bm{X}_{i},f_{\bm{\omega}^{\prime}},k_{i}))\bm{\omega}||_{1}$ $\displaystyle\leq$ $\displaystyle\sqrt{k_{i}}||(\text{NE}(\bm{X}_{i},f_{\bm{\omega}},k_{i})-\text{ NE}(\bm{X}_{i},f_{\bm{\omega}^{\prime}},k_{i}))||_{F}||\bm{\omega}||_{2}$ $\displaystyle\leq$ $\displaystyle r\sqrt{k_{i}}||(\text{NE}(\bm{X}_{i},f_{\bm{\omega}},k_{i})- \text{NE}(\bm{X}_{i},f_{\bm{\omega}^{\prime}},k_{i}))||_{F}$ $$

Next, we appeal to theorem 1 which establishes the $\eta-$Lipschitz continuity of the NE function in $\bm{\omega}$ under the $||\cdot||_{F}$ norm to state the following:

$$ $\displaystyle r\sqrt{k_{i}}||(\text{NE}(\bm{X}_{i},f_{\bm{\omega}},k_{i})- \text{NE}(\bm{X}_{i},f_{\bm{\omega}^{\prime}},k_{i}))||_{F}\leq$ $\displaystyle\eta r\sqrt{k_{i}}||\bm{\omega}-\bm{\omega}^{\prime}||_{1}$ $$

Thus in combining the results here, we can state the following, where the last inequality follows from the definition of a $\gamma$ covering:

$$ $|L(\bm{X}_{i},\bm{y}_{i},f_{\omega},k_{i})-L(\bm{X}_{i},\bm{y}_{i},f_{\omega^{ \prime}},k_{i})|\leq\lambda d||\bm{\omega}-\bm{\omega}^{\prime}||_{1}+\frac{ \lambda}{k_{i}}\eta r\sqrt{k_{i}}||\bm{\omega}-\bm{\omega}^{\prime}||_{1}\leq \lambda(d+\eta r)\gamma$ $$

This essentially bounds the change in empirical and true risk due to using classifier parameters from using parameters in the finite covering $\mathcal{N}^{\zeta}_{\bm{\omega}}$. Formally, we expand Equation 2 to state the following ($\bm{\omega}^{\prime}$ is the closest element in $\mathcal{N}^{\zeta}_{\bm{\omega}}$ to $\bm{\omega}$):

$$ $\displaystyle\sup_{\bm{\omega}\in\Omega}|R(f_{\bm{\omega}})-\hat{R}(f_{\bm{ \omega}})|=$ $\displaystyle\sup_{\bm{\omega}\in\Omega}|R(f_{\bm{\omega}^{\prime}})-\hat{R}(f _{\bm{\omega}^{\prime}})+R(f_{\bm{\omega}})-R(f_{\bm{\omega}^{\prime}})+\hat{R }(f_{\bm{\omega}^{\prime}})-\hat{R}(f_{\bm{\omega}})|$ $\displaystyle\leq$ $\displaystyle\max_{\bm{\omega}^{\prime}\in\mathcal{N}^{\zeta}_{\bm{\omega}}}|R (f_{\bm{\omega}^{\prime}})-\hat{R}(f_{\bm{\omega}^{\prime}})|+2\lambda(d+\eta r )\gamma.$ $$

By choosing $\zeta=\frac{\varepsilon}{8\lambda(d+\eta r)\gamma}$, we get that

$$ $\operatorname{\mathbb{P}}\left(\sup_{\bm{\omega}\in\Omega}|R(f_{\bm{\omega}})- \hat{R}(f_{\bm{\omega}})|\geq\tfrac{\varepsilon}{2}\right)\leq\operatorname{ \mathbb{P}}\left(\max_{\bm{\omega}^{\prime}\in\mathcal{N}^{\zeta}_{\bm{\omega} }}|R(f_{\bm{\omega}^{\prime}})-\hat{R}(f_{\bm{\omega}^{\prime}})|\geq\tfrac{ \varepsilon}{4}\right)$ $$

Lastly, we can apply Hoeffding’s inequality due to Equation 1 and using union bound over $\mathcal{N}^{\delta}_{\omega}$ at the right-hand side of the inequality above, we have that

$$ $\displaystyle\operatorname{\mathbb{P}}\left(\max_{\bm{\omega}^{\prime}\in \mathcal{N}^{\zeta}_{\bm{\omega}}}|R(f_{\bm{\omega}^{\prime}})-\hat{R}(f_{\bm{ \omega}^{\prime}})||\geq\tfrac{\varepsilon}{4}\right)$ $\displaystyle\leq 2|\mathcal{N}^{\zeta}_{\bm{\omega}}|\exp{\left(\frac{-n \varepsilon^{2}}{8}\right)}$ $\displaystyle\leq 2\left(\frac{16\lambda(d+\eta r)\gamma}{\varepsilon}\right)^ {d}\exp{\left(\frac{-n\varepsilon^{2}}{8}\right)}$ $$

and the theorem follows by choosing $n$ accordingly.
∎

###### Lemma 1 .

###### Definition 3 .

###### Theorem 3 .

###### Proof.

### 4.1 Minimizing Empirial Risk

While we have shown PAC learning is possible in our multi-agent strategic classification game, a cornerstone of learning is minimizing the empirical risk; that is, finding a classifier that minimizes loss incurred on the training set $\mathcal{S}$. Even for a convex loss function $\ell$ and linear classifier $f_{\omega}$, minimizing this across the samples of $\mathcal{S}$ is non-trivial since the NE function is the solution to an optimization problem. In general, there is no closed-form expression for the NE function and we cannot hope for this loss minimization problem to be convex.

Machine learning nonetheless has a vast literature on optimizing nonconvex loss functions; these, however, are largely gradient-based and require computing the loss gradient with respect to the learning parameter $\bm{\omega}$.
This loss is computed with respect to the equilibrium outcome/score of a participating agent $i$: $f_{\bm{\omega}}(\text{NE}(\bm{X},f_{\bm{\omega}})_{i:})$(^10^1010Since we are concerned with the loss on a sample, we assume $k=k_{max}$ and drop the dependence on $k$.). When $f_{\bm{\omega}}$ is linear, this is simply $\langle\text{NE}(\bm{X},f_{\bm{\omega}})_{i:},\bm{\omega}\rangle$. We now show when and how this gradient can be explicitly computed.

Let $v_{i}=\text{NE}(\bm{X},f_{\bm{\omega}})_{i:}$ and $z_{i}=f_{\bm{\omega}}(\text{NE}(\bm{X},f_{\bm{\omega}})_{i:})=f(v_{i},\bm{
\omega})$ for $i\in[k]$, noting that $z_{i}\in\mathbb{R}$ and $v_{i}\in\mathbb{R}^{d}$. The loss gradient is given as follows:

$$ $\displaystyle\nabla_{\bm{\omega}}L(\bm{x},\bm{y},f_{\bm{\omega}})=\frac{1}{k} \sum_{i=1}^{k}{\nabla_{\bm{\omega}}\ell(f(\text{NE}(\bm{X},f_{\bm{\omega}})_{i :},\bm{\omega}),y_{i})}=\frac{1}{k}\sum_{i=1}^{k}{\nabla_{\bm{\omega}}\ell(z_{ i},y_{i})}=\frac{1}{k}\sum_{i=1}^{k}{\frac{\partial\ell}{\partial z_{i}}\nabla _{\bm{\omega}}z_{i}}$ $\displaystyle=\frac{1}{k}\sum_{i=1}^{k}{\frac{\partial\ell}{\partial z_{i}} \left[\nabla_{v_{i}}^{T}f\mathcal{J}_{\bm{\omega}}(\text{NE}(\bm{x},f_{\bm{ \omega}})_{i:})+\nabla_{\bm{\omega}}f\right]}$ $$

We use the chain rule here, with $\mathcal{J}_{\bm{\omega}}$ representing the Jacobian with respect to $\bm{\omega}$. $\frac{\partial\ell}{\partial z_{i}}$ is the derivative of the loss with respect to the score, a feature of the loss function. Further, the gradients $\nabla_{v_{i}}^{T}f$ and $\nabla_{\bm{\omega}}f$ depend only on the function class we are learning. Indeed, for a linear function class, the desired gradient is given by:

$$ $\nabla_{\bm{\omega}}L(\bm{x},\bm{y},f_{\bm{\omega}})=\frac{1}{k}\sum_{i=1}^{k} {\frac{\partial\ell}{\partial z_{i}}\left[\bm{\omega}^{T}\mathcal{J}_{\bm{ \omega}}(\text{NE}(\bm{x},f_{\bm{\omega}})_{i:})+\text{NE}(\bm{x},f_{\bm{ \omega}})_{i:}\right]}$ (3) $$

The remaining and crucial term is the Jacobian of the outcome of the PNE optimizer with respect to the weights: $\mathcal{J}_{\bm{\omega}}(\text{NE}(\bm{x},f_{\bm{\omega}})_{i:})$. The theorem below proves exactly when this Jacobian exists, and explicitly characterizes it. Once again, for ease of exposition we interpret the input and output of the NE function as a vector. To sketch the key ideas, we introduce primal and dual slack variables to capture the KKT conditions 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, we can use the implicit function theorem to compute the gradient explicitly. With this hand, the learner is free to use standard gradient descent based algorithms to solve the empirical risk minimization problem.

###### Theorem 4 .

For $\mathrm{NE}(\bm{x},f_{\bm{\omega}})=\operatorname*{arg\,max}_{\bm{x}^{\prime}
\in[0,1]^{kd}}{\Phi(\bm{x}^{\prime},\bm{x},f_{\bm{\omega}})}$ where $\Phi$ is strictly concave and smooth, let $\bm{\lambda}$ and $\bm{\mu}$ denote the dual variables corresponding to the upper and lower bound constraints. Then $\bm{x}^{*}(\bm{\omega})=\text{NE}(\bm{x},f_{\bm{\omega}})$ is differentiable with respect to $\bm{\omega}$ everywhere except possibly if there exists an $x^{*}_{i}(\bm{\omega})\in\{0,1\}$ with the corresponding dual variable set to 0; i.e., if there exists $i$ such that $\left(x^{*}_{i}(\bm{\omega})=1\wedge\lambda_{i}^{*}=0\right)\vee\left(x^{*}_{i
}(\bm{\omega})=0\wedge\mu_{i}^{*}=0\right)$.

###### Proof.

Note that NE is the solution to a strictly convex optimization problem. Let $z=kd$. We express the Lagrangian of this problem as follows, with the $\bm{\lambda}\in\mathbb{R}^{z}$ denoting the dual variables for the upper bound constraint and $\bm{\mu}\in\mathbb{R}^{z}$, the duals for the lower bound (recall our feasible region is a box $[0,1]^{z})$:

$$ $\mathcal{L}(\bm{x}^{\prime},\bm{\lambda},\bm{\mu},\bm{\omega};\bm{x})=\Phi(\bm {x}^{\prime},\bm{x},f_{\bm{\omega}})-\sum_{i=1}^{z}{\lambda_{i}(x^{\prime}_{i} -1)}+\sum_{i=1}^{z}{\mu_{i}x^{\prime}_{i}}$ $$

Since our 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 sufficient and necessary for the optimal solution $\bm{x}^{*}=\text{NE}(\bm{x},\bm{\omega})$. Since the constraints are affine, in non-concave setting, the KKT conditions are necessary at a local optimum. Define vectors $\bm{s}_{x+}\in\mathbb{R}^{z},\bm{s}_{x-}\in\mathbb{R}^{z},\bm{s}_{\lambda}\in
\mathbb{R}^{z},\bm{s}_{\mu}\in\mathbb{R}^{z}$ which will be used to denote the primal and dual slacks. We now define the following implicit function $G(\cdot):\mathbb{R}^{7z\times d}\rightarrow\mathbb{R}^{7z}$:

$$ $G(\bm{x}^{\prime},\bm{\lambda},\bm{\mu},\bm{s}_{x+},\bm{s}_{x-},\bm{s}_{ \lambda},\bm{s}_{\mu},\bm{\omega})=\begin{bmatrix}\nabla_{\bm{x}^{\prime}}{ \mathcal{L}(\bm{x}^{\prime},\bm{\lambda},\bm{\mu},\bm{\omega};\bm{x})}\\ x^{\prime}_{i}-1+{s^{2}_{x+,i}}\,\,\,\forall i\in[m]\\ x^{\prime}_{i}-{s^{2}_{x-,i}}\,\,\,\forall i\in[m]\\ \text{diag}(\bm{\lambda})(1-\bm{x}^{\prime})\\ \text{diag}(\bm{\mu})(\bm{x}^{\prime})\\ \lambda_{i}-s^{2}_{\lambda,i}\,\,\,\forall i\in[m]\\ \mu_{i}-s^{2}_{\mu,i}\,\,\,\forall i\in[m]\end{bmatrix}$ $$

Let $G(\cdot)=\bm{0}$. Under this implicit equation, the first row of equations corresponds to the KKT stationarity conditions. The second two rows of equations enforce each $x^{\prime}_{i}$ is less than $1$ and greater than 0 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 are positive, the KKT dual feasibility condition. Thus, when $G(\cdot)=\bm{0}$, it means the KKT conditions are satisfied, and with a concave objective this also implies the solution is optimal. Similarly, for any optimal $\bm{X}^{*},\bm{\lambda}^{*},\bm{\mu}^{*}$, since it is feasible, we can always find the corresponding slacks so as to satisfy $G(\cdot)=0$. Therefore, solutions to this implicit equation fully characterizes the optimal solution.

Let $\bm{p}=(\bm{x}^{\prime},\bm{\lambda},\bm{\mu},\bm{s}_{x},\bm{s}_{\lambda},\bm{
s}_{\mu})$ and we can simplify our equation to $G(\bm{p},\bm{\omega})=0$. Any $\bm{p}$ that satisfies this is the optimal solution for $\bm{\omega}$. We aim to use the Implicit Function Theorem and to that end, we first compute the Jacobian $\mathcal{J}_{\bm{z}}(G)$ as follows (the columns represent the derivative with respect to $\bm{x}^{\prime},\bm{\lambda},\bm{\mu},\bm{s}_{x+},\bm{s}_{x-},\bm{s}_{\lambda}
,\bm{s}_{\mu}$):

$$ $\displaystyle\mathcal{J}_{\bm{z}}(G)=\begin{bmatrix}\nabla^{2}_{\bm{x}^{\prime }}{\Phi(\bm{x}^{\prime},\bm{x},f_{\bm{\omega}})}&\bm{-I}&\bm{I}&\bm{0}&\bm{0}& \bm{0}&\bm{0}\\ \bm{I}&\bm{0}&\bm{0}&\text{diag}(2)\bm{s}_{x+}&\bm{0}&\bm{0}&\bm{0}\\ \bm{I}&\bm{0}&\bm{0}&\bm{0}&\text{diag}(-2)\bm{s}_{x-}&\bm{0}&\bm{0}\\ \text{diag}(\bm{\lambda})&\bm{I}\bm{x}&\bm{0}&\bm{0}&\bm{0}&\bm{0}&\bm{0}\\ -\text{diag}(\bm{\mu})&\bm{0}&-\bm{I}\bm{x}&\bm{0}&\bm{0}&\bm{0}&\bm{0}\\ \bm{0}&\bm{I}&\bm{0}&\bm{0}&\bm{0}&\text{diag}(-2)\bm{s}_{\lambda}&\bm{0}\\ \bm{0}&\bm{0}&\bm{I}&\bm{0}&\bm{0}&\bm{0}&\text{diag}(-2)\bm{s}_{\mu}\\ \end{bmatrix}$ $$

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. A constraint $i$ is active if $x^{*}_{i}\in\{0,1\}$. Under the KKT conditions, the Lagrange multiplier for inactive constraints must be 0. Let $\mathcal{I}\subseteq[2m]$ denote a set of active constraints. Let $\mathcal{I}(\bm{\omega})=\left\{i|x^{*}_{i}(\bm{\omega})=0\right\}\cup\left\{i
+m|x^{*}_{i}(\bm{\omega})=1\right\}$. We define the inverse mapping $\bm{\omega}(\mathcal{I})$ as follows: $\bm{\omega}(\mathcal{I})=\{\bm{\omega}\in\bm{\Omega}|I(\bm{\omega})=\mathcal{I}\}$. It is immediate that the set $\{\bm{\omega}(\mathcal{I})\,\,\forall\mathcal{I}\in[2m]\}$ is a partition of the parameter space $\bm{\Omega}$.

Fix an $\mathcal{I}$ and without loss of generality, let $i$ constraints from $\bm{\lambda}$ and $j$ constraints from $\bm{\mu}$ be active. Then for $\bm{\omega}\in\bm{\omega}(\mathcal{I})$, it suffices to consider $\bm{\lambda}_{i}\in\mathbb{R}^{i}$ and $\bm{\mu}_{j}\in\mathbb{R}^{j}$ - 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 $\bm{\omega}\in\bm{\omega}(\mathcal{I})$ we can simplify the general function $G$ to a function $G^{\prime}:\mathbb{R}^{3m+i+j}\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{3m+i+j}$ 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 (otherwise those constraints would be active). Hence the columns corresponding to those are also independent. Thus, if the dual slacks for the active constraints are non-zero, then the Jacobian for $G^{\prime}$ has full rank. This allows us to apply the implicit function theorem and state the following:

$$ $\mathcal{J}_{\bm{\omega}}(\text{NE}(\bm{x},f_{\bm{\omega}}))\triangleq\frac{ \partial\text{NE}(\bm{x},f_{\bm{\omega}})}{\partial\bm{\omega}}=\mathcal{J}^{- 1}_{\bm{p}}(G^{\prime}(\bm{p},\bm{\omega}))\mathcal{J}_{\bm{\omega}}(G^{\prime }(\bm{p},\bm{\omega}))$ $$

If however some of these dual slacks are zero, then it suggests that some of these constraints are redundant and the Jacobian of $G^{\prime}$ may not be invertible. This is formally equivalent to:

$$ $\exists\,i\,|\left(x^{*}_{i}=1\wedge\lambda_{i}^{*}=0\right)\vee\left(x^{*}_{i }=0\wedge\mu_{i}^{*}=0\right)$ $$

Indeed, this is a degenerate situation known as strict complementary failure (Nocedal & Wright, ) and represents the threshold or boundary of the $w(\mathcal{I})$ region where one set of constraints is becoming active and another inactive.
∎

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 are still necessary at local optima (Boyd & Vandenberghe, ). Since our approach relies on implicitly characterizing the KKT conditions, we can still use this to compute the derivative at local optima, provided we can find them effectively. Game-theoretically, this would correspond to local Nash Equilibrium (Balduzzi et al., ).

###### Theorem 4 .

###### Proof.

## 5 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. Section 3 concluded by noting a more general Condition ($1^{\prime}$) on the cost and externality to ensure this. This allows us 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 detection/audit due to others also manipulating. In 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, it is natural that one’s externality due to manipulation increases proportional to the extent to which others in the system also manipulate. We express the externality suffered by agent $i$ in such a setting as:

$$ $t(\bm{x}^{\prime}_{i},\bm{x}_{i},\bm{x}_{j},\bm{x}^{\prime}_{j})=\tfrac{\beta} {k-1}\sum_{\ell=1}^{d}{(x^{\prime}_{i\ell}-x_{i\ell})^{2}(x^{\prime}_{j\ell}-x _{j\ell})^{2}}$ $$

We scale by $k-1$ since each agent pays a single cost $c(\cdot)$ but suffers externality from $k-1$ agents; this allows $\alpha$ (the scale constant for the cost) and $\beta$ to be on the same scale. Next, observe that for individuals who do not manipulate, the total externality they incur is 0. This is 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 is pairwise symmetric and we show below that it satisfies the updated condition (proof in Appendix).

###### Proposition 1 .

Under the cost $c(\bm{x},\bm{x}^{\prime})=\alpha||\bm{x}-\bm{x}^{\prime}||_{2}^{2}$, the cumulative impact of manipulation under the proportional externality model is smooth and strictly convex for $\beta<\alpha$.

*Congestion Externality:* In many decision-making 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 et al., ). Naturally, an influx of applicants may report such intentions and initially move to these areas (with many reneging on this soon after and relocating(^11^1111The government of Canada which deploys such a policy, reported a 5 years retention rate of only 39% for the province of Prince Edward Island (Picot et al., ).)); this can significantly increase housing and living costs for new immigrants in these underpopulated communities. In such cases, individuals suffer from others manipulating even if they are being honest. Externalities of this nature can be modelled as follows:

$$ $\displaystyle t(\bm{x}^{\prime}_{i},\bm{x}_{i},\bm{x}_{j},\bm{x}^{\prime}_{j}) =\tfrac{\beta}{k-1}\sum_{\ell=1}^{d}{\exp(-(x^{\prime}_{i\ell}-x^{\prime}_{j \ell})^{2})}$ $$

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 is pairwise symmetric and satisfies our updated convexity condition (proof in Appendix).

###### Proposition 2 .

Under cost $c(\bm{x},\bm{x}^{\prime})=\alpha||\bm{x}-\bm{x}^{\prime}||_{2}^{2}$, the cumulative impact of manipulation under the congestion externality model is smooth and strictly convex for $\beta<\tfrac{\alpha}{\sqrt{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.

###### Proposition 1 .

###### Proposition 2 .

## 6 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 to 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 is 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-Nash 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.

A limitation of our work is the structural assumptions on externality. Their pairwise nature gives rise to a 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 guarantees, 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 learnability 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 multiple interactions. This closely parallels the literature on online strategic classification (Dong et al., ; Chen et al., ) and learning in games (Cesa-Bianchi & Lugosi, ). 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, ) in terms of a given classifier or simultaneously optimizing for welfare alongside robustness. Lastly, engaging with pertinent stakeholders to accurately capture real costs and externality and assess the implications of our model is an important future step. Our work lays the groundwork for such important questions, allowing us to comprehensively understand and mitigate the real challenges of classification in strategic multi-agent settings.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 4
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?

Line 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.
soundness: 3
strengths: I think the writing of the paper is fantastic!
Also, the problem formulation is interesting.
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.

They show:

Under some assumption the PNE of this game is unique and can be computed efficiently.

PAC learning results for the principal.

And they show ERM results through gradient-based methods.
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.?

---

confidence: 5
contribution: 3
initial_rating: 6
presentation: 4
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? 

- The authors did a good job surveying recent related work on strategic classification, but perhaps missed the following:
** 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.
** Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses, ICML 2022. This paper also accounts for causal effects in strategic classification.
soundness: 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. 

The 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.

These 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.
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:
- Under certain conditions, the agent manipulation game has a unique Pure Nash Equilibrium (PNE)
- The PNE can be efficiently computed under certain technical conditions
- A PAC learning guarantees for learning the optimal classifier
- Some characterization of the optimization problem for learning the classifier
- Two concrete externality models (that can be special cases of their general model): proportional externality and congestion externality.
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.

While 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.

---

confidence: 3
contribution: 4
initial_rating: 6
presentation: 3
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?

At 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?

“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.
The 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).
soundness: 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.

By 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.

The paper is well-written, with a lot of content and interesting theoretical results.
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). 

The paper brings externalities to the model, which means that one agent's manipulations can affect the outcomes or incentives of others.

The 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.
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.

More discussion could be provided on the social optimality of the equilibria studied in the paper, for the players as a whole.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Is it reasonable to assume each agent knows the full $\mathbf{X}$?
2. 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?
3. Given that you still have one page of space, could you provide at least one set of case studies?
soundness: 4
strengths: 1. Considering externalities in SC settings is well-motivated and the university admission example is quite natural. 
2. 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.
3. The technical parts seem to be solid and mostly make sense to me.
4. The paper is situated well in the previous literature. The discussion of [Eilat et al., 2023] is necessary.
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.
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.

> Assumptions:

1. 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. 

2. 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.

3. 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$.


> Experiments

While 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.

[1] Jagadeesan, Meena, Celestine Mendler-Dünner, and Moritz Hardt. "Alternative microfoundations for strategic classification." International Conference on Machine Learning. PMLR, 2021.

[2] Bechavod, Yahav, et al. "Information discrepancy in strategic learning." International Conference on Machine Learning. PMLR, 2022.

[3] Xie, Tian, and Xueru Zhang. "Non-linear Welfare-Aware Strategic Learning." arXiv preprint arXiv:2405.01810 (2024).

Meta-review: This paper examines the problem of strategic classification via a model where agents' feature manipulations can affect others, capturing inter-agent strategic externalities. The authors model the principal-agent interactions as a Stackelberg game and the agents' manipulation dynamics as a simultaneous game. They then show that, under certain assumptions, the pure Nash equilibrium of this agent manipulation game is unique and can be computed efficiently. Building on this, they establish PAC learning guarantees, indicating that classifiers can be learned to minimize loss even when agents manipulate their features to reach a pure Nash equilibrium.

Reviewers commended the paper’s novel approach to incorporating inter-agent externalities in strategic classification, noting its potential to enhance the realism and applicability of models in this domain. The reviewers appreciated in particular the authors' equilibrium uniqueness and computation results. Some concerns were raised regarding the practicality of the proposed methods and the assumptions underlying the authors' model but, for the most part, these were addressed by the authors' rebuttal. In view of all this, the consensus among reviewers was that the paper provides a solid contribution to the problem of strategic classification, and unanimously recommended acceptance.

Decision: Accept (Poster)