Algorithms for strategyproof classification

The strategyproof classification problem deals with a setting where a decision maker must classify a set of input points with binary labels, while minimizing the expected error. The labels of the input points are reported by self-interested agents, who might lie in order to obtain a classifier that more closely matches their own labels, thereby creating a bias in the data; this motivates the design of truthful mechanisms that discourage false reports. In this paper we give strategyproof mechanisms for the classification problem in two restricted settings: (i) there are only two classifiers, and (ii) all agents are interested in a shared set of input points. We show that these plausible assumptions lead to strong positive results. In particular, we demonstrate that variations of a random dictator mechanism, that are truthful, can guarantee approximately optimal outcomes with respect to any family of classifiers. Moreover, these results are tight in the sense that they match the best possible approximation ratio that can be guaranteed by any truthful mechanism. We further show how our mechanisms can be used for learning classifiers from sampled data, and provide PAC-style generalization bounds on their expected error. Interestingly, our results can be applied to problems in the context of various fields beyond classification, including facility location and judgment aggregation.

Authors

• Reshef Meir Technion - Israel Institute of Technology
• Ariel D. Procaccia Harvard University
• Jeffrey S. Rosenschein

Keywords

• Mechanism design
• Classification
• Game theory
• Approximation