Research map / Multi-agent systems and games / Games and equilibria
Strategic Classification With Externalities
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Models strategic classification with inter-agent externalities as a Stackelberg-Nash game, shows the agent manipulation game is a potential game with a unique, efficiently computable pure Nash equilibrium under convexity conditions, and gives PAC guarantees and gradient characterization for learning the classifier.
Problem
Strategic classification ignores that agents' manipulations affect each other through externalities (e.g., shared resources, detection risk), so classifiers trained under independent-agent assumptions may be mis-calibrated in multi-agent settings.
Approach
Model the learner-agent interaction as a Stackelberg game and the inter-agent manipulation as a simultaneous game with pairwise symmetric externalities; this yields a potential game whose strictly concave potential gives a unique PNE computable via convex optimization, enabling PAC learning and implicit-differentiation-based gradient training.
Key results
- Under strictly concave potential (convex cost and externality), the pure Nash equilibrium of the manipulation game is unique and computable as a convex program.
- PAC generalization guarantee is proven for linear classifiers under a random number of agents, with sample complexity depending on the Lipschitz constant of the equilibrium map.
- Experiments on synthetic data show strategic training and validation losses decrease in lockstep, while a truthful baseline performs poorly when cost and externality are low.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| train with agents manipulating to a pure Nash equilibrium instead of training on truthful reports | Linear classifier · Synthetic 2-class strategic validation | loss | Helped |
| train strategically with equilibrium reports | Linear classifier · Synthetic 2-class validation | generalization error | No clear effect |
| increase the intensity of cost and externality | Truthful/non-strategic baseline classifier · Synthetic 2-class strategic test | loss | Helped |
| increase the number of agents k | Truthful/non-strategic baseline classifier · Synthetic 2-class strategic test | loss | Helped |
| increase the intensity of cost and externality | Strategic training · Synthetic 2-class validation | generalization error | Helped |
Surprising findings
- The non-strategic baseline's performance improves as the number of agents k grows, since per-agent influence on the average externality diminishes.
Limitations
- Results rely on structural assumptions (pairwise symmetric, convex or cumulatively strictly convex externalities) that may not hold in practice.
- Assumes the learner knows the cost and externality functions.
- Experiments are limited to small synthetic data and do not validate the model on real-world data.
Experimental setup
Datasets: scikit-learn synthetic 2-class dataset
Benchmarks: synthetic scikit-learn dataset
Metrics: strategic validation loss loss vs training epochs
Baselines: non-strategic truthful classifier classifier trained with cost-only strategic model
Builds on: strategic classification (Hardt et al.) strategic regression potential games cvxpylayers
Closest papers by meaning
- Bayesian Strategic Classification (NeurIPS 2024 · similarity 0.89)
- Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning (NeurIPS 2025 · similarity 0.87)
- Understanding Model Selection for Learning in Strategic Environments (NeurIPS 2024 · similarity 0.86)
- Should Decision-Makers Reveal Classifiers in Online Strategic Classification? (ICML 2025 · similarity 0.86)
- One-Shot Strategic Classification Under Unknown Costs (ICML 2024 · similarity 0.86)
- Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.