Research map / Label-efficient and robust learning / Recognition and long-tail
Should Decision-Makers Reveal Classifiers in Online 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 online strategic classification when the decision-maker withholds the current classifier and agents best respond to a discounted average of past classifiers, proving mistake bounds that grow by (1-γ)^{-1} or k_in relative to the transparent setting.
Problem
In online strategic classification, the standard model assumes the decision-maker publicly reveals the classifier; it is unclear whether hiding it helps. The paper asks how limiting agents' access to the current classifier (agents respond to past classifiers) changes the learner's worst-case mistake
Approach
Model agents who best respond to a γ-discounted weighted average of historically implemented classifiers, with arbitrary tie-breaking, and show the learner's optimal mistake bound is worse by a factor of (1-γ)^{-1} or k_in; give a reduction algorithm and a matching-in-regimes lower bound, plus a discussion of learning (mean-based) agents that can cause infinitely many mistakes.
Key results
- Revealed-Arb setting has mistake bound O(k_in k_out ln(k_in k_out) d) with a matching Omega(k_in k_out d) lower bound up to logarithms.
- Gamma-weighted setting admits an algorithm with mistake bound O((1-gamma)^{-1} k_in k_out ln(k_in k_out) d) and a lower bound Omega(min{d(1-gamma)^{-1}, |H|}) on the mistake bound for deterministic algorithms.
- For mean-based learning agents (e.g., multiplicative weights or epsilon-greedy with eps_t = 1/sqrt(t)), the decision-maker can suffer infinitely many mistakes in the strategic realizable setting (informal observation).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Withhold the current classifier and have agents respond to a γ-weighted average of historical classifiers instead | Online strategic classification · Strategic realizable | mistake bound: (1-\gamma)^{-1} or k_{\text{in}} | Hurt |
| Replace standard tie-breaking with arbitrary tie-breaking while agents still observe the classifier (ablation) | Online strategic classification · Revealed-Arb versus Revealed-Std | mistake bound: an extra $k_\text{in}$ multiplicative factor | Hurt |
| Use arbitrary tie-breaking for best responses to the revealed classifier (ablation) | Online strategic classification · Revealed-Arb, strategic realizable | mistake bound: \Omega(k_{\text{in}}\cdot k_{\text{out}}\cdot d) versus the Revealed-Std lower bound of $\Omega(k_{\text{out}} \cdot \ma | Hurt |
| Set γ closer to 1, lengthening agents' effective memory of past classifiers | γ-Weighted online strategic classification · Strategic realizable | mistake bound lower bound: $(1-\gamma)^{-1}$ | Hurt |
| Use γ → 0, so agents respond approximately to the previous classifier, with arbitrary tie-breaking | Online strategic classification · γ-Weighted, γ → 0 | mistake bound lower bound: \Omega(d\cdot\kin\cdot\kout) | Hurt |
| Use the conservative algorithm that keeps all remaining hypotheses and predicts positive if any predicts positive | γ-Weighted online strategic classification · Strategic realizable | mistake bound: O(|\mathcal{H}|) | Helped |
| Use learning agents with Multiplicative Weights or ε-Greedy and ε_t = 1/√T or 1/√t | Online strategic classification · Strategic realizable | mistakes: infinite mistakes as T goes to infinity | Hurt |
Surprising findings
- Withholding the classifier can backfire: hiding it degrades the learner's mistake bound by a multiplicative factor of (1-gamma)^{-1} or k_in.
- Some mean-based learning agents can cause the decision-maker to make infinitely many mistakes even in the strategic realizable setting.
Limitations
- Gap between upper and lower bounds is not closed; the lower bound applies in different regimes of gamma and k_in separately.
- Analysis restricted to deterministic algorithms and the realizable setting; randomized and agnostic settings remain open.
- No general guarantee for learning agents; sleeping regret remains an open direction.
Experimental setup
Metrics: mistake bound Stackelberg regret
Baselines: Revealed-Std setting (standard best response with standard tie-breaking) Revealed-Arb setting Conservative algorithm for gamma-Weighted (|H| mistake bound)
Builds on: Littlestone dimension / standard optimal algorithm (SOA) manipulation graph model of strategic classification fictitious play
Closest papers by meaning
- Bayesian Strategic Classification (NeurIPS 2024 · similarity 0.87)
- Strategic Classification with Non-Linear Classifiers (NeurIPS 2025 · similarity 0.87)
- Incentivizing Desirable Effort Profiles in Strategic Classification: The Role of Causality and Uncertainty (NeurIPS 2025 · similarity 0.87)
- Strategic Classification With Externalities (ICLR 2025 · similarity 0.86)
- Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning (NeurIPS 2025 · similarity 0.86)
- Classification Under Strategic Self-Selection (ICML 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.