Welfare-Optimal Classification with Accuracy Auctions

Prediction algorithms are increasingly used to inform decisions about humans, but maximizing accuracy—the standard learning objective—is not necessarily optimal for this purpose. 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 benefit 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—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.

Traditional machine learning focuses on maximizing overall accuracy, assuming that correct predictions benefit everyone equally. However, people value accuracy differently - for instance, a correct diagnosis may matter far more to some users than others. To maximize total societal benefit, algorithms should prioritize accuracy where it is valued most, but because these personal valuations are private, users have an incentive to exaggerate them to get better results for themselves. To address this, we introduce "accuracy auctions," an approach that combines machine learning with an auction mechanism. Users submit bids reflecting how much they care about a correct prediction, and the system uses a smart pricing rule to charge a fee only if a user’s bid directly alters the algorithm's final decision. This setup aligns economic incentives, encouraging everyone to report their true valuations honestly. Interestingly, we prove that for many standard algorithms, the number of users who actually need to pay is very small and does not grow with the dataset's size. Furthermore, these payments are only collected during the initial training phase; once deployed, the AI provides welfare-optimized predictions to all future users.