Classification with Strategically Withheld Data
  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.
