Reconciling Model Multiplicity for Downstream Decision Making
Authors: Ally Yalei Du
Dung Daniel Ngo
Steven Wu
Venue: ICLR 2025 Poster (2025)
Keywords: model multiplicity
multi-calibration
decision-making
uncertainty quantification
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: We consider the problem of model multiplicity in downstream decision-making, a setting where two predictive models of equivalent accuracy cannot agree on what action to take for a downstream decision-making problem. Prior work attempts to address model multiplicity by resolving prediction disagreement between models. However, we show that even when the two predictive models approximately agree on their individual predictions almost everywhere, these models can lead the downstream decision-maker to take actions with substantially higher losses. We address this issue by proposing a framework that calibrates the predictive models with respect to both a finite set of downstream decision-making problems and the individual probability prediction. Specifically, leveraging tools from multi-calibration, we provide an algorithm that, at each time-step, first reconciles the differences in individual probability prediction, then calibrates the updated models such that they are indistinguishable from the true probability distribution to the decision-makers. We extend our results to the setting where one does not have direct access to the true probability distribution and instead relies on a set of i.i.d data to be the empirical distribution. Furthermore, we generalize our results to the settings where one has more than two predictive models and an infinitely large downstream action set. Finally, we provide a set of experiments to evaluate our methods empirically. Compared to existing work, our proposed algorithm creates a pair of predictive models with improved downstream decision-making losses and agrees on their best-response actions almost everywhere.

Published as a conference paper at ICLR 2025
RECONCILING MODEL MULTIPLICITY FOR DOWN- STREAM DECISION MAKING
Ally Yalei Du Camegic Mellon University aydu8andrewt cmu, edu
Dung Daniel Ngo* University of Minnesota ago0005 00000000000000 40 edu
Zhiwei Steven Wu Carnegie Mellon University zstevenwue cmu. edu
ABSTRACT
We consider the problem of model multiplicity in downstream decision-making, a setting where two predictive models of equivalent accuracy cannot agree on what action to take for downstream decision- decision-making problem. Prior work attempts to address model multiplicity by resolving prediction disagreement between mod- els. However, we show that even when the two predictive models approximately agree on their individual predictions almost everywhere, these models can lead the downstream decision-make to take actions with substantially higher losses. We address this issue by proposing a framework that calibrates the predictive mod- els with respect to both finite set of downstream decision- makinn problems and the individual probability prediction. Specifically, leveraging tools from multi- calibration, we provide an algorithm that, each time-step. first reconciles the differences in individual probability prediction, then calibrates the updated mod- els such that they are indistinguishable from the true probability distribution to the decision makers. We extend our results to the setting where one does not have direct access the true probability distribution and instead relies on set of i.i data to be the empirical distribution. Furthermore, we generalize our results to the settings where one has more than two predictive models and an infinitely large downstream action set. Finally, we provide set of experiments to evaluate our methods empirically. Compared to existing work, our proposed algorithm creates pair of predictive models with improved downstream decision-making makinn losses and agrees on their best-response actions almost everywhere.
INTRODUCTION
In many applications, individual probability prediction is central to decision decision-making. For example, in the Job Training Partnership Act (JTPA) training program (Bloom et al. 1997). decision maker may predict whether an individual employed before assigning them to training; or medical trials, doctor may predict the probability that the patient has contracted disease before recommending them a treatment. Since the hospital does not know the true probability that particular patient is ill, they can only evaluate the individual probability predictions through its average outcome sufficiently large sample set. For a predictive task, the standard convention is to choose the model that maximizes accuracy. However, previous work has shown that it is common have multiple predictive models with similar accuracy but substantially different properties (Chen et al., 2018 Rodolfa et al., 2020; D A'mour al. 2022). This phenomenon is called predictive (or model) multiplicity. line of work studied by Breiman 20011
Marx et al. (2020); Black et al. (2022).
In predictive multiplicity scenarios, ddecision-makee may have multiple models with similar accu- racy but conflicting predictions on individual samples. In our motivating example (Figure [ the hospital has access to two models f1 and f2 predicting the probability of disease which are equally accurate on average over the entire population in terms of squared loss, but their predictions on outcome prediction may have a disparate
subpopulation may vastly differ. This disagreement impact on the subpopulation if the hospital has to choose one predictor over the other to make im- portant downstream decisions. For example, they might select a treatment based on the predicted probability that patient has contracted disease. Formally, given predictive model f and decision- making loss function E(y,-), the decision-maker wants to choose a best-response action, i.e. the action that minimizes Eyy [((', a)]. When models fi and fa have nearly equivalent

---

Published as a conference paper at ICLR 2025
accuracy but lead different best-response actions, the decision-maker would not be able identify which best-response action to take for individual patients. While predictive multiplicity offers great flexibility for the decision- maker in the model selection process, it also places additional bur- den on the decision-maker to correctly navigate such freedom and justify how they use a predictive model make downstream decisions.
Roth et al. (202)) address model multiplicity by resolving prediction disagreements using techniques from multi-calibration (Hebert-Johnson et al. 2018), which aligns the mean of estimated probability with data across diverse reference groups. Specifically, Rooh et al. (2023) provide a procedure called "Reconcile" that updates the predictive models minimize their disagreements and improve the accuracy of each model. However, we show simple settings where the reconciled predictions from Roth et al. (2023) can lead the downstream decision-makern to take actions with substantially higher losses. We visually demonstrate this scenario in Figure 1 For a more detailed discussion on the limitation of prior work, see Section [.4 and Appendix [ This motivates the study of how to reconcile predictive multiplicity with explicit focus on its impact on downstream decisions.
Before Reconcile
After Reconcile
1.0
No Treatment Treatment
0.8
Pfx (0)
0.5-
0.4
0.2
0.0
Unit
Unit
Unit
Figure 1: An illustrative example of the drawback in prior work's attempt addressing model mul- tiplicity. Consider a stylized binary classification problem on a dataset with units (patients) and the hospital deciding between two actions (treatment vs. treatment). Treatment is assigned if the predicted probability is above 1/2. Left: The true probability that each patient is labeled 'ill'. Mid- dle: The predicted probability that each patient is ill according Si (white) and f2 (blue). While these two predictors have almost the same accuracy (in squared loss), their individual probability predictions for patients 3 and vastly differ. Right: After running the Reconcile procedure of Roth et al.) (2023), the individual probability predictions agree everywhere. However, the best-response action unit 3 changed from correct (no treatment) to incorrect (treatment). If the hospital uses the updated fi to make their treatment recommendation, they would incur more loss than before had they not updated the predictor using Reconcile. This example formalized in Theorem 2.7
In this work, our goal is to leverage tools from multi-calibration (Hebert-Johnson et al. 2018) to alle- viate the model multiplicity issue in high- nigh-dimensional decision- making tasks for multiple decision- makers with multiple decision-making loss functions. Specifically, we show how the decision-maker can update the input predictors they approximately agree on (1) individual predictions and (2) best-response actions for each individual in the downstream decision -akiing task. Our procedure ensures that the number of disagreements in best-response actions decreases over time, which en- ables the ceetisionmmakere to confidently use either of the updated predictors to justify their decisions.
Overview of Paper. We study the problem of reconciling model multiplicity for multiple down- stream decision-making tasks, where the decision-makers have multiple predictive models with nearly equivalent squared loss but may lead vastly different best-response actions for a signif- icant number of individuals in the population. Our key contributions are summarized as follows.
In Section 2. decision-makert
we formulate the problem of model multiplicity from the perspective of the
Section 2.4 we formalize our motivating example in Figure [ and show that it is insufficient to only update two predictive models that they have improved squared loss and nearly agree on their individual predictions almost everywhere.
In Section 3 we introduce algorithm, ReDCal, that outputs predictive models that are (1) calibrated to finite set of downstream decision decision-making making tasks and (2) approximately agree their predictions and best-response actions almost everywhere for each downstream task.
2

---

Published as a conference paper at ICLR 2025
In Section 3.2
extend our analysis to the setting where does not have direct access to the true distribution and instead only has a validation dataset with samples drawn i.i.d from the underlying distribution. We show that the guarantees obtained using the empirical distribution can be translated to the unknown underlying distribution.
In Section 3.3 we extend our analysis to the setting where one has k > 2 predictors that need to be reconciled. We provide an efficient "contestation" algorithm that only requires approximately & times more samples than the base model that reconciles 2 predictors. In Appendix F] we further generalize our result to the setting where the action space of the downstream decision-making tasks is infinitely large.
Finally, in Section we empirically evaluate the performance of the proposed algorithm on real-world datasets and show our improvement over the benchmark prior work in resolving disagreement in downstream decision-makinn making tasks.
1.1 RELATED WORK
Model multiplicity. Within the literature on predictive multiplicity, our work builds off the line of work focusing on predicting individual probabilities (Marx et al. 2020 D' Amour et al. 2022 Black
et al.
2022 Breiman 2001), where solving an error minimization problem for some prediction tasks can lead to multiple solutions with roughly similar performance in terms of accuracy. [Sandroni (0003 showed that one cannot empirically distinguish the outcomes from predictor encoding the true individual probabilities from one without in isolation, while Al-Najjar & Weinstein (2008);
Feinberg & Stewart (2008) provided comparative tests to differentiate between the true probability predictor and one that is not. Particularly, /Feinberg & Stewart (2008) relied on cross-calibration
i.c., calibration conditional on the predictions of both models to empirically falsify one of them. For downstream decision-ne citiiionnmmking,,,, [Garg et al. (219)) worked on refining predictors and provided an algorithm that produces a predictor fa that cross calbbbaal with respect to both fi and fz- An alternative framework studied by Globus- Harris et al. (2022b) seeks to update models that are sub- optimal for different subsets of the population, following the 'bug bounties' approach used by the software and security communities. Towards the same Roth et al. (2023) proposed an algorithm ("Reconcile") that aims to reconcile different predictors with equivalent errors such that the updated predictors both have lower errors compared to the initial models and approximately agree prediction on almost all units. Our work follows the reconciliation idea from Roth et al. (2023) but focuses not only the predictive accuracy but also the downstream decision- making. In our model, we consider reconciling predictors for both regression and multi-class classification problems, and their impact on the downstream decision-making tasks. In Section 2.4 we provide numerical example where simply reconciling the probability predictions according to Roth et al. (0233) can lead to additional losses downstream decision Decision-making tasks.
their
Multi-calibration. Our work draws on techniques from the growing literature on multi-calibratiin
(Hebert-Johnson et al. 2018 8) Kim et al. 2019: Dwork et al. 2019: Shabat et al.] 2020 Jung al.
2020 Dwork et al. [201]] Jung et al. [2022] Haghtalab et al. 2023 Deng et al.) 2003]] Noarov et al,
2023
Globus-Harris et al.) (2022a 2023). Multi-calibration has been used as a notion of fairness
guarantees calibration for any identifiable group. (A more detailed discussion of calibration and fair- ness is given in Appendix(A) Particularly, we leverage the connection between multi-calibration and loss minimization from the omniprediction literature (Gopalan et al. 2022b (021) in our analysis. Within the framework of multi-calibration, the work most related to ours that of Zhao al. (202T), who considered decision calibration with respect to all classes of loss functions. Similar to us, Zhao al. (20TT) takes the perspective of a decision-malee maker who wants to ensure the predictive models are indistinguishable from the true probability when they are used to make downstream decisions. However, two recision-calibratee models can still disagree on their individual predictions and best- response actions for many units. In motivating example, hospital with two predictors may still aim for consistent predictions and downstream decision recommendations (i.c. treatment or not) across the population. We formalize this example in Appendix B and provide empirical experiments to show our improvement over their result in Section
An independent and concurrent work by Globus-Harris et al. (2024) considers ensembling multiple predictive models for high- nigh-dimensional downstream decision decision-making tasks. While their work also leverages techniques from multi-calibration, their goal is to output ensemble predictor whose
3

---

Published as a conference paper at ICLR 2025
self-estimated expected payoft is accurate and whose induced policy has payoff at least high as the maximum self-assessed payoff of individual models. In contrast, our interest is in reduc- ing the downstream decision losses by resolving the differences between equivalent predictors and mitigating model multiplicity for decision-making.
PROBLEM FORMULATION
Notation. Throughout this paper, we use subscripts index different predictions, superseripts t to index different time-steps, and a to index actions. For K E N. use the shorthand [K] == (1,2.-- ... K}. ( denote the set of possible distributions over X.
We consider the prediction problem with random variables and y, where E X represents the features and y E y represents the labels. We focus on the regression problem in which the label domain is real-valued and bounded: y [0, 1j Our formulation also permits the multi-class classification problem by writing the label y as one-hot vectors.
We denote D A Y) as the true distribution over the pairs of features-label (x. y). In practice, we will not have access to D, and instead only know a set of n data points D sampled i.i.d from D. In such case, we consider the dataset D {(I1,,)).
v1). (In, Dn)) be the empirical distribution over D, which is discrete distribution that place uniform weight 1/n on each sample (xr, y) E D.
predictor a map f : X' + [0, 1jd. Our goal is to find the Bayes optimal predictor f X [0, 1] such that for all æ E X, (z) E (a.y)) [y] is the conditional label expectation given æ.
2.1 MODEL EVALUATION
Given a predictor f E [0, 1jd, we evaluate its squared error, i.e., expected deviation from the true label. We formalize this objective in the following definition.
Definition 2.1 (Brier Score). The squared error (also known as Brier score) of predictor f evalu- aled distribution D is given as:
B(J,D) (tl.//)Dllf(())) -v1
When only have dataset D (1), (In, }n)}. the empirical Brier score is given as:
B D)
2 (f(x,)) vill
Note that we use the Brier score as our metric because it can be accurately estimated given access only the samples from the distribution. Moreover, among all possible predictors, the Brier score is minimized by the Bayes optimal predictor f"
Lemma 2.2. Fix any distribution 'D and let f*(x) = (a pyyl) represent the true conditional
label encoded by D. Let f: X + [0, 1]dt be any other model. Then we have B(f D) < B(f. D).
Hence, given two predictors fi and f2, if we can verify empirically from the observable data that B(J.D) D) < B(2,, D), then we can empirically falsify that f2 encodes the true conditional label.
2.2 DOWNSTREAM DECISION-MAKIN TASKS AND LOSS FUNCTIONS
Beyond our initial goal finding a good estimate for the true conditional predictor f*, we are also interested in using our predictors for downstream decision-making problems. Formally, we consider a loss minimization problem, where the decision-man function é y A [0, dj. Wlog, we only consider finite action possible actions" In this paper, we assume that the loss function does not directly depend on the features J and linear in y. That is, for each action a A, there exists some la [0, 1]d such that
has a set of possible actions A and loss
[A], i.c., there are A
Ely, a) (y. la)
(1)
!Our technical results can be generalized to setting with infinitely many actions, i.e., |A| details, Appendix
For
4

---

Published as a conference paper at ICLR 2025
We write L = ( A + [ } to denote finite family of loss functions. We consider the setting with multiple different decision-maken each using a different linear loss function in L. For any loss function é 3/ x A + R. we can rescale each coordinate of l, to be between [0, 1].
Given a predictor ff and a loss function É, the decision-made maker selects an action a E A that minimizes the expected loss. We define the best-response policy taken by the pocision-maker as follows. Definition 2.3 (Best-response policy). Given a loss function E, a predictor f and the action set A, the best restoresponse policy for E is given as
(f(x)) = arg m
aeA
2.3 CALIBRATION
In our setting, we consider the decision-maker only having access to some pre-trained predictors given by a third-party. For instance, a data scientist trained a pair of models on an image dataset without exact knowledge of how the downstream recision-maker will such predictors. We may imagine the decision-maker as a hospital considering whether to recommend treatment to certain patients based on the predicted probability that the patient has contracted a skin disease. Since the hospital's 'ss treamment-recommedtttin we assume that the data scientists initially aim to minimize the squared error in their predictions.
algorithm is not known to the public (and the data scientist),
Since the hospital believes that the input predictors may not perform well according to their own loss function, they want the data scientist convey trust through other performance guarantees of the predictors. One such guarantee is multi culti-calibration with respect to finite set of loss functions C and set of events & on the best-response policy, i.e., if the loss function / belongs C, the decision-maker should be able to accurately compute the expected loss of choosing an action using the best-response policy xF Formally, we let (x),) x) denote the action selection events: Definition 2.4 (Best-response Events). Given a predictor f. let be the set of best- best-response events, is defined as BR (f(z)) = =a]]
where each event Er,a E & for some loss function E and action
(e,a((()) 1/2 {x :
Given a set of events E. we can define an approximate notion of Definition 2.5 (8-approximate decision calibration). A predictor f is 8 dedeissoo calibrated with respect to the set of best-response events & for all Ee, E E, we have;
with respect E.
E [((xa))Dlly - f(x)) EE,a (f). $3
This definition follows from an equivalent definition of decision calibration in Zhao et al. 202 The main difference is we define calibration with respect to a set of events on the best-respond actions following the formulation of multi-calibration for online learning in Noarov et al. (2023) and a generalization of multi-calibration in Deng et al. (2023). This definition implies that if a predictor is B- decisiio calibrated with respect to the best-response events E, then the decision-maker can accurately estimate the expected loss from using f to make decisions.
Lemma 2.6 ( (Zhao et al. (2021). For all a, E A, E L, if f is @-decissioncallbrraed with respect to the best-response events &, then the loss estimation satisfies
[(ex))D|((y, a') Et,a
xx) (fx),
E (x))))) Era(f(x)) BVd
2.4 LIMITATIONS OF PRIOR WORKS
In this section, we show that, for the predictive model multiplicity problem under decision-making improving the accuracy until the two predictors agree on their predictions almost every is not sufficient solution to our problem. In our analysis below, we consider a stylized problem with y {0. and A = {0. 1}. i.e., binary class and binary action space. A predictor here is f: X + [0. 1]. and the optimal predictor is f*) = "r(r")//>> = =1/²" = zz.. As shorthand, we denote S1 (1) as the probability of unit being labelled 1. The loss is defined as
(( = ((1, = O, E(L,0) ((0,1) 1) 1,
That is, for any v, the best-response policy is take action 0 if f(x) < 1/2 and action otherwise.
5

---

Published as a conference paper at ICLR 2025
Reconcile individual predictions. Prior work by Roth et al. (2023) considers the model multi- plicity problem for individual probability predictions. Their proposed algorithm, Reconcile (Al- gorithm B), iteratively adjusts predictions for subsets where models differ significantly, aligning predicted and true mean values. The algorithm ultimately returns a pair of predictors that has a smaller Brier score than the input predictors and approximately agree on their predictions almost all units, In the following theorem, we show that the best-response policy induced by the predictors updated by Reconcile might lead to higher expected loss than the ones they started with.
Theorem 2.7. For any a E (0, 1/s), oj E (0, 1), there exists a pair of predictors f1, f1.f2 such that after running Algorithm 3 (Reconcile), the output models f J2 satisfy (x) = f2 (x), Vx E X, but there exists a loss function such that at least one of ft. f induce worse losses compared to the original models f1, f2- That is, for some E [2].
E(a.)) [ely, x BR (87 (x)) Ely, n BR (f(()))) = 1/2> 0
(3)
Proof. Consider setting with X' = [2] and Pr(æ 1] 1 = Pr(s 2] 0.5. For any 0 < a 1/3,
let Φ 2 a, we consider the two predictors J2 defined as follows:
(1) 1/2 - 9/2, fi(2) = 1/2 - s6/2, f2(1) 1/2 + 6/2, f2( - 1/2-0/2
(4)
and the true probability of each unit being labeled are (1) = 0 and (2) 11
The Brier scores of f1 and f2 differ only by d² but their individual predictions differ for both
features x = and x = 2. We can run Algorithm 3 and patch fi to get the updated model f/ with
((1) = 1/2 + #/2 = f2(1),
FF = 1/2 f/2 = =2(
Consider the loss function E defined in equation 2 The change in expected loss after patching fi is
B(e,)) ( (zx))
E(y, - (z)))) 1/2 0.
Therefore, no matter how small a and 17 are, the loss of predictor fı increases by a constant amount.
Moreover, we provide a countercxample to show that it is insufficient to only ensure each individual predictor is approximately
using Algorithm 1 See Appendix B for details.
3 RECONCILE FOR DECISION MAKING
Suppose we are given two predictors fI, f2 : X + [0. 11dh where fi, have nearly equivalent accuracy in terms of Brier score differ in their induced decision-making policies, but we cannot falsify either of the two from the data. Informally, our goal is to return pair of models fí fi such that: (1) for both i E {1, fr is more accurate than in terms of Brier score; (2) for both i E {1, 2), the best-response policy induced by f has no larger expected loss than that of fæ; (3) Sí and J/2 approximately agree almost everywhere, indicating limited room for additional improvement.
To this end, we are interested in the region where the two predictors disagree substantially with respect to the downstream recision-making task. We define the disagreement region as follows: Definition 3.1 (Disagreement Event). For f1, fz. margin a > O. and a loss function E, the disagree- ment event is defined for pair of best-response actions a1, 01,02 AA where 01 F a2
(1))), = 1 x E {ar : BR (J1 = a1, m
BR (f2(z)) = .22
(fi(z), - lo,) > a or (f2(2), las - laz) > at}p
As shorthand, we denote Fie, (x) = F.g ag (z) f2(x), x)) when the predictors fi, S2 and the margin a are clear from context. For finite family of loss functions L, we can always iterate through L to identify the tuple (E, a1, a2) that defines disagreement region between fi and fz.
We say the two models approximately agree with each other when the size of the disagreement event is small enough, i.e., its probability mass p( (zg)) on the underlying distribution ' is small. Definition 3.2. (Probability Mass) Under distribution D, the probability mass μ(E) of event E
((FF) = Pr
[x = 1).
(s.g)~>

---

Published as a conference paper at ICLR 2025
3.1 THE RECONCILE PROCEDURE
In this section, we propose our main algorithm ReDCal (Algorithm 2). Whenever the decision-
maker observes a large disagreement event Eg the best-response action and its corresponding expected loss given by at least one of the predictors must be incorrect. For example, at time step I and unit æ, if the gap between the losses of taking d1 and 0g according to f2 substantially different from the loss gap observed on the data, then the decision-man makerr can induce that fe must have been wrong in its prediction for x. Then, the
would want to 'patch' f2 this time-step.
The calibration procedure within each time-step is divided into two stages. In the first stage, we update model fz f32 by minimizing the mean prediction eтror on the disagreement event, i.e., min- imizing [((l
Er.ay ,az (1) = I]]. Following the intuition from multi-calibration, this update operation would improve the Brier score and produce a more accurate predictor. However, the up- dated model f/2 is not guaranteed to induce the correct best-response action and could instead induce some other actions that might lead to a larger expected loss. To cope with this, in the second stage, we further update f/2 to model fi that is approximately decision-calibrated within event Eg using Algorithm [ Since the loss estimation given by f² is accurate for all best-response events within Eg and best-response action induced by f2 The formal description of the algorithm is given by Algorithm 2
taking actions to minimize estimated loss,
now safely take the
Algorithm 1: Decision Calibration
Input: Predictor f, loss family C. 3 > 0, event E
1: Let f f.
2: while f is not 6-multicalibrated with respect to events E n E for some E L do
3: Let L", "²,at arg max (E<a,))>>ly El
4: Let Ø² ( y - (x) a (f) =1
5:
Patch (x)((x) = pr (f'(z) & Ex (f((),,))
6: 1= 1-1+1.
Output: fr
Algorithm 2: Reconcile Decision Calibration (ReDCal)
Input: f1. f2, L, n 0, > 3.3 > 0
1: Let / f1,
f2 and f = O.
2: while μu( (F 2 n) for some ag, a2 E A and l do
3: Let lt of, a = arg max ((E E² Ee
4: Pick
8 = arg max sE(1,2)
E (( 1 (v,
(v. (v. =
- E (c (f((z), (1) (f((s), ob)l = 1|}.
5: Denote fút as f.. Let 0¹ (layy
1| E (x) iI.
6: Patch f'(x) pf (x)).
7: Let sf p++1_ Decision- CiiiiionCCalibrationnff L. B. E²), t=1+1.
Output: fi.
We provide the theoretical guarantees of our proposed algorithm below. At a high level, Algorithm 2 produces a pair of models with improved accuracy and approximately agrees on the best-response action almost everywhere. Unlike prior work in model multiplicity. our theoretical guarantees in this section (and their extensions in later sections) do not require the input predictors fi, f2 have similar accuracy. Using techniques from multi-calibration, our proposed algorithms can reconcile predictors with distinct accuracy, which could be beneficial to downstream decision-mate makerss depend- ing on the context. For the formal proofs of Theorem 3.3 see Appendix [
Theorem 3.3. For any pair of models fi, fa X + [0, 1]d, any distribution D, family of loss functions L. on set of action A satisfying A A, any loss margin a > O, disagreement region
7

---

Published as a conference paper at ICLR 2025
mass yi O, and decision-calibration tolerance O, Algorithm 2 updates f1 and fa for T1 and Ty time-steps, respectively, and outputs a pair of models (fi :1 such that:
1. Algorithm terminates within T= = + 4.d.(Bi5 D time-steps.
a'1)
2. The Brier scores of the final models are lower than that of the input models (f1, f2):
BfA, D) & B(f. - Ti n/n/ (4d) and B(f2 D) S B(f2.D) -T2 a² (4d)
3. All the downstream decision- losses of the final models do not increase by much compared to that of the input models (Ji, f2): for each i E [1,2] and for all E L.
() [0yy, BR (ft (x)) Ex (yy, Tt BR (fi(z)) S T,BVAA
4. The final models approximately agree on their best-response actions almost everywhere. That is, the disagreement region Et,ar,02 calculated using fi f2 has small mass. VE L.
Ju {L <n for all 01, 02 E A s.I 01 + 0/
Remark 3.4. In the third result of Theorem 3.3 the increase in downstream decision-making loss at each time-step only depends on the decision-calibrat tolerance B, dimension d, and number of actions A. Since the total number of time-steps does not depend on B, can set B a/TVOA to ensure the loss of taking the best-response action does not degrade by more than a. Moreover, we empirically observe that the loss only increases minimally.
in Section 4
3.2 FINITE SAMPLE ANALYSIS
In Section 3.1] we have presented an algorithm, ReDCal, to reconcile two predictors with similar
makers have direct access the probability distribution D. In Brier scores, assuming the will only have a dataset D = { .......... (x Bn)} containing practice, the i.i.d samples drawn from D. In this section, we will instead run Algorithm [ on the empirical distribution over D) and show that its guarantees can translate to the underlying distribution 'D with high probability. To prevent data leakage, we assume that the dataset is drawn independently of the predictors fi and f2. i.c., the dataset contains freshly drawn data that not used to train either of the predictors that we want to reconcile. For the formal proofs, see Appendix D
At high level, since the samples in D are independently and identically distributed, can ap- ply Chernoff-Hoeffding inequality to show that, with high probability, the in-sample quantities are approximately equal to sut-sample quantities. We summarize the results in the theorem below.
Theorem 3.5. Fix any distribution D and dataset D containing n samples drawn i.id from D. For any pair of models SI, f2 X + [0, 1]2, family of loss functions L set of action A satisfying tolerance
[A| = A, loss margin a >> O, disagreement region mass 1) >> O, and > 0, Algorithm run over the empirical distribution D updates fi and fa for Ti and T2 time- steps, respectively, and outputs a pair of predictors (ST [2 such that, with probability at least
1 8 over the randomness of D D
The total number of time-steps for Algorithm 2 and Algorithm iis
T Ti + T2 2d/ min /4d}]
2. For i {1,2], the Brier scores of the final models are lower than that of the input models:
BITT D) B(f. (T, -) min 132.no² (4d)
3. For i E 21 and for all E C. the downstream decision-making losses of the final models do not increase by much compared to that of the input models:
B((za))D(((( BR(
(ST (x)) - Ely, at BR (f(())) S 2T.3VdA
4. The final models approximately agree their best- best-response actions almost everywhere. That is, the disagreement region Ex calculated using ff J has small mass: VI C, p ((Er,a),ag) 2n for all aı, as E A s.1 01 a2
in 2 22 (1///1/ min min (In(dA)2) In(ō min (a)))))))
8

---

Published as a conference paper at ICLR 2025
3.3 EXTENSION TO RECONCILING MULTIPLE PREDICTORS
In the previous sections, we addressed reconciling two predictors for downstream decision-making tasks. When there are k >> 2 predictors that need to be reconciled, straightforward approach to generalize our previous analysis is applying ReDCal iteratively until each pair among the i pre- dictors "agrees" on their individual prediction and best-response action. However, since there are O(k2) pairs of predictors and this approach requires fresh calibration data for each new reconcilia- tion procedure, the data requirement significantly increases.
Another approach is to simply apply ReDCal (k-1) times for each new predictor. However, running ReDCal sequentially does not minimize disagreement among all predictors. For instance, initially reconciling fi with f2 minimizes their disagreement, but after fi undergoes further reconciliations with other predictors, its updated version Jí may still end up disagreeing with for sufficiently many units. This disagreement indicates falsification potential and suggests room for further im- provements in fi.
To address these challenges, we introduce a "contestation" method. We select a base model, f. and focus updates events where f disagrees with the other models, fz- Using Definition 3.1
disagreement event ii az (z))), x) in this setting is identified by pair of actions (01, 42), a Ioss function f, and contestant predictor fj. At each iteration, we select the disagreement event with the largest size and "patch" the model whose estimated loss the event has larger error. The detailed algorithm is written in Algorithm and theoretical guarantees are in Theorem E.
To maintain the same guarantee in Theorem 3.5 need roughly i times more samples for Algorithm 4 compared to ReDCal. Since each iteration decreases the Brier score of one predictor, the cumulative number of necessary updates across predictors, i.c., the total number of time-steps, is approximately multiplied by (kk). The sample complexity then scales up only linearly with k. The detailed algorithm, formal theorem, and its proof are in Appendix
4 EXPERIMENTS
In this section, we complement theoretical results with of experiments real-world datasets to show our improvement in decreasing decision-making loss compared to prior work.
4.1 IMAGENET MULTI-CLASS CLASSIFICATION
Experiment Setup. We use the ImageNet dataset (Deng et al. 2009) and two pre-trained models provided by py Porch (inception-v3 (Szegedy et al. 2015) and resnet50 (He et al.] (015)). Among the 50000 validation samples, we use 40000 samples for calibration and 10000 samples for testing.
We investigate how the downstream decision loss changes with the four calibration algorithms: Reconcile (Algorithm{3) 33. DeciisionCCalibration (Algorithm[]} ReDCal (Algorithm 2 and the com- bination running ReDCal after Decision Calibration as post-process. We run each calibration algorithm 500 times. For each run, we first randomly draw 100 classes from the 1000 classes of ImageNet. Then, we randomly generate a loss function such that, for each y E y, a E .A, Ely, a) ~ Normal(O, 1). For each randomly generated loss function f, we compare the expected losses derived from the best-response policies based on predictors fi and fo against those based on the optimal predictor f" Formally, the loss gap at timestep / using predictor Si is defined
LossGap(f!) = B(zaa)=Dllly B (f(()))) E(y. T (f*())))
The hyperparameters chosen follows: loss margin a 0.001, disagreement region mass 0.01, decision-caliibattion tolerance B 0.00001, and the number of actions K = 10.
The results shown in Figure Compared to Reconcile, ReDCal converges within similar number of time-step and decreases the loss by larger amount on the test dataset. Moreover, ReDCal further decrease the loss when used post-proces:, after Caalibraaoiiooiiooon terminates.
Results.

---

Published as a conference paper at ICLR 2025
Predictor Test
Predictor Test
Predictor "est
Predictor Test
1.525
Dedision Coep.
1,500
1.450
1,125
0
10
20
30
40
50
10
20
30
40
50
10
20
30
40
50
30
20
30
40
50
Timesseps
Timesteps
Timesteps
Timesteps
Reconcile
ReDCal
DecisienCallbratonn
Figure 2: ReDCal decreases decision loss on Imagenet. We plot the gap between the average loss of each predictor and the optimal loss had known the true predictor f the test set. Left two figures: We compare the LossGap of ReDCal (orange) with Reconcile (blue). Compared to Reconcile, our algorithm converges similar rate and decreases the loss by larger amount the test dataset. Right two figures: We compare the LossGap of Decision-Calibration (green) to that of Docision-Calibratiin improve upon Decision-Calibratie Calibration output predictors and further reduce the loss on the test dataset. Results are averaged over 500 runs and the shaded region indicates #1 standard errors.
with run of ReDCal as post-process (red). Our proposed algorithm can
4.2 HAM10000 MULTI-CLASS CLASSIFICATION
We use the HAM10000 dataset (Tschandl et al., 2018) on pigmented skin lesions to predict the probability that a patient has contracted one of possible skin diseases. The results are shown in Figure
For detailed description and discussion of the results of this experiment, see Appendix G
Predlccoo Test
Predictor 2 Test
Predictor That
Predictor 2 Test
0.40
Decision Loss Gap
0.38
0.34
0.32
10
20
10
Timesteps
limesteps
limesteps
limesteps
Reconcile
ReDCal
DecibionCClltraation
DecisionnaalireeiooRRDDaa
Figure 3: ReDCal decreases decision loss on the HAM10000 dataset. The comparisons and results similar to that of Figure Results are averaged over 10 runs and the shaded region indicates #1 standard errors.
CONCLUSION
Predictive multiplicity is phenomenon in machine learning where the decision-makers have multi- ple predictors with nearly equivalent squared loss but vastly different individual predictions. Lever- aging technique from the multi-calibration literature, we propose an algorithm, ReDCal, that up- dates a pair of predictors until they approximately agree almost everywhere on (1) individual pre- dictions, (2) best-response actions in the downstream decision-making task, and (3) following the best-response actions incur losses that are close to the optimal loss. We further generalize this result to the settings where one has more than two predictive models and infinitely many possible down- stream actions. Our theoretical results help alleviate the problem of predictive multiplicity in model selection. Finally, we provide experiments using real-word datasets to show that our proposed al- gorithm achieves lower decision loss compared to existing work. While do not provide examples of domain- speciffc loss functions as part our analysis and experiments, we hope that our findings can aid future studies on the impact of model multiplicity in decision-making.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Z. S. W. and D. D. N were supported in part by NSF grant 1952085 and STTR grant.
REFERENCES
Nabil Al-Najjar and Jonathan Weinstein. Comparative testing experts. Econometrica, 76(3);
541-559, 2008. ISSN 00129682, 14680262. URL htttp://www. http://wwwwwj..oooooooo www.:rattoors.oo....oo.o otttor.org//table/ 40056456
Emily Black, Manish Raghavan, and Solon Barocas. Model multiplicity: Opportunities, concerns, and solutions. Proceedings of the 2022 ACM Conference on Fairness, Accountabilitty and Transparency, FAceT "22. pp. 850-863 New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978 4503935355
doi: 10. 10.1145/331146633331449
URL https://doi.
org/10. 1445 3531 1 3533149
Howard S. Bloom, Larry L. Orr, Stephen H. Bell, George Cave, Fred Doolittle, Winston Lin, and Johannes M. Bos. The benefits and costs of jtpa title ii-a programs: Key findings from the national job training partnership act study. The Journal of Human Resources, 32(3):549-577, 1997. ISSN 0022166X.
www. jstor hrggstaable/14600
Leo Breiman. Statistical modeling: the two cultures. Statist. Sci., 16(3):199 2001. ISSN 0883-4237. doi: 0t.1224//s/100211133
URL http::/ http:://xxxco..org//./... wwt.:c....rg/1.111444/8880/9 With comments and rejoinder by the author.
1009213726
Chaofan Chen, Kangcheng Lin, Cynthia Rudin, Yaron Shaposhnik, Sijia Wang, and Tong Wang. An interpretable model with globally consistent explanations for credit risk, 2018.
Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D Hoffman, et al. Underspecifica- tion presents challenges for credibility in modern machine learning. Journal of Machine Learning Research, 23(226):1-6) 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009. doi: 10.1 L09/CCVR.20099520666...
Zhun Deng, Cynthia Dwork, and Linjun Zhang. method, 2023.
Happymap:
A generalized multi-calibration
Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Learning from outcomes: Evidence-based rankings. In 2019 IEEE 60th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 106-125, 2019. doi: 10//FOCS.2009.00000
Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Outcome indistinguishability. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, STOC 2021, pp. 1095-1108, 1108, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 9781450380539
doi: 00.11457340632534451666 URL https://doi.
org 10. 11 4 34 630..63322..0 011133446335.55550633 3451064
Yossi Feinberg and Colin Stewart. Testing multiple forecasters. Econometrica, 76(3):561-582, 2008. ISSN 00129682, 14680262. URLhttt:://wwe http:////tw......oooro/tttllllee
Sumegha Garg, Michael P. Kim, and Omer Reingold. Tracking and improving information in the service of fairness. In Proceedings of the 2019 ACM Conference on Economics and Compu- tation, EC '19, pp. 809-824, New York, NY, USA, 2019, Association for Computing Machin- ery. ISBN 9781450367929. doi: 10.1145/3328526.322222 33399624
URL httpt::tt//sete /tt.///i.........ooo/o
1145/3328 011.33222226336268232222 3329524
Ira Globus-Harris Varun Gupta, Christopher Jung, Michael Kearns, Jamie Morgenstem, and Aaron Roth. Multicalibrated regression for downstream fairness, 2022a. URL :ttttps///rxi>>
:
brrg/bb// 2209. 07312
11

---

Published as a conference paper at ICLR 2025
Ira Globus Globus-Harris, Michael Kearns, and Aaron Roth. An algorithmic framework for bias boun- ties. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT '22, pp. 1106-1 1106--1226 124, New York, NY. USA, 2022b. Association for Computing Machin- ery. ISBN 9781 45039352..
doi: 10.1 10.1145/3531 146.3533172. URL httpps://ooi..otttt
1145/353 3536112
Ira Glrrus,Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. Multicalibra- tion as boosting for regression, 2023.
Ira Globus-Harriss Varun Gupta, Michael Kearns, and Aaron Roth. Model ensembling for con- strained optimization, 2024.
Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Om- nipredictors, 2021. URL wtt.::ttss//// hattpss//axx....rr///////0000000
05389
Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder. Loss minimization through the lens of outcome indistnguishhability 2022a. URL https://arxiv.er abs/
22100.88 08649]
Parikshit Gopalan, Michael P. Kim, Mihir Singhal, and Shengjia Zhao. Low-degree multicalibration, 2022b. URL
01255
Nika Haghtalab, Michael I. Jordan, and Eric Zhao. A unifying perspective on multi-calibration: Game dynamics for multi-objective learning, 2023.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition, 2015.
Ursula Hebert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Cal- ibration for the (Computationally-denniiii
masses. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1939-1948. PMLR, 10-15 Jul 2018. URL htttss://proceed.ngg mlr press/ http://////bbbbebbbebeeeeeeeeeee jownerttttooosonnooom 1a..
Lunjia Hu, Charlotte Peale, and Judy Hanwen Shen. Multigroup robustness, 2024. URL https:
//axxiv.rr/aab// 00614
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks, 2018.
Christopher Jung, Changhwa Lee, Mallesh M. Pai, Aaron Roth, and Rakesh Vohra. Moment multi- calibration for uncertainty estimation, 2020.
Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Batch multivalid confor- mal prediction, 2022.
Michael P. Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, AIES 19, pp. 247-254, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781 450363242. doi: 10.1145/330661 org/100 11 30045/3336610 3314287
URL /ttpp:://doi.
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs the fair determi- nation of risk scores, 2016. htt.:http://aaaa
//t.vvv//vi/v////. wwtp:/wwwwww//////./..50030 05807
Yiqi Liu and Francesca Molinari. Inference for an algorithmic fairness-accuracy frontier, 2024.
URL hRR.httpp::/acxxvvoorg 24000 08879
Charles Marx, Flavio Calmon, and Berk Ustun. Predictive multiplicity in classification. In
Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6765-6774. PMLR. 13-18 Jul 2020. URL https: bttps://proceeding/ mmrr. wwwppppwwsss.epeepe.p.ppppawpeee html
12

---

Published as a conference paper at ICLR 2025
Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. High-dimensional prediction for sequential decision making, 2023.
Kit T. Rodolfa, Erika Salomon, Lauren Haynes, Iván Higuera Mendieta, Jamie Larson, and Rayid Ghani. Case study: predictive faimess to reduce misdemeanor recidivism through social ser- vice interventions. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, FAT* '20, pp. 142-153, New York, NY. USA, 2020, Association for Com- doi: 10.1145/3511995337786.. URL https:
puting Machinery. ISBN 9781450369367.
//doi. oogii.rrg/00 11 45/3311311000 095 3372863
Aaron Roth, Alexander Tolbert, and Scott Weinstein. Reconciling individual probability fore- casts. In Proceedings of the 2023 ACM Conference on Faimess, Accountability, and Trans-
parency. FAceT '23, pp. 101-110, 10, New York, NY, USA, 2023. Association for Computing Ma- chinery. ISBN 9798400701924.. doi: 10.1145/3593013
URL https: //do1. .rgg/
10.
Guy N Rothblum and Gal Yona. Multi-grow agnostic pac learnability, 2021. URL https://
arxiv. www.worggaaae abs 2105. 09989
Alvaro Sandroni. The reproducible properties correct forecasts. International Journal of Game Theory, 32(1):151-159, 2003. URL httph:tt//// Btttes////ooPaapeeeee rwpec. org/ RRPPc::PPPP:: spr:
Eliran Shabat, Lee Cohen, and Yishay Mansour. Sample complexity of uniform convergence for multicalibration. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 13331-13340, Curran Associates, Inc., 2020. URL https::/proceediinrrrr wwwpinngg..euurrae www.wnuurr...... wwtppippppcppppppprreeee
Xudong Shen, Yongkang Wong, and Mohan Kankanhalli. Fair representation: Guaranteeing ap- proximate multiple group fairness for unknown tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):525-533 January 2023. ISSN 1939-3539. doi: 10.1 10.1109/tpami.
2022.3148908 URL http: /xx wow.doo....oo..oooooooo..oo..o.. 10 1109 TPAMI 2022. 3148905
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jonathon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision, 2015.
Philipp Tschandl, Cliff Rosendahl, and Harald Kittler. The ham 10000 dataset, large collection of multi source dermatoscopic images of common pigmented skin lesions. Scientific Data, 5(1), August 2018. ISSN 2052-4463. doi: 2..1038/sattt.201... 10. 1038/038/500 sdata 2018.18
URL httt:://dd..k doi. org/
Shengjia Zhao, Michael Kim, Roshni Sahoo, Tengyu Ma. and Stefano Ermon. Calibrat- ing predictions to decisions: A novel approach to multi-class calibration. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang and J. Wortman Vaughan (eds.), Advances in Neu- ral Information Processing Systems, volume 34, pp. 22313-22324 Curran Associates, Inc.,
2021. URL
cc ccppaper. comeer_filess filles/pappe//201/
APPENDIX
A ADDITIONAL RELATED WORK
Within the literature on multigroup fairness, Kleinberg et al.) (2016) highlighted the trade-offs in fairness by proving the incompatibility of three key fairness conditions-ccalirattoon positive class balance, and negative class Balance-emphasion Building on these foundational insights, Kim et al. 2019) introduced multiaccuracy. This post- processing technique ensures consistent accuracy across subpopulations without access to group labels, laying the baseline for future work on predictive fairness. Following such framework, RRoth blum & Yona (202)) extended the PAC learning paradigm multi-group scenarios. Shen et al.
the need for prioritization in fairness criteria.
13

---

Published as a conference paper at ICLR 2025
proposed framework for fair representations across multiple fairness notions and unknown tasks. More recently, Hu et al. (2024) explored robustness multigroup faimess and proposed
2023
algorithms tailored for subpopulations under data corruption. Liu & Molinari (2024) proposed
method to estimate the fairness- fairness-accuracy frontier for testing fairness in decision-making. Another line of work (Haghtalab et al. (023) connects fairness and optimization with unified game theo- retic framework. However, our work does not focus on the fairness aspect of multicalibration but instead borrows its techniques.
B LIMITATION OF PRIOR WORK (CONTINUE)
We provide the Algorithm 3 from Roth et al. 2023 and their theoretical guarantees for completion. First, given two predictors J1 and f2, define the disagreement region as:
U.(fi, fe) == fx (f((z) - f2(x)] >
which can be further divided into two partitions:
U.² (f). = far E (.(. fi(x) > fa(a)
(2) = far E. (1()) < </(2))
Algorithm 3: Reconcile (Roth et al. 2023)
Input: Si. J2, 0, 0
1: Let f f1. = f2.
2: while (f, f(1
7 do
3: For each {>, <} and i [1,2), let:
Elyl> U. f2)] of (x] ( [2))
4: Let
(ic: .))
((((F))))))) (o. =2²² (E(1.2)
arg max
breaking ties arbitrarily.
5: Let:
9c(x) {
U
otherwise
6:
Let
Å, ((x))) (v)er(x)) 1]- B( (x)la(())
A Round (Aii))
7: Let (1: projjo. (1. (.gr( 4 Output: (fa) sta)
Theorem B.1 (Reconcile (Roth al. 2023
) For any pair of models f1. X + [0. 1), any
distribution DD and any a, >> O, Algorithm runs for T Ti + T2 many rounds and outputs pair of models (fT 3 (T2) such that:
T < (B(fi, D) + B(f2, D))
na²
2. B( D) < B(f. D) Ti ya² and B(f D) < B(fe. D) T3 16
3. (( ,)²))) Sn
14

---

Published as a conference paper at ICLR 2025
Furthermore, provide counterexample that shows ensuring each individual predictor is decision-calibrated by running Algorithm is not sufficient.
Dacisien predictions. Another baseline algorithm consider is to Algorithm separately for both f1, f2. However, in the following theorem, we show that the updated predictors f' and f/2 still disagree with each other the best-response actions for substantially many units, indicating room for further improvement.
Theorem B.2. For any di (0, 1/4) and 3 (0, 1/2), there exists a pair of predictors fi, f2 and a loss function l, such that after running B-ddeision-calibrated
(Zhao et al. (022), the resulting models fi f2 are B-decision calibrated with respect to the loss function There exists set of
units x with probability mass 2n where fi and f2 disagree on the individual best-response actions.
Proof. For any n E (0,, 3 E 1/2). let X = [4]. with Pr[[] = Pr[4] = 1/2 17 and Pr(z
= Pr(z 3] 77. Consider the predictors f1 f2 follows:
f((1) f1(2) f2(1) f2(3) 8
2m3 + 2n.
(5)
f1(3) f1(4) = (2( f2(4) = -1- B
(6)
2
(*(1) = 8
3
(*(2) - (3)
2'
2
Notice that
8 2//3 + 21
-+ + 2n(1 - 8) < 7 -
4
The best-response policy for each predictor is
t BR (f)()) Ni BR (fi =0, T7
BR (fi(3) (fi 1,
(8)
BR (f2(1)) 7
nH.
TT (fz(3)) 0, Ty
BR (f2(2)) - (fi(4)
(9)
For each best-response event, we have
E(a.)> [f (x) E, (f)) = E (/) (Si (x),
((,))~ f (z) [f
(2()(
D (f)
(e f (x) Bi (f2(x), ((..) ((c
E ((an)> (z) [2) Bun.))-ol(((c)))55(()))...
That is, fi, f2 are already decision-calibrated, running Decision Calibration will not further im- prove either of the two predictors. However, based on our definition of disagreement events, we still have
E1.2 [2], E2,1 {1}.
each with size
=(E)))=:(Baa) (B2,1)
we observe that f1 and f2 still disagree on the best-response action for units x = and x 3. We can further reduce the differences in best-response actions using algorithm Algorithm
However,
C PROOFS OF SECTION 3.1. RECONCILE FOR DECISION MAKING
First, we show that if disagreement event has a large probability mass, then least one of fi, f2 has a large prediction error within the region: Lemma C.1. Fix any two predictors fi.f2 X 1] and a, > O. If ((E n for some 01, 02 E A. then we have
E [f((x) Er,
(x)] 12 a 2dd
(10)
for some i (1,2).
15

---

Published as a conference paper at ICLR 2025
Proof. By definition of event Ei,01,02 we have
E ((()(()), ((f((x))
((f2(x). +(((()))) - (2) Ee (2)] 20
Also, we have
Ex [((f(()), 02) - ((]((x))) 01)
Ex [(f(()) f2(x), faz lai) Li [x)]
Ex x Kff(z)= fx) la Ee,0r (x)]
+ Bxxx (z) - f2(x)), laz - lai |Ee
E [f( - (x) (((x))EE,,o) Et, (z)] 112vd || [f((z) ff (o) lleva
=vd. (|Ezax [f(()) f (z)) as, (z)] la + | [fa(x) f (x) Ee az (x)) l12)
where the last inequality comes from Cauchy-Schwarte Schwartz and that is bounded in [0. 1). Combining the above inequalities, we have
Vd- (||Ex>x (x)) az + +||Eaax [f2(x) - (x) aa 2 a.
Therefore, for some E (1, we have
BZwx [f(()) (L 2Vd
This lemma indicates that, if we have two predictors fi, f2 that create large disagreement event, we can falsify at least one the models. We now show that these events also provide a directly actionable way to improve one of the models.
Lemma C.2. For any predictor
X' + [0, 1ja. any event E E, and distribution D. Let (aas))--l-f(((EBB33 Exx) = 1]. We patch f as
E B(z.))-Dy -
f'(x) pjoojo.naa(( + @F(())), where projoo.jady)
arg min |yy y'1l2. v'Elo,11a
Then,
B(JD) -UJ,)) (Io))
Proof.
B(FD) - -( =B [1]((x) 211 (1) v1ž
2B (1l((r) - -112 [lf(z) + (ε(x)) v1
(since projection is non-expansive)
= [2(v ((x) - [(FF())
2|00|12 (FFE)
Therefore, whenever we have two predictors that have large disagreement event, we can always falsify at least one of the predictors and improve through patching, causing the Brier score to decrease by a large amount. Similarly, for fixed predictor, if one of its best-response events has large calibration error, we can patch the predictor within the event to decrease the Brier score. As the Brier score is bounded in [0, d], these two observations imply that the number of time-steps for both Algorithm 2 and its subroutine Algorithm I are bounded.
Other than the Brier score, also about minimizing the loss of the downstream decision- making task. We now show that, after a further update through the subroutine Algorithm [ the loss does not increase much each time-step of Algorithm
16

---

Published as a conference paper at ICLR 2025
Lemma C.3. For any predictors fi. f2. loss function & L and any distribution D, any time step t of Algorithm 2 the predictors satisfies
E(ay)D [ey, ni u (x))) - Ely, (f(+)))) SBVdA,
BR 1
for all E (1,
Proof. At each round, define the set 4/ E²
A = fo E² T (f(+(((()) a}.
Then, we have
(D lly Te @ ( (x))) Cyy - (f)))
E (an)) - Ely, (z)) REA
For each term in the summation, we can upper-bound it as
E E(a.)) Ely. (x))
(11)
-l (x)), lai)
(Linearity of Expectation)
<X 1st (z) (z)), la²) + BVa <3vd.
(Since f++l is 3-calibrated)
(Since a is the new Best-response action)
Summing these actions together, we have
E( (aly) oe Ut+ - Ely, me BR (f(o)))) S BVdA.
(12)
n
Instead of setting a fixed 3, we can calculate a different 3 at each round, which allows a smaller increase in loss.
Lemma C.4. At each round t, if at is not the best action on Et in average, i.e.
8 max B(e,)) al,, > 0,
aEA
then we can set S 8t/ /d, such that
B( BR
Ely, x BR (f+(())) So.
Proof.
We can write the change in loss at each round as
((n [lly, TH BR ( (z))) E(y, nt BR (f(x))))
-B( ((v,, 7H
(f++(())) - Ely, [x))
-E(a.y)-D pllyy n. BR (x))) - -E(y, a')) ((). - Ely, E'))]
Σ E ( ( (f(y)
-(( ((y.dd)) (x) E. E ()) (x)),
AEA
for any a' E A.
We can use the same analysis in Lemma C.3 to get
Σ E(eg) a) ((y,a')))((()) s 3'Vd.
For the second term, we would want the loss be small as possible, so we can choose a' arg min ((x.)))((((.aa) (x)) and let
aEA
8 - -EE,g))D(((((... Ely, ((),
(13)
17

---

Published as a conference paper at ICLR 2025
then 8 is maximized and 8 2 by definition.
The total change in loss in this round can be written as
B(x.a)-D(((()
me FR (f!+ (z))) fly. TE (f()) < 3' 3 8
If 8 > 0, we can set B 2 8 3 to ensure the loss does not increase at this round.
C.I PROOF OF THEOREM 3.3
Proof. By Lemma C.I and C.2 for any i 21, at time-step we have the inequality
a²n
B) - B(ft
ft ,D) 2
4d
Taking the sum over all time-steps, we have for any i E {1,2},
a²11
B(f, B(J D) T;
4d
Since the Brier score is always non-negative, we have
4d B(f,D)
T,
a²1
Second, using Lemma C.3 and summing over all time-steps, we have
E (a.y)~l(((() ( (f/ (z))
( (o 2R (ff(z))
(14)
Σ The = i) ( (ft (x))) Ely, मं BR ((())))
(15)
ST. 3VdA.
(16)
Finally, the halting condition implies that pl (E oz) < for all 01, E A.
D PROOFS OF SECTION 3.2 FINITE SAMPLE ANALYSIS
First, to make our argument that in-sample quantities translate to out-sample quantities, it is useful for the patching operations to use values that are rounded to a finite grid, rather than the precise value from the arbitrary sample. We define the finite grid as follows:
Definition D.1. For any integer m > 0, let 1 1/m denote the m 1 grid points,
1
1 2 2
m 1 1
0.
m
m
For any value v e 1]d. let Round(u; m) = arg min dellym] ||e- - v'112 denote the closest grid point to e in [1/m]]
At each time-step in Algorithm and Algorithm 2 denote Zt Round(0; m)) and we patch the predictors using Øf instead of o² i.e., we update f to f++ as
g (z) projja (f E'E
With this new patching operation, we can perform a similar analysis in Section 3.1 to show that
the Brier score decreases at each iteration, and therefore the algorithm terminates within finite number of time-steps. We denote the maximum number of time-steps, counting both Algorithm
and Algorithm 2 T Tmax-
18

---

Published as a conference paper at ICLR 2025
Then, count the total number of possible predictors outputted by Algorithm 2 by observing that, for a fixed pair of input predictors, each pair of output predictors can be encoded as a sequence L, a1 02 AA ( Ee,a n ,a e, L. 01, 02 a E A], and A, E [1/m]4 are all chosen from a finite set, and the length of the sequence, T, is also bounded. Specifically, for fixed input f1, f2. we denote be the set of all possible predictors outputted by Algorithm22 Then, its size satisfies
of tuple, {(i', E², E hemm. Here, index i' {1,2}. event E {Er,as.02
JS| - (4|c) A
We show that the number predictors outputted by Algorithm 2 is bounded:
Lemma D.2. Fix any pair of predictors f1, X
[0, 1] and any 1), Oz > O. Then the total
number of possible predictors outputted by Algorithm 2 is at most (S) such that, for any distribution
D which Algorithm! 2 is run, the output predictors
Ji.f2 S.
Proof. First, notice that sequence of quantities ((i', F², A') he) defines the pair of predictors outputted by Algorithm 2
Let S denote the pairs of functions induced by all such trajectories defined above. Here, 1² E {1,2), E E {Eg : L,a,,a2 E A} (E ar,a l, L, 0,0,000 a2, a A}, and A, E [1/m]". Therefore, there are
| (2(IC)A*+ + A2) 1)9)* s (4/4/22 + 1)a)
output predictors.
D.1 FINITE GRID
With this new patching operation, we can show that the Brier score decreases on the empirical distribution D, corresponding to Lemma C.2
Lemma D.3. Fix any event F. Let B(wD)~DV - [(x))B(())) = 1]. For any predictor J, we patch I (x) = -proia + EE())) Then,
d
B(f B(f [1012((E)
4m
Proof. Let f'(x) f(x) + (x)). Then, we have
B(f, D) - B(f' D) BB, D) B( D) B(J' D) B(J, D)
21 + [x) + <E(x) -v12 |((()) + (E(r) -
(Lemma
||ا 0 2 m(E)
$1
= =1<bl - E
By definition ē, we know that each index of 13 Ø is in 10. Im
Therefore, we have
d
B - B / D) > 2110 ((E)
4m
Since the Brier score is within the range |0, d], and it decreases at each iteration, we can show that, we set large enough, Algorithm terminates within finite number of iterations:
Lemma D.4. For any predictor fi, f2. Let m 2 iteration of Algorithm 7 and Algorithm! satisfies
V 3min /1d]
The Brier score at each
min(3?, nn²/((Ad))
B(f', D) - B(fe+1, .D
2
19

---

Published as a conference paper at ICLR 2025
Counting both Algorithm 2 and its subroutine Algorithm 7
the total number of iterations T satisfies
2d
T S
mj² /4d}
Proof. By Algorithm we have by definition of 3-decision calibration that
p(E" n Ee,a) ( byy f(x) Ee,o(2) 1111
(17)
2p(E" n Ee,a)² )2 (
f(x) Ex,a(x) 1]ll2
(18)
= (a.) ((y fxx E (z)) (x)] B².
(19)
In Algorithm 2 we have by Lemma C.I that
[ f()) = 1|ll na²
m(E")
(20)
4d
Therefore, for any Φ and event E that patch in Algorithm Tor Algorithm 2 they satisfy
10l1 m(E) > min n7
4d
Letting m V 2mi (3" (3"" /dd}
we can ensure
1013 m())
min (B2, m/²2 /(d)(((A))))
B(J*, D) B( D)
2
2
Since the Brier score is in the range [0, d]. we can bound the total number of iterations of both Algorithm and Aggorihmmaas
2d
T min(3 nou //22/4d
L
D.2 PROOF OF THEOREM 3.5
First, we show that, for fixed predictor f and event Ex,a, the in-sample prediction error is approx- imately accurate. The deviation bound of the Brier score and calibration error can then be directly implied.
Lemma D.5. Fix any J, Ee,,s with probability at least 8', we have
Eolly ((a))) 1 [o El.
dlln(2//8)
S
n
2n
2
Proof. Fix an index j [d]. we know E F f(x)); Fe,. (f()) [0, and
1 n E [m f(x))) Ee, (J x:)l
En
Reawwolly--a f(x)); Ee,
Since (I,, U:) drawn i.i.d from D,
Hoeffding's inequality to get, with probability 8' /d,
In (n2//0)))
B(n - f(x)); Ee,a (f().
Σ (vs - f(x:)); Eg, (f,s(, S
2n
Using union bound, we have that with probability - 8', the above incquality holds for all j e [d]. Then, have
B(z,y~ol( - ((x))) (e,)((()),x))
[wi - f(x:)) Er,a (J (x:))
1I((2d/8))
Σ
2n
2n
jed
20

---

Published as a conference paper at ICLR 2025
The deviation bound of the Brier score and calibration error can be directly implied by Lemma D.5 We summarize them in the lemmas below:
Lemma D.6. For a fixed f, with probability least 1-16, 8', -
In (2d/22)))
2n
Proof. Using triangle inequality, we have
[B(f.D) - -(J,, D)I =
1 (a. f(x)]]1
1/4
f(x;)]
1
12 B(an))Dly-- f(x)]
1/
(x,)]
71
1=1
2
d'In(2//8)
2n
Lemma D.7. For fixed f, any loss function & andd (Et,an Ee il a, 02 A}, with probability - 8', we have
3d 3d 18")
Bolly f(x))
[m f(z)
S
2n
for all E. E.
Proof. The claim follows by using a union bound over the events E using Lemma D.5 and that |89| A3 4
For fixed pair of predictors, E2 is approximately correct with high probability:
also show that the empirical size of the disagreement events
Lemma D.8. Fix any pair of predictors (fi,f) E S, with probability at least have
8' over D,
(Ft,
1
Σ
as = S
In (2(2AA()/88)
n
2n
for all a1, a2 E A with aı * and for all f L.
Proof. We know I[E (1;) = 1] E 10 and
1
En
T (0 = ((
Since (s) drawn i.idd. from D, we can use Hoeffding's inequality to get, with probability 1 - 8' (1)((
1 71
M
n I[ (z:)] S
2 InA 2ln(2A|(1/8))
2n
Using union bound over all pairs of a1, 02 E A and E E L, we know the above inequality holds for all 01 0g and & E L with probability least 1 8'.
We summarize the above results in the theorem below. Theorem 3.5 follows by solving for n in the 2-4th guarantees below.
Theorem D.9. Fix any distribution D and dataset D ~ D containing n samples drawn i.i.d from
D. For any pair of predictors fi, f2 : X - [0, 1]d. loss margin a > 0, disagreement region mass n O, and decision-caliiration tolerance 3 >> 0, Algorithm run over the empirical distribution D updates predictors fi and foroo T, and T2 time-steps, respectively, and outputs a pair of predictors
(ST 12 such that, with probability at least 5 over the randonness of D) D
21

---

Published as a conference paper at ICLR 2025
1. The total number of time-steps for Algorithm and Algorithm 7
2d
T = Ti + -
min [82 na / 4d)
2. For i E {1,2), the Brier scores of the final models lower than that of the input models:
B(ff.D D) S B) -T; min n3 /(4d) + ((dlm(6d((1/0)((22))
3. For i {1,2}, the downstream decision- -making losses of the final models do not increase by much compared to that of the input models:
E ((ay) (ly, π BR (f/ (x)) fT (f((x)) s (3+ V (Bddm(644A VdAT;
4. The final models approximately agree their best-response actions almost everywhere. That is, the disagreement region Esyaz calculated using f f has small mass.
((Ee,or s /
for all a2,02 E A s. # oz
Here, is the set of all possible predictors outputted by Algorithm satisfying
+ +1) In 4///233 (Tv
2d
d 2 m3 no? /Ad]
In([S]) &
+1)
min na /Ad]
Proof. The upper bound on 7 holds true with probability 1. For the remaining three guarantees, we
show that each of them holds with probability at least 1 1- 8/3 over the randomness of D.
Brier Score. First, by Lemma D.6 and using union bound over all possible output predictors f2) S, we have with probability at least 8/3 that
ddnn6dd
B D) - B(f., D)1 &
2n
By Lemma D4 and summing over all iterations, we have
na?
B(F,D) < B(f; D) min
2
Therefore,
dln(6d))1/8)
B <B(P'
2n
nja"
d dIn(6d]SS/0
<B(;, D) T: min
2 8d
2n
for E [1,2].
Expected Loss. Using union bound over all predictors in S, by Lemma bility at least 1 - 8/3.
D.7 we have, with proba-
1 E1. -L
3d InddA|]] (
Ep Ep (()))
2n
1=1
for all predictors f. action the set A C E as
A and loss é E L. Using similar method in Lemma 2.6 we define
A = fr E BR (f( a).
22

---

Published as a conference paper at ICLR 2025
Then, have
B(e.w) (x)))
(4, B(ay)) a(g) aEA
For each term in the summation,
(te.w>/((((y.00) e(y. = (B pI lai)
(21)
(Linearity of Expectation)
3d (d11(6dd)|(114)
<E If (x) -lat)
3
Vd
2n
(Lemma D.7 and 3-calibrated)
<(++) |
3d 3d1n(6dA[S] Va.
L1/8)
(Since a is the new Best-response action)
2n
Summing these actions together, we have
3 In(6dA|/|]]4) dA. (22)
((a.)))(((()) mi ( (x)+ Ely, "( (I((() S BVdA
2n
Summing over all iterations, we conclude that, with probability at least 1
58/3,
3 3In(6dA|S)) |C] /6)
E ((r,))=(((y BR (f, - x ( IT,(BVaA+ for all i {1,2}.
dA)
2n
Disagreement Event. By Lemma D.8 with probability least 1 88/(3] have, for all l L, E A with # 02 and all (2) S.
Σ 1 "
2 (n(6A|()
(EEroon (f((
5
From the while loop condition Algorithm)
we know that
aF
12 (x:), sn
7
Then, using union bound over all (f1 E and l E L. with probability at least 1 -5/3, we have the guarantee
a
(11(6A|/S] /8)
oz (F))
EE (8 (2x) (a))
2n
(23)
2 (6.A |C
Sn+
(24)
2n
for all a1 02 E A, a1 # and E E C.
[V
Finally, using results from Lemma D.2 value Tmax, and m by showing
we conclude
m (3" ma 2/4]
In((S) Sin ((4)2)2 + Tmae)em
(Tmax + 1) 22 A + 1)d
2/3 (TV2
2d
d 2 2 1.2 na? /dd
+1)
+ +1) In
min no? 4d}
23

---

Published as a conference paper at ICLR 2025
E PROOFS OF SECTION 3.3 EXTENSION TO MULTIPLE PREDICTORS
Here, we present the algorithm we described in Section 3.3
As a shorthand, we write
Eg e, (5(); as 00
Algorithm 4: Reconcile Decision Calibration for Multiple Predictors (ReDCal-Multi)
Input: fi. f2...., fu. L, 0 0, >
We use ( as the base predictor. 2: while u( (2.)) 2 r for some 01,42 E A. L, and j E [k] do
1: Let 1 = -i for all E [1], and
3: Let aa, a2; = arg max, t, m 1 (( E Epgajaai,
4: Pick
8 arg max ( (1, (y, e" Eb) = (E(1,f*
- E (fi()), at) - es (fi(t), a5) (x) 1]}.
5: Denote l/ as f. Let Ø ((y Bs) =1] EawDx 1o (3) 1].
6: Patch f'(x) p (f)(z) o (x)).
7: Let ft pt+1
C. t
Output: fi.....ffk
With Algorithm 4 we obtain the following guarantee.
Theorem E.1. Fix any distribution 'D and datasel D ~ DD containing n samples drawn i.i.d from
D. For any predictors f fr XX - [0, 1] family of loss functions L, loss margin > O, disagreement region mass > O, and Decision-calibratio tolerance 3 > 0, Algorithm 4 run over the empirical distribution updates each fs for T; time-steps, and outputs predictors
.2²) UT......' such that, with probability at least 1 - over the randomness of D ~ D
1. The total number of time-steps for Algorithm and Algorithm 7 is
2dk
T=
Σ T
min na? /Ad]
KE[K]
2. For i E [k), the Brier scores of the final models are lower than that of the input models:
B D) S -((: -) min (B2,mao' ((d))
3. For i E [b]] and for all l E C. the downstream decision maaiinnnmaainggg losses of the final models do not increase by much compared to that of the input models:
B(g.a)~ m BFT (x)) (fT(())) Ely, - BR (ft(f)) 2T,3AVd
4. The final models approximately agree on their best-response actions almost everywhere. That is, the disagreement region Ee,a and all j E [k), L, and 01, 02 s.t. 01 02
ae calculated using JT 13. has small mass: For
1 [(FF,,n S 2m
inn A (PPk(1T min (3, //d//d))//))))))))))))){)) (In(dk A L)) - In(6 min (B, mj. mox/d))))
Proof. The proof follows the same idea and structure as the proof of theorem 3.5
Number of Iterations. By lemma D.3 D.3. at each iteration of Algorithm and Algorithm the Brier score some predictor j E [k] satisfies
B(f,, D) - B(f .D) min min 133,naa (o22/(4d)}
2
24

---

Published as a conference paper at ICLR 2025
Since the Brier score is non-negative and we have l predictors in total, we have that, after T
k
Ti iterations.
E (B ; D)) T. min m na? / JC(R]
Σ B)
2
jE[R]
Since Brier score is in the range [0, d], we can solve for T the incquality and have the upper bound on the number of iterations
2dk
Tmax I
min ma² (4d)
Brier Score. We first count the number of possible predictors outputted by Algorithm 4 At each iteration in Algorithm oo its subroutine Algorithm [ we patch on a predictor f; for some it E [k),, on the event F. ( E f, 01,02 E A.j [k]) U ( Ee e, L. 01, 022 E A.j [k]), with the value A, [1/m]d. Therefore, at each iteration, the number of different patching operations satisfies
(1 + () 1) < 2| + 1)a..
For fixed predictors, the output predictors are defined by the sequence of patches. The total number of different sets of output predictors
|S| S Σ (210) +1) (2)4 + ())) 1imat
Using lemma and using union bound over all possible output predictors, we have with probabil- ity at least - 0/3 that
In 6dk S1/6)
Bif,, B(;,))
2n
Summing over all iterations, we have
( B22
na?
In (6dk) (6dk)S1/8)
BUT < BUT - min
+
2
8d
2n
Expected Loss. Using lemma D.6 and union bound over the events in E = =EEEEee (Ei O Evr ll L, 02, a E A.j [k] we have with probability 8/3 that
[EDl(y- - f(=)) 1 Σ f(x)))
3d I
( S
2n
for all predictors f, action A, loss E L. The rest of the steps are the same in the proof of theorem 3.5 We have, at iteration t,
Ely, me ER (f(()))) &VGA+ 3 3ln(bckAA/c]|s/// dA.
(xzx)) [K m BR ( ( (x)))
2n
The result follows by summing over all iterations.
Disagreement event is small. The stopping condition at line 2 of algorithm fimillhmmimpieess that the final output models satisfies
pl (Ft
Σ Es Fi and H (wx), f/ (x)), sn
for all a1 0g A, C. and E [k]][1]. That is, the disagreement region between our base model ff and any of the other h: - models is small. Using Hoeffding's 's inequality and union bound, we have that, for any predictors (fi,...,ft) E S, with probability 1 6/3 over D,
In S
n M
(
n
for a1, 02 E A with aj # a2, all f C. and predictor j E [k]] Combining this with the bound on I F given by the stopping condition, can obtain the fourth guarantee. |]
25

---

Published as a conference paper at ICLR 2025
Note that, with the fourth condition in Theorem E.1 we can also obtain that the size of the disagree- ment event between other predictors, f with i,J + satisfies
( (U( (f)), s 21,A. az e
For each x E F
must either x E Ea ( or x for some a E A. Therefore.
Ea La
1 E a0. (l
Σ
(e (()))) + ( (10)),
(EAA())))))
Σ
2n S 2Am.
aEA)/ar,02)
F EXTENSION TO INFINITELY LARGE ACTION SET
We extend our results to setting where the action space A of the downstream decision decision-making tasks is infinitely large. Now that cannot enumerate all actions in the action space, the disagreement event this setting can not specify the best-response action. For a loss L, one approach is to define the event
(((((()) T(([(x)) ((m*(((())) (x))) > a, or (J2(x), ((m(((())) (=)")(()))) > a].
We now want to "patch" predictor on the disagreement event, such that the predictor's Brier score decreases by a large amount after patching. However, using this definition of disagreement event, cannot guarantee that at least one of fi and fz has large prediction error. For example, consider = = [//2, 1/2]. predictors (x(
[o. 1], and the loss fi, the loss vector of the best-response action of la [[x x] : E [0, 1]}. According
f2(x2) ) = [1, OJ. (122 = f2
is faz = =00,1] 1]. and that of x2 is lap = [1, 0]. According to ʃ2, the loss vector of the best-response action 11 and ø2 is laz and la, respectively. Clearly, data .r and ø2 are both the disagreement event ES for any < 1, but the mean estimation error of fi and fz on the disagreement event [21 are both 0, since 1/2(0,, + [1. 0]) [1/2, 1/2].
A solution to this problem is to further separate the Eg into 2d sub-events that focus on the dis- agreement per-label. The union of these 2d sub-events is equivalent to Ep, shown in Lemma Formally, we have the following definition.
Definition E. (Per-label Disagreement Event). For each a loss E E L, index E [d], we define
(f(())) [ fe(x); a/d, (f(f)z)) f2(), 1]. E (fi.) = [[f((z); - ff((),, < -a/d, (f() = 1].
To ensure the predictor's expected loss is accurate, we define per-label best-response event using a discretized approach, approximating each index of the loss vector la with finite grid [ (Definition D.I.. Then, if a predictor is approximately accurate with respect to each per-label best- response event, then its estimated loss for the best-response actions are approximately accurate.
Definition F.2 (Per-label Best RestoRes Event). Given a predictor f, a loss l, and level 7 E [1/T], for each index i E [d], we define the best-response event as
Es, (f(x),)) : ( ST..
where (n denote the i-th index of (
With the disagreement and best-response events now clearly defined, can adapt our existing algorithm (Algorithm/2 2 to this new context: at each iteration, we find the largest per-label disagree- ment events and patch the predictor with the larger estimation error; then, in subroutine similar to Algorithm|1 [] we iteratively calibrate the predictor we just patched on, using the lab-label best- response events. This algorithm can maintain similar guarantees as Theorem 3.5 with data size á (dz (n/ min . na² 2 /d3 (d))). The formal algorithm is written in Algorithm
26

---

Published as a conference paper at ICLR 2025
Given approximation of each action feature &a using finite grid [1/T], it may intuitive to approximate the entire infinite action set as [1/7]] and simply run Algorithm 2 However, such an approach yields action set whose size grows exponentially with d, which in turn would require a data sample size that also grows exponentially to achieve guarantees comparable to those in The- orem 3.5 In contrast, our algorithm X operates with polynomial data requirement relative d, making it more feasible for practical application.
Algorithm 5: Decision Calibration for Infinite Action Set
Input: Predictor f. loss family C. 3 > 0, event E
1: Let f0= =
2: while ft is not index-wise 8-multicalibrated with respect events Eeirr n E for some l C.
e [d]. and T E [L/7] do
3: Let Et, f arg max f,r.7 ([
4: Let o' = /y - (x) Ee s
,, (f)()), =1]
5: Patch (x) = p (f((z) O' E (f(()))
6: t= 1.
Output: f
Algorithm 6: Reconcile Decision Calibration for Infinite Action Set (R+DCal-Inf)
Input: f1. f2, L. 0, 9. 0
1: Let 1 fi, f2 = f2 and = O.
2: while ul (E) 2 17 for some & E C do
3: Let ,","", arg max ). E E
4: Pick
= arg max (( 1e (1, BR (f((z))) (v, BR (1(())) = (E(1.)
Exax (f(()), BR (f(( (((((t) (())) 1]/.
5: Denote f/ as f. Let B - ENNDY (3( 1].
6: Patch ('(x) (rojjo
7:
Let f p++ Decision-Calibaation--l(fff L. B, E*) 11
Output: 1 f2
We now present the formal proofs related to Algorithm 6
Lemma F.3. For any loss E L, we have
EG
E
(E),))
Proof. By definition, we may get
U
E C
For the other direction, assume for the sake of contradiction that there is an element E E7 such that x & EG,, for all e [d] and (>,<) Then, this means
[f(, f2(x)) < a/d
for all E [d]. We can then get the inequality
(fi (z) - f2(x), (oR(((()) - (
= Σ (f(x)) - fa(x))) (L4 - -f-0110000 (())
iE[d
Σ [x) 11(0))-1(4((M(te)))) - - ((
<
iE(d]
<d a/d
27

---

Published as a conference paper at ICLR 2025
On the other hand, by definition of event Ey, have for all Es, (f1(z) f2(x)) ((((()())) - (x))(((())) a,
which leads to contradiction.
The following lemma shows that, if f is 3-index-wise decision-calibrated, then the loss estimation approximately accurate.
Lemma F.4. If the predictor f 3-index-wise decision-calibratedn i.e. for all E C. [d], (1/T,
D - f(x))l2 Fe.,,- 3,
then, the loss estimation given by f is approximately accurate for all L:
E Ky ((a))))))) - ((..)))l(((())
( (( - dTB + d/T.
Letting T 2 1/VB, get
B(za))Dly (((())))) (ff)) s 2d
Proof. We can rewrite the expected loss
E(z,))~D(( (BB()(=)))] =
Σ
((ax)~Dly; ((E()()))))
iE|d]
(here (f(m) represents the i-th index of & ((())
Σ
(( blys ( (f(x))
iE|d rE/L7]]
Σ
Σ
B B (farr(()),
iE|d TE/171
Similarly, we can rewrite the estimated loss as
(()))))D(((()) E ((()))))))
Σ Σ
(T-1/T)
((o)))Dl(((); (f))))(
:E|d] FE(L/T]
The estimation enror is
(( Kl,, (((()))) - (f)))
Σ
Σ
B(aay)Dlv (y: (f(.)((())
< rE[L/T]
Σ
Σ
1T-1/7) B(z,)>~(((s);; (fs),
ke|d] rELL/T]
Σ
Σ
E ELay) f(11))-((x)))))) (f
( rELLT]]
Σ
Σ
1/T olfx)=)f(( Et,,, (f(x),
*E|d rE[l/T]
Since f is ß-index-wise decision-calibrated we have
E(syeelly f(x), xf))) =
Therefore,
E P(ay)ED(yy (oo (. $ dTB + d/T
We now ready give the formal guarantees of Algorithm 6
28

---

Published as a conference paper at ICLR 2025
Theorem F.5. Fix any distribution DD and dataset D ~ DD containing samples drawn i.i.d from D. For any pair of predictors fi. : X + [0, 1] family of loss functions L. loss margin a > 0, disagreement region mass 1j > 0, and deciston-calibratti the empirical distribution D updates fn and f2 for Ti and T2 time-steps, respectively. and outputs pair of predictors - such that, with probability least 1 - over the randomness of
tolerance 3 > 0. Algorithm 6 run over
D ~ D
1. The total number of time-steps, for Algorithm and Algorithm 5
2d
T= + n/.
2. For i E (1,2), the Brier scores of the final models are lower than that of the input models:
BUT D) S B(, D) (T: min {3² ( na² (2d"))
3. For i E [1,2] and for all & E L, the downstream decision makiing losses of the final models do not increase by much compared to that of the input models:
B( (0l BR (JT (fT())) fly, TR ( (filx)) 2T.
4. The final models approximately agree on their best-rexponse actions almost everywhere. That is, the disagreement region Eg calculated using J 12 has small mass: Ve E L,
1 s 2n
in 2 2 (22 m0n/mmmmmm333. mna (In(dT (2) In min na? no2//d1)))
Proof. Number of time-steps. By Lemma C.2 each iteration & in Algorithm 6 of its sub- routine Algorithm I the Brier score of f decreases by min [,² /2d when m 2 [vd/2min n102" "od2/ Since Brier score is bounded in [0, d). the total number of time-steps satisfies
4d
T max Ti T
min
n/2/222
Number of Output Predictors. We count the number of pairs of output predictors. The patching event each iteration is in the set (Eg,,, C, i, [d]. T, {<,>}} The total number of event is at most 2| 2f T]. Since each pair of output predictors is defined by the sequence of patchings and A E [1/m]] we have the total number of possible output predictors is
L, E [d], E [{,>}} U (Er,,, n Eg .r e,
|S| < ((4d ())TT) + 1)d)Tmea+!
Therefore,
df
In([S]) S Ω min no? /2d?
In Ind min min (0?,n0 (/aa///dP))
Brier Score.
The result directly follows using the same argument as in Theorem 3.5 We can obtain Blf DD B(f., D) T. min { na² /(2d)((2)))))))))))))))))) + (dd1((4(5110))((2)))
Loss Estimation. Using Lemma D.5 and union bound over (Er,,, n Eg [1/T], {<,>}} and |S,, we have with probability at least 8/3,
E, E L,i,i'
ED ((nv-s(()) Er.) (f()) 1 ((:)
3d In(d' | (8)
2n
Using Lemma F44 and summing over all time-steps, obtain the result following the same steps as the proof in Theorem 3.5
E (xx.)) ((c.))>D((l. BR (fT (x)) - -ly. BR (f((x))) (VBd+ (/aa/( T,
(f(()))
29

---

Published as a conference paper at ICLR 2025
Disagreement Event. Using union bound over the disagreement events (Es : L.} and the set of possible output predictors, we have, for all & E L. and (fi.f2] E,
x:)) $ [C]6)S)|4//6)
a
2n
From the while loop condition in Algorithm Therefore,
we know 1 32 Σ. [E (I.), (x,),, n.
k Ep) S n + (In(6]] (2)) for all & E L
The theorem follows from solving n in the conditions 2 through 4.
G ADDITIONAL EXPERIMENT DETAIL
Our ImagineNet experiments are run on a Macbook Pro with 32GB of RAM. The experiment on the ImageNet dataset uses pre-trained models provided by pyTorch which do not require additional training. The experiment
the HAM10000 dataset includes neural network models trained using py TyTorc on NVIDIA GA 100 GPU (80 GB RAM) with 2 compute workers loading the data. The total time train the two neural network models with approximately 88% Top-1 accuracy takes less than minutes.
G.1 ADDITIONAL EXPERIMENT ON IMAGENET DATASET
Brier score. In Figure we compare the Brier score of ReDCal (Algorithm 2 with the two baseline algorithms on both the calibration and the test datasets. Compared to Reconcile, our algo- rithm decreases the Brier score by a smaller amount on the test dataset. The combined algorithm of Dacision-Calibration with ReDCal as post-process achieves the most substantial decrease in the Brier score.
Prodictor 1 Trinn
Predictor 2 Train
Predictor 1 Test
Predictor 2 Test
1.00
0.95
0.90
0.65
Reconcile
ReDCal
DedisionCalibaatin
Decisoncalloration--eeCC
Figure 4: ReDCal decreases Brier score on Imagenet. Compared to Reconcile, our algorithm de- creases the Brier score by smaller amount the test dataset. Cecision-Calibration with ReDCal as post-process achieves the most substantial decrease in the Brier score.
Decision loss on calibration dataset. In Figure we compare the decision gap of our proposed algorithm with the two baseline algorithms on the training dataset.
Decision loss comparison for high-dimensional classification problem. In Figure 6 we com- pare the decision loss gap of our proposed algorithm with the two baseline algorithms the testing dataset, using = 10, 100, and 1000 classes. We plot the average loss gap of the two predictors. The hyperparameters are: disagreement margin a 0.1/d, decision-calibration tolerance 3 0.001/d, disagreement region mass = 0.01, number of actions K = 10.
G.2 HAM1000 CLASSIFICATION
Experiment Setup. We use the HAM10000 dataset (Tschandl et al. 2018 (licensed CC BY- NC 4.0) on pigmented skin lesions to predict the probability that patient has contracted one of
30

---

Published as a conference paper at ICLR 2025
Predictor Train
Predictor 2 Train
Predictor Train
Predictor Train
1.50
Deciion Loss Gap
1.45
1.40
1.35
0
10
20
30
40
50
0
10
20
20
40
50
10
50
Timestops 50
Timesteps
Timestops
Timestops
ReDCal
DectsionCallbratio
DecisionCal bratiinn
Figure 5: ReDCal decreases decision loss Imagenet. We plot the gap between the average loss of each predictor and the optimal loss had we known the true predictor f on the calibration set. Left two figures: We compare the LossGap of ReDCal (orange) with Reconcile (blue). Compared to Reconcile, our algorithm converges at similar rate and decreases the loss by a larger amount on the test dataset. Right figures: We compare the LossGap of Decision-Calibration (green) that of Decision-Calibration with run of ReDCal as post-process (red). Our proposed algorithm can improve upon Decision Calibration output predictors and further reduce the loss on the test dataset. Results are averaged over 500 runs and the shaded region indicates +1 standard errors.
Classes
155
Decdkion Gap
1.10
1.
1.05
2.06
1.00
1.42
2.04
0.95
1:40
10
20
30
40
50
0
10
20
50
0
1.0
20
20
40
50
Timesteps
Timestops
Timestops
DecisionCallbration
DecisionCalbbration
Figure 6: ReDCal decreases decision loss on Imagenet. The takeaway results similar to Figure 2 As the number of classes in the multi-class classification problem grows from 10 to 1000, ReDCal still outperforms Reconcile in decreasing decision loss the test dataset. When have 1000 classes, ReDCal converges slower than Reconcile. Furthermore, ReDCal can further decrease the decision loss when is used a post-process after Decision Calibration terminates.
possible skin diseases: "akiec', 'bec', "bkl', 'df", "nv", 'vasc', and 'mel'. We split the dataset into train/validation/tess sets, with 20% of the data are used for validation and 20% are used for testing. We use the train set to train two neural networks using py pyTorch with resnet50 (He et al. 2015) and densenet121 (Huang al. 2018) architectures and learn two models with around 88% top-1 accuracy. From each model, we output the individual probability prediction for each of the possible labels. We use the validation set to calibrate the predictors using our proposed algorithm and the two baseline algorithms, and the test set to measure the final performance.
We each calibration algorithm 10 times. At each run, draw fresh loss function created based on the loss function motivated by medical domain knowledge in Zhao et al.) (2021) and additional random noise drawn from Normal(O, 1). There
two possible actions for the
treatment (a = [1. OJ) or no treatment (a = [0, IJ). Given a loss function and a predictor f. the decision-maker will choose an action that minimizes their loss.
For each calibration algorithm, we calculate (1) the Brier score of the updated predictors and (2) the differences between the optimal loss had we known y and the actual loss from taking the best- response actions induced by each predictor.
The hyperparameters for Algorithm are chosen as follows: loss margin a 0.1, target disagree- ment region mass 7 = 0.01, and decision-calibration tolerance / = 0.000001.
Results.
The takeaway results similar to those of the ImageNet experiment.
31

---

Published as a conference paper at ICLR 2025
compare the Brier of ReDCal (Algorithm 2 with the base- line algorithms on both the calibration and the test datasets. Compared to Reconcile, our proposed algorithm decreases the Brier score by smaller amount.
Brier score. In Figure 7
Decision loss. In Figure 8 we compare the decision loss gap of our proposed algorithm with the two baseline calibration algorithms. Compared to Reconcile, our algorithm decreases the decision loss by larger amount on the test dataset. Furthermore, while Catision-aalibattion already de- creases the decision loss, our algorithm can further improve upon their result when used as a post-process after Decision-Calibratin terminates.
Predictor 1 Train
Predictor Irain
Predictor 1 lest
Predictor 2 lest
Brerr Score
0.15
Timestaps
Timesteps
Timesteps
Timesteps
Reconclee
DedisonCalitraiion-ReCCa
Figure 7: Brier of the updated predictors using Algorithm 2 (orange) and two benchmark algorithms: Algorithm (dashed-blue) and Algorithm (dashed-green) Our algorithm reduces the Brier score by smaller amount compared Algorithm Results are averaged over 10 runs and the shaded region indicates +1 standard error.
Predictor 1 Train
Predictor Train
Predictar Train
Predictor 2 Train
Deccion Loss Gap
0.45
0.35
20
Timestaps
Timestops
Timestops
Timestops
DecisionCal
Decisinnalllration-RReDC
(a) ReDCal decreases the decision loss on the validation partition of HAM10000 datasct.
Predictor_1
Predictor
Fredictor
Predictor Test
0.40
Decisio Loos Cap
0.36-
0
10
20
30
10
20
30
10
20
30
0
10 Timestepi
20
30
Timesteps
Timesteps
Timesteps
Reconcile
ReDCal
DecisionCal lbration
DecisianCallbraiinn--ee ReDCal
(b) ReDCal decreases the decision loss the test partition of HAM10000 dataset.
Figure 8: In Figure Sa and Figure 8b we plot the gap between optimal loss had we know the true label y and the loss from taking best-response actions induced by the calibrated predictors on the validation set and test set, respectively. In the left two figures, we compare Algorithm/ [ (orange) with Algorithm (blue). While the average loss of predictors updated using Algorithm may increase on the test set, our algorithm quickly converges and produces predictors with lower decison-making loss. In the right two figures, we compare Algorithm/ [ run of Algorithm (red) post-process. We observe that running algorithm as post-process can still further decrease the loss compared to just running Algorithm on its own. Results are averaged over 10 runs and the shaded region indicates +1 standard errors.
(green) Algorithm | with an additional
32


Reviews:
[{"review_id": "FSZcgEYDki", "reviewer": "Reviewer_eKLK", "summary": "This paper studied the problem of model multiplicity in downstream decision-making. In this setting, two predictive models of equivalent accuracy do not agree on their predictions for the downstream decision-making problem.\nThe paper proposed a new calibration framework which calibrates the predictive models with respect to both a finite set of downstream decision-making problems and the individual probability prediction. Further, the paper proposed an algorithm that first reconciles the differences in individual probability prediction then calibrates the updated models so that they are indistinguishable from the true probability distribution to the decision-makers together with its finite-sample analysis. Numerical experiments on two datasets demonstrate the effectiveness of the proposed method.", "questions": "- W.r.t. the finite sample analysis, is the proposed algorithm robust towards any noise in the samples?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper studied an important and practical problem of model multiplicity. The paper overall is well-organized and presented with a good clarity. \n- It is in particular helpful to have the illustrative example in Figure 1, which directly shows that it is insufficient to only update two predictive models so that they have improved squared loss and nearly agree on their individual predictions almost everywhere.\n- Theoretical guarantee shows that the new algorithm ReDCal provides an improved accuracy and approximately agrees on the best-response action almost everywhere compared to the prior work.", "weaknesses": "- The experimental results with the HAM10000 dataset show substantially larger error bars, and much less smooth convergence. It is helpful to provide more details on this differences between the two sets of results.\n- The experiments only compared to one other baseline proposed in (Roth et al 2023). How does the proposed algorithm compared to other related works in the model multiplicity?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "yK6jfvgsxH", "reviewer": "Reviewer_ctoE", "summary": "This paper studies the Reconcile algorithm proposed in [1] which takes two prediction models and outputs two models that have better prediction accuracy which is quantified by the Brier score. They expand on the existing method by proposing a new reconcile algorithm that looks to improve prediction accuracy while also preserving the downstream decision-loss. They provide theoretical bounds that show their method trades off improvement to prediction accuracy at the cost of downstream decision-loss.  They provide numerical results to show their algorithm helps reduce the loss gap after running their version of the Reconcile algorithm. \n\n\n\n-----\n[1] Aaron Roth, Alexander Tolbert, and Scott Weinstein. Reconciling individual probability fore- casts. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Trans- parency, FAccT ’23, pp. 101–110, New York, NY, USA, 2023. Association for Computing Ma- chinery. ISBN 9798400701924. doi: 10.1145/3593013.3593980. URL https://doi.org/ 10.1145/3593013.3593980.", "questions": "1. One thing I didn't understand was if you are given two models at the end of ReDCal, how do you choose which model to use? Why is it important that the two models agree in the decisions they make if you already control the decision-loss gap?\n2. If you don't want to affect the decision-loss, it makes sense to me that you just wouldn't change the two predictors. Is that the case and is it reflected in your algorithm if you choose the correct parameters?\n3. Why does the algorithm converge so fast in the numerics? The upper bound on the time steps seems to suggest the number of time steps that should be run before convergence should be large given the choices of $\\beta$ and $\\alpha$. Does this imply the bound is is potentially very loose and is it possible for it to be made tighter?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper highlights an important problem, that improvements to prediction models can hurt downstream decision-making since downstream decision-makers may have loss functions that do not necessarily align with prediction accuracy. The paper combines existing work in multi-calibration with work in model multiplicity to solve this problem.  The algorithm proposed by the paper seems novel and provides what seems to be sensible theoretical guarantees that trade-off between improvements to prediction accuracy and preserving decision-loss. This seems to be a relatively significant improvement to the Reconcile algorithm.", "weaknesses": "The paper has weaknesses in its presentation as well as results that seem somewhat suspicious/hard to interpret precisely.\n\nThe following items could be addressed and improved for presentation:\n- In the paper's introduction, the authors mention calibration several times, but for someone not immediately familiar with the literature it's hard to understand what it is formally. It becomes a little better defined at Lemma 2.6, but having extra background or explanation in the introduction would be helpful in understanding the high-level concepts used to construction the paper's proposed algorithm. \n- The paper could provide better background on the Reconcile algorithm which seems to be a key motivation for pursuing the work. There is no high level description of how the algorithm works, so Theorem 2.7 for example feels impossible to verify. Additionally, the Reconcile algorithm reproduced in the appendix seems to be missing key elements, like defining $h$ and $\\mu$. The former seems to be an important update step.\n- The paper does not define notation well. For example $\\mu$ and $A$ are not defined or are defined offhandedly, making it hard to decipher when it shows up later in the text.\n- In Theorem 2.7 the distribution $\\mathcal{D}$ is not defined which makes the last expectation in the proof hard to verify. I could not immediately come up with a distribution where the expectation is 1/2. \n- Some notation seems to be incorrect or have a typo. For example the Definition 2.4 of $E_{\\ell,a}$ is an indicator outside a set. I don't think this is standard notation and is not precise. My guess is it's a typo.\n- Is the notation $\\ell_a$ necessary? If so how do you obtain $\\ell_a$ given $\\ell$?\n- The descriptions of Decision-Calibration, ReDCal, and Decision-Calibration + ReDCal are confusing to me. What exactly is the algorithm for the first and last algorithms. When you count the number of time steps for ReDCal, which loop are you counting? Does it include the loops in decision-calibration? \n\nThe following items can be addressed to help improve the results of the paper:\n\n**Questions related to Theorem 3.4**\n- In Theorem 3.4, does item 1. have a typo? \n- Define $A$ the number of actions in the theorem statement for part 3. since it is off-handedly defined somewhere else in the paper. \n- How do I choose $\\beta$, $\\alpha$, and $\\eta$ if I wanted to guarantee a certain decision-making loss level while optimizing the Brier scores? Managing the trade-off between prediction accuracy and decision-loss would help improve the impact of this theoretical result. Right now it seems hard since the term $T_i \\beta$ seems hard to control.\n- The decision gap in the numerical results don't seem to correspond to the bound in 3. Shouldn't it be close to 0 if you choose $\\beta = 0.00001$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "TbmGeckPjy", "reviewer": "Reviewer_1e2c", "summary": "The paper presents a new algorithm for reconciling two or more models in a supervised setting; the goal is to address the model multiplicity problem (which refers to the phenomenon that there may be > 1 model with similar accuracy but substantial disagreements among predictions) in a decision-aware way. Specifically, the paper shows how to perform model reconciliation in a way that (1) makes the models agree in the prediction space, (2) does not hurt (and possibly even improves) the squared loss of either model, and (3) does not hurt (and possibly even improves) the decision loss of a given downstream decision-maker. (The decision loss is an arbitrary linear loss that the decision maker uses to map predictions to actions.) In addition, the paper performs preliminary experiments showing that the method outperforms (with respect to decision loss) a prior reconciliation algorithm on some vision datasets.", "questions": "The paper currently appears mostly in good shape; my main small improvement suggestions are about the experimental section (at least by lightly tweaking existing experiments/adding another simple but conceptual one). \n\nIn addition, even though the writing of the paper is mostly quite good, it could still be improved in a few places. For instance, the subsection about handling more than 2 models is somewhat confusingly written: e.g. consider the sentence about exponentially many output predictors in the number of models k, followed by the sentence that union and Chernoff-Hoeffding bounds \"suggest\" that the sample complexity scales linearly in k --- a reader who may not have checked the details in the appendix may easily confuse this for saying that the method may not necessarily be scalable in k, even though it actually is. Also, the event collection setup in that case, which involves reconciling a single base model with every other model, is not described that well in prose --- so consider e.g. including a quick diagram which could e.g. have the base model with \"reconciliation arrows\" pointing to the other models, or something similar.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is overall a good and novel contribution to the predictive multiplicity literature. Specifically:\n\n+ The contribution of this paper appears new in the model multiplicity literature: it gives a rigorous method for reconciliation of any two models with provable guarantees in terms of the resulting model loss (for which only one algorithm exists in the literature), while at the same time ensuring in a rigorous way that downstream decision making is not affected negatively (which is new); and it moreover extends this method to more than 2 models in a natural way. \n\n+ In fact, from what I can tell, it has an even broader scope than typically considered in the model multiplicity context, as it does not require the to-be-reconciled models to start off having similar or equal accuracy. When the to-be-reconciled models do have similar accuracy to begin with, then the paper's contribution intuitively appears to offer the interesting and thought-provoking semantics of: \"given two different models with similar performance, you can bypass the multiplicity issue by finding an even higher-performing model (which ensembles/combines the two initial models), with similar or better downstream decision making guarantees\".", "weaknesses": "While overall I believe this to be a good-quality paper, there is the following (relatively non-major) consideration that I would call a weakness:\n\n- The paper currently appears written with a primarily theoretical audience in mind, but I think it could still do a better/more thorough job coming up with/describing experiments. It currently gives two semi-synthetic ones. In the first one, linear decision losses are generated in a Gaussian manner --- so that the two vision models are essentially being calibrated to realizations of random noise (granted, the experiment does illustrate the point that the new method achieves better decision-making properties than the old one, but the setup still sounds strange). In the second one, the decision loss is a \"loss function motivated by medical domain knowledge in Zhao et al (2021) and additional random noise\" --- and in this case, the paper should at the very least clearly state what the loss function in Zhao et al (2021) is, and perhaps provide more principled perturbations of it than Gaussian noise ones.\n\nNeither of these experiments, however, connects in any way to the examples given earlier in the paper on how disregarding decision loss can lead to its deterioration during the reconciliation procedure. These examples are in some sense prototypical of how reconciliation could hurt downstream decision making; and given how easy it is to come up with a synthetic task/models + synthetic loss clearly showcasing them (i.e. making it to where some significant mass of items will flip across the decision boundary as a result of the reconciliation), I would like to urge the authors to do just that as it will make the paper more logically coherent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "xM6sILiTmP", "reviewer": "Reviewer_x3z4", "summary": "The paper provides a framework using multi-calibration to reconcile model multiplicity in downstream decisions. It seeks to develop a framework to address the inherent discrepancies between predictive models, which often result in varying decision recommendations despite equivalent accuracy levels. The authors propose an algorithm that aligns predictive models with decision-making, improving agreement on best-response actions and losses. Empirical validation shows enhancements in downstream decision performance and addressing prediction disagreements, relevant to multi-calibration advancements. Proposed approach improves the consistency and utility of models in decision-based applications, including cases where only empirical data is available.", "questions": "Please see my questions above. Additionally: \n\n1) How does the framework perform across different domains or datasets that exhibit varying levels of complexity and noise?\n2) As mentioned, determining optimal ranges and conditions for key hyperparameters parameters across varying contexts can be challenging. \n3) Although the paper addresses computational efficiency, the scalability of the algorithm for very large datasets remains an open question. How will the computational complexity grow with increased data size?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a novel framework to address the issue of model multiplicity in predictive modeling for decision-making, using multi-calibration techniques. It identifies specific hyperparameters, such as loss margin and decision-calibration tolerance as the driving parameters of key results. In practice, these parameters will need to be adjusted to mediate trade-offs between model fairness and computational efficiency. The authors provide both theoretical insights and empirical validations of their approach. The paper makes a reasonable contribution by integrating theoretical multi-calibration concepts into empirical settings and testing them across multiple datasets.", "weaknesses": "Comments/Questions to Authors: \n•\tThe initial concept of multi-calibration was introduced by Hebert-Johnson et al. in 2017 which focused on ensuring fairness across overlapping subpopulations. Recent advancement includes extension of multi-calibration to game dynamics and multi-objective learning – for example, work by Nika Haghtalab and Eric Zhao, which utilize game dynamics to connect fairness and optimization. Another line of work by Roth et al deals with a wide array of issues from online multicalibrated learning to omnipredictors. While the article does a good job at comparing and showing differences with respect to work of Roth, the conceptual difference with respect to work of Haghtalab et al. would be much appreciated. \n\n•\tThe algorithm’s performance depends on several hyperparameters (such as loss margin and decision-calibration tolerance). It seems techniques to fine-tune parameters such as loss margin and decision-calibration tolerance are crucial for achieving the results and trade-offs that is important in practice (e.g., between prediction fairness and accuracy). These are critical for adapting multi-calibration models to robustly function across heterogeneous data distributions and complex decision environments, the paper should clearly discuss how the choice of these hyperparameters impact the performance of proposed algorithm. I am also curious about the third result of Theorem 3.2 (remark 3.3). How does the impact of this result show up in practice/experiments? I believe a major limitation of the paper is lack of explicit focus on loss margin and decision-calibration tolerance hyperparameters.\n\n•\tThe paper could better motivate the empirical tests conducted and discuss how they confirm the theoretical claims and show improvements in decision-making outcomes and model agreement. Avenues for future work on validating the proposed algorithm's effectiveness in real-world data scenarios should be discussed. \n\n•\tAdditional literature – please clarify the relationships / novelty of this paper with respect to work of these authors. I would be especially interested in knowing the relevance of this paper with issues of fairness-accuracy tradeoff.  \n\n“Inference for an Algorithmic Fairness-Accuracy Frontier,” Yiqi Liu and Francesca Molinari (2024). This work provides a consistent estimator for a fairness-accuracy frontier. Method for testing fairness-related hypotheses in algorithmic decision-making seems relevant. \n\n“Fair Representation: Guaranteeing Approximate Multiple Group Fairness for Unknown Tasks,” Xudong Shen and Yongkang Wong and Mohan S. Kankanhalli, IEEE Transactions on Pattern Analysis and Machine Intelligence (2021). Explores approximate fairness using fair representation across multiple fairness notions. \n\n“Multigroup Robustness,” Lunjia Hu and Charlotte Peale and Judy Hanwen Shen (2024). This work establishes a connection between multigroup fairness and robustness and discusses robustness algorithms tailored for subpopulations under data corruption.\n\n“Inherent Trade-Offs in the Fair Determination of Risk Scores,” J. Kleinberg and S. Mullainathan and Manish Raghavan (2016). Shows inherent trade-offs in algorithmic fairness in risk scores and formalizes three fairness conditions and proves their incompatibility in most cases.\n\n“Multi-group Agnostic PAC Learnability,” G. Rothblum and G. Yona, International Conference on Machine Learning (2021). Provides a framework for multi-group agnostic PAC learning.\n\nAlso important is work by Michael P. Kim et al. on Multiaccuracy: Black-Box Post-Processing for Fairness in Classification (2018): It introduces a foundational framework for ensuring fairness in classification, with a focus on multi-group fairness using multiaccuracy post-processing techniques. This paper sets a critical baseline for future research on fairness in predictions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)