Strategic Classification With Externalities

We thank the reviewer for their helpful suggestions and feedback. We appreciate that they found our problem well-motivated and our technical contributions solid. In the responses, we address their comments in detail, and hope our clarifications will further improve the appreciation of our work.

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 X. Is this realistic in practice and how can each agent know the full X matrix?

You are correct that we assume a complete information setting in our model; our solution concept for the classifier induced game is a Pure Nash Equilibrium (PNE) which is only well-defined for complete information settings since the agent needs to evaluate their best-response for them to verify an equilibrium. In settings such as multiple students from a high-school are applying to the same university, complete information may be reasonable.

Nonetheless, you rightly point out that in other scenarios, an agent may not exactly know the features of others (which is needed to compute externality). We can consider then a variant of our model, where each agent $i$ has some estimate $\hat{X_{-i}}$ about the features of the remaining agents, with $X_{-i} = \hat{X_{-i}} + b_i$, with $b_i$ 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 on this. It can be shown that the complete information PNE strategy that we compute is $\varepsilon$ optimal for any agent $i$ under their biased utility estimate, where $\varepsilon$ depends on $b$. In other words, at the complete information PNE strategy, no agent believes they can increase their utility (computed using $\hat{X_{-i}}$) by more than $\varepsilon$.

Appendix A of the updated manuscript contains a formal treatment of this setting, cites the relevant literature mentioned in the review, and formally proves the result above, showing $\varepsilon$ to linearly depend on the bias $b_i$. We think it's an interesting observation, bridging the complete information setting to one where agents have biased/erroneous information; thank you for suggesting this. Future work should further explores this direction of uncertainty and incomplete information; incorporating beliefs and Bayesian perspectives here can also be insightful.

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$ Could you elaborate more on the externality function in the admission example? Specifically, why the agents who do not manipulate will not impose externality on other agents who manipulate?

In the proportional externality model, it is helpful to think of the cost $c(\cdot)$ as the intrinsic effort/risk in manipulating (i.e. changing your features and the risk of getting caught as part of a routine random audit), and externality $e(\cdot)$ as the extrinsic risk in manipulating (i.e. the principal initiating a widescale audit due to systematic manipulation). A non-manipulating agent has nothing to fear on either counts. If an agent does manipulate, their intristic cost/risk is independent of what everyone else does. But their extrinsic cost $e(\cdot)$ depends on what others have done. If very few manipulate, then the principal will not suspect any major loss of integrity, and unlikely to initiate a widespread audit; this implies the manipulating agent suffers minimal externality despite misreporting.

The two-agent case the review pointed out is essentially a limiting case of this phenomena. The agent $i$ who does not manipulate suffers naturally suffers neither cost nor externality. The manipulating agent $j$ still suffers a cost due to manipulating. However, in this model, they suffer no externality since there is no additional extrinsic risk in being caught/audited since the other party was honest.

Lastly, we note that our work is not beholden to this or any specific model of externality. This was an example that we think fits a certain setting. The paper also highlights other externality models (ex: congestion externality) where $j$ could suffer externality even if $i$ is honest.

We thank the reviewer for their insightful comments and questions. We are very glad they found strategic classification in multi-agent settings to be an important problem and commended our framework to capture this. We respond to their comments in detail below and hope it clarifies their questions:

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

We agree that there are scenarios wherein the externality suffered by an agent is global and cannot be factorized in a pairwise fashion. Interestingly, our model and all technical results also hold for a general type of global externality. For a set of reported values $X' = (x’_1, \dots, x'_k)$, let $T(X’,X)$ denote 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 to the combined actions of the whole. The agent-dynamic under such externality can be captured by a potential function, and when $T(X’, X)$ is convex and smooth, our whole suite of technical results on equilibrium and learning hold. We make note of this in the updated manuscript (line 235 and Appendix B) as it is an important flexibility of our work; thank you for mentioning it.

In general, there is a vast literature on modeling and capturing different forms of externality. We posit our work as laying the foundations for studying this phenomena in classification settings and consider it important for future work to extend it to wider class of externalities.

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?

We agree that considering coalitions of agents would be a very interesting and non-trivial extension of our model. One possible way to accommodate this is to model agents as having transferrable utilities (e.g. by introducing payments) and consider groups/coalitions of agents, where each group aims to maximize their collective utility. This would still allow for a PNE notion between the groups. However, the dynamic within each group needs to be modeled. Specifically, each group’s collective utility must be apportioned to its members in a fair way that incentivizes them to remain in the group. Concepts like Shapley Value from cooperative game theory will become relevant here. However, for most strategic classification applications (e.g. college admissions), we think it’s more reasonable to model agents as having non-transferrable utilities. Under a non-transferable utility model, then any stable coalitions have the same action profile as the PNE we characterized in our paper. We discuss these as exciting future directions in the updated manuscript (line 537).

“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)

This hints on some really interesting ideas. Indeed, inter-agent externalities can manifest in different ways. Our externality model intends to capture the externality imposed by the simultaneous actions of agents. It will also be very interesting to consider an online setting, as in the Strategic Apple Testing paper, where a decision maker interacts with agents sequentially. Then, early agents’ actions may impose an externality to a later agent through the change of the classification rule and/or the decision maker’s increasing or decreasing inspection. When agents have transferable utility, then notions like contracting may help restribute the impact of externalities. We hope that our work can inspire followup works on studying externality in strategic ML settings.

I thank the authors for the discussion which truly helped me to understand the concerns that I had about this paper. I believe that it is a great contribution to the field and I am happy to increase my rating accordingly.

We thank the reviewer for their constructive comments and feedback. We are glad they found our new model of strategic classification to be clean and filling a gap in the literature. We respond to their comments in detail below.

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?

While we consider our key contributions as proposing a new model of strategic classifcation that captures a crucial phenomena and settling the associated theoretical questions, we agree that adding experimental validation would further improve the manuscript. To that end, we have updated the manuscript (see Section 6) with a set of experiments on synthetic data that:

• Validate the learnability of cost and externality aware classifiers
• Ablate over the impact of the number of agents and the strength of cost and externality in agent utility
• Compare against two non-strategy aware baselines.

To breifly summarize the results, we train a linear classifier and compute agent utilities for the corresponding outcome using cost and externality functions discussed in the paper. During training, we sample a set of $k$ agents from the training set, compute their PNE given the current classifier, and use the equilibrium features to compute the classifier outcome and the corresponding loss, and update the classifier with gradient descent algorithms. Our experiments show the loss of this strategic training closely matches the validation loss, wherein agents are also classified based on their PNE outcomes.

We compare this against two baselines. One is where the classifier is trained with truthful data/no strategic considerations (Figure 1) and another where it is trained assuming the agents are strategic but only care about cost (Figure 2). The latter captures existing models of strategic classification. At validation these baseline models classify agents who misreport to PNE based on cost and externality. Naturally, we notice these baselines under-perform in validation when compared to our model above, trained with full strategy awareness. We notice the non-strategic baseline performs relatively better as the intensity of cost, externality increases (and misreporting becomes expensive) and as the number of agents increase. Conversely, the cost-only baseline performs worse as the intensity increases, likely because it overlooks the significant negative impacts of manipulation caused by externalities. This may lead to expecting a more severe manipulation compared to what actually occurs.

In general, the question of practical training and deployment of a model is important; we hope our results lead to more real world empirical analysis of strategic classification with externalities in diverse settings.

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?

Indeed, the fact that best response dynamics will converge to the Pure Nash Equilibrium is strength of our model. We highlight this in line 252 of the updated manuscript.

Regarding Related Works

Thank you for pointing out additional relevant literature. We include them in the related works section (Section 1.2) of the updated manuscript.

We thank the reviewer for their insightful comments and commending our problem formulation and model. We address their questions in detail below:

Do you think you can get tighter bounds using other techniques like Rademacher complexity etc.?

This is an excellent question and we did consider using a Rademacher complexity based approach. Indeed, it is possible to use a symmetrization argument to bound the generalization error in terms of the Rademacher Complexity. In our setting, however, the Rademachar complexity is of the function $f_{\omega}$ applied to the Nash Equilibrium outcome $\text{NE}(X, f_\omega,k)$ (which itself depends on $f_{\omega}$), and not directly on the set of $k$ samples $X$. In other words, the generalization error can be stated in terms of the following quantity:

$\mathbb{E}[\sup_{\omega\in \Omega} \frac{1}{n} \sum_{i=1}^n \sigma_i \cdot \langle \omega, NE(X_i, f_\omega, k_i)_j\rangle )]$

where $\sigma_i$ are Rademacher variables and $\text{NE}(X, f_\omega,k)$ is the $j^{th}$ agent's PNE value. In standard analysis for linear classifiers, the dependence on $\sup_{\omega}$ can be eliminated and Cauchy-Schwartz applied to bound this term. In our case, however, the dependence of $NE(X_i, f_\omega, k_i)$ on $\omega$, mean the supremum cannot be easily elimated to give a meaningful bound. So while the RC approach is feasible, it does not lead to a interpretable bound, leading us to use a covering approach.

When does the number of agents being dynamic lead to different outcomes vs fixed agents.

This is also an insightful question. When thinking about generalization, each sample in our setting consists of a value $k$ (sampled from a distribution) and the features vectors of $k$ agents. We assume these features vectors are sampled independently from some distribution $D$. While this is reasonable in many of the settings where strategic classification is relevant, one can consider an alternate setting where the $k$ agent feature vectors are sampled from a joint distribution where these feature vectors can be arbitrarily correlated (and not independent). If $k$ is fixed, our results still hold in correlated world. However, if $k$ is random and we are in this correlated world, it is unclear if generalization can hold. In short, for fixed value of $k$, our results hold regardless of correlations within a sample, while for random $k$, we require the feature vectors of the $k$ agents to be independent.