Classification with Strategically Withheld Data


  • Anilesh K. Krishnaswamy Duke University
  • Haoming Li University of Southern California
  • David Rein Duke University
  • Hanrui Zhang Duke University
  • Vincent Conitzer Duke University



Mechanism Design, Classification and Regression


Machine learning techniques can be useful in applications such as credit approval and college admission. However, to be classified more favorably in such contexts, an agent may decide to strategically withhold some of her features, such as bad test scores. This is a missing data problem with a twist: which data is missing depends on the chosen classifier, because the specific classifier is what may create the incentive to withhold certain feature values. We address the problem of training classifiers that are robust to this behavior. We design three classification methods: MINCUT, Hill-Climbing (HC) and Incentive-Compatible Logistic Regression (IC-LR). We show that MINCUT is optimal when the true distribution of data is fully known. However, it can produce complex decision boundaries, and hence be prone to overfitting in some cases. Based on a characterization of truthful classifiers (i.e., those that give no incentive to strategically hide features), we devise a simpler alternative called HC which consists of a hierarchical ensemble of out-of-the-box classifiers, trained using a specialized hill-climbing procedure which we show to be convergent. For several reasons, MINCUT and HC are not effective in utilizing a large number of complementarily informative features. To this end, we present IC-LR, a modification of Logistic Regression that removes the incentive to strategically drop features. We also show that our algorithms perform well in experiments on real-world data sets, and present insights into their relative performance in different settings.




How to Cite

Krishnaswamy, A. K., Li, H., Rein, D., Zhang, H., & Conitzer, V. (2021). Classification with Strategically Withheld Data. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5514-5522.



AAAI Technical Track on Game Theory and Economic Paradigms