Balancing Lexicographic Fairness and a Utilitarian Objective
with Application to Kidney Exchange
John P. Dickerson†,‡

Duncan C. McElfresh†,‡
‡

†

arXiv:1702.08286v2 [cs.GT] 7 Sep 2017

Department of Mathematics
University of Maryland
dmcelfre@math.umd.edu

Abstract
Balancing fairness and efficiency in resource allocation is a
classical economic and computational problem. The price of
fairness measures the worst-case loss of economic efficiency
when using an inefficient but fair allocation rule; for indivisible goods in many settings, this price is unacceptably high.
One such setting is kidney exchange, where needy patients
swap willing but incompatible kidney donors. In this work,
we close an open problem regarding the theoretical price of
fairness in modern kidney exchanges. We then propose a general hybrid fairness rule that balances a strict lexicographic
preference ordering over classes of agents, and a utilitarian
objective that maximizes economic efficiency. We develop a
utility function for this rule that favors disadvantaged groups
lexicographically; but if cost to overall efficiency becomes
too high, it switches to a utilitarian objective. This rule has
only one parameter which is proportional to a bound on the
price of fairness, and can be adjusted by policymakers. We
apply this rule to real data from a large kidney exchange and
show that our hybrid rule produces more reliable outcomes
than other fairness rules.

1

Introduction

Chronic kidney disease is a worldwide problem whose societal burden is likened to that of diabetes (Neuen et al. 2013).
Left untreated, it leads to end-stage renal failure and the need
for a donor kidney—for which demand far outstrips supply.
In the United States alone, the kidney transplant waiting list
grew from 58,000 people in 2004 to over 100,000 needy patients (Hart et al. 2016).1
To alleviate some of this supply-demand mismatch, kidney exchanges (Rapaport 1986; Roth et al. 2004) allow patients with willing living donors to trade donors for access
to compatible or higher-quality organs. In addition to these
patient-donor pairs, modern exchanges include non-directed
donors, who enter the exchange without a patient in need of
a kidney. Exchanges occur in cycle- or chain-like structures,
and now account for 10% of living transplants in the United
States. Yet, access to a kidney exchange does not guarantee equal access to kidneys themselves; for example, certain
classes of patients may be particularly disadvantaged based
on health characteristics or other logistical factors. Thus,
fairness considerations are an active topic of theoretical and
1

https://optn.transplant.hrsa.gov/converge/data/

Department of Computer Science
University of Maryland
john@cs.umd.edu

practical research in kidney exchange and the matching market community in general.
Intuitively, any enforcement of a fairness constraint or
consideration may have a negative effect on overall economic efficiency. A quantification of this tradeoff is known
as the price of fairness (Bertsimas et al. 2011). Recent work
by Dickerson et al. (2014) adapted this concept to the kidney exchange case, and presented two fair allocation rules
that strike a balance between fairness and efficiency. Yet, as
we show in this paper, those rules can “fail” unpredictably,
yielding an arbitrarily high price of fairness.
With this as motivation, we adapt to the kidney exchange
case a recent technique for trading off a form of fairness and
utilitarianism in a principled manner. This technique is parameterized by a bound on the price of fairness, as opposed
to a set of parameters that may result in hard-to-predict final matching behavior, as in past work. We implement our
rule in a realistic mathematical programming framework
and–on real data from a large, multi-center, fielded kidney
exchange–show that our rule effectively balances fairness
and efficiency without unwanted outlier behavior.

1.1

Related Work

We briefly overview related work in balancing efficiency
and fairness in resource allocation problem. Bertsimas et
al. (2011) define the price of fairness; that is, the relative
loss in system efficiency under a fair allocation rule. Hooker
and Williams (2012) give a formal method for combining
utilitarianism and equity. We direct the reader to those two
papers for a greater overview of research in fairness in general resource allocation problems.
Fairness in the context of kidney exchange was first studied by Roth et al. (2005b); they explore concepts like Lorenz
dominance in a stylized model, and show that preferring fair
allocations can come at great cost. Li et al. (2014) extend
this model and present an algorithm to solve for a Lorenz
dominant matching. Stability in kidney exchange, a concept intimately related to fairness, was explored by Liu et
al. (2014). The use of randomized allocation machanisms to
promote fairness in stylized models is theoretically promising (Fang et al. 2015; Aziz et al. 2016; Mattei et al. 2017).
Recent work discusses fairness in stylized random graph
models of dynamic kidney exchange (Ashlagi et al. 2013;
Anderson et al. 2015). None of these papers provide practi-

cal models that could be implemented in a fully-realistic and
fielded kidney exchange.
Practically speaking, Yılmaz (2011) explores in simulation equity issues from combining living and deceased donor
allocation; that paper is limited to only short length-two kidney swaps, while real exchanges all use longer cycles and
chains. Dickerson et al. (2014) introduced two fairness rules
explicitly in the context of kidney exchange, and proved
bounds on the price of fairness under those rules in a random graph model; we build on that work in this paper, and
describe it in greater detail later. That work has been incorporated into a framework for learning to balance efficiency,
fairness, and dynamism in matching markets (Dickerson and
Sandholm 2015); we note that the fairness rule we present in
this paper could be used in that framework as well.

1.2

Our Contributions

Dickerson et al. (2014) finds that the theoretical price of fairness in kidney exchange is small when only patient-donor
pairs participate in the exchange. They did not include nondirected donors (NDDs). However, in modern kidney exchanges, non-directed donors (NDDs) provide many more
matches than patient-donor pairs; furthermore, NDDs create
more opportunities to expand the fair matching, potentially
increasing the price of fairness. Here, we prove that adding
NDDs to the theoretical model actually decreases the price
of fairness, and that—with enough NDDs—the price of fairness is zero.
Real kidney exchanges are less dense and more uncertain
than the (standard) theoretical model in which we prove our
results. Previous approaches to incorporating fairness into
kidney exchange have neglected this fact: they have been either ad-hoc—e.g., “priority points” decided on by committee (Kidney Paired Donation Work Group 2013)—or brittle (Roth et al. 2005b; Dickerson et al. 2014), resulting in
an unacceptably high price of fairness. This paper provides
the first approach to incorporating fairness into kidney exchange in a way that both prioritizes disadvantaged participants, but also comes with acceptable worst-case guarantees
on the price of fairness. Our method is easily applied as an
objective in the mathematical-programming-based clearing
methods used in today’s fielded exchanges; indeed, using
real data we show that this method guarantees a limit on
efficiency loss.
Section 1.3 introduces the kidney exchange problem. Section 2 extends work by Ashlagi and Roth (2014) and Dickerson et al. (2014), showing that the price of fairness is small
on the canonical random graph model even with NDDs. Section 3 shows that two recent fair allocation rules from the
kidney exchange literature (Dickerson et al. 2014) can perform unacceptably poorly in the worst case. Then, Section 4
presents a new allocation rule that allows policymakers to set
a limit on efficiency loss, while also favoring disadvantaged
patients. Section 5 shows on real data from a large fielded
kidney exchange that our method limits efficiency loss while
still favoring disadvantaged patients when possible.

1.3

Preliminaries

A kidney exchange can be represented as a directed compatibility graph G = (V, E), with vertices V = P ∪N including
both patient donor pairs p ∈ P and non-directed-donors n ∈
N (Roth et al. 2004; Roth et al. 2005a; Roth et al. 2005b;
Abraham et al. 2007). A directed edge e is drawn from vertex vi to vj if the donor at vi can give to the patient at vj .
Fielded kidney exchanges consist mainly of directed cycles
in G, where each patient vertex in the cycle receives the
donor kidney of the previous vertex. Modern exchanges also
include non-cyclic structures called chains (Montgomery et
al. 2006; Rees et al. 2009). Here, an NDD donates her kidney to a patient, whose paired donor donates her kidney to
another patient, and so on.
In practice, cycles are limited in size, or “capped,” to some
small constant L, while chains are limited in size to a much
larger constant R—or not limited at all. This is because
all transplants in a cycle must execute simultaneously; if a
donor whose paired patient had already received a kidney
backed out of the donation, then some participant in the market would be strictly worse off than before. However, chains
need not be executed simultaneously; if a donor backs out after her paired patient receives a kidney, then the chain breaks
but no participant is strictly worse off. We will discuss how
these caps affect fairness and efficiency in the coming sections.
The goal of kidney exchange programs is to find a matching M —a collection of disjoint cycles and chains in the
graph G. The cycles and chains must be disjoint because
no donor can give more than one of her kidneys (although
ongoing work explores multi-donor kidney exchange (Ergin et al. 2017; Farina et al. 2017)). The clearing problem
in kidney exchange is to find a matching M ∗ that maximizes some utility function u : M → R, where M is
the set of all legal matchings. Real kidney exchanges typically optimize
the maximum weighted cycle cover (i.e.,
P forP
u(M ) =
c∈M
e∈c we ). This utilitarian objective can
favor certain classes of patient-donor pairs while disadvantaging others. This is formalized in the following section.

1.4

The Price of Fairness

As an example for this paper, we focus on highly-sensitized
patients, who have a very low probability of their blood passing a feasibility test with a random donor organ; thus, finding
a kidney is often quite hard, and their median waiting time
for an organ jumps by a factor of three over less sensitized
patients.2 Utilitarian objectives will, in general, marginalize
these patients. Sensitization is determined using the Calculated Panel Reactive Antibody (CPRA) level of each patient,
which reflects the likelihood that a patient will find a matching donor.
Formally the sensitization of each patient-donor vertex v
be vs ∈ [0, 100], the CPRA level of v’s patient; NDD vertices are not associated with patients, so they do not have
sensitization levels. Each patient-donor vertex v ∈ P is
considered highly sensitized if vs exceeds threshold τ ∈
2

https://optn.transplant.hrsa.gov/data/

Mf∗ = arg max uf (M )
M ∈M

Bertsimas et al. (2011) defined the price of fairness to be
the “relative system efficiency loss under a fair allocation assuming that a fully efficient allocation is one that maximizes
the sum of [participant] utilities.” Caragiannis et al. (2009)
defined an essentially identical concept in parallel. Formally,
given a fair utility function uf and the utilitarian utility function u, the price of fairness is:


u (M ∗ ) − u Mf∗
(1)
POF(M, uf ) =
u (M ∗ )
The price of fairness POF(M, uf ) is the relative loss in
(utilitarian) efficiency caused by choosing the fair outcome
Mf∗ rather than the most efficient outcome.
In the next section we show that the theoretical price of
fairness in kidney exchange is small, even when both cycles
and chains are used—thus generalizing an earlier result due
to Dickerson et al. (2014) to modern kidney exchanges.

2

The Theoretical Price of Fairness with
Chains is Low (or Zero)

In this section we use the random graph model for kidney exchange introduced by Ashlagi and Roth (2014) to
show that the theoretical price of fairness is always small,
especially when NDDs are included. A complete description of this model can be found in Appendix A.1. Dickerson et al. (2014) finds that without NDDs, the maximum
price of fairness is 2/33. Adding NDDs to this model creates more opportunities to match highly sensitized patients,
which could potentially lead to a higher price of fairness.
However we find that including chains in this model only
decreases the price of fairness; furthermore, when the ratio
of NDDs to patient-donor pairs is high enough, the price of
fairness is zero.

2.1

Price of Fairness

Ashlagi and Roth (2014) characterize efficient matchings
in a random graph model without chains, and Dickerson
et al. (2014) build on this to show that the price of fairness without chains is bounded above by 2/33. Dickerson
et al. (2012) extend the efficient matching of Ashlagi and
Roth (2014) to include chains, but do not calculate the price
of fairness. In this work, we close the remaining gap in theory regarding the price of fairness with chains.

Given |P | patient-donor pairs, we parameterize the number of NDDs |N | with β ≥ 0 such that |N | = β|P |. Theorems 1 and 2 state our two main results: adding chains to the
random graph model does not increase the price of fairness,
and when the fraction of NDDs is high enough (β > 1/8),
the price of fairness is zero. The proofs of the following theorems are given in Appendix A.
Theorem 1. Adding NDDs to the random graph model (β >
0) does not increase the upper bound on the price of fairness
found by Dickerson et al. (2014).
Proof Sketch: We explore every possible efficient matching on the random graph model with chains; only four of
these matchings have nonzero price of fairness. For each
case, we compare the price of fairness to that of the efficient
matching without chains found in Dickerson et al. (2014),
and find that the upper bound does not increase.
Theorem 2. The price of fairness is zero when β > 1/8.
Proof sketch: For each matching with nonzero price of
fairness, β ≤ 1/8. When β > 1/8, a different matching
occurs, and the price of fairness is zero.
0.07
0.06
0.05
0.04
0.03
0.02
0.01
0.00
0.00
■
●

Max PoF

[0, 100], and lowly-sensitized otherwise. These vertex sets
VH and VL are defined as:
• Lowly sensitized: VL = {v | v ∈ P : vs < τ }
• Highly sensitized: VH = {v | v ∈ P : vs ≥ τ }.
By definition, highly-sensitized patients are harder to match
than lowly-sensitized patients. Naturally, efficient matching
algorithms prioritize easy-to-match vertices in VL , marginalizing VH . Let uf : M → R be a fair utility function. Formally, a utility function is fair when its corresponding optimal match Mf∗ is viewed as fair, where Mf∗ is defined as:

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

With chains

●
●
●
●
●
●
●

Without chains

●
●
●
●

●

●

●

●

●

0.02

0.04

0.06

0.08

0.10

0.12

β

Figure 1: Price of fairness with chains. (The horizontal dotted line at 2/33 is the price of fairness without chains.)
To illustrate these results, we compute the price of fairness when β ∈ [0, 1/8]. These calculations confirm our theoretical results, as shown in Figure 2.1: the price of fairness
decreases as β increases, and is zero when β > 1/8.
The worst-case price of fairness is small in the random graph model, with or without NDDs. However, real
exchange graphs are typically much sparser and less
uniform—in reality the price of fairness can be high. In the
next section, we discuss two notions of fairness in kidney
exchange and determine their worst-case price of fairness.

3

The Price of Fairness in State-of-the-Art
Fair Rules can be Arbitrarily Bad

The price of fairness depends on how fairness is defined.
This is especially true in real exchanges where the price of
fairness can be unacceptably high.
In this section, we discuss two kidney-exchange-specific
fairness rules introduced by Dickerson et al. (2014): lexicographic fairness and weighted fairness. These rules favor the
disadvantaged class, or classes, without considering overall

loss in efficiency; we will show in the worst case these rules
allow the the price of fairness to approach 1 (i.e., total efficiency loss). Proofs of these theorems are in Appendix B.

3.1

Lexicographic Fairness

As proposed by Dickerson et al. (2014), α-lexicographic
fairness assigns nonzero utility only to matchings that award
at least a fraction α of the maximum possible fair utility.
Letting uH (M ) and uL (M ) be the utility assigned to only
vertices in VH and VL , respectively, the utility function for
α-lexicographic fairness is given in Equation (2).


uL (M ) + uH (M )

if uH (M ) ≥ α max
uH (M 0 )
uα (M ) =
M 0 ∈M


0
otherwise.

(2)

Theorems 3 and 4 state that strict lexicographic fairness
(α = 1) allows the price of fairness to approach 1.
Theorem 3. For any cycle cap L there exists a graph G
such that the price of fairness of G under α-lexicographic
.
fairness with 0 < α ≤ 1 is bounded by POF(M, uα ) ≥ L−2
L
Theorem 4. For any chain cap R there exists a graph
G such that the price of fairness of G under the αlexicographic fairness rule with 0 < α ≤ 1 is bounded by
.
POF(M, uα ) ≥ R−1
R
Thus, α-lexicographic fairness allows for a price of fairness that approaches 1 as the cycle and chain cap increase.

3.2

Weighted Fairness

The weighted fairness rule (Dickerson et al. 2014) defines a
utility function by first modifying the original edge weights
we by a multiplicative factor γ ∈ R such that
(
(1 + γ)we
0
we =
we

A similar result exists with cycles rather than chains.
Theorem 8. With no cycle cap there exists a graph G such
that the price of fairness of G under the weighted fairness
γ
rule is bounded by POF(M, uW F ) ≥ γ+1
.
These bounds show that weighted fairness allows for a
price of fairness that approaches 1, i.e., arbitrarily bad, as
the cycle cap, chain cap, or γ increase.
We have shown that the worst-case prices of fairness approach 1 under both the lexicographic and weighted fairness
rules of Dickerson et al. (2014). Next, we propose a rule that
favors disadvantaged groups, but also strictly limits the price
of fairness using a parameter set by policymakers.

4

4.1

c∈M

where u0 (c) is the utility of a chain or cycle c with modified
edge weights.
The modified edge weights prompt the matching algorithm to include more highly-sensitized patients; as in the
lexicographic case, we now show that the price of fairness
approaches 1 under weighted fairness.
Theorem 5. For any cycle cap L and γ ≥ L−1, there exists
a graph G such that the price of fairness of G under the
.
weighted fairness rule is bounded by POF(M, uW F ) ≥ L−2
L
Theorem 6. For any chain cap R and γ ≥ R−1, there exists
a graph G such that the price of fairness of G under the
weighted fairness rule is bounded by POF(M, uW F ) ≥ R−1
.
R
In the worst case, weighted fairness allows a price of fairness that approaches 1 as the cycle and chain caps increase.
The price of fairness also approaches 1 as γ increases.
Theorem 7. With no chain cap, there exists a graph G such
that the price of fairness of G under the weighted fairness
γ
rule is bounded by POF(M, uW F ) ≥ γ+1
.

Utilitarian and Rawlsian Fairness

Consider two classes of agents that receive utilities u1 (X)
and u2 (X), respectively, for outcome X. The fairness rule
introduced by Hooker and Williams (2012) maximizes the
utility of the worst-off class, unless this requires taking too
many resources from other classes. When the inequality exceeds a threshold ∆ (i.e., |u1 (X)−u2 (X)| > ∆) they switch
to a utilitarian objective that maximizes u1 (X)+u2 (X). The
utility function for this rule is

if e ends in VH
otherwise.

Then the weighted fairness rule uWF is
X
uW F (M ) =
u0 (c),

Hybrid Fairness Rule

In this section, we present a hybrid fair utility function
that balances lexicographic fairness and a utilitarian objective. We generalize the hybrid utility function proposed
by Hooker and Williams (2012), which chooses between a
Rawlsian (or maximin) objective and a utilitarian objective
for multiple classes of agents.

u∆ (X) =



2 min(u1 (X), u2 (X)) + ∆




if |u1 (X) − u2 (X)| ≤ ∆




u1 (X) + u2 (X)



otherwise.

The parameter ∆ is problem-specific, and should be chosen by policymakers. Figure 2(a) shows the level sets of this
utility function, with ∆ = 2. This utility function can be
generalized by switching to a different fairness rule in the
fair region (i.e. when |u1 (X) − u2 (X)| ≤ ∆). The next
section generalizes this rule using lexicographic fairness.

4.2

Hybrid-Lexicographic Rule

When it is desirable to favor one class of agents g1 over class
g2 , lexicographic fairness favors g1 . We propose a rule that
implements lexicographic fairness only when inequality between groups does not exceed ∆. This rule uses two steps: 1)
determine whether inequality is small enough to use lexicographic fairness 2) choose the optimal outcome. These steps
are outlined below, and formalized in Algorithm 1.
Step 1: Find all outcomes that maximize a hybrid utility function, and determine whether lexicographic fairness
is appropriate.
We use a utility function to identify outcomes that satisfy
either a lexicographic or utilitarian objective. Equation (3)
shows one option for such a utility function, which assigns

10

10

10

8

8

8

XL
XL
XF

XF
u2

4

4

4

2

2

2

0

0
0.0

2.5

5.0

7.5

10.0

0
0.0

u1 (disadvantaged)
(a) Hybrid Rawlsian-Utilitarian

XF

6

u2

6

u2

6

XL

2.5

5.0

7.5

u1 (disadvantaged)
(b) ∆-Lexicographic (u∆1 )

10.0

0.0

2.5

5.0

7.5

10.0

u1 (disadvantaged)
(c) Relaxed ∆-Lexicographic (u∆ )

Figure 2: Level sets for hybrid fair utility functions with ∆ = 2, with example outcomes XL and XF .
strict lexicographic utility (α = 1) according to Equation (2)
in the fair region, and utilitarian utility otherwise.

u∆1 (X) =



u1 (X) + u2 (X) if |u1 (X) − u2 (X)| ≤ ∆



and u1 (X) = max
(u1 (X 0 ))


X 0 ∈X



u1 (X) + u2 (X) if |u1 (X) − u2 (X)| > ∆








0
otherwise.
(3)

where X is the set of all possible outcomes. Figure 2(b)
shows the contours u∆1 . This utility function is clearly too
harsh—it assigns zero utility to outcomes in the fair region
that do not maximize u1 , and its optimal outcomes are not
always Pareto efficient. Consider outcomes XF and XL in
Figure 2(b). XF is in the fair region but does not maximize
u1 , so u∆1 (XF ) = 0; XL is in the utilitarian region but is
less efficient, so u∆1 (XL ) = u(XL ). Under utility function
u∆1 , the less-efficient outcome XL is chosen over XF .
To address this problem we introduce u∆ in Equation (4),
which relaxes u∆1 . For outcomes in the fair region (that is,
with |u1 − u2 | ≤ ∆), utility is assigned proportional to u1 .
As shown in Figure 2(c), the contours of u∆ are continuous.


u1 (X) + u2 (X) − ∆ if u2 (X) − u1 (X) > ∆
u∆ (X) = 2u1 (X)
if |u1 (X) − u2 (X)| ≤ ∆

u (X) + u (X) + ∆ if u (X) − u (X) > ∆
1
2
1
2
(4)

Let XOPT be the set of outcomes that maximize u∆ . If
any outcomes in XOPT are in the utilitarian region , then
any utilitarian-optimal outcome is selected. However, if any
outcomes in XOPT are in the fair region, then Step 2 must
be used. This process is described below, and formalized in
Algorithm 1.
Step 2: If any solution in XOPT is in the fair region, select the lexicographic-optimal solution in the fair region.
The utility function u∆ assigns the same utility to all solutions in the fair region with the same u1 (X), no matter

the value of u2 (X). However, if there exist two outcomes
XA and XB such that u1 (XA ) = u1 (XB ) and u2 (XA ) >
u2 (XB ), then XA is lexicographically preferred to XB .
Algorithm 1 FairMatching
Input: Threshold ∆, matchings M
Output: Fair matching M ∗
MOP T ← arg maxM ∈M u∆ (M )
if |MOP T | > 1 then
Select a matching M ∈ MOP T
if M is in the utilitarian region then
M∗ ← M
else
M1 ← {M 0 ∈ MOP T | u1 (M 0 ) = u1 (M )}
M ∗ ← arg maxM 0 ∈M1 u2 (M 0 )
else
M ∗ ← MOP T

4.3

Hybrid Rule for Several Classes

We now generalize the hybrid-lexicographic fairness rule
to more than two classes. Consider a set P of classes gi ,
i = 1, . . . , |P|. Let there be an ordering  over gi , where
ga  gb indicates that ga should receive higher priority over gb . WLOG, let the preference ordering over gi be
g1  g2  · · ·  gP . Let ui (X) be the utility received by
group i under outcome X. As in the previous section, we
1) use a utility function to determine whether lexicographic
fairness is appropriate, then 2) select either a lexicographicor utilitarian-optimal outcome.
Step 1: To define a utility function, we observe that in
Equation (4), in the utilitarian region a positive offset ∆ is
added if u1 (X) > u2 (X), and a negative offset is added
otherwise. With |P| classes, each solution in the utilitarian
region receives a utility offset of +∆ if u1 (X) > ui (X),
and −∆ otherwise, for each class i = 2, 3, . . . , |P|. As in
the previous section, these offsets ensure continuity in the
utility function, and ensure that at least one of the maximizing outcomes will be Pareto optimal.

5

u∆ (X) =


|P| · u1 (X)





if maxi (ui (X)) − mini (ui (X)) ≤ ∆,

P|P|




u1 (X) + i=2 (ui (X) + sgn(u1 (X) − ui (X))∆)

otherwise
(5)

Step 2: Let XOPT be the set of solutions that maximize
u∆ . If all optimal solutions are in the utilitarian region, any
utilitarian-optimal solution is selected. If any optimal solution is in the fair region, then the lexicographic-optimal solution in the fair region must be selected, subject to the preference ordering g1  g2  · · ·  g|P| .
Algorithm 2 FairMatching for |P| ≥ 2 classes
Input: Threshold ∆, matchings M
Output: Fair matching M ∗
MOP T ← arg maxM ∈M u∆ (M )
if |MOP T | > 1 then
Select a matching M ∈ MOP T
if M in utilitarian region then
M∗ ← M
else
M1 ← {M 0 ∈ MOP T | u1 (M 0 ) = u1 (M )}
for i = 2, . . . , |P| do
Mi ← arg maxM 0 ∈Mi−1 ui (M 0 )
∗
M ← any matching in M|P|
else
M ∗ ← MOP T

4.4

Price of Fairness for the
Hybrid-Lexicographic Rule

Theorem 9 gives a bound on the price of fairness for the
hybrid-lexicographic rule; its proof is given in Appendix B.
Theorem 9. Assume the optimal utilitarian outcome XE receives utility u(XE ) = uE , with most prioritized class g1 ∈
P receiving utility u1 , and Z other classes gi ∈ P such that
.
u1 (XE ) > ui (XE ). Then, POF(M, u∆ ) ≤ 2((|P|−1)−Z)∆
uE

4.5

Hybrid Fairness in Kidney Exchange

The hybrid-lexicographic fairness rule in Equation (4) is
easily applied to kidney exchange, with uH and uL the total utility received by highly-sensitized and lowly-sensitized
patients, respectively,


uL (M ) + uH (M ) − ∆ if uL (M ) − uH (M ) > ∆
u∆ (M ) = 2uH (M )
if |uL (M ) − uH (M )| ≤ ∆

u (M ) + u (M ) + ∆ if u (M ) − u (M ) > ∆
L
H
H
L
(6)

In the following section, we demonstrate the practical effectiveness of the hybrid-lexicographic rule by testing it on
real kidney exchange data.

Experiments

In this section, we compare the behavior of α-lexicographic,
weighted, and hybrid-lexicographic fairness. All code for
these experiemnts are available on GitHub.3 We use each
rule to find the optimal fair outcomes for 314 real kidney exchanges from the United Network for Organ Sharing (UNOS), collected between 2010 and 2016. To solve the
kidney exchange clearing problem (KEP) we use the PICEF
formulation introduced by Dickerson et al. (2016), with cycle cap 3 and various chain caps. In real exchanges, not
all recommended edges in a matching result in successful
transplants. To reflect this uncertainty, we use the concept
of failure-aware kidney exchange introduced in (Dickerson
et al. 2013): all edges in the exchange can fail with probability (1 − p); the matching algorithm maximizes expected
matching weight, considering edge success probability p.

5.1

Procedure

For each UNOS exchange graph G, we use the following
procedure to implement each fairness rule. We repeat the
following procedure for chain caps 0, 3, 10, and 20, and for
edge success probabilities p = 0.1n, with n = 1, 2, . . . , 10.
1. Find the efficient matching ME by solving the to optimality the NP-hard kidney exchange problem (KEP) on G.
2. Find the fair matching MF by solving the KEP on G0 =
(V, E 0 ), where each edge e ∈ E 0 has weight 1 if e ends in
VH and 0 otherwise.
3. Weighted Fairness: Find the γ-fair matching Mγ by
solving the KEP on Gγ = (V, E γ ), where each edge
e ∈ E γ has weight 1 + γ if e ends in VH and 1 otherwise. After finding Mγ , the reported utilities are calculated using edge weights of E and not E 0 . We use weight
parameters γ = 2n, with n = 0, 1, 2, . . . , 10.
4. α-Lexicographic Fairness: Find the α-fair matching Mα
by solving the KEP on G, with the additional constraint
uH (Mα ) ≥ αuH (ME ). We use parameters α = 0.1n,
with n = 0, 1, 2, . . . , 10.
5. Hybrid-Lexicographic Fairness: Find the ∆-fair matching M∆ using the α-fair matchings Mα , and Algorithm 1.
That is, M∆ = FairMatching(∆, Mα ). We use parameters ∆ = 0.1n · u(ME ), with n = 0, 1, 2, . . . , 10.
Throughout this procedure, we calculate the utility of the
efficient matching (uE ) and the fair matching (uF ) for each
UNOS graph, and for each fairness rule—with parameters
α ∈ [0, 1], γ ∈ [0, 20], and ∆ ∈ [0, u(ME )].
There are two important outcomes of each fairness rule:
Price of Fairness (PoF), and fraction of the fair score (%F ).
To calculate PoF we use the definition in Equation (1), using
uE and uF . We define %F as the fraction of the maximum
highly sensitized utility, achieved by M{α,γ,∆} , defined as
%F (M{α,γ,∆} , MF ) = uH (M{α,γ,∆} )/uH (MF ).
PoF and %F indicate the efficiency loss and the fairness of
each rule, respectively.
3

https://github.com/duncanmcelfresh/FairKidneyExchange

Max. PoF

Chain cap = 0

Chain cap = 3

Chain cap = 20
weighted
α-lex.
hybrid-lex.

0.5

Min. % F

0.0

0.5
0.0
0.1

0.5
Edge success prob.

1.0

0.1

0.5
Edge success prob.

1.0

0.1

0.5
Edge success prob.

1.0

Figure 3: Worst-case price of fairness and %F for various edge success probabilities, and fairness parameters α = 0.1, γ = 0.1,
∆ = 0.1u(ME ).

5.2

Results and Discussion

Each fairness rule offers a parameter that balances efficiency
and fairness. Two of these rules guarantee a certain outcome:
α-lexicographic guarantees fairness, but allows high efficiency loss, while hybrid-lexicographic bounds overall efficiency loss. Weighted fairness makes no guarantees.
The price of fairness can be high in real exchanges, especially when edge success probability p is small. In failureaware kidney exchange, cycles and chains of length k receive utility proportional to pk . Fair matchings often use
longer cycles and chains than the efficient matching, in order
to reach highly sensitized patients; this leads to a high price
of fairness when p is small.
Even when α and γ are small, there are cases when both
α-lexicographic and weighted fairness allow for a high PoF.
This becomes worse with lower edge probability. Figure 3
shows the worst-case PoF and %F for each rule, for the
smallest parameters tested, for a range of edge success probabilities. Appendix C contains results for all parameter values tested.
Hybrid-lexicographic fairness limits PoF within the guaranteed bound of 0.2; this comes at the cost of a low
%F —when edge success probability is small, hybridlexicographic fairness awards zero fair utility in the worst
case. α-lexicographic fairness produces the opposite behavior: %F is always larger than the guaranteed bound of 0.1,
but the worst-case price of fairness grows steadily as edge
probability decreases.
Theory suggests that the price of fairness is small on
denser random graphs (see Section 2). We empirically confirm this theoretical finding by calculating the worst-case
price of fairness and %F for random graphs of various sizes
generated from real data; these results are given in Section C. In this case—when the price of fairness is small—
α-lexicographic fairness may be appropriate, as overall efficiency loss is not severe.
Both α-lexicographic and hybrid-lexicographic fairness

are useful, depending on the desired outcome. Policymakers may choose between these rules, and set the parameters
α and ∆ to guarantee either a minimum %F or a maximum
price of fairness.

6

Conclusion

We addressed the classical problem of balancing fairness
and efficiency in resource allocation, with a specific focus
on the kidney exchange application area. Extending work
by Ashlagi and Roth (2014) and Dickerson et al. (2014), we
show that the theoretical price of fairness is small on a random graph model of kidney exchange, when both cycles and
chains are used. However this model is too optimistic—real
kidney exchanges are less certain and more sparse, and in
reality the price of fairness can be unacceptably high.
Drawing on work by Hooker and Williams (2012), which
is not applicable to kidney exchange, we provided the first
approach to incorporating fairness into kidney exchange in
a way that prioritizes marginalized participants, but also
comes with acceptable worst-case guarantees on overall efficiency loss. Furthermore, our method is easily applied as an
objective in the mathematical-programming-based clearing
methods used in today’s fielded exchanges. Using data from
a large fielded kidney exchange, we showed that our method
bounds efficiency loss while also prioritizing marginalized
participants when possible.
Moving forward, it would be of theoretical and practical interest to address fairness in a realistic dynamic model
of a matching market like kidney exchange (Anshelevich
et al. 2013; Akbarpour et al. 2014; Anderson et al. 2015;
Dickerson and Sandholm 2015). For example, how does prioritizing a class of patients in the present affect their, or
other groups’, long-term welfare? Similarly, exploring the
effect on long-term efficiency of the single-shot ∆ we use in
this paper would be of practical importance; to start, ∆ can
be viewed as a hyperparameter to be tuned (Thornton et al.
2013).

References
[Abraham et al. 2007] David Abraham, Avrim Blum, and
Tuomas Sandholm. Clearing algorithms for barter exchange
markets: Enabling nationwide kidney exchanges. In Proceedings of the ACM Conference on Electronic Commerce
(EC), pages 295–304, 2007.
[Akbarpour et al. 2014] Mohammad Akbarpour, Shengwu
Li, and Shayan Oveis Gharan. Dynamic matching market
design. In Proceedings of the ACM Conference on Economics and Computation (EC), page 355, 2014.
[Anderson et al. 2015] Ross Anderson, Itai Ashlagi, David
Gamarnik, and Yash Kanoria. A dynamic model of barter
exchange. In Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 1925–1933, 2015.
[Anshelevich et al. 2013] Elliot
Anshelevich,
Meenal
Chhabra, Sanmay Das, and Matthew Gerrior. On the social
welfare of mechanisms for repeated batch matching. In
AAAI Conference on Artificial Intelligence (AAAI), pages
60–66, 2013.
[Ashlagi and Roth 2014] Itai Ashlagi and Alvin E Roth. Free
riding and participation in large scale, multi-hospital kidney
exchange. Theoretical Economics, 9(3):817–863, 2014.
[Ashlagi et al. 2013] Itai Ashlagi, Patrick Jaillet, and
Vahideh H. Manshadi. Kidney exchange in dynamic sparse
heterogenous pools. In Proceedings of the ACM Conference
on Electronic Commerce (EC), pages 25–26, 2013.
[Aziz et al. 2016] Haris Aziz, Aris Filos-Ratsikas, Jiashu
Chen, Simon Mackenzie, and Nicholas Mattei. Egalitarianism of random assignment mechanisms. In International
Conference on Autonomous Agents and Multi-Agent Systems
(AAMAS), 2016.
[Bertsimas et al. 2011] Dimitris Bertsimas, Vivek F Farias,
and Nikolaos Trichakis. The price of fairness. Operations
Research, 59(1):17–31, 2011.
[Caragiannis et al. 2009] Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, and Maria Kyropoulou.
The efficiency of fair division. International Workshop on
Internet and Network Economics (WINE), 2009.
[Dickerson and Sandholm 2015] John P. Dickerson and Tuomas Sandholm. FutureMatch: Combining human value
judgments and machine learning to match in dynamic environments. In AAAI Conference on Artificial Intelligence
(AAAI), pages 622–628, 2015.
[Dickerson et al. 2012] John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm. Optimizing kidney exchange
with transplant chains: Theory and reality. In International
Conference on Autonomous Agents and Multi-Agent Systems
(AAMAS), pages 711–718, 2012.
[Dickerson et al. 2013] John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm. Failure-aware kidney exchange.
In Proceedings of the ACM Conference on Electronic Commerce (EC), pages 323–340, 2013.
[Dickerson et al. 2014] John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm. Price of fairness in kidney
exchange. In International Conference on Autonomous

Agents and Multi-Agent Systems (AAMAS), pages 1013–
1020, 2014.
[Dickerson et al. 2016] John P. Dickerson, David Manlove,
Benjamin Plaut, Tuomas Sandholm, and James Trimble.
Position-indexed formulations for kidney exchange. In Proceedings of the ACM Conference on Economics and Computation (EC), 2016.
[Ergin et al. 2017] Haluk Ergin, Tayfun Sönmez, and
M Utku Ünver.
Multi-donor organ exchange, 2017.
Working paper.
[Fang et al. 2015] Wenyi Fang, Aris Filos-Ratsikas, Søren
Kristoffer Stiil Frederiksen, Pingzhong Tang, and Song Zuo.
Randomized assignments for barter exchanges: Fairness vs.
efficiency. In International Conference on Algorithmic Decision Theory (ADT), 2015.
[Farina et al. 2017] Gabriele Farina, John P. Dickerson, and
Tuomas Sandholm. Operation frames and clubs in kidney
exchange. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2017.
[Hart et al. 2016] A. Hart, J. M. Smith, M. A. Skeans, S. K.
Gustafson, D. E. Stewart, W. S. Cherikh, J. L. Wainright,
G. Boyle, J. J. Snyder, B. L. Kasiske, and A. K. Israni. Kidney. American Journal of Transplantation (Special Issue:
OPTN/SRTR Annual Data Report 2014), 16, Issue Supplement S2:11–46, 2016.
[Hooker and Williams 2012] John N Hooker and H Paul
Williams.
Combining equity and utilitarianism in a
mathematical programming model. Management Science,
58(9):1682–1693, 2012.
[Kidney Paired Donation Work Group 2013] Kidney Paired
Donation Work Group. OPTN KPD pilot program cumulative match report (CMR) for KPD match runs: Oct 27, 2010
– Apr 15, 2013, 2013.
[Li et al. 2014] Jian Li, Yicheng Liu, Lingxiao Huang, and
Pingzhong Tang. Egalitarian pairwise kidney exchange: Fast
algorithms via linear programming and parametric flow. In
International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 445–452, 2014.
[Liu et al. 2014] Yicheng Liu, Pingzhong Tang, and Wenyi
Fang. Internally stable matchings and exchanges. In AAAI
Conference on Artificial Intelligence (AAAI), pages 1433–
1439, 2014.
[Mattei et al. 2017] Nicholas Mattei, Abdallah Saffidine, and
Toby Walsh. Mechanisms for online organ matching. In Proceedings of the International Joint Conference on Artificial
Intelligence (IJCAI), 2017.
[Montgomery et al. 2006] Robert Montgomery, Sommer
Gentry, William H Marks, Daniel S Warren, Janet Hiller,
Julie Houp, Andrea A Zachary, J Keith Melancon, Warren R
Maley, Hamid Rabb, Christopher Simpkins, and Dorry L
Segev. Domino paired kidney donation: a strategy to
make best use of live non-directed donation. The Lancet,
368(9533):419–421, 2006.
[Neuen et al. 2013] Brendon L Neuen, Georgina E Taylor,
Alessandro R Demaio, and Vlado Perkovic. Global kidney
disease. The Lancet, 382(9900):1243, 2013.

[Rapaport 1986] F. T. Rapaport. The case for a living emotionally related international kidney donor exchange registry. Transplantation Proceedings, 18:5–9, 1986.
[Rees et al. 2009] Michael Rees, Jonathan Kopke, Ronald
Pelletier, Dorry Segev, Matthew Rutter, Alfredo Fabrega,
Jeffrey Rogers, Oleh Pankewycz, Janet Hiller, Alvin Roth,
Tuomas Sandholm, Utku Ünver, and Robert Montgomery.
A nonsimultaneous, extended, altruistic-donor chain. New
England Journal of Medicine, 360(11):1096–1101, 2009.
[Roth et al. 2004] Alvin Roth, Tayfun Sönmez, and Utku
Ünver. Kidney exchange. Quarterly Journal of Economics,
119(2):457–488, 2004.
[Roth et al. 2005a] Alvin Roth, Tayfun Sönmez, and Utku
Ünver. A kidney exchange clearinghouse in New England.
American Economic Review, 95(2):376–380, 2005.
[Roth et al. 2005b] Alvin Roth, Tayfun Sönmez, and Utku
Ünver. Pairwise kidney exchange. Journal of Economic
Theory, 125(2):151–188, 2005.
[Thornton et al. 2013] Chris Thornton, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms. In International Conference on Knowledge Discovery and Data Mining (KDD), pages 847–855.
ACM, 2013.
[Yılmaz 2011] Özgür Yılmaz.
Kidney exchange: An
egalitarian mechanism.
Journal of Economic Theory,
146(2):592–618, 2011.

A

Price of Fairness in the Random Graph
Model

Ashlagi and Roth (2014) characterize efficient matchings
in a random graph model without chains, and Dickerson
et al. (2014) build on this to show that the price of fairness without chains is bounded above by 2/33. Dickerson
et al. (2012) extend the efficient matching of Ashlagi and
Roth (2014) to include chains, but do not calculate the price
of fairness. We close the remaining theory gap regarding the
price of fairness with chains. Appendix A.1 describes the
random graph model, and Appendix A.2 presents the theoretical price of fairness with chains.

A.1

Random Graph Model

Let all patient-donor pairs P be partitioned into subsets
V X-Y for each patient blood type X and donor blood type
Y . These subsets will be further partitioned into lowly- and
highly sensitized pairs VLX-Y and VHX-Y . Let µX be the fraction of both patients and donors of each blood type X.
Let N X be the set of NDDs of blood type X. Let β|P |
be the total number of NDDs, with the same blood type
distribution as patients. That is, |N X | = βµX |P |, with
X ∈ {A, B, AB, O}.
Patient-donor vertices may be blood-type compatible, but
will not be connected by a directed edge due to tissuetype incompatibility. Let p̄ be the fraction of patientdonor pairs that are blood-type-compatible, but tissue-typeincompatible.
We refer to certain blood-type vertex subsets of as follows:
1. V A-B and V B-A : reciprocal pairs
2. V X-X : self-demanded pairs
3. V

AB-B

,V

AB-A

,V

AB-O

,V

A-O

,V

B-O

: over-demanded pairs

4. V A-AB , V B-AB , V O-A , V O-B , V O-AB : under-demanded pairs
To reflect real-world exchanges, assume p̄ > 1 − λ,
µO > µA > µB > µAB , and p̄ < 2/5. WLOG, let
|V A-B | > |V B-A |, and assume that the absolute difference
between these pools grows sublinearly with the size of the
exchange, that is |V A-B | − |V B-A | = o(n).

A.2

The Price of Fairness With Chains

We calculate the price of fairness in this model by exploring
all of the possible ways that the efficient matching can proceed, which depends on β. We state without proof that there
are only four possible matchings with nonzero price of fairness, and several matchings with zero price of fairness. It is
tedious, but straightforward, to confirm this statement, using
the assumptions made while constructing these matchings.
Figure 4 shows each possible matching on this model, and
some of the impossible matchings.
Propositions 2, 3, 4, and 5 give the price of fairness for
each of the four matchings with nonzero price of fairness;
for each of these cases, β < µAB (1 − p̄). Proposition 1 states
that the price of fairness is zero when β > µAB (1 − p̄).

In all of these matchings, the price of fairness is bounded
above by the price of fairness without NDDs, found by Dickerson et al. (2014); Theorem 1 states this finding, which uses
by Lemmas 2 and 3.
Theorem 2 states that the price of fairness is zero when
β > 1/8, and Lemmas 4, 5, 6, and 7 give bounds on β for
each matching with nonzero price of fairness.
We start with the efficient matching proposed in (Dickerson et al. 2012) using cycles and chains up to length 3. This
matching may proceed in many different ways, depending
on β. However, most outcomes are impossible based on the
canonical assumptions for the random graph model. Figure
4 shows all possible ways that the matching can proceed.
Lemma 1 states that even without chains, all highlysensitized patients except for those in V O-AB are matched in
the efficient matching, only using cycles; this Lemma will
be used in all following propositions.
Lemma 1. Denote by M the set of matchings in G(n)
using cycles and chains up to length 3. As n → ∞, a.s. all
highly sensitized pairs can be matched with no efficiency
loss under the lexicographic fairness rule, except for those
of type O-AB.
(This Lemma uses the same efficient matching introduced
by Dickerson (Dickerson et al. 2012).)
sketch. Begin with the efficient matching M ∗ using only
cycles up to length 3, proposed by Dickerson in (Dickerson et al. 2014). M ∗ matches all over-demanded and selfdemanded vertices with high probability, but leaves some
under-demanded vertices unmatched. We proceed through
the initial steps of matching M ∗ to show that all vertices in
VHO-A , VHO-B , VHA-AB , and VHB-AB are matched.
1. Match all vertices in V B-A in 2-cycles with V A-B , exhausting V B-A and leaving |V A-B | ∝ o(n).
2. Match all remaining vertices in V A-B in 3-cycles with
V B-O and V O-A . There are only |V A-B | ∝ o(n) of these
cycles, which will become negligible to the price of fairness as n → ∞.
3. Match all remaining vertices in V A-O in 2-cycles with
V O-A . Note that |V A-O | ∝ p̄µA µO and |V O-A | ∝ µA µO .
The V A-O vertices are exhausted first if |V A-O | < |V O-A |,
which holds almost surely because p̄µA µO < µA µO due
to the assumption p̄ < 2/5. All highly sensitized vertices
VHO-A are matched because (1 − λ)µA µO < p̄µA µO holds
under the assumption 1 − λ < p̄. Thus both V A-O and
VHO-A are exhausted, and |V O-A | ∝ µA µO (1 − p̄).
4. Match all remaining vertices in V B-O in 2-cycles with
V O-B . Note that |V B-O | ∝ p̄µB µO and |V O-B | ∝ µB µO .
As before, the a.s. |V O-B | > |V B-O |. All highly sensitized
vertices VHO-B are matched a.s., because p̄µB µO > (1 −
λ)µB µO holds under the assumption p̄ > 1−λ. Thus both
V B-O and VHO-B are exhausted, and |V O-B | ∝ µB µO (1−p̄).
5. Match all vertices in V AB-A in 2-cycles with V A-AB .
Note that, |V AB-A | ∝ p̄µA µAB and |V A-AB | ∝ µA µAB .
As before, a.s. |V A-AB | > |V A-AB |. All highly sensitized vertices VHA-AB are matched, because p̄µA µAB >

1

A and B NDDs donate to A-AB and B-AB

2

3-cycles (AB-O, O-A, A-AB)

(A-AB and B-AB are exhausted)
PoF = 0

(A and B NDDs exhausted)

(O-A is exhausted)
impossible

(AB-O is exhausted)

(A-AB exhausted)

(O-B is exhausted)
impossible

3

3-cycles (AB-O, O-B, B-AB)

4

3-chains (O,O-A,A-AB)

(O exhausted first)

5

3-chains (O,O-B,B-AB)

None exist

6

O and AB-O match with
underdemanded pairs

None exist

None exist

Price of Fairness

PoF > 0
(Prop. 2)

PoF > 0
(Prop. 3)

None exist

(AB-O exhausted)

None exist (A-AB = ∅)

(O-B is exhausted)
impossible

(O exhausted)

(B-AB exhausted)

None exist (A-AB = ∅)

(B-AB exhausted)

(B-AB exhausted)

All (O-AB)H
matched

Some (O-AB)H
matched

PoF=0

PoF > 0
(Prop. 4)

All (O-AB)H
matched

PoF = 0

Some (O-AB)H
matched

PoF > 0
(Prop. 5)

Figure 4: All possible matchings on the random graph model. Boxes with blue borders represent the matching outcomes, and
boxes with black borders represent intermediate steps in each matching. Some of the impossible matchings are shown as boxes
with dashed black borders.
(1 − λ)µA µAB under the assumption p̄ > 1 − λ. Thus
both V AB-A and VHA-AB are exhausted, and |V A-AB | ∝
µA µO (1 − p̄).
6. Match all vertices in V AB-B in 2-cycles with V B-AB . Note
that, |V AB-B | ∝ p̄µB µAB and |V B-AB | ∝ µB µAB , and a.s.
|V B-AB | > |V AB-B |. All highly sensitized vertices VHB-AB
are matched, because p̄µB µAB > (1 − λ)µB µAB under
the assumption p̄ > 1 − λ. Thus both V AB-B and VHB-AB
are exhausted, and |V B-AB | ∝ µB µO (1 − p̄).
Thus, these initial steps of matching M ∗ exhaust all
highly sensitized pairs in VHO-A , VHO-B , VHA-AB , and VHB-AB .
With uniform edge weights, lexicographic fairness requires that we match the maximum possible number of
highly sensitized vertices. Lemma 1 states that the efficient
matching M ∗ includes all highly sensitized patients, except
for those in V O-AB . Therefore all efficiency loss–and price
of fairness–is caused by matching vertices in VHO-AB .
Using both chains and cycles increases overall efficiency.
In the dense graph model used in this Appendix, adding
chains can only decrease the price of fairness.
Proposition 1 in (Dickerson et al. 2014) states that with
only cycles up to length 3, and assuming p̄ > 1 − λ, and
µO < 3µA /2, and µO > µA > µB > µAB , the price of

2
fairness is at most 33
. In the dense graph model used here,
adding chains tightens this upper bound.
The following propositions tighten the upper bound on the
price of fairness, for every possible value of β.

Proposition 1. Assume
1 β > (1 − p̄)µAB .
Denote by M the set of matchings in G(n) using cycles and chains up to length 3. As n → ∞, almost surely
POF(M, uLEX ) = 0.
sketch. We begin by executing the initial steps of matching
M ∗ as done in the proof of Lemma 1, matching all highly
sensitized vertices except for those in VHO-AB . The following
steps continue the matching M ∗ from Lemma 1.
7. A- and B-type NDDs donate to V A-AB and V B-AB , respectively. Note that |N A | ∝ βµA and |V A-AB | ∝
(1 − p̄)µA µAB . Assuming β > (1 − p̄)µAB , the inequality βµA > µA µAB (1 − p̄) holds and a.s. |N A | >
|V A-AB |. By the same argument, a.s. |N B | > |V B-AB |.
Thus, both V A-AB and V B-AB are exhausted, and |N B | ∝
µB (β − (1 − p̄)µAB ) and |N A | ∝ µA (β − (1 − p̄)µAB ).
8. Create cycles of the form (AB-O, O-X, X-AB), with X ∈
{A, B}. None of these cycles occur because both V A-AB
and V B-AB have been exhausted in previous steps.

9. Create chains of the form (O,O-X,X-AB), with X ∈
{A, B}. None of these cycles occur, because both V A-AB
and V B-AB have been exhausted in previous steps.
10. Remaining O-type NDDs donate to remaining underdemanded vertices, beginning with V O-AB . Note that
no O-type NDDs have been used in previous steps, so
|N O | ∝ βµO .
11. 2-cycles are created with V AB-O and remaining underdemanded vertices, beginning with V O-AB . Note that no
vertices in V AB-O have been used in previous steps, so
|V AB-O | ∝ p̄µO µAB .
The final two steps match up to |V AB-O | + |N O | ∝ βµO +
p̄µO µAB vertices in V O-AB . The only remaining highly|
sensitized vertices are in VH OAB ∝ (1 − λ)µO µAB . Assuming that p̄ > 1 − λ, the inequality βµO + p̄µO µAB >
p̄µO µAB > (1 − λ)µO µAB holds, and a.s. |V AB-O | + |N O | >
|
|VH OAB|. This exhausts all vertices in |VHO-AB |. All other
highly-sensitized vertices were matched in steps 1-6 of, as
in Lemma 1. Thus, all highly sensitized vertices can be
matched with no efficiency loss, and the price of fairness
is zero.
Proposition1 assumes that β is extremely large, specifically β > 1/4 > (1 − p̄)µAB . In practice, β < 0.01 – that is,
the number of NDDs in an exchange is often less than 1% of
the size of the exchange. The following Propositions address
the price of fairness when β < (1 − p̄)µAB < 1/4.
Proposition 2. Assume
A.1 β < µA (1 − p̄) − p̄µAB
A.2 β < µAB (1 − p̄) − p̄µAB µO /µA


A
−
p̄
A.3 β < µAB µAµ+µ
O
These constraints imply β ∈ [0, 1/8].Denote by M the set
of matchings in G(n) using cycles and chains up to length
3. Almost surely as n → ∞, the price of fairness is
POF(M, uLEX ) =

(1 − λ)µO µAB
uE

with
h
uE = p̄ 2µAB µB + 2µAB µA + 3µAB µO
+2µA µO + 2µB µO + µ2O + µ2A + µ2B + µ2AB

i

+2µA µB + β (µA + µB + 2µO )
sketch. We begin with matching M ∗ as done in the proof
of Lemma 1, matching all highly sensitized vertices except
for those in VHAB-O . We now complete the efficient matching using both 3-cycles and 3-chains as in (Dickerson et al.
2012).
7. A- and B-type NDDs donate to V A-AB and V B-AB , respectively. Note that |N A | ∝ βµA and |V A-AB | ∝ (1 −
p̄)µA µAB . The inequality βµA < µA µAB (1− p̄) holds due

to assumption A.2, and a.s. |N A | < |V A-AB |. By the same
argument, a.s. |N B | < |V B-AB |. Thus, both N A and N B
are exhausted, and |V A-AB | ∝ µA µAB (1 − p̄) − βµA and
|V B-AB | ∝ µB µAB (1 − p̄) − βµB .
8. Create cycles of the form (AB-O, O-A, A-AB). The current size of each vertex group is
(1) |V AB-O | ∝ p̄µAB µO
(2) |V O-A | ∝ (1 − p̄)µA µO
(3) |V A-AB | ∝ µA µAB (1 − p̄) − βµA
The inequality (1) < (2) holds due to the model assumptions, so a.s. |V AB-O | < |V O-A |. Note that the inequality
(1) < (3) can be written as
β < µAB (1 − p̄) − p̄µAB µO /µA
which holds by assumptions A.2, and a.s. |V AB-O | <
|V A-AB |. Executing these cycles exhausts V AB-O and
leaves the following vertices remaining
(1) |V O-A | ∝ (1 − p̄)µA µO − p̄µAB µO .
(2) |V A-AB | ∝ (1 − p̄)µA µAB − p̄µAB µO − βµA
9. Create cycles of the form (AB-O, O-B, B-AB). The previous step exhausted V AB-O , so none of these cycles occur.
10. Create chains of the form (O,O-A,A-AB). The current
size of each vertex group is
(1) |N O | ∝ βµO
(2) |V O-A | ∝ (1 − p̄)µA µO − p̄µAB µO
(3) |V A-AB | ∝ (1 − p̄)µA µAB − p̄µAB µO − βµA
The inequality (1) < (2) holds due to assumption A.1, so
a.s. |N O | < |V O-A |. Note that inequality (1) < (3) can be
written as


µA
β < µAB
− p̄
µA + µO
which holds due to A.3. Thus a.s. |N O | < |V A-AB |,
and |N O | is exhausted. The vertices unmatched by these
chains are
(1) |V O-A | ∝ (1 − p̄)µA µO − p̄µAB µO − βµO
(2) |V A-AB | ∝ (1 − p̄)µA µAB − p̄µAB µO − β (µA + µO )
11. Remaining O-type NDDs donate to remaining underdemanded vertices. The previous step exhausted N O , so
none of these donations occur.
12. 2-cycles are created with V AB-O and remaining underdemanded vertices. The previous step exhausted V AB-O ,
so none of these cycles occur.
In the efficient matching described above, the number of
matched pairs in each under-demanded group is
|V O-A | ∝ µO (β + p̄ (µA + µAB ))
|V O-B | ∝ p̄µB µO
|V A-AB | ∝ (β + p̄µAB )(µA + µO )
|V B-AB | ∝ (β + p̄µAB )µB
|V O-AB | = 0

Combining these with the over-demanded and selfdemanded vertices, the total size of the efficient matching
is
h
uE = p̄ 2µAB µB + 2µAB µA + 3µAB µO
+2µA µO + 2µB µO + µ2O + µ2A + µ2B + µ2AB

i

+2µA µB + β (µA + µB + 2µO )
This efficient matching includes all highly sensitized vertices except for those in VHO-AB . To calculate the price of fairness we now find the size of the fair matching. We match
each vertex in VHO-AB by removing a 3-cycle of the form
(AB-O, O-A, A-AB) and creating a 2-cycle (AB-O, O-AB).
This matching used |V AB-O | ∝ p̄µO µAB 3-cycles of this
form, while |VHO-AB | ∝ (1 − λ)µO µAB . The model assumption p̄ > 1 − λ ensures that |V AB-O | > |VHO-AB |, and all
vertices in VHO-AB can be matched in this way.
To match each vertex in VHO-AB , we remove from the
matching one vertex from both V O-A and V A-AB . Thus the
total efficiency loss is |VHO-AB | ∝ (1 − λ)µO µAB . The price
of fairness is
POF(M, uLEX ) =

(1 − λ)µO µAB
uE

µA µAB (1−p̄)+µB µO (1−p̄)−p̄µO µAB
µA +µO

3 β > µAB (1 − p̄) − µAB µO p̄/µA
4 β < µAB (1 − p̄) − p̄µAB µO /µA + (1 − p̄)µB µO /µA
5 β < µAB (1 − p̄) − µO µAB /(1 − µAB )
Note that as written, constraint 4 is a looser bound than
5, and can be removed. However it is convenient to leave 4
for clarity. These constraints imply β ∈ [0, 1/12]. Denote by
M the set of matchings in G(n) using cycles and chains up
to length 3. Almost surely as n → ∞, the price of fairness is

β > µAB (1 − p̄) − p̄µAB µO /µA
which holds by assumption 3, and a.s. |V A-AB | < |V AB-O |.
The inequality (3) < (2) can be written as
β > (1 − p̄)(µAB − µO )
which holds by model assumptions, and a.s. |V A-AB | <
|V O-A |. Executing these cycles exhausts V A-AB and leaves
the following vertices remaining

(1) |V AB-O | ∝ p̄µAB µO − µA µAB (1 − p̄) + µA β
(2) |V O-B | ∝ (1 − p̄)µB µO
(3) |V B-AB | ∝ µB µAB (1 − p̄) − βµB
Inequality (1) < (2) can be written as
β < µAB (1 − p̄) − p̄µAB µO /µA + (1 − p̄)µB µO /µA
which holds by assumption 4. Inequality (1) < (3) can be
written as
β < µAB (1 − p̄) − µAB µO p̄/(µA + µB )

(1 − λ)µO µAB
uE

which holds by assumption 1.
Executing these cycles exhausts V AB-O and leaves the following vertices remaining

with

|V O-B | ∝ µA µAB (1− p̄)+(µB − p̄(µAB +µB ))µO −βµA
|V B-AB | ∝ ((1 − p̄)µAB − β) (µA + µB ) − p̄µAB µO

h
uE = p̄ 2µAB µB + 2µAB µA + 3µAB µO
+2µA µO + 2µB µO + µ2O + µ2A + µ2B + µ2AB

Note that the inequality (3) < (1) can be written as

9. Create cycles of the form (AB-O, O-B, B-AB). The current size of each vertex group is

Proposition 3. Assume
1 β < µAB (1 − p̄) − µAB µO p̄/(µA + µB )

POF(M, uLEX ) =

(1) |V AB-O | ∝ p̄µAB µO
(2) |V O-A | ∝ (1 − p̄)µA µO
(3) |V A-AB | ∝ µA µAB (1 − p̄) − βµA

|V O-A | ∝ (1 − p̄)µA (µO − µAB ) + µA β
|V AB-O | ∝ p̄µAB µO − µA µAB (1 − p̄) + µA β

With uE defined previously.

2 β<

7. A- and B-type NDDs donate to V A-AB and V B-AB , respectively. Note that |N A | ∝ βµA and |V A-AB | ∝ (1 −
p̄)µA µAB . The inequality βµA < µA µAB (1− p̄) holds due
to assumption A.1, and a.s. |N A | < |V A-AB |. By the same
argument, a.s. |N B | < |V B-AB |. Thus, both N A and N B
are exhausted, and |V A-AB | ∝ µA µAB (1 − p̄) − βµA and
|V B-AB | ∝ µB µAB (1 − p̄) − βµB .
8. Create cycles of the form (AB-O, O-A, A-AB). The current size of each vertex group is

i

+2µA µB + β (µA + µB + 2µO )
sketch. We begin with matching M ∗ as done in the proof
of Lemma 1, matching all highly sensitized vertices except
for those in VHAB-O . We now complete the efficient matching using both 3-cycles and 3-chains as in (Dickerson et al.
2012).

10. Create chains of the form (O,O-A,A-AB). Previous steps
exhausted V A-AB so none of these chains occur.
11. Create chains of the form (O,O-B,B-AB). The current size
of each vertex group is
(1) |N O | ∝ βµO
(2) |V O-B | ∝ µA µAB (1− p̄)+(µB − p̄(µAB +µB ))µO −βµA
(3) |V B-AB | ∝ ((1 − p̄)µAB − β) (µA + µB ) − p̄µAB µO

total efficiency loss is |VHO-AB | ∝ (1 − λ)µO µAB . The price
of fairness is

The inequality (1) < (2) can be written as
β<

µA µAB (1 − p̄) + µB µO (1 − p̄) − p̄µO µAB
µA + µO

which holds by assumption 2. The inequality (1) < (3)
can be written as
β < µAB (1 − p̄) − µO µAB /(1 − µAB )
which holds by assumption 5. Executing these chains exhausts N O and leaves the following vertices remaining
|V O-B | ∝ µA µAB (1 − p̄) + (µB − p̄(µAB + µB ))µO
− β(µA + µO )
|V B-AB | ∝ (1 − p̄)µAB − β)(µA + µB ) − (β + p̄µAB )µO
12. Remaining O-type NDDs donate to remaining underdemanded vertices. The previous step exhausted N O , so
none of these donations occur.
13. 2-cycles are created with V AB-O and remaining underdemanded vertices. The previous steps exhausted V AB-O ,
so none of these cycles occur.
In the efficient matching described above, the number of
matched pairs in each under-demanded group is
|V O-A | ∝ (1 − p̄)µA (µO − µAB ) + µA β
|V O-B | ∝ µA µAB (1 − p̄) + (µB − p̄(µAB + µB ))µO
− β(µA + µO )
|V A-AB | = 0
|V B-AB | ∝ (1 − p̄)µAB − β)(µA + µB ) − (β + p̄µAB )µO
|V O-AB | = 0
Combining these with the over-demanded and selfdemanded vertices, the total size of the efficient matching
is
h
uE = p̄ 2µAB µB + 2µAB µA + 3µAB µO
+2µA µO + 2µB µO + µ2O + µ2A + µ2B + µ2AB

i

+2µA µB + β (µA + µB + 2µO )
This efficient matching includes all highly sensitized vertices except for those in VHO-AB . To calculate the price of fairness we now find the size of the fair matching. We match
each vertex in VHO-AB by removing a 3-cycle of the form
(AB-O, O-A, A-AB) and creating a 2-cycle (AB-O, O-AB).
This matching used |V AB-O | ∝ p̄µO µAB 3-cycles of this
form, while |VHO-AB | ∝ (1 − λ)µO µAB . The model assumptions ensure that |V AB-O | > |VHO-AB |, and all vertices in
VHO-AB can be matched in this way.
To match each vertex in VHO-AB , we remove from the
matching one vertex from both V O-A and V A-AB . Thus the

POF(M, uLEX ) =

(1 − λ)µO µAB
uE

With uE defined previously.
Proposition 4. Assume
1 β > µAB (1 − p̄) − µAB µO p̄/µA
2 β < µAB (1 − p̄) − µAB µO p̄/(µA + µB )
3 β < µAB (1 − p̄) − p̄µAB µO /µA + (1 − p̄)µB µO /µA


µO
4 β > µAB (1 − p̄) − 1−µ
AB
µAB
5 β < µAB (1 − p̄) − λµO 1−µ
AB

These constraints imply β ∈ [0, 1/8]. Denote by M the
set of matchings in G(n) using cycles and chains up to
length 3. Almost surely as n → ∞, the price of fairness
is
POF(M, uLEX ) =

(1 − µAB )((1 − p̄)µAB − β) − λµAB µO
uE

with
uE = µAB µB + µA (µAB + 2µB ) + βµO

+ p̄ µ2A + µA µAB + µ2AB + µAB µB + µ2B

+ 2(µA + µAB + µB )µO + µ2O
sketch. We begin with matching M ∗ as done in the proof
of Lemma 1, matching all highly sensitized vertices except
for those in VHAB-O . We now complete the efficient matching using both 3-cycles and 3-chains as in (Dickerson et al.
2012).
7. A- and B-type NDDs donate to V A-AB and V B-AB , respectively. Note that |N A | ∝ βµA and |V A-AB | ∝ (1 −
p̄)µA µAB . The inequality βµA < µA µAB (1 − p̄) holds
due to assumption 2, and a.s. |N A | < |V A-AB |. By the
same argument, a.s. |N B | < |V B-AB |. Thus, both N A and
N B are exhausted, and |V A-AB | ∝ µA µAB (1 − p̄) − βµA
and |V B-AB | ∝ µB µAB (1 − p̄) − βµB .
8. Create cycles of the form (AB-O, O-A, A-AB). The current size of each vertex group is
(1) |V AB-O | ∝ p̄µAB µO
(2) |V O-A | ∝ (1 − p̄)µA µO
(3) |V A-AB | ∝ µA µAB (1 − p̄) − βµA
Note that the inequality (3) < (1) can be written as
β > µAB (1 − p̄) − p̄µAB µO /µA
which holds by assumption 1, and a.s. |V A-AB | < |V AB-O |.
The inequality (3) < (2) can be written as
β > (1 − p̄)(µAB − µO )
which holds by model assumptions, and a.s. |V A-AB | <
|V O-A |. Executing these cycles exhausts V A-AB and leaves
the following vertices remaining

|V O-A | ∝ (1 − p̄)µA (µO − µAB ) + µA β
|V AB-O | ∝ p̄µAB µO − µA µAB (1 − p̄) + µA β
9. Create cycles of the form (AB-O, O-B, B-AB). The current size of each vertex group is
(1) |V AB-O | ∝ p̄µAB µO − µA µAB (1 − p̄) + µA β
(2) |V O-B | ∝ (1 − p̄)µB µO
(3) |V B-AB | ∝ µB µAB (1 − p̄) − βµB
Inequality (1) < (2) can be written as
β < µAB (1 − p̄) − p̄µAB µO /µA + (1 − p̄)µB µO /µA
which holds by assumption 3. Inequality (1) < (3) can be
written as
β < µAB (1 − p̄) − µAB µO p̄/(µA + µB )
which holds by assumption 2.
Executing these cycles exhausts V AB-O and leaves the following vertices remaining
|V O-B | ∝ µA µAB (1− p̄)+(µB − p̄(µAB +µB ))µO −βµA
|V B-AB | ∝ ((1 − p̄)µAB − β) (µA + µB ) − p̄µAB µO
10. Create chains of the form (O,O-A,A-AB). Previous steps
exhausted V A-AB so none of these chains occur.
11. Create chains of the form (O,O-B,B-AB). The current size
of each vertex group is
(1) |N O | ∝ βµO
(2) |V O-B | ∝ µA µAB (1− p̄)+(µB − p̄(µAB +µB ))µO −βµA
(3) |V B-AB | ∝ ((1 − p̄)µAB − β) (µA + µB ) − p̄µAB µO
The inequality (3) < (1) can be written as


µO
β > µAB (1 − p̄) −
1 − µAB
which holds by assumption 4. The inequality (3) < (2)
can be written as
β > (1 − p̄)(µAB − µO )
which holds by the model assumptions. Executing these
chains exhausts V B-AB and leaves the following vertices
remaining
|N O | ∝ (β + p̄µAB )(µA + µB + µO ) − µAB (µA + µB )
|V O-B | ∝ µB ((β + (1 − p̄)(µO − µAB ))
12. Remaining O-type NDDs and V AB-O vertices match with
remaining under-demanded vertices, starting with V O-AB .
The remaining size of each vertex group is
(1) |N O | ∝ (β + p̄µAB )(µA + µB + µO ) − µAB (µA + µB )
(2) |V O-AB | ∝ µAB µO
(3) |V AB-O | = 0
After simplifying, the inequality (1) < (2) can be written
as
β < µAB (1 − p̄)
which holds by assumption 2. Thus O-type NDDs are exhausted first, leaving some vertices remaining in V O-AB ,
with
|V O-AB | ∝ ((1 − p̄)µAB − β) (1 − µAB )

In the efficient matching described above, the number of
matched pairs in each under-demanded group is
|V O-A | ∝ µA (µAB (1 − p̄) + p̄µO − β)
|V O-B | ∝ µB (µAB (1 − p̄) + p̄µO − β)
|V A-AB | ∝ µA µAB
|V B-AB | ∝ µB µAB
|V O-AB | ∝ (β + µAB p̄)(1 − µAB ) − µAB (µA + µB )
Combining these with the over-demanded and selfdemanded vertices, the total size of the efficient matching
is
uE = µAB µB + µA (µAB + 2µB ) + βµO

+ p̄ µ2A + µA µAB + µ2AB + µAB µB + µ2B

+ 2(µA + µAB + µB )µO + µ2O
To calculate the price of fairness we now find the size
of the fair matching. The only unmatched highly sensitized
patients are in VHO-AB , some of which were matched in step
12 above. We now show that the number of matched vertices
in V O-AB is smaller than the initial size of VHO-AB , so not all
vertices in VHO-AB can be matched. Let M O-AB be the number
of matched vertices in V O-AB , and H O-AB be the initial size
of VHO-AB . The inequality M O-AB < H O-AB can be written as
(β + µAB p̄)(1 − µAB ) − µAB (µA + µB ) < (1 − λ)µO µAB
(7)
µAB
β < µAB (1 − p̄) − λµO
1 − µAB

(8)

This inequality holds by assumption 5, and a.s. there
are some unmatched vertices in VHO-AB . The number of unmatched highly sensitized vertices is
H O-AB − M O-AB ∝ (1 − µAB )((1 − p̄)µAB − β) − λµAB µO
.
We match each of these remaining vertices by removing a 3-cycle of the form (AB-O, O-A, A-AB) and creating
a 2-cycle (AB-O, O-AB). This matching used |V AB-O | ∝
p̄µO µAB 3-cycles of this form, while |VHO-AB | ∝ (1 −
λ)µO µAB . The model assumptions ensure that |V AB-O | >
|VHO-AB |, and all remaining vertices in VHO-AB can be matched
in this way.
To match each remaining vertex in VHO-AB , we remove
from the matching one vertex from both V O-A and V A-AB .
Thus the total efficiency loss is H O-AB − M O-AB . The price
of fairness is
POF(M, uLEX ) =

(1 − µAB )((1 − p̄)µAB − β) − λµAB µO
uE

With uE defined previously.
Proposition 5. Assume

1 β > µAB (1 − p̄) − µAB µO p̄/(µA + µB )
µAB
2 β < µAB (1 − p̄) − λµO 1−µ
AB

Inequality (3) < (2) can be written as

These constraints imply β ∈ [0, 1/10]. Denote by M
the set of matchings in G(n) using cycles and chains up to
length 3. Almost surely as n → ∞, the price of fairness is

which holds by the model assumptions. Inequality (3) <
(1) can be written as

β > (1 − p̄)(µAB − µO )

β > µAB (1 − p̄) − µAB µO p̄/(µA + µB )
POF(M, uLEX ) =

(1 − µAB )((1 − p̄)µAB − β) − λµAB µO
uE

with
uE = µAB µB + µA (µAB + 2µB ) + βµO

+ p̄ µ2A + µA µAB + µ2AB + µAB µB + µ2B

+ 2(µA + µAB + µB )µO + µ2O
sketch. We begin with matching M ∗ as done in the proof
of Lemma 1, matching all highly sensitized vertices except
for those in VHAB-O . We now complete the efficient matching using both 3-cycles and 3-chains as in (Dickerson et al.
2012).
7. A- and B-type NDDs donate to V A-AB and V B-AB , respectively. Note that |N A | ∝ βµA and |V A-AB | ∝ (1 −
p̄)µA µAB . The inequality βµA < µA µAB (1 − p̄) holds
due to assumption 2, and a.s. |N A | < |V A-AB |. By the
same argument, a.s. |N B | < |V B-AB |. Thus, both N A and
N B are exhausted, and |V A-AB | ∝ µA µAB (1 − p̄) − βµA
and |V B-AB | ∝ µB µAB (1 − p̄) − βµB .
8. Create cycles of the form (AB-O, O-A, A-AB). The current size of each vertex group is
(1) |V AB-O | ∝ p̄µAB µO
(2) |V O-A | ∝ (1 − p̄)µA µO
(3) |V A-AB | ∝ µA µAB (1 − p̄) − βµA
Note that the inequality (3) < (1) can be written as
β > µAB (1 − p̄) − p̄µAB µO /µA
which holds by assumption 1 and a.s. |V A-AB | < |V AB-O |.
The inequality (3) < (2) can be written as
β > (1 − p̄)(µAB − µO )
which holds by the model assumptions, and a.s.
|V A-AB | < |V O-A |. Executing these cycles exhausts V A-AB
and leaves the following vertices remaining
|V O-A | ∝ (1 − p̄)µA (µO − µAB ) + µA β
|V AB-O | ∝ p̄µAB µO − µA µAB (1 − p̄) + µA β
9. Create cycles of the form (AB-O, O-B, B-AB). The current size of each vertex group is
(1) |V AB-O | ∝ p̄µAB µO − µA µAB (1 − p̄) + µA β
(2) |V O-B | ∝ (1 − p̄)µB µO
(3) |V B-AB | ∝ µB µAB (1 − p̄) − βµB

which holds by assumption 1.
Executing these cycles exhausts V B-AB and leaves the following vertices remaining
|V AB-O | ∝ (β − (1 − p̄)µAB )(µA + µB ) + p̄µAB µO
|V B-AB | ∝ µB (β − (1 − p̄)(µAB − µO ))
10. Create chains of the form (O,O-A,A-AB). Previous steps
exhausted V A-AB so none of these chains occur.
11. Create chains of the form (O,O-B,B-AB). Previous steps
exhausted V B-AB so none of these chains occur.
12. O-type NDDs and V AB-O match with remaining underdemanded vertices, starting with V O-AB . The remaining
size of each vertex group is
(1) |N O | ∝ βµO
(2) |V AB-O | ∝ (β − (1 − p̄)µAB )(µA + µB ) + p̄µAB µO
(3) |V O-AB | ∝ µO µAB
Note that the inequality (1) + (2) < (3) can be written as
β < µAB (1 − p̄)
which holds by assumption 2 Thus O-type NDDs are exhausted first, leaving some vertices remaining in V O-AB ,
with
|V O-AB | ∝ ((1 − p̄)µAB − β)(1 − µAB )
In the efficient matching described above, the number of
matched pairs in each under-demanded group is
|V O-A | ∝ µA (µAB + p̄(µO − µAB ) − β)
|V O-B | ∝ µB (µAB + p̄(µO − µAB ) − β)
|V A-AB | ∝ µA µAB
|V B-AB | ∝ µB µAB .
|V O-AB | ∝ (β + µAB p̄)(1 − µAB ) − µAB (µA + µB )
Combining these with the over-demanded and selfdemanded vertices, the total size of the efficient matching
is
uE = µAB µB + µA (µAB + 2µB ) + βµO

+ p̄ µ2A + µA µAB + µ2AB + µAB µB + µ2B

+ 2(µA + µAB + µB )µO + µ2O
To calculate the price of fairness we now find the size
of the fair matching. The only unmatched highly sensitized
patients are in VHO-AB , some of which were matched in step
12 above. We now show that the number of matched vertices
in V O-AB is smaller than the initial size of VHO-AB , so not all
vertices in VHO-AB can be matched. Let M O-AB be the number

of matched vertices in V O-AB , and H O-AB be the initial size
of VHO-AB . The inequality M O-AB < H O-AB can be written as
(β + µAB p̄)(1 − µAB ) − µAB (µA + µB ) < (1 − λ)µO µAB
(9)
µAB
(10)
β < µAB (1 − p̄) − λµO
1 − µAB
This inequality holds by assumption 2, and a.s. there
are some unmatched vertices in VHO-AB . The number of unmatched highly sensitized vertices is
H O-AB − M O-AB ∝ (1 − µAB )((1 − p̄)µAB − β) − λµAB µO .
We match each of these remaining vertices by removing a 3-cycle of the form (AB-O, O-A, A-AB) and creating
a 2-cycle (AB-O, O-AB). This matching used |V AB-O | ∝
p̄µO µAB 3-cycles of this form, while |VHO-AB | ∝ (1 −
λ)µO µAB . The model assumptions ensure that |V AB-O | >
|VHO-AB |, and all remaining vertices in VHO-AB can be matched
in this way.
To match each remaining vertex in VHO-AB , we remove
from the matching one vertex from both V O-A and V A-AB .
Thus the total efficiency loss is H O-AB − M O-AB . The price
of fairness is
(1 − µAB )((1 − p̄)µAB − β) − λµAB µO
uE
With uE defined previously.

POF(M, uLEX ) =

Next we compare the price of fairness in Propositions 2,
3, 4, and 5 to the price of fairness in the efficient matching
without NDDs, given in Dickerson et al. (2014):
POF0 =

(1 − λ)µO µAB
uE

(11)

h
uE = p̄ 2µAB µB + 2µAB µA + 3µAB µO
+2µA µO + 2µB µO + µ2O + µ2A + µ2B + µ2AB

i

sketch. The price of fairness in Propositions 2 and 3 is
(1 − λ)µO µAB
uE

+2µA µB + β (µA + µB + 2µO )

sketch. The price of fairness in Propositions 4 and 5 is
POFB =

(1 − µAB )((1 − p̄)µAB − β) − λµAB µO
uE

uE = µAB µB + µA (µAB + 2µB ) + βµO

+ p̄ µ2A + µA µAB + µ2AB + µAB µB + µ2B

+ 2(µA + µAB + µB )µO + µ2O
To show that POFB < POF0 holds, we first show both (1)
the numerator of POFB is smaller than that of POF0 , and (2)
the denominator of POFB is larger than the denominator of
POF0 .
(1) In both POF0 and POFB , the numerator is proportional to
the number of remaining vertices in VHO-AB , after constructing the efficient matching. In Proposition 4 and 5 the efficient matching contains some vertices in VHO-AB ; without
NDDs, the efficient matching contains no vertices in VHO-AB .
Thus, the numerator of POFB is strictly smaller the numerator of POF0 .
(2) Let the D0 be the denominator of POF0 , and DB be
the denominator of POFB . We now show that the inequality D0 < DB holds. First, note that this inequality can be
written as
µAB − (1 − p̄)µ2AB + βµO > µAB (p̄ + µO ).
Rearranging, we have
(12)

We now show that inequality 12 is satisfied by the the
following assumption on β, made in Propositions 4 and 5:
A : β > µAB (1 − p̄) − µAB µO p̄/µA .
Next, we show that assumption A implies inequality 12,
and thus assumption A implies D0 < DB . Assumption A
implies 12 if the right-hand side of A is larger than the right
hand side of 12, that is,
µAB (1 − p̄) − µAB µO p̄/µA > (µAB /µO )(1 − p̄)µAB
− (µAB /µO )(µA + µB + µAB − p̄)

h
uE = p̄ 2µAB µB + 2µAB µA + 3µAB µO
+2µA µO + 2µB µO + µ2O + µ2A + µ2B + µ2AB

Lemma 3. The price of fairness in Propositions 4 and 5 is
bounded above by POF0 .



β > (µAB /µO ) (1 − p̄)µAB − (µA + µB + µAB − p̄) .

+2µA µB
The following Lemmas state that POF0 is an upper bound
on the price of fairness when NDDs are used, for each of the
four cases when the price of fairness is nonzero.
Lemma 2. The price of fairness in Propositions 2 and 3 is
bounded above by POF0 .

POFA =

Both POF0 and POFA have the same numerator, and the
denominator of POFA is equal to the denominator of POF0 ,
with the additional term β (µA + µB + 2µO ). Thus when
β = 0, POF0 = POFA , and when β > 0, POF0 > POFA ,
and the price of fairness in Propositions 2 and 3 is bounded
above by POF0 .

rearranging, we have
i
µO 1 − µAB − µB
1 − p̄
>
p̄
µA
1 − µB

The random graph model assumes p̄ ≤ 2/5, and µO ≤
(3/2)µA , thus we have
1 − p̄
3
3 1 − µAB − µB
µO 1 − µAB − µB
≥ >
≥
.
p̄
2
2
1 − µB
µA
1 − µB
This shows that assumption A implies D0 < DB .
Thus, the numerator of POF0 is larger than the numerator
of POFB , and the denominator of POF0 is smaller than the
denominator of POFB , and therefore POFB < POF0 .
Lemmas 2 and 3 show that with β > 0, the price of
fairness has the same upper bound as when β = 0, given
in Dickerson et al. (2014). That is, adding NDDs to the random graph model does not increase the price of fairness.
Theorem 1. Adding NDDs to the random graph model (β >
0) does not increase the upper bound on the price of fairness
found by Dickerson et al. (2014).
Proof. When β > 0, there are only four possible matchings
with nonzero price of fairness, and the price of fairness for
each case is given in Propositions 2, 3, 4, and 5. Lemmas 2
and 3 state that in each of these four cases, the matching with
NDDs has a tighter bound on the price of fairness than the
matching without NDDs, given in Dickerson et al. (2014).
Next we show that the price of fairness is zero when β >
1/8, by finding the maximum possible β for each of the four
cases with nonzero price of fairness.
Lemma 4. In the matching described by Proposition 2, β <
1/8.
Proof. Proposition 2 makes the following assumptions on
β:
1 β < µA (1 − p̄) − p̄µAB
2 β < µAB (1 − p̄) − p̄µAB µO /µA


A
3 β < µAB µAµ+µ
−
p̄
O
To determine an upper bound on β, we maximize the
right hand side of constraint 3. Note that the model assumes
µAB < 1/4, µA < 1/2, and µA + µO < 1. Using these
bounds, and p̄ → 0, constraint 3 is bounded by

β < µAB


µA
(1/2)
− p̄ < (1/4)
= 1/8
µA + µO
1

β < 1/8
Constraints 1 and 2 are looser than constraint 3: with the
values p̄ → 0, µA → 1/4, and µAB → 1/4, both constraints
reduce to β < 1/4.
Lemma 5. In the matching described by Proposition 3, β <
1/12.
Proof. Proposition 3 makes the following assumptions
1 β < µAB (1 − p̄) − µAB µO p̄/(µA + µB )

2 β<

µA µAB (1−p̄)+µB µO (1−p̄)−p̄µO µAB
µA +µO

3 β > µAB (1 − p̄) − µAB µO p̄/µA
4 β < µAB (1 − p̄) − p̄µAB µO /µA + (1 − p̄)µB µO /µA
5 β < µAB (1 − p̄) − µO µAB /(1 − µAB )
Combining 3 and 5, we have
µO µAB /(1 − µAB ) < µAB (1 − p̄) − β < µAB µO p̄/µA
µO µAB /(1 − µAB ) < µAB µO p̄/µA
A : µA /(1 − µAB ) < p̄
Combining constraint A with 5 gives a new upper bound
on β,
β < µAB (1 − p̄) − µO µAB /(1 − µAB )
< µAB (1 − µA /(1 − µAB )) − µO µAB /(1 − µAB )

β < µAB

µA + µO
1−
1 − µAB



This bound is maximized when when µAB is maximal, and
(µA +µO ) is minimal. In the random graph model, these values are µAB → 1/4 and (µA +µO ) → 1/2, and the numerical
bound is


(1/2)
β < (1/4) 1 −
= 1/12
1 − 1/4
β < 1/12

Lemma 6. In the matching described by Proposition 4, β <
1/8.
Proof. Proposition 4 makes the following assumptions on β
1 β > µAB (1 − p̄) − µAB µO p̄/µA
2 β < µAB (1 − p̄) − µAB µO p̄/(µA + µB )
3 β < µAB (1 − p̄) − p̄µAB µO /µA + (1 − p̄)µB µO /µA


µO
4 β > µAB (1 − p̄) − 1−µ
AB
µAB
5 β < µAB (1 − p̄) − λµO 1−µ
AB

Combining 1 and 5 results in the following constraint,
which is consistent with the above assumptions:
A:λ

µA
< p̄
1 − µAB

Note that 5 is maximized when λ is minimized; this occurs when λ + p̄ → 1, and λ → 1 − p̄. In this case, 5 can be
relaxed as

β < µAB (1 − p̄) − λµO

µAB
1 − µAB

< µAB (1 − p̄) − (1 − p̄)µAB

µO
1 − µAB

β < µAB (1 − p̄) − (1 − p̄)µAB

µO
1 − µAB

= (1 − p̄)

µAB (µA + µB )
1 − µAB

1 β > µAB (1 − p̄) − µAB µO p̄/(µA + µB )
µAB
2 β < µAB (1 − p̄) − λµO 1−µ
AB
Combining these assumptions results in the following
constraint:
A:λ

µA + µB
< p̄
1 − µAB

Note that assumption 2 is identical to assumption 5 in
Lemma 6. Following the same procedure used in the proof
of Lemma 6, 2 can be relaxed as

Finally, we have
β < (1 − p̄)
β < (1 − p̄)

µAB (µA + µB )
1 − µAB

The right hand side of this constraint is maximal when p̄
is minimal; constraint A determines the lower bound for p̄,
with λ → 1 − p̄:
µA
(1 − p̄)
< p̄
1 − µAB


µA
µA
< p̄ 1 +
1 − µAB
1 − µAB
µA
< p̄
1 − µAB + µA
Using this lower bound on p̄, we can further relax 5
µAB (µA + µB )
1 − µAB
µA
µAB (µA + µB )
< (1 −
)
1 − µAB + µA
1 − µAB
1 − µAB µAB (µA + µB )
=
1 − µAB + µA
1 − µAB
µAB (µA + µB )
=
1 − µAB + µA

β < (1 − p̄)

β<

µAB (µA + µB )
1 − µAB + µA

The right hand side is maximal when µAB is maximal, and
µAB , µA , µB , µO → 1/4. This gives the final bound on β,
(1/4)(1/2)
= 1/8
1
β < 1/8

β<

µAB (µA + µB )
1 − µAB

The right hand side of this constraint is maximal when p̄
is minimal; constraint A determines the lower bound for p̄,
with λ → 1 − p̄:
µA + µB
< p̄
1 − µAB


µA + µB
µA + µB
< p̄ 1 +
1 − µAB
1 − µAB
µA + µB
< p̄
2µA + 2µB + µO
(1 − p̄)

Using this lower bound on p̄, we can further relax 2
µAB (µA + µB )
1 − µAB
µA + µB
µAB (µA + µB )
< (1 −
)
2µA + 2µB + µO
1 − µAB
1 − µAB
µAB (µA + µB )
=
2µA + 2µB + µO
1 − µAB
µAB (µA + µB )
=
2µA + 2µB + µO

β < (1 − p̄)

β<

µAB (µA + µB )
2µA + 2µB + µO

The right hand side is maximal when µAB is maximal, and
µAB , µA , µB , µO → 1/4. This gives the final bound on β,
(1/4)(1/2)
= 1/10
5/4
β < 1/10

β<

Lemma 7. In the matching described by Proposition 5, β <
1/10.

Combining Lemmas 4, 5, 6, and 7, we find that the price
of fairness is zero when β > 1/8.

Proof. Proposition 5 makes the following assumptions on β

Theorem 2. The price of fairness is zero when β > 1/8.

Proof. There are only four matchings with nonzero price of
fairness and β > 0, which are described in Propositions 2, 3,
4, and 5. Lemmas 4, 5, 6, and 7 state that the maximum β for
any of these matchings is 1/8. When β > 1/8, the matching
is not one of these four cases, and the price of fairness is
zero.

V2
H

B.1

■
●

■

■

■

●

■

■

●

■

■

●

■

■

■

●

■

■

●
◆

●

◆

■
◆

■
◆

■
◆

■
◆
◆
■

◆

■
◆

◆
●
◆

0.05

Prop. 3

■
◆

◆
●

■
◆
■
◆

●

◆

◆
■

●

■
◆
●

◆

■
◆
●

◆

◆
■
■
◆

●

■
◆

●

■
◆
●

◆
■
■
◆

●

■
◆

●
◆

Max PoF

Prop. 4

■
◆
●

■
◆

●

◆
■
●
■
◆
●
■
◆
●

Prop. 5

■
◆
●

◆

◆

●
●
●

◆
●
●
◆

●
●

◆

●

◆
●
●

0.03

◆
●
●
◆
●
●
◆
●
●

◆

◆
▲
▲

▲

▲

▲

▲

●
▲

▲

●

▲

◆

▲

▲

▲

●
▲
▲

▲

●

◆

▲
▲

0.02

●
▲
◆

▲

▲

Lexicographic Fairness

Theorem 4. For any chain cap R there exists a graph
G such that the price of fairness of G under the αlexicographic fairness rule with 0 < α ≤ 1 is bounded by
POF(M, uα ) ≥ R−1
R .

■
◆
●

◆

◆

0.04

V4

Proof. Consider a kidney exchange graph consisting of one
highly-sensitized patient H and L non-highly-sensitized patients Vi that form a directed cycle of length L. A 2-cycle
connects H with one Vi , as shown in Figure 6. With a cycle cap of L, the optimal utilitarian matching has utility L,
while the optimal lexicographic matching has utility uα = 2,
for any 0 < α ≤ 1. The price of fairness in this graph is
POF(M, uα ) = (L − 2)/L.

Prop. 2
■

●

V3

N

Theorem 3. For any cycle cap L there exists a graph G such
that the price of fairness of G under the α-lexicographic
fairness rule with 0 < α ≤ 1 is bounded by POF(M, uα ) ≥
L−2
L .

Max PoF
■
●

H

Figure 6: Supporting graphs for Theorems 3 (left) and 4
(right), with cycle cap 4 and chain cap 3, respectively.

0.07
■
●

V2
V3

V4

Theorems 1 and 2 are the two main theoretical results of
this paper: adding NDDs to the random graph model does
not increase the upper bound on the price of fairness, and
when the proportion of NDDs is high enough (β > 1/8), the
price of fairness is zero. We show this by addressing each of
the four efficient matchings on the random graph model with
nonzero price of fairness. In each case, and β < 1/8, and the
matching with NDDs has a smaller price of fairness than the
matching without NDDs given in Dickerson et al. (2014).
To further explore these results, we numerically find the
maximum price of fairness for the matchings given in Propositions 2, 3, 4, and 5. For each matching, we find the maximum price of fairness for a range of β, within the defined
constraints, using the “NMaximize” function in Mathematica with the nonlinear interior point method.

0.06

V1

●
▲
▲

●

◆

▲
▲

●

▲
▲

◆

●

▲

▲

▲

Proof. Consider the graph used in the proof of Theorem 3,
with vertex V2 as an NDD rather than a pair. With a chain cap
of R, the optimal utilitarian matching has utility R, while
the optimal α-lexicographic matching has utility uα = 1
for any 0 < α ≤ 1. The price of fairness in this graph is
POF(M, uα ) = (R − 1)/R.

●

▲

◆

▲
▲

●
▲
◆
▲

●
▲

0.01

●

◆

▲
▲

B.2

●
◆
▲
●

▲

◆

▲

●

▲
▲

Weighted Fairness

◆
●

▲
▲
▲

◆
●
▲

0.00
0.00

▲
▲

◆
●
▲

▲
◆

0.02

0.04

0.06

0.08

0.10

0.12

β

Figure 5: Maixmum price of fairness for each of the four
matchings addressed in Propositions 2, 3, 4, and 5.
Figure A.2 confirms both of our main theoretical results:
adding NDDs to the efficient matching decreases the upper
bound on the price of fairness, and when β > 1/8 the price
of fairness is zero.

B

Price of Fairness for α-Lexicographic-,
Weighted-, and Hybrid-Lexicographic
Fairness

This section presents Theorems and Proofs regarding the
price of fairness for the lexicographic, weighted, and hybridlexicographic fairness rules.

Theorem 5. For any cycle cap L and γ ≥ L − 1, there
exists a graph G such that the price of fairness of G under
the weighted fairness rule is bounded by POF(M, uW F ) ≥
L−2
L .
Proof. Consider the graph used in the proof of Theorem 3,
with all edge weights equal to 1. Weighted fairness increases
the weight of the edge ending in H to (1 + γ). The weighted
utility of the 2-cycle is 2 + γ, while the weighted utility of
the L-cycle is L. If γ is chosen such that γ ≥ L − 2, then
the 2-cycle will be chosen over the L-cycle, resulting in the
price of fairness POF(M, uW F ) = (L − 2)/L.
Theorem 6. For any chain cap R and γ ≥ R − 1, there
exists a graph G such that the price of fairness of G under
the weighted fairness rule is bounded by POF(M, uW F ) ≥
R−1
R .
Proof. Consider the graph used in the proof of Theorem 4,
with all weights equal to 1. The weighted utility of the 1chain is 1 + γ, while the weight of the R-chain is R. If γ
is chosen such that γ ≥ R − 1, then the 1-chain will be

HN

···

H1

N

V1

···

VN 0

HN

···

H1

H0

V1

···

VN 0

Figure 7: Graphs for Theorems 7 (top) and 8 (bottom).

chosen over the R-chain, resulting in the price of fairness
POF(M, uW F ) = (R − 1)/R.

B.3

Theorem 9. Assume the optimal utilitarian outcome XE
receives utility u(XE ) = uE , with one disadvantaged
class that receives utility u1 , and Z non-disadvantaged
classes such that u1 (XE ) > ui (XE ). For |P| classes,
POF(M, u∆ ) ≤ 2((|P|−1)−Z)∆
.
uE
Proof. Consider two outcomes, one in the fair regime (XF ),
one in the utilitarian regime (XE ). Let u∆ (XF ) > u∆ (XE ),
such that XE receives nearly the same utility as XF ; that is,
u∆ (XE ) = u∆ (XF ) −  for some 0 <   1. WLOG, let
there be Z classes i such that u1 (XE ) > ui (XE ), and
u∆ (XE ) = u∆ (XF ) − 

Theorem 7. With no chain cap, there exists a graph G such
that the price of fairness of G under the weighted fairness
γ
rule is bounded by POF(M, uW F ) ≥ γ+1
.
Proof. Consider a graph with a single NDD connected to a
chain with highly-sensitized patients Hi of length N , and
a chain with non-highly sensitized patients Vi of length
N 0 = b(γ + 1)N c − 1. Under weighted fairness, the Vi
chain receives utility uL = b(γ + 1)N c − 1 while the Hi
chain receives utility uH = (γ + 1)N , so uH > uL . The
price of fairness for this graph is

POF(M, uW F ) =

bγNH c − 1
γN − 2
≥
.
bγN c + N − 1
(γ + 1)N − 1

Taking the limit as N → ∞ yields
lim

N →∞

γN − 2
γ
=
,
(γ + 1)N − 1
γ+1

which implies POF(M, uW F ) ≥

γ
γ+1 .

Theorem 8. With no cycle cap there exists a graph G such
that the price of fairness of G under the weighted fairness
γ
rule is bounded by POF(M, uW F ) ≥ γ+1
.
Proof. Consider the graph used in the proof of Theorem 7,
where the NDD N is instead a highly-sensitized pair H0 ,
and the end vertices of both chains both have edges ending
in H0 . Under weighted fairness, the Vi cycle receives utility
uL = b(γ + 1)N c, while the Hi chain receives utility uH =
(γ + 1)N + 1, so uH > uL . The price of fairness for this
graph is
POF(M, uW F ) =

bγcN − 1
γN − 1
≥
.
bγN c + N
(γ + 1)N + 1

Taking the limit as N → ∞ yields
lim

N →∞

γN − 1
γ
=
,
(γ + 1)N + 1
γ+1

Hybrid-Lexicographic

≤

|P|
X

(13)

ui (XF ) + (|P| − 1)∆ − 

i=1

Using the definition of utilitarian utility uE =

P|P|

i=1

ui ,

uE (XE ) − uE (XF ) ≤ (2(|P| − 1) − 2Z)∆ − 
and the price of fairness is
POF(M, u∆ ) ≤

C

2((P − 1) − Z)∆
.
uE (XE )

Experimental Results

This section contains worst-case price of fairness (PoF) and
worst-case fairness (%F ) for real UNOS graphs, and for
simulated graphs; these results were produced using the
method described in Section 5.

C.1

UNOS Graphs

Figure C.1 shows the worst-case (maximum) PoF of each
fairness rule on the 314 UNOS graphs; Figure C.1 shows
worst-case (minimum) %F .
Real exchange graphs are relatively sparse, and have
very few feasible matchings. Each fairness rule effectively
chooses one of these matchings, based on a fairness criteria. Especially with sparse graphs, fairness is often achieved
by using longer cycles or cycles to match highly sensitized
vertices. When edge success probability p is high, fairness
has little effect on overall utility, and PoF is often below 0.3.
With lower edge success probability, using longer cycles and
chains causes a huge loss in efficiency: the expected utility
of n-cycles and chains is proportional to pn , which incurs
a huge penalty for long cycles and chains when p is small.
Thus as p decreases, very small α and β values result in
a high PoF. Our results show that for p ≤ 0.8, even the
smallest parameters for α-lexicographic and weighted fairness (α = 0.1 and β = 2) achieve the worst-case PoF. As
expected, hybrid-lexicographic fairness limits PoF according to Theorem 9. With two classes of patients (highly- and
lowly-sensitized), the theoretical price of fairness is bounded
by POF(M, u∆ ) ≤ 2∆/u(ME ); in the Figures, ∆ is scaled
by u(ME ), so the upper bound on the price of fairness has a
slope of two.

Max. PoF

Max. PoF

Max. PoF

0

Fraction of
max. parameter

1

0

Fraction of
max. parameter

1

0
Fraction of
max. parameter

p = 0.3

1

0
Fraction of
max. parameter

p = 0.4

1

0
Fraction of
max. parameter

p = 0.5

1

0
Fraction of
max. parameter

p = 0.6

1

0
Fraction of
max. parameter

p = 0.7

1

0
Fraction of
max. parameter

p = 0.8

1

0
Fraction of
max. parameter

p = 0.9

1

0
Fraction of
max. parameter

p = 1.0

1

ChainCap=20.0

weighted
α-lex.
hybrid lex.

Fairness rule

Figure 8: Maximum PoF for each fairness rule. Parameters for each rule are α ∈ [0, 1], β ∈ [0, 20], and ∆ ∈ [0, u(ME )]. Rows correspond to edge success
probabilities from 0.1 to 1.0; columns correspond to different chain caps: 0, 3, and 20.

0.0

0.2

0.4

0.6

p = 0.2

ChainCap=10.0

0.8

0.0

0.2

0.4

0.6

0.8

0.0

0.2

0.4

0.6

0.8

0.0

0.2

0.4

0.6

0.8

p = 0.1

ChainCap=3.0

Max. PoF

ChainCap=0.0

To illustrate the other side of the fairness-efficiency tradeoff, we consider worst case %F . Figure C.1 shows the minimum (worst case) %F over all UNOS graphs for each fairness rule, and for various edge success probabilities and
chain caps.
As expected, α-lexicographic fairness guarantees at
%F ≥ α; weighted and hybrid-lexicogrpahic fairness do
not make this guarantee. Small edge success probabilities
make it impossible to match highly sensitized patients without large efficiency loss; when p becomes small hybridlexicographic fairness matches no highly sensitized patients
in the worst case.
These results demonstrate the balance between fairness
and efficiency offered by both α-lexicographic and hybridlexicographic fairness. If fairness is more important than efficiency, then the α-lexicographic rule can be used to guarantee that the resulting matching achieves at least fraction
α of the maximum possible fair score. Alternatively, if efficiency is more important than fairness, hybrid-lexicographic
fairness can bound the price of fairness using parameter ∆.

C.2

Simulated Exchange Graphs

Simulated exchange graphs were drawn from previous
UNOS exchanges, using the same method as Dickerson
et al. (2013). These graphs are typically denser than real
graphs, and have a much lower price of fairness. Figures 10
and 11 show the worst-case PoF and %F on 32 simulated
exchanges of size 64 and 128.

Min. %F

Min. %F

Min. %F

0

Fraction of
max. parameter

1

0

Fraction of
max. parameter

p = 0.2

1

0
Fraction of
max. parameter

p = 0.3

1

0
Fraction of
max. parameter

p = 0.4

1

0
Fraction of
max. parameter

p = 0.5

1

0
Fraction of
max. parameter

p = 0.6

1

0
Fraction of
max. parameter

p = 0.7

1

0
Fraction of
max. parameter

p = 0.8

1

0
Fraction of
max. parameter

p = 0.9

1

0
Fraction of
max. parameter

p = 1.0

1

ChainCap=20.0

weighted
α-lex.
hybrid lex.

Fairness rule

Figure 9: Minimum fraction of the fair score for each fairness rule. Parameters for each rule are α ∈ [0, 1], β ∈ [0, 20], and ∆ ∈ [0, u(ME )]. Rows correspond to
edge success probabilities from 0.1 to 1.0; columns correspond to different chain caps: 0, 3, and 20.

0.00

0.25

0.50

p = 0.1

ChainCap=10.0

0.75

0.00
1.00

0.25

0.50

0.75

0.00
1.00

0.25

0.50

0.75

0.00
1.00

0.25

0.50

0.75

1.00

ChainCap=3.0

Min. %F

ChainCap=0.0

Max. PoF

Max. PoF

(a) Maximum PoF.

p = 1.0

1

Fraction of
max. parameter

1 0

Fraction of
max. parameter

1 0

Fraction of
max. parameter

1 0

Fraction of
max. parameter

0

p = 0.8

weighted
α-lex.
hybrid lex.

Fairness rule

0.00

0.25

0.50

0.75

0.00
1.00

0.25

0.50

0.75

0.00
1.00

0.25

0.50

0.75

0.00
1.00

0.25

0.50

0.75

1.00

p = 0.5

p = 0.8

p = 1.0

(b) Minimum %F .

1 0
1 0
1 0
1
Fraction of
Fraction of
Fraction of
Fraction of
max. parameter
max. parameter
max. parameter
max. parameter

0

p = 0.2

ChainCap=20.0

ChainCap=20.0

weighted
α-lex.
hybrid lex.

Fairness rule

Figure 10: Worst-case PoF and %F for 32 64-vertex random graphs. Parameters for each rule are α ∈ [0, 1], β ∈ [0, 20], and ∆ ∈ [0, u(ME )]. Rows correspond to
edge success probabilities from 0.1 to 1.0; columns correspond to different chain caps: 0, 3, and 20.

0.0

0.1

0.2

p = 0.5

ChainCap=10.0

0.3

0.0

0.1

0.2

0.3

0.0

0.1

0.2

0.3

0.0

0.1

0.2

0.3

p = 0.2

ChainCap=5.0

Max. PoF

Min. %F
Min. %F
Min. %F

ChainCap=0.0

ChainCap=10.0

Max. PoF

ChainCap=5.0

Min. %F

ChainCap=0.0

Max. PoF

Max. PoF

(a) Maximum PoF.

p = 1.0

1

Fraction of
max. parameter

1 0

Fraction of
max. parameter

1 0

Fraction of
max. parameter

1 0

Fraction of
max. parameter

0

p = 0.8

weighted
α-lex.
hybrid lex.

Fairness rule

0.2

0.4

0.6

0.8

0.2
1.0

0.4

0.6

0.8

0.2
1.0

0.4

0.6

0.8

0.2
1.0

0.4

0.6

0.8

1.0

p = 0.5

p = 0.8

p = 1.0

(b) Minimum %F .

1 0
1 0
1 0
1
Fraction of
Fraction of
Fraction of
Fraction of
max. parameter max. parameter max. parameter max. parameter

0

p = 0.2

ChainCap=20.0

ChainCap=20.0

weighted
α-lex.
hybrid lex.

Fairness rule

Figure 11: Worst-case PoF and %F for 32 128-vertex random graphs. Parameters for each rule are α ∈ [0, 1], β ∈ [0, 20], and ∆ ∈ [0, u(ME )]. Rows correspond
to edge success probabilities from 0.1 to 1.0; columns correspond to different chain caps: 0, 3, and 20.

0.0

0.2

p = 0.5

ChainCap=10.0

0.4

0.0

0.2

0.4

0.0

0.2

0.4

0.0

0.2

0.4

p = 0.2

ChainCap=5.0

Max. PoF

Min. %F
Min. %F
Min. %F

ChainCap=0.0

ChainCap=10.0

Max. PoF

ChainCap=5.0

Min. %F

ChainCap=0.0

