2020/12/18 by A. Krishnaswamy, Anilesh K. Krishnaswamy, Krishnaswamy, Anilesh K. +9 · 2 citations
Computer Science · Decision Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data #cs.GT #cs.LG
paper · pdf · doi:10.48550/arxiv.2012.10203
openalex publication_date 2020/12/18 · arxiv created 2021/01/14 · arxiv updated 2021/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \em 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: \sc Mincut, \sc Hill-Climbing (\sc HC) and Incentive-Compatible Logistic Regression (\sc IC-LR). We show that \sc 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 \sc 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, \sc Mincut and \sc HC are not effective in utilizing a large number of complementarily informative features. To this end, we present \sc 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.