acceptodds
Under review as a conference paper at ICLR 2027

The Price of Predictive Multiplicity

Abstract

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 when every classifier is population optimal ( is even, is an upper bound for values, 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 . 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 with confidence on a balanced instance for fixed . 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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
predictive multiplicity, mechanism design, incentive compatibility, private values, randomized deployment

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_K9f6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates the economic costs associated with predictive multiplicity, where multiple classifiers achieve the same or similar population welfare but produce correct predictions for different individuals. They consider a model-selection setting in which each individual has a private value for receiving a correct prediction. The platform selects a classifier using a Gibbs distribution based on reported values and charges critical-value payments to ensure truthful reporting. The authors establish a connection between truthful payments and predictive multiplicity and provide statistical bounds on total payments.

Critical strengths
  1. The paper considers an interesting problem: classifiers with identical population welfare can affect individuals differently, creating incentives for strategic reporting.
  2. This paper provides strong theoretical analysis with several nontrivial results. For example, the KL-divergence characterization connects individual payments to the sensitivity of Gibbs selection, and Theorem 2 links payments to disagreement among near-optimal classifiers. Also, Theorem 4 establishes matching upper and lower bounds at all temperatures for a particular population with conflicting beneficiaries.
Critical weaknesses
  1. The assumptions for theoretical guarantees are restrictive. For example, the beneficiary-consensus condition in Theorem 3 requires all population-optimal classifiers to agree on correctness for individuals with positive values, almost surely.
Questions for authors

See weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer K9f6

Thank you for your supportive evaluation and for highlighting our KL-divergence payment characterization, Theorem 2's localization to near-optimal classifiers, and Theorem 4's matching upper and lower bounds across temperatures.

[W1] Role of beneficiary consensus, distinct optimal classifiers, and general disagreement bounds

Theorem 3's beneficiary consensus condition concerns only binary correctness of population-optimal classifiers on positive-value cases, requiring neither a unique optimal classifier nor identical predictions. In the three-class example in Appendix D.4, two distinct imperfect population-optimal classifiers are correct on the same three quarters of the positive-value cases and predict different wrong labels on the rest, while optimal models may also differ arbitrarily whenever vi=0v_i = 0. Under this condition, Theorem 3 gives vanishing total expected payment on every predetermined positive temperature schedule Tn=o(n)T_n = o(n).

Universal truthfulness, Theorem 1's individual joint accuracy-payment laws, and our blockwise upper-tail bounds require no consensus. In Theorem 2, any participant whose correctness varies across empirically near-optimal classifiers has expected bill at most bi2/(8T)b_i^2/(8T), while the mass outside those near-optima controls other bills. Theorem 4 provides a sharp example under disagreement, exhibiting two population-optimal classifiers benefiting different people in a fair-label population and proving expected total payments of Θ(min⁡Vn,,nV2/T)\Theta(\min\\{V\sqrt{n},\\, nV^2/T\\}) at every positive temperature and even sample size. Whereas recent work such as Haghighat, Anahideh, and Rudin (AAAI 2026) and Hsu, Chen, Zhong, and Semenova (ICML 2026) studies choice among comparably accurate models, we isolate the price of truthful choice under predictive multiplicity, arising in this example with no loss in population welfare.

To address partial agreement, Appendix C.3 Equation (C.7) introduces D2D_2, the population expectation of v2v^2 times the indicator of optimal-model disagreement on correctness. For M>0M > 0 nonoptimal classifiers and n≥4V/Δn \ge 4V/\Delta, this finite-sample upper bound on total expected payment is nD2/(8T)nD_2/(8T) plus two remainders controlled by the welfare gap Δ\Delta, whereas if M=0M = 0, only nD2/(8T)nD_2/(8T) remains for every nn.

Reviewer_qRhhOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper considers a stochastic model selection problem over a fixed, finite set of classifiers. The setting includes a platform and a group of participants. Each participant reports how much a correct prediction is worth to them. The platform uses these reported correctness values to select classifiers for the participants. Each participant privately knows their true correctness value, which the platform does not observe. The authors propose Blockwise Accuracy Auctions (BAA), which select a classifier using the Gibbs rule and use critical payments to make truthful reporting optimal. They analyze payments under this mechanism and show that expected total payments can vanish or grow as the number of participants increases under different conditions. They further show how independent selections across groups help control the risk of large total payments while preserving each participant’s joint distribution of correctness and payment.

Critical strengths

The topic is interesting, and the theoretical results are also useful for classifier selection based on participants’ reported values of correct predictions.

Critical weaknesses
  1. My main concern is that this paper does not introduce its problem and objective clearly. Although the utility function and model selection rule are given, the decision variables, optimization goals, and the relationships among these elements have not been clearly stated. These presentation issues make it difficult to understand the problem setting and how the main results address it. Some symbols are not clearly introduced when they first appear. For instance, in Equation (2), q is not explicitly introduced. These expression issues significantly increase the difficulty of understanding the research objectives and main results.

  2. I am also concerned about the lack of an AI-use disclosure statement. The authors should clarify whether and how AI was used in this work.

Questions for authors
  1. Please state the problem formulation completely and clearly.

  2. Please provide an AI-use statement with more details about the use of AI in this paper.

1 comment
AuthorsOpenReview ↗

Response to Reviewer qRhh

Thank you for your constructive review and for noting both the appeal of our problem and the usefulness of our results for classifier selection with private values for accuracy. Your suggestions guided our rewrite of Section 2, which now introduces the distribution qq and the complete optimization problem upfront, alongside an explicit AI Use Statement in the manuscript.

[W1/Q1] Complete problem formulation, decision variables, and objectives

A platform holds a fixed finite library HH of pre-trained deterministic classifiers. Each participant i∈1,…,ni \in \\{1,\dots,n\\} has fixed covariates xix_i, verified label yiy_i, and binary correctness allocation ai(h)=I[h(xi)=yi]∈0,1a_i(h) = \mathbb{I}[h(x_i) = y_i] \in \\{0,1\\}. Participant ii privately knows their value vi∈[0,V]v_i \in [0,V] for a correct prediction and submits a bid bi∈[0,V]b_i \in [0,V].

In Equation (2), q∈Δ(H)q \in \Delta(H) denotes a probability distribution over the library. Given reports b=(b1,…,bn)b = (b_1,\dots,b_n) and temperature T>0T > 0, the platform chooses qq by maximizing entropy-regularized reported welfare. \max_{q \in \Delta(H)} \left\\{ \mathbb{E}_{h \sim q}\\!\left[\sum_{i=1}^n b_i a_i(h)\right] - T \cdot \mathrm{KL}(q \\,\\\|\\, \mathrm{Uniform}(H)) \right\\}. The Gibbs distribution qbq_b in Equation (3) is the unique optimizer of this objective. Our statistical benchmark is true population welfare W(q)W(q) and its optimum W∗W^* evaluated on true values vv.

Beyond the marginal family qb\\{q_b\\}, the platform specifies two mechanism design choices to align incentives and control aggregate payment risk:

  1. Deployment coupling: a bid-independent partition of the nn participants into blocks, where each block draws its deployed classifier from qbq_b using an independent random seed while still computing qbq_b from all nn reports (relating to multi-model deployment questions studied in Gorecki and Hardt, NeurIPS 2025).
  2. Payment rule pi(b,seed)p_i(b, \text{seed}): critical-value bills satisfying pi(0,b−i,seed)=0p_i(0, b_{-i}, \text{seed}) = 0 and universal truthfulness, so reporting bi=vib_i = v_i maximizes realized utility ui=viai(h)−piu_i = v_i a_i(h) - p_i for every fixed seed.

Theorem 1 proves that under normalization and universal truthfulness, each participant's full allocation response curve αi(⋅)\alpha_i(\cdot) uniquely fixes their joint distribution of accuracy and payment, and integrating along the Gibbs reporting path gives expected bill T⋅KL(qb,∥,qi,0)T \cdot \mathrm{KL}(q_b \\,\\\|\\, q_{i,0}). Independent block draws preserve expected welfare and every individual's marginal outcome law and tighten the theoretical upper-tail bound on total payments. In our experiments they lower expected shortfall on both datasets.

[W2/Q2] AI-use disclosure

The revised manuscript includes the following AI Use Statement: "We used large language models to revise the manuscript’s language and organization. The authors take full responsibility for the final content of this work."

Reviewer_HhniOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the problem of predictive multiplicity. Predictive multiplicity, at a high level, is the general observation that models that have the same population performance often provide differing predictions for a particular individual. This work studies the problem of, when there are multiple models, how and which one should we select. The authors study "welfare-based Gibbs selection from a fixed library". There are numerous theorems/results that characterize individual allocation, establish a consistency-payment tradeoff within the Gibbs family, and characterize concentrated payments. The authors also provide experiments to validate the effectiveness of their proposed mechanism.

Critical strengths

None

Critical weaknesses

This paper is very difficult to read. From the very beginning, the work introduces numerous technical definitions and jargon that many readers are not familiar with. Of course, any work will have new concepts, definitions, etc. However, it is the author's job to distill this into a paper that people can understand. In its current form, the paper is extremely difficult to follow. Here are just a few instances where there is a severe lack of clarity:

  1. Section 2: In the problem formulation, the authors introduce many quantities and terms. What is a library? What is a report? Why is u_i a utility? Beyond just the mathematical definition, what is a correctness allocation? What is it measuring?

  2. Section 3: You define α(t)\alpha(t). What is this? What is it quantifying? What is a monotone allocation response and normalized single-parameter truthfulness?

  3. Section 3.2: The authors begin with mathematical equations for H and I. What are these quantities? What are they measuring?

  4. Section 4: The first sentence states, "Payment identities relate elicitation costs to generalization." What does this even mean? What is the following finite concentration result telling us?

I could enumerate even more instances where nothing is clear and there is just a ton of technical jargon without explanations.

Questions for authors

N/A

1 comment
AuthorsOpenReview ↗

Response to Reviewer Hhni

Thank you sincerely for your detailed, section-specific reading suggestions across the paper. Your feedback guided a thorough rewrite of our exposition for readers new to mechanism design, and Section 2 now describes the platform and participants concretely before presenting the optimization. Below we address your four questions in order.

[W1a] Section 2 library, reports, and utility

The library HH is a fixed, finite set of pre-trained deterministic classifiers held constant across all bids, motivated by predictive multiplicity settings where accurate candidate models differ on individual predictions (Du, Ngo, and Wu, ICLR 2025, Hsu, Cao, Semenova, and Zhong, NeurIPS 2025). Each participant ii has a fixed feature vector xix_i, a verified label yiy_i, and a private monetary value vi∈[0,V]v_i \in [0,V] for receiving a correct prediction, and submits a bid report bi∈[0,V]b_i \in [0,V] to the platform (Sadi, Saig, and Rosenfeld, ICML 2026). For a given classifier h∈Hh \in H, the binary correctness indicator ai(h)∈0,1a_i(h) \in \\{0,1\\} is participant ii's allocation, equal to 1 when h(xi)=yih(x_i) = y_i and 0 otherwise. With bill pip_i, the quasilinear utility ui=viai(h)−piu_i = v_i a_i(h) - p_i measures the participant's realized value from prediction accuracy minus their payment.

[W1b] Section 3 allocation response and normalized universal truthfulness

Holding other reports fixed, the allocation response αi(t)\alpha_i(t) is participant ii's probability of receiving a correct classification when reporting tt. Raising their bid gives a common score increment to all classifiers correct on them while leaving wrong classifiers unchanged, making αi(t)\alpha_i(t) nondecreasing. With fixed random perturbations in our implementation, increasing tt produces at most one switch from an incorrect to a correct classifier. Past that switch, the participant's bill is the critical threshold where the switch occurred rather than their bid, and if already correct at zero, their bill is zero. Universal truthfulness means truthful reporting is optimal for every random seed, while normalization sets zero payment at zero bid for every seed. Theorem 1 proves that any normalized, universally truthful implementation sharing this continuous response curve fixes each individual's entire joint law of correctness and payment.

[W1c] Section 3.2 analytical near-optimal set HϵH_\epsilon and disagreement flag IiϵI_i^\epsilon

While the mechanism always samples from the full library HH, Theorem 2 uses two analytical quantities to localize where payments arise. The empirical near-optimal set HϵH_\epsilon collects all classifiers in HH whose total reported welfare lies within ϵ\epsilon of the empirical maximum under bb. The indicator Iiϵ∈0,1I_i^\epsilon \in \\{0,1\\} equals 1 when classifiers inside HϵH_\epsilon disagree on whether participant ii is predicted correctly. Theorem 2 bounds the expected payment of each disputed participant (Iiϵ=1I_i^\epsilon = 1) by bi2/(8T)b_i^2 / (8T) and accounts for all remaining payments via the bound Me−(ϵ−V)/TM e^{-(\epsilon-V)/T} on Gibbs mass outside HϵH_\epsilon along the reporting path, where M=∥H∖Hϵ∥M=\|H\setminus H_\epsilon\|.

[W1d] Section 4 generalization identity and finite-class concentration

Zeroing participant ii's report makes the Gibbs selection rule independent of their observation with the library and temperature unchanged, so their expected value-weighted correctness under that rule equals its expected population welfare. Across an i.i.d. sample, the difference between expected in-sample welfare of the full-sample rule and expected population welfare of this (n−1)(n-1)-observation rule equals the expected average bill plus a nonnegative reverse-divergence term. Finite-class concentration bounds this difference. For a fixed finite library and fixed TT, total expected payments are O(n)O(\sqrt{n}), equivalently an O(1/n)O(1/\sqrt{n}) expected average bill, while separately the full rule's expected welfare shortfall from the population optimum is O(1/n)O(1/\sqrt{n}). Intuitively, as empirical averages concentrate around population values, expected per-person bills and expected welfare loss both vanish.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Note to AC: Rebuttal Summary

Dear Area Chair,

We are grateful to all three reviewers for their constructive engagement with our paper. Reviewer K9f6 highlighted our "strong theoretical analysis with several nontrivial results," Reviewer qRhh noted that "the theoretical results are also useful for classifier selection based on participants’ reported values of correct predictions," and Reviewer Hhni provided helpful section-by-section questions that guided our exposition rewrite.

Our results show how predictive multiplicity shapes the cost of truthful preference elicitation. At fixed positive temperature, we exhibit an explicit population where every model is welfare-optimal but different people benefit and total expected truthful payments grow as n\sqrt{n} for even sample sizes, whereas under beneficiary consensus total expected payments instead vanish. Because normalized universal truthfulness fixes each person's entire correctness-and-payment law from their reporting-path allocation probabilities, blockwise deployment keeps selection probabilities, expected welfare, and individual outcomes in distribution unchanged while reducing exposure to large total bills.

At the reviewers' suggestion, we substantially rewrote our explanations across Sections 2 through 4 covering the problem formulation, individual allocation and payments, and generalization. We also revised Figure 1 to contrast shared and independent draws, and added Appendix C.3's finite-sample bound for partial beneficiary agreement.

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.