# Human-Algorithm Collaboration: Achieving Complementarity and Avoiding
Unfairness

Kate Donahue<EMAIL_ADDRESS>done during internship at Amazon.
Department of Computer Science, Cornell University  Alexandra Chouldechova
Carnegie Mellon University and Amazon Web Services  Krishnaram Kenthapadi Work
done while at Amazon. Fiddler AI

###### Abstract

Much of machine learning research focuses on predictive accuracy: given a
task, create a machine learning model (or algorithm) that maximizes accuracy.
In many settings, however, the final prediction or decision of a system is
under the control of a human, who uses an algorithm’s output along with their
own personal expertise in order to produce a combined prediction. One ultimate
goal of such collaborative systems is complementarity: that is, to produce
lower loss (equivalently, greater payoff or utility) than either the human or
algorithm alone. However, experimental results have shown that even in
carefully-designed systems, complementary performance can be elusive. Our work
provides three key contributions. First, we provide a theoretical framework
for modeling simple human-algorithm systems and demonstrate that multiple
prior analyses can be expressed within it. Next, we use this model to prove
conditions where complementarity is impossible, and give constructive examples
of where complementarity is achievable. Finally, we discuss the implications
of our findings, especially with respect to the fairness of a classifier. In
sum, these results deepen our understanding of key factors influencing the
combined performance of human-algorithm systems, giving insight into how
algorithmic tools can best be designed for collaborative environments.

##  1 Introduction

(a) Scenario 1: Combined system has higher loss than either unaided human or
algorithm.

(b) Scenario 2: Combined system has lower loss than unaided human, but higher
loss than algorithm.

(c) Scenario 3: Complementary performance: lower error than either unaided
human or algorithm.

Figure 1: Three possible scenarios for human-algorithm collaboration, each
with the same algorithmic and unaided human loss. However, the loss of the
combined system (human using the algorithm) might vary substantially. Section
4 gives a more detailed analysis.

Consider a prediction task where the goal is to take a set of features about
the world as input and predict an outcome of interest. A typical machine
learning approach to such a task is to attempt to select a model with low
(generalization) loss for the problem at hand. If such a model is applied
directly to the prediction task, it will minimize expected loss.

However, this standard approach does not necessarily reflect the way that
machine learning tools are actually implemented. Often, algorithmic
predictions are presented to humans, who then make a final decision by
additionally relying on their own expertise [35, 1, 17, 38]. For example,
consider a doctor looking at a medical record and trying to make a
determination of whether disease is present. An algorithmic prediction based
on the record may be useful, but it almost certainly will not be the sole
factor influencing the doctor’s diagnosis. For example, the doctor may have
access to different data, such as conversations with the patient. The doctor
may also have access to different knowledge, such as distilled expertise from
years of practice. The doctor’s decision will be a function of the algorithm’s
prediction, as well as their own inherent belief. Note that the doctor’s
decision-making may be imperfect, such as relying on their own judgement when
the algorithm may have better performance. A successful outcome occurs when
the combined system (the doctor using algorithmic output) has low loss, not
when the algorithm alone has low loss. Figure 1 illustrates three scenarios
where a combined human-algorithm system could have differing levels of loss.

In particular, one especially valuable goal is _complementarity_ (or
_complementary performance_). Complementarity (originally defined in Bansal et
al. [2]) is achieved whenever the combined human-algorithm system has strictly
lower expected loss than either the human or the algorithm alone (Figure 1).
Complementarity is not necessary for a combined system to be deemed
successful: for example, a combined system that does better than the human
alone, but not necessarily better than the algorithm alone, would still
reflect an improvement from a human-alone status-quo. However, complementarity
creates the strongest incentive for adoption of a combined human-algorithm
system, which is why it is the focus of our analysis.

Contributions: At a high level, we address the following problems: _(i) How do
we formally and tractably model human-algorithm collaborative systems? (ii)
When can human-algorithm collaborative systems produce higher accuracy than
either the human or algorithm alone? (iii) What are the fairness implications
of such collaborative systems?_

The contributions of this work are three-fold. First, in Section 3, we
introduce a simple theoretical framework for analyzing human-algorithm
collaboration, and demonstrate the richness of this framework by showing that
it can encapsulate models from previous works analyzing human decision-making.
In Section 4, we provide a simple, concrete motivating example using this
framework that illustrates the core results of this paper.

Next, in Section 5, we use this approach to analyze complementarity. First, we
present several impossibility results that characterize regimes in which
human-algorithm collaboration can never achieve complementarity. We then give
concrete conditions for when complementarity can be achieved. In particular,
our results suggest that complementarity is easier to achieve when loss rates
are highly variable: when the unaided human (or algorithm) has very low loss
on some inputs and very high loss on inputs. Disparate levels of loss raises
issues of fairness, which we turn to next.

In Section 6 we conclude our analysis by examining the fairness impacts of
complementarity. The variability in loss rates implied by our results has
implications for fairness, since types of inputs with very high error rates
may correspond to protected attributes, such as race, gender, or ethnicity. To
investigate this concern, we propose and analyze three types of fairness
relating to human-algorithm systems, giving conditions for when they can and
cannot be achieved. One of main results shows that when complementarity is
achieved, at least one group does worse in the combined system than under the
human-only status quo. Additionally, we give a simple condition where the
combined human-algorithm system will guarantee that loss disparity between
different protected groups will not increase.

##  2 Related Work

###  2.1 Human-Algorithm Collaboration

A series of papers have explored issues related to human-algorithm
collaboration. For example, Poursabzi-Sangdeh et al. [28] and Yin et al. [38]
analyze how explainability and accuracy, respectively, influence how humans
use algorithmic predictions. Similarly, Dietvorst and Bharti [8] hypothesize
that humans may prefer algorithmic predictions that are more variable in their
loss rates and Dietvorst et al. [9] suggests that allowing algorithmic
predictions to be modified may make humans more likely to use them.

Other papers center more on in-depth qualitative assessments of how
professionals incorporate tailor-made algorithmic tools into their workflow.
For example, Lebovitz et al. [22, 21] studies how doctors in major US
hospitals use AI predictions in their daily work. Similarly, Okolo et al. [27]
studies how community healthcare workers in India believe AI tools could
influence their work. Finally, Yang et al. [37] studies how UX designers work
with machine learning tools and the data scientists who create them.

Some research teams that develop tools for human-in-the-loop settings have run
experiments analyzing how their tools perform with human collaboration. For
example, Raghu et al. [29], Beede et al. [3] both study how an AI tool for
predicting diabetic retinopathy fits in with a broader ecosystem (human
doctors and the overall healthcare system). Similarly, De-Arteaga et al. [6]
studies how child welfare call screeners incorporate algorithmic predictions
in their risk assessments. Tan et al. [33] studies how human and algorithmic
distributions of loss rates differ for recividism predictions for the COMPAS
dataset (but not in ways that allowed for complementary performance by
combined systems). Similarly, Geirhos et al. [13] compares the similarity
(consistency) of loss in predictions made by humans and a deep learning
algorithm.

Some computer science papers specifically analyze models of human-algorithm
interaction, such as [4, 30, 31, 1, 17, 35]. Of these, Bansal et al. [2] is
especially relevant because it is framed through the goal of complementarity.
Bansal et al. [1] also highlights the fact that the optimizing for the
algorithm’s error may not minimize the loss of the combined system. In Section
3, we show how human decision-making processes rules inspired by analyses
Bansal et al. [1] and Vodrahalli et al. [35] can be represented in our model.
Some papers show how to build models optimized for a human-algorithm
_deferral_ system, where the final decision is made by either the human or the
algorithm [5, 26, 25]. Straitouri et al. [32] studies a variant of this
problem for classification where the algorithm presents a subset of possible
labels to the human, who selects the final decision from among them.

###  2.2 Fairness in Human-Algorithm Collaboration

Some papers specifically consider the fairness implications of combined human-
algorithm systems. For example, Madras et al. [23] studies fairness and
accuracy in deferring to a human expert, while Keswani et al. [18, 19] extends
this analysis to deferring to multiple different human experts. For example,
Gillis et al. [14] takes a theoretical approach towards modeling the human-
algorithm system and gives conditions where adding a biased (unfair) human can
change the fairness properties of the overall system. Valera et al. [34]
studies a system with multiple biased “experts”, where assigning the correct
expert to each task can improve accuracy while still satisfying fairness
requirements.

###  2.3 Related Papers From Other Areas

Finally, some papers in seemingly unrelated areas end up being relevant to our
analysis. For example, ensemble learning studies how to incorporate
predictions from multiple algorithms into a unified (more accurate) system
[20]. Ensemble learning differs from our analysis in that each expert
(predictor) is assumed to be an algorithm, and predictions are assumed to be
combined by some additional algorithm under our control (rather than a human
decision-maker we cannot control). However, certain factors identified in the
ensemble learning literature as affecting overall performance, such as
diversity, are relevant for our analysis [7]. Additionally, multiple works
study how fairness properties of predictors change when they are composed [10,
11, 36]. These works are relevant to our analysis in Section 6 of the fairness
of a combined human-algorithm system, but differ somewhat from ours: in
general, these other papers tend to study fairness of allocating or achieving
some desired prediction, while our analysis describes fairness as equal loss
across groups. Finally, Meehl [24] compares statistical and clinical methods
of reasoning, a framing that parallels to our analysis of algorithmic versus
human prediction methods.

##  3 Model and Assumptions

###  3.1 Model

Our model considers a prediction task: given some element $x\in\mathcal{X}$,
make a prediction $y\in\mathcal{Y}$ that minimizes some loss function
$\mathcal{L}$, with loss bounded $\geq 0$. This loss could reflect any error
rates for any type of learning problem—for example, regression and
classification tasks could both be represented by this loss function. We model
the input space $\mathcal{X}$ as being made up of $N$ discrete regimes: all
inputs within the same regime are identical from the perspective of
algorithmic and human loss. Note that this is without loss of generality,
given that $N$ could be arbitrarily large. We will denote the probability of
seeing regime $i$ is given by $p_{i}$, with $\sum_{i=1}^{N}p_{i}=1$.

The human-algorithm system consists of three components:

  1. 1.

An _algorithm_ , which for each regime in the input space
$x_{i}\in\mathcal{X}$ makes a prediction $\hat{y}_{i}^{a}$ with some loss rate
$a_{i}$. The average loss is given by $\sum_{i=1}^{N}p_{i}\cdot a_{i}=A$. We
can write $a_{i}=A+\delta_{ai}$, with $\sum_{i=1}^{N}p_{i}\cdot\delta_{ai}=0$.
The term $\delta_{ai}$ represents how much $a_{i}$ varies (differs from the
average loss $A$).

  2. 2.

A _unaided human_ , which similarly for each regime in the input space
$x_{i}\in\mathcal{X}$ makes some prediction $\hat{y}_{i}^{h}$. The average
loss of the human is given by $\sum_{i=1}^{N}p_{i}\cdot h_{i}=H$. Similarly,
we write write $h_{i}=H+\delta_{hi}$, with
$\sum_{i=1}^{N}p_{i}\cdot\delta_{hi}=0$.

  3. 3.

Finally, some _combiner_ (a human using algorithmic input)
$g(\hat{y}_{i}^{a},\hat{y}_{i}^{h})$, which takes predictions given by the
algorithm and unaided human and returns a combined prediction,
$\hat{y}_{i}^{c}$. The combining function reflects human decision-making: it
could select the algorithm’s prediction, the unaided human’s prediction, or
interpolate between the two of them. We could also view this as a (loss)
_combining function_ $c(a_{i},h_{i})$ that takes the algorithmic loss and
human loss on a particular instance and returns some combined loss.

In general, we may not have control over all (or even any) of these
components. For example, the combining function reflects human judgement,
which typically can’t be directly manipulated. A primary goal of our analyses
is to determine when a human-algorithm system displays complementarity,
defined in Definition 1 below.

######  Definition 1 (From Bansal et al. [2]).

A human-algorithm system displays complementary performance when the combined
system has (strictly) lower loss than either the human or algorithm:

$\sum_{i=1}^{N}p_{i}\cdot c(a_{i},h_{i})<\min\left(\sum_{i=1}^{N}p_{i}\cdot
a_{i},\sum_{i=1}^{N}p_{i}\cdot h_{i}\right)=\min(A,H)$

###  3.2 Assumptions

The combining function models the key question in human-algorithm
collaboration: how do humans incorporate algorithmic predictions with their
own expertise? In this work, we will make two main assumptions about how such
combination occurs. First, throughout this paper, we will find it useful to
work in the space of combining _losses_ , rather than combining predictions.
Specifically, we will use the $c(a_{i},h_{i})$ loss combining function.
Assumption 1 describes the assumption this implies.

######  Assumption 1.

The loss of a combined human-algorithm system can be modeled by a combining
rule relying only on the loss rates of the unaided human and algorithm in a
particular regime: $c(a_{i},h_{i})$. That is, regimes with identical (unaided
human, algorithm) pairs of loss rates are treated identically.

This assumption reflects the case where the level of accuracy in the algorithm
and (unaided) human is the only feature influencing the accuracy of the
combined system. An example of a situation that might _violate_ this
assumption is if regime 1 and 2 both have loss of 3% for the unaided human and
5% for the algorithm, but the human using the algorithm (combined system) has
loss of 3% for regime 1 and 4% for regime 2. Considering the case where this
assumption is relaxed could be an interesting avenue for future work: however,
it would likely result in much more complicated analysis.

Next, Assumption 2 below, describes the assumption that the combining rule’s
outputs are bounded.

######  Assumption 2.

For each regime, the loss of the combined system is bounded between the loss
of the human and algorithm:

$\min(a_{i},h_{i})\leq c(a_{i},h_{i})\leq\max(a_{i},h_{i})$

This assumption reflects a case where the combiner operates by interpolating
between the predictions made by the human or algorithm. An example of a
situation that might _violate_ this assumption is if the combined system has
loss 3% in a certain regime, where the human has loss 4% and the algorithm has
loss 6% in that regime. A bounded combining rule makes modeling human-
algorithm collaboration more realistic: complementarity is trivial to achieve
if the combining rule’s loss can be arbitrarily disconnected from the loss of
the human and algorithm.

It’s worth considering why a system may satisfy bounded inputs (Assumption 2)
and still exhibit complementarity. Assumption 2 refers to bounds at the level
of each _regime_ , while complementarity refers to _overall average loss_. For
example, Scenario 3 (Table 4) in Section 4 obeys the bound in Assumption 2,
and yet also achieves complementarity.

###  3.3 Weighting function

In this work, we will find it helpful to think about the combined human-
algorithm system as involving a _weighting function_ $0\leq
w_{h}(a_{i},h_{i})\leq 1$ controlling how much the human influences the final
prediction:

$c(a_{i},h_{i})=(1-w_{h}(a_{i},h_{i}))\cdot a_{i}+w_{h}(a_{i},h_{i})\cdot
h_{i}$ (1)

Lemma 1, below, shows that using a weighting function requires no new
assumptions.

######  Lemma 1.

Any combining rule relying only on loss rates (Assumption 1) with bounded
output (Assumption 2) can be written as a combining rule with a weighting
function $0\leq w_{h}(a_{i},h_{i})\leq 1$.

One simple (ideal) combining function is given by Example 1: it simply selects
whichever of the unaided human or algorithm has lower loss. While this is the
best possible combining function (given our assumptions), it is likely not a
realistic model of how human decision-makers incorporate algorithmic advice.

######  Example 1 (Min).

The combining function becomes $c(a,h)=\min(a,h)$ is represented by the
weighting function:

$w_{h}(a,h)=\begin{cases}1&h\leq a\\\ 0&\text{otherwise}\end{cases}$

While our framework is simple, it is also sufficiently flexible to capture
models of human-algorithm collaboration studied in multiple previous papers
(described in greater detail in Appendix A). Examples 2 and 3 demonstrate this
in reference two particular models suggested by prior literature. First,
Example 2 selects whichever of the human or algorithm has lower loss rate with
probability $p_{s}$. For high $p_{s}$, this reflects a decision-maker who
accurately trusts whichever has lower loss.

######  Example 2 (Bansal et al. [1]).

The analysis in Bansal et al. [1] suggests the weighting function:

$w_{h}(a,h)=\begin{cases}p_{s}&h\leq a\\\ 1-p_{s}&\text{otherwise}\end{cases}$

Next, in Example 3, the decision-maker first decides whether to consider
algorithmic advice at all: it does so only if the loss rate is $\epsilon$
lower than the human loss rate. Then, the decision-maker incorporates
algorithmic advice with some probability $p_{s}(\cdot)$ that is a function
depending on the gap between human and algorithmic loss rates.

######  Example 3 (Vodrahalli et al. [35]).

The two-stage model in Vodrahalli et al. [35] could be written as:

$w_{h}(a,h)=\begin{cases}1&a\geq h-\epsilon\\\
p_{s}(h-a)&\text{otherwise}\end{cases}$

###  3.4 Research Ethics and Social Impact

While our paper is primarily theoretical, its application area prompts a
number of ethical considerations. For example, in this work, we are primarily
concerned with building better prediction functions. In general, such
functions could be used for positive means (helping a doctor correctly
diagnose a disease) or negative ones (enabling the identification and
repression of minority groups). Additionally, even if a function is being used
for positive goals, it could be the case that factors besides the loss rate
are ultimately more important. For example, it could be that the process of
coming to a prediction, rather than the prediction itself, is more important.
This is especially salient for our discussion of fairness, which assumes that
the fairness of outcomes (of loss rate disparities) is the relevant factor to
consider, rather than fairness of the prediction process. The issue of
explanation of algorithmic predictions, which is orthogonal to our main
analysis, could be relevant for this consideration.

##  4 Motivating example

| (Unaided) human | Algorithm |  | Combined
---
(human using algorithm)
| Weight
---
(on unaided human)
Regime 1 | 1 | 0.35 | 0.94 | 0.9
Regime 2 | 0.5 | 0.65 | 0.64 | 0.1
Average | 0.75 | 0.5 | 0.79 | 0.5
Table 1: Scenario 1 Loss rates: An example of a combined human-algorithm
system. There are two regimes, each making up equal proportions of the input
space ($p_{0}=p_{1}=0.5$). Note here that complementarity is _not_ satisfied:
in fact, the combined system has higher loss than either the human or
algorithm alone!

| (Unaided) human | Algorithm |  | Combined
---
(human using algorithm)
| Weight
---
(on unaided human)
Regime 1 | 1 | 0.35 | 0.51 | 0.25
Regime 2 | 0.5 | 0.65 | 0.54 | 0.75
Average | 0.75 | 0.5 | 0.53 | 0.5
Table 2: Scenario 2 Loss rates: A second example of a combined human-algorithm
system, but with different loss distributions. Here, the combined system
(human using algorithm) has average loss which is lower than the loss of the
unaided human, but higher than the loss of the algorithm alone.

| (Unaided) human | Algorithm |  | Combined
---
(human using algorithm)
| Weight
---
(on unaided human)
Regime 1 | 1.15 | 0.2 | 0.44 | 0.25
Regime 2 | 0.35 | 0.8 | 0.46 | 0.75
Average | 0.75 | 0.5 | 0.45 | 0.5
Table 3: Scenario 3 Loss rates: A third example of a combined human-algorithm
system. Here, the combined system (human using algorithm) displays
_complementary performance_ : its average loss of 0.45 is lower than the loss
of either the unaided human (0.75) or algorithm alone (0.5).

Table 4: Three possible scenarios for human-algorithm collaboration. In each,
the algorithm and unaided human have the same average loss. However, the loss
of the human using the algorithm varies. Figure 1 gives a visual description
of these scenarios.

To further motivate the analysis, let us revisit the medical application from
in the introduction (Figure 1) and introduce further specifics111Code for all
examples and figures in this paper are available at
https://github.com/kpdonahue/human_algorithm_collaboration. Consider the
medical prediction task of using information from a patient’s medical record
to predict disease severity (on a scale from 0 to 5, as in [29]). As
illustrated in Figure 1, we will assume that doctors relying on their medical
training (unaided humans) have an average loss rate of 0.75: they are off by
0.75 grades, on average. A data science team has created a machine learning
algorithm that has average loss of 0.5.

Even though the algorithm has lower loss, doctors won’t simply rubber-stamp
algorithmic suggestions. Because they have specialized training and access to
additional information (such as conversations with patients), a doctor might
reasonably incorporate algorithm advice only partially, or only sometimes.
However, this leaves open a crucial question: what is the combined human-
algorithm loss? That is, what is the average loss once doctors start
incorporating the new machine-learning algorithm into their decision-making
process?

###  4.1 Three scenarios

To help build intuition before delving into our formal theoretical results, we
will consider three different example scenarios for how a human-algorithm
collaborative system might look like, given in Tables 4, 4, 4. Each scenario
has the same average loss for the unaided human and for the algorithm (0.75
and 0.5, respectively). However, each scenario differs in 1) the way (unaided)
human and algorithm loss is distributed and 2) the way the human combines
algorithmic advice. Specifically, these three scenarios illustrate the
simplified case where patient records (“regimes”) come in one of two types:
regime 1 and regime 2, each of which makes up 50% of the total input space.
These regimes might differ in multiple ways: say disease progression, data
quality, or patient characteristics. We will treat observations from within
the same regime as identical: the doctor or algorithm or combined system each
has uniform loss for every record within the same regime. (In later sections,
we will relax this consider arbitrary numbers of regimes, reflecting
arbitrarily complex distributions of loss).

Scenario 1 (combined loss higher than unaided human or algorithm): For
example, in Table 4, the unaided human has loss 1 on instances of type 1, but
loss 0.5 for instances of type 2. The algorithm’s loss rate distribution
differs: 0.35 for type 1, and 0.65 for type 2. Finally, the combined loss
(loss of the human using algorithmic input) for a particular regime is a
function of the loss of the unaided human and the algorithm: for this example,
it’s 0.94 in regime 1, and 0.64 in regime 2. Note that this results in an
average loss of 0.79—the human using the algorithm has a strictly _greater_
loss rate than either the unaided human or the algorithm! This unfortunate
case could result from inappropriately relying on the algorithm: for example,
the doctor might mistakenly incorporate algorithmic advice more frequently in
regimes where it happens to have higher loss. The fourth column concretely
reflects this cause: it calculates the weighting function for each regime
(reliance on the unaided human, as opposed to the algorithm). In this case,
the regime 1 weighting function is 0.9, meaning the combined system is relying
heavily on the unaided human for this instance, even though it has higher loss
than the algorithm. Similarly, in regime 2, the weighting function is 0.1,
indicating that the combined system is relying more on the algorithm, even
though (for this regime), the algorithm has higher loss than the human. This
inappropriate reliance explains why the combined system has higher loss than
either the unaided human or algorithm alone.

Scenario 2 (combined system lower error than human, higher error than
algorithm): Table 4 presents a slightly more optimistic Scenario 2. Here, _the
distribution of loss rates for the unaided human and the algorithm are the
same as in Scenario 1, but the combined loss differs_ : the average loss of
the human using the algorithm is 0.53—lower than the loss of the unaided human
(0.75), but higher than the loss of the algorithm alone (0.5). This reflects a
common scenario in human-algorithm collaboration: the combined system ends up
improving over the human alone, but still falls short of the loss rate
achievable by the algorithm alone [2]. In this case, the reason is because
_the combined system is doing a better job than in Scenario 1 of appropriately
relying on the unaided human or algorithm_. Note that the weighting function
is lower in regime 1 (when the unaided human has higher loss) and higher in
regime 2 (where the unaided human has lower loss). This more appropriate
reliance explains why the combined system has better performance than Scenario
1.

Scenario 3 (complementarity: lower than unaided human or algorithm): Finally,
Table 4 presents Scenario 3. In this case, _we keep the weighting function the
same as in Scenario 2_ , as well as the average loss of the unaided human and
the algorithm. However, _we change the distribution of loss rates across the
regimes: we make them more variable_. For example, the unaided human now has
loss 1.15 in regime 1 and 0.35 in regime 2, while the algorithm has loss 0.2
in regime 1 and 0.8 in regime 2. While average (unaided) human and algorithmic
loss are the same as in Scenarios 1 and 2, the combined human-algorithmic
system ends up having average loss of 0.45, which strictly lower than either
the unaided human or algorithm alone. Complementarity arises here because
diversity of errors and appropriate reliance when algorithmic error is lower
than the human’s. As we show in Section 5, these conditions are necessary for
complementarity to arise.

Let’s return to our motivating example: a doctor using algorithmic input to
make predictions about patients. These three examples illustrate different
possible overall loss rates from a doctor and algorithm with the same average
loss rates alone. It is clearly important for overall performance (including
patient well-being) to determine whether the human-algorithm system will
result in something like Scenario 1 (with higher loss than either the doctor
or algorithm alone) or Scenario 3 (with lower loss than either alone). In the
coming sections we lay out a theoretical framework for analyzing combined
human-algorithm systems more generally to understand their implications for
fairness and complementary performance. Our analysis formalizes the
observations made in the scenarios above by precisely characterizing the role
that “appropriate” reliance on the algorithm and variability in performance
across regimes plays in complementarity and fairness.

###  4.2 Complementarity and fairness

Complementarity is the best-case scenario for human-algorithm collaboration,
and much of our paper will revolve around proving when it can and cannot
exist. For instance, in Section 5 we will give theoretical results describing
the kinds of factors necessary for complementarity to be achievable. In
particular, we will give conditions on the distributions of loss rates as well
as the way predictions are combined. We will show that, all else being equal,
complementarity is easier to achieve when distributions of loss for the
algorithm and unaided human are highly variable. For example, the algorithm’s
loss rates are less variable in Tables 4 and 4 (ranging from 0.35 to 0.65)
than they are in Table 4 (where they go from 0.2 to 0.8). However, variable
loss rates naturally have fairness implications.

Fairness concerns are especially salient if the regimes are correlated with
sensitive attributes, such as race, ethnicity, sex, gender, or socioeconomic
status. One fairness question could revolve around the “loss disparity” \- the
difference in loss rates between multiple regimes. Many papers in algorithmic
fairness focus on loss disparity (also called accuracy parity or disparate
mistreatment [39, 12]), making them a natural focus in our work. In Table 4,
there’s an loss disparity (difference in loss rates between regimes) of 0.8
for the unaided human and 0.6 for the algorithm. However, the combined system
has an loss disparity of 0.02—much lower than either the human or algorithm!
Can we guarantee that combined systems will always have lower loss
disparities? In Section 6 we will show that, under some conditions,
complementarity implies a bounded loss disparity. Another fairness concern
could revolve around whether the benefits of incorporating an algorithm are
shared among all groups. For example, in Table 4, regime 2 sees a reduction in
loss when the algorithm is incorporated, going from 1.15 (unaided human) to
0.44 (combined human with algorithm). However, regime 1 sees an increase in
loss, from 0.35 to 0.46. Ideally, a combined system should benefit all
regimes—but (when) is this possible? In Section 6, we will show that,
unfortunately, any system exhibiting complementarity can’t be one where all
regimes see their loss decrease from what it was with the unaided human.

##  5 Complementarity

In this section, we analyze complementarity: when will a combined human-
algorithm system have lower average loss than either the unaided human or
algorithm? First, we give general results for when complementarity is
impossible to achieve. Secondly, we build on these previous results in order
to give constructive examples where complementarity is possible. Finally, we
discuss some implications of our findings. All proofs are given in Appendix B.

###  5.1 Cases Where Complementarity is Impossible

This section gives cases where complementarity is _impossible_ to achieve.
These results help to narrow the scope of cases that we must consider for
future analysis. They could also be helpful for practitioners: if any of their
cases is addressed by these lemmas, then they can immediately know that their
system can never achieve complementarity.

We begin by presenting two lemmas that concern the distribution of loss rates
for the unaided human or the algorithm. Lemma 2 considers a case where the
loss of the algorithm and unaided human are constant across regimes. Constant
loss is of course unlikely to arise in practice, but is often a setting
considered in the computational science literature.

######  Lemma 2.

A human-algorithm system where unaided human and algorithm loss rates are
constant over regimes can never achieve complementary performance.

The next result, Lemma 3, considers the setting where one of the components
outperforms the other in every regime. Specifically, it says that if one of
the unaided human or algorithm always has lower loss than the other, then
complementarity is impossible.

######  Lemma 3.

Complementarity is impossible if one of the human or algorithm always weakly
dominates the loss of the other: that is, if $a_{i}\leq h_{i}$ for all $i$, or
$a_{i}\geq h_{i}$ for all $i$.

This result may have implications for tasks where the algorithm has extremely
high performance, achieving lower loss than the human for all types of inputs.
While this could mean that the combined system will have lower loss than the
human alone, Lemma 3 tells us that it can’t achieve lower loss than both the
human and algorithm.

Next, we will consider two lemmas that concern properties of the combining
rules (the way the human incorporates advice from the unaided human and the
algorithm). First, Lemma 4 analyzes a case where the combining function is
convex in its arguments.

######  Lemma 4.

A combining function $c(a_{i},h_{i})$ that is convex in $a_{i},h_{i}$ can
never achieve complementary performance.

Recalling that the maximum function, $\max(a,h)$, that returns whichever of
the unaided human or algorithm has higher loss, is convex, this result is very
intuitive.

A simple but important corollary (Corollary 1) is that complementarity is
impossible whenever the weighting function $w_{h}(a_{i},h_{i})$ is constant
(independent of the algorithm or human’s loss rate). This might reflect a
situation where the decision-maker either is ignorant of the loss rates by the
human or algorithm, or else decides to ignore them.

######  Corollary 1.

A combining function with a constant weighting function
$w_{h}(a_{i},h_{i})=w_{h}$ can never achieve complementarity performance.

###### Proof.

Note that $c(a,h)=w_{h}\cdot h+(1-w_{h})\cdot a$ is convex in both $a$ and
$h$. ∎

These results, taken together, show that any system that could potentially
achieve complementarity must have weighting function that varies with the
inputs, must have human or algorithmic loss that varies, must have a combining
function that is not convex, and cannot have either the human or algorithm
dominate the loss of the other.

###  5.2 Cases Where Complementarity is Possible: $N=2$ regimes

Having shown cases where complementarity is impossible, in this section we
give conditions where complementarity is possible. As we described in Section
3, our notation describes the loss of the unassisted human in regime $i$ by
$h_{i}=H+\delta_{hi}$ and the loss of the algorithm by $a_{i}=A+\delta_{ai}$,
where $H$ and $A$ are the average losses of the unassisted human and
algorithm, respectively. Additionally, $w_{h}(a_{i},h_{i})$ (as defined in
Equation 1) is the weighting function—the weight that the human places on
themselves in making a final prediction.

We will first build intuition with the $N=2$ case: there are exactly two
regimes, with regime 1 having probability $p$ of occurring. By assumption,
$\sum_{i=1}^{N}p_{i}\cdot\delta_{ai}=0$ (and similarly for unaided human
loss). This allows us to simplify the $N=2$ loss distributions into:

$\text{unaided human loss: }\begin{cases}h_{1}=H+\delta_{h}\\\
h_{2}=H-\frac{p}{1-p}\delta_{h}\end{cases}\quad\text{algorithmic loss:
}\begin{cases}a_{1}=A+\delta_{a}\\\
a_{2}=A-\frac{p}{1-p}\delta_{a}\end{cases}$

This formulation is without loss of generality because we allow
$\delta_{a},\delta_{h}$ to be positive, negative, or zero. In the case that
$\delta_{a},\delta_{h}$ are the same sign, loss rates for the human and
algorithm are correlated. If they are of a different sign, then loss rates are
anti-correlated. $\delta_{a},\delta_{h}$ values of larger magnitude correspond
to a more variable distribution of losses.

Lemma 5 gives a condition for when a $N=2$ example can achieve
complementarity. Note that the condition gives a lower bound on the magnitude
of $|\delta_{a}-\delta_{h}|$, terms which reflect the variability in human and
algorithmic loss. This bound depends on $A$ and $H$, the average loss rates of
the algorithm and human. It also depends on
$w_{h}(a_{1},h_{1}),w_{h}(a_{2},h_{2})$, the weighting functions for the human
in the 1st and 2nd regime, respectively. Recall that Corollary 1 tells us that
any system exhibiting complementarity cannot have
$w_{h}(a_{1},h_{1})=w_{h}(a_{2},h_{2})$, because that would imply a constant
weighting function.

######  Lemma 5.

Consider the case where $N=2$, and WLOG assume that $A\leq H$: the algorithm
has lower average loss than the human. Then, the combined system exhibits
complementarity whenever:

$(H-A)\cdot\frac{w_{h}(a_{1},h_{1})+\frac{1-p}{p}\cdot
w_{h}(a_{2},h_{2})}{|w_{h}(a_{2},h_{2})-w_{h}(a_{1},h_{1})|}<|\delta_{a}-\delta_{h}|$

Figure 2: Low combined loss occurs for high variability (large
$|\delta_{a}-\delta_{h}|$). The plot displays combined loss for a $N=2$
system, for four combining functions. The black dashed line gives loss of
algorithm alone: since for this setting the algorithm has lower error than the
unaided human, complementarity occurs below this line. Note that for all four
combining functions, complementarity occurs where $|\delta_{a}-\delta_{h}|$ is
large. For details on the combining functions, including the exemplar function
(original to this work), see Appendix A.

Figure 2 displays the loss of the combined system for four different possible
combining functions (models of how humans incorporate algorithmic advice). For
each of them, complementarity occurs when $|\delta_{a}-\delta_{h}|$ is high,
as Lemma 5 suggests. However, as Lemma 6 states, this does _not_ mean that
unaided human and algorithm loss need to be anti-correlated.

| (Unaided) human | Algorithm |  | Combined
---
(human using algorithm)
| Weight
---
(on unaided human)
Regime 1 | 1.15 | 0.2 | 0.44 | 0.25
Regime 2 | 0.35 | 0.8 | 0.46 | 0.75
Average | 0.75 | 0.5 | 0.45 | 0.5

Table 5: (Reproduced version of Table 4). The unaided human has loss 0.75, the
algorithm has loss 0.5, and the combined system has loss 0.45 (complementary
performance). In this table, we have $\delta_{a}=0.4,\delta_{h}=-0.3$, for
$|\delta_{a}-\delta_{h}|=0.7$. Note that here, losses are anti-correlated: the
unaided human has higher loss in regime 1, while the algorithm has higher loss
in regime 2.

| (Unaided) human | Algorithm |  | Combined
---
(human using algorithm)
| Weight
---
(on unaided human)
Regime 1 | 1.48 | 0.53 | 0.77 | 0.25
Regime 2 | 0.02 | 0.47 | 0.13 | 0.75
Average | 0.75 | 0.5 | 0.45 | 0.5

Table 6: Correlated loss: The combined system (human using algorithm) displays
complementary performance even though the unaided human and the algorithm both
have higher loss for regime 1. In this table, we have
$\delta_{a}=0.73,\delta_{h}=0.03$, for $|\delta_{a}-\delta_{h}|=0.7$.

######  Lemma 6.

A system can exhibit complementarity even if the unaided human and the
algorithm have correlated loss (both have higher loss in the same regime).

This is a reassuring result because, otherwise, complementarity would not be
possible in settings where a given regime is fundamentally harder than
another. For example, one regime might be low-resolution images while another
might be high-resolution images, so both humans and algorithms are expected to
perform worse in the low-resolution regime. In our notation, if $\delta_{a}>0$
and $\delta_{h}>0$, then both the unaided human and algorithm have lower loss
in regime 2. If $|\delta_{a}-\delta_{h}|$ is large, complementarity still may
be possible. However, because $\delta_{a},\delta_{h}$ have the same signs, the
variability must be larger in order to make $|\delta_{a}-\delta_{h}|$ satisfy
the lower bound.

Tables 6 and 6 prove Lemma 6 through an example. Table 6 is a copy of Scenario
3 (Table 4) from the motivating example in Section 4. The values in the table
correspond to $\delta_{a}=0.4,\delta_{h}=-0.3$ (giving
$|\delta_{a}-\delta_{h}|=0.7$). Here, the losses are anti-correlated: the
unaided human has higher loss in regime 1, while the algorithm has higher loss
in regime 2.

Table 6 gives an example where the losses are correlated: both the unaided
human and algorithm have higher loss for regime 1. The values in the table are
given by $\delta_{a}=0.03,\delta_{h}=0.73$, which again gives
$|\delta_{a}-\delta_{h}|=0.7$. Even though losses are correlated, the overall
system still displays complementarity because $|\delta_{a}-\delta_{h}|$ has
remained the same, as Lemma 5 suggests.

###  5.3 Cases Where Complementarity is Possible: $N>2$ regimes

Finally, we will consider the general $N>2$ case.

######  Lemma 7.

WLOG, assume that $A\leq H$: the algorithm has lower loss, on average. Then, a
combined human-algorithm system achieves complementarity whenever:

$(H-A)\cdot\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})<\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(\delta_{ai}-\delta_{hi})$

If we view $w_{h}(a_{i},h_{i})$ and $\delta_{ai},\delta_{hi}$ as random
variables over the instance space with probability mass governed the
distribution of instances given by $\\{p_{i}\\}$, then we can interpret the
condition as:

$(H-A)\cdot\mathbb{E}[w_{h}(a_{i},h_{i})]<Cov\left(w_{h}(a_{i},h_{i}),\delta_{ai}-\delta_{hi}\right)$

where $Cov(\cdot)$ gives the covariance.

Lemma 7 gives conditions on complementarity, requiring that the weighting
function $w_{h}(a_{i},h_{i})$ have high covariance with the difference between
$\delta_{ai}$ and $\delta_{hi}$. Intuitively, this means that when the
algorithm is more _above_ its typical loss than the unaided human (when
$\delta_{ai}>\delta_{hi}$), then the combined loss should rely more heavily on
the unaided human ($w_{h}(a_{i},h_{i})$ should be large). Conversely, if the
algorithm is more _below_ its typical loss than the unaided human (when
$\delta_{ai}<\delta_{hi}$), then the combined loss should rely more heavily on
the algorithm ($w_{h}(a_{i},h_{i})$ should be small). The lefthand side of the
equation lower bounds how large this covariance must, as a function of the gap
between the average loss of the unaided human and the algorithm, and the
expected value of the weighting function.

The results in this section imply that unaided human and algorithmic error
rates must be highly variable. One question this raises is about
achievability: is it even possible to arrange human and algorithmic loss rates
like this? For example, achieving a highly variable loss rate for an algorithm
may require retraining, and for certain cases may not be possible.
Manipulating the loss rate for a human may be possible through re-assigning
human effort: for example, assigning multiple humans to certain portions of
the input space in order to reduce loss.

Even if highly variable loss rates are possible, they may not be desirable for
other reasons. In particular, the next section discusses the fairness
implications of complementarity.

##  6 Fairness

There are numerous possible notions of fairness that could be relevant for a
human-algorithm classifier. In this section, we will analyze three of them and
describe how they relate to complementarity. (All proofs are given in Appendix
B). In general, the notions of fairness concern disparities in loss across
different regimes. Disparities in loss rates could be alarming (if they align
or correlate with sensitive attributes, such as race, gender, or socioeconomic
status) or innocuous (if they are unrelated to sensitive attributes). In this
paper, we will consider two general classes of fairness concerns: _fairness of
benefit_ and _loss disparity_ rates. Fairness of benefit relates to which
regimes see their loss rate decrease when the algorithm is incorporated into
the decision-making process. Ideally, all regimes would benefit from human-
algorithm collaboration. We will show that is unfortunately not possible. Loss
disparity rates relate to the gap in loss rates between different regimes:
ideally, this gap would be small, which would reflect equal loss rates for all
regimes. In this work, we will show that complementarity can sometimes help
bound loss disparity.

###  6.1 Fairness of benefit

First, Definition 2 says that a system has “fairness of benefit” if all
regimes experience a lower loss from the combined human-algorithm system than
they would experience with the unassisted human.

######  Definition 2 (Fairness of benefit).

A human/algorithm system exhibits _fairness of benefit_ if all regimes benefit
from the combined system (experience a lower loss than with the unaided
human).

This notion captures the desideratum that the benefits resulting from
switching to a combined human-algorithm system are shared by all. However,
Lemma 8 shows that this notion of fairness is incompatible with
complementarity.

######  Lemma 8.

Any system exhibiting fairness of benefits cannot have complementary
performance.

###### Proof.

This result is largely due to Lemma 3. Note that we have:

$c(a_{i},h_{i})=(1-w_{h}(a_{i},h_{i}))\cdot a_{i}+w_{h}(a_{i},h_{i})\cdot
h_{i}$

for $s_{i}\in[0,1]$. Then, if we have fairness of benefits, we know:

$(1-w_{h}(a_{i},h_{i}))\cdot a_{i}+w_{h}(a_{i},h_{i})\cdot h_{i}<h_{i}\
\forall i\in[N]$

In order to achieve this, we need $w_{h}(a_{i},h_{i})<1$ and $a_{i}<h_{i}$,
for all $i\in[N]$. However, this is exactly the condition addressed in Lemma
3: the algorithm always has lower loss than the unassisted human, which means
that complementarity is impossible. ∎

Note that Definition 2 could be defined symmetrically, defining “benefit” as a
reduction in loss as compared to the algorithmic prediction. In this case, an
analogous version of Lemma 8 would hold, similarly showing that this notion of
fairness is incompatible with complementarity.

Lemma 8 tells us that there is an inherent tension between achieving
complementarity and ensuring all people who use the system see their loss
rates decrease. For certain application areas, fairness of benefit might be
more important than complementarity, so practitioners might consciously choose
to prioritize it. On the other hand, a practitioner who opts to achieve
complementarity instead of fairness of benefit might wish to consider
alternate ways to support any groups that see their loss increase in the
combined system.

###  6.2 Loss disparity

Next, Definition 3 describes fairness as the disparity in loss rates between
different regimes. Intuitively, this notion relates to group-based notions of
fairness: loss rates should be relatively similar between members of different
groups. However, Lemma 9 again describes how this notion of fairness is in
tension with complementarity, which puts a lower bound on the level of this
kind of unfairness.

######  Definition 3 (Loss disparity).

A prediction system exhibits $\epsilon$-loss disparity if the losses in
different regimes differ by no more than $\epsilon$. We will use
$\epsilon_{h},\epsilon_{a},\epsilon_{c}$ to refer to the loss disparity of the
unaided human, algorithm alone, and combined human-algorithm system,
respectively.

######  Lemma 9.

WLOG assume that $A\leq H$: the algorithm has lower average loss than the
human. Then, any system exhibiting complementarity has a lower bound on
$\epsilon_{a}+\epsilon_{h}$: the combined loss disparity of the unaided human
and algorithm.

$A-C+(H-A)\cdot\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})<\epsilon_{a}+\epsilon_{h}$

Lemma 9 should match our intuition from Section 5. There, results indicated
that complementarity is easiest to achieve when loss rates are highly
variable. However, this directly contradicts with the goal of minimizing loss
disparity.

Next, we will consider the loss disparity of the combined human-algorithm
system. Unfortunately, it is possible for a system exhibiting complementarity
to _exacerbate_ unfairness. Table 7 gives an example where the combined system
has a higher loss disparity than either the unaided human or the algorithm,
even though it exhibits complementarity. This result (which parallels results
from [10, 11, 36]) means that practitioners must be careful when discussing
fairness of combined systems: fairness guarantees from the individual
components don’t necessarily transfer to the combined human-algorithm system.

| (Unaided) Human | Algorithm | Combined (human using algorithm)
---|---|---|---
Regime 1 | 0.95 | 0.85 | 0.895
Regime 2 | 0.95 | 0.02 | 0.05
Regime 3 | 0.15 | 0.45 | 0.255
Average loss | 0.68 | 0.44 | 0.40
Table 7: This system exhibits complementarity, since average loss is lowest in
the combined human-algorithm system. However, note that loss disparity is
_increased_ in the combined system: $\epsilon_{h}=0.8,\epsilon_{a}=0.83$, but
$\epsilon_{c}=0.84$.

However, Lemma 10 gives a condition where the loss disparity of the combined
human-algorithm system is upper bounded by the loss disparity of the unaided
human or the algorithm.

######  Lemma 10.

Define $i+$ as the regime where the combined human-algorithm system has
highest loss and $i-$ as the regime where it has lowest loss. Then, the loss
disparity of the combined system is upper bounded by the loss disparity of the
unaided human or algorithm, so long as neither the unaided human or algorithm
dominates the other in both $i+,i-$. That is,

$\text{If either case is satisfied: }\begin{cases}h_{i+}\leq a_{i+}\text{ and
}h_{i-}\geq a_{i-}\\\ h_{i+}\geq a_{i+}\text{ and }h_{i-}\leq a_{i-}\\\
\end{cases}\quad\Rightarrow\quad\epsilon_{c}\leq\max(\epsilon_{a},\epsilon_{h})$

This last lemma gives our first positive result for fairness: it gives
conditions where human-algorithm system exhibiting complementarity at least
doesn’t exacerbate unfairness. Specifically, what it requires is that neither
the unaided human nor the algorithm dominates the other for both of the most
extreme regimes (where the combined system has highest and lowest loss). As we
would expect, the scenario in Table 7 violates this: the unaided human
dominates in both regime 1 (highest loss) and regime 2 (lowest loss), which
allows the combined loss disparity $\epsilon_{c}$ to be greater than
$\max(\epsilon_{a},\epsilon_{h})$. Interestingly, Lemma 10 is quite powerful:
it only relies on the losses within two specific regimes and holds regardless
of whether the overall system satisfies complementarity. Practitioners could
use Lemma 10 to guide their algorithm development: so long as the
preconditions are satisfied, they can guarantee that the combined system will
never exacerbate unfairness.

As we mentioned previously, these definitions are only a few of the possible
fairness concerns we could analyze. However, this analysis highlights the
importance of considering fairness, especially ways that it might be in
tension with achieving complementarity.

##  7 Conclusion and Future Directions

In this work, we introduce a simple theoretical model of human-algorithm
collaboration, which we show is flexible enough to encompass models analyzed
in prior work. Using this model, we obtain theoretical impossibility results
that characterize settings where complementarity is not achievable. We also
use this framework to construct cases where complementarity is possible, given
certain conditions on the loss distributions. Finally, we consider the
implications, especially fairness, of the requirements in order to achieve
complementarity.

Our approach admits multiple possible avenues for future work. Our work
highlights the importance of variable loss rates: algorithmic loss that is not
constant over the input space. However, as mentioned previously, it may not be
possible to achieve extremely variable loss rates. Future work could model
algorithmic loss rates more explicitly, describing loss distributions that are
both achievable and lead to complementary performance. For example, some prior
work has demonstrated that, for many algorithms, reducing loss becomes harder
as the level of loss decreases, which could make it more difficult to achieve
highly variable loss rates [15, 16].

Similarly, future work could relax assumptions made in our work. Relaxing
Assumption 2, for example, could involve analyzing combining rules that, on
any individual regime, could do better or worse than the human or algorithmic
input loss rates. Relaxing Assumption 1 could involve modeling cases where
regimes with identical human and algorithmic loss rates might be treated
differently by the combiner. Any of these future analyses could allow us to
have greater insight into a variety of ways human-algorithm systems perform.

## Acknowledgments

This work was supported in part by NSF grant DGE-1650441. We are grateful to
Vijay Keswani, Jon Kleinberg, Pang Wei Koh, Michela Meister, Emma Pierson,
Charvi Rastogi, Aaron Roth, Kiran Tomlinson, Aaron Tucker, Qian Yang, Joyce
Zhou, James Zou, the AWS Machine Learning team, the AI, Policy, and Practice
working group at Cornell, and the attendees at the NeurIPS 2021 Workshops on
Human-Centered AI and Human and Machine Decisions for invaluable discussions.

## References

  * Bansal et al. [2021a] G. Bansal, B. Nushi, E. Kamar, E. Horvitz, and D. S. Weld.  Is the most accurate AI the best teammate? Optimizing AI for teamwork.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 11405–11414, 2021a.
  * Bansal et al. [2021b] G. Bansal, T. Wu, J. Zhou, R. Fok, B. Nushi, E. Kamar, M. T. Ribeiro, and D. Weld.  Does the whole exceed its parts? The effect of AI explanations on complementary team performance.  In _Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems_ , pages 1–16, 2021b.
  * Beede et al. [2020] E. Beede, E. Baylor, F. Hersch, A. Iurchenko, L. Wilcox, P. Ruamviboonsuk, and L. M. Vardoulakis.  A human-centered evaluation of a deep learning system deployed in clinics for the detection of diabetic retinopathy.  In _Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems_ , pages 1–12, 2020.
  * Cowgill and Stevenson [2020] B. Cowgill and M. T. Stevenson.  Algorithmic social engineering.  In _AEA Papers and Proceedings_ , volume 110, pages 96–100, 2020\.
  * De et al. [2021] A. De, N. Okati, A. Zarezade, and M. Gomez-Rodriguez.  Classification under human assistance.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 5905–5913, 2021.
  * De-Arteaga et al. [2020] M. De-Arteaga, R. Fogliato, and A. Chouldechova.  A case for humans-in-the-loop: Decisions in the presence of erroneous algorithmic scores.  In _Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems_ , pages 1–12, 2020.
  * Didaci et al. [2013] L. Didaci, G. Fumera, and F. Roli.  Diversity in classifier ensembles: Fertile concept or dead end?  In _International workshop on multiple classifier systems_ , pages 37–48. Springer, 2013.
  * Dietvorst and Bharti [2020] B. J. Dietvorst and S. Bharti.  People reject algorithms in uncertain decision domains because they have diminishing sensitivity to forecasting error.  _Psychological science_ , 31(10):1302–1314, 2020\.
  * Dietvorst et al. [2018] B. J. Dietvorst, J. P. Simmons, and C. Massey.  Overcoming algorithm aversion: People will use imperfect algorithms if they can (even slightly) modify them.  _Management Science_ , 64(3):1155–1170, 2018\.
  * Dwork and Ilvento [2018] C. Dwork and C. Ilvento.  Fairness under composition.  In _10th Innovations in Theoretical Computer Science Conference (ITCS 2019)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * Dwork et al. [2020] C. Dwork, C. Ilvento, and M. Jagadeesan.  Individual fairness in pipelines.  In _1st Symposium on Foundations of Responsible Computing (FORC 2020)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * Fraenkel [2020] A. Fraenkel.  Fairness and algorithmic decision making, 2020.  URL https://afraenkel.github.io/fairness-algo-decision.
  * Geirhos et al. [2020] R. Geirhos, K. Meding, and F. A. Wichmann.  Beyond accuracy: quantifying trial-by-trial behaviour of cnns and humans by measuring error consistency.  _Advances in Neural Information Processing Systems_ , 33:13890–13902, 2020.
  * Gillis et al. [2021] T. Gillis, B. McLaughlin, and J. Spiess.  On the fairness of machine-assisted human decisions.  _arXiv preprint arXiv:2110.15310_ , 2021.
  * Hestness et al. [2017] J. Hestness, S. Narang, N. Ardalani, G. F. Diamos, H. Jun, H. Kianinejad, M. M. A. Patwary, Y. Yang, and Y. Zhou.  Deep learning scaling is predictable, empirically.  _CoRR_ , abs/1712.00409, 2017.  URL http://arxiv.org/abs/1712.00409.
  * Kaplan et al. [2020] J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, J. Wu, and D. Amodei.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Kerrigan et al. [2021] G. Kerrigan, P. Smyth, and M. Steyvers.  Combining human predictions with model probabilities via confusion matrices and calibration.  2021\.
  * Keswani et al. [2021] V. Keswani, M. Lease, and K. Kenthapadi.  Towards unbiased and accurate deferral to multiple experts.  In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 154–165, 2021.
  * Keswani et al. [2022] V. Keswani, M. Lease, and K. Kenthapadi.  Designing closed human-in-the-loop deferral pipelines.  _arXiv preprint arXiv:2202.04718_ , 2022.
  * Kuncheva [2014] L. I. Kuncheva.  _Combining pattern classifiers: methods and algorithms_.  John Wiley & Sons, 2014.
  * Lebovitz et al. [2020] S. Lebovitz, H. Lifshitz-Assaf, and N. Levina.  To incorporate or not to incorporate ai for critical judgments: The importance of ambiguity in professionals’ judgment process.  _Collective Intelligence, The Association for Computing Machinery_ , 2020.
  * Lebovitz et al. [2021] S. Lebovitz, N. Levina, and H. Lifshitz-Assaf.  Is AI ground truth really “true”? the dangers of training and evaluating AI tools based on experts’ know-what.  _Management Information Systems Quarterly_ , 2021.
  * Madras et al. [2018] D. Madras, T. Pitassi, and R. Zemel.  Predict responsibly: Improving fairness and accuracy by learning to defer.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/09d37c08f7b129e96277388757530c72-Paper.pdf.
  * Meehl [1954] P. E. Meehl.  Clinical versus statistical prediction: A theoretical analysis and a review of the evidence.  1954\.
  * Meresht et al. [2020] V. B. Meresht, A. De, A. Singla, and M. Gomez-Rodriguez.  Learning to switch between machines and humans.  _ICML Workshop on Human-AI Collaboration in Sequential Decision-Making._ , 2020.
  * Okati et al. [2021] N. Okati, A. De, and M. Rodriguez.  Differentiable learning under triage.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Okolo et al. [2021] C. T. Okolo, S. Kamath, N. Dell, and A. Vashistha.  “it cannot do all of my work”: Community health worker perceptions of ai-enabled mobile health applications in rural india.  In _Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems_ , pages 1–20, 2021.
  * Poursabzi-Sangdeh et al. [2021] F. Poursabzi-Sangdeh, D. G. Goldstein, J. M. Hofman, J. W. Wortman Vaughan, and H. Wallach.  Manipulating and measuring model interpretability.  In _Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems_ , pages 1–52, 2021.
  * Raghu et al. [2018] M. Raghu, K. Blumer, G. Corrado, J. Kleinberg, Z. Obermeyer, and S. Mullainathan.  The algorithmic automation problem: Prediction, triage, and human effort.  _NeurIPS Workshop on Machine Learning for Health (ML4H)_ , 2018.
  * Sayres et al. [2019] R. Sayres, A. Taly, E. Rahimy, K. Blumer, D. Coz, N. Hammel, J. Krause, A. Narayanaswamy, Z. Rastegar, D. Wu, S. Xu, S. Barb, A. Joseph, M. Shumski, J. Smith, A. B. Sood, G. S. Corrado, L. Peng, and D. R. Webster.  Using a deep learning algorithm and integrated gradients explanation to assist grading for diabetic retinopathy.  _Ophthalmology_ , 126(4):552–564, 2019.
  * Srivastava et al. [2020] M. Srivastava, B. Nushi, E. Kamar, S. Shah, and E. Horvitz.  An empirical analysis of backward compatibility in machine learning systems.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 3272–3280, 2020.
  * Straitouri et al. [2022] E. Straitouri, L. Wang, N. Okati, and M. G. Rodriguez.  Provably improving expert predictions with conformal prediction, 2022\.
  * Tan et al. [2018] S. Tan, J. Adebayo, K. Inkpen, and E. Kamar.  Investigating human+ machine complementarity for recidivism predictions.  _NeurIPS 2018 Workshop on Ethical, Social and Governance Issues in AI_ , 2018.
  * Valera et al. [2018] I. Valera, A. Singla, and M. Gomez Rodriguez.  Enhancing the accuracy and fairness of human decision making.  In _Advances in Neural Information Processing Systems 31 (NeurIPS 2018)_ , pages 1774–1783. Curran Associates, Inc., Dec. 2018.  URL http://papers.nips.cc/paper/7448-enhancing-the-accuracy-and-fairness-of-human-decision-making.pdf.
  * Vodrahalli et al. [2021] K. Vodrahalli, T. Gerstenberg, and J. Zou.  Do humans trust advice more if it comes from AI? An analysis of human-AI interactions.  _arXiv preprint arXiv:2107.07015_ , 2021.
  * Wang et al. [2021] X. Wang, N. Thain, A. Sinha, F. Prost, E. H. Chi, J. Chen, and A. Beutel.  Practical compositional fairness: Understanding fairness in multi-component recommender systems.  In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ , pages 436–444, 2021.
  * Yang et al. [2018] Q. Yang, A. Scuito, J. Zimmerman, J. Forlizzi, and A. Steinfeld.  Investigating how experienced ux designers effectively work with machine learning.  In _Proceedings of the 2018 Designing Interactive Systems Conference_ , pages 585–596, 2018.
  * Yin et al. [2019] M. Yin, J. Wortman Vaughan, and H. Wallach.  Understanding the effect of accuracy on trust in machine learning models.  In _Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems_ , pages 1–12, 2019.
  * Zafar et al. [2017] M. B. Zafar, I. Valera, M. Gomez Rodriguez, and K. P. Gummadi.  Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment.  In _Proceedings of the 26th International Conference on World Wide Web_ , WWW ’17, page 1171–1180, Republic and Canton of Geneva, CHE, 2017\. International World Wide Web Conferences Steering Committee.  ISBN 9781450349130.  doi: 10.1145/3038912.3052660.  URL https://doi.org/10.1145/3038912.3052660.

##  Appendix A Modeling Combining Functions

The definitions presented in Section 3 reflect multiple ways humans could
incorporate algorithmic inputs. However, their functional forms in some cases
are less clean to analyze. Definition 4 gives an _exemplar_ weighting function
(original to this work) that we created in order to illustrate common patterns
in weighting functions, while also allowing for tractable theoretical
analysis. In this function, for $m>0$, the combining rule is more likely to
select the algorithm when $a<h$ (when the algorithm has lower loss rate). For
$m>0$, the reverse is true: the combining rule “mistakenly” goes with the
input with higher loss.

######  Definition 4 (Exemplar weighting function).

The exemplar weighting function is given by:

$w_{h}(a,h)=\begin{cases}b-m\cdot(h-a)&0\leq b-m\cdot(h-a)\leq 0\\\
0&b-m\cdot(h-a)<0\\\ 1&b-m\cdot(h-a)>1\end{cases}$

Figure 3 plots the weighting function for each of the selection rules
presented. Note that, in general, as the human gets higher loss, the weight on
the human decreases.

Figure 3: The weight on the human, given a difference $h-a$ between
algorithmic and human loss, for multiple weighting functions. Note that, in
general, as the human gets higher loss than the algorithm, the weight on the
human decreases.

Lemma 11, below, gives an analgous version of Lemma 5 for the exemplar
function. Note that it similarly shows that complementarity occurs when
$|\delta_{a}-\delta_{h}|$ is large (when losses are highly variable).

######  Lemma 11.

Consider the exemplar weighting function with $N=2$ and
$w_{h}(a_{0},h_{0}),w_{h}(a_{1},h_{1})<1$, and where $A\leq H$. Then, the
system exhibits complementarity whenever:

$\sqrt{H-A}\cdot\sqrt{\frac{1-p}{p}\cdot\left(\frac{1-b}{m}-(H-A)\right)}<|\delta_{a}-\delta_{h}|$

##  Appendix B Proofs

See 1

###### Proof.

We will define a weighting function as follows:

$w_{h}(a,h)=\begin{cases}\frac{c(a,h)-a}{h-a}&a\neq h\\\
\frac{1}{2}&a=h\end{cases}$

Note that if $c(a,h)=h$, then $w_{h}(a,h)=1$ (the weighting function puts all
weight on the unaided human), and if $c(a,h)=a$, then $w_{h}(a,h)=0$ (the
weighting function puts no weight on the unaided human).

First, we’ll show that $w_{h}(a,h)\in[0,1]$. If $a=h$, this is true by
construction (because $w_{h}(a,h)=\frac{1}{2}$). What we want to show is:

$0\leq\frac{c(a,h)-a}{h-a}\leq 1$

If $h>a$, then this is equivalent to requiring:

$0\leq c(a,h)-a\leq h-a$

The lefthand inequality is satisfied because $c(a,h)\geq\min(a,h)=a$ (in this
case). The righthand inequality is satisfied because $c(a,h)\leq\max(a,h)=h$
(in this case).

On the other hand, if $h<a$, then the inequality we want to show is:

$0\geq c(a,h)-a\geq h-a$

Again, the lefthand inequality is satisfied because $c(a,h)\leq\max(a,h)=a$
(in this case). The righthand inequality is satisfied because
$c(a,h)\geq\min(a,h)=h$ (in this case).

Next, we’ll show that this weighting function is correct: that is, that:

$c(a,h)=(1-w_{h}(a,h))\cdot a+w_{h}(a,h)\cdot h$

Note that Assumption 2 means that if $a=h$, then $c(a,h)=a=h$, so any
$w_{h}(a,h)\in[0,1]$ would result in a correct weighting function. For $a\neq
h$, we can write:

$\displaystyle(1-w_{h}(a,h))\cdot a+w_{h}(a,h)\cdot h$ $\displaystyle=$
$\displaystyle
a\cdot\left(1-\frac{c(a,h)-a}{h-a}\right)+h\cdot\frac{c(a,h)-a}{h-a}$
$\displaystyle=$ $\displaystyle
a\cdot\frac{h-a-c(a,h)+a}{h-a}+h\cdot\frac{c(a,h)-a}{h-a}$ $\displaystyle=$
$\displaystyle a\cdot\frac{h-c(a,h)}{h-a}+h\cdot\frac{c(a,h)-a}{h-a}$
$\displaystyle=$ $\displaystyle\frac{a\cdot h-a\cdot c(a,h)+h\cdot
c(a,h)-a\cdot h}{h-a}$ $\displaystyle=$
$\displaystyle\frac{c(a,h)\cdot(h-a)}{h-a}$ $\displaystyle=$ $\displaystyle
c(a,h)$

as desired. ∎

See 2

###### Proof.

Constant loss rates means that $a_{i}=A$ and $h_{i}=H$ for all $i\in[N]$. The
combined system has loss:

$\sum_{i\in[N]}p_{i}\cdot c(a_{i},h_{i})=\sum_{i\in[N]}p_{i}\cdot
c(A,H)=c(A,H)\geq\min(A,H)$

∎

See 3

###### Proof.

WLOG, we will assume that $A\leq H$. Then, complementarity occurs when:

$\displaystyle\sum_{i=1}^{N}p_{i}\cdot c(a_{i},h_{i})<$ $\displaystyle A$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot((1-w_{h}(a_{i},h_{i}))\cdot
a_{i}+w_{h}(a_{i},h_{i})\cdot h_{i})<$ $\displaystyle\sum_{i=1}^{N}p_{i}\cdot
a_{i}$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot(-w_{h}(a_{i},h_{i})a_{i}+w_{h}(a_{i},h_{i})\cdot
h_{i})<$ $\displaystyle 0$ $\displaystyle\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(h_{i}-a_{i})<$ $\displaystyle 0$

If the algorithm weakly dominates the unaided human ($h_{i}\geq a_{i}$ for all
$i$), then this inequality can never be satisfied because the entire lefthand
side is positive or 0. If the unaided human weakly dominates the algorithm
($a_{i}\geq h_{i}$ for all $i$) then $A\geq H$. From our previous assumption
that $A\leq H$, which means that we must have that $A=H$: both have identical
average losses.

We will now show that further analysis means in the case that $A=H$,
complementarity is still impossible. If $A=H$, we could have equivalently
written the complementarity condition as:

$\displaystyle\sum_{i=1}^{N}p_{i}\cdot c(a_{i},h_{i})<$ $\displaystyle H=A$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot((1-w_{h}(a_{i},h_{i}))\cdot
a_{i}+w_{h}(a_{i},h_{i})\cdot h_{i})<$ $\displaystyle\sum_{i=1}^{N}p_{i}\cdot
h_{i}$ $\displaystyle\sum_{i=1}^{N}p_{i}\cdot((1-w_{h}(a_{i},h_{i}))\cdot
a_{i}+(1-w_{h}(a_{i},h_{i}))\cdot h_{i})<$ $\displaystyle 0$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot(1-w_{h}(a_{i},h_{i}))\cdot(a_{i}-h_{i})<$
$\displaystyle 0$

In this case, we’ve assumed that $a_{i}\geq h_{i}$. However, this means that
the lefthand side of the above inequality is positive, which means
complementarity isn’t satisfied. ∎

See 4

###### Proof.

The first inequality in this proof is by Jensen’s inequality and the last
inequality is due to our construction of the combining function:

$\sum_{i\in[N]}p_{i}\cdot c(a_{i},h_{i})\geq c\left(\sum_{i\in[N]}p_{i}\cdot
a_{i},\sum_{i\in[N]}p_{i}\cdot h_{i}\right)=c(A,H)\geq\min(A,H)$

∎

See 5

###### Proof.

If we assume that $A\leq H$, then complementarity occurs whenever $C<A$, or:
The system exhibits complementarity when:

$\displaystyle p\cdot c(a_{1},h_{1})+(1-p)\cdot c(a_{2},h_{2})<$
$\displaystyle A$ $\displaystyle p\cdot((1-w_{h}(a_{1},h_{1}))\cdot
a_{1}+w_{h}(a_{1},h_{1})\cdot h_{1})+(1-p)\cdot((1-w_{h}(a_{2},h_{2})\cdot
a_{2}+w_{h}(a_{2},h_{2})\cdot h_{2})<$ $\displaystyle p\cdot a_{1}+(1-p)\cdot
a_{2}$ $\displaystyle p\cdot w_{h}(a_{1},h_{1})\cdot(h_{1}-a_{1})+(1-p)\cdot
w_{h}(a_{2},h_{2})\cdot(h_{2}-a_{2})<$ $\displaystyle 0$

We insert the values of $a_{i},h_{i}$, to get:

$\displaystyle p\cdot
w_{h}(a_{1},h_{1})\cdot(H+\delta_{h}-A-\delta_{a})+(1-p)\cdot
w_{h}(a_{2},h_{2})\cdot\left(H-\frac{p}{1-p}\cdot\delta_{h}-A+\frac{p}{1-p}\cdot\delta_{a}\right)<$
$\displaystyle 0$ $\displaystyle(H-A)\cdot(p\cdot
w_{h}(a_{1},h_{1})+(1-p)\cdot w_{h}(a_{2},h_{2}))+p\cdot
w_{h}(a_{1},h_{1})\cdot(\delta_{h}-\delta_{a})-p\cdot
w_{h}(a_{2},h_{2})\cdot\left(\delta_{h}-\delta_{a}\right)<$ $\displaystyle 0$
$\displaystyle(H-A)\cdot(p\cdot w_{h}(a_{1},h_{1})+(1-p)\cdot
w_{h}(a_{2},h_{2}))-p\cdot(\delta_{a}-\delta_{h})\cdot(w_{h}(a_{1},h_{1})-w_{h}(a_{2},h_{2}))<$
$\displaystyle 0$

Note that we have assumed $H\geq A$, so in order for this inequality to hold,
we must have that the other term (involving $\delta_{a},\delta_{h}$) be
positive. Note that by Lemma 2 we cannot have
$w_{h}(a_{1},h_{1})=w_{h}(a_{2},h_{2})$ if it exhibits complementarity. In
order to have the inequality satisfied, one of two conditions must hold:

  * •

Case 1: $\delta_{a}>\delta_{h}$ and $w_{h}(a_{1},h_{1})>w_{h}(a_{2},h_{2})$
(the unaided human is weighted more heavily in regime 1). Note that in this
case, we must have $h_{2}>a_{2}$, because:

$\displaystyle h_{2}>$ $\displaystyle a_{2}$ $\displaystyle
H-\frac{p}{1-p}\cdot\delta_{h}>$ $\displaystyle
A-\frac{p}{1-p}\cdot\delta_{a}$ $\displaystyle
H-A-\frac{p}{1-p}\cdot(\delta_{h}-\delta_{a})>$ $\displaystyle 0$
$\displaystyle H-A+\frac{p}{1-p}\cdot(\delta_{a}-\delta_{h})>$ $\displaystyle
0$

which is satisfied because $H-A\geq 0$ and $\delta_{a}>\delta_{h}$. By Lemma
3, we know that $h_{2}>a_{2}$ implies that $h_{1}\leq a_{1}$. Taken together
with $w_{h}(a_{1},h_{1})>w_{h}(a_{2},h_{2})$, this means that the combined
system must weight the human more heavily in instance 1, where it has lower
loss than the human.

  * •

Case 2: $\delta_{a}<\delta_{h}$ and $w_{h}(a_{1},h_{1})<w_{h}(a_{2},h_{2})$
(the unaided human is weighted more heavily in regime 2). In this case, we
must have $h_{1}>a_{1}$, because:

$\displaystyle H+\delta_{h}>$ $\displaystyle A+\delta_{a}$ $\displaystyle
H-A+\delta_{h}-\delta_{a}>$ $\displaystyle 0$

This must be satisfied because $H-A>0$ and $\delta_{h}>\delta_{a}$. By similar
reasoning to above, this means that $h_{2}\leq a_{2}$. Taken with
$w_{h}(a_{1},h_{1})<w_{h}(a_{2},h_{2})$, this again means that the system must
weight the unaided more heavily in the regime where it has lower loss.

Finally, we can simplify the inequality:

$(H-A)\cdot(p\cdot w_{h}(a_{1},h_{1})+(1-p)\cdot
w_{h}(a_{2},h_{2}))<p\cdot(\delta_{a}-\delta_{h})\cdot(w_{h}(a_{1},h_{1})-w_{h}(a_{2},h_{2}))$

If $\delta_{a}>\delta_{h}$, then we know that
$w_{h}(a_{1},h_{1})>w_{h}(a_{2},h_{2})$, so we can rewrite this as:

$(H-A)\cdot\frac{w_{h}(a_{1},h_{1})+\frac{1-p}{p}\cdot
w_{h}(a_{2},h_{2})}{w_{h}(a_{1},h_{1})-w_{h}(a_{2},h_{2})}\leq\delta_{a}-\delta_{h}$

On the other hand, if $\delta_{a}<\delta_{h}$, we know that
$w_{h}(a_{1},h_{1})<w_{h}(a_{2},h_{2})$, so we can rewrite this as:

$\displaystyle(H-A)\cdot(p\cdot w_{h}(a_{1},h_{1})+(1-p)\cdot
w_{h}(a_{2},h_{2}))<$ $\displaystyle
p\cdot(\delta_{h}-\delta_{a})\cdot(w_{h}(a_{2},h_{2})-w_{h}(a_{1},h_{1}))$
$\displaystyle(H-A)\cdot\frac{w_{h}(a_{1},h_{1})+\frac{1-p}{p}\cdot
w_{h}(a_{2},h_{2})}{(w_{h}(a_{2},h_{2})-w_{h}(a_{1},h_{1})}<$
$\displaystyle\delta_{a}-\delta_{h})$

Either way simplifies to:

$(H-A)\cdot\frac{w_{h}(a_{1},h_{1})+\frac{1-p}{p}\cdot
w_{h}(a_{2},h_{2})}{|w_{h}(a_{2},h_{2})-w_{h}(a_{1},h_{1})|}<|(\delta_{a}-\delta_{h})|$

∎

See 7

###### Proof.

If we assume that $A\leq H$, then complementarity occurs whenever $C<A$, or:

$\displaystyle\sum_{i=1}^{N}p_{i}\cdot c(a_{i},h_{i})\leq$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot a_{i}$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot((1-w_{h}(a_{i},h_{i}))\cdot
a_{i}+w_{h}(a_{i},h_{i})\cdot h_{i})\leq$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot a_{i}$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot(-w_{h}(a_{i},h_{i})\cdot
a_{i}+w_{h}(a_{i},h_{i})\cdot h_{i})\leq$ $\displaystyle 0$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(h_{i}-a_{i})\leq$ $\displaystyle 0$

Plugging in for the values gives:

$\displaystyle\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(H+\delta_{hi}-A-\delta_{ai})\leq$ $\displaystyle 0$
$\displaystyle(H-A)\cdot\sum_{i=1}^{N}p_{i}\cdot w_{h}(a_{i},h_{i})<$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(\delta_{ai}-\delta_{hi})$

as desired. ∎

See 9

###### Proof.

First, we will use the complementarity result from partway through the proof
of Lemma 7. We calculate the difference between the average algorithmic loss
and the average combined human-algorithmic loss (which gives us the average
benefit of collaboration):

$\displaystyle A-C=$ $\displaystyle\sum_{i=1}^{N}p_{i}\cdot
a_{i}-\sum_{i=1}^{N}p_{i}\cdot c(a_{i},h_{i})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot
a_{i}-\sum_{i=1}^{N}p_{i}\cdot((1-w_{h}(a_{i},h_{i}))\cdot
a_{i}+w_{h}(a_{i},h_{i})\cdot h_{i})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot(a_{i}-a_{i}+w_{h}(a_{i},h_{i})\cdot
a_{i}-w_{h}(a_{i},h_{i})\cdot h_{i})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}p_{i}\cdot w_{h}(a_{i},h_{i})\cdot(a_{i}-h_{i})$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(A+\delta_{ai}-H-\delta_{hi})$ $\displaystyle=$
$\displaystyle(A-H)\cdot\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})+\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(\delta_{ai}-\delta_{hi})$

Rearranging gives:

$A-C+(H-A)\cdot\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})=\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(\delta_{ai}-\delta_{hi})$

Next, we will define:

$\epsilon_{a}=a_{a+}-a_{a-}=A+\delta_{a+}-A-\delta_{a-}=\delta_{a+}-\delta_{a-}$
$\epsilon_{h}=h_{h+}-h_{h-}=H+\delta_{h+}-H-\delta_{h-}=\delta_{h+}-\delta_{h-}$

where $a+,a-,h+,h-$ are the indices of the maximum and minimum loss for the
algorithm and unaided human, respectively. Note that we require
$\sum_{i=1}^{N}p_{i}\cdot\delta_{ai}=\sum_{i=1}^{N}p_{i}\cdot\delta_{hi}=0$,
which implies that $\delta_{a+},\delta_{h+}\geq 0$ and
$\delta_{a-},\delta_{h-}\leq 0$. Then, we know that:

$\epsilon_{a}+\epsilon_{h}=\delta_{a+}-\delta_{a-}+\delta_{h+}-\delta_{h-}>\delta_{a+}-\delta_{h-}$

Define $\mathcal{P}=\\{i\ |\ \delta_{ai}\geq\delta_{hi}$ and
$\mathcal{N}=\\{i\ |\ \delta_{ai}<\delta_{hi}$. By definition,
$\delta_{a+}\geq\delta_{ai}$ and $\delta_{h-}\leq\delta_{hi}$ for all
$i\in[N]$. Then, we know that:

$\delta_{a+}-\delta_{h-}\geq\sum_{i\in\mathcal{P}}p_{i}\cdot(\delta_{hi}-\delta_{ai})\geq\sum_{i\in\mathcal{P}}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(\delta_{hi}-\delta_{ai})$

where we have used the fact that $w_{h}(a_{i},h_{i})\leq 1$. Finally, we know
that:

$\sum_{i\in\mathcal{P}}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(\delta_{hi}-\delta_{ai})\geq\sum_{i\in\mathcal{P}}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(\delta_{hi}-\delta_{ai})+\sum_{i\in\mathcal{N}}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(\delta_{hi}-\delta_{ai})=\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(\delta_{hi}-\delta_{ai})$

where the first inequality comes by the fact that $\delta_{hi}-\delta_{ai}$
for $i\in\mathcal{N}$. Finally, we can combine this analysis with our previous
analysis on the gap in loss rate between the algorithm and the combined
system:

$A-C+(H-A)\cdot\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})=\sum_{i=1}^{N}p_{i}\cdot
w_{h}(a_{i},h_{i})\cdot(\delta_{ai}-\delta_{hi})\leq\delta_{a+}-\delta_{h-}<\epsilon_{a}+\epsilon_{h}$

as desired. ∎

See 10

###### Proof.

We wish to upper bound $\epsilon_{c}$, which is given by:

$\epsilon_{c}=c(a_{i+},h_{i+})-c(a_{i-},h_{i-})$

such that:

$i+=\text{argmax}_{i\in[N]}c(a_{i},h_{i})\quad
i-=\text{argmin}_{i\in[N]}c(a_{i},h_{i})$

Note that by Assumption 2, we must have:

$c(a_{i+},h_{i+})\leq\max(a_{i+},h_{i+})\text{ and
}c(a_{i-},h_{i-})\geq\min(a_{i-},h_{i-})$

The statement of this lemma gives two cases, which we will consider in turn.
In Case 1, we assume that:

$h_{i+}\leq a_{i+}\text{ and }h_{i-}\geq a_{i-}$

In this case, we know that:

$c(a_{i+},h_{i+})-c(a_{i-},h_{i-})\leq
a_{i+}-a_{i-}\leq\epsilon_{a}\leq\max(\epsilon_{a},\epsilon_{h})$

In Case 2, we assume that:

$h_{i+}\geq a_{i+}\text{ and }h_{i-}\leq a_{i-}$

In this case, we know that:

$c(a_{i+},h_{i+})-c(a_{i-},h_{i-})\leq
h_{i+}-h_{i-}\leq\epsilon_{h}\leq\max(\epsilon_{a},\epsilon_{h})$

In either case, $\epsilon_{c}\leq\max(\epsilon_{a},\epsilon_{h})$ ∎

See 11

###### Proof.

This lemma is a more specific version of Lemma 5, so we start with an
intermediate result from that proof. Complementarity occurs whenever:

$p\cdot w_{h}(a_{1},h_{1})\cdot(h_{1}-a_{1})+(1-p)\cdot
w_{h}(a_{2},h_{2})\cdot(h_{2}-a_{2})<0$

For the exemplar combining rule, we have that:

$w_{h}(a_{i},h_{i})=b-m\cdot(h_{i}-a_{i})$

Plugging in for the values of $w_{h}(a_{1},h_{1}),w_{h}(a_{2},h_{2})$ gives:

$\displaystyle
p\cdot(b-m\cdot(h_{1}-a_{1}))\cdot(h_{1}-a_{1})+(1-p)\cdot(b-m\cdot(h_{2}-a_{2}))\cdot(h_{2}-a_{2})<$
$\displaystyle 0$ $\displaystyle
b\cdot(p\cdot(h_{1}-a_{1})+(1-p)\cdot(h_{2}-a_{2}))-m(p\cdot(h_{1}-a_{1})^{2}+(1-p)\cdot(h_{2}-a_{2})^{2})<$
$\displaystyle 0$ $\displaystyle b\cdot(p\cdot h_{1}-p\cdot a_{1}+(1-p)\cdot
h_{2}-(1-p)\cdot
a_{2})-m(p\cdot\cdot(h_{1}-a_{1})^{2}+(1-p)\cdot(h_{2}-a_{2})^{2})<$
$\displaystyle 0$ $\displaystyle
b\cdot(H-A)-m(p\cdot(h_{1}-a_{1})^{2}+(1-p)\cdot(h_{2}-a_{2})^{2})<$
$\displaystyle 0$

We can analyze the term with the $m$ coefficient by plugging in for values of
$a_{i},h_{i}$.

$\displaystyle p\cdot(h_{1}-a_{1})^{2}+(1-p)\cdot(h_{2}-a_{2})^{2}$
$\displaystyle=$ $\displaystyle
p\cdot(H+\delta_{h}-A-\delta_{a})^{2}+(1-p)\cdot\left(H-\frac{p}{1-p}\cdot\delta_{h}-A+\frac{p}{1-p}\cdot\delta_{a}\right)^{2}$

We expand out each to get:

$\displaystyle=$ $\displaystyle
p\cdot(H-A)^{2}+p\cdot(\delta_{h}-\delta_{a})^{2}+2p\cdot(H-A)\cdot(\delta_{h}-\delta_{a})+(1-p)\cdot(H-A)^{2}$
$\displaystyle+(1-p)\cdot\frac{p^{2}}{(1-p)^{2}}\cdot(\delta_{a}-\delta_{h})^{2}+2\cdot(1-p)\cdot(H-A)\cdot\frac{p}{1-p}\cdot(\delta_{a}-\delta_{h})$

We note that two of the terms cancel:

$\displaystyle
2p\cdot(H-A)\cdot(\delta_{h}-\delta_{a})+2\cdot(1-p)\cdot(H-A)\cdot\frac{p}{1-p}\cdot(\delta_{a}-\delta_{h})$
$\displaystyle=$ $\displaystyle
2p\cdot(H-A)\cdot(\delta_{h}-\delta_{a})+2\cdot
p\cdot(H-A)\cdot(\delta_{a}-\delta_{h})$ $\displaystyle=$ $\displaystyle 0$

Next, we can simplify the other terms:

$\displaystyle=$ $\displaystyle
p\cdot(H-A)^{2}+p\cdot(\delta_{h}-\delta_{a})^{2}+(1-p)\cdot(H-A)^{2}+(1-p)\cdot\frac{p^{2}}{(1-p)^{2}}\cdot(\delta_{a}-\delta_{h})^{2}$
$\displaystyle=$
$\displaystyle(H-A)^{2}+p(\delta_{h}-\delta_{a})^{2}+\frac{p^{2}}{1-p}\cdot(\delta_{a}-\delta_{h})^{2}$
$\displaystyle=$
$\displaystyle(H-A)^{2}+(\delta_{h}-\delta_{a})^{2}\cdot\left(p+\frac{p^{2}}{1-p}\right)$
$\displaystyle=$
$\displaystyle(H-A)^{2}+(\delta_{h}-\delta_{a})^{2}\cdot\frac{p}{1-p}$

where we have used that
$p+\frac{p^{2}}{1-p}=\frac{p-p^{2}+p^{2}}{1-p}=\frac{p}{1-p}$. We can combine
this with the inequality we were analyzing earlier to get:

$\displaystyle(1-b)\cdot(H-A)-m\cdot\left((H-A)^{2}+(\delta_{h}-\delta_{a})^{2}\cdot\frac{p}{1-p}\right)<$
$\displaystyle 0$ $\displaystyle(1-b)\cdot(H-A)-m\cdot(H-A)^{2}<$
$\displaystyle m\cdot(\delta_{h}-\delta_{a})^{2}\cdot\frac{p}{1-p}$
$\displaystyle\frac{1-p}{p}\left(\frac{1-b}{m}\cdot(H-A)-(H-A)^{2}\right)<$
$\displaystyle(\delta_{h}-\delta_{a})^{2}$

where we have used the assumption that $0<p<1$ and $m>0$. If the lefthand side
of the inequality is positive, we can take the square root of both sides to
get:

$\sqrt{H-A}\cdot\sqrt{\frac{1-p}{p}\left(\frac{1-b}{m}-\left(H-A\right)\right)}<|\delta_{h}-\delta_{a}|$

Finally, we will show that the term under the square root, give the
assumptions of this lemma. The term under the square root is _negative_ if:

$\frac{1-b}{m}-\left(H-A\right)<0$

or:

$1<b-m\cdot(H-A)$ (2)

We will show that, if this happens, we must have $w_{h}(a_{1},h_{1})>1$ or
$w_{h}(a_{2},h_{2})>0$ (either of which violate the assumptions of this
lemma). For this combining rule,

$w_{h}(a_{1},h_{1})=b-m\cdot(h_{1}-a_{1})=b-m\cdot(H+\delta_{h}-A-\delta_{a})=b-m\cdot(H-A)+m\cdot(\delta_{h}-\delta_{a})$

In the event that $\delta_{h}>\delta_{a}$, then the above equation is greater
than Equation 2. Therefore, if Equation 2 is greater than 1, then
$w_{h}(a_{1},h_{1})$ is also greater than 1, which violates the assumptions of
the lemma. Similarly, we can write:

$w_{h}(a_{2},h_{2})=b-m\cdot(h_{2}-a_{2})=b-m\cdot\left(H-\delta_{h}\cdot\frac{p}{1-p}-A+\delta_{a}\cdot\frac{p}{1-p}\right)=b-m\cdot(H-A)+m\cdot\frac{p}{1-p}\cdot(\delta_{a}-\delta_{h})$

In the event that $\delta_{h}<\delta_{a}$, then the above equation is greater
than Equation 2. Therefore, if Equation 2 is greater than 1, then
$w_{h}(a_{2},h_{2})$ is also greater than 1, which violates the assumptions of
the lemma. ∎