The Price of Predictive Multiplicity

Classifiers with the same population performance may assign correct predictions to different people. We consider the problem of model selection in a scenario where individuals privately value correctness. Using Gibbs selection of a fixed library, we show that payments for truthful critical values can scale as $\min \{V\sqrt{n},n{V}^2/T\}$ when every classifier is population optimal ($n$ is even, $V$ is an upper bound for values, $T$ is temperature). Each payment depends not only on the report induced change in the probability that a model is chosen, but also on disagreement among almost optimal classifiers. Moreover, if all optimal classifiers agree on the correctness of individuals with positive values, aggregate payments vanish asymptotically along each predetermined schedule $T_n=o(n)$. We further show that each person's law of joint correctness and payment is characterized by normalized universal truthfulness, while the dependence across people is available for design. Based on these observations, we propose Blockwise Accuracy Auctions, which leave each individual's law invariant, while reducing the quantile of aggregate payment from linear to $\log n/\log \log n$ with confidence $1-n^{-c}$ on a balanced instance for fixed $c>1$. On Adult and Bank Marketing, independent deployment reduces 99% expected shortfall from 10.23 to 1.10 and from 6.62 to 1.02 without changing expected welfare or distributions of individual payments.