Towards Human-AI Complementarity with Prediction Sets
Authors: Giovanni De Toni
Nastaran Okati
Suhas Thejaswi
Eleni Straitouri
Manuel Gomez Rodriguez
Venue: NeurIPS 2024 poster (2024)
Keywords: conformal prediction
decision support systems
human-ai complementarity
Primary area: human-AI_interaction
TL;DR: Prediction sets based on conformal prediction can be suboptimal in achieving human-ai complementarity. We show that finding optimal prediction sets is NP-hard and we give a greedy algorithm with provably improved performance than conformal prediction

Abstract: Decision support systems based on prediction sets have proven to be effective at helping human experts solve classification tasks. Rather than providing single-label predictions, these systems provide sets of label predictions constructed using conformal prediction, namely prediction sets, and ask human experts to predict label values from these sets. In this paper, we first show that the prediction sets constructed using conformal prediction are, in general, suboptimal in terms of average accuracy. Then, we show that the problem of finding the optimal prediction sets under which the human experts achieve the highest average accuracy is NP-hard. More strongly, unless P = NP, we show that the problem is hard to approximate to any factor less than the size of the label set. However, we introduce a simple and efficient greedy algorithm that, for a large class of expert models and non-conformity scores, is guaranteed to find prediction sets that provably offer equal or greater performance than those constructed using conformal prediction. Further, using a simulation study with both synthetic and real expert predictions, we demonstrate that, in practice, our greedy algorithm finds near-optimal prediction sets offering greater performance than conformal prediction.

Towards Human-AI Complementarity with Prediction Sets
Giovanni De Toni"
Nastaran Okati
Fondazione Bruno Kessler & University of Trento
Max Planck Institute for Software Systems
Trento, Italy
Kaiserslautern, Germany
giovanni..o dew.niennnnnooo @unitn. it
wewranni.detoiii
nastarandmpi-sws org
Suhas Thejaswi
Eleni Straitouri
Max Planck Institute for Software Systems Kaiserslautern, Germany
Max Planck Institute for Software Systems Kaiserslautern, Germany
wetiaasssiiisssss..m org
estraitouri (opuurimppissssse org
Manuel Rodriguz
Max Planck Institute for Software Systems Kaiserslautern, Germany
manuelgr@mpe @mw.-wwwswwww...pp org
Abstract
Decision support systems based on prediction sets have proven to be effective at helping human experts solve classification tasks. Rather than providing single- label predictions, these systems provide sets of label predictions constructed using conformal prediction, namely prediction sets, and ask human experts predict label values from these sets. In this paper, we first show that the prediction sets constructed using conformal prediction are, general, suboptimal in terms of average accuracy. Then, we show that the problem of finding the optimal predic- tion sets under which the human experts achieve the highest average accuracy NP-hard. More strongly, unless P = NP, we show that the problem is hard to approximate to any factor less than the size of the label set. However, we introduce a simple and efficient greedy algorithm that, for large class of expert models and non-conformity scores, is guaranteed to find prediction sets that provably offer equal greater performance than those constructed using conformal prediction. Further, using a simulation study with both synthetic and real expert predictions, we demonstrate that, in practice, our greedy algorithm finds near-optimal prediction sets offering greater performance than conformal prediction.
Introduction
In recent years, there has been increasing excitement about the potential of decision support systems based on machine learning to help human experts make more accurate predictions in a variety of application domains, including medicine, education and science (143]. In this context, the ultimate goal is human-Al complementarity- the predictions made by the human expert who uses a decision support system are more accurate than the predictions made by the expert on their own and by the classifier used by the decision support system 4
The conventional wisdom is that to achieve Numan-Al complementarity. decision support systems should help humans understand when and how to use their predictions to update their own. As result,
TThe author contributed to this paper during an internship at the Max Planck Institute for Software Systems.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

a flurry of empirical studies has analyzed how factors such as confidence, explanations, or calibration influence when and how humans use the predictions provided by a decision support system [2] Unfortunately, these studies have been so far inconclusive and it is yet unclear how to design decision support systems that achieve human-Al complementarity 13.
In this context, Straitouri et al. 18 19 have recently argued, both theoretically and empirically, that an alternative type of decision support systems may achieve human-Al complementarity. by design. Rather than providing single label prediction and letting a human expert decide when and how to use the predicted label to update their own prediction, these systems provide a set of label predictions, namely a prediction set, and ask the expert to predict a label value from the set To construct each prediction set, these systems rely on a conformal predictor [20] (1]. The conformal predictor first computes non-conformity score for each potential label value using the output provided by a classifier (e.g., the softmax scores), and then adds a label value to the prediction set if its non- conformity score is below a data-driven threshold computed using a calibration set. Further, to optimize the performance of these systems, Straitouri et al. have introduced several methods to efficiently find the optimal value of the threshold used by the conformal predictor However, it is unclear whether the optimal prediction sets maximizing the average accuracy achieved by an expert who uses such systems can always be constructed using deterministic threshold rule as the one used by a conformal predictor. Motivated by this observation, in this work, our goal is to understand how to construct optimal prediction sets under which human experts achieve the highest average accuracy.
Our contributions. We first demonstrate that there exist (many) data distributions for which the optimal prediction sets under which the human experts achieve the highest average accuracy cannot be constructed using a conformal predictor. Then, we show that the problem of finding the optimal prediction sets is NP-hard by using a reduction from the k-clique problem [22). More strongly, unless P = NP, we show that the problem is hard to approximate to any factor less than the size of the label set. However, we introduce a simple and computationally efficient greedy algorithm that, for large class of non-conformity scores and expert models parameterized by a mixture of multinomial logit models (MNLs), is guaranteed to find prediction sets that provably offer equal or greater performance than those constructed using conformal prediction. Moreover, using simulation study with both synthetic and real expert predictions, we demonstrate that, in practice, our greedy algorithm finds near-optimal prediction sets offering greater performance than conformal prediction. We have released an open-source implementation of our greedy algorithm as well as the code and data used in our experiments at /ttttp:://gtttub com/Networks -errkkkssLLnnngg/ towards- human ai wwappllmmetttatttppeeeeeee
sets
Further related work. Our work builds upon further related work on set-valued predictors, assort- ment optimization, and learning under algorithmic triage.
The literature on set-valued predictors aims to develop predictors that, for each sample, output set of label values, namely a prediction set (23] Set-valued predictors have not been designed nor evaluated by their ability help human experts make more accurate predictions 24] except for a few notable exceptions 18 28 30 These exceptions provide empirical evidence that
conformal predictors, a specific type of set-valued predictors, may help human experts make more accurate predictions. Among these exceptions, the work by Straitouri et al. [88 19), which we have already discussed previously, is most related to ours. In this context, it is also worth noting that recent theoretical study has argued that prediction sets may also help experts create more accurate rankings [31].
The literature on assortment optimization aims to develop methods to help a seller select a subset of products from a universe of substitutable products, namely assortment, with maximum expected revenue (2)36) Within this literature, the work most closely related to ours tackles the assortment optimization problem under customization [55 36), where there are different types of customers and each type of customer chooses products following a different multinomial logit model. More specifically, by mapping products to label values, types of customers to ground truth label values, and revenue to accuracy, one could think of our problem as an assortment optimization problem
"There are many decision support systems used by experts that, under normal operation, forcefully limit experts' level of agency. For example, in aviation, there are automated, adaptive systems that prevent pilots from taking certain actions based on the monitoring of the environment.
A threshold value is optimal if it maximizes the average accuracy achieved by an expert who predicts label values from the prediction sets created by the conformal predictor.

---

Data sample E
Pueutosshrra
Lung Concer
Lang
y=
Sarcoldoeis
8(x)
Paeumonia
Pneumonia
Pleural Edfusion
Pleural Elflusion
Decision Support System
Human Expert
Our automated decision support system. Given an instance with a feature vector x, the system C helps the expert by automatically narrowing down the set of potential label values to prediction set ((z) C V. The system asks the expert to predict a label value ý from S(x).
Figure 1:
under customization. However, in the assortment optimization problem under customization, the type of each customer is known and thus may be offered different subsets of products whereas, in our problem, the ground truth label unknown. As result, (the complexity of) our problem and our technical contributions are fundamentally different.
The literature learning under algorithmic triage aims to develop classifiers that make predictions for a given fraction of the samples and leave the remaining ones to human experts, as instructed by a triage policy (37 42]. In contrast, in work, for each sample, classifier is used to construct prediction set and human expert needs to predict a label value from the set. In this context, is also worth noting that learning under algorithmic triage has been extended to reinforcement learning settings 43]
2 Decision Support Systems Based on Prediction Sets
Given a multiclass classification task where, for each task instance, a human expert needs predict the value of ground truth label E y = {1...., ,.,..,,,,,, LJ,,
we focus on the design of decision support system that, given set of features x E X, helps the expert by narrowing down the set of potential
label values subset of them S(x) C V. Here, similarly in Straitouri et al. [ 19 we assume that, for any instance with features x E X, the system asks the expert's s prediction ý E y to belong to the prediction set S(z), i.e., S(x). The key rationale for restricting the expert's agency is that, if we would allow the expert to predict label values from outside the prediction set, a good performance would depend the expert developing good understanding of when predict label from the prediction set. In this context, it is worth highlighting that Straitouri et al. [19] run a large-scale human subject study compare the above setting against alternative setting where experts are allowed to predict label values from outside the prediction sets. They found that, in the alternative setting, the number of predictions in which the prediction sets do not contain the true label and the experts succeed is consistently smaller than the number of predictions in which the prediction sets contain the true label and the experts fail. As consequence, in the alternative setting, experts perform worse. Refer to Figure T for an illustration of the decision support system.
Then, for any E X, goal is to find the optimal prediction set S* (z) that maximizes the average accuracy of the expert's 's prediction i.e.
(x) = argmax (S Scy
where
g (2) = 10)-P0YXXX8 [U( x
(1)
where P(Y| X) denotes the conditional distribution of the ground-truth label and Ps X,Y) denotes the conditional distribution of the expert's predictions Y under the prediction set S
We denote random variables with capital letters and realizations of random variables with lowercase letters. 'The expert's prediction Y and the ground truth label Y may not be conditionally independent given the set of features X since, in most application domains of interest, the expert may have access to additional features. Otherwise, one may argue that pursuing human-AI complementarity is not worthy goal [47).

---

3 On the Suboptimality of Conformal Prediction
Given a user-specified parameter a E [0, 1]. a conformal predictor uses a choice of non-conformity score s X' x y + R and a calibration set Deal = { ((24,,)))e yt) where (IA, 34) ~ PX (X).
to construct the prediction sets (X) Spp (X) as follows:
(x) {u (x,,,) S (n))
where 9a is the ['mm + +1)(1 -a0=aa) -a]l/m empirical quantile of the non-conformity scores of the samples in the calibration set Deat- By using the above construction, the conformal predictor guarantees that the probability that the true label Y belongs to the subset (X) is almost exactly a, i.e.
1 a S P(Y (X)) I
1/(m 1), as shown elsewhere 20 21).
Under common choices of non-conformity scores [48] 49), there are many data distributions for which the optimal prediction set under which the human expert achieves the highest accuracy cannot be constructed using a conformal predictor. Consider the following example where y = 21,
and.
0.4
if =
Ciyy
P(Y y/ X x))
0.35
if y and Ps(Ý = 0 xx v) Eyes
0.25
if y=
where C1.1 C2,1 C3.1 1 = 0.33, C1.2 C1.3 = 0.4, C2.2 = C3.3 0.6, and -3,2- = C2.3 0. A brute force search reveals that the optimal prediction set is {2, and, under this set, the expert achieves accuracy 0.6. Now, assume we have access to a perfectly calibrated classifier f(x) E [0, 1]" i.e., for all x E X' and E V. it holds that (z) = P(Y y x = z). Then, for any choice of [0. 1]. as long as the con-conforyyty scores rank the label set in decreasing order of fz), the prediction set provided by conformal prediction can only be among the sets (0. (1) {1,2) 2]. (1. 2, 3. Among these sets, the set under which the expert achieves the highest accuracy (1, 3) and, under this set, the expert achieves accuracy 0.49 < 0.6.
Motivated by the above example, one may think of closing the above performance gap by incorpora- ting information about the distribution of experts' predictions in the definition of the non-conformity score. However, we cannot expect fully close the performance gap since, as we will show next, the problem of finding the optimal prediction sets is NP-hard to solve and approximate to any factor less than the size of the label set y
4
On the Hardness of Finding the Optimal Prediction Sets
In this section, we first show that, given E X, we cannot expect to find the optimal prediction set S* (z) that maximizes the accuracy of the expert's 's prediction in polynomial time
Theorem The problem of finding the optimal prediction set, as defined in Eq. 7 is NP-hard.
In the proof of the above theorem, NP-complete [22]. to an instance of the problem of deciding whether there exists a prediction set S C Y' such that g(8 (:) 2 B given a constant B O. More specifically, given k-clique problem defined over graph G = (V, E) with ls S [V], we reduce it to an instance of the above decision
first reduce the k-clique problem which is known to be
problem in which y = V, B = MV] and, for all y E y. we have that P(Y = y -y = x)
M and
Cgy Eyes Cyyy
f0 {
if (V. E otherwise,
=) Y Ps( =
where Cw'v
(3)
(1/Ng(y)
and No(s) denotes the number of vertices that are not adjacent to y. Then, since the above decision problem can be trivially reduced to the problem of finding the optimal prediction set (in polynomial time), we conclude that the problem is NP-hard.
Motivated by the above result, we may think in looking for desirable properties for the objective function (S æ) such as monotonicity and submodularity which would allow for the design of
'All proofs are in Appendix[A)
'Given graph G (V, E) and integer & S |1/ the k-clique problem seeks decide whether there exists S C V with size [S]
such that, for every u, o E S. there exists (u, v) E E.
"A function f 2 + 12 is submodular if and only if, for every S E T S y' and y E VVT it holds that S(SU (()(())) f(S)= 2 F(T U (v)) S(T).

---

Algorithm 1: Greedy algorithm
Input: Label set y, features classifier f. confusion matrix C Output: Prediction S
S+
(U(1)..... M(2) t- (z))
1/ Sort in descending order // Add labels the prediction until hit A
for kork {1, 1 do
S f- Ø
while [Sx do
+ 00
for E [Va)...... 9()) Sz do
A < g(S, U [w) r
G(Sa x)) // Eval the marginal gain of adding to Sa
if A A then
A A. y
S < Sy U {y"}
// Add label offering the largest marginal gain
12
g 2) ((512)
then
13
Sk
// Update if S achieves higher objective value
14 return S
approximation algorithms with non-trivial approximation guaranteess (50). Unfortunately. there many data distributions for which the objective function is neither monotone nor submodular. For example, assume y (1,
0.4
if
Cÿy
P(Y / X x)
0.35
if y and Ps(Y - 5 X x, = v) Eyes Cv'v
0.25
if y
where 01, = 0.2, C12 C2 C1.3 C3.1 0.4, C2 C3.3 0.6 and C2.3 C3.2 0. For S = = C C holds that g .)) = 0.4 > [T x)) = 0.34 and g x;) = 0.34 < x)) 0.44, and thus we can conclude it monotone. Moreover, it also holds that ((S ==) - < (T3 [x)- (T x) 0.096, and thus we can conclude
is not submodular.
In fact, the following theorem shows that we cannot expect to find a polynomial-tin cittomiill-imeeeeee algorithm to find a non-trivial approximation to our problem:
Theorem 2
The problem of finding the optimal prediction set, defined in Eq. 7 is NP-hard to approximate to any factor less than the size L of the label set y.
In the proof of the above theorem, we first show that, given a polynomial-time a-approximation algorithm for the problem of finding the optimal prediction set, we can obtain a polynomial-tim a-approximation algorithm for the problem of finding the maximum clique in a graph G = (V,E) Then, since it known that, for any >> the latter problem is NP-hard approximate
factor [V] I- ST, we can conclude that the problem of finding the optimal prediction set is NP-hard to
approximate a factor -
While the above hardness results may be discouraging, in what follows, we will introduce simple greedy algorithm that provably offers equal or greater performance than conformal prediction for large class of non-conformity scores and expert models, and in practice, often succeeds at finding (near-)optimal prediction sets.
simple greedy algorithm. Given a sample with features x E X' and prediction set C V, our greedy algorithm estimates the accuracy of the expert's 's prediction, as defined in Eq. [ using the following estimator:
Cgy
0(S1z)
Σ fz(
Eyes
Cy's
DES
(a)
(6)
Given graph G (V,E), the maximum clique problem seeks to find the largest S C V such that, for every u, E S, there exists (u, E.
5

---

where (a) approximates P(Y y y|x= x) using a well-calibrated classifier f(x) E [o, 1]" and, similarly as in Straitouri et al. [8] (b) approximates P's(Y' y y Y = y) using mixture of multinomial logit models (MNLs) parameterized by the confusion matrix of the predictions made by the expert on their own, i.e., Cy'y = Py = y | = y).
The greedy algorithm first ranks each label value y E y using the output (1 of the classifier. Let V(1). (()) be the label values ordered according to such a ranking, where '(t) denotes the i-th label value in the ranking and fuce (z) 2 Suug (z) for all i < j. Then, runs L rounds and, at each k-thh round, it starts from the prediction set S₁ 0 and iteratively adds to Sş the label value E ( D(B) F Sr that provides the maximum marginal gain O(Sz U {v} | O(Sk a)) until it exhausts the set (1(1)..... }(a).. J. Moreover, at each iteration and round, it keeps track of the set with the highest objective value. At each of the L runs of the greedy algorithm, at most L elements are added to the set S, and adding each element needs at most L times computing the marginal gain g(S U {y} z² ((S æ7,, which takes O(L) to compute. Hence, our algorithm has an overall complexity of O(L*). ). See Appendix B for a detailed running time analysis. Algorithm provides a pseudocode implementation of the procedure.
Importantly, the prediction sets provided by the greedy algorithm are guaranteed to achieve higher objective value 0 than those provided by any conformal predictor using a non-conformity score s(x, y) that is nonincreasing with respect to fx), as formalized by the following proposition! 10
Proposition 1 For any x E X, let S be the prediction set provided by Algorithm Hand Sep be the prediction set provided by any conformal prediction with a non-conformity score s(x, y) that is nonincreasing with respect to fa(x)), then, holds that g(S 2 g(S
Experiments with Synthetic Data
In this section, we compare the average accuracy achieved by different simulated human experts using prediction sets constructed with our greedy algorithm (Algorithm D]. brute force search, and conformal prediction on several synthetic multiclass classification tasks where the experts and the classifier used by the greedy algorithm, brute force search, and conformal prediction achieve different accuracies on their own.
Experimental setup. We create several synthetic multiclass classification tasks, each with n = 20 features per sample and varying difficulty. Out of 20 features per sample, only d = 4 of these features are informative"" while the rest are drawn at random. Refer to Appendix C for more details about the classification tasks. For each classification task, we generate 19,000 samples, which we split into training set (16,000 samples), a calibration set (1000 samples), a validation set (1000 samples) and a test set (1000 samples).
We use the first half of the samples in the training set to train a multinomial logistic regression model fæx) This model is used by the greedy algorithm. brute force search and conformal prediction. It achieves a different average test accuracy P(Y = Y), depending on the difficulty of the classification task. We use the second half of the samples in the training set train another multinomial logistic regression model f(x). However, during the training of this model, we modify the value a of one of the (informative) features of each training sample to (1 - (1-7)a+ + 7e, where e ~ (O, 1) and 7 E [o, 1] controls the average accuracy of the resulting model. Then, we use the (estimated) confusion matrix C(²) of the predictions made by fxx to model (the predictions made by) the simulated expert by (2)
means of a mixture of MNLs, i.e., Ps(Ý = y X = I, Y = y) = EV'Es C2
Further, we use the calibration set to calibrate the (softmax) outputs of the logistic regression model f using top-k-label calibration [52] with k = 5. We also use it to estimate the confusion matrices C(+) that parameterize the mixture of MNLs used to model (the predictions made by) the simulated human expert, and calculate the quantile da used by conformal prediction. Finally, we use the test set to evaluate the average accuracy achieved by the simulated expert using prediction sets constructed with our greedy algorithm, brute force search and conformal prediction. Here, note that
'PPropoiiioon I can be generalized to conformal predictors with any non-conformity score as long as the ranking that our greedy algorithm uses is the same as the ranking induced by the non-conformity scores. A feature is informative if its value conrlltes with the label value.

---

Table I: Empirical average test aceuracy achieved by four different (simulated) human experts, each with a different noise value ", on their own (NONE) and using prediction sets constructed with conformal prediction (NAIVE, APS, RAPS and SAPS) and with the greedy algorithm (GREEDY) four synthetic classification tasks. In each classification task, the classifier f used by conformal prediction and the greedy algorithm achieves different average accuracy P(Y = -). The number of labels is L = 10, the size of the calibration set is m = 1000, and we do not include brute force search because it achieves the same performance as the greedy algorithm. Each cell shows the average
and standard deviation over 10 runs. We denote the best results for each classification task in bold.
METHOD
P(Y' = Y) = 0.3
P(Y" = Y) = 0.5
P(Y"= = 0.7 P(Y" = YY = 0.9
NAIVE
0.340 10.014
0.588 10.015
0.799 10.013
0.944 10.006
APS
0.341 +0.013
0.587 +0.013
0.804 #0.015
0.941 #0.006
RAPS
0.341 #0.013
0.587 +0.013
0.804 #0.014
0.941 #0.006
0.3
SAPS
0.340 10.015
0.585 10.012
0.804 10.015
0.940 10.008
GREEDY
4.36440.01.
1.605+0.01
0.824
0.953 0.005
NONE
0.281 +0.018
0.485 +0.019
0.693 #0.018
0.883 #0.008
NAIVE
0.328 +0.014
0.564 +0.012
0.774 #0.014
0.932 +0.007
APS
0.329 10.012
0.565 10.010
0.787 10.013
0.932 10.008
RAPS
0.330 10.012
0.566 10.010
0.787 10.013
0.932 10.008
0.5
SAPS
0.329 +0.013
0.563 +0.008
0.787 #0.014
0.932 #0.009
GREEDY
0.353 10.015
0.587 10.010
0.805 10.012
0.945 0..004
NONE
0.261 10.016
0.446 100013
0.644 10:019
0.843 100011
NAIVE
0.319 10.012
0.534 1.0013
0.737 10.013
0.908 1000066
APS
0.320 +0.008
0.542 +0.012
0.759 10.015
0.913
RAPS
0.320 1.0.05
0.542 1.0.012
0.760 10.015
0.914 1:0.008
0.7
SAPS
0.319 1.0009
0.534 10.012
0.760 10.014
0.915 1:0.009
GREEDY
0.345 20.011
0.573 20.010
0.784 20.013
0.938 00000
NONE
0.238 +.0011
0.380 10.015
0.540 10.018
0.716 1:0013
NAIVE
10.015 +0.015
0.517 #0.011
0.714 20.015
0.894 #0.012
APS
0.316 +0.013
0.525 +0,009
0.733 20.014
0.895 10.000
RAPS
0.316 +0.013
0.525 +0.009
0.734 10.015
0.896 #0.010
1.0
SAPS
0.315 10.014
0.517 40.011
0.734 10.015
0.896 +0.009
GREEDY
0.348 +0.013
0.567 #0.011
0.782 00.015
0.936 00000
NONE
0.214 10.017
0.303 10.014
0.382 10.021
0.452 #0.021
our greedy algorithm and brute force search have access to the true mixtures of MNL. used to model the simulated human expert. our experiments, we implement conformal prediction using several non-conformity scores:
s(x, v) 1 (x) (NAIVE, 20 6(x,y)=
Σ
(x) (APS. 53
s(x,y) = (z(()
Σ
fx(x) + Araps (o(x, y) kreg)" )
(RAPS, 49
(=),())
mmxxy' fy (x)
o(x, v) = o(I 9)
s(x,1)
(SAPS, 54
maxx fy (z) Asaps (o(z.g)
where o(x, y) Ky/ (z) S fy (z)) denotes the ranking of label y according fy (z) and we decided to omit the randomization for APS, RAPS and SAPS as it is only required to achieve exact 1 a coverage and did have an influence the empirical average accuracy achieved by the simulated human experts in our experiments. For RAPS and SAPS, we run the procedure outlined in Appendix in Angelopoulous al. 449 optimize the additional hyperparameters, kregs and Xraps- for RAPS, and Asaps for SAPS, using the validation set. Further, for each con-oonfommiyy score and classification task, we report the results for the value under which the expert achieves the highest average test accuracy and, to avoid empty sets, we always include the label value with the lowest non-conformity score in the prediction sets. this context, note that, in practice, one would need to select using held-out dataset, however, our evaluation aims to show how our greedy algorithm

---

0.40
0:28
0.06
0.00
0.06
0,02
0.00 0.00 0.06 0.01
0.6
NAIVE
BAPS
GREEDY
42
0,06
0.02
0.06
0.07
0.00
0,00
0,02 0.06
Aps
SAPS
0.08
0.60
0.64
0.21
0.06
1.00
0.02
0.00 0.00 0.05
0.5
0.00
0:14
022
0.52
0.02
0.04
0.04
0,00
0.00 0.02
0.4
00
0.04
0.01
0.02
49 0:28
0.00
0,00
0.10 0.00
0.4
L0
00
0.01
0.01
0.00
0.00
0,02 0.01
0.3
8
0.01
0.01 0.02 0.10
0.06
0.00
0.61
0.30
0.00
0.00
0.3
0.2
00 02 0.02 0.08
0.01
0.03
0.20
0.65
0.00
0.02
0.2
30
0 00 02 0.00 0.00 0.05 0.00
0.06
0.00
0.56
0:97
0.1
-
0.0G
0.08 0.00 0.02 0.02 0.00 0.04
0.01
0.24
8.50
0.1
0.0
0.0
Y
y 0,8
Figure 2: (Left) Confusion matrix C' for the predictions made by a (simulated) human expert on their own. The label i = argmax,' y' Cy'y that is most frequently mistaken with the ground truth-label y highlighted in red for y E {0, 2, 6, 8}. (Right) Empirical conditional probability that a prediction set includes {y. 57 given Y = y with conformal prediction (NAIVE, APS, RAPS and SAPS) and our greedy algorithm (GReEDy). In both panels. 7 = 0.7 and P(Y Y) = 0.7.
improves over conformal prediction for any value of a. Finally, we repeat each experiment ten times and, each time, we sample different training, calibration, validation and test sets.
Results. We first estimate the average test accuracy achieved by four different (simulated) human experts, each with a different y value, on four classification tasks where the classifier ff achieves a different average accuracy P(Y' Y). We report their average test accuracy their own (NONE) and when using prediction sets constructed with conformal prediction (NAIVE, APS, RAPS and SAPS), greedy algorithm (GReeDy) and brute force search (BRUTE FORCE SEARCH), Table T summarizes the results, where we have not included brute force search because it achieves the same performance our greedy algorithm. The results show that, using the greedy algorithm construct prediction sets, the experts consistently achieve the highest average accuracy across classification tasks. Moreover, the results also show that, under the prediction sets constructed using the greedy algorithm, the average accuracy achieved by the expert degrades gracefully as y increases whereas, under the prediction sets constructed using conformal prediction. the average accuracy degrades significantly. Refer to Appendix D for additional results for L E [25, 50} showing that the relative gain in average accuracy offered by the greedy algorithm increases with the number of labels and noise y. Refer to Appendix E for additional results showing that the empirical average coverage achieved by the prediction sets constructed using conformal prediction and our greedy algorithm may be a bad proxy for estimating the average accuracy achieved by human experts using prediction sets.
To better understand why the prediction sets constructed by the greedy algorithm help human experts achieve higher average accuracy than those constructed by conformal prediction, we now look closer into the structure of the prediction sets. Given ground truth-label Y y. let ý argmax, sy Cy's be the label that is most frequently mistaken with y. Then, we estimate the empirical conditional probability that a prediction set includes {y, 3) given Y y with the greedy algorithm and conformal prediction. Figure summarizes the results for 7 = 0.7 and P(Y' Y) = 0.7 and E {0, 2, 6, 8}. Appendix(Finncldde (iincluees additional results for other configurations. The results show that, with the greedy algorithm, the empirical probability that prediction set includes {y. 7h given Y = y is much lower (i.e., 2-3x lower) than with conformal prediction despite creates overall larger prediction sets.
Appendix
Experiments with Real Data
In this section, we compare the average accuracy achieved by a simulated human expert using prediction sets constructed with our greedy algorithm, brute force search and conformal prediction on real multiclass classification task over noisy natural images. The simulated human expert follows
8

---

Table 2: Average test aceuracy achieved by (simulated) human expert on their own (NONE), and using the prediction sets constructed with conformal prediction (NAIVE, APS, RAPS and SAPS), and our greedy algorithm (GREEDy) because it achieves the same performance as the greedy algorithm. Each cell shows the average and standard deviation over 10 runs. We denote the best results in bold.
the ImageNet1 6H dataset. We do not include brute force search
METHOD
W = 80
= 95
= 110
W 125
NAIVE
0.957 +0.008
0.946 00.008
0.919 =: 006
0,860 #0.008
APS
0.944 00000
0.932 =0.005
0.902 +0.008 008
0.852 #0.010
RAPS
=0.009
0.943 =0.010
0.914 #0.010
0.849 #0.011
SAPS
0.953 =0.010
0.942 =0.009
0.918 +0.009
0,855 #0.007
GREEDY
0.957 10.007
0.951 t0.009
0.925 10.008
0.874 10.009
NONE
0.900 00.02
0.859 10.003
0.771 100005
0.603 1.0.007
the mixture of MNLs introduced in Eq. 4 which is parameterized by the (estimated) confusion matrix of the predictions made by real human experts on their own 12
Experimental setup. We experiment with the ImageNet 66 dataset 77. which was created using 1,200 natural images from the ImageNet Large Scale Visual Recognition Challenge (ILSRVR) 2012 dataset [55]. More specifically, in the ImageNet16f 16H dataset, each of the above images was used to create four noisy images with different levels of phase noise distortion w {80, 95, 110, 125) and the same ground-truth label from a lahel set y of size n = 16. In addition, for each noisy image, the dataset contains (approximately) six label predictions made by human experts on their own. In experiments, we run and evaluate each method separately by grouping the above noisy images (and expert predictions) according to their level of noise. For each group of images and method, we use the deep neural network classifier VGG-19 (56) after 10 epochs of fine-tuning as provided by Steyvers et al. (7). Further, we randomly split the images (and expert predictions) in each group into two disjoint subsets, a calibration set (800 images), and test set (400 images). The accuracy of the (pretrained) VGG-19 classifier on the test set is 0.900 = 0.014 (w 80), 0.895 = 0.009 (w = 95), 0.857 = 0.016 (w = 110) and 0.792 + 0.016 (w = 125). We use the calibration set to (i) calibrate the (softmax) outputs of the VGG-19 scores using top-k-label calibration with k = 5, (ii) estimate the confusion matrix C that parameterizes the mixture of MNLs used to model the simulated human expert, and (iii) caleulate the quantile ςa used by conformal prediction 13 We use the test set to evaluate the average accuracy the simulated expert achieves using prediction sets constructed with our greedy algorithm, brute force search and conformal prediction. Here, note that, similarly to in the experiments in synthetic data, our greedy algorithm and brute force search have access to the true mixture of MNLs used to model the simulated human expert. We implement conformal prediction using the same non-confornity scores used in the experiments with synthetic data and, for each non-conformity score and group of images, we report the results for the a value under which the expert achieves the highest average test accuracy. In Appendix H report results for all a values. To obtain error bars, we repeat each experiment 10 times, sampling different calibration and test sets.
Results. Table 2 and Figure 3 show the average test accuracy and complementary cumulative distribution (cCDF) of the test per-image accuracy achieved by a simulated human expert using the prediction sets constructed with conformal prediction (NAIVE, APS, RAPS and SAPS), our greedy algorithm (GREaDY) and brute force search (BRUTE FORCE SEARCH) for different values of noise w. The results show that, similarly as in our experiments with synthetic data, the greedy algorithm achieves the same performance as brute force search. Moreover, they also show that, using greedy algorithm to construct prediction sets, the expert achieves the highest average accuracy in all groups of images except the group with w = 80, where both the greedy algorithm and one of the conformal predictors offer comparable performance. Similarly as in the synthetic experiments, refer to Appendix El for additional results regarding the empirical average coverage achieved by the prediction sets constructed using conformal prediction and our greedy algorithm.
In Appendix G we evaluate the goodness of fit of the mixture of MNLs to predictions made by real human experts using support system based prediction sets [19].
1FFor RAPS and SAPS, we further split the calibration set to obtain a (reduced) calibration (400 images) and validation (400 images) sets to calculate the quantile q., and optimize the hyperparameters of RAPS and SAPS, respectively.

---

NAIVE
APS
RAPS
SAPS
GREEDY
1.0
1.0
1,0
1.0
Imspiteal cCDV
0.8
0.5
0.5
0.5
0.7
0.7-
0.7
0.5
0.5
0.5
0.5
0.6
0.4
0.5
0.4
0.5
0.8
0.5
Empieiod Avesage Ascuracy
Empiriol Astunge Accureey
Empirool Asssage Accunee
Empircoal Avssage Accureey
80
95
110
125
Figure 3: Complementary cumulative distribution (cCDF) of the per-image test accuracy achieved by simulated human expert using the prediction sets constructed with conformal prediction (NAIVE, APS, RAPS and SAPS) and our greedy algorithm (GREEDY) on the ImageNet1 6H dataset.
7 Discussion and Limitations
In this section, we discuss several assumptions and limitations of our work, which open up interesting avenues for future work.
Hardness analysis. In our hardness analysis, our reduction utilizes an instance of our problem in which, for every prediction set, the predictions made by experts follow mixture of MNLs. As immediate consequence, this implies that, in general, the problem of finding the prediction set S that maximizes O(S) x)) is NP-hard approximate. However, in our experiments, the greedy algorithm is almost always able to find such a set S. As a result, we hypothesize that there may be certain conditions on the parameters of the mixture of MNLs under which the problem can be efficiently approximated to a factor less than the size of the label set.
Methodology. Our greedy algorithm assumes that, for every prediction set, the predictions made by the human expert follow a parameterized expert model-the above mentioned mixture of MNLs. would be worthy to develop model-free algorithms since, in the context of prediction sets constructed using conformal prediction, they have been shown to be superior to their model-based counter- parts [19]. To this end, a good starting point may be the literature (contextual) combinatorial multi-armed bandits [57] 588, where one can map each arm to a label value and each subset of arms, namely super arm, prediction set.
Evaluation. The results of our experiments suggest that the prediction sets constructed using our greedy algorithm may help human experts make more accurate predictions than the prediction sets constructed using conformal prediction. However, one may argue that the difference in performance is partly due to the fact that the non-conformity scores used in conformal prediction do not incorporate information about the distribution of experts' predictions. Motivated by this observation, would be important to investigate how to incorporate such information in the definition of non-conformity scores. Moreover, in our experiments, the true distribution experts predictions matches the mixture of MNLs used by the greedy algorithm and brute force search. However, in practice, there may be mismatch between the true distribution of experts' predictions and the mixture of MNLs, and this may decrease performance. Finally, in our experiments with real data, the ground truth labels are estimated by aggregating (multiple) predictions by human annotators using majority voting, however, this may introduce additional sources of errors that may influence our results [59].
Broader impact. We have focused on maximizing the average accuracy of the predictions made by an expert using decision support system based on prediction sets. However, in high-stakes application domains, it would be important to extend our methodology to account for fairness considerations.
Conclusions
We have looked at the problem of finding the optimal prediction sets under which human experts achieve the highest accuracy in given multiclass classification task. We have shown that this problem is NP-hard to solve and to approximate to any factor less than the size of the label set. However, we have empirically shown that, for a large parameterized class of expert models, simple greedy algorithm consistently outperforms conformal prediction.
10

---

Acknowledgments and Disclosure of Funding
Gomez-Rodriguez acknowledges support from the European Research Council (ERC) under the European Union's s Horizon 2020 research and innovation programme (grant agreement No. 945719). De Toni acknowledges support from the TANGO project (grant #101 (07663-ANGG), Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the EU or HaDEA. Neither the EU nor the granting authority can be held responsible for them.
References
[1] Wei Jiao, Gurnit Atwal, Paz Polak, Rosa Karlic, Edwin Cuppen, Alexandra Danyi, Jeroen de Ridder, Carla van Herpen, Martijn P Lolkema, et al. A deep learning system accurately classi- fies primary and metastatic cancers using passenger mutation patterns. Nature Communications, 11(1):728, 2020.
[2] Jacob Whitehill, Kiran Mohan, Daniel Seaton, Vigal Rosen, and Dustin Tingley. Mooc dropout prediction: How to measure accuracy? Proceedings of the ACM conference on learning @ scale, pages 161-164. ACM, 2017.
[3] Alex Davies, Petar Veličković, Lars Buesing, Sam Blackwell, Daniel Zheng, Nenad Tomašev, Richard Tanburn, Peter Battaglia, Charles Blundell, András Juhász, et al. Advancing math- ematies by guiding human intuition with AL. Nature Communications, 600(7887):70-74, 2021.
[4] Abir De, Paramita Koley, Niloy Ganguly, and Manuel Gomez-Rodriguez. Regression under human assistance. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2611-2620, 2020.
[5] Bryan Wilder, Eric Horvitz, and Ece Kamar. Learning to complement humans. Proceedings of the International Joint Conference on Artificial Intelligence. IJCAI, 2020.
[6] Gagan Bansal, Besmira Nushi, Ece Kamar, Eric Horvitz, and Daniel S Weld. Is the most accurate ai the best teammate? optimizing for teamwork. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11405-11414, 2021.
[7] Mark Steyvers, Heliodoro Tejeda, Gavin Kerrigan, and Padhraic Smyth. Bayesian mod- eling of human-ai complementarity. Proceedings of the National Academy of Sciences, (19(1))e2111547111 2022.
[8] Kori Inkpen, Shreya Chappidi, Keri Mallari, Besmira Nushi, Divya Ramesh, Pietro Michelucci, Vani Mandava, Libuše Hannah VepRek, and Gabrielle Quinn. Advancing human-ai com- plementarity: The impact of user expertise and algorithmic tuning on joint decision making. Transactions on Computer- Human Interaction, 10( 2023.
[9] Andrea Papenmeier, Gwenn Englebienne, and Christin Seifert. How model accuracy and explanation fidelity influence user trust. arXiv preprint arXiv:1907.12633 2019.
[10] Xinru Wang and Ming Yin. Are explanations helpful? a comparative study of the effects of explanations in ai-assisted decision-making In Proceedings of the International Conference on Intelligent User Interfaces, pages 318- 30-28,811 2021.
[11] Kailas Vodrahalli, Tobias Gerstenberg, and James Zou. Uncalibrated models can improve human-Al collaboration. In Advances in Neural Information Processing Systems, 2022.
[12] Han Liu, Yizhou Tian, Chacha Chen, Shi Feng, Yuxin Chen, and Chenhao Tan. Learning human-compatible representations for case-based decision support. In Proceedings of the International Conference on Learning Representations, 2023.
[13] Ming Yin, Jennifer Wortman Vaughan, and Hanna Wallach. Understanding the effect of accuracy on trust in machine learning models. In Proceedings of the CHI conference on human factors in computing systems, pages 1-12, 2019.

---

[14] Yunfeng Zhang. Q Vera Liao, and Rachel KE Bellamy. Effect of confidence and explanation on accuracy and trust calibration in ai-assisted decision making. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 295-305. ACM, 2020.
[15] Harini Suresh, Natalie Lao, and Ilaria Liccardi. Misplaced trust: Measuring the interference of machine learning in human pocision-maaingg In Proceedings of the ACM Conference on Web Science, pages 315-324, ACM, 2020.
[16] Vivian Lai, Chacha Chen, Q Vera Liao, Alison Smith-Renner, and Chenhao Tan. Towards a science of human-ai decision making: a survey of empirical studies. arXiv preprint arXiv:2112.114711 2021.
[17] Nina Corvelo Benz and Manuel Godez-Rodriguez. Human-aligned calibration for ai-assisted decision making. In Advances Neural Information Processing Systems, volume 36, 2024.
[18] Eleni Straitouri, Lequn Wang, Nastaran Okati, and Manuel Rodriguz. Improving expert predictions with conformal prediction. In Proceedings of the International Conference on Machine Learning, pages 32633-32652 PMIR, 2023.
[19] Eleni Straitouri and Manuel Gomez Rodriguz. Designing decision support systems using counterfactual prediction sets. In Proceedings of the International Conference on Machine Learning. PMLR, 2024.
[20] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer, 2005.
[21] Anastasios N Angelopoulos, Stephen Bates, et al. Conformal prediction: A gentle introduction. Foundations and Trends in Machine Learning, 16(4):494-591, 2023.
[22] Richard M. Karp. Reducibility among Combinatorial Problems, pages 103 Springer, 1972.
[23] Exgenii Chzhen, Christophe Denis, Mohamed Hebiri, and Titouan Lorieul. Set-valued via a unified framework. arXiv preprint arXiv:2 12318, 2021.
[24] Gen Yang, Sébastien Destercke, and Mérie-Hélène Masson. Cautious classification with nested dichotomies and imprecise probabilities. Soft Computing, 21(44))444-7462, 2017.
[25] Thomas Mortier, Marek Wydmuch, Krzysztof Dembezyússk, Eyke Hüllermeier, and Willem Waegeman. Efficient set-valued prediction in multi-class classification. Data Mining and Knowledge Discovery, 35(4): (444)::4335:: 435-1469, 2021.
[26] Liyao Ma and Thierry Denoeux. Partial classification in the belief function framework. Knowledge-Based Systems, 214:106742, 2021.
[27] Vu-Linh Nguyen and Eyke Hüllermeier. Multilabel classification with partial abstention: Bayes-optimal prediction under label independence. Journal of Artificial Intelligence Research, 72:613-665, 2021.
[28] Varun Babbar, Umang Bhatr, and Adrian Weller. On the utility of prediction sets in human-ai teams. Proceedings of the International Joint Conference on Artificial Intelligence, pages 2457-2463. IJCAI, 7 2022.
[29] Jesse C Cresswell, Yi Sui, Bhargava Kumar, and Noël Vouitsis. Conformal prediction sets improve human decision making. urXiv preprint arXiv:2401. 137444 2024.
[30] Dongping Zhang, Angelos Chatzimparmpas, Negar Kamali, and Jessica Hullman. Evaluating the utility of conformal prediction sets for ai-advised image labeling. In Proceedings of the ACM CHI conference on Human Factors in Computing Systems, 2024.
[31] Kate Donahue, Sreenivas Gollapudi, and Kostas Kollias. When are two lists better than one?: Benefits and harms in joint decision-making. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 10030-10038, 2024.
[32] Kalyan Talluri and Garrett Van Ryzin. Revenue management under a general discrete choice model of consumer behavior. Management Science 50(1):15-33, 2004.
12

---

[33] Paat Rusmevichientong, Zuo-Jun Max Shen, and David B Shmoys. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research, 58(6):1666-1666 2010.
[34] James Davis, Guillermo Gallego, and Huseyin Topaloglu. Assortment planning under the multinomial logit model with totally unimodular constraint structures. Work in Progress, 2013.
[35] Omar El Housni and Huseyin Topaloglu. Joint assortment optimization and customization under a mixture of multinomial logit models: On the value of personalized assortments. Operations research, 71(4):1197-122 2023.
[36] Rajan Udwani. Submodular order functions and assortment optimization. In Proceedings of the International Conference on Machine Learning, pages 34584-3465 34614. PMLR, 2023.
[37] Maithra Raghu, Katy Blumer, Greg Corrado, Jon Kleinberg, Ziad Obermeyer, and Sendhil Mullainathan. The algorithmic automation problem: Prediction, triage, and human effort. arXiv preprini arXiv: 1903. 12200, 2019.
[38] Hussein Mozannar and David Sontag. Consistent estimators for learning to defer to an expert. In Proceedings of the International Conference on Machine Learning, pages 7076-7087. PMLR, 2020.
[39] Abir De, Nastaran Okati, Ali Zarezade, and Manuel Gomez Rodriguez. Classification under human assistance. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 5905-5913, 2021.
[40] Nastaran Okati, Abir De, and Manuel Rodriguez. Differentiable learning under triage. In Advances in Neural Information Processing Systems, volume 34, pages 9140-9151, 2021.
[41] Mohammad-Amm Charusaie, Hussein Mozannar, David Sontag, and Samira Samadi. Sample efficient learning of predictors that complement humans. In Proceedings of the International Conference Machine Learning, pages 2972-3005. PMLR, 2022.
[42] Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David Sontag. Who should predict? exact algorithms for learning defer to humans. Proceedings of the International conference on artificial intelligence and statistics, pages 10545.
PMLR, 2023.
[43] Eleni Straitouri, Adish Singla, Vahid Balazadeh Meresht, and Manuel Gomez-Rodrige Reinforcement learning under algorithmic triage. arXiv preprint vrXiv:2209, 1 //28, 2021.
[44] Vahid Balazadeh, Abir De, Adish Singla, and Manuel Gomez Rodriguez. Learning to switch among agents in team via 2-layer markov decision processes. Transactions on Machine Learning Research, 2022.
[45] Andrew Fuchs, Andrea Passarella, and Marco Conti. Optimizing delegation between human and ai collaborative agents. arXiv preprini arXiv:2309. 2023.
[46] Stratis Tsirtsis, Manuel Gomez Rodriguez, and Tobias Gerstenberg. Responsibility judgments in sequential human-ai collaboration. In Proceedings of the Anmual Conference of the Cognitive Science Society, 2024.
[47] Rohan Alur, Loren Laine, Darrick Li, Manish Raghavan, Devavrat Shah, and Dennis Shung, Au- diting for human expertise. In Advances in Neural Information Processing Systems, volume 36, 2023.
[48] Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223-2) 2244, 2019.
[49] Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael Jordan. Uncertainty sets for image classifiers using conformal prediction. In Proceedings of the International Conference on Learning Representations, 2021.
[50] Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability, 3(71- 104):3, 2014.
13

---

[51] David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the ACM Symposium on Theory of Computing, page 681-690. ACM, 2006.
[52] Chirag Gupta and Aaditya Ramdas. Top-label calibration and multiclass-to-binary reductions. In Proceedings of the International Conference on Learning Representations, 2021.
[53] Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 358 3581-3591. Curran Associates, Inc., 2020.
[54] Jianguo Huang, Huajun Xi, Linjun Zhang, Huaxiu Yao, Yue Qiu, and Hongxin Wei. Conformal prediction for deep classifier via label ranking. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver. Jonathan Scarlett, and Felix Berkenkamp, editors, Proceed- ings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 20331-20347 PMLR, 21-27 Jul 2024.
[55] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115:211-252, 2015.
[56] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1409 2014.
[57] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armes bandit: General framework and applications, In Proceedings of the International conference on machine learning, pages 151-159, PMLR, 2013.
[58] Tyler Lu, Dávid Pál, and Martin Pál. Contextual multi-armed bandits. In Proceedings of the International conference Artificial Intelligence and Statistics, pages 485-492 4924 JMLR, 2010.
[59] David Stutz, Abhijit Guha Roy, Tatiana Matejovicova, Patricia Strachan, Ali Taylan Cemgil, and Arnaud Doucet. Conformal prediction under ambiguous ground truth. Transactions on Machine Learning Research, 2023.
14

---

A Proofs
A.1 Proof of Proposition !
We prove by contradiction. Assume there exist x E X' such that j(S x)) < (SSp x²) Let k: := Sepl and Sj be the set providing the highest objective among all the sets seen at the k-th round of the greedy algorithm. It should hold that:
(((v()) ((8) SSSpp œ) (8)
[x)
< (16)
g(S)
x) S g(S|z)) (186)
which is a contradiction, hence, it should hold that g(S Ix) (S.p zz) Note that (i) is due to the fact that the ranking imposed by the non-conformity scores are the same as the ranking considered by whenever the conformal prediction outputs set of size k; the &o elements correspond to same & elements that are considered in the k-th round in the greedy algorithm, ie., (V()).... v(() ; (ii) is due to the fact that Sg is the best set at the k-th round of the greedy algorithm; and (iii) is because S argmax s: ( 2).
our greedy algorithm
A.2 Proof of Theorem 1
To establish NP-hardness we reduce an instance (V)),, of the k-clique problem
1 which
is known to be NP-complete (22), to instance BB C*) of deciding whether there exists prediction set S S y such that g(S x)) 2 B given constant B > 0, as follows: E Rd y V.
B = & and, for all y E V, we have that P(Y = X = r) Moj and
M
Ciu
{
fo
(1' v) E otherwise,
Ps( = 1 X = = 5)
where Cy'v
{
Eyes Cv's
1/Nv(v)
and Nv(3) denotes the number of vertices that are not adjacent to y G. For any S V.
Cuy
( = Σ (z)) Eves Cv'v
D
WES Ns(u)*
15 and (v) denotes the number of vertices that are not adjacent to y in the subgraph induced by S. The transformation described above is dominated by the size of C, which is O(1V))), so the reduction is polynomial time.
We note that the above decision problem can be reduced, in polynomial time, to the problem of finding the optimal prediction set. Precisely, given the optimal prediction set S*, for every B S gS xx) we return YES, otherwise NO. Thus, establishing the NP-hardness for the decision problem suffices.
(=) Here, show that, if the (decision-variis variant of the) optimal prediction sets problem is YES instance then the k-clique problem is also a YES instance. Since the optimal prediction sets problem a YES instance, we have a subset C y such that g x)) Z & We anticipate two possibilities,
D
either max,es Ny( = or max,es Ns(y) > 1, in both cases, we will show that there exists a clique of size least i in G.
If m (y) 1 then every pair of vertices y, y E S are adjacent. Since ( 2 & the & DJ
y9. So S induces clique of size at least l in G.
size of S must be at least & otherwise gS xx) <
If max (s(v) > 1. we (iteratively) remove y = arg max Ns(y) that has least number of neighbours in Gs. that is the subgraph induced by vertices in S. In Lemma I we show that, by remov- ing v = arg es Ns( from S, it holds that g(S \ (v/} x) 2 gS xr). Further, the assertion
"Given graph & = (V,8) ) and an integer & < [V] the k-clique problem seeks to decide whether there exists S V with size |S] k such that, for every distinct pair graph 9 simple, do not contain self loops and do not contain multiple edges between same pair of vertices. 15 A graph Gs = (S, Es) is a vertex- vertex-induced subgraph in graph & = (V,g). i S V and for every u, E S. (u, v) E Es if and only if (u, v) E E.
S, there exists (u, v) E E. We assume that the
15

---

g(S [0')))>> 2 9 22) remains true for each iteration as we remove y' = arg m Ns(v) iteratively, obtain S' S such that maXyes' (v) 1 and it holds that g(8 x)) Z - The size of S' is at least k, any smaller subset results in g x:) v.y/ E S' are adjacent, S' induces clique of size at least A:
Since |8|| k and every & [
(=) If k-clique is YES instance and S C V be clique of size k, then g x)) the optimal predictions set problem is YES instance. This concludes the proof.
M 1-1- So
Lemma For any subset C y with maxyes Nwy > and y' = arg maxyes Ns(u), holds that g(S \ (w') ax) 2 g(S x))
Proof
9 \ (1/) g(81x)
1
Σ
1
Ns(u)- -1 Ns(u)
Ni(wr)
Σ
(Ns())-1)(V
No(or)
(Eds)((n)(0))
(
(Nss(V) - 1Y(N5(r1) (186())-1x6607)))
|
No(or)
vEAS)(u)(())
(18)
0
Note that (i) and (ii) valid because y' arg maXyEs Ns(y).
A.3 Proof of Theorem
To establish the hardness of approximation, in Lemma we will show that, given a polynomial-time a-approximation algorithm for the problem of finding the optimal prediction set, can obtain polynomial-tin time a-approximation algorithm for the problem of finding maximum clique graph EV, It is known that, assuming * NP, for every > the latter problem NP-hard
16 in
to approximate to a factor |i- [5I]. So we conclude that the optimal prediction sets problem is NP-hard to approximate to factor D
Lemma Suppose there exists a polynomial-tin a-approximation algorithm for the optimal pre- diction sets problem with a 2 1, then there exists a polynomial-time a-approximation algorithm for the maximum clique problem.
Proof Let S* y denote the optimal solution for the optimal prediction sets problem, as defined in Eq A subset S C 3 is an a-approximation for the optimal prediction sets problem if g(S x)) -a 2 g(S Jr). We say an algorithm approximates an instance the maximum clique problem within a factor a if it can find a clique of size at least [ when the graph contains a max-clique of size k".
The reduction closely resembles the construction outlined in the proof of Theorem I with subtly distinction being the absence of a bound B. For completeness, we will describe the construction again. Given instance
(G- (V, E)) of the maximum elique problem, we construct instance (r, V, C) of the optimal prediction sets problem as follows: x E Idd, y = V and, for all y E V, we have that P(Y = yy X = x) = 4 and
Ps( = ú X = = Y v) = Cipy
So \/
if (V
where Cy's
Eyes Cy
otherwise,
16 Given graph G (V, E). the maximum clique problem seeks to find the largest S C such that, for every u, U. E S, there exists (u, E.
16

---

and Nv(8) denotes the number of vertices that are not adjacent to in G. For any S S y,
Cyu
(( = E5(r)
Eves Cw'
D WES Ns(u)'
WES
and Ns(y) denotes the number of vertices that are not adjacent to in the subgraph induced by S.
Let S* S V be a maximum clique of size k- in G. For all E S", Ns- (v) 1 and g x)) = kn
37
In Lemma we show that, for any y if S is not clique of size k", then g(S S g(S x). Further, if C y is an a-approximation, then from the definition of approximation ratio, it holds that,
o -g(S = g
|
In the remainder of this proof, we show that there exists a clique of size at least | g. do so, consider two possibilities: maxyes (y) 1 and maxyes Nvv) > 1. In both cases, we will establish the validity of the aforementioned claim.
A- maxyes (v) = and g(S (x) ... then [S] K. and every y: y E S is adjacent in the subgraph induced by So induces clique of size
If max (v) > 1, we (iteratively) remove y' = arg max Nv) In Lemmal we show that, by removing y arg argmaxx//s Ns(y) from S, it holds that g(S \ (v)) x)) 2 g(S [:). Further, the assertion g(S \ [v))z) 2 g (() remains true for each iteration as we remove y' = arg maxyes Ns(y) iteratively, to obtain S' C S such that maxyes: (v) = 1 and it holds that g(S |x) J. The size of S' is least 1+ any smaller subset results in and every y.v/ E S' are adjacent. So, we conclude that S Iz) < . Since [8"| Pf
induces clique of size least
Lemma For any C V. if the vertices in S do not induce maximum clique in G. then g(S x)) S g(S" [x), where S C induces maximun clique in G.
and S = k- Based the values k and k- can take, have three possibilities: (i) le < kt, (ii) k = k*, and (tii) k > kt. In each case, we show that the aforementioned claim holds.
Proof Let [8]
Case (i): If k < k", then g [x) D>i
k-1 g( Ir).
Case (1i): If & = k.,""" then gS x))
k-
= 9(S* xz)
1
Case (iii): If l K* and S do not induce a clique. then there exists at least one pair y, y' E S that are not adjacent, and the value of g(S x) < h-1 Without loss of generality, assume that g(S x) = D strict, i.e., gS x) 5 Let S {u} be clique of size k: 1. In order for gax,, > g(x, S*) to hold, S must contain a clique of size greater than b- + 1, which contradicts our premise that the maximum clique in G has size k.. More precisely,
TDT
k-1 Note that, if there are more vertex pairs that are not adjacent, then the inequality is
4: -
b >
g(S 2)) > g(S" (z) =
k k² +1.
D
|
This concludes the proof.
17

---

B Running time analysis of the greedy algorithm
In this section, we present the complexity analysis for the greedy algorithm in Algorithm [ Adding each element requires computing the marginal gain A O(S U {y} x) O(S) æ)) at most & times. This computation in Line 8 can be efficiently performed in O(k) time, where & is the size of Sk- Specifically, it can be rewritten as:
Cgs
Cgp
(S Hut x) - 0(Sk (z)= =
E (ESLU(U)
fa(x),
Σ fo(a) UES.
Eyes)u()) Cys
Eyees Cyr
The term Eves, Cyrg in the denominator can be computed as Eyres, Cv's + Cuo by storing the value of Eyes. Cyg at the end of each iteration after Line 11. The loops in Line 5 and Line 7 each iterate over k, resulting in ((k3) iterations for each value of ls E { L}. So, the overall running time of our algorithm is (L*)).
C Implementation details for the experiments with synthetic and real data
We report the implementation details and computational resources used to run the experiments in Section 5 and Section 6 The code infrastructure was written using Python 3.8 and the standard of scientific opensource libraries (e.g., numpy, pandas, scikit-learr. etc.). The full set of requirements can be found in the released code. We run the experiment on Linux machine equipped with an Intel Xeon(R) Gold 6252N CPU, with 96 cores and 1024 GB of RAM. Practically, our experiments and the algorithms require little resources to be run. We parallelized the execution using OpenMPI and 50 physical cores and 20 GB of RAM.
Experiments with synthetic data. We employ the _ake_claasse classification utility function of selkit-learrs generate the various prediction task. It is convenient method generate L-class classification tasks by varying several parameters such as the task difficulty, the number of labels and the number of informative features. generates clusters of points positioned on the vertices of d-dimensional hypercube by adding interdependencies and noise to the features. In Section [ we set the number of features to 20, the number of redundant features 0 and the number of informative features to d = 4 (for a L = 10 label classification task). We assign a balanced proportion of samples for each class. We control the task difficulty by choosing the class_sep parameter, which represents the length of the sides of the hypercubes. thus indicating how far apart are the various classes. A smaller class class_sep implies more difficult classification task. We vary the __ass_sep parameter to ensure the classifier and the humans span different ranges of accuracies. Please refer to the original documentation for more information
Experiments with real data. We use the data provided by Steyvers et al. 77] to evaluate our algorithm against the best conformal predictors. The dataset is composed of 1200 images from the ImageNet- 16H classification task. The authors provide also noisy version of these images by applying a different phase noise w. Noisier images imply a more difficult classification task. For each image and each phase noise, they provide also the softmax scores of several pre-trained classifiers for different levels of fine-tuning: baseline (no fine-tuning), between 0 and I epochs, 1 epochs and 10 epochs. We use the classifier scores (VGG-19 19 fine-tuned for 10 epochs) and the human classification performance alone for all the 1200 images for different levels of phase noise w {80, 95, 110, 125). We chose the VGG-19 classifier because it is the one achieving consistently higher accuracy than the expert alone in the classification task, for all phase noise levels. The data are freely available online [18] In our experiment, used Steyvers et al. normalized softmax scores which are obtained by dropping from VGG-19 all the irrelevant classes and by renormalizing.
18

---

D Empirical average test accuracy on additional classification tasks
In this section, we keep the same experimental setting as described in Section S but we vary the number of labels L E {25, 50) of the classification task. Table summarizes the results.
Table 3: Empirical average accuracy for I {25, 50).
Noise
Method
P(Y" Y) =
P(Y" Y)
P(Y" Y) 0.7
P(Y" Y) 0.9
NAIVE
0.399 10.012
0.614 10.000
0.892 100111
0.947 1: 006
APS
0.395 +0.011
0.601 =0.088
0.873 +0.00
0.938 =0 008
RAPS
0.395 10.011
0.601 10.008
0.874 10.009
0,939 1:0 008
0.3
SAPS
0,396 20.020
0.601 000008
0.876 20.013
0.943 =:0 OUT
GREEDY
0.431 +0.010
0.649:0..01
0.902 00.011
0.956 10.008
NONE
0.301 10.012
0.490 100015
0.805 10.012
0.904 1. 010
NAIVE
0,383 10.011
0.595 10.000
0.879 10.011
0.941 1:0, 005
APS
0.380 =00010
0.585 :00000
0.862 20.011
0.932 1:0 008
RAPS
0.380 10.010
0.585 1:0000
0.863 10.011
0.933 1:0. 008
0.5
SAPS
0.380 #0.009
0.585 =0.011
0.863 +0.014
01937 =0 007
GREEDY
0.417 +00.013
0.634 +-0.012
0.894 00.010
0,952 0:0.008
NONE
0.278 000011
0.445 000014
0,767 #0.012
0.879 3:0 010
NAIVE
0.365 #0.012
0.566 =0.009
0,848 +0.030
0.923 =:0.
APS
0.363 #0.009
0.560 =0.010
0.840 +0.012
0.918 =:
RAPS
0.363 100009
0.560 10.011
0,841 10.011
0.920 1:0,
0.7
SAPS
0.362 100000
0.558 10.015
0.840 10.014
0.920 1:0. 008
GREEDY
0.408 10.013
0.621 1000114
0.885 10.011
0.944 1:0,00
NONE
0.244
0.391 =0.014
0.661 +0.010
0.772 =00000 000
NAIVE
0.343
0.530
0.819 40.012
0,906
APS
0.346
0.529 10.016
0.822 10.015
0.906 1:0
RAPS
0.346 #0.011
0.529 =0.016
0.823 +0.013
0.907 =00 009
1.0
SAPS
0.344 =0.010
01528 =0.017
0.822 +0.014
0.907 =0
GREEDY
0.408 +0.012
0,618 01000014
0.888 +0.012
0.949 4-0.006
NONE
0.197 #0.006
0.299 =0.008
0,432 40,008
0.475 =:0 010
L = 25
Noise
Method
P(Y' - Y)- 0.3
P(Y" Y) 0.5
P(Y' - Y)
0.7
P(V'=X Y) 0.9
NAIVE
0.435 20.014
0.656 10.018
0.813 10.015
0.939 40.007
APS
0.413 20.018
0.626 #0.018
0.792 40.013
0.932 +0.009
RAPS
0.412 10.017
0.625 10.016
0.791 10.013
0.932 0.009
0.3
SAPS
0.425 10.020
0.635 10.034
0.802 10.014
0.934 10.009
GREEDY
0.477 0.16
0.685 000
0.832 00.011
0.956 0.0007
NONE
0.303 =0.012
0.508 :000066
0.699 10.011
0.907 10.000
NAIVE
0.417
0.640
0.803
0.937
APS
0.399
0.613 10.016
0.782
0,927
RAPS
0.398
0.612 10.016
0.781
0.927
0.5
SAPS
0.407 =0.021
0.620 .00.033
0.793 10.014
0.931 10.000
GREEDY
0.463 00.024
0.67410.015
0.824 20.012
0.953 20.007
NONE
0.281 =0.011
0.477 200009
0.669 +0.012
0.890 +0.005
NAIVE
0.396 20.005
0.606.40.018 10.018
0.770 40.011
0.925 40.007
APS
0.380 =0.010
0,587 +0.016
0.754 40.015
0.915 40.012
0.380 10.010
0.587 10.016
0.754 10.015
0.916 10.012
0.7
SAPS
0.387 10.008
0.590 1.0.000000 10.029
0.764 10.013
0.920 10.000
GREEDY
0.450
0.657 10.015
0.811 20.015
0.944 20.005
NONE
0.246 =0.000
10.011
0.574 10.011
0.798
NAIVE
0.376 10.012
0. 0.569 1000113
0.727 10.014
0.907 10.011
APS
0.367 10.014
0 0.560 110.016
0,722 10.017
0,905 10.012
RAPS
0.367 20.014
0.560 20.015
0.722 20.017
0.906 20.012
1.0
SAPS
0.367 20.017
0.556 :10
0.725 20.020
0.907 40.012
GREEDY
0.463 20.022
0.665 10.012
0.818 20.017
0.946 20.007
NONE
0.193 10.011
0.296 #0.013
0.380 +0.012
0.463 40.007
L 50
19

---

E Empirical average test coverage of prediction sets across classification tasks
In this section, we report the empirical average test coverage across synthetic and real classification tasks achieved by the prediction sets constructed using conformal prediction and our greedy algo- rithms. Table @ and Table summariizs the results, which show that the prediction sets constructed using the best conformal predictors and our greedy algorithm achieve comparable empirical coverage. Moreover, those few settings in which the prediction sets constructed using conformal prediction achieve higher coverage (e.g., P(Y" Y)= = 0.3 and 0.3), the average test accuracy achieved by the simulated human experts using the prediction sets constructed using conformal prediction lower (ef. Table D which underlines how coverage alone may be bad proxy for estimating the average accuracy achieved by human experts using prediction sets.
Table 6: Empirical average test coverage achieved by the prediction sets constructed using conformal prediction (NAIVE, APS, RAPS, SAPS) and using the greedy algorithm (GREEDY) on four synthetic classification tasks with four different (simulated) human experts, each with a different noise value For each classification task. the classifier f used by conformal prediction and the greedy algorithm achieves different average accuracy P(Y Y). For each (simulated) human expert, the best value of a for each conformal predictor is different and thus the reported coverage different. The number
of labels is I 10 and, the size of the calibration set is = 1000. Each cell shows the average and standard deviation over 10 runs. We denote the best results for each task bold.
7
METHOD P(Y" Y 0.3
P = Y] 0.5
P YJ 0.7
P\Y' YJ = 0.9
NAIVE
0.637 #0.066
0.802 20.058
0.908 10.020
0.973 00.007
APS
0.603 #0.083
0.804 10.045
0.900 #0.026
0.967 =0.006
0.3
RAPS
0.592 20.087
0.792 00.032
0.911 40.015
0.965 =0.012
SAPS
0,580 #0.067
0.794 #0.011
0.890 20.013
0.965 =0.010
GREEDY
0.502 40.024
0.764 10.019
0.920 10.012
0.976 10.004
NAIVE
0.583 10.104
0.770 10.044
0.897 10.021
0.968 10.009
APS
0.557 +0 100
0,741 =0.036
0.879 +0.010
0,961 =0.007
0.5
RAPS
0.534 #0.098 0906
0.761 #0.040
0.844 +0.043
0.950 =0.012
SAPS
0.557 10.081
0.768 20.042
0.876 10.014
0.961 10.009
GREEDY
0.489 #0.027
0.732 10.015
0.902 00.013
0.970 :0.003
NAIVE
0.535 10.104
0.676 20.047
0.823 +0.044
0.938 20.013
APS
0.519 10.115
0.661 20.036
0.853 +0.015
0.941 20.013
0.7
RAPS
0.506 #0.071
0.644 #0.056
0.813 +0.019
0.938 =0.010
SAPS
0.492 #0.079
0.721 #0.051
0.858 #0.031
0.942 00.011
GREEDY
0.473 10.017
0.696 10.014
0.861 10.014
0.958 10.005
NAIVE
0.499 #0.075
0.608 10.034
0.750 10.025
0.905 10.014
APS
0.453 40.062
0.631 #0.038
0.806 +0.026
0.912 20.013
1.0 RAPS
0.466 +0.071
0.611 20.024
0.787 #0.026
0.920 20.013
SAPS
0.484 070
0.609 20.063
0.764 E0.022
0,907 006006
GREEDY
0.457 40.024
0.664 10.015
0.839 10.014
0.951 10.006
Table 7: Empirical coverage achieved by the prediction sets constructed using conformal prediction (NAIVE, APS, RAPS, SAPS) and using the greedy algorithm (Greedy) on the ImageNet- 16H dataset. Each cell shows the average and standard deviation over 10 runs. We denote the best results for each noise level in bold.
METHOD
80
95
w = 110
125
NAIVE
0.977 10.00
0.972
10.009
0.962 10.010
0.923 10.018
APS
0.970 #0.009
0.962 +0.007
0.943 +0.015
0.887 +0.009
RAPS
0.967 +0.009
0.956 +0.007
00.007
0.944 +0.013
0.876 01.05
SAPS
0.967 10.009
0.966 1.0.009
0.946 1..000
0.921 10.011
GREEDY
0.975 10.008
0.972 10.010
0.962
0.931 10.007
20

---

Empirical conditional probability that a prediction set includes {v, 9) given ground-truth label Y y for additional classification tasks
Given a ground truth-label Y = y/ let y/ = argmax, Cy'v be the label that most frequently mistaken with y. Then, estimate the empirical conditional probability that a prediction set includes {y, ÿ) given Y = y with the greedy algorithm and conformal prediction. Figure summarizes the results for different y and P(Y" Y) values of several classification tasks where the classifier f and the simulated human expert achieve different average accuracy on their own. The results show that, the average accuracy achieved by the expert on their own worsens (y increases), the empirical probability that a prediction set constructed by the greedy algorithm includes {v, 1) decreases.
NAIVE
RAPS
GREEDY
GREEDY
SAPS
APS
SAPS
0.30
PQYY J Y 80
0.5
0.25
0.3
0.15
0.10
0.1
0.05
0.00
0,8
8.9
0,8
1
1.g
4-
5,8
P(Y' Y) 0.5, 0.5
P(Y' = 0.7, 0.7
NATVE Aps
RAAPS
CHERDO
NAIVE
RAPS
GREEDY
SAPS
SAPS
0.6
0.25
P(Y.Y S =
0.5
0.200
P(YYYE S Y
0.4
0.15
0.3
0.2
0.05
0,9
1,8
2,9
3,8
0.8
7,9
P(Y' Y) 0.5, 1.0
P(Y' = Y) 0.7,
0.5
NAIVE
RAPS
GREEDY
GREEDY
Aps
SAPS
SAPS
0.12
J IY= -Y= si
0.10
P
0.08
0.2
0.06
0.04
0.1
0.02
0=0,8= ==
y=3,y=2 1,85
0 ==2,y= y= ==9,==8
P(Y==Y) 0.7,
P(Y"=)) 0.9, 0.5
Figure 4: Empirical conditional probability that prediction set includes {y. 7) given = y with conformal prediction (NAIVE, APS, RAPS and SAPS) and our greedy algorithm (GREEDY).
21

---

G Evaluation of the Mixture of Multinomial Logit Models (MNLS)
For the group of images with w 110 from the ImageNetlóH dataset, Straitouri al. [9] have gathered predictions made by real human experts using prediction sets constructed by all possible conformal predictors with the first non-conformity score we have considered in our experiments (NAIVE), given choice of calibration set. Here, we use these predictions to evaluate the goodness of fit of the mixture MNLs used our experiments.
Figure 5 shows that the average accuracy achieved by a simulated expert following the mixture of MNLs and by real human experts using the prediction sets constructed with all possible conformal predictors, each with a different value, using the choice of calibration set by Straitouri et al. [19]. The results show that, while the mixture MNLs tend overestimates the average accuracy achieved by the predictions made by real experts, the average accuracy follows the same qualitative trend.
MNL optimum
Empirical Average Accuracy
Real humans
MNL
0.90
0.85
0.80
Real human optimum
0.75
0.0
0.2
0.4
0.6
0.8
1.0
a
Figure 5: Average accuracy achieved by simulated expert following the mixture of MNLs and by real human experts using the prediction sets constructed with all possible conformal predictors, each with different value, using the choice of calibration by Straitouri et al. [19]. We highlight in red the highest average accuracy for both the simulated and the real humans.
22

---

H Conformal Prediction under different a values
In this section, estimate the average accuracy achieved by (simulated) expert using the prediction sets constructed with conformal prediction (NAIVE, APS, RAPS and SAPS) on the ImageNet 6H dataset under different a values. Figure summarizes the results.
NAIVI
Aps
Rars
SAPS
NAIVE:
Aps
RaPs
SAPS
0.96
0.94
Empirioal Average
Emppirion Averagge
0.94
Accusuy
Autuaay
0.92
0.86
80
95
NAIVI:
RAPS
SAPS
APS
RaPs
SAPS
0.925
0.900
Eipptrioal Average
0.50
Aceuraty
0.875
Arcurary
Empirical
0.70
0.825
0,800
0.775
0.00
0.0
0.2
0.4
0.8
1.0
0.0
0.4
0.6
0.8
1.0
w 110
125
Figure Average accuracy achieved by a (simulated) expert using the prediction sets constructed with conformal prediction (NAIVe, APS, RAPS and SAPS) on the ImageNet 66 dataset under different values. Each panel shows the average and standard error over 10 runs. We highlight with red marker the highest average accuracy for the simulated humans under each conformal predictor.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the main claims made in the abstract and introduction accurately reflect the paper's 's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
The proofs of all our theoretical results are included in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experimental details are discussed in Section and Section implementation details are also described in Appendix C
The
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
25

---

Answer: [Yes]
Justification: We have released an open-source implementation of our greedy algo- rithm well the code and data used in our experiments https://githuu.... com/
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ ptapps..c/publlc/gguueeeee////// hute://////deee//eeeuubbbbn Catb///oeeeSeeaaaaaaeeee ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The training details about data splits, hyperparameters, and pre- pre-trained models are presented in Section 5 and Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For each experiment in Section 5|and Section 6
we report the suitable error
bars, standard deviations or confidence intervals depending on the table/plot. The same applies to Appendices D G and H
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
26

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The information is reported in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://aaaaaaaccppppaaaaaaacaaaa
Answer: [Yes].
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have discussed potential negative societal impact of our work under "Broader Impact" in Section 7
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
The paper does not introduce any data models with high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The authors of the existing datasets and pre-trained models used in the paper are duly cited in the main text and the asset license was respected.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
28

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not introduce assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing experiments nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
29

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "PuBhlvUJD1", "reviewer": "Reviewer_9FF1", "summary": "This paper aims to construct optimal prediction sets under which experts can achieve the highest accuracy. The authors claim that human experts cannot attain maximum accuracy with the prediction sets generated by conformal predictors. To address this issue, the paper proposes an efficient greedy algorithm based on maximum marginal gain to find prediction sets that outperform those generated by conformal predictors. The paper offers two main theoretical contributions: the first proves that finding the optimal prediction set is an NP-hard problem, while the second demonstrates that the proposed method enables experts to achieve higher accuracy than conformal predictors. Empirical results further validate the effectiveness of the proposed approach.", "questions": "1. In Figure 3, how is the Empirical Success Probability for each image calculated?\n    \n2. In line 210, why does the score function of APS discard the random variable? In other words, does the random variable affect the performance of the empirical average test accuracy?\n    \n3. Can you report the empirical coverage of the Greedy algorithm, since valid coverage is the fundamental guarantee for conformal prediction?", "limitations": "They are adequately discussed.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-motivated and easy to follow.\n    \n2. The authors provide a theoretical analysis for their motivation and offer a theoretical guarantee for the superior performance of the proposed greedy algorithm.\n    \n3. The paper presents an extensive set of experiments, including both synthetic and real data.", "weaknesses": "1. Further validation on more realistic datasets, such as ImageNet and CIFAR100, could strengthen the main points of the paper.\n    \n2. The experiments lack comparison with other classical score functions, such as Regularized Adaptive Prediction Sets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**[More realistic datasets]** The dataset ImageNet-16H is among the only publicly available datasets that we found containing multiple expert predictions per sample, a relatively large number of samples, more than two/three classes and a reasonable level of difficulty. The suggested datasets, ImageNet and CIFAR100, do not contain multiple expert predictions per sample. Another dataset for a multiclass classification task is CIFAR-10H which also has multiple expert predictions per sample and 10 classes. However, we found that the experts on their own already achieve high accuracy ($\\sim 0.95$), making it a less challenging scenario than ImageNet-16H.\n\n**[RAPS]** Following the reviewer's suggestion, we conducted extensive additional experiments using the best conformal predictors created with RAPS and SAPS [*], and we will include them as baselines in the revised version of the paper. Both methods present additional hyperparameters ($k_{reg}$ and $\\lambda_{raps}$, for RAPS, and $\\lambda_{saps}$ for SAPS), which we optimized using a held-out validation set and the procedure outlined in the original papers (e.g., see Appendix E [49]).\n\nThe empirical evaluation shows that their performance is worse than our greedy algorithm for synthetic and real-world tasks (Tables 1 and 2 of the rebuttal PDF). Moreover, RAPS and SAPS offer comparable performances to NAIVE and APS in all the tasks. The complete results can be found in the PDF attached to the general rebuttal comment above.\n\n[*] Huang, Jianguo, et al. \"Conformal prediction for deep classifier via label ranking.\" ICML (2024).\n\n\n**[Empirical success probability]** For each image $x$ and prediction set $\\mathcal{S}$, we estimate the empirical success probability using the mixture of multinomial logit models (MNLs), i.e., $P_{\\mathcal{S}}(\\hat Y = y | X=x, Y=y) = \\frac{C_{yy}}{\\sum_{y' \\in \\mathcal{S}} C_{y'y}}$, where $\\hat{Y}$ denotes the prediction by the human, $Y$ denotes the true label and, in the experiments with real data, the confusion matrix $\\mathbf{C}$ is estimated using predictions made by real human experts on their own. \n\n**[Randomization in APS]** We did not find the randomization in APS, which is just needed to achieve $1-\\alpha$ coverage exactly, to influence the empirical success probability in our experiments. Therefore, for simplicity, we decided to omit it. We will clarify this in the revised version of the paper.\n\n**[Empirical coverage of Greedy]** We will report the empirical coverage achieved by the greedy algorithm and the best conformal predictors used as baselines in the revised version of the paper. Here below we show the empirical coverage for the synthetic tasks. \n\nIn summary, prediction sets constructed with our greedy algorithm present a comparable empirical coverage with respect to the best conformal predictors (Naive and APS) in both synthetic and ImageNet-16H tasks. Moreover, in those few settings in which the conformal predictors coverage is higher (e.g., $P(\\hat{Y} = Y) = 0.3$ and $\\gamma = 0.3$), the conformal predictors' empirical success probability is lower (see Table 1 of the main paper), which underlines how coverage alone can be a bad proxy to estimate the empirical human accuracy.  Moreover, please note how the empirical success probability of the human acting alone with the full label set, that achieves perfect coverage (1.0), is always worse than the combination of human + predictions sets in all of our experiments.\n\n| $\\gamma$ | Method |   $\\mathbb{P}[Y' = Y] = 0.3$  |   $\\mathbb{P}[Y' = Y] = 0.5$  |   $\\mathbb{P}[Y' = Y] = 0.7$  |   $\\mathbb{P}[Y' = Y] = 0.9$  |\n|:-----:|--------|:-----------------------------:|:-----------------------------:|:-----------------------------:|:-----------------------------:|\n|  0.3  | Naive  | $0.637 \\scriptstyle\\pm 0.066$ | $0.802 \\scriptstyle\\pm 0.058$ | $0.908 \\scriptstyle\\pm 0.020$ | $0.973 \\scriptstyle\\pm 0.007$ |\n|       | Aps    | $0.603 \\scriptstyle\\pm 0.083$ | $0.804 \\scriptstyle\\pm 0.045$ | $0.900 \\scriptstyle\\pm 0.026$ | $0.967 \\scriptstyle\\pm 0.006$ |\n|       | Greedy | $0.502 \\scriptstyle\\pm 0.024$ | $0.764 \\scriptstyle\\pm 0.019$ | $0.920 \\scriptstyle\\pm 0.012$ | $0.976 \\scriptstyle\\pm 0.004$ |\n|  0.5  | Naive  | $0.583 \\scriptstyle\\pm 0.104$ | $0.770 \\scriptstyle\\pm 0.044$ | $0.897 \\scriptstyle\\pm 0.021$ | $0.968 \\scriptstyle\\pm 0.009$ |\n|       | Aps    | $0.557 \\scriptstyle\\pm 0.100$ | $0.741 \\scriptstyle\\pm 0.036$ | $0.879 \\scriptstyle\\pm 0.016$ | $0.961 \\scriptstyle\\pm 0.007$ |\n|       | Greedy | $0.489 \\scriptstyle\\pm 0.027$ | $0.732 \\scriptstyle\\pm 0.015$ | $0.902 \\scriptstyle\\pm 0.013$ | $0.970 \\scriptstyle\\pm 0.003$ |\n|  0.7  | Naive  | $0.535 \\scriptstyle\\pm 0.104$ | $0.676 \\scriptstyle\\pm 0.047$ | $0.823 \\scriptstyle\\pm 0.044$ | $0.938 \\scriptstyle\\pm 0.013$ |\n|       | Aps    | $0.519 \\scriptstyle\\pm 0.115$ | $0.661 \\scriptstyle\\pm 0.036$ | $0.853 \\scriptstyle\\pm 0.015$ | $0.941 \\scriptstyle\\pm 0.013$ |\n|       | Greedy | $0.473 \\scriptstyle\\pm 0.017$ | $0.696 \\scriptstyle\\pm 0.014$ | $0.861 \\scriptstyle\\pm 0.014$ | $0.958 \\scriptstyle\\pm 0.005$ |\n|  1.0  | Naive  | $0.499 \\scriptstyle\\pm 0.075$ | $0.608 \\scriptstyle\\pm 0.034$ | $0.750 \\scriptstyle\\pm 0.025$ | $0.905 \\scriptstyle\\pm 0.014$ |\n|       | Aps    | $0.453 \\scriptstyle\\pm 0.062$ | $0.631 \\scriptstyle\\pm 0.038$ | $0.806 \\scriptstyle\\pm 0.026$ | $0.912 \\scriptstyle\\pm 0.013$ |\n|       | Greedy | $0.457 \\scriptstyle\\pm 0.024$ | $0.664 \\scriptstyle\\pm 0.015$ | $0.839 \\scriptstyle\\pm 0.014$ | $0.951 \\scriptstyle\\pm 0.006$ |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1TvSIBwYpt", "reviewer": "Reviewer_Dxna", "summary": "The paper shows the conformal prediction set may not be the optimal set recommendation to humans if humans follow certain choice models. The authors then propose a greedy algorithm by modeling $P(y|x)$ and the choice model of humans assuming it follows MNL model. Authors compare the proposed method against the standard conformal prediction set under synthetic human experts and the proposed method has a slightly better performance compared to traditional conformal sets.", "questions": "See weakness.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors consider conformal prediction in the human-in-the-loop setting, which is an important problem. The first part of the paper shows the conformal prediction set may not be the best recommendation set for humans, which is easy to understand since most conformal sets arrange the set in a ranked order and we can play with the human choice models to create an example that conformal sets may not be the best recommendation set.", "weaknesses": "The problem setting is not realistic: The authors do not allow humans to select outside the conformal prediction set. However, in the setups of most empirical successes of human-AI collaboration with conformal prediction, this is allowed. Similarly, if the authors do not allow humans to select outside the conformal prediction set, humans' value is greatly reduced and the optimal thing to do may be just to use fully automated AI prediction and in all the toy examples the authors provided, kicking humans out of the loop is the optimal system (humans only make things worse). \n\nThe theoretical analysis seems useless: I think the theoretical analysis is useless for two reasons: 1) while identifying the optimal set is NP-hard, in practice the metric we care about is $\\mathbb{E} g(S|x)$, not identifying the optimal set. If an algorithm can get a good rate of convergence for this regret, then this problem is not hopeless, so I think authors need to show for all conformal prediction algorithms, what is the regret lower bound for $\\mathbb{E} g(S|x)$; 2) while I can see that sometimes the label set can be large. In practice, the theoretical results may not be a big issue for many problems since most problems have small label set (binary or three classes). This negative results may not seem that severe as the authors presented in the paper. \n\nThe solution is disconnected and not useful in human-AI collaboration: 1) The proposed solution does not enjoy the distributionally-free guarantee, which is the main reason why people use conformal prediction. I would expect authors to provide a conformal prediction algorithm that is human-centered, rather than directly switch lanes to traditional prediction methods. 2) The proposed solution requires $P(y|x)$ and the true human choice model, which is too strong to be realistic. If I know $P(y|x)$, why should I involve humans in the loop anymore (recall that authors can restrict humans only select from prediction set so humans are not necessary in the system). The optimal strategy would be directly use $P(y|x)$ to select actions. \n\nBaselines: For human-AI collaboration tasks, I expect to see the proposed solution is better than human working alone or AI working alone. The authors should compare with AI only baseline using $P(y|x)$. Based on the toy example and my current understanding of the paper, the proposed solution cannot beat AI only baseline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**[Problem setting]** Straitouri et al. (ICML 2024) [19] conducted a large-scale human subject study where they compared the setting we adopted, where users are not allowed to select label values outside the conformal prediction sets, against the setting the reviewer suggests, where users are allowed to select label values outside the sets. The results of their study (refer to Figure 3 in their paper) suggest that humans perform better under the setting we adopted, which Straitouri et al. refer to as the strict implementation of their system, than under the setting the reviewer suggests, which they refer to as the lenient implementation of their system.\n\nFurther, we would like to clarify that, in our experiments, we found that kicking humans out of the loop is **not** the optimal system (humans do **not** make things worse) in the setting we adopted. More specifically, in the experiments with synthetic data, both the accuracy of the classifier $P(Y'=Y)$ we used (shown in the top row of Table 1) and the accuracy of the human (rows under NONE in Table 1) are always lower than the accuracy of the human using the prediction sets provided by our greedy algorithm (shown in rows under GREEDY of Table 1). This suggests that even if the human has low performance overall, it may still be beneficial to use prediction sets tailored to the performance of humans rather than \"kicking them out\".\n\nIn the experiments with real data, the accuracy of the (fine-tuned) VGG-19 classifier we used ($0.896$ for $w=80$, $0.894$ for $\\omega=95$, $0.857$ for $\\omega=110$ and $0.792$ for $\\omega=125$) and the accuracy of the human working alone ($0.9$ for $\\omega=80$, $0.859$ for $\\omega=95$, $0.771$ for $\\omega=110$ and $0.603$ for $\\omega=125$), which we missed reporting in our paper, are also always lower than the accuracy of the humans using the prediction sets provided by our greedy algorithm (shown in rows under GREEDY in Table 2). In the revised version of the paper, we will report the accuracy of the (fine-tuned) VGG-19 classifier we used and of the human working alone.\n\n**[Theoretical analysis]** Our hardness analysis implies that finding the optimal prediction sets that maximize the metric $\\mathbb{E}[g(\\mathcal{S}|x)]$ is NP-hard, and even finding a prediction set that approximates this to a reasonable factor (e.g. a constant factor) is also NP-hard. As a consequence, there is no polynomial-time algorithm with a sublinear regret (i.e., a _good_ regret) with respect to the (oracle) algorithm that creates optimal prediction sets that maximize $\\mathbb{E}[g(\\mathcal{S}|x)]$. We will clarify this in the revised version of the paper.\n\nWhile there are certainly many problems with small label sets, there are also many problems with large label sets. In fact, two of the most popular benchmark datasets in the machine learning literature used by thousands of papers, ImageNet and its more commonly known subset ImageNet-1k, contain over 20,000 and 1,000 different label values, respectively. As an additional example of tasks with large label space, we mention a clinical text annotation task where each span of text has to be mapped to a _\"concept label in a large (>400,000) medical vocabulary\"_ [1].\n\n[1] Levy, Ariel, et al. \"Assessing the impact of automated suggestions on decision making: Domain experts mediate model errors but take less initiative.\" Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems. 2021.\n\n**[Distributionally-free guarantees of conformal prediction]** One of the main contributions of our paper is to demonstrate that, in human-AI collaboration, the distributionally-free guarantees offered by conformal prediction may be insufficient to achieve optimal performance. More specifically, in Section 3, we show that, under common choices of non-conformity scores, there are many data distributions for which the optimal prediction set under which the human expert achieves the highest accuracy **cannot** be constructed by **any** conformal predictor. As suggested by the reviewer, one may think of developing human-centered conformal predictors that incorporate information about the distribution of experts’ predictions in the definition of the non-conformity score. However, as argued in lines 118-122, our hardness results show that one cannot expect to fully close the performance gap with such human-centered conformal predictors.\n\n**[Knowledge of $P(Y|X)$]** Even if one knows the conditional distribution of the ground-truth label $P(Y|X)$, one may benefit from involving humans in the loop if the humans have access to additional features besides X, as pointed out in footnote 4. For instance, in the example in lines 106-117, the optimal prediction set under which the human achieves the highest accuracy does not contain the label value with the highest $P(Y|X)$ value. Further, under this prediction set, the human achieves higher accuracy than a classifier that picks the label value with the highest $P(Y|X)$ value (0.6 vs 0.4).\n\n**[Human-only and AI-only baselines]** In our experiments, both with synthetic and real data, our proposed solution is better than humans working alone or AI working alone. Regarding the comparison with AI working alone, please, refer to our previous reply under [Problem setting]. Regarding the comparison with human working alone, in the experiments with synthetic data, the accuracy of the human working alone is reported under \"NONE\" and, in the experiments with real data, the accuracy of the human working alone is $0.9$ for $\\omega=80$, $0.859$ for $\\omega=95$, $0.771$ for $\\omega=110$ and $0.603$ for $\\omega=125$, which we missed reporting in our paper and we will report in the revised version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w4PJnXKOnJ", "reviewer": "Reviewer_QrrM", "summary": "The authors first show that conformal prediction sets may not lead to human decision optimality.  The authors then introduce a greedy algorithm to generate candidate prediction sets that improve human decisions regarding the accuracy metric.", "questions": "* Typo in the title: Predictions --> Prediction\n\n* Did you include the results from the conformal prediction sets by varying the value of $\\alpha$?\n\n*  Why choose those values of $\\omega$? I think their magnitudes are close. The authors may consider even smaller and larger values of $\\omega$ to show its sensitivity.", "limitations": "Please see the above sections.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors find the sub-optimality of conformal prediction sets on providing candidates for human decisions. Thereby, they propose a novel method to produce prediction sets that helps to improve human prediction.", "weaknesses": "* The presentation somewhere is unclear: \n  * Line 86. Please break the sentence properly.\t\n  * Line 40/43/48: It is unclear for readers when the authors mention “optimal” multiple times but delay its explicit definition later.\n  * Line 197: It is confusing when the authors refer to the role of $a$. What is the value of $a$?\n\n* The authors claim they propose an efficient algorithm. However, I am not sure which part is efficient. Are there any numerical metrics, e.g., running time, supporting this contribution? Additionally, how should we understand this restriction of “for a large class of non-conformity scores and expert models” in line 51?\n\n* Line 90:  But you also miss the possibility outside the prediction set, especially when the prediction set is not that good. I think the authors need to discuss the exploitation-exploration dilemma.\n\n* The authors use the scores related to softmax and APS. Other papers propose alternative scores like RAPS and SAPS. I think they should be included.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**[Optimal]** We will define what we mean by optimal the first time we mention optimal in the revised version of the paper.\n\n**[Role of $a$]** In the generative model we used in the synthetic experiments, out of 20 features per sample, $d=4$ of these features correlate with the label value and thus are informative and the rest are just noise. In this context, \"a\" denotes the value of one of these four informative features. We will bring this information from Appendix C to the main in the revised version of the paper.\n\n**[Efficient algorithm]** The computational complexity of our greedy algorithm is polynomial on the size of the label set $|\\mathcal{Y}|$, as shown in lines 171-176 in Section 4 and Appendix B. We will clarify that, by efficient, we refer to \"computational efficiency\" in the revised version of the paper.\n\n**[Class of non-conformity scores and expert models]** The guarantees of our greedy algorithm with respect to conformal prediction (Proposition 1) apply to any non-conformity score that is nonincreasing with respect to the classifier scores $f_y(x)$ and expert models parameterized by a mixture of multinomial logit models (MNLs). We will clarify this in the revised version of the paper. \n\n**[Exploitation-exploration dilemma]** Straitouri et al. (ICML 2024) [19] conducted a large-scale human subject study where they compared a setting where users are not allowed to select label values outside the prediction sets against another setting where users are allowed to select label values outside the prediction sets. They found that, in the latter setting, the number of predictions in which the prediction sets do not contain the true label and the experts succeed is consistently smaller than the number of predictions in which the prediction sets contain the true label and the experts fail, as shown in Figure 10 in their paper. As a consequence, humans perform better in the former setting than in the latter setting, as shown in Figure 3 in their paper. Following the reviewer's suggestion, we will include such a discussion in the revised version of the paper.\n\n**[RAPS and SAPS]** Following the reviewer's suggestion, we conducted extensive additional experiments using the best conformal predictors created with RAPS and SAPS [*], and we will include them as baselines in the revised version of the paper. Both methods present additional hyperparameters ($k_{reg}$ and $\\lambda_{raps}$, for RAPS, and $\\lambda_{saps}$ for SAPS) we optimize using a held-out validation set and the procedure outlined in the original papers (e.g., see Appendix E [49]). \n\nThe empirical evaluation shows that their performance is worse than our greedy algorithm for synthetic and real-world tasks (Tables 1 and 2 of the rebuttal PDF). Moreover, RAPS and SAPS offer comparable performances to NAIVE and APS in all the tasks. The complete results can be found in the PDF attached to the general rebuttal comment above.\n\n[*] Huang, Jianguo, et al. \"Conformal prediction for deep classifier via label ranking.\" ICML (2024).\n\n**[$\\alpha$ value]** In Table 1 and Table 2, we report the results for the value of achieving the highest empirical success probability for each non-conformity score and classification task, as noted in lines 211-212 and 262-263. In Appendix G, for the experiments with real data, we report the result for all values of $\\alpha$. \n\n**[$\\omega$ values]** The ImageNet-16H dataset contains only images with the $\\omega$ values we used and thus we cannot experiment with smaller or larger values.  However, we would like to point out that, even if the levels of phase noise $\\omega$ seem close, the accuracy of the predictions made by humans on their own varies significantly among $\\omega$ values, as shown in Figure 4S of Steyvers, Mark, et al. \"Bayesian modeling of human–AI complementarity.\" Proceedings of the National Academy of Sciences 119.11 (2022): e2111547119.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hnM7bUiFtD", "reviewer": "Reviewer_trEi", "summary": "The paper analyzes decision support systems based on prediction set algorithms. The authors show that: (i) the usage of conformal prediction techniques is generally sub-optimal in terms of accuracy; (ii) the problem of finding the optimal prediction sets under human assistance is NP-hard. Moreover, they provide (iii) a greedy algorithm that is guaranteed to find prediction sets that are better than those provided by conformal predictors. Experimental evaluation on synthetic and real data show the effectiveness of the considered approach.", "questions": "I have a couple of questions/remarks:\n\n1. Can you elaborate a bit more on lines 91-93? I am not fully sure I understand the point there.\n2. Can you add the results for BRUTE FORCE SEARCH in Table 2 and Figure 3?", "limitations": "The paper adequately discussed the limitations and societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strengths of the paper are:\n\n1. the actual paper contribution is well framed;\n2. the theoretical analysis is sound;\n3. the proposed algorithm improves over existing approaches.", "weaknesses": "I think this work is a good paper, without major weaknesses, as it provides solid theoretical insights.\nThe concerns I have are mainly due to typos/details missing. I will point out here these and a few remarks that might be considered for the final version of the paper.\n\n1. It seems to me that Table 2 and Figure 3 are missing the BRUTE FORCE baseline.\n2. regarding the style of the paper, I found lines 135-146 very dense. Maybe providing a more concrete example (e.g., what could 1,2,3 represent?) might help the reader getting through it.\n3. In Algorihm 1, I think adding a comment to the pseudo-code (from lines 4 to 13) could be useful\n4. regarding the limitation section (evaluation) a useful reference might be [Stutz et al., 2023], where the authors evaluate the possibility that human experts might not be approximating the true probability distribution \n5. the experimental analysis (on real data) could be enriched with other popular Learning-to-Defer datasets, such as Cifar10H or hatespeech.\n\n[Stutz et al., 2023] - Stutz, David, Abhijit Guha Roy, Tatiana Matejovicova, Patricia Strachan, Ali Taylan Cemgil, and Arnaud Doucet. \"Conformal prediction under ambiguous ground truth.\" Transactions on Machine Learning Research (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**[Lines 125-146 & Algorithm 1]** To ease readability, we will rewrite 135-146 and we will add comments to the pseudo-code in Algorithm 1.\n\n**[Limitation section]** In the limitation section under \"Evaluation\", we will add a discussion of and citation to Stutz et al., 2023.\n\n**[Other popular datasets]** We agree that it would be interesting to evaluate our greedy algorithm in other datasets besides ImageNet-16H. However, there is a scarcity of publicly available datasets with multiple expert predictions per sample, a relatively large number of samples, and more than two/three classes. In the suggested datasets, either the performance of the human experts on their own is very high (CIFAR-10H) or the number of classes is very small (hatespeech) for decision support systems based on prediction sets to be practical.  \n\n**[Lines 91-93]** If we allow the expert to predict label values from outside the prediction set, the expert would have to decide when to believe that the true label is in the prediction set and thus predict a label from the prediction set, and when to question that the true label is in the prediction set and thus predict a label from outside the prediction set. \n\nIn this context, it is worth pointing out that, as shown in a large-scale human subject study by Straitouri et al. (ICML 2024) [19], if we allow the expert to predict label values from outside the prediction sets, the number of predictions in which the prediction sets do not contain the true label and the experts succeed is consistently smaller than the number of predictions in which the prediction sets contain the true label and the experts fail, as shown in Figure 10 in their paper.\n\n**[Brute force search]** Since the greedy algorithm achieves the same performance as brute force search, we omitted brute force search from Table 1, Table 2 and Figure 3. However, we missed to clarify that in the caption of Table 2 and Figure 3. We will clarify that in the revised version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for their careful and insightful comments, which will help improve our paper. Please, find a point-by-point response below and a one-page pdf with additional results attached.

Meta-review: All four reviewers are in favor of acceptance. They appreciated the submission's main contributions: finding that conformal prediction yields suboptimal prediction sets in terms of human accuracy, showing the NP-hardness of finding optimal prediction sets, and showing that a proposed greedy algorithm is guaranteed to improve upon conformal prediction. The theoretical nature of the last two contributions was especially appreciated. Other strengths include the experiments involving real experts and the writing being easy to follow.

The rebuttal satisfactorily addressed several issues, including the value of restricting humans to selecting from the prediction set, experimenting on additional datasets, and a comparison with RAPS and SAPS. It also answered reviewer questions, clarified some misunderstandings, and promised to report additional results, for example regarding empirical coverage and selection of $\alpha$. I hope that the authors will incorporate these elements into the camera-ready version. I do note one reviewer comment about the necessity of knowing $P(Y|X)$ and the human choice model. It would be good to comment on this in the final version.
Decision: Accept (poster)