Information Design Against Gaming and Learning Adversaries
Not on the map. Why?
Abstract (arXiv)
A principal who deploys a binary classifier with an abstention option must decide which queries the mechanism abstains on. The right choice depends on the adversary. A gaming adversary already knows the classifier and tries to manipulate features across the boundary, so the principal does best by abstaining on queries close to that boundary. The same boundary-localizing rule is the worst possible choice against a learning adversary who does not know the classifier: each abstention now tells the adversary that the boundary is nearby, which is enough to drive a binary search. We analyze this tension. The two natural defenses, abstaining at a fixed rate and abstaining near the boundary, are Blackwell-incomparable: neither can be simulated by post-processing the other's responses. The number of queries needed to reconstruct the boundary to error eps is tildeTheta(d/eps) under the first defense and Theta(d log(1/eps)) under the second, where d is the VC dimension of the classifier family and tildeTheta suppresses factors polylogarithmic in d and 1/eps. The first rate is a worst case over query distributions; no reconstruction algorithm can close the gap at the distributions that attain it. We characterize the Pareto frontier between the two defense objectives, and confirm both rates on seven binary-classification tasks spanning tabular, image, and language-model-feature inputs: label-plus-counterfactual access extracts the boundary with up to 200× fewer queries than a published label-only baseline.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 26 of its 53 references that are in the map. First posted on arXiv 12 Sep 2026.
Builds on
26 of 53 references.
References · 26
- 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
- 2015Character-level Convolutional Networks for Text Classificationcited by 2,330
- 2020MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformerscited by 1,463
- 2016Stealing Machine Learning Models via Prediction APIscited by 619
- 2017Decision-Based Adversarial Attacks: Reliable Attacks Against Black-Box Machine Learning Modelscited by 462
- 2021Retiring Adult: New Datasets for Fair Machine Learningcited by 449
- 2019Nuanced Metrics for Measuring Unintended Bias with Real Data for Text Classificationcited by 404
- 2019SelectiveNet: A Deep Neural Network with an Integrated Reject Optioncited by 350
- 2019HopSkipJumpAttack: A Query-Efficient Decision-Based Attackcited by 333
- 2015Strategic Classificationcited by 257
- 2019High Accuracy and High Fidelity Extraction of Neural Networkscited by 214
- 2017Strategic Classification from Revealed Preferencescited by 128
14 more
- 2018Model Reconstruction from Model Explanationscited by 86
- 2018Exploring Connections Between Active Learning and Model Extractioncited by 85
- 2018How Do Classifiers Induce Agents To Invest Effort Strategically?cited by 83
- 2022A Characterization of Multiclass Learnabilitycited by 67
- 2021Detecting Adversarial Examples Is (Nearly) As Hard As Classifying Themcited by 48
- 2020Model extraction from counterfactual explanationscited by 47
- 2017Active Learning for Cost-Sensitive Classificationcited by 41
- 2022DualCF: Efficient Model Extraction Attack from Counterfactual Explanationscited by 32
- 2014Beyond Disagreement-based Agnostic Active Learningcited by 22
- 2022Efficient Active Learning with Abstentioncited by 22
- 2024Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theorycited by 14
- 2015Truthful Linear Regressioncited by 13
- 2024Bayesian Strategic Classificationcited by 13
- 2025When In Doubt, Abstain: The Impact of Abstention on Strategic Classificationcited by 3
Built on by
Not cited yet.