Research map / Multi-agent systems and games / Games and equilibria
Bayesian Strategic Classification
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.
Studies strategic classification where agents hold a distributional prior over the deployed classifier and the learner strategically releases a truthful subset of hypotheses, giving oracle-efficient best-response algorithms and hardness/closed-form results for the learner's release problem.
Problem
Strategic classification under partial information: agents know only a prior over the deployed classifier, and the learner must decide how much (truthful) information to release to maximize accuracy after strategic manipulation.
Approach
Replace full classifier knowledge with a common prior over hypotheses; the learner releases a subset of hypotheses that contains the deployed classifier, agents best respond to the prior conditioned on that subset, and the learner optimizes the released subset (shown to be NP-hard for arbitrary priors but tractable for uniform priors).
Key results
- Shows the learner's optimal information release problem is NP-hard for arbitrary priors over threshold classifiers (reduction from subset sum).
- Gives an oracle-efficient exact best-response algorithm making O(n^d) oracle calls for linear classifiers in d dimensions, and proves a 2^n/sqrt(n) oracle lower bound for general p-norm costs.
- Provides an O(n^3) algorithm that exactly solves the learner's optimal release for discrete uniform priors, and closed-form optimal releases for continuous uniform priors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Release {h1, h2} rather than fully reveal {h1} | Bayesian Strategic Classification · Partial vs. full information release (two-point example) | accuracy: 2/3 -> 1 | Helped |
| Release {h2, h1.8} rather than fully reveal {h2} | Bayesian Strategic Classification · Partial vs. full information release (threshold example) | accuracy: 0.55 -> 1 | Helped |
| Use no-information release rather than full-information release | Bayesian Strategic Classification · One-dimensional threshold classification | false positive rate | Helped |
| Use full-information release rather than any partial release | Bayesian Strategic Classification · One-dimensional threshold classification | false negative rate | Helped |
Surprising findings
- Releasing partial information can strictly increase the learner's accuracy over full disclosure of the deployed classifier, even when the deployed classifier is optimal under full disclosure.
- For minimizing false positive rate, no-information-release (releasing the full prior support) weakly beats full-information-release, while for false negative rate full-information-release is optimal.
Limitations
- Learner's optimal release is NP-hard for arbitrary priors, so efficient results rely on uniform priors or 1-D threshold classes.
- Best response for general p-norm costs requires exponentially many oracle calls, so only approximations are efficient under V-submodular costs.
Experimental setup
Metrics: expected strategic accuracy false positive rate false negative rate
Baselines: full information release
Builds on: strategic classification Bayesian persuasion calibrated Stackelberg games
Closest papers by meaning
- Strategic Classification With Externalities (ICLR 2025 · similarity 0.89)
- Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning (NeurIPS 2025 · similarity 0.88)
- Should Decision-Makers Reveal Classifiers in Online Strategic Classification? (ICML 2025 · similarity 0.87)
- Incentivizing Desirable Effort Profiles in Strategic Classification: The Role of Causality and Uncertainty (NeurIPS 2025 · similarity 0.87)
- 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.85)
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.