Welfare-Optimal Classification with Accuracy Auctions
2026-06-01 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors discuss how prediction algorithms usually try to be as accurate as possible, but being accurate isn't always the best way to help users. They suggest focusing on 'social welfare,' which means making sure users get the most value from correct predictions, considering that different users may benefit differently. Since these benefit values are private and users might lie to get more advantage, the authors create a learning algorithm that uses a truthful auction to get honest inputs and optimize welfare. Their method efficiently decides who benefits and who pays, and they test it on real and fake data to compare welfare and accuracy.
prediction algorithmssocial welfareuser benefitheterogeneous valuationtruthful auctionlearning algorithmincentive compatibilityallocationprice mechanismaccuracy
Authors
Bana Sadi, Eden Saig, Nir Rosenfeld
Abstract
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.