Reconciling Model Multiplicity for Downstream Decision Making

## Abstract

Abstract We consider the problem of model multiplicity in downstream decision-making, a setting where two predictive models of equivalent accuracy cannot agree on the best-response action for a downstream loss function. We show that even when the two predictive models approximately agree on their individual predictions almost everywhere, it is still possible for their induced best-response actions to differ on a substantial portion of the population. We address this issue by proposing a framework that calibrates the predictive models with regard to both the downstream decision-making problem 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-maker. 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. Finally, we provide a set of experiments to empirically evaluate our methods: compared to existing work, our proposed algorithm creates a pair of predictive models with both improved downstream decision-making losses and agrees on their best-response actions almost everywhere.

## 1 Introduction

In many applications, individual probability prediction is at the heart of a decision-making process.
For example, in the Job Training Partnership Act (JTPA) training program (Bloom et al., ), a decision-maker may want to predict whether an individual is employed or not before assigning them to training; or in medical trials, a doctor wants to predict the probability that the patient has contracted a disease before recommending them a treatment. Since the hospital does not know the true individual probability that a particular patient is ill, they can only evaluate the individual probability predictions through its average outcome over a 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 to have multiple predictive models with similar accuracy but substantially different properties (Chen et al., ; Rodolfa et al., ; D’Amour et al., ). This phenomenon is called *predictive* (or model) multiplicity, a line of work studied by Breiman (); Marx et al. (); Black et al. ().

In a predictive multiplicity scenario, the decision-maker may have two or more predictive models that are nearly equivalent in terms of accuracy but disagree on their predictions on many individual samples. In our motivating example (Figure 1), the hospital has access to two models $f_{1}$ and $f_{2}$ predicting the probability of disease which are equally accurate on average over the entire population, but their predictions on a subpopulation may vastly differ. This disagreement in outcome prediction may have a disparate impact on the subpopulation if the hospital has to choose one predictor over the other to make important downstream decisions. For example, they might select a treatment based on the predicted probability that a patient has contracted a disease. Formally, given a predictive model $f$ and a decision-making loss function $\ell(y,\cdot)$, the decision-maker wants to choose a best-response action, i.e., the action $a$ that minimizes $\mathbb{E}_{y\sim f}[\ell(^{\prime},a)]$. When two models $f_{1}$ and $f_{2}$ have nearly equivalent accuracy but lead to different best-response actions, the decision-maker would not be able to 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 an additional burden on the decision-maker to correctly navigate such freedom and justify how they use a predictive model to make downstream decisions.

Roth et al. () attempts to address the model multiplicity issue by resolving prediction disagreement between models. Adapting techniques from the literature of multi-calibration (Hebert-Johnson et al., ), they provide a procedure called "Reconcile" that updates the predictive models to minimize their disagreements and improve the accuracy of each model. However, we show simple settings where the reconciled predictions from Roth et al. () can lead the downstream decision-makers 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 2.4 and Appendix A. This motivates the study of how to reconcile predictive multiplicity with an explicit focus on its impact on downstream decisions.

Figure: Figure 1: An illustrative example of the drawback in a prior work’s attempt at addressing model multiplicity. Consider a stylized binary classification problem on a dataset with $8$ units (patients) and the hospital deciding between two actions (treatment vs. no treatment). Treatment is assigned if the predicted probability is above 1/2. Left: The true probability that each patient is labeled ‘ill’. Middle: The predicted probability that each patient is ill according to $f_{1}$ (white) and $f_{2}$ (blue). While these two predictors have almost the same accuracy, their individual probability predictions for patients $3$ and $6$ vastly differ. Right: After running the Reconcile procedure of Roth et al. (), the individual probability predictions agree everywhere. However, the best-response action of unit $3$ changed from correct (no treatment) to incorrect (treatment). If the hospital uses the updated $f_{1}$ to make their treatment recommendation, they would incur more loss than before had they not updated the predictor using Reconcile. This example is formalized in Theorem 2.7.
Refer to caption: extracted/5630318/plots/counterexample/counterexample2.png

In this work, our goal is to leverage tools from multi-calibration (Hebert-Johnson et al., ) to alleviate the model multiplicity issue in high-dimensional decision-making tasks for multiple decision-makers with multiple decision-making loss functions. Specifically, we show how the decision-maker can update a pair of predictors so they approximately agree on (1) individual predictions and (2) best-response actions for each individual in the downstream decision-making task. Our procedure ensures that the number of disagreements in best-response actions decreases over time, which enables the decision-makers 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 downstream decision-making tasks, where the decision-makers have two predictive models with nearly equivalent accuracy but may lead to vastly different best-response actions for a significant number of individuals in the population. Our key contributions are summarized as follows.

- •
In Section 2, we formulate the problem of model multiplicity from the perspective of the decision-makers.
In Section 2.4, we formalize our motivating example in Figure 1 and show that it is insufficient to only update two predictive models so that they have improved accuracy and nearly agree on their individual predictions almost everywhere.
- •
In Section 3, we introduce an algorithm, ReDCal, that outputs predictive models that are (1) calibrated to a finite set of downstream decision-making tasks and (2) approximately agree on their predictions and best-response actions almost everywhere for each downstream task.
- •
In Section 3.2, we extend our analysis to the setting where one 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.
- •
Finally, in Section 4, 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-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., ; D’Amour et al., ; Black et al., ; Breiman, ), where solving an error minimization problem for some prediction tasks can lead to multiple solutions with roughly similar performance in terms of accuracy. Sandroni () showed that one cannot empirically distinguish the outcomes from a predictor encoding the true individual probabilities from one without in isolation. Al-Najjar and Weinstein (); Feinberg and Stewart () provided comparative tests to differentiate between the true probability predictor and one that is not. Particularly, Feinberg and Stewart () relied on *cross-calibration*, i.e., calibration conditional on the predictions of both models to empirically falsify one of them. For downstream decision-making, Garg et al. () worked on refining predictors and provided an algorithm that produces a predictor $f_{3}$ that is cross-calibrated with respect to both $f_{1}$ and $f_{2}$. An alternative framework studied by Globus-Harris et al. () 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.

Particularly relevant to our work is Roth et al. (), which 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 on their prediction on almost all units. Despite the similarity in our motivation, our results go beyond the binary classification setting considered in Roth et al. (). 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 a numerical example where simply reconciling the probability predictions according to Roth et al. () can lead to additional losses in downstream decision-making tasks.

#### Calibration and Multi-calibration.

Our work draws on techniques from the growing literature on multi-calibration (Hebert-Johnson et al., ; Kim et al., ; Dwork et al., ; Shabat et al., ; Jung et al., ; Dwork et al., ; Jung et al., ; Haghtalab et al., ; Deng et al., ; Noarov et al., ). Multi-calibration has been used as a notion of fairness as it guarantees calibration for any identifiable group.

Within the framework of multi-calibration, the work most related to ours is that of Zhao et al. (), who considered decision calibration with respect to all classes of loss functions. Similar to us, Zhao et al. () takes the perspective of a decision-maker who wants to ensure the predictive models are *indistinguishable* from the true probability when they are used to make downstream decisions. However, two decision-calibrated models can still disagree on their individual predictions and best-response actions for sufficiently many units. In our motivating example, a hospital with two decision-calibrated predictors may still want to make their predictive models approximately agree on their predictions for almost all individuals in the population and lead to the same downstream decision, i.e., whether to recommend treatment or not based on the predicted probability that a patient has contracted a disease. We formalize this example in Section 2.4 and provide empirical experiments to show our improvement over their result in Section 4.

An independent and concurrent work by Globus-Harris et al. () considers ensembling multiple predictive models for high-dimensional downstream decision-making tasks. While their work also leverages techniques from multi-calibration, their goal is to output an ensembled predictor whose self-estimated expected payoff is accurate and whose induced policy has a payoff at least as high as the maximum self-assessed payoff of individual models. In contrast, our interest is in reducing the downstream decision losses by resolving the differences between equivalent predictors and mitigating model multiplicity for decision-making.

## 2 Problem Formulation

#### Notation.

Throughout this paper, we use subscripts $i$ to index different predictions, superscripts $t$ to index different time-steps, and $a$ to index actions. For $K\in\mathbb{N}$, we use the shorthand $[K]\coloneqq\{1,2,\cdots,K\}$. $\Delta(\mathcal{X})$ denote the set of possible distributions over $\mathcal{X}$.

We consider the prediction problem with random variables $x$ and $y$, where $x\in\mathcal{X}$ represents the features and $y\in\mathcal{Y}$ represents the labels. We focus on the regression problem in which the label domain is real-valued and bounded: $\mathcal{Y}\subset[0,1]^{d}$. Our formulation also permits the multi-class classification problem by writing the label $y$’s as one-hot vectors, e.g., for $\left\lvert\mathcal{Y}\right\rvert=3$, we can write $\mathcal{Y}=\{[1,0,0],[0,1,0],[0,0,1]\}$.

We denote $\mathcal{D}\in\Delta(\mathcal{X}\times\mathcal{Y})$ as the true distribution over the pairs of features-label $(x,y)$. In practice, we will not have access to $\mathcal{D}$, and instead only know a set of $n$ data points $D$ sampled i.i.d from $\mathcal{D}$. In such case, we consider the dataset $D=\{(x_{1},y_{1}),\cdots,(x_{n},y_{n})\}$ to be the *empirical distribution* over $D$, which is a discrete distribution that place uniform weight $\nicefrac{{1}}{{n}}$ on each sample $(x,y)\in D$.

A predictor is a map $f:\mathcal{X}\rightarrow[0,1]^{d}$. Our goal is to find the Bayes optimal predictor $f^{*}:\mathcal{X}\rightarrow[0,1]^{d}$ such that for all $x\in\mathcal{X}$, $f^{*}(x)=\mathbb{E}_{(x,y)\sim\mathcal{D}}[y|x]$ is the *conditional label expectation given $x$*.

### 2.1 Model Evaluation

Given a predictor $f\in[0,1]^{d}$, we evaluate $f$ via its squared error, i.e., its 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 a predictor $f$ evaluated on distribution $\mathcal{D}$ is given as:

$$ $B(f,\mathcal{D})=\mathbb{E}_{(x,y)\sim\mathcal{D}}[\left\lVert f(x)-y\right \rVert_{2}^{2}]$ $$

When we only have a dataset $D=\{(x_{1},y_{1}),\cdots,(x_{n},y_{n})\}$, the empirical Brier score is given as:

$$ $B(f,D)=\frac{1}{n}\sum_{i=1}^{n}\left\lVert f(x_{i})-y_{i}\right\rVert_{2}^{2}$ $$

Note that we use the Brier score as our metric because it can be accurately estimated given access to 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 $\mathcal{D}$ and let $f^{*}(x)=\mathbb{E}_{(x,y)\sim\mathcal{D}}[y|x]$ represent the true conditional label encoded by $\mathcal{D}$. Let $f:\mathcal{X}\rightarrow[0,1]^{d}$ be any other model. Then we have $B(f^{*},\mathcal{D})\leq B(f,\mathcal{D})$.

Hence, given two predictors $f_{1}$ and $f_{2}$, if we can verify empirically from the observable data that $B(f_{1},\mathcal{D})\leq B(f_{2},\mathcal{D})$, then we can empirically falsify that $f_{2}$ encodes the true conditional label.

###### Definition 2.1 (Brier Score) .

###### Lemma 2.2 .

### 2.2 Downstream Decision-Making Tasks and Loss Functions

Beyond our initial goal of 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-maker has a set of possible actions $\mathcal{A}$ and a loss function $\ell:\mathcal{Y}\times\mathcal{A}\rightarrow[0,d]$. Wlog, we only consider action set $\mathcal{A}=[K]$, i.e., there are $K$ possible actions. In this paper, we assume that the loss function does not directly depend on the features $x$ and is linear in $\mathcal{Y}$. That is, for each action $a\in\mathcal{A}$, there exists some $\ell_{a}\in[0,1]^{d}$ such that

$$ $\ell(y,a)=\langle y,\ell_{a}\rangle$ $$

We write $\mathcal{L}=\{\ell:\mathcal{Y}\times\mathcal{A}\rightarrow[0,d]\}$ to denote a finite family of loss functions. In general, we consider the setting with multiple different decision-makers, each using a different linear loss function in $\mathcal{L}$. For any loss function $\ell:\mathcal{Y}\times\mathcal{A}\rightarrow\mathbb{R}$, we can rescale each coordinate of $\ell_{a}$ to be between $[0,1]$.

Given a predictor $f$ and a loss function $\ell$, the decision-maker selects an action $a\in\mathcal{A}$ that minimizes the expected loss. We define the best-response policy taken by the decision-maker as follows.

###### Definition 2.3 (Best-response policy) .

Given a loss function $\ell$, a predictor $f$ and the action set $\mathcal{A}$, the best-response policy for $\ell$ is given as

$$ $\pi_{\ell}^{\mathsf{BR}}(f(x))=\mathrm{argmin}_{a\in\mathcal{A}}\langle f(x), \ell_{a}\rangle.$ $$

###### Definition 2.3 (Best-response policy) .

### 2.3 Calibration

In our setting, we consider the decision-maker only having access to some pre-trained predictors $f$ 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 decision-maker will use 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 treatment-recommendation algorithm is not known to the public (and the data scientist), we assume that the data scientist initially aim to minimize the squared error in their predictions.

Since the hospital believes that the input predictors may not perform well according to their own loss function, they want the data scientist to convey trust through other performance guarantees of the predictors. One such guarantee is multi-calibration with respect to a finite set of loss functions $\mathcal{L}\ni\ell$ and a set of events $\mathcal{E}$ on the best-response policy, i.e., if the loss function $\ell$ belongs to $\mathcal{L}$, the decision-maker should be able to accurately compute the expected loss of choosing an action using the best-response policy $\pi_{\ell}^{\mathsf{BR}}$. Formally, we let $E_{a,\ell}(f(x),x)$ denote the action selection events:

###### Definition 2.4 (Best-response Events) .

Given a predictor $f$ and a loss function $\ell$, for each action $a\in[K]$, define the event

$$ $E_{\ell,a}(f(x),x)=\mathbf{1}\{x:\pi_{\ell}^{\mathsf{BR}}(f(x))=a\}$ $$

and let $\mathcal{E}=\{E_{\ell,a}\}_{a\in[K],\ell\in\mathcal{L}}$.

Given a set of events $\mathcal{E}$, we can define an approximate notion of multi-calibration with respect to $\mathcal{E}$.

###### Definition 2.5 ( $\beta$ -approximate decision calibration) .

A predictor $f$ is $\beta-$decision calibrated with respect to the set of best-response events $\mathcal{E}$ if for all $E_{\ell,a}\in\mathcal{E}$, we have:

$$ $\left\lVert\mathbb{E}_{(x,y)\sim\mathcal{D}}[(y-f(x))\cdot E_{\ell,a}(f(x),x)] \right\rVert_{2}\leq\beta.$ $$

This definition follows from an equivalent definition of decision calibration in Zhao et al. (). The main difference is we define calibration with respect to a set of events on the best-response actions following the formulation of multi-calibration for online learning in Noarov et al. () and a generalization of multi-calibration in Deng et al. ().
This definition implies that if a predictor $f$ is $\beta-$decision calibrated with respect to the best-response events $\mathcal{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,a^{\prime}\in\mathcal{A},\ell\in\mathcal{L}$, if $f$ is $\beta$-decision-calibrated with respect to the best-response events $\mathcal{E}$ , then the loss estimation satisfies

$$ $\displaystyle\left|\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,a^{\prime})\cdot E _{\ell,a}(f(x),x)]-\mathbb{E}_{x\sim\mathcal{D}_{\mathcal{X}}}[\langle f(x), \ell_{a^{\prime}}\rangle\cdot E_{\ell,a}(f(x),x)]\right|\leq\beta\sqrt{d}$ $$

###### Definition 2.4 (Best-response Events) .

###### Definition 2.5 ( β 𝛽 \beta italic_β -approximate decision calibration) .

###### Lemma 2.6 ( (Zhao et al., 2021 ) ) .

### 2.4 Limitations of Prior Works

In this section, we show that improving the accuracy until the two predictors agree on their predictions almost everywhere is not a sufficient solution to our problem. In our analysis below, we consider a stylized problem with $\mathcal{Y}=\{0,1\}$ and $\mathcal{A}=\{0,1\}$, i.e., binary class and binary action space. A predictor here is $f:\mathcal{X}\rightarrow[0,1]$, and the optimal predictor is $f^{*}(x)=\Pr_{(x^{\prime},y^{\prime})\sim\mathcal{D}}[y^{\prime}=1|x^{\prime}=x]$. As shorthand, we denote $f_{1}(1)$ as the probability of unit $1$ being labeled $1$. The loss is defined as

$$ $\displaystyle\ell(0,0)=\langle[1,0],[0,1]\rangle=0,\quad\ell(1,0)=\langle[0,1] ,[0,1]\rangle=1,$ $\displaystyle\ell(0,1)=\langle[1,0],[1,0]\rangle=1,\quad\ell(1,1)=\langle[0,1] ,[1,0]\rangle=0,$ (1) $$

That is, for any $x$, the best-response policy is to take action 0 0 if $f(x)\leq\nicefrac{{1}}{{2}}$ and action $1$ otherwise.

#### Reconcile individual predictions.

Prior work by Roth et al. () considers the model multiplicity problem for individual probability predictions. Their proposed algorithm, Reconcile (Algorithm 3), returns a pair of predictors that has a smaller Brier score than the input predictors and approximately agree on their predictions on almost all units. In the following theorem, we show that the best-response policy induced by the predictors updated by Reconcile might lead to a higher expected loss than the ones they started with.

###### Theorem 2.7 .

For any $\alpha\in(0,\nicefrac{{1}}{{3}})$, $\eta\in(0,1)$, there exists a pair of predictors $f_{1},f_{2}$ with equivalent accuracy such that after running Algorithm 3, the output models $f_{1}^{T},f_{2}^{T}$ agree on their individual predictions everywhere, but there exists a loss function $\ell(y,a)$ such that $f_{1}^{T}$ and $f_{2}^{T}$ induce worse losses compared to the original models.

###### Proof.

Consider a setting with $\mathcal{X}=[2]$ and $\Pr[x=1]=\Pr[x=2]=0.5$. For any $0<\alpha<\nicefrac{{1}}{{3}}$, let $\phi\geq\alpha$, we consider the two predictors $f_{1},f_{2}$ defined as follows:

$$ $\displaystyle f_{1}(1)=\frac{1}{2}-\frac{\phi}{2},\quad f_{1}(2)=\frac{1}{2}- \frac{3\phi}{2},\quad f_{2}(1)=\frac{1}{2}+\frac{\phi}{2},\quad f_{2}(2)=\frac {1}{2}-\frac{\phi}{2}$ (2) $$

and the true probability of each unit being labeled $1$ are $f^{*}(1)=0$ and $f^{*}(2)=1$.

The Brier scores of $f_{1}$ and $f_{2}$ differ only by $\phi^{2}$, but their individual predictions differ for both feature $x=1$ and $x=2$. We can run Algorithm 3 and patch $f_{1}$ to get the updated model $f_{1}^{T}$ with

$$ $f_{1}^{T}(1)=\frac{1}{2}+\frac{\phi}{2}=f_{2}(1),\quad f_{1}^{T}(2)=\frac{1}{2 }-\frac{\phi}{2}=f_{2}(2).$ $$

Consider the loss function $\ell$ defined as Equation 1.
The change in expected loss after patching $f_{1}$ is

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}} (f_{1}^{T}(x)))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{1}(x)))]=\frac{1}{2}>0.$ $$

Therefore, no matter how small we let $\alpha$ and $\eta$ be, the loss of predictor $f_{1}$ increases by a constant amount after running Algorithm 3. For the theoretical guarantees of Algorithm 3, see Appendix A.
∎

Moreover, we provide a counterexample to show that it is insufficient to only ensure each individual predictor is approximately decision-calibrated using Algorithm 1.

###### Theorem 2.7 .

###### Proof.

#### Decision-Calibrated predictions.

Another baseline algorithm we consider is to run Decision Calibration (Algorithm 1) separately for both $f_{1},f_{2}$. However, in the following theorem, we show that the updated predictors $f_{1}^{\prime}$ and $f_{2}^{\prime}$ can still disagree with each other on the best-response actions for substantially many units, indicating room for further improvement.

###### Theorem 2.8 .

For any $\eta\in(0,\nicefrac{{1}}{{4}})$ and $\beta\in(0,\nicefrac{{1}}{{2}})$, there exists a pair of predictors $f_{1},f_{2}$ and a loss function $\ell(y,a)$ such that after running Decision-Calibration (Zhao et al., ), the resulting models $f_{1}^{T},f_{2}^{T}$ are $\beta$-decision-calibrated with respect to the loss function $\ell$. There exists a set of units $x$ with probability mass $2\eta$ where $f_{1}^{T}$ and $f_{2}^{T}$ disagree on the individual best-response actions.

###### Proof.

For any $\eta\in(0,\nicefrac{{1}}{{4}}),\beta\in(0,\nicefrac{{1}}{{2}})$, let $\mathcal{X}=[4]$, with $\Pr[1]=\Pr[4]=\nicefrac{{1}}{{2}}-\eta$ and $\Pr[x=2]=\Pr[x=3]=\eta$. Consider the predictors $f_{1},f_{2}$ as follows:

$$ $\displaystyle f_{1}(1)=f_{1}(2)=f_{2}(1)=f_{2}(3)=\frac{\beta}{4}-2\eta\beta+2\eta,$ (3) $\displaystyle f_{1}(3)=f_{1}(4)=f_{2}(2)=f_{2}(4)=1-\frac{\beta}{2},$ (4) $\displaystyle f^{*}(1)=\frac{\beta}{2},~{}~{}f^{*}(2)=f^{*}(3)=f^{*}(4)=1- \frac{\beta}{2}.$ (5) $$

Notice that

$$ $\displaystyle\frac{\alpha}{4}-2\eta\alpha+2\eta=\frac{\alpha}{4}+2\eta(1- \alpha)<\frac{1}{4}+\frac{1}{4}=\frac{1}{2}.$ $$

The best-response policy for each predictor is

$$ $\displaystyle\pi_{\ell}^{\mathsf{BR}}(f_{1}(1))=\pi_{\ell}^{\mathsf{BR}}(f_{1} (2))=0,~{}~{}$ $\displaystyle\pi_{\ell}^{\mathsf{BR}}(f_{1}(3))=\pi_{\ell}^{\mathsf{BR}}(f_{1} (4))=1,$ (6) $\displaystyle\pi_{\ell}^{\mathsf{BR}}(f_{2}(1))=\pi_{\ell}^{\mathsf{BR}}(f_{2} (3))=0,~{}~{}$ $\displaystyle\pi_{\ell}^{\mathsf{BR}}(f_{2}(2))=\pi_{\ell}^{\mathsf{BR}}(f_{1} (4))=1.$ (7) $$

For each best-response event, we have

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[f^{*}(x)E_{0}(f_{1}(x),x)]$ $\displaystyle=\mathbb{E}_{(x,y)\sim\mathcal{D}}[f_{1}(x)E_{0}(f_{1}(x),x)],$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[f^{*}(x)E_{1}(f_{1}(x),x)]$ $\displaystyle=\mathbb{E}_{(x,y)\sim\mathcal{D}}[f_{1}(x)E_{1}(f_{1}(x),x)],$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[f^{*}(x)E_{0}(f_{2}(x),x)]$ $\displaystyle=\mathbb{E}_{(x,y)\sim\mathcal{D}}[f_{2}(x)E_{0}(f_{2}(x),x)],$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[f^{*}(x)E_{1}(f_{2}(x),x)]$ $\displaystyle=\mathbb{E}_{(x,y)\sim\mathcal{D}}[f_{2}(x)E_{1}(f_{2}(x),x)].$ $$

That is, $f_{1},f_{2}$ are already decision-calibrated, so running Decision Calibration (Algorithm 1) will not further improve either of the two predictors. However, based on our definition of disagreement events (Definition 3.1), we still have

$$ $\displaystyle E_{0,1}=\{2\},~{}~{}E_{1,0}=\{3\},$ $$

each with size

$$ $\displaystyle\mu(E_{0,1})=\mu(E_{1,0})=\eta.$ $$

We observe that $f_{1}$ and $f_{2}$ still disagree on the best-response action for units $x=2$ and $x=3$.
We can further reduce the differences in best-response actions using our algorithm Algorithm 2.
∎

###### Theorem 2.8 .

###### Proof.

## 3 Reconcile for Decision Making

Suppose we are given two predictors $f_{1},f_{2}:\mathcal{X}\rightarrow[0,1]^{d}$. We consider the model multiplicity problem with respect to the downstream decision-making problem – where $f_{1},f_{2}$ with nearly equivalent accuracy differ in their induced decision-making policies, but we cannot falsify either of the two from the data. Informally, our goal is to return a pair of models $f_{1}^{\prime},f_{2}^{\prime}$ such that: (1) for both $i\in\{1,2\}$, $f_{i}^{\prime}$ is more accurate than $f_{i}$ in terms of Brier score; (2) for both $i\in\{1,2\}$, the best-response policy induced by $f_{i}^{\prime}$ has no larger expected loss than that of $f_{i}$; (3) $f_{1}^{\prime}$ and $f_{2}^{\prime}$ 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 decision-making task. We define the disagreement region as follows:

###### Definition 3.1 (Disagreement Event) .

For $f_{1},f_{2}$, margin $\alpha>0$, and a loss function $\ell$, the disagreement event is defined for a pair of best-response actions $a_{1},a_{2}\in\mathcal{A}$ where $a_{1}\neq a_{2}$ as

$$ $\displaystyle E^{\alpha}_{\ell,a_{1},a_{2}}(f_{1}(x),f_{2}(x),x)=\mathbb{I} \Big{[}x\in\big{\{}x:$ $\displaystyle\pi_{\ell}^{\mathsf{BR}}(f_{1}(x))=a_{1},\pi_{\ell}^{\mathsf{BR}} (f_{2}(x))=a_{2},$ $\displaystyle\langle f_{1}(x),\ell_{a_{2}}-\ell_{a_{1}}\rangle>\alpha~{}\text{ or}~{}\langle f_{2}(x),\ell_{a_{1}}-\ell_{a_{2}}\rangle>\alpha\big{\}}\Big{]},$ $$

As shorthand, we denote $E_{\ell,a_{1},a_{2}}(x)=E^{\alpha}_{\ell,a_{1},a_{2}}(f_{1}(x),f_{2}(x),x)$ when the predictors $f_{1},f_{2}$ and the margin $\alpha$ are clear from context. For a finite family of loss functions $\mathcal{L}$, we can always iterate through $\mathcal{L}$ to identify the tuple $(\ell,a_{1},a_{2})$ that defines a disagreement region between $f_{1}$ and $f_{2}$.

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 $\mu(E_{\ell,a_{1},a_{2}})$ on the underlying distribution $\mathcal{D}$ is small.

###### Definition 3.1 (Disagreement Event) .

### 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 $E_{\ell,a_{1},a_{2}}$, 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 $t$ and a unit $x$, if the gap between the losses after taking $a_{1}$ and $a_{2}$ according to $f_{2}$ is substantially different from the loss gap observed on the data, then the decision-maker can induce that $f_{2}$ must have been wrong in its prediction for $x$.
Then, the decision-maker would want to ’patch’ predictor $f_{2}$ in this time-step.

The calibration procedure within each time-step is divided into two stages. In the first stage, we update model $f_{2}$ to $f_{2}^{\prime}$ by minimizing the mean prediction error on the disagreement event, i.e., minimizing $\mathbb{E}[\|f_{2}^{\prime}(x)-y|E_{\ell,a_{1},a_{2}}(x)=1\|]$. Following the intuition from multi-calibration, updating predictor $f_{2}$ in this manner would improve the Brier score and produce a more accurate predictor.
However, the updated model $f^{\prime}_{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}^{\prime}$ to a model $f_{2}^{\prime\prime}$ that is approximately decision-calibrated within event $E_{\ell,a_{1},a_{2}}$ using Algorithm 1. Since the loss estimation given by $f_{2}^{\prime\prime}$ is accurate for all best-response events within $E_{\ell,a_{1},a_{2}}$ and we are taking actions to minimize estimated loss, we can now safely take the best-response action induced by $f_{2}^{\prime\prime}$. The formal description of the algorithm is given by Algorithm 2.

Figure: Algorithm 1 Decision Calibration

Figure: Algorithm 2 Reconcile Decision Calibration (ReDCal)

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. For the formal proofs of this section, see Appendix B.

###### Theorem 3.2 .

For any pair of models $f_{1},f_{2}:\mathcal{X}\rightarrow[0,1]^{d}$, any distribution $\mathcal{D}$, family of loss functions $\mathcal{L}$, any loss margin $\alpha>0$, disagreement region mass $\eta>0$, and decision-calibration tolerance $\beta>0$, Algorithm 2 updates $f_{1}$ and $f_{2}$ for $T_{1}$ and $T_{2}$ time-steps, respectively,
and outputs a pair of models $(f_{1}^{T},f_{2}^{T})$, such that:

- 1.
Algorithm 2 terminates within $T=T_{1}+T_{2}\leq\frac{4\cdot d\cdot\left(B(f_{1},\mathcal{D})+B(f_{2},
\mathcal{D})\right)}{\alpha^{2}\eta}$ time-steps.
- 2.
The Brier scores of the final models are lower than that of the input models $(f_{1},f_{2})$:
$B(f_{1}^{T},\mathcal{D})\leq B(f_{1},\mathcal{D})-T_{1}\cdot\frac{\alpha^{2}
\eta}{4d}\quad\text{and }\quad B(f_{2}^{T},\mathcal{D})\leq B(f_{2},\mathcal{D
})-T_{2}\cdot\frac{\alpha^{2}\eta}{4d}$
- 3.
All the downstream decision-making losses of the final models do not increase by much compared to that of the input models $(f_{1},f_{2})$: for each $i\in\{1,2\}$ and for all $\ell\in\mathcal{L}$,
$\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{T}(x)
)]-\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}(x))
]\leq T_{i}\beta\sqrt{d}K$
- 4.
The final models approximately agree on their best-response actions almost everywhere. That is, the disagreement region $E_{\ell,a_{1},a_{2}}$ calculated using $f_{1}^{T},f_{2}^{T}$ has small mass. For all $\ell\in\mathcal{L}$,
$\mu(E_{\ell,a_{1},a_{2}})<\eta\quad\text{ for all }a_{1},a_{2}\in\mathcal{A}
\quad\text{s.t }a_{1}\neq a_{2}$

###### Remark 3.3 .

Note that in the third result of Theorem 3.2, the increase in downstream decision-making loss at each time-step only depends on the decision-calibrate tolerance $\beta$, dimension $d$, and number of actions $K$. Since the total number of time-steps in Theorem 3.2 does not depend on $\beta$, we can set $\beta=\frac{\alpha}{T\sqrt{d}K}$ to ensure the loss of taking the best-response action does not degrade by more than $\alpha$. Moreover, in our empirical experiments (Section 4), we observe that the loss of taking the best-response action only increases minimally.

###### Theorem 3.2 .

###### Remark 3.3 .

### 3.2 Finite Sample Analysis

In Section 3.1, we have presented an algorithm, ReDCal, to reconcile two predictors assuming the decision-makers have direct access to the probability distribution $\mathcal{D}$. However, in practice, the decision-makers will only have access to a dataset $D=\{(x_{1},y_{1}),\cdots,(x_{n},y_{n})\}$ containing $n$ i.i.d samples drawn from $\mathcal{D}$. In this section, we will instead run Algorithm 2 on the empirical distribution over $D$ and show that its guarantees can translate to the underlying distribution $\mathcal{D}$ with high probability. To prevent data leakage, it is important to assume that the dataset $D$ is drawn independently of the predictors $f_{1}$ and $f_{2}$, i.e., the dataset contains freshly drawn data that was not used to train either of the predictors that we want to reconcile. For the formal proofs, see Appendix C.

At a high level, since the samples in $D$ are independently and identically distributed, we can apply Chernoff-Hoeffding inequality to show that, with high probability, the in-sample quantities are approximately equal to out-sample quantities. We summarize the results in the theorem below.

###### Theorem 3.4 .

Fix any distribution $\mathcal{D}$ and dataset $D\sim\mathcal{D}$ containing $n$ samples drawn i.i.d from $\mathcal{D}$. For any pair of predictors $f_{1},f_{2}:\mathcal{X}\rightarrow[0,1]^{d}$, family of loss functions $\mathcal{L}$, loss margin $\alpha>0$, disagreement region mass $\eta>0$, and decision-calibration tolerance $\beta>0$, Algorithm 2 run over the empirical distribution $D$ updates $f_{1}$ and $f_{2}$ for $T_{1}$ and $T_{2}$ time-steps, respectively, and outputs a pair of predictors $(f_{1}^{T},f_{2}^{T})$ such that, with probability at least $1-\delta$ over the randomness of $D\sim\mathcal{D}^{n}$,

- 1.
The total number of time-steps for Algorithm 2 and Algorithm 1 is
$T=T_{1}+T_{2}\leq\frac{2d}{\min\{\beta^{2},\eta\alpha^{2}/4d\}}$
- 2.
For $i\in\{1,2\}$, the Brier scores of the final models are lower than that of the input models:
$\displaystyle B(f_{i}^{T_{i}},\mathcal{D})\leq B(f_{i},\mathcal{D})-(T_{i}/2)
\cdot\min\left\{\beta^{2},\eta\alpha^{2}/(4d)\right\}$
- 3.
For $i\in\{1,2\}$ and for all $\ell\in\mathcal{L}$, the downstream decision-making losses of the final models do not increase by much compared to that of the input models:
$\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}}
(f_{i}^{T}(x))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}(x))]\leq 2T_{i}\beta\sqrt
{d}K$
- 4.
The final models approximately agree on their best-response actions almost everywhere. That is, the disagreement region $E_{\ell,a_{1},a_{2}}$ calculated using $f_{1}^{T},f_{2}^{T}$ has small mass: $\forall\ell\in\mathcal{L}$,
$\mu(E_{\ell,a_{1},a_{2}})\leq 2\eta\quad\text{ for all }a_{1},a_{2}\in\mathcal
{A}\quad\text{s.t }a_{1}\neq a_{2}$

if $n\geq\Omega\left(d/(\eta^{2}\min\{\beta,\eta\alpha^{2}/d\})\cdot\left(\ln(K)+
\ln(\left\lvert\mathcal{L}\right\rvert)+d\ln\left(d/\min\{\beta,\eta\alpha^{2}
/d\}\right)+\ln(1/\delta)\right)\right).$

###### Theorem 3.4 .

## 4 Experiments

In this section, we complement our theoretical results with a set of experiments on real-world datasets to show our improvement in decreasing decision-making loss compared to prior work in calibration.

### 4.1 Imagenet Multi-class Classification

#### Experiment Setup.

We use the ImageNet dataset (Deng et al., ) and two pre-trained models provided by pyTorch (inception-v3 (Szegedy et al., ) and resnet50 (He et al., )). 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), Decision-Calibration (Algorithm 1), ReDCal (Algorithm 2), and the combination of 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\in\mathcal{Y}$, $a\in\mathcal{A}$, $\ell(y,a)\sim\mathsf{Normal}(0,1)$. For each randomly generated loss function $\ell$, we compare the expected losses derived from the best-response policies based on predictors $f_{1}$ and $f_{2}$ against those based on the optimal predictor $f^{*}$. Formally, the loss gap at timestep $t$ using predictor $f_{i}$ is defined as

$$ $\text{LossGap}(f_{i}^{t})=\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^ {\mathsf{BR}}(f_{i}^{t}(x)))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f^{*}(x)))].$ $$

The hyperparameters are chosen as follows: loss margin $\alpha=0.001$, disagreement region mass $\eta=0.01$, decision-calibration tolerance $\beta=0.00001$, and the number of actions $K=10$.

#### Results.

We compare the performance of ReDCal with the two baseline algorithms in terms of Brier scores and decision loss reduction. Furthermore, in Figure 4, we provide a comparison of the calibration algorithms’ performance when the number of dimensions increases.

#### Brier score.

In Figure 2, 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 algorithm decreases the Brier score by a smaller amount on the test dataset. The combined algorithm of Decision-Calibration with ReDCal as post-process achieves the most substantial decrease in the Brier score.

Figure: Figure 2: ReDCal decreases Brier score on Imagenet. Compared to Reconcile, our algorithm decreases the Brier score by a smaller amount on the test dataset. Decision-Calibration with ReDCal as post-process achieves the most substantial decrease in the Brier score.
Refer to caption: extracted/5630318/plots/ImageNet/withgap_brier_100classes_10actions_500.png

#### Decision loss on calibration dataset.

In Figure 3, we compare the decision gap of our proposed algorithm with the two baseline algorithms on the training dataset.
Compared to Reconcile, ReDCal converges within a similar number of time-step and decreases the loss by a larger amount on the test dataset. Moreover, ReDCal further decrease the loss when used as a post-process after Decision-Calibration terminates.

Figure: (a) ReDCal decreases the decision loss on the validation partition of the ImageNet dataset.
Refer to caption: extracted/5630318/plots/ImageNet/withgap_loss_100classes_10actions_500_train.png

#### Decision loss comparison for high-dimensional classification problem.

In Figure 4, we compare the decision loss gap of our proposed algorithm with the two baseline algorithms on the testing dataset, using $d=10,100$, and $1000$ classes. We plot the average loss gap of the two predictors.
The hyperparameters are: disagreement margin $\alpha=0.1/d$, decision-calibration tolerance $\beta=0.001/d$, disagreement region mass $\eta=0.01$, number of actions $K=10$.

Figure: Figure 4: ReDCal decreases decision loss on Imagenet. The takeaway results are similar to Figure 3(b). As the number of classes in the multi-class classification problem grows from $10$ to $1000$, ReDCal still outperforms Reconcile in decreasing decision loss on the test dataset. When we have $1000$ classes, ReDCal converges slower than Reconcile. Furthermore, ReDCal can further decrease the decision loss when it is used as a post-process after Decision Calibration terminates.
Refer to caption: extracted/5630318/plots/ImageNet/compare_loss_10actions_500_test.png

### 4.2 HAM10000 Multi-class Classification

#### Experiment Setup.

We use the HAM10000 dataset (Tschandl et al., ) (licensed CC BY-NC $4.0$) on pigmented skin lesions to predict the probability that a patient has contracted one of $7$ possible skin diseases: ’akiec’, ’bcc’, ’bkl’, ’df’, ’nv’, ’vasc’, and ’mel’. We split the dataset into train/validation/test 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 pyTorch with resnet50 (He et al., ) and densenet121 (Huang et al., ) architectures and learn two models with around $88\%$ top-$1$ accuracy. From each model, we output the individual probability prediction for each of the $7$ 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 run each calibration algorithm $10$ times. At each run, we draw a fresh loss function created based on the loss function motivated by medical domain knowledge in Zhao et al. () and additional random noise drawn from $\mathsf{Normal}(0,1)$. There are two possible actions for the decision-maker: treatment ($a=[1,0]$) or no treatment ($a=[0,1]$). Given a loss function $\ell$ 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 2 are chosen as follows: loss margin $\alpha=0.1$, target disagreement region mass $\eta=0.01$, and decision-calibration tolerance $\beta=0.000001$.

#### Results.

Similar to the experiment on the ImageNet dataset, we observe lower decision loss after running ReDCal compared to the baseline algorithm Reconcile. Moreover, we compare the performance of running Decision-Calibration on its own and using ReDCal as a post-process.

#### Brier score.

In Figure 5, 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 proposed algorithm decreases the Brier score by a smaller amount.

Figure: Figure 5: Brier score of the updated predictors using Algorithm 2 (orange) and two benchmark algorithms: Algorithm 3 (dashed-blue) and Algorithm 1 (dashed-green). Our algorithm reduces the Brier score by a smaller amount compared to Algorithm 2. Results are averaged over $10$ runs and the shaded region indicates $\pm 1$ standard error.
Refer to caption: extracted/5630318/plots/HAM/HAM_brier.png

#### Decision loss.

In Figure 6, 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 a larger amount on the test dataset. Furthermore, while Decision-Calibration already decreases the decision loss, our algorithm can further improve upon their result when it is used as a post-process after Decision-Calibration terminates.

Figure: (a) ReDCal decreases the decision loss on the validation partition of HAM10000 dataset.
Refer to caption: extracted/5630318/plots/HAM/HAM_decision_loss_train.png

## 5 Conclusion

Predictive multiplicity is a phenomenon in machine learning where the decision-makers have two predictors with nearly equivalent accuracy but vastly different individual predictions. We propose an algorithm, ReDCal, that updates the pair of predictors using either true distribution or an i.i.d validation set until they approximately agree almost everywhere on (1) individual predictions, (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. This result helps alleviate the problem of predictive multiplicity in model selection. Finally, we provide experiments using real-world datasets to show that our proposed algorithm achieves lower decision loss compared to existing work. While we do not provide examples of domain-specific loss functions as part of our analysis and experiments, we hope that our findings can aid future studies on the impact of model multiplicity in decision-making.

## Appendix A Limitation of Prior Work (Continue)

We provide the Algorithm 3 from [Roth et al., ] and their theoretical guarantees for completion. First, given two predictors $f_{1}$ and $f_{2}$, define the disagreement region as:

$$ $\displaystyle U_{\epsilon}(f_{1},f_{2})\coloneqq\{x:\left\lvert f_{1}(x)-f_{2} (x)\right\rvert>\epsilon\}$ $$

which can be further divided into two partitions:

$$ $\displaystyle U_{\epsilon}^{>}(f_{1},f_{2})$ $\displaystyle=\{x\in U_{\epsilon}(f_{1},f_{2}):f_{1}(x)>f_{2}(x)\}$ $\displaystyle U_{\epsilon}^{<}(f_{1},f_{2})$ $\displaystyle=\{x\in U_{\epsilon}(f_{1},f_{2}):f_{1}(x)<f_{2}(x)\}$ $$

Figure: Algorithm 3 Reconcile [Roth et al., ]

###### Theorem A.1 (Reconcile [Roth et al., 2023 ] ) .

For any pair of models $f_{1},f_{2}:\mathcal{X}\rightarrow[0,1]$, any distribution $\mathcal{D}$, and any $\alpha,\eta>0$, Algorithm 3 runs for $T=T_{1}+T_{2}$ many rounds and outputs a pair of models $(f_{1}^{T_{1}},f_{2}^{T_{2}})$ such that:

- 1.
$T\leq(B(f_{1},\mathcal{D})+B(f_{2},\mathcal{D}))\cdot\frac{16}{\eta\alpha^{2}}$
- 2.
$B(f_{1}^{T_{1}},\mathcal{D})\leq B(f_{1},\mathcal{D})-T_{1}\cdot\frac{\eta
\alpha^{2}}{16}$ and $B(f_{2}^{T_{2}},\mathcal{D})\leq B(f_{2},\mathcal{D})-T_{2}\cdot\frac{\eta
\alpha^{2}}{16}$
- 3.
$\mu(U_{\epsilon}(f_{1}^{T_{1}},f_{2}^{t_{2}}))\leq\eta$

###### Theorem A.1 (Reconcile [Roth et al., 2023 ] ) .

## Appendix B Proofs of Section 3.1 : Reconcile for Decision Making

First, we show that if a disagreement event has a large probability mass, then at least one of $f_{1}$, $f_{2}$ has a large prediction error within the region:

###### Lemma B.1 .

Fix any two predictors $f_{1},f_{2}:\mathcal{X}\rightarrow[0,1]^{d}$ and $\alpha,\eta>0$. If $\mu(E_{\ell,a_{1},a_{2}})>\eta$ for some $a_{1},a_{2}\in\mathcal{A}$, then we have

$$ $\displaystyle\|\mathbb{E}_{x\sim\mathcal{X}}\left[f_{i}(x)-f^{*}(x)\big{|}E_{ \ell,a_{1},a_{2}}(x)\right]\|\geq\frac{\alpha}{2\sqrt{d}}$ (8) $$

for some $i\in\{1,2\}$.

###### Proof.

By definition of event $E_{\ell,a_{1},a_{2}}$, we have

$$ $\displaystyle\mathbb{E}_{x\sim\mathcal{X}}\left[\ell(f_{1}(x),a_{2})-\ell(f_{1 }(x),a_{1})+\ell(f_{2}(x),a_{1})-\ell(f_{2}(x),a_{2})]|E_{\ell,a_{1},a_{2}}(x) \right]\geq\alpha$ $$

Also, we have

$$ $\displaystyle\mathbb{E}_{x\sim\mathcal{X}}\left[\ell(f_{1}(x),a_{2})-\ell(f_{1 }(x),a_{1})+\ell(f_{2}(x),a_{1})-\ell(f_{2}(x),a_{2})]|E_{\ell,a_{1},a_{2}}(x)\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{x\sim\mathcal{X}}\left[\langle f_{1}(x)-f_{2}(x),\ell _{a_{2}}-\ell_{a_{1}}\rangle|E_{\ell,a_{1},a_{2}}(x)\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{x\sim\mathcal{X}}\left[\langle f_{1}(x)-f^{*}(x),\ell _{a_{2}}-\ell_{a_{1}}\rangle|E_{\ell,a_{1},a_{2}}(x)\right]$ $\displaystyle\quad+\mathbb{E}_{x\sim\mathcal{X}}\left[\langle f^{*}(x)-f_{2}(x ),\ell_{a_{2}}-\ell_{a_{1}}\rangle|E_{\ell,a_{1},a_{2}}(x)\right]$ $\displaystyle\leq$ $\displaystyle\|\mathbb{E}_{x\sim\mathcal{X}}\left[f_{1}(x)-f^{*}(x)\big{|}E_{ \ell,a_{1},a_{2}}(x)\right]\|_{2}\sqrt{d}+\|\mathbb{E}_{x\sim\mathcal{X}}\left [f_{2}(x)-f^{*}(x)\big{|}E_{\ell,a_{1},a_{2}}(x)\right]\|_{2}\sqrt{d}$ $\displaystyle=$ $\displaystyle\sqrt{d}\cdot\left(\|\mathbb{E}_{x\sim\mathcal{X}}\left[f_{1}(x)- f^{*}(x)\big{|}E_{\ell,a_{1},a_{2}}(x)\right]\|_{2}+\|\mathbb{E}_{x\sim \mathcal{X}}\left[f_{2}(x)-f^{*}(x)\big{|}E_{\ell,a_{1},a_{2}}(x)\right]\|_{2}\right)$ $$

where the last inequality comes from Cauchy-Schwartz and that $\ell$ is bounded in $[0,1]$.

Combining the above inequalities, we have

$$ $\displaystyle\sqrt{d}\cdot\left(\left\lVert\mathbb{E}_{x\sim\mathcal{X}}\left[ f_{1}(x)-f^{*}(x)\big{|}E_{\ell,a_{1},a_{2}}(x)\right]\right\rVert_{2}+\left \lVert\mathbb{E}_{x\sim\mathcal{X}}\left[f_{2}(x)-f^{*}(x)\big{|}E_{\ell,a_{1} ,a_{2}}(x)\right]\right\rVert_{2}\right)\geq\alpha.$ $$

Therefore, for some $i\in\{1,2\}$, we have

$$ $\displaystyle\left\lVert\mathbb{E}_{x\sim\mathcal{X}}\left[f_{i}(x)-f^{*}(x) \big{|}E_{\ell,a_{1},a_{2}}(x)\right]\right\rVert_{2}\geq\frac{\alpha}{2\sqrt{ d}}.$ $$

∎

This lemma indicates that, if we have two predictors $f_{1},f_{2}$ that create a large disagreement event, we can falsify at least one of the models. We now show that these events also provide a directly actionable way to improve one of the models.

###### Lemma B.2 .

For any predictor $f:\mathcal{X}\rightarrow[0,1]^{d}$, any event $E\in\mathcal{E}$, and distribution $\mathcal{D}$. Let $\phi=\mathbb{E}_{(x,y)\sim\mathcal{D}}[y-f(x)|E(x)=1]$. We patch $f$ as

$$ $f^{\prime}(x)=\mathrm{proj}_{[0,1]^{d}}(f(x)+\phi E(x)),~{}~{}\text{where}~{}~ {}\mathrm{proj}_{[0,1]^{d}}(y)=\mathrm{argmin}_{y^{\prime}\in[0,1]^{d}}\|y-y^{ \prime}\|_{2}.$ $$

Then,

$$ $B(f,\mathcal{D})-B(f^{\prime},\mathcal{D})\geq\|\phi\|^{2}_{2}\mu(E).$ $$

###### Proof.

$$ $\displaystyle B(f,\mathcal{D})-B(f^{\prime},\mathcal{D})=$ $\displaystyle\mathbb{E}\left[\|f(x)-y\|_{2}^{2}-\|f^{\prime}(x)-y\|_{2}^{2}\right]$ $\displaystyle\geq$ $\displaystyle\mathbb{E}\left[\|f(x)-y\|_{2}^{2}-\|f(x)+\phi E(x)-y\|_{2}^{2}\right]$ (since projection is non-expansive) $\displaystyle=$ $\displaystyle\mathbb{E}\left[2\langle y-f(x),\phi E(x)\rangle-\|\phi E(x)\|_{2 }^{2}\right]$ $\displaystyle\geq$ $\displaystyle\|\phi\|_{2}^{2}\cdot\mu(E)$ $$

∎

Therefore, whenever we have two predictors that have a large disagreement event, we can always falsify at least one of the predictors and improve it through patching, causing the Brier score to decrease by a large amount. Similarly, for a fixed predictor, if one of its best-response events has a 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 1 are bounded.

Other than the Brier score, we also care about minimizing the loss of the downstream decision-making task. We now show that, after a further update through the subroutine Algorithm 1, the loss does not increase much at each time-step of Algorithm 2:

###### Lemma B.3 .

For any predictors $f_{1},f_{2}$, loss function $\ell\in\mathcal{L}$ and any distribution $\mathcal{D}$, at any time-step $t$ of Algorithm 2, the predictors satisfies

$$ $\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t+1}( x)))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t}(x)))]\leq\beta\sqrt{d}K,$ $$

for all $i\in\{1,2\}$.

###### Proof.

At each round, we define the set $\Delta_{a}^{t}\subseteq E^{t}$ as

$$ $\displaystyle\Delta_{a}^{t}=\{x\in E^{t}:\pi_{\ell}^{\mathsf{BR}}(f^{t+1}_{i}( x))=a\}.$ $$

Then, we have

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}} (f_{i}^{t+1}(x)))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t}(x)))]$ $\displaystyle=$ $\displaystyle\sum_{a\in\mathcal{A}}\mathbb{E}_{(x,y)\sim\mathcal{D}}[(\ell(y,a )-\ell(y,a_{i}^{t}))\Delta_{a}^{t}(x)].$ $$

For each term in the summation, we can upper-bound it as

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[(\ell(y,a)-\ell(y,a_{i}^{t})) \Delta_{a}^{t}(x)]$ (9) $\displaystyle=$ $\displaystyle\langle\mathbb{E}_{(x,y)\sim\mathcal{D}}[y\Delta_{a}^{t}(x)],\ell _{a}-\ell_{a_{i}^{t}}\rangle$ (Linearity of Expectation) $\displaystyle\leq$ $\displaystyle\langle\mathbb{E}_{x\sim\mathcal{D}_{\mathcal{X}}}[f_{i}^{t+1}(x) \Delta_{a}^{t}(x)],\ell_{a}-\ell_{a_{i}^{t}}\rangle+\beta\sqrt{d}$ (Since $f_{i}^{t+1}$ is $\beta$ -calibrated) $\displaystyle\leq$ $\displaystyle\beta\sqrt{d}.$ (Since $a$ is the new Best-response action) $$

Summing these actions together, we have

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}} (f_{i}^{t+1}(x)))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t}(x)))]\leq\beta \sqrt{d}K.$ (10) $$

∎

Instead of setting a fixed $\beta$, we can calculate a different $\beta^{t}$ at each round, which allows a smaller increase in loss.

###### Lemma B.4 .

At each round $t$, if $a_{i}^{t}$ is not the best action on $E^{t}$ in average, i.e.

$$ $\delta^{t}=\max_{a\in\mathcal{A}}\mathbb{E}_{(x,y)\sim\mathcal{D}}[(\ell(y,a_{ i}^{t})-\ell(y,a))E^{t}(x)]>0,$ $$

then we can set $\beta^{t}\leq\delta^{t}/\sqrt{d}$, such that

$$ $\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t+1}( x)))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t}(x)))]\leq 0.$ $$

###### Proof.

We can write the change in loss at each round as

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}} (f_{i}^{t+1}(x)))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t}(x)))]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}} (f_{i}^{t+1}(x)))-\ell(y,a_{i}^{t}))E^{t}(x)]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}} (f_{i}^{t+1}(x)))-\ell(y,a^{\prime}))E^{t}(x)]+\mathbb{E}_{(x,y)\sim\mathcal{D }}[\ell(y,a^{\prime})-\ell(y,a_{i}^{t}))E^{t}(x)]$ $\displaystyle=$ $\displaystyle\sum_{a\in\mathcal{A}}\mathbb{E}_{(x,y)\sim\mathcal{D}}[(\ell(y,a )-\ell(y,a^{\prime}))\Delta_{a}^{t}(x)]+\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell (y,a^{\prime})-\ell(y,a_{i}^{t}))E^{t}(x)],$ $$

for any $a^{\prime}\in\mathcal{A}$.

We can use the same analysis as in Lemma B.3 to get

$$ $\sum_{a\in\mathcal{A}}\mathbb{E}_{(x,y)\sim\mathcal{D}}[(\ell(y,a)-\ell(y,a^{ \prime}))\Delta_{a}^{t}(x)]\leq\beta^{t}\sqrt{d}.$ $$

For the second term, we would want the loss to be as small as possible, so we can choose $\displaystyle a^{\prime}=\mathrm{argmin}_{a\in\mathcal{A}}\mathbb{E}_{(x,y)
\sim\mathcal{D}}[\ell(y,a)\cdot E^{t}(x)]$ and let

$$ $\displaystyle\delta^{t}=-\mathbb{E}_{(x,y)\sim\mathcal{D}}[(\ell(y,a^{\prime}) -\ell(y,a_{i}^{t}))E^{t}(x)],$ (11) $$

then $\delta^{t}$ is maximized and $\delta^{t}\geq 0$ by definition.

The total change in loss in this round can be written as

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}} (f_{i}^{t+1}(x)))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t}(x)))]\leq\beta^{t} \sqrt{d}-\delta^{t}.$ $$

If $\delta^{t}>0$, we can set $\beta^{t}\leq\delta^{t}/\sqrt{d}$ to ensure the loss does not increase at this round.

∎

###### Lemma B.1 .

###### Proof.

###### Lemma B.2 .

###### Proof.

###### Lemma B.3 .

###### Proof.

###### Lemma B.4 .

###### Proof.

### B.1 Proof of Theorem 3.2

###### Proof.

By Lemma B.1 and B.2, for any $i\in\{1,2\}$, at time-step $t$, we have the inequality

$$ $\displaystyle B(f_{i}^{t},\mathcal{D})-B(f_{i}^{t+1},\mathcal{D})\geq\frac{ \alpha^{2}\eta}{4d}.$ $$

Taking the sum over all time-steps, we have for any $i\in\{1,2\}$,

$$ $\displaystyle B(f_{i},\mathcal{D})-B(f_{i}^{T},\mathcal{D})\geq T_{i}\cdot \frac{\alpha^{2}\eta}{4d}.$ $$

Since the Brier score is always non-negative, we have

$$ $\displaystyle T_{i}\leq\frac{4d\cdot B(f_{i},\mathcal{D})}{\alpha^{2}\eta}.$ $$

Second, using Lemma B.3 and summing over all time-steps, we have

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}} (f_{i}^{T}(x))]-\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{ BR}}(f_{i}(x))]$ (12) $\displaystyle=$ $\displaystyle\sum_{t=1}^{T}\mathbb{I}[i_{t}=i]\mathbb{E}_{(x,y)\sim\mathcal{D} }[\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t+1}(x)))-\ell(y,\pi_{\ell}^{\mathsf{ BR}}(f_{i}^{t}(x)))]$ (13) $\displaystyle\leq$ $\displaystyle T_{i}\cdot\beta\sqrt{d}K.$ (14) $$

Finally, the halting condition implies that $\mu(E_{\ell,a_{1},a_{2}})<\eta$ for all $a_{1},a_{2}\in\mathcal{A}$.
∎

###### Proof.

## Appendix C 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 C.1 .

For any integer $m>0$, let $1/m$ denote the $m+1$ grid points,

$$ $\left[\frac{1}{m}\right]=\left\{0,\frac{1}{m},\frac{2}{m},\ldots,\frac{m-1}{m} ,1\right\}.$ $$

For any value $v\in[0,1]^{d}$, let $Round(v;m)=\mathrm{argmin}_{v^{\prime}\in[1/m]^{d}}\left\lVert v-v^{\prime}
\right\rVert_{2}$ denote the closest grid point to $v$ in $[1/m]^{d}$.

At each time-step in Algorithm 1 and Algorithm 2, denote $\widetilde{\phi}^{t}=Round(\phi;m)$, and we patch the predictors using $\widetilde{\phi}^{t}$ instead of $\phi^{t}$, i.e., we update $f^{t}$ to $f^{t+1}$ as

$$ $f^{t+1}(x)=\mathrm{proj}_{[0,1]^{d}}(f^{t}(x)+\widetilde{\phi}^{t}E^{t}(f^{t}( x),x)).$ $$

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 a finite number of time-steps. We denote the maximum number of time-steps, counting both Algorithm 1 and Algorithm 2, as $T_{\max}$.

Then, we can 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 of tuple, $\{(i^{t},E^{t},\Delta^{t})\}_{t\in[T]}$. Here, index $i^{t}\in\{1,2\}$, event $E^{t}\in\{E_{\ell,a_{1},a_{2}}:\ell\in\mathcal{L},a_{1},a_{2}\in\mathcal{A}\}
\cup\{E_{\ell,a}\cap E_{\ell^{\prime},a_{1},a_{2}}:\ell,\ell^{\prime}\in
\mathcal{L},a_{1},a_{2},a\in\mathcal{A}\}$, and $\Delta_{t}\in[1/m]^{d}$ are all chosen from a finite set, and the length of the sequence, $T$, is also bounded. Specifically, for a fixed input $f_{1},f_{2}$, we denote $S$ to be the set of all possible predictors outputted by Algorithm 2. Then, its size satisfies

$$ $\displaystyle|S|\leq(4|\mathcal{L}|^{2}K^{3}(m+1)^{d})^{T_{\max}+1}$ $$

We show that the number of predictors outputted by Algorithm 2 is bounded:

###### Lemma C.2 .

Fix any pair of predictors $f_{1},f_{2}:\mathcal{X}\rightarrow[0,1]^{d}$ and any $\eta,\alpha,\beta>0$. Then the total number of possible predictors outputted by Algorithm 2 is at most $\left\lvert S\right\rvert$ such that, for any distribution $\mathcal{D}$ on which Algorithm 2 is run, the output predictors $(f_{1}^{t},f_{2}^{t})\in S$.

###### Proof.

First, notice that a sequence of quantities $\{(i^{t},E^{t},\Delta^{t})\}_{t\in[T]}$ defines the pair of predictors outputted by Algorithm 2.

Let $S$ denote the pairs of functions induced by all such trajectories defined above. Here, $i^{t}\in\{1,2\},E^{t}\in\{E_{\ell,a_{1},a_{2}}:\ell\in\mathcal{L},a_{1},a_{2}
\in\mathcal{A}\}\cup\{E_{\ell,a}\cap E_{\ell^{\prime},a_{1},a_{2}}:\ell,\ell^{
\prime}\in\mathcal{L},a_{1},a_{2},a\in\mathcal{A}\}$, and $\Delta_{t}\in[1/m]^{d}$. Therefore, there are

$$ $\displaystyle|S|\leq\sum_{t=1}^{T}\left(2(|\mathcal{L}|K^{2}+|\mathcal{L}|^{2} K^{3})(m+1)^{d}\right)^{t}\leq(4|\mathcal{L}|^{2}K^{3}(m+1)^{d})^{T_{\max}+1}$ $$

output predictors.
∎

###### Definition C.1 .

###### Lemma C.2 .

###### Proof.

### C.1 Finite Grid

With this new patching operation, we can show that the Brier score decreases on the empirical distribution $D$, corresponding to Lemma B.2:

###### Lemma C.3 .

Fix any event $E$. Let $\phi=\mathbb{E}_{(x,y)\sim D}[y-f(x)|E(x)=1]$. For any predictor $f$, we patch $f$ as $f^{\prime}(x)=\mathrm{proj}_{\Delta}(f(x)+\tilde{\phi}E(x))$. Then,

$$ $B(f,D)-B(f^{\prime},D)\geq\|\phi\|_{2}^{2}\mu(E)-\frac{d}{4m^{2}}$ $$

###### Proof.

Let $\tilde{f}^{\prime}(x)=f(x)+\phi E(x)$. Then, we have

$$ $\displaystyle B(f,D)-B(f^{\prime},D)=$ $\displaystyle B(f,D)-B(\tilde{f}^{\prime},D)+B(\tilde{f}^{\prime},D)-B(f^{ \prime},D)$ $\displaystyle\geq$ $\displaystyle\|\phi\|_{2}^{2}\mu(E)+\mathbb{E}[\left\lVert f(x)+\phi E(x)-y \right\rVert_{2}^{2}-\left\lVert f(x)+\tilde{\phi}E(x)-y\right\rVert_{2}^{2}]$ ( Lemma B.2 ) $\displaystyle=$ $\displaystyle\|\phi\|_{2}^{2}\mu(E)-\mathbb{E}\left[\left\lVert\tilde{\phi}- \phi\right\rVert_{2}^{2}\right]\mu(E)$ $$

By definition $\tilde{\phi}$, we know that each index of $|\tilde{\phi}-\phi|$ is in $[0,\frac{1}{2m}]$. Therefore, we have

$$ $\displaystyle B(f,D)-B(f^{\prime},D)\geq$ $\displaystyle\|\phi\|_{2}^{2}\cdot\mu(E)-\frac{d}{4m^{2}}.$ $$

∎

Since the Brier score is within the range $[0,d]$, and it decreases at each iteration, we can show that, if we set $m$ large enough, Algorithm 2 terminates within a finite number of iterations:

###### Lemma C.4 .

For any predictor $f_{1},f_{2}$. Let $m\geq\left\lceil\sqrt{\frac{d}{2\min\{\beta^{2},\eta\alpha^{2}/4d\}}}\right\rceil$. The Brier score at each iteration of Algorithm 1 and Algorithm 2 satisfies

$$ $B(f^{t},D)-B(f^{t+1},D)>\frac{\min\{\beta^{2},\eta\alpha^{2}/(4d)\}}{2}.$ $$

Counting both Algorithm 2 and its subroutine Algorithm 1, the total number of iterations $T$ satisfies

$$ $\displaystyle T\leq\frac{2d}{\min\{\beta^{2},\eta\alpha^{2}/4d\}}.$ $$

###### Proof.

By Algorithm 1, we have by definition of $\beta$-decision calibration that

$$ $\displaystyle\mu(E^{t}\cap E_{\ell,a})\cdot\left\lVert\mathbb{E}_{(x,y)\sim D} [(y-f(x)|E^{t}(x)\cdot E_{\ell,a}(x)=1]\right\rVert_{2}^{2}$ (15) $\displaystyle\geq$ $\displaystyle\mu(E^{t}\cap E_{\ell,a})^{2}\cdot\left\lVert\mathbb{E}_{(x,y) \sim D}[(y-f(x)|E^{t}(x)\cdot E_{\ell,a}(x)=1]\right\rVert_{2}^{2}$ (16) $\displaystyle=$ $\displaystyle\left\lVert\mathbb{E}_{(x,y)\sim D}[(y-f(x)\cdot E^{t}(x)\cdot E_ {\ell,a}(x)]\right\rVert_{2}^{2}>\beta^{2}.$ (17) $$

In Algorithm 2, we have by Lemma B.1 that

$$ $\displaystyle\mu(E^{t})\left\lVert\mathbb{E}_{(x,y)\sim D}[(y-f(x)|E^{t}(x)=1] \right\rVert_{2}^{2}>\frac{\eta\alpha^{2}}{4d}.$ (18) $$

Therefore, for any $\phi$ and event $E$ that we patch in Algorithm 1 or Algorithm 2, they satisfy

$$ $\|\phi\|_{2}^{2}\cdot\mu(E)>\min\{\beta^{2},\frac{\eta\alpha^{2}}{4d}\}.$ $$

Letting $m\geq\left\lceil\sqrt{\frac{d}{2\min\{\beta^{2},\eta\alpha^{2}/4d\}}}\right\rceil$, we can ensure

$$ $\displaystyle B(f^{t},D)-B(f^{t+1},D)\geq$ $\displaystyle\frac{\|\phi\|_{2}^{2}\cdot\mu(E)}{2}>\frac{\min\{\beta^{2},\eta \alpha^{2}/(4d)\}}{2}.$ $$

Since the Brier score is in the range $[0,d]$, we can bound the total number of iterations of both Algorithm 1 and Algorithm 2 as

$$ $\displaystyle T\leq\frac{2d}{\min\{\beta^{2},\eta\alpha^{2}/4d\}}.$ $$

∎

###### Lemma C.3 .

###### Proof.

###### Lemma C.4 .

###### Proof.

### C.2 Proof of Theorem 3.4

First, we show that, for a fixed predictor $f$ and event $E_{\ell,a}$, the in-sample prediction error is approximately accurate. The deviation bound of the Brier score and calibration error can then be directly implied.

###### Lemma C.5 .

Fix any $f$, $E_{\ell,a}$, with probability at least $1-\delta^{\prime}$, we have

$$ $\displaystyle\left\lVert\mathbb{E}_{\mathcal{D}}[(y-f(x))E_{\ell,a}(f(x),x)]- \frac{1}{n}\sum_{i=1}^{n}[(y_{i}-f(x_{i}))E_{\ell,a}(f(x_{i}),x_{i})]\right \rVert_{2}\leq\sqrt{\frac{d\ln(2d/\delta^{\prime})}{2n}}.$ $$

###### Proof.

Fix an index $j\in[d]$,
we know $\mathbb{E}_{(x,y)\sim\mathcal{D}}[(y-f(x))_{j}\cdot E_{\ell,a}(f(x),x)]\in[0,1]$ and

$$ $\mathbb{E}_{D}\left[\frac{1}{n}\sum_{i=1}^{n}[(y_{i}-f(x_{i}))_{j}\cdot E_{ \ell,a}(f(x_{i}),x_{i})]\right]=\mathbb{E}_{(x,y)\sim\mathcal{D}}[(y-f(x))_{j} \cdot E_{\ell,a}(f(x),x)].$ $$

Since $(x_{i},y_{i})$ is drawn i.i.d. from $\mathcal{D}$, we can use Hoeffding’s inequality to get, with probability $\delta^{\prime}/d$,

$$ $\displaystyle\left|\mathbb{E}_{(x,y)\sim\mathcal{D}}[(y-f(x))_{j}\cdot E_{\ell ,a}(f(x),x)]-\frac{1}{n}\sum_{i=1}^{n}[(y_{i}-f(x_{i}))_{j}\cdot E_{\ell,a}(f( x_{i}),x_{i})]\right|\leq\sqrt{\frac{\ln(2d/\delta^{\prime})}{2n}}$ $$

Using union bound, we have that with probability $1-\delta^{\prime}$, the above inequality holds for all $j\in[d]$. Then, we have

$$ $\displaystyle\left\lVert\mathbb{E}_{(x,y)\sim\mathcal{D}}[(y-f(x))\cdot E_{ \ell,a}(f(x),x)]-\frac{1}{n}\sum_{i=1}^{n}[(y_{i}-f(x_{i}))\cdot E_{\ell,a}(f( x_{i}),x_{i})]\right\rVert_{2}$ $\displaystyle\leq$ $\displaystyle\sqrt{\sum_{j\in d}\left(\sqrt{\frac{\ln(2d/\delta^{\prime})}{2n} }\right)^{2}}=\sqrt{\frac{d\ln(2d/\delta^{\prime})}{2n}}.$ $$

∎

The deviation bound of the Brier score and calibration error can be directly implied by Lemma C.5. We summarize them in the lemmas below:

###### Lemma C.6 .

For a fixed $f$, with probability at least $1-\delta^{\prime}$, $|B(f,\mathcal{D})-B(f,D)|\leq\sqrt{\frac{d\ln(2d/\delta^{\prime})}{2n}}$.

###### Proof.

Using triangle inequality, we have

$$ $\displaystyle|B(f,\mathcal{D})-B(f,D)|=$ $\displaystyle\left|\left\lVert\mathbb{E}_{(x,y)\sim\mathcal{D}}[y-f(x)]\right \rVert_{2}-\left\lVert\frac{1}{n}\sum_{i=1}^{n}[y_{i}-f(x_{i})]\right\rVert_{2 }\right|$ $\displaystyle\leq$ $\displaystyle\left\lVert\mathbb{E}_{(x,y)\sim\mathcal{D}}[y-f(x)]-\frac{1}{n} \sum_{i=1}^{n}[y_{i}-f(x_{i})]\right\rVert_{2}$ $\displaystyle\leq$ $\displaystyle\sqrt{\frac{d\ln(2d/\delta^{\prime})}{2n}}.$ $$

∎

###### Lemma C.7 .

For a fixed $f$, any loss function $\ell\in\mathcal{L}$ and $\mathcal{E}=\{E_{\ell,a}\cap E_{\ell^{\prime},a_{1},a_{2}}:\ell,\ell^{\prime}
\in\mathcal{L},a,a_{1},a_{2}\in\mathcal{A}\}$, with probability $1-\delta^{\prime}$, we have

$$ $\displaystyle\left\lVert\mathbb{E}_{\mathcal{D}}[(y-f(x))E(x)]-\frac{1}{n}\sum _{i=1}^{n}[(y_{i}-f(x_{i}))E(x)]\right\rVert_{2}\leq\sqrt{\frac{3d\ln(2dK\left \lvert\mathcal{L}\right\rvert/\delta^{\prime})}{2n}}$ $$

for all $E\in\mathcal{E}$.

###### Proof.

The claim follows by using a union bound over the events in $\mathcal{E}^{t}$, using Lemma C.5, and that $|\mathcal{E}^{t}|=K^{3}\left\lvert\mathcal{L}\right\rvert^{2}$.
∎

For a fixed pair of predictors, we can also show that the empirical size of the disagreement events $E_{\ell,a_{1},a_{2}}$ is approximately correct with high probability:

###### Lemma C.8 .

Fix any pair of predictors $(f_{1},f_{2})\in S$, with probability at least $1-\delta^{\prime}$ over $D$, we have

$$ $\displaystyle\left|\mu(E_{\ell,a_{1},a_{2}})-\frac{1}{n}\sum_{i=1}^{n}\mathbb{ I}[E_{\ell,a_{1},a_{2}}(x_{i})=1]\right|\leq\sqrt{\frac{2\ln(2K\left\lvert \mathcal{L}\right\rvert/\delta^{\prime})}{2n}}.$ $$

for all $a_{1},a_{2}\in\mathcal{A}$ with $a_{1}\neq a_{2}$ and for all $\ell\in\mathcal{L}$.

###### Proof.

We know $\mathbb{I}[E_{\ell,a_{1},a_{2}}(x_{i})=1]\in[0,1]$ and

$$ $\mathbb{E}_{D}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}[E_{\ell,a_{1},a_{2}}(x _{i})\right]=\mu(E_{\ell,a_{1},a_{2}}).$ $$

Since $(x_{i},y_{i})$ is drawn i.i.d. from $\mathcal{D}$, we can use Hoeffding’s inequality to get, with probability $1-\delta^{\prime}/(K^{2}|\mathcal{L}|)$,

$$ $\displaystyle\left|\mu(E_{\ell,a_{1},a_{2}})-\frac{1}{n}\sum_{i=1}^{n}\mathbb{ I}[E_{\ell,a_{1},a_{2}}(x_{i})]\right|\leq\sqrt{\frac{2\ln(2K\left\lvert \mathcal{L}\right\rvert/\delta^{\prime})}{2n}}.$ $$

Using union bound over all pairs of $a_{1},a_{2}\in\mathcal{A}$ and $\ell\in\mathcal{L}$, we know the above inequality holds for all $a_{1},a_{2}$ and $\ell\in\mathcal{L}$ with probability at least $1-\delta^{\prime}$.
∎

We summarize the above results in the theorem below. Theorem 3.4 follows by solving for $n$ in the 2-4th guarantees below.

###### Theorem C.9 .

Fix any distribution $\mathcal{D}$ and dataset $D\sim\mathcal{D}$ containing $n$ samples drawn i.i.d from $\mathcal{D}$. For any pair of predictors $f_{1},f_{2}:\mathcal{X}\rightarrow[0,1]^{d}$, loss margin $\alpha>0$, disagreement region mass $\eta>0$, and decision-calibration tolerance $\beta>0$, Algorithm 2 run over the empirical distribution $D$ updates predictors $f_{1}$ and $f_{2}$ for $T_{1}$ and $T_{2}$ time-steps, respectively, and outputs a pair of predictors $(f_{1}^{T},f_{2}^{T})$ such that, with probability at least $1-\delta$ over the randomness of $D\sim\mathcal{D}^{n}$,

- 1.
The total number of time-steps for Algorithm 2 and Algorithm 1 is
$T=T_{1}+T_{2}\leq\frac{2d}{\min\{\beta^{2},\eta\alpha^{2}/4d\}}$
- 2.
For $i\in\{1,2\}$, the Brier scores of the final models are lower than that of the input models:
$\displaystyle B(f_{i}^{T_{i}},\mathcal{D})\leq B(f_{i},\mathcal{D})-T_{i}\cdot
\min\left\{\beta^{2},\eta\alpha^{2}/(4d)\right\}+\sqrt{(d\ln(6d|S|/\delta)/(2n)}$
- 3.
For $i\in\{1,2\}$, the downstream decision-making losses of the final models do not increase by much compared to that of the input models:
$\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi^{\mathsf{BR}}(f_{i}^
{T}(x))-\ell(y,\pi^{\mathsf{BR}}(f_{i}(x))]\leq\left(\beta+\sqrt{(3d\ln(6dK|S|
\left\lvert\mathcal{L}\right\rvert/\delta)/(2n)}\right)\sqrt{d}KT_{i}$
- 4.
The final models approximately agree on their best-response actions almost everywhere. That is, the disagreement region $E_{a_{1},a_{2}}$ calculated using $f_{1}^{T},f_{2}^{T}$ has small mass.
$\mu(E_{\ell,a_{1},a_{2}})\leq\eta+\sqrt{(2\ln(6K|S|\left\lvert\mathcal{L}
\right\rvert/\delta)/(2n)}\quad\text{ for all }a_{1},a_{2}\in\mathcal{A}\quad
\text{s.t }a_{1}\neq a_{2}$

Here, $S$ is the set of all possible predictors outputted by Algorithm 2 satisfying

$$ $\displaystyle\ln(|S|)\leq\left(\frac{2d}{\min\{\beta^{2},\eta\alpha^{2}/4d\}}+ 1\right)\ln\left(4|\mathcal{L}|^{2}K^{3}\left(\left\lceil\sqrt{\frac{d}{2\min \{\beta^{2},\eta\alpha^{2}/4d\}}}\right\rceil+1\right)^{d}\right)$ $$

###### Proof.

The upper bound on $T$ holds true with probability $1$. For the remaining three guarantees, we show that each of them holds with probability at least $1-\delta/3$ over the randomness of $D$.

Brier Score. First, by Lemma C.6 and using union bound over all possible output predictors $(f_{1},f_{2})\in S$, we have with probability at least $1-\delta/3$ that

$$ $\displaystyle|B(f_{i},\mathcal{D})-B(f_{i},D)|\leq\sqrt{\frac{d\ln(6d|S|/ \delta)}{2n}}.$ $$

By Lemma C.4, and summing over all iterations, we have

$$ $\displaystyle B(f_{i}^{T_{i}},D)\leq B(f_{i},D)-T_{i}\cdot\min\left\{\frac{ \beta^{2}}{2},\frac{\eta\alpha^{2}}{8d}.\right\}$ $$

Therefore,

$$ $\displaystyle B(f_{i}^{T_{i}},\mathcal{D})\leq$ $\displaystyle B(f_{i}^{T_{i}},D)+\sqrt{\frac{d\ln(6d|S|/\delta)}{2n}}$ $\displaystyle\leq$ $\displaystyle B(f_{i},\mathcal{D})-T_{i}\cdot\min\left\{\frac{\beta^{2}}{2}, \frac{\eta\alpha^{2}}{8d}\right\}+\sqrt{\frac{d\ln(6d|S|/\delta)}{2n}}$ $$

for $i\in\{1,2\}$.

Expected Loss.
Using union bound over all predictors in $S$, by Lemma C.7, we have, with probability at least $1-\delta/3$,

$$ $\displaystyle\left\lVert\mathbb{E}_{\mathcal{D}}[(y-f(x))E_{\ell,a}(f(x),x)]- \frac{1}{n}\sum_{i=1}^{n}[(y_{i}-f(x_{i}))E_{\ell,a}(f(x_{i}),x_{i})]\right \rVert_{2}\leq\sqrt{\frac{3d\ln(6dK|S|\left\lvert\mathcal{L}\right\rvert/ \delta)}{2n}}$ $$

for all predictors $f$, action $a\in\mathcal{A}$ and loss $\ell\in\mathcal{L}$.
Using similar method as in Lemma 2.6, we define the set $\Delta_{a}^{t}\subseteq E^{t}$ as

$$ $\displaystyle\Delta_{a}^{t}=\{x\in E^{t}:\pi_{\ell}^{\mathsf{BR}}(f^{t+1}_{i}( x))=a\}.$ $$

Then, we have

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}} (f_{i}^{t+1}(x)))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t}(x)))]$ $\displaystyle=$ $\displaystyle\sum_{a\in\mathcal{A}}\mathbb{E}_{(x,y)\sim\mathcal{D}}[(\ell(y,a )-\ell(y,a_{i}^{t}))\Delta_{a}^{t}(x)].$ $$

For each term in the summation,

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[(\ell(y,a)-\ell(y,a_{i}^{t})) \Delta_{a}^{t}(x)]$ (19) $\displaystyle=$ $\displaystyle\langle\mathbb{E}_{(x,y)\sim\mathcal{D}}[y\Delta_{a}^{t}(x)],\ell _{a}-\ell_{a_{i}^{t}}\rangle$ (Linearity of Expectation) $\displaystyle\leq$ $\displaystyle\langle\mathbb{E}_{x\sim\mathcal{D}_{\mathcal{X}}}[f_{i}^{t+1}(x) \Delta_{a}^{t}(x)],\ell_{a}-\ell_{a_{i}^{t}}\rangle+\left(\beta+\sqrt{\frac{3d \ln(6dK|S|\left\lvert\mathcal{L}\right\rvert/\delta)}{2n}}\right)\sqrt{d}$ ( Lemma C.7 and $\beta$ -calibrated) $\displaystyle\leq$ $\displaystyle\left(\beta+\sqrt{\frac{3d\ln(6dK|S|\left\lvert\mathcal{L}\right \rvert/\delta)}{2n}}\right)\sqrt{d}.$ (Since $a$ is the new Best-response action) $$

Summing these actions together, we have

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi_{\ell}^{\mathsf{BR}} (f_{i}^{t+1}(x)))-\ell(y,\pi_{\ell}^{\mathsf{BR}}(f_{i}^{t}(x)))]\leq\beta \sqrt{d}K+\sqrt{\frac{3\ln(6dK|S|\left\lvert\mathcal{L}\right\rvert/\delta)}{2 n}}dK.$ (20) $$

Summing over all iterations, we conclude that, with probability at least $1-\delta/3$,

$$ $\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(y,\pi^{\mathsf{BR}}(f_{i}^ {T_{i}}(x)))-\ell(y,\pi^{\mathsf{BR}}(f_{i}(x)))]\leq T_{i}(\beta\sqrt{d}K+ \sqrt{\frac{3\ln(6dK|S|\left\lvert\mathcal{L}\right\rvert/\delta)}{2n}}dK)$ $$

for all $i\in\{1,2\}$.

Disagreement Event.
By Lemma C.8, with probability at least $1-\delta/(3|S|)$, we have, for all $\ell\in\mathcal{L}$, $a_{1},a_{2}\in\mathcal{A}$ with $a_{1}\neq a_{2}$ and all $(f_{1},f_{2})\in S$,

$$ $\displaystyle\left|\mu(E_{\ell,a_{1},a_{2}}(f_{1}(x),f_{2}(x),x)-\frac{1}{n} \sum_{i=1}^{n}\mathbb{I}[E_{\ell,a_{1},a_{2}}(f_{1}(x_{i}),f_{2}(x_{i}),x_{i}) )]\right|\leq\sqrt{\frac{2\ln(6K|S|\left\lvert\mathcal{L}\right\rvert/\delta)} {2n}}.$ $$

From the while loop condition in Algorithm 2, we know that

$$ $\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}[E_{\ell,a_{1},a_{2}}(f_{1}^{T_{1}}(x_{i}), f_{2}^{T_{2}}(x_{i}),x_{i})]\leq\eta$ $$

Then, using union bound over all $(f_{1},f_{2})\in S$ and $\ell\in\mathcal{L}$, with probability at least $1-\delta/3$, we have the guarantee

$$ $\displaystyle\mu(E_{\ell,a_{1},a_{2}}(f_{1}^{T_{1}}(x),f_{2}^{T_{2}}(x),x))\leq$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}[E_{\ell,a_{1},a_{2}}(f_{1}^{T _{1}}(x_{i}),f_{2}^{T_{2}}(x_{i}),x_{i})]+\sqrt{\frac{2\ln(6K|S|\left\lvert \mathcal{L}\right\rvert/\delta)}{2n}}$ (21) $\displaystyle\leq$ $\displaystyle\eta+\sqrt{\frac{2\ln(6K|S|\left\lvert\mathcal{L}\right\rvert/ \delta)}{2n}}$ (22) $$

for all $a_{1},a_{2}\in\mathcal{A},a_{1}\neq a_{2}$ and $\ell\in\mathcal{L}$.

Finally, using results from Lemma C.2, value of $T_{\max}$, and $m=\left\lceil\sqrt{\frac{d}{2\min\{\beta^{2},\eta\alpha^{2}/4d\}}}\right\rceil$, we conclude by showing

$$ $\displaystyle\ln(|S|)\leq$ $\displaystyle\ln\left((4|\mathcal{L}|^{2}K^{3}(m+1)^{d})^{T_{\max}+1}\right)$ $\displaystyle=$ $\displaystyle(T_{\max}+1)\ln(4|\mathcal{L}|^{2}K^{3}(m+1)^{d})$ $\displaystyle=$ $\displaystyle\left(\frac{2d}{\min\{\beta^{2},\eta\alpha^{2}/4d\}}+1\right)\ln \left(4|\mathcal{L}|^{2}K^{3}\left(\left\lceil\sqrt{\frac{d}{2\min\{\beta^{2}, \eta\alpha^{2}/4d\}}}\right\rceil+1\right)^{d}\right)$ $$

∎

###### Lemma C.5 .

###### Proof.

###### Lemma C.6 .

###### Proof.

###### Lemma C.7 .

###### Proof.

###### Lemma C.8 .

###### Proof.

###### Theorem C.9 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: - W.r.t. the finite sample analysis, is the proposed algorithm robust towards any noise in the samples?
soundness: 3
strengths: - This paper studied an important and practical problem of model multiplicity. The paper overall is well-organized and presented with a good clarity. 
- 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.
- 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.
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.
The 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.
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.
- 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?

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
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?
2. 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?
3. 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?
soundness: 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.
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. 



-----
[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.
weaknesses: The paper has weaknesses in its presentation as well as results that seem somewhat suspicious/hard to interpret precisely.

The following items could be addressed and improved for presentation:
- 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. 
- 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.
- 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.
- 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. 
- 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.
- Is the notation $\ell_a$ necessary? If so how do you obtain $\ell_a$ given $\ell$?
- 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? 

The following items can be addressed to help improve the results of the paper:

**Questions related to Theorem 3.4**
- In Theorem 3.4, does item 1. have a typo? 
- Define $A$ the number of actions in the theorem statement for part 3. since it is off-handedly defined somewhere else in the paper. 
- 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.
- 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$?

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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). 

In 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.
soundness: 3
strengths: This paper is overall a good and novel contribution to the predictive multiplicity literature. Specifically:

+ 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. 

+ 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".
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.
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:

- 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.

Neither 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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Please see my questions above. Additionally: 

1) How does the framework perform across different domains or datasets that exhibit varying levels of complexity and noise?
2) As mentioned, determining optimal ranges and conditions for key hyperparameters parameters across varying contexts can be challenging. 
3) 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?
soundness: 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.
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.
weaknesses: Comments/Questions to Authors: 
•	The 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. 

•	The 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.

•	The 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. 

•	Additional 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.  

“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. 

“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. 

“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.

“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.

“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.

Also 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.

Meta-review: This a paper which just sits above the borderline area. The paper studies the problem of model multiplicity in downstream decision-making.
All reviews have been cautiously positive with various suggestions for improving and strengthening the paper. In particular, the paper studies an important problem and provides some theoretical guarantees. I believe the paper is good enough for publication but the authors should incorporate the improvements suggested by the reviewers.

Decision: Accept (Poster)