Welfare-Optimal Classification with Accuracy Auctions
For machine learning practitioners deploying predictive models in social contexts, this work addresses the misalignment between accuracy and user benefits by enabling welfare optimization with truthful value elicitation.
The paper proposes optimizing social welfare instead of accuracy in prediction algorithms used for human decisions, and introduces a learning algorithm that incorporates a truthful auction to elicit private user valuations. Experiments on real and synthetic data demonstrate the algorithm's effectiveness.
Prediction algorithms are increasingly used to inform decisions about humans, but maximizing accuracy$\rule[0.25em]{1em}{0.4pt}$the standard learning objective$\rule[0.25em]{1em}{0.4pt}$does not necessarily maximize user benefits. Instead, we propose optimizing social welfare, defined as the average gain users receive from correct predictions. Welfare enables to express, and therefore account for, heterogeneity in how much users benefit from accuracy. But since these valuations are private and users can gain from overreporting them, learning must simultaneously elicit truthful values and optimize welfare with respect to them. To this end, we propose a novel learning algorithm that incorporates a truthful auction. We show how to compute allocations and prices efficiently, and bound the number of paying users$\rule[0.25em]{1em}{0.4pt}$ which surprisingly is independent of the sample size. We conclude with experiments on real and synthetic data that demonstrate our algorithm and explore the connections between welfare and accuracy.