Department of Policy and Planning Sciences
Discussion Paper Series

No.1352

Dual Organ Markets: Coexistence of Living and
Deceased Donors

byHidekazu ANNO and Morimitsu KURINO

March 2018
Revised December 2020

UNIVERSITY OF TSUKUBA
Tsukuba, Ibaraki 305-8573
JAPANDual-Organ Markets:
Coexistence of Living and Deceased Donors ∗Hidekazu Anno †Morimitsu Kurino ‡December 2, 2020

Abstract
To overcome the worldwide shortage of deceased-donor organs, the medical community has developed various modalities of transplantation. For dual-organ transplantation, the shortage is serious as the modality requires two donors for a single patient.
Lung transplantation, a representative example of dual-organ transplantation, is the
only treatment for patients in the final stage of a chronic lung disease. Prior to April
2015, there were only two types of transplantation available: deceased-donor transplants and living-donor transplants. Ergin, Sönmez, and Ünver (2017) have proposed
the idea of exchanging donors exclusively for living-donor lung transplantation. The
new technology, called hybrid transplantation, is now available as evidenced as Dr. Otoand his team at Okayama University Hospital successfully transplanted a deceased lungand a lobe of live lung to one patient at the same time. As the modality itself reveals
the importance of simultaneously operating the deceased- and living-donor markets,
we study the market with both deceased- and living-donors. In particular, we point∗

We would like to thank Tayfun Sönmez and Utku Ünver for bringing the topic of donor exchange tous and for their continuous support; Eizo Akiyama, Tomohiro Koda, Fuhito Kojima, Taro Kumano, Maiko
Shigeno, and Akiko Yoshise for their comments. We are grateful for comments by participants at Keio,
Kyoto, Sophia U., Tokyo U. of Science, WZB Berlin, and the 13th Meeting of the Society of Social Choiceand Welfare. In particular, we would like to thank Takahiro Oto for giving us numerous useful commentsfrom his expertise. Hidekazu Anno gratefully acknowledges JSPS KAKENHI Grant Number 18K12741.
Morimitsu Kurino acknowledges financial support from JSPS KAKENHI Grant number 18H00830. Allremaining errors are our own.
†
Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Tennodai, Tsukuba,
Ibaraki 305-8573, Japan; e-mail: anno.hidekazu.fp@u.tsukuba.ac.jp‡
Department of Economics, Keio University, 2-15-45 Mita, Minato-ku, Tokyo 108-8345, Japan; e-mail:kurino@econ.keio.ac.jp

1out that the hybrid transplantation opens up a new type of donor exchange. We investigate a mechanism of organizing transplants in terms of eﬃciency, fairness, andincentive-compatibility.
Journal of Economic Literature Classification Numbers : C78, D47, D71.
Keywords: Market design; Multi-unit demand matching problem; Hybrid lung transplantation; Japanese mechanism; Priority mechanism.

1

Introduction

To overcome the worldwide shortage of deceased-donor organs, the medical community has
developed various modalities of transplantation. For dual-organ transplantation including
lung transplantation, dual-graft liver transplantation, and simultaneous liver-kidney transplantation, the shortage is serious as the modality requires two donors for a single patient.
This paper studies how to operate these markets when both deceased- and living-donors areavailable.
Lung transplantation, a representative example of dual-organ transplantation, is the
only treatment for patients with end-stage lung diseases. As of October 31, 2020, 430
patients were registered on the waiting list for deceased-donor lung transplants in Japan,
while 79 patients received transplants in 2019.1 Deceased-donor transplantation uses one
or two lungs of a deceased donor to replace the diseased lungs of a patient.2 Because
the number of deceased donors is historically low for various reasons, the Japanese medical
community has developed live donor lung transplantation which needs two living donors eachof whom donates one lobe out of five to their intended recipient. These transplants have been
conducted on approximately 10 to 20 patients a year in recent years.3 For the liver case, it isreported that about 400 dual-graft transplants had been conducted till 2017 in South Korea(Song et al., 2017). Although they are a substantial source for transplantation, living donors
are conventionally constrained to being relatives of patients.4 Moreover, they are medically1

The cited data are available on the Japan Organ Transplant Network homepage. In particular, theformer is on https://www.jotnw.or.jp/data/, while the latter is on https://www.jotnw.or.jp/data/offer.php?year=2019. These were retrieved on November 18, 2020.
2
We refer to the donor by the male personal pronoun and to the patient by the female personal pronoun.
3
See the Factbook by the Japan Society for Transplantation, http://www.asas.or.jp/jst/pdf/
factbook/factbook2019.pdf, accessed on September 15, 2020.
4“Conventionally” means that this practice is not illegal, but it is followed by the medical community as
the ethical guideline published in the Japan Society for Transplantation. A transplant from non-relativesof a patient needs special permission in hospitals conducting the transplant. The guideline is available on
http://www.asas.or.jp/jst/about/about12.html, accessed on March 5, 2018.

2

constrained to being compatible with patients of blood type, tissue type, sizes, etc. These
constraints are diﬃcult to meet as a patient needs two compatible relatives. To overcome
such diﬃculties, Ergin, Sönmez, and Ünver (2017) recently proposed a novel transplantation
modality of donor exchange — a between-patients exchange of the incompatible donors —by applying the same idea for kidney exchange (Rapaport, 1986; Roth, Sönmez, and Ünver,
2004, 2005). Due to the multi-unit demand, the application is theoretically non-trivial andis practically important as Ergin, Sönmez, and Ünver (2017) show the potential increase oflung transplants from roughly 80 to 260%, depending on the size of the exchange, using theJapanese data.5
Another innovative transplant, called hybrid transplantation, has been successfully conducted for liver by Dr. Lee and his colleagues in 2000 (Lee et al., 2001) and for the lung by
Dr. Oto and his colleagues in 2015.6 The hybrid transplantation uses one graft of a living
donor and one graft of a deceased donor,7 which is one of a key modality for patients who
could not receive transplants through conventinal modalities.
We incorporate the possibility of hybrid transplantation for donor exchange in lungtransplants, extending the Ergin, Sönmez, and Ünver (2017) model which exclusively takes
up living-donor transplantation for donor exchange. This extension not only practically increases the number of saved patients but it also opens up a new type of theoretical challenge.
Let us discuss its practical importance and then the theoretical challenge.
A patient with only one compatible donor has an obvious benefit from hybrid transplantation. There might also be a situation in which two patients, each with two incompatible
donors, cannot exchange donors for living-donor transplants but can do so under hybridtransplantation. Hybrid transplantation can enhance a living-donor exchange in the sensethat patients who could not participate in the swapping of donors can have a living-donortransplant (see Figure 1). Moreover, if we consider only two-way exchange under a livingdonor transplantation, O-blood type patients do not benefit from donor exchange (Lemma
1 in Ergin, Sönmez, and Ünver, 2017). However, with the introduction of hybrid transplantation, such patients can receive transplants (see Figure 1).
Taking into account hybrid transplantation poses several new theoretical challenges. The
model we introduce has one deceased donor and finitely many patients who bring a number of

5

The numbers are for 50 patients. See Table II in Ergin, Sönmez, and Ünver (2017).
See the oﬃcial news at Okayama University, https://www.okayama-u.ac.jp/eng/news/index_
id4469.html. The web was accessed on January 6, 2019.
7
One of the biggest diﬀerence between lung and liver transplantation is that the main modality for lungis the dual-graft transplant while that of liver is the single-graft one.
6

3

Figure 1: Benefits from hybrid transplantation.

Note: In the figure, one lung from the deceased donor, dc , is available, patient 1 of blood type A has adonor of blood type O, and patient 2 of blood type O has two donors with blood types A and O. The
allocation indicated by the arrows shows that with donor exchange, patient 1 receives the hybrid transplant,
while patient 2 the living donor transplant. Note that without the hybrid transplantation, patient 2 has notransplant opportunity.

their relatives as (compatible or incompatible) living donors.8 A patient may have multi-unit
demand as she is assigned two living donors for living-donor transplantation, or is assigned
one lung from a deceased donor and one graft from a living donor for hybrid transplantation,
unlike the standard matching model with unit demand. Organs are indivisible goods, a
deceased organ is taken to be a social endowment (common ownership), and living donors
are those owned by patients (private ownership). Thus, a patient, who forms preferences
over the transplantation types, can simultaneously participate in the two “dual” markets
for deceased donors and living donors.9 Thus, a hybrid transplantation treatment naturally
leads to the model with mixed ownership. Our model is the first real-life application of amatching problem with multi-unit demand and mixed ownership.10 A desirable mechanism
in such a model has not been discussed.
We search for a matching mechanism — a procedure of assigning donors to patients fortransplants based on their medical types and preferences — which should have the desirable
properties of individual rationality, Pareto eﬃciency, fairness, and the incentive compatibility of strategy-proofness. We focus on individually rational allocations in which each patient
receives an assignment at least as good as the no-transplant. The Pareto eﬃciency is thestandard one, requiring that no one could be improved without hurting others. We propose
8

The assumption of one deceased donor reflects the situation of countries with relatively few deceased
donors. Such an example is Japan which has at most 97 deceased donors a year from 1997 to 2019. Since thearrival date of a deceased donor is not controllable, the assumption is appropriate if we operate a mechanism
every day or every time when the pool of patients and donors is updated.
9
We use the term “dual-organ markets” for the following two meanings. First, it expresses the multi-unit
demand used by Ergin, Sönmez, and Ünver (2017). Second, patients simultaneously participate in the twomarkets for deceased donors and living donors.
10
An exception is Roth, Sönmez, and Ünver (2004) for mixed ownership. In their kidney exchange model,
they have living donors and the waiting option of putting patients on higher priority in the waiting list ofpatients. The waiting option implicitly expresses the treatment of deceased donors. On the other hand, we
explicitly model the situation in which a patient can have access to and use resources in both the markets
for living donors and those for deceased donors.

4

a notion of ⪰-fairness, based on a priority ordering ⪰ over patients, which represents thepriority to receive the organ from the deceased donor. A ⪰-fair allocation is the one without
justified envy, adjusted to our environment from the school choice problem (Balinski and
Sönmez, 1999; Abdulkadiroğlu and Sönmez, 2003). Roughly speaking, justified envy meansthat some patient can improve with the deceased donor’s organ assigned to a lower-priority
patient. Finally, the strategy-proofness we use is also the standard one where truth-tellingis a weakly dominant strategy of each patient in the induced preference revelation game.
We examine the current Japanese mechanism that is only for assigning deceased lungs.
We show in Proposition 3 that it is neither strategy-proof nor ⪰-fair, though it is individually rational and Pareto eﬃcient. Instead, we adapt a priority mechanism consideredin the literature, in particular Roth, Sönmez, and Ünver (2005)’s mechanism for a kidneyexchange. In the priority mechanism, the highest-priority patient selects all of her favorite
individually rational allocations, the second-highest patient selects all of her favorites among
those selected by the highest-priority patient, and so on. Then, we show in Theorem 1 thatin regimes without donor exchange, including the current Japanese one, the priority mechanism recovers strategy-proofness and ⪰-fairness, still keeping individual rationality andPareto eﬃciency. However, once we allow for donor exchange, the strategy-proofness will beviolated (Proposition 4) because a lower-priority patient can, by misreporting, narrow down
the higher-priority patient’s allocations by hiding her own donors and then obtain more
preferable deceased transplants. It turns out that such a negative result is from a general
impossibility result (Theorem 2) under any regime with donor exchange: no mechanism
is individually rational, Pareto eﬃcient, ⪰-fair, and strategy-proof. Note that the priority
mechanism satisfies all of the properties except for strategy-proofness. We observe thatmisreporting is risky in the priority mechanism in that if the medical types were diﬀerent,a misreporting patient would get no-transplant instead of some transplant. With this observation, we introduce uncertainty over the medical type of the deceased donor as well asother patients’ medical types and preferences. Then, the priority mechanism is shown to berobust against manipulation, that is, the truth-telling profile is a Bayesian Nash equilibrium(Theorem 3).
We introduce the dual-organ markets in Section 2. The model covers dual-donor organ
exchange (Ergin, Sönmez, and Ünver, 2017) for dual-graft liver transplantation, bilateralliving-donor lung transplantation, and simultaneous liver-kidney transplantation, with a
new structure of hybrid transplantation when both deceased and living donors coexist.
Our description in the paper is for lung for simplicity, but the model is applicable to any
other organ by selectively ignoring some parts of the model. In Section 3, we provide and5investigate several properties of mechanisms. Section 4 discusses our main results regarding
the current Japanese mechanism and the priority mechanism. Finally, Section 5 concludes.
Omitted proofs are given in Appendix.

1.1

Related literature

In the matching problem with unit demand, a model with social endowments is called ahouse allocation problem (Hylland and Zeckhauser, 1979); the one with private ownershipis called a housing market (Shapley and Scarf, 1974); the one with mixed ownership is ahouse allocation problem with existing tenants (Abdulkadiroğlu and Sönmez, 1999) which
Roth, Sönmez, and Ünver (2004) apply to the donor exchange for kidney transplantation.
In dichotomous preferences, Roth, Sönmez, and Ünver (2005) further investigate a priority
mechanism under private ownership in which higher-priority patients narrow down theirfavorite allocations. For the liver market, Ergin, Sönmez, and Ünver (2018) consider theunit-demand of a patient with the possibility that a donor can choose one of her left andright lobes. Thus, in this regard, their model is diﬀerent from the kidney exchange model
as well as ours.
For multi-unit demand, a matching problem with social endowment is studied by, forexample, Klaus and Miyagawa (2001), Pápai (2001) and Budish and Cantillon (2012), while
the one with private endowment is studied by Pápai (2007). Its special case where objects
are exogenously separated by types is a multiple-type market (e.g., Moulin 1995; Konishi,
Quint, and Wako 2001; Anno and Kurino 2016).
The most related paper is Ergin, Sönmez, and Ünver (2017) which is modeled as amatching problem with multi-unit demand and private endowment. Their model is a special
case of our model when a deceased donor is not compatible with any patients. In this case,they focus on maximal matching instead of a mechanism. Our priority mechanism canachieve their maximal matching for a two-way donor exchange, too.

2

Model: Dual-Organ Markets

2.1

BasicsWe describe the model for dual-organ markets. Although our description of the model isbest fit for a more complex lung market with multi-unit demand, markets for the kidney

6and liver with single-unit demand can be easily adjusted with a trivial modification.11
There is one deceased donor who donates (one or two grafts of) her organs and finitely
many patients each of whom accompanies living donors. All of the patients and donors
have (medical) types for transplantation which determines which donor can donate to which
patient. All patients have a priority for the organ(s) from a deceased donor which is typicallydetermined by their waiting time. Formally, a model is a list (N, {DiL }i∈N , DC , (T, ), θ, ⪰)which satisfies the following conditions:
1. N := {1, . . . , n} is a finite set of patients. We suppose that with enough medical
knowledge each patient has the authority to decide for transplantation.12 We assume
that N contains at least two patients.
2. For each i ∈ N , DiL is the finite set of patient i’s living donors. With this condition,
patients may have various number of living donors.13 We assume that DiL ∩ DjL = ∅for all i, j ∈ N with i ̸= j. That is, no living donor is shared by two patients. Since
the main focus of this paper involves living-donor exchange, we assume that at least
two patients have multiple living donors. Let DL := ∪i∈N DiL be the set of all living
donors in the market.
3. DC := {dc } where dc is the deceased (cadaveric) donor.14 We assume that the deceased
donor is not one of the donors registered as a living donor of a patient, i.e., DC ∩ DL =∅. We denote D := DL ∪ DC .
4. (T, ) is the medical type space defined as the product space of given K kinds ofcomponent medical type spaces {(Tk , k )}K
k=1 . For each k ∈ {1, . . . , K}, Tk is a
finite set of k-th component types equipped with a reflexive binary relation ⊵k wheretk ⊵k t′k means that tk is medically compatible with t′k . For example, a donor withblood type O can donate to a patient with blood type A, not vice versa. This medical
11

Several exceptional cases with dual-graft liver transplants are reported. For example, see Lee et al.
(2001) for hybrid transplant and heterodoxical dual-graft living donor transplant, and Soejima et al. (2008)
for orthodoxical dual-graft living donor transplant. Here, however, we understand the liver market as themarket with single-unit demand, since it is the main modality in that market.
12This is because a patient can be considered to represent a team with her doctor. She does not necessarily
know nor understand her own health status for transplantation, but she makes decision about whether totake a transplant. On the other hand, a medical doctor knows her health status, but cannot force her toagree to a transplant.
13
Note that this setting generalizes the assumption of Ergin, Sönmez, and Ünver (2017) in which eachpatient has exactly two living donors.
14
See Footnote 8 for the justification of this assumption of one deceased donor.
We mainly use the adjective “deceased” instead of “cadaveric” for the status of the donor. However, we
use the notation dc to denote the deceased donor to avoid the puzzling notation dd .

7

∏compatibility is written as O ⊵k A and A ̸⊵k O. For each {t, t′ } ⊆ T = K
k=1 Tk , a′donor of type t is medically compatible with a patient of type t if and only if for eachk ∈ {1, . . . , K}, tk ⊵k t′k . This is denoted as t ⊵ t′ .
In case a component medical type space is defined by blood types, written as (TB , B ),TB := {O, A, B, AB}, andB := {(O, A), (O, B), (O, AB), (A, AB), (B, AB)} ∪ {(X, X) | X ∈ B}.
We call (TB , B ) the ABO type space. We assume for exposition that the collectionof component type spaces {(Tk , k )}K
k=1 contains the ABO type space.
5. θ = (θdc , θ1 , . . . , θn ) represents the medical status of all agents. For brevity but slight
confusion, we call it a type profile.
• θdc := (θdc q , θdc T ) ∈ {1, 2} × T is the medical status, or type, of the deceased
donor where the deceased donor can supply θdc q units of grafts and is of medical
type θdc T .15 Let Θdc := {1, 2} × T denote the set of types of the deceased donor.
• For each i ∈ N , θi = (θi (i), (θi (d))d∈DiL ) ∈ T {i}∪Di is the medical status, ortype, of patient i which indicates her own medical type θi (i) ∈ T and her living
Ldonors’ medical types (θi (d))d∈DiL ∈ T Di . We assume that the set of living
donors of patient i contains at most one donor whose type is compatible withpatient i. That is, for all d, d′ ∈ DiL , θi (d)  θi (i) and θi (d′ )  θi (i) imply d = d′ .
This is because a patient would conduct a living-donor transplant with her own
compatible donors if she had at least two compatible donors.16 In other words,
our model captures the market with patients who cannot have a transplant with
their own donors. Note that this simplification is also employed in Ergin, Sönmez,
and Ünver (2017).
L

15

A unit of donated organ, called a “graft,” is diﬀerent according to the kind or source of the organ underconsideration. As for the lung, the human body is equipped with a left and right lung, where each of them iscomposed of smaller parts called “lobe.” In practice, a deceased donor donates both the left and right lung,
except for the infected side if one exists, where each of them can be transplanted to diﬀerent patients, whilea living donor cannot donate more than a lobe of her lungs for health reasons. Following the convention,
by a unit of graft donated from the deceased donor, we mean a lung (left lung or right lung), while by a unitof graft donated from a living donor, we mean a lobe of lung. As for the liver, the human body is equippedwith a liver consisting of a left and right lobe. In practice, a deceased donor donates her whole liver to
one recipient in Japan, while a living donor cannot donate more than a lobe of her liver for health reasons.
Following the convention, by a unit of graft donated from the deceased donor, we mean a whole liver, whilea unit of graft donated from a living donor, we mean a lobe of liver. As for the kidney, the human body isequipped with two kidneys, and its unit is understood in an obvious way.
16
The modality of transplantation will be introduced in the next subsection.

8• Let Θi be the set of types of patient i. Let Θ := Θdc × Θ1 × . . . × Θn be the∏set of type profiles. For each i ∈ N , let Θ−i := Θdc × j̸=i Θj . For notational
simplicity, given θ ∈ Θ, let θ(i) denote θi (i) for each i ∈ N , and θ(d) denote θi (d)for each i ∈ N and each d ∈ DiL .
6. The symbol ⪰ represents a priority order for patients. Mathematically, it is a complete,transitive and anti-symmetric binary relation over N .
A dual-organ market is the model above together with a preference profile of patients.
We will introduce the preferences after defining allocations in the next subsection.

2.2

Allocation

To describe the notion of assignments, we first clarify what kinds of transplants are potentially available for each patient i ∈ N under a given type profile θ. A transplant for patientLC
i is expressed by a pair xi = (xC
i , xi ) where xi is the number of grafts from the deceased
donor and xLi is the set of living donors who contribute the transplant. Given θ ∈ Θ, weclassify available transplants as follows.
1. Deceased-donor dual-graft transplantation: Transplanting two grafts from thedeceased donor to a patient. The set of such transplants for patient i is denoted by
Xi20 (θ) :=
{(2, ∅)}

if θdc q = 2 and θdc T  θ(i),∅otherwise.

.

2. Deceased-donor single-graft transplantation: Transplanting a single graft fromthe deceased donor to a patient. The set of such transplants for patient i is denotedby
{(1, ∅)} if θ  θ(i),dc T
10
Xi (θ) :=∅otherwise.
3. Living-donor dual-graft transplantation: Transplanting two grafts from two living donors, one for each, to a patient. The set of such transplants for patient i isdenoted by{}
L

Xi02 (θ) :=(0, xL )i) xL ∈ 2D and |xL | = 2, andii) ∀d ∈ xL , θ(d)  θ(i)9

4. Hybrid transplantation: Transplanting two grafts, one from the deceased donor
and another from a living donor, to a patient. The set of such transplants for patient
i is denoted by

Xi11 (θ) :=

{
}
L
DL
L

i)
x
∈
2
and
|x
|
=
1,
and

 (1, xL )if θdc T  θ(i),∅otherwise.

ii) ∀d ∈ xL , θ(d)  θ(i)This was newly conducted at Okayama University Hospital for lung transplantation.
In particular, let X̃i11 (θ) be the set of hybrid transplants with i’s own donor, i.e.,X̃i11 (θ) := {(1, xL ) ∈ Xi11 (θ) | xL ⊆ DiL }.
5. Null transplantation: The transplant (0, ∅), called the null transplant, meansthat patient i will not receive any transplant. The set Xi00 (θ) = {(0, ∅)} denotes theone that contains only the null transplant.17
Then, the set of potentially possible transplants for patient i under θ, Xi (θ), is defined asfollows.18
Xi (θ) := Xi20 (θ) ∪ Xi10 (θ) ∪ Xi11 (θ) ∪ Xi02 (θ) ∪ Xi00 (θ).
We will later describe by preferences which transplant is suﬃcienta patient.
( or not for) saving
∏
θ
θ
θC
θL
Given a type profile θ ∈ Θ, an allocation, a = (ai )i∈N = (ai , ai )∈ i∈N Xi (θ),
i∈N

describes a distribution of transplants among patients. In particular, we say that aθi ∈ Xi (θ)
is an assignment of patient i at aθ , or a transplant of patient i at aθ . We impose three
conditions on allocations. The first is a physical constraint: the number of grafts of dc usedat the allocation cannot exceed the number of grafts supplied by dc . That is,∑aθCi ≤ θdc q .

(1)

i∈N

The second is also a physical constraint: the number of grafts that a living donor canL∈ 2D describes who provides adonate is at most one. Note that for each patient i, aθLi17Actually, the set Xi00 (θ) does not depend on the type profile θ. However, for notational consistency, we
do not use the notation without the reference for the type profile such as Xi00 .
18
When we interpret our model as a kidney transplant market, the set of potentially possible transplants isdefined as Xi (θ) := Xi10 (θ) ∪ Xi01 (θ) ∪ Xi00 (θ) while for the liver market Xi (θ) := Xi20 (θ) ∪ Xi01 (θ) ∪ Xi00 (θ),
where Xi01 (θ) denotes the set of living-donor transplants by using a single living donor. Note that thedeceased donor in the kidney market can generate two transplants for the market since two kidneys canbe delivered to diﬀerent recipients, while the deceased donor in the liver market can generate only one
transplant since the left and right lobes from the donor are conventionally transplanted to a single recipient.

10Figure 2: Inflow and outflow are not balanced.

graft to i. Thus, to formalize the second condition, we just need the requirement that aliving donor should not be included in two living-donor assignments at an allocation. Thatis,θL∀i, j ∈ N with i ̸= j, aθLi ∩ aj = ∅.

(2)

The last condition is motivated by the allocations described in Figure 2. At the allocationin the left figure, patient i’s donor di provides a graft to patient j, even though his own
patient i does not receive a transplant. This allocation would fail to achieve the goal of donor
di who participates in the market to relieve patient i. At the allocation in the right figure,both patients i and j receive transplants. However, their treatments are very diﬀerent.
Patient i receives a donation from dj in exchange for the donation by donors’ di2 and di3 .
This situation might arise when the type of patient i is so rare that she cannot find any
compatible donor except for di1 . In this case, if i finally finds dj as her compatible donor,
she and her own donors might be willing to accept dj in exchange for donors di2 and di3 .
However, this type of exchange has a flavor of price mechanism which in most countries isstrictly prohibited for the distribution of organs.
In this paper, we will not be involved in a radical interpretation of an allocation that
calls for a drastic change in organ transplant legislation. To construct an allocation system
without controversial concepts, we employ the cautious condition, requiring that each patient’s benefit from the market in terms of the number of grafts from others’ living donors
should not exceed the contribution of her own living donors to other patients in terms ofthe number of grafts. That is,∀i ∈ N,

L
aθL
i \Di

≤

DiL ∩

(

∪j̸=i aθL
j

)
.

(3)

The left-hand side of the inequality is the number of grafts from other patients’ living donors,
while the right-hand side is the number of i’s own donors who donate to other patients. We
call this condition the balanced condition. Note that the allocations in Figure 2 are
11

excluded because patient j violates the condition. Let us emphasize that this condition is
implicitly employed in the Ergin, Sönmez, and Ünver’s (2017) living-donor exchange model.
Thus, our model with deceased and living donors under the balanced condition is a naturalextension of their model. We denote the set of all allocations under θ by A(θ). Moreover,let A be the set of all potentially possible allocations, i.e., A := ∪θ∈Θ A(θ).
Our notion of allocations describes not only which patients are assigned organs and lobes
from donors, but also which transplants are conducted. This point is technically important.
For example, if the assignment (1, {di }) for patient i just described the former, it would not
be clear whether the actual transplant is single-graft or hybrid. For this reason, we interpretthe assignment aθi of agent i as the conducted transplant, and assume that the transplantusing all of the grafts described in aθi will be conducted.
Remark 1 (Organs not described in an allocation). Based on the above interpretation, we
explain how organs that do not appear in an allocation are treated.
∑∑
θC
1. At an allocation aθ ∈ A(θ), if i∈N aθCi < θdc q , then θdc q −i∈N ai units of deceased
grafts are disposed of at allocation aθ .
2. At an allocation aθ ∈ A(θ), if a living donor di ∈ DiL does not appear in any patient’s
θL
assignment i.e., di ̸∈ aθL
1 ∪ . . . ∪ an , then di does not undergo surgery at the allocation.
As a consequence of conditions imposed on allocations, we have the following simple
pattern of allocations, i.e., the balanced condition holds with equality.
Proposition 1. Under any type profile θ ∈ Θ, every allocation aθ ∈ A(θ) is balanced in thefollowing sense.
(
)
L
L
θL
∀i ∈ N, aθL
\D
=
D
∩
∪
a
.
j̸=i jiiiNamely, for each i ∈ N , the number of grafts donated to i from other patients’ living donors
is equal to the number of i’s living donors who donate a graft to other patients.

2.3

Preference

We formulate the preferences of patients. To this end, it is useful to have the notations
R(Z) and P(Z) for any finite set Z: R(Z) is the set of complete and transitive binary
relations on Z, while P(Z) is the set of complete, transitive, and anti-symmetric binary
relations on Z.
We assume that each patient has a preference in the set of transplantation types {20, 10, 11, 02, 00},
where 20, 10, 11, 02, and 00 stand for deceased-donor dual-graft, deceased-donor single-graft,12

Hybrid transpl.

unacceptable
acceptable

Donation of living donors to non-relatives
unacceptable
acceptable
Regime O
Regime E
Regime H
Regime EH

Table 1: Four regimes
hybrid, living-donor dual-graft, and null transplantation, respectively. That is, each patienti ∈ N has a strict preference Ri ∈ P({20, 10, 11, 02, 00}) over the set of transplantation
types. Note that the formulation of a preference is free from a given type profile θ. Let
R be the set of preferences, i.e., R := P({20, 10, 11, 02, 00}). For each Ri ∈ R, the antisymmetric part and symmetric part of Ri are denoted by Pi and Ii , respectively. For
each Ri ∈ R, a transplantation type α is acceptable at Ri if she prefers α to the nulltransplantation 00. Let Aci (Ri ) be the set of acceptable transplantation types at Ri , i.e.,Aci (Ri ) := {α | α Pi 00}.
Based on a preference Ri ∈ R over transplantation types, we induce a preference overavailable transplants under a type profile θ. Namely, given θ ∈ Θ, we assume that a patienti ∈ N with her preference Ri ∈ R has a preference Ri (θ) ∈ R (Xi (θ)) defined as follows;∀α, β ∈ {20, 10, 11, 02, 00}, ∀xi ∈ Xiα (θ), ∀yi ∈ Xiβ (θ), xi Ri (θ) yi ⇔ α Ri β.
Note that in the induced preference Ri (θ) patients are indiﬀerent between two transplants ina same-type transplantation. Without any confusion, we abuse the notation Ri to represent
Ri (θ). That is, we write xi Ri yi instead of xi Ri (θ) yi for two transplants xi , yi ∈ Xi (θ)
under a type profile θ.
Given a type profile θ, a transplant xi ∈ Xi (θ) is called acceptable for agent i with her
preference Ri if she prefers s transplant xi to nothing, i.e., xi Pi (0, ∅). Let Aci (Ri ; θ) be theset of acceptable transplants for agent i with Ri under θ.
A preference profile is a list R = (Ri )i∈N ∈ RN consisting of the preferences of all
patients. The set of all preference profiles RN is called the preference domain.

2.4

Regimes: Legal constraints

The feasibility of an allocation is determined not only by medical technologies but also bysocial environments. By social environment we mean legal and ethical ones that stipulate
whether a medically possible transplant is socially acceptable and implementable without
much of an administrative and monetary burden. In our paper we examine two types of13technologies that are constrained by social environments: (i) hybrid transplantation, and(ii) donation from living donors to non-relative patients. According to how these constraints
are treated, we consider the following 2 × 2 kinds of regimes (see Table 1).
2.4.1

Regime O

Regime O is the environment before the introduction of the living-donor exchange andhybrid transplantation technology.19 Since each patient cannot have a living-donor transplant with her own donors, only deceased-donor (dual-graft or single-graft) transplantationis possible. Thus, given θ ∈ Θ, an allocation aθ ∈ A(θ) is feasible under regime O if foreach i ∈ N , aθi ∈ Xi20 (θ) ∪ Xi10 (θ) ∪ Xi00 (θ). Let AO (θ) be the set of feasible allocations at
θ under regime O.
2.4.2

Regime E

Regime E is the environment in which a living-donor exchange is introduced to the original
market. Donor exchanges (Ergin, Sönmez, and Ünver, 2017) are allowed, in addition to
deceased-donor (dual-graft or single-graft) and living-donor transplantation. Thus, givenθ ∈ Θ, an allocation aθ ∈ A(θ) is feasible under regime E if for each i ∈ N , aθi ∈Xi20 (θ) ∪ Xi10 (θ) ∪ Xi02 (θ) ∪ Xi00 (θ). Let AE (θ) be the set of feasible allocations at θ underregime E.
2.4.3

Regime H

Regime H is the environment where hybrid transplantation technology is introduced tothe original market. The hybrid transplant between a patient and one of her own donors
is allowed, in addition to deceased-donor (dual-graft or single-graft) transplantation. Thus,
given θ ∈ Θ, an allocation aθ ∈ A(θ) is feasible under regime H if for each i ∈ N ,aθi ∈ Xi20 (θ) ∪ Xi10 (θ) ∪ X̃i11 (θ) ∪ Xi00 (θ). Let AH (θ) be the set of feasible allocations at θunder regime H.
2.4.4

Regime HE

Regime HE is the environment in which both the living-donor exchange and hybrid transplantation technology is introduced to the original market. All types of (deceased-donor,
living-donor, hybrid) transplantation are possible. Thus, given θ ∈ Θ, every allocation19

Because this is the “original” state of the market, we call the regime “O”.

14

Figure 3: Hybrid exchange opens up new patterns of allocation.

aθ ∈ A(θ) is feasible under regime HE. Let AHE (θ) be the set of feasible allocations at θunder regime HE. The new patterns of exchange that our paper advocates are exchangesof donors for hybrid transplantation. In the left allocation in Figure 3, both patients i andj receive a hybrid transplant with the other’s donor. In the middle in Figure 3, patienti receives a hybrid transplant while j receives a living-donor transplant. This allocationsuggests that the hybrid transplant makes the living-donor transplant possible.20 Theoretically, the number of living-donor transplants caused by a hybrid transplant can be any large
number. On the right in Figure 3, three living-donor transplants are implemented.
Remark 2. By definition, we have the following relations among the sets of feasible allocations under various regimes.
AE (θ)⊆AHE (θ)⊇⊆⊇AO (θ)AH (θ)

2.5

Dual-organ markets under various regimes

Let us summarize our model. A dual-organ market under regime Y ∈ {O, E, H, HE}consists of the following components:
1. (N, {DiL }i∈N , DC , (T, ), θ, ⪰) as described in Section 2.1.
2. R = (Ri )i∈N ∈ RN , a preference profile as described in Section 2.3;
3. AY (θ), the set of feasible allocations under regime Y as described in Section 2.4.

20

The literature on kidney exchange considers the system that allows patients to exchange their donors
with the right to receive a deceased kidney (Roth, Sönmez, and Ünver, 2004). Note that it contains aliving-donor kidney and deceased-donor kidney exchange. What is new in the middle allocation in Figure 3
is that patient i who receives a hybrid transplant exchanges her living donor with patient j’s living donor.

15

We assume that there is a clearinghouse whose goal is to distribute transplants among agentsin a “desirable” manner.21 To do so, it needs to collect the decentralized information on the• market participants’ type θ = (θi )i∈N and• preferences of patients R.
Together with the type of the deceased donor, the clearinghouse processes the informationin determining a feasible allocation.22 The procedure is called a mechanism. Formally, amechanism under regime Y is a function φ from RN ×Θ to ∪θ∈Θ AY (θ) such that for each(R; θ) ∈ RN ×Θ, φ(R; θ) ∈ AY (θ). That is, the clearinghouse has patients report their types
and preferences. Expressing the information by type and preference profile (R; θ) ∈ RN ×Θ,
the clearinghouse uses a mechanism φ to determine an allocation φ(R; θ) ∈ AY (θ) that is
feasible under regime Y .

3Properties of Mechanisms

In a general indivisible goods allocation problem, the desirable properties for a mechanism
to satisfy are individual rationality, eﬃciency, fairness, and incentive compatibility. We
introduce these properties for our dual-organ market. We fix a regime Y ∈ {O, E, H, HE}
throughout this section.

3.1

Individual rationality

We introduce individual rationality for our model. It is a condition on allocations in which
any patient does not hurt from participating in a market. Formally, we define:
Definition 1. Under regime Y , an allocation aθ ∈ AY (θ) is individually rational at(R; θ) ∈ RN × Θ if for each patient i ∈ N , aθi is at least as good as the null transplant at Ri .
We denote by I Y (R; θ) the set of all individually rational allocations at (R; θ). Moreover, amechanism under regime Y , φ, is individually rational if for each (R; θ) ∈ Θ × RN , theselected allocation φ(R; θ) ∈ AY (θ) is individually rational at (R; θ).

21

In the next section, we will discuss what allocations are desirable.
We assume that the type information of the deceased donor is known by the clearinghouse whenever a
deceased donor appears. This is natural because it is reported by a medical doctor who is in charge of thedeceased donor. The clearinghouse shares the information with the medical doctors in charge who are outof our model.
22

16

3.2

Eﬃciency

We define three notions of eﬃciency. The first is the standard notion of Pareto eﬃciency.
Under regime Y , an allocation aθ ∈ AY (θ) is Pareto eﬃcient at (R; θ) ∈ RN × Θ if there
is no allocation bθ ∈ AY (θ) such that for each i ∈ N , bθi Ri aθi , and for some i ∈ N , bθi Pi aθi .
A mechanism under regime Y , φ, is Pareto eﬃcient if for each (R; θ) ∈ RN × Θ, theselected allocation φ(R; θ) is Pareto eﬃcient at (R; θ).
We next introduce the notions of non-wastefulness for our dual-organ market. The standard notion of non-wastefulness is defined for indivisible goods allocation problems undercommon ownership and unit demand where no agent initially owns an object and an agent
consumes one object. The non-wastefulness means that “unused” objects cannot be assigned
to benefit some agent without aﬀecting anybody else’s assignment (Balinski and Sönmez,1999). On the other hand, our dual-organ market has mixed ownership and multi-unit demand. Thus, the unused objects available for a patient are disposed deceased lungs and alobe from one of her own donors who did not donate at the original allocation. Thus, eachpatient could potentially access to the unused objects in addition to the original assignment
without aﬀecting anybody else’s assignment. Although the set of better opportunities canbe well captured by the set of unused objects under unit demand, the appropriate extension
to our model with multi-unit demand and mixed ownership should include both unused
objects and the original individual assignment. If a patient finds a better transplant within
her potentially “accessible” objects, she might be better oﬀ by herself. The accessibility canbe captured by the following notion of induced allocations.
Definition 2 (Induced allocation). Given a type profile θ ∈ Θ and an allocation aθ =( θC θL )()θL(ai , ai ) i∈N ∈ A(θ), we define the induced allocation aθ = (aθCi , ai ) i∈N as follows:
For each i ∈ N ,
(
)
∑
θC
θC
θC
(i) ai := ai + θdc q − j∈N aj , andθLL
θL(ii) aθLi := ai ∪ {d ∈ Di d ̸∈ ∪j̸=i aj }.

In words, patient i’s induced grafts assignment aθCfrom the deceased donor is the sum ofithe number of grafts from dc she receives at aθ and the number of grafts from dc disposedat aθ . Patient i’s induced living-donor assignment aθLi denotes the union of her assignment
at aθ and her own donors who do not donate to other patient at aθ . Thus, aθi formalizes
the potentially accessible resources of patient i at aθ without changing the other patients’assignment. Note that aθi may not be an assignment. Now, we are ready to introduce
non-wastefulness.

17Definition 3. Under regime Y , an allocation aθ ∈ AY (θ) is wasteful at (R; θ) ∈ Θ × RN
if there exist i ∈ N and bi ∈ Xi (θ) such that (i) bi Pi aθi , (ii) (bi ; aθ−i ) ∈ AY (θ), and (iii)
θC
θ
Y
bC
and bLi ⊆ aθLi ≤ aii . Under regime Y , an allocation a ∈ A (θ) is non-wasteful at(R; θ) ∈ Θ × RN if it is not wasteful at (R; θ) ∈ Θ × RN .
The condition says that patient i cannot find (i) a better transplant (ii) which is allowed
under regime Y without aﬀecting others’ assignments, and (iii) which can be constructedwithin patient i’s accessible resources at aθ . For example, if aθi = (1, ∅) is a deceaseddonor single-graft transplant, then bi = (1, {di }) can be a hybrid transplant if patient i’s
compatible own donor di does not donate at aθ , i.e., di ∈ aLi .
In addition to being non-wasteful, an allocation is strongly non-wasteful if it maximizes
the number of grafts from the deceased donor used at the allocation within individually
rational allocations. Such an allocation is desirable because it expresses the view that
donated organs should be fully utilized, leading to respect for deceased donors. That is,
Definition 4. Under regime Y , an allocation aθ ∈ AY (θ) is strongly non-wasteful at(R; θ) ∈ RN × Θ if aθ is non-wasteful, and
∑

aθC
i =

i∈N

max

bθ ∈I Y (R;θ)

∑

bθC
j .

j∈N

We say that a mechanism under regime Y , φ, is (strongly) non-wasteful if for each(R; θ) ∈ RN × Θ, the selected allocation φ(R; θ) ∈ AY (θ) is (strongly) non-wasteful at(R; θ).
Example 1 (Non-wasteful but not strongly non-wasteful allocation). Let (T, ) = (TB , B ).23
Let θ ∈ Θ be such that θdc = (2, A) and θ(1) = θ(2) = A. Suppose also that for eachi ∈ N \{1, 2} and each d ∈ DL , θ(i) = O and θ(d) = AB. Let R ∈ RN be a preference
profile described by the following table.
R1
R2

10 00
20 00

···
···

Thus, patients 1 and 2 can only receive a donation from the deceased donor. Moreover,patient 1 only finds the single-graft transplant acceptable, and patient 2 only the dualgraft transplant acceptable. Consider an allocation aθ := ((1, ∅), (0, ∅)) where one graftis transplanted to patient 1, but the other is disposed so that patient 2 receives the null
23This assumption simplifies the description without any loss of generality as it corresponds to the assumption that all patients and donors have the identical medical type except for the ABO blood type.

18

Figure 4: Logical relationship among eﬃciency concepts

Under regime O or H.

Under regime E or HE.

Note: SNW stands for strong non-wastefulness, NW for non-wastefulness, and PE for Pareto eﬃciency.

transplant.24 Obviously, aθ is non-wasteful. However, one graft is disposed and the two
grafts can be transplanted to patient 2 in another individually rational allocation bθ :=((0, ∅), (2, ∅)) ∈ I Y (R; θ), and thus allocation aθ is not strongly non-wasteful. Note that
∑
∑
θC
θC
♢
i∈N bi .
i∈N ai = 1 < 2 =The following remark clarifies the logical relationship among our eﬃciency notions (seeFigure 4). For a proof, see the online appendix.
Remark 3. We have the following three statements. Sentences without a reference for regime
hold under any regime. Let (R; θ) ∈ RN × Θ.
1. If an allocation is strongly non-wasteful at (R; θ), then it is non-wasteful at (R; θ).
The converse is not true.
2. If an allocation is Pareto eﬃcient at (R; θ), then it is non-wasteful at (R; θ). The
converse is also true only if Y ∈ {O, H}.
3. There is no logical relationship between Pareto eﬃciency and strong non-wastefulness
under any regime Y ∈ {E, HE}.

3.3

Fairness

In our dual-organ market, we have a priority ⪰ given as one component of the market. The
priority expresses the right of patients receiving grafts from the deceased donor. In thissubsection we introduce the notion of fairness with respect to the priority.
We say that a patient i has a justified envy at an allocation if some lower-priority patient
j is assigned an organ from the deceased donor, and patient i can be made better oﬀ withthe deceased donor’s graft while keeping the same welfare except j. A fair allocation has
no patient having such justified envies. More formally,
The assignments for i ∈ N \{1, 2} are necessarily the null transplant (0, ∅), and they are thus omitted
in the description of the allocations.
24

19

Definition 5. Under regime Y , patient i ∈ N has a justified envy under an allocation
θCaθ ∈ AY (θ) at (R; θ) ∈ RN × Θ if there is bθ ∈ I Y (R; θ) such that (i) bθi Pi aθi , (ii) bθCi > aiand for each j ∈ N with j ≻ i, bθC= aθCand (iii) for each j ∈ N , aθj Pj bθj implies
j
j
θC
θ
Y
N
aθC
j > bj . Moreover, an allocation a ∈ A (θ) is ⪰-fair at (R; θ) ∈ R × Θ if no patient
has a justified envy under aθ at (R; θ).
We say that a mechanism under regime Y , φ, is ⪰-fair if for each (R; θ) ∈ RN × Θ, theselected allocation φ(R; θ) ∈ AY (θ) is ⪰-fair at (R; θ).
The following remark clarifies the logical relationship between ⪰-fairness and axioms
previously introduced. For a proof, see the online appendix.
Remark 4. We have the following two statements. Sentences without a reference for regime
hold under any regime.
1. ⪰-fairness does not imply individual rationality. Under any regime Y ∈ {E, HE},even the combination of Pareto eﬃciency and ⪰-fairness does not imply individual
rationality.
2. There is no logical relationship between ⪰-fairness and any one of the three eﬃciency
notions of non-wastefulness, strong non-wastefulness, and Pareto eﬃciency.
The following impossibility asserts that strong non-wastefulness is too demanding as aneﬃciency notion as long as we employ individual rationality and ⪰-fairness as basic axioms
for a mechanism.
Proposition 2. Under any regime Y ∈ {O, E, H, HE}, there exists (R; θ) ∈ RN × Θ suchthat no allocation is individually rational, strongly non-wasteful, and ⪰-fair at (R; θ).

3.4

Incentive compatibility

We employ strategy-proofness as our incentive compatibility condition. In our model, eachpatient has two pieces of private information about herself: type θi and preference Ri . These
information is not treated symmetrically, since the former is verifiable but the latter is not.
Thus, we assume that her reporting type θi is sincerely transmitted without manipulation,
while her reporting preference Ri may not be. In other words, preference reporting is the
only source of strategic manipulation.
Assumption 1 (Sincere reporting about types). Each patient reports her type sincerely.

20Under the above assumption, the following is a standard definition of strategy-proofness.
We discuss the importance of strategy-proofness in section 4.2.2.
Definition 6. A mechanism under regime Y , φ, is strategy-proof if for each (R; θ) ∈RN × Θ, each i ∈ N , and each Ri′ ∈ R, φi (R; θ) Ri φi (Ri′ , R−i ; θ).

4Main Results

In this section, we first investigate the mechanism currently used in the Japanese lungmarket under regime O.25 We show that the Japanese mechanism is individually rationaland Pareto eﬃcient, but it is neither ⪰-fair nor strategy-proof. Then, we propose priority
mechanisms that can be used for any regime, and show its prominence in our dual-organ
market. To define these mechanisms, we use the notation T op(⪰, M ) which is the highestpriority patient among those in the non-empty set M of patients. That is, for each i ∈ M ,T op(⪰, M ) ⪰ i.

4.1

Case study: The Japanese mechanism in the lung market

We describe the Japanese mechanism, denoted as φJ , that works only under regime O.26
To this end, we introduce the following notation. For each (R; θ) ∈ RN × Θ, let
N (R; θ) := {i ∈ N | (2, ∅) ∈ Aci (Ri ; θ) or (1, ∅) ∈ Aci (Ri ; θ)}be the set of all candidates of the deceased-donor transplantation.
The Japanese mechanism first looks at the preference of the highest-priority patient in
N (R; θ) when the deceased donor provides two units of lungs. Let us call the highest-priority
patient i1 . If i1 has multi-unit demand, the mechanism gives two units to the patient (Case1). On the other hand, if i1 has single-unit demand, the mechanism tries to pick another
patient with single-unit demand to allocate one unit for each. If the market has another
patient with single-unit demand, the mechanism selects the highest-priority patient among
them (Case 2). If i1 is the only patient with single-unit demand, the mechanism looks at
the second-most preferred transplant of patients. If there is at least one patient who can
accept a single-graft transplant (as the second-most preferred transplant), the mechanism
25

We formalize the mechanism based on the recipient selection rule described in http://www.jotnw.or.
jp/jotnw/law_manual/pdf/rec-lungs.pdf. A formal description of the mechanism is given in the online
appendix.
26
For a rigorous description of the Japanese mechanism, see Appendix A in online appendix.

21

picks the highest-priority patient among them, giving one unit to her and i1 for each (Case3). Finally, if i1 is the only patient with single-unit demand even when we consider the firstand second-most preferred transplant of all patients, then there are two subcases. If i1 canonly accept a single-graft transplant and there is at least one patient who needs a dual-grafttransplant, then the mechanism skips i1 , giving two units to the highest-priority patientamong the rest of the patients (Case 3.2.1). Otherwise, i.e., when i1 is the only patient
who is willing to accept a graft from the deceased donor, the mechanism gives one unit
to i1 , disposing of one unit (Case 3.2.2). Next we consider the case when only one unit oflung is donated by the deceased donor. The Japanese mechanism selects the highest-priority
patient among the unit-demand patients (Case 4).27 If there is no unit-demand patient thenthe mechanism picks the highest-priority patient who can accept a single-graft transplantas the second-most preferred transplant (Case 5).
The Japanese mechanism aspires to be a strongly non-wasteful allocation in a situation
where the compatible highest-priority patient has the unit demand after rejecting two units.
In that situation, if (1) there is no lower-priority patient with unit demand, and (2) at least
one lower-priority patient is demanding two units, then the mechanism skips the compatible
highest-priority patient and assigns two grafts to the compatible highest-priority patient who
needs two units to reduce the number of disposed grafts (see Case 3.2.1 in the definition of
the Japanese mechanism).28
However, the attempt to reduce the number of disposed grafts is not fully achieved by
the current mechanism, i.e., there is another situation where it fails to assign grafts in astrongly non-wasteful manner. Moreover, the anomalistic manner of the mechanism canbe a source of unfairness and strategic manipulation. These points are captured by thefollowing example.
Example 2 (Flaws of the Japanese mechanism). Suppose that there are two units of deceased grafts available, and also that only patients 1 and 2 have the same type as thedeceased grafts. That is, let θ ∈ Θ be such that θdc q = 2, θ(1) = θ(2) = θdc T , and for eachi ∈ N \{1, 2}, θdc T ̸  θ(i). Suppose also that patient 1 has a higher priority than patient 2,
i.e., 1 ≻ 2.
Flaw 1 (φJ is not strongly non-wasteful). Let R ∈ RN be a preference profile in Table
2. Then, N (R; θ) = {1, 2} and i1 = 1. Note that the highest-priority patient demands one
27

Not necessarily, the highest-priority patient in N (R; θ).
More precisely, this type of skip is not applied if the deceased donor is not one of the relatives of thecompatible highest-priority patient at Case 3.2.1. Since we assume that DC ∩ DL = ∅, this case is omitted
from the description of the Japanese mechanism.
28

22

Table 2: Preferences for Example 2
R1 10 20 00 · · ·R2 20 00 · · ·
R1′

10 00

···

unit. Thus, the mechanism tries to pick another patient who can accept a deceased-donor
single-graft transplant. Since 1) patient 1 is the only patient who can accept single-unit
transplantation even when we look at the first- and second-most preferred transplantationof all patients, and 2) the second-most preferred transplant is a deceased-donor dual-graft()
transplant, Case 3.2.2 in the definition is applied. Thus, φJ (R; θ) = (1, ∅), (0, ∅) , disposing()
of one unit of lung. However, since (0, ∅), (2, ∅) is individually rational at (R; θ), φJ (R; θ)
is not strongly non-wasteful at (R; θ).
Flaw 2 (φJ is not ⪰-fair nor strategy-proof ). Let R1′ ∈ R be a preference in Table 2.
Let R′ := (R1′ , R2 ). Then, N (R′ ; θ) = {1, 2} and i1 = 1. Again, the market does not havea patient, except for i1 , who can accept a deceased-donor single-graft transplant. Thus,
the Japanese mechanism considers the second-most preferred transplantation of patient 1.
Since on this occasion it is a null transplantation, Case 3.2.1 is applied. Thus, φJ (R′ ; θ) =((0, ∅), (2, ∅)). Higher-priority patient 1 would be better oﬀ from a graft assigned to lowerpriority patient 2 at φJ (R′ ; θ). Thus, φJ (R′ ; θ) is not ⪰-fair at (R′ ; θ).
Now consider the strategic deviation of patient 1 from R1′ to R1 . Then, the allocation()
selected at (R1 , R2 ; θ) = (R; θ) is (1, ∅), (0, ∅) (see the calculation at Flaw 1). Thus,
φJ1 (R1 , R2 ; θ) = (1, ∅) P1′ (0, ∅) = φJ1 (R1′ , R2 ; θ), which violates strategy-proofness.
♢
The following proposition summarizes the properties of the Japanese mechanism.
Proposition 3. Under regime O, the Japanese mechanism φJ is (i) individually rational,(ii) Pareto eﬃcient, (iii) not strongly non-wasteful, (iv) not ⪰-fair, and (v) not strategyproof.

4.2

Priority mechanism

We introduce a priority mechanism which extends Roth, Sönmez, and Ünver (2005)’s mechanism to our setting. Roughly speaking, in the mechanism agents select their favorite andindividually rational allocations among those selected by higher-priority agents. For its
definition, we need the following notation. Let σ : {1, . . . , n} → N be the bijection that23

represents the priority order. That is, for each i ∈ {1, . . . , n}, σ selects the i-th highestpriority patient, i.e., σ(1) ≻ σ(2) ≻ · · · ≻ σ(n).
Definition 7 (Priority mechanism). The priority correspondence under regime Y ,ΦY , is the nonempty-valued correspondence from RN ×Θ to ∪θ∈Θ AY (θ) that selects feasible
allocations in AY (θ) for each (R; θ) ∈ RN × Θ as follows.
Round 0: ΦY0 (R; θ) selects all individually rational allocations at (R; θ). That is, ΦY0 (R; θ) :=I Y (R; θ).
patient, σ(k), prefers
Round k ∈ {1, . . . , n}: ΦYk (R; θ) selects all allocations that k th -priority{
θYY
the most among those in Φk−1 (R; θ). That is, Φk (R; θ) := a ∈ ΦYk−1 (R; θ) | ∀bθ ∈}ΦYk−1 (R; θ), aθσ(k) Rσ(k) bθσ(k) . Let ΦY (R; θ) := ΦYn (R; θ).
A priority mechanism under regime Y , φP , is a selection from the priority correspondence, i.e., for each (R; θ) ∈ RN × Θ, φP (R; θ) ∈ ΦY (R; θ).
Example 3 (Priority mechanism). This example describes the procedure of the priority
mechanism (Figure 5). There are three patients, each of whom has exactly two living
donors. For each i ∈ {1, 2, 3}, the types of patient i and her donors are shown in box i in
the figures. We assume that only the blood type accounts for the medical type of agents.
For example, at allocation a, patient 1’s type is shown in the left-hand side of the box,i.e., θ1 (1) = A, while her two donors have the identical type B as shown in the right-handside of the same box. Suppose that patient 1 has the highest priority, patient 2 the second,and patient 3 the third. The preferences of patients are given as follows. R1 : 02, 20, 00,
R2 : 11, 02, 00, R3 : 11, 02, 00.
In the first round, patient 1 chooses her assignment. Since her best is a living-donor dualgraft transplantation, all feasible allocations in which patient 1 receives a living-donor dualgraft transplant are selected by the priority correspondence. Such allocations are abundant,
and some of them are given in Figure 5: allocations a, b, and c. Note that all three allocations
are indiﬀerent for patient 1 but not for patients 2 and 3.
In the second round, patient 2 chooses her assignment. Since her best assignment is ahybrid transplantation, some allocations selected in the first round are rejected. Among
allocations a, b, and c, allocation a is rejected, since it assigns a living-donor dual-grafttransplant to patient 2. On the other hand, allocations b and c remain selected at thesecond round, since they assign a living-donor dual-graft transplant to patient 1 and a
hybrid transplant to patient 2. Note that patient 3 is not indiﬀerent between b and c.
In the third round, patient 3 chooses her assignment. Since her best choice is a hybridtransplantation, some allocations selected in the second round are rejected. Among alloca24

Figure 5: Allocations a, b and c in Example 3

tions b and c, allocation b is rejected, since it assigns a living-donor dual-graft transplant topatient 3.
Consequently, the priority correspondence contains allocation c. As shown in this example, in each round, the priority mechanism selects the best feasible allocations for theselecting patient in this round so as not to harm the higher-priority patients.29♢
Remark 5. The diﬀerence in regimes makes some diﬀerences in the nature of priority mechanisms. The following items 2 and 3 are basic. For a proof, see the online appendix.
1. Under any regime Y ∈ {O, E, H, HE}, if both φ and φ̃ are priority mechanisms thenthey are welfare-equivalent. That is, for each (R; θ) ∈ RN × Θ and each i ∈ N ,φi (R; θ) Ii φ̃i (R; θ).
2. Under any regime Y ∈ {O, H}, ΦY is single-valued. Thus, a priority mechanism is
unique.
3. Under any regime Y ∈ {E, HE}, ΦY may not be single-valued. Thus, a priority
mechanism may not be unique.

29

Rigorously speaking, a variant of c is also selected by the priority correspondence. It is the allocation inwhich the donation from patient 3’s second donor is replaced by the one from patient 3’s first donor. Notethat c and its variant are indiﬀerent for all patients.

25

4.2.1

Performance of priority mechanism under regimes O and H

Under regimes without donor exchange (regime O or H), the performance of the priority
mechanism is quite good:
Theorem 1. Under any regime Y ∈ {O, H}, the priority mechanism is individually rational, Pareto eﬃcient, ⪰-fair, and strategy-proof.
The priority mechanism overcomes the two major flaws of the Japanese mechanism —the violation of ⪰-fairness and strategy-proofness. Moreover, the prominence is kept evenunder the introduction of hybrid transplantation. However, by Proposition 2, strong nonwastefulness is not overcome. This is viewed as an inevitable cost for a mechanism to be
individually rational and ⪰-fair.
4.2.2

Performance of priority mechanism under regimes E and HE

Under regimes with donor exchange (regime E or HE), each priority mechanism keeps its
good performance for the normative properties.
Proposition 4. Under any regime Y ∈ {E, HE}, each priority mechanism is individually
rational, Pareto eﬃcient, and ⪰-fair. However, it is not strategy-proof.
One of the critical diﬀerences between regimes with and without donor exchange lies inthe degree of manipulability of the mechanisms. In particular, under regimes with donor
exchange, a patient can hide her own donors by rejecting hybrid and living-donor transplants
in her preference.30 Recall that we focus on balanced allocations (Proposition 1). Thus, if
a patient pretends that she cannot accept any hybrid and living-donor transplants then noother patients can use her living donors. This type of strategic behavior is a source for the
manipulation of a mechanism. Consequently, every priority mechanism is manipulable. To
scrutinize the problem evoked by strategic behavior in dual-organ markets, we consider thefollowing example.
Example 4 (Manipulation of the priority mechanism). There are five patients, patients
1 to 5, who are prioritized as 1 ≻ 2 ≻ 3 ≻ 4 ≻ 5. Patients 1, 2, and 5 have two living
donors, patient 4 has one while patient 3 has nothing. Their medical types and preferences
are illustrated in Figure 6.

30Note that hiding donors has no positive eﬀect for that patient under the regimes without donor exchange.

26

Figure 6: Allocations a and b in Example 4

Under true preferences (R2 ; R−2 ), patients 1,3,4, and 5 have just one acceptable surgery
type, while patient 2 prefers a deceased-donor dual-graft transplant to a living-donor dualgraft transplant. This market has individually rational allocations in which patient 1 receives
a living-donor dual-graft transplant, for example, allocation a, the priority mechanism selects
one of them. Now we claim that patient 2 must receive a living-donor dual-graft transplant in
the selected allocation. To show this, suppose to the contrary that patient 2 does not. Since
we assume the balanced condition, the living donors of patient 2 are not used for the selected
allocation. Thus, patient 1 receives A-type living donors from patients 4 and 5. Thus, by
the balanced condition, patient 5 must receive a living-donor dual-graft transplant under theselected allocation. However, this is impossible because no available A-type living donors
remain in the market. Therefore, we have proved that patients 1 and 2 receive living-donor
dual-graft transplants at the selected allocation. At this point, it is obvious that patients
3,4, and 5 are assigned their most preferred transplants at the selected allocation. Thus,
the priority mechanism selects allocation a (or, its welfare equivalent variant) in the left
figure.31
Now suppose that patient 2 deviates from R2 to R2′ . At R2′ , patient 2 hides the fact that
she can accept a living-donor dual-graft transplant. This is a kind of “truncated strategy”
well known in two-sided matching models (Roth and Sotomayor, 1990). Note that forpatient 1 to get a living-donor dual-graft transplant, the living donors of patient 2 are
31

Since we assume that patients are indiﬀerent to identical surgery-type transplants, the welfare-equivalentvariant of a can be easily obtained by changing some of the patient-donor combinations at a.

27

critical. Consequently, since the hiding strategy of patient 2 narrows down the opportunity
for patient 1, she cannot help but choose the null transplant in the first round of the priority
mechanism. This enables patient 2 to get a more preferred transplant, i.e., the deceaseddonor dual-graft transplant.
♢
In practice, it might be realistic to operate the mechanism by letting patients register
their preferences once within a certain fixed period, such as three or six months. Since thepriority order is mainly based on waiting time, it should be noted that even the patientwith the highest-priority in our model must have experienced low-priority positions before.
Although the dual-organ market in this paper is defined as a static model, the switch from R2
to R2′ in Example 4 can be interpreted as the free-riding behavior of patient 2. By hiding her
living-donors, not only does she prevent the transplants of other four patients, but she also
eliminates the opportunity of having her living donors contribute to the market, although
she positions herself with the potential possibility for a living-donor transplantation throughthe previous interaction with higher-priority patients when she was a lower-priority patient.
This point enhances the importance of incentive property for a mechanism in the dual-organ
market.
A natural question arising from Proposition 4 is: Is there a mechanism satisfying all
axioms listed in the proposition? The answer is negative.
Theorem 2. Under any regime Y ∈ {E, HE}, no mechanism is individually rational,
Pareto eﬃcient, ⪰-fair, and strategy-proof.
Since no mechanism satisfies all axioms listed in Theorem 2, we have to give up at least
one of the axioms to design a plausible mechanism under a regime with donor exchange.
Since Proposition 4 says that under regimes with donor exchange, each priority mechanism satisfies three of our four basic axioms, priority mechanisms attain one of the best
we can choose. Moreover, we will see a positive aspect of priority mechanisms which arerobust against strategic manipulation under incomplete information, although they are notstrategy-proof under complete information.

4.3

Preference revelation game with incomplete information undera priority mechanism

The successful manipulation of the priority mechanism in Example 4 heavily depends onthe complete information setup. In practice, the type of deceased donors is uncertain, andthe types of other patients and living donors are usually not open to the public. Thus, the28

Figure 7: Allocations a and c in Example 5

manipulation of the mechanism pertains to the risk of missing a transplant opportunity. To
see this point, let us consider the previous example under modification.
Example 5 (Manipulation of the priority mechanism is risky). Consider Example 4 where
patient 2 of blood type B gets the deceased donor of the same blood type by manipulating
the priority mechanism with the truncation strategy. Here, for simplicity, we focus on thesubmarket with patients 1 and 2. Let us consider a slightly modified case in which the blood
type of the deceased donor is type A instead of type B. Note that patient 2’s truncation
strategy, in this case, ends up with no transplants for both patients (Figure 7). In otherwords, she cannot receive a living-donor dual-graft transplant plus a deceased-donor dualgraft transplant because the truncation strategy narrows down not only the opportunity
for the higher-priority patient but also the one for herself. In this sense, the manipulation
strategy is risky.
Summing up, without accurate information about resources, i.e., types of deceaseddonor and other patients’ living donors, the manipulation behavior may be harmful to the
manipulator, too. In that sense, the truncation strategy is a “double-edge sword” for the
manipulator.32♢
Motivated by the above example, we introduce incomplete information into our model.
We assume that each patient can observe only her own medical type and preference, not theothers’. That is, she knows her own preference and type (Ri , θi ), but does not know other
patients’ (R−i ; θ−i ), including the deceased donor’s.33 Formally, we consider a preference
revelation game G = (N, DC , {DiL }i∈N , (T, ), Θdc , {R × Θi }i∈N , {u∗i }i∈N , Y, φP , {pi }i∈N ),
where
32

In Lemma 1 of the Appendix, we show that all successful manipulation strategies of the priority mechanism are necessarily double-edge in the sense that they always narrow down the possible assignment forthe manipulator.
33
This setup is suitable for Japan, because patients simply register for the Japan Organ Transplant
Network without any communication with other patients.

29

1. The symbols N, DC , {DiL }i∈N , (T, ), Θdc are the same as in the complete information
model: Each of them represents the set of patients, the set of deceased donors, thecollection of the set of living donors, the type space for the medical status of patientsand donors, and the type space of the deceased donor, respectively.
2. For each i ∈ N , R × Θi denotes patient i’s action set. It also represents patient i’s“type space” in the standard Bayesian game terminology.
()
3. For each i ∈ N , u∗i : {20, 10, 11, 02, 00} × R × Θi → R is a state-dependent utility
function. For each (Ri , θi ) ∈ R × Θi , u∗i (· | Ri , θi ) represents Ri . Without any confusion, given θ ∈ Θ, for each xθi ∈ Xi (θ), u∗i (xθi | Ri , θi ) denotes the value of u∗i (· | Ri , θi )for the transplantation type to which xθi belongs. Note that the above setup does not
exclude the state-independent utility case.
4. A priority mechanism φP under regime Y is fixed.
5. For each i ∈ N , pi : RN × Θ → [0, 1] is a probability distribution that represents patient i’s prior belief. We assume that pi has full support, i.e., for each(R; θ) ∈ RN × Θ, pi (R; θ) > 0. Note that we do not place the common prior assumption. For each (Ri , θi ) ∈ R × Θi , the posterior belief is denoted by pi (· | Ri , θi ),
i.e., it is the function from RN \{i} × Θ−i to [0, 1] defined as pi (R−i ; θ−i | Ri , θi ) :=pi (Ri ,R−i ;θi ,θ−i )∑.
pi (Ri ,R′ ;θi ,θ′ )N \{i}′′(R ;θ )∈R
−i −i

−i

×Θ−i

−i

Now we make an assumption about the players’ utility functions that reflects the huge gap
in utilities between acceptable transplants and unacceptable ones. To describe it, for eachi ∈ N and each (Ri , θi ) ∈ R × Θi , we introduce the following two notations:•

U D(u∗i ; Ri , θi ) :=• pi (Ri , θi ) :=
 max u∗i (α | Ri , θi ) −α∈Aci (Ri )0minα∈Aci (Ri )u∗i (α | Ri , θi )if Aci (Ri ) ̸= ∅,if Aci (Ri ) = ∅.

min

(R−i ;θ−i )∈RN \{i} ×Θ−ipi (R−i ; θ−i | Ri , θi ).

In words, U D(u∗i ; Ri , θi ) denotes the utility diﬀerence between the best acceptable transplantation and the worst acceptable one which in turn shows the maximal gain from the quality
improvement when a patient gets an acceptable transplant instead of another. Given patienti’s own type (Ri , θi ) ∈ R × Θi , the most unlikely event occurs with probability pi (Ri , θi ) inpatient i’s perspective. Note that pi (Ri , θi ) > 0, since we assume that pi has full support.
30

Assumption 2 (Huge utility gap between acceptable and unacceptable transplants). Evenat the most unlikely event, the expected utility loss from the worst acceptable transplant tothe best unacceptable one is so huge that a patient cannot recover it even if she gets anadditional utility U D(u∗i ; Ri , θi ) in every other event. Formally, for each i ∈ N and each
(Ri , θi ) ∈ R×Θi with at least one acceptable transplantation type at Ri , we have the following
inequality:(pi (Ri , θi )minα∈Aci (Ri ))()
u∗i (α | Ri , θi ) − u∗i (00 | Ri , θi ) > (1 − pi (Ri , θi )) RN \{i} × Θ−i − 1 U D(u∗i ; Ri , θi ).

Since an assignment in our model represents a transplant, an unacceptable transplantcan be interpreted as the death of the patient. Thus, it is natural that there is a huge utility
gap between acceptable and unacceptable transplants.
For each player i ∈ N , a strategy is a function si : R × Θi → R × Θi such that foreach (Ri , θi ) ∈ R × Θi , the submitted type is a sincere one, i.e., the second coordinate ofsi (Ri , θi ) is θi . Recall that the medical condition of a patient and her donors θi is verifiable
by medical doctors (see Assumption 1).34 Let Si be the set of patient i’s strategies. The
identity mapping s∗i ∈ Si is called the truth-telling strategy.
Before introducing the equilibrium concept of the game G, we use the following simplifying notation. For each (R; θ) = (R1 , . . . , Rn ; θdc , θ1 , . . . , θn ) ∈ RN × Θ, we sometimes
denote it as (θdc ; (R1 , θ1 ), . . . , (Rn , θn )). Moreover, when we focus on a patient i, we denote∏
it as (θdc ; (Ri , θi ); (Rj , θj )j̸=i ). A strategy profile s = (s1 , . . . , sn ) ∈ i∈N Si is a BayesianNash equilibrium in G if for each i ∈ N , each (Ri , θi ) ∈ R × Θi , and each Ri′ ∈ R,
∑

(
)
(
)
pi (R−i ; θ−i | Ri , θi )u∗i φPi (θdc ; si (Ri , θi ); sj (Rj , θj ) j̸=i ) Ri , θi

(R−i ;θ−i )∈RN \{i} ×Θ−i

≥

∑

(
)
(
)
pi (R−i ; θ−i | Ri , θi )u∗i φPi (θdc ; (Ri′ , θi ); sj (Rj , θj ) j̸=i ) Ri , θi .

(R−i ;θ−i )∈RN \{i} ×Θ−i

The main result of this subsection shows that each priority mechanism is robust against
strategic manipulation even under regimes with living-donor exchange under incomplete
information.35 To show that positive result, we need some specifications and simplifications
that decently approximate the real world. We make the following three assumptions.
34

Each patient knows that other patients submit own medical type honestly. However, she does not know
which types are realized.
35
Ehlers and Massó (2007, 2015) introduce incomplete information to the many-to-one matching problems
to characterize the Bayesian Nash equilibrium profiles under the stable mechanism. Our problem is diﬀerent
from theirs in 1) the uncertainty in our model is wider in the sense that the other players’ and deceased
donor’s medical types are included, and 2) patients’ do not necessarily have unit demand.

31

Assumption 3 (The number of component type spaces are two). The collection of component type spaces {(Tk , k )}K
k=1 is simplified to the one with the length two, i.e., K = 2, suchthat (T1 , 1 ) is the blood type space (TB , B ); (T2 , 2 ) is the other factor space that needs
coincidence, i.e., for all t2 , t′2 ∈ T2 , t2 2 t′2 ⇔ t2 = t′2 ; T2 contains at least four elements.
We denote it as T2 = {I, II, III, IV, . . .}.
This assumption seems too specific, but can reasonably accommodate the current practice. For example, consider the simplest space TB × T2 = TB × {l, s} × {c1 , c2 } where thecomponent space {l, s} of T2 expresses the sizes of grafts, large (l) or small (s); moreover,the component space {c1 , c2 } of T2 does the types of leucocyte. There are many types of leucocyte which are an important compatibility condition for lung transplantation. However,these types cannot be classified with a clear formula.36 For this reason, the cross-match test
is used and there would be at least two types which are incompatible with each other.37
What is common within a T2 space is that it needs a coincidence of types for a donor and arecipient. With these two component spaces of T2 , it is reasonable to assume at least four
elements in T2 . Hence, our example space satisfies Assumption 3. Note that T2 can be anylarger cardinality as long as it contains four elements.
Assumption 4 (On the number of living donors of each patient). The following three
conditions hold.38
1. Each patient has at most two living donors, i.e., for each i ∈ N , |DiL | ≤ 2.
2. At least four patients have multiple living donors, i.e., there exist distinct i, j, k, ℓ ∈ N
Lsuch that for each m ∈ {i, j, k, ℓ}, |Dm| = 2.
L| ≥ 2.
3. The highest-priority patient σ(1) has multiple living donors, i.e., |Dσ(1)36

We would like to thank Prof. Takahiro Oto for numerous useful comments from his expertise.
Although the red blood cell has four types of A, B, O, AB, leucocyte also has many types. The humanleucocyte is first classified into three types of A, B, DR, and then each of A, B, DR is classified into dozens
of antigen types. Moreover, there are unknown types, i.e., the antigens have not yet been exhausted. It
is known that every human being has two of the HLA (human leucocyte antigen)s. Thus,( ) for example,
when each of A, B, DR types are assumed to contain 20 antigens, human HLA types are 60
2 = 1770. The
extreme diversity and the existence of unknown types make it hard to specify which type is compatible withthe given type. For this reason, in practice, the cross-match test is carried out to experiment whether thepatient’s and donor’s blood have the immunological rejection in HLA type. In our example, for simplicity,
the HLA type is described by the two types. Note that our general setup, especially the fact that T2 canbe large as long as it contains four types, allows more complex type spaces.
38
A special case of the model satisfying this assumption is a market formed by four or more patients withexactly two living donors for each (Ergin, Sönmez, and Ünver, 2017).
37

32

The first condition is weak compared with the corresponding one in Ergin, Sönmez, andÜnver (2017) that requires each patient to have exactly two living donors. The second
condition is also weak because hundreds of patients are in line for deceased donors in theJapanese lung market. The last condition seems strong but is actually weak, because ournotion of donors include potential donors who are incompatible and usually do not show
up in hospitals. Theoretically speaking, this assumption is for simplification. That is, tomaintain our main result of Theorem 3, we can drop Assumption 4 when there are atleast four patients and each of them faces further uncertainty over the number of the other
patients’ living donors.
Assumption 5 (Type space restriction). For each i ∈ N , we redefine the type space Θi toslightly restrict a feasible type profile.39{
Θi :=θi ∈ T{i}∪DiLi) ∀d, d′ ∈ DiL , θi (d)  θi (i) and θi (d′ )  θi (i) ⇒ d = d′ ,ii) ∀d ∈ DiL , θi (d) ̸= θi (i)}.

The new definition of the type space excludes that a patient has a living donor who is not
only compatible with the own patient but also has the identical type with the patient. Let
us emphasize that the new definition does not necessarily exclude a compatible living donor.
It only excludes the complete coincidence between the type of a patient and her own donor.
Since T2 can be any large set, the restriction of the type space leaves almost no loss ofgenerality.40
We are now ready to state our main result of this subsection which asserts that eachpriority mechanism is robust against strategic behavior under incomplete information evenwhen the living-donor exchange is allowed.
Theorem 3. The truth-telling strategy profile s∗ = (s∗1 , . . . , s∗n ) ∈Nash equilibrium in G.

∏i∈N Si is a Bayesian

Theorem 3 shows that priority mechanisms satisfy a version of the ordinal Bayesian
incentive compatibility discussed in D’Aspremont and Peleg (1988) and Majumdar and Sen(2004). Note that we adopt Assumption 1 that ensures the truth-telling about patients’
medical type throughout this paper, and Assumption 2 that might be a plausible restriction
along with the problem pertaining to patients’ death throughout this section. Thus, theappropriately adjusted version of the ordinal Bayesian incentive compatibility with respect
39

The role of Assumption 5 is critical only when Y = HE. Theorem 3 can be proved without it if
Y ∈ {O, E, H}.
40
For example, a cross-match type space based on individual tissue type can be large.

33

to the given prior belief {pi }i∈N is the following: given a regime Y ∈ {O, E, H, HE}, amechanism φ is ordinally Bayesian incentive-compatible with respect to {pi }i∈N if
for each i ∈ N , each (Ri , θi ) ∈ R×Θi , each Ri′ ∈ R, and each ui (·; θi ) : {20, 10, 11, 02, 00} →R satisfying Assumption 2,(∑

pi (R−i ; θ−i | Ri , θi )ui φi (θdc ; (Ri , θi ); (Rj , θj )j̸=i ) Ri , θi)

(R−i ;θ−i )∈RN \{i} ×Θ−i∑≥
(R−i ;θ−i)∈RN \{i} ×Θ

pi (R−i ; θ−i | Ri , θi )ui(

φi (θdc ; (Ri′ , θi ); (Rj , θj )j̸=i ))
Ri , θi .

−i

Now we are ready to restate the incentive-compatible nature of priority mechanisms.
Corollary 1. Under any regime Y ∈ {O, E, H, HE}, any priority mechanisms are ordinally
Bayesian incentive-compatible.

5

Conclusion

We introduce a dual-organ market where patients are in the two markets for deceased donors
and living donors. We investigated the properties of the priority mechanism. Without donor
exchange, the priority mechanism is shown to be individually rational, Pareto eﬃcient,fair, and strategy-proof. However, once we allow for donor exchange, we lose its strategyproofness. Because patients’ manipulation is risky, we show that the priority mechanism
is robust against any manipulation by showing that the truth-telling strategy profile is a
Bayesian Nash equilibrium under the uncertainty over other patients’ type and preference,i.e., priority mechanisms are ordinally Bayesian incentive-compatible.
For countries with many deceased donors, it will be more appropriate to consider a static
model with multiple deceased donors or a dynamic model developed by Ünver (2010) for akidney exchange. We believe that our model of a static model with a single deceased donor
is important in the light of the current status of many countries, including Japan, and isalso a benchmark for extended models.

A

Appendix : The Japanese mechanism in lung market

In this appendix, we provide a formal description of the Japanese mechanism introduced in
Subsection 4.1. To describe the Japanese mechanism formally, we need some notations. For
each (R; θ) ∈ RN × Θ,
34• N 20 (R; θ) = {i ∈ N (R; θ) | 20 Pi 00 Pi 10} is the set of all patients who think the
only the dual-graft transplant as acceptable;• N 21 (R; θ) = {i ∈ N (R; θ) | 20 Pi 10 Pi 00} is the set of all patients who prefer thedual-graft transplant to single-graft ones with no unacceptable surgery types;• N 10 (R; θ) = {i ∈ N (R; θ) | 10 Pi 00 Pi 20} is the set of all patients who think the
only single-graft transplant as acceptable;• N 12 (R; θ) = {i ∈ N (R; θ) | 10 Pi 20 Pi 00} is the set of all patients who prefer the
single-graft transplant to dual-graft ones with no unacceptable surgery types.
Note that the sets N 20 (R; θ), N 21 (R; θ), N 10 (R; θ), and N 12 (R; θ) are disjoint.
Definition 8 (Japanese mechanism). Under the regime O, the Japanese mechanism,
φJ , selects an allocation for each (R; θ) ∈ RN × Θ as follows.
First, we consider the case with θdc q = 2. If N (R; θ) = ∅, then let φJ (R; θ) =()(0, ∅), · · · , (0, ∅) . Otherwise, let i1 := T op(⪰; N (R; θ)).
Case 1: i1 ∈ N 20 (R; θ) ∪ N 21 (R; θ).
For each i ∈ N , (2, ∅) if i = i ,1
φJi (R; θ) =(0, ∅) if i ̸= i .
1
(
)
10
12
Case 2: i1 ∈ N (R; θ) ∪ N (R; θ) and N 10 (R; θ) ∪ N 12 (R; θ) \{i1 } ̸= ∅.
()
Let i2 := T op(⪰; N 10 (R; θ) ∪ N 12 (R; θ) \{i1 }). For each i ∈ N ,(1, ∅) if i = i or i = i ,12Jφi (R; θ) =(0, ∅) if i ∈ N \{i , i }.
1 2
10
12
Case 3: N (R; θ) ∪ N (R; θ) = {i1 }.
Case 3.1: N 21 (R; θ) ̸= ∅.
Let i3 := T op(⪰; N 21 (R; θ)). For each i ∈ N ,(1, ∅) if i = i or i = i ,13J
φi (R; θ) =(0, ∅) if i ∈ N \{i , i }.
1 3
21Case 3.2: N (R; θ) = ∅.
Case 3.2.1: i1 ∈ N 10 (R; θ) and N 20 (R; θ) ̸= ∅.
Let i4 := T op(⪰; N 20 (R;θ)). For each i ∈ N ,(2, ∅) if i = i ,4
φJi (R; θ) =(0, ∅) if i ̸= i .
435

Case 3.2.2: i1 ∈ N 12 (R; θ) or N 20 (R; θ) = ∅.
For each i ∈ N ,(1, ∅) if i = i ,1
φJi (R; θ) =(0, ∅) if i ̸= i .
1
21
Next, we consider the case with θdc q = 1. If N (R; θ) ∪ N 12 (R; θ) ∪ N 10 (R; θ) = ∅, then()
let φJ (R; θ) = (0, ∅), · · · , (0, ∅) . Otherwise,
Case 4: N 12 (R; θ) ∪ N 10 (R; θ) ̸= ∅.
Let i5 := T op(⪰; 
N 12 (R; θ) ∪ N 10 (R; θ)). For each i ∈ N ,(1, ∅) if i = i ,5
φJi (R; θ) =(0, ∅) if i ̸= i .
51210Case 5: N (R; θ) ∪ N (R; θ) = ∅.
(Let i6 := T op(⪰; N 21 (R; θ)). For each i ∈ N ,(1, ∅) if i = i ,6
φJi (R; θ) =(0, ∅) if i ̸= i .
6BAppendix: Proofs

In this appendix, we provide the omitted proofs in the main text.
Proof of Proposition 1. Let aθ ∈ A(θ) be arbitrary. First, we show two claims.
)]
[
(
∪(
∪
∪
)
L
aθL
.
Claim 1.
aθL
=
DiL ∩
j
i \Di
i∈N

i∈N

j̸=i

To show that the left hand side of the equality is a subset of the right hand side, let
(
)
L
θL
L
L
L
d ∈ ∪i∈N aθL
i \Di . Then there is i ∈ N such that d ∈ ai \Di . Since d ∈ D = ∪j∈N Dj
θLand d ̸∈ DiL , there is j0 ∈ N \{i} such that d ∈ DjL0 . Moreover, d ∈ aθLi ⊆ ∪j̸=j0 aj . Thus()
d ∈ DjL0 ∩ ∪j̸=j0 aθL
.
j
[
(
)]
To show the converse, let d ∈ ∪i∈N DiL ∩ ∪j̸=i aθL. Then there is i ∈ N such that
j
(
)
L
θL
L
L
d ∈ Di ∩ ∪j̸=i aj . Thus, there is j0 ∈ N \{i} such that d ∈ aθL
j0 . Since Di ∩ Dj0 = ∅,Ld ∈ DiL implies d ̸∈ DjL0 . Thus d ∈ aθL
j0 \Dj0 . 2
(
)]
[
∪
∪
∪(
)
L
DiL ∩
aθL
are a direct union.
andaθL
Claim 2. Both
j
i \Di
i∈N
i
)
( θL L ) (j̸=θL
θL
Let i, i ∈ N be distinct. If d ∈ ai \Di ∩ ai′ \DiL′ , then d ∈ aθLi ∩ ai′ . This violates( θL L )the second condition of an allocation (2). Thus ∪i∈N ai \Di is direct a union.
i∈N

′

36

[
(∪
)] [
(∪
)]
θL
L
θL
If d ∈ DiL ∩
a
∩
D
∩
a
, then d ∈ DiL ∩ DiL′ , a contradiction.
i′j̸=i jj̸=i′ j[()]
Thus, ∪i∈N DiL ∩ ∪j̸=i aθL
is also a direct union. 2j
Now we turn back to the proof of Proposition 1. We have
∑
i∈N

L
aθL
i \Di =

∪(
i∈N

)
L

aθL
i \Di

=

∪

[

(

DiL ∩

i∈N

∪

)]
aθL
j

=

∑

(
DiL ∩

i∈N

j̸=i

∪

)
aθL
j

.

(∗)

j̸=i

Note that the first and the third equalities follow from Claim 2, while the second one follows
from Claim 1. On the other hand, the balanced condition requires
LL∀i ∈ N, aθL
i \Di ≤ Di ∩()∪j̸=i aθL.
j

For the equality (∗) to be true, the balanced condition must hold with equality for eachi ∈ N.
To show Remark 3, we need the following lemma.
Lemma 1. Under any regime Y ∈ {O, H}, non-wastefulness implies individual rationality.
Proof. Let (R; θ) ∈ RN × Θ. We show the contrapositive. Suppose that aθ ∈ AY (θ) is notindividually rational at (R; θ). Then we have a patient i ∈ N such that (0, ∅) Pi aθi . Since
Y ∈ {O, H}, no patient j ∈ N \{i} uses a graft from a living donor in DiL at aθ . ThatLθθ
θis, for each j ∈ N \{i}, aθLj ∩ Di = ∅. Thus, letting bi := (0, ∅), we have (i) bi Pi ai , (ii)θCθL
θand bθL(bθi ; aθ−i ) ∈ AY (θ) and (iii) bθC
i = ∅ ⊆ ai . This means that a is wastefuli = 0 < aiat (R; θ).
Proof of Remark 3. (Item 1) The first part is trivial. The second one is already shownin Example 1.
(Item 2) Since the first part is trivial, we only show the second part. Let Y ∈ {O, H} and(R; θ) ∈ RN × Θ. Suppose that aθ ∈ AY (θ) is non-wasteful at (R; θ). Let bθ ∈ AY (θ) be
such that for each i ∈ N , bθi Ri aθi . It is suﬃcient to show that there is no i ∈ N suchthat bθi Pi aθi . We consider four cases separately according to the distribution of grafts fromdc . Note that aθ is individually rational at (R; θ) by Lemma 1. Consequently, bθ is also
individually rational at (R; θ).
Case 1: ∃i ∈ N s.t. aθi ∈ Xi20 (θ). Note that no patient, except for patient i, receives
a non-null transplant at aθ , since all grafts from dc are used by i and the regime underconsideration is Y ∈ {O, H}. Thus, at the induced allocation, aθi = (2, DiL ). If patient i’s
37θC
assignment bθi is not (2, ∅), i.e., bθi ∈ Xi10 (θ) ∪ X̃i11 (θ) ∪ Xi00 (θ), then bθi Pi aθi , bθCi ≤ ai , and
θL
θ
θ
bθL
i ⊆ ai . This violates the non-wastefulness of a at (R; θ). Thus bi = (2, ∅). Note thatas bθCi = 2 and Y ∈ {O, H}, no patient, except for patient i, receives a non-null transplantθat b . Thus bθ = aθ .
∑
θCCase 2:= 2 and ̸ ∃i ∈ N s.t. aθi ∈ Xi20 (θ). Then there exist i, j ∈ N suchi∈N aithat i ̸= j and aθC= aθCij = 1. Note that no patient, except for patients i and j, receives
a non-null transplant at aθ , since all grafts from dc are used by i and j, and the regime
under consideration is Y ∈ {O, H}. Thus, at the induced allocation, aθi = (1, DiL ) andaθj = (1, DjL ).
θ
If bθi = (2, ∅), then bθC
j = 0. Since Y ∈ {O, H}, bj = (0, ∅). However, this violates thefact that bθj Rj aθj Pj (0, ∅), as bθj Rj aθj , aθj (̸= (0, ∅)) is individually rational at (R; θ). Thusbθi ̸= (2, ∅). Thus, as Y ∈ {O, H}, bθi ∈ Xi10 (θ) ∪ X̃i11 (θ) ∪ Xi00 (θ). Note that bθC
≤ aθC
i
i
θL
θL
θ
θ
and bi ⊆ ai . Therefore, bi Pi ai is impossible as it violates the non-wastefulness of aθ
at (R; θ). Thus bθi Ii aθi . Since Y ∈ {O, H}, bθi = aθi . By the identical argument, we havebθj = aθj . Note that, as Y ∈ {O, H}, no patient, except for patients i and j, receives a
non-null transplant at bθ . Thus bθ = aθ .
∑Case 3: i∈N aθC
i = 1. We treat two cases separately according to the number of available
grafts from dc .
Case 3.1: θdc q = 1. We can show that bθ = aθ by the same argument as the proof for Case
1.
Case 3.2: θdc q = 2. Let i ∈ N be the patient such that aθC
i = 1. Note that, since Y ∈ {O, H},
no patient, except for patient i, receives a non-null transplant at aθ . Note also that one
graft from dc is disposed at aθ . Thus, the induced allocation is as follows: For each j ∈ N ,(2, DL ) if j = i,jaθj =(1, DL ) if j ̸= i.
j

θC
θL
θ
θ
Note that, since Y ∈ {O, H}, bθi satisfies that bθCand bθLi ≤ aii ⊆ ai . Therefore, bi Pi ai
is impossible as it violates the non-wastefulness of aθ at (R; θ). Thus bθi Ii aθi . Since
Y ∈ {O, H}, bθi = aθi . Thus bθC
i = 1.
≤ 1. Thus
Since patient i uses one graft from dc at bθ , for each j ∈ N \{i}, bθC
j
θC
θC
θ
00
11
10
θ
θL
bj ∈ Xj (θ) ∪ X̃j (θ) ∪ Xj (θ). Note that bj satisfies that bj ≤ aj and bj ⊆ aθL
j , sinceY ∈ {O, H}. Therefore, bθj Pj aθj is impossible as it violates the non-wastefulness of aθ at(R; θ). Thus bθj Ij aθj . Since Y ∈ {O, H}, bθj = aθj = (0, ∅). Summing up with aθi = bθi , weobtain bθ = aθ .

38

∑
θC
= 0. Note that no patient receives a non-null transplant at aθ , sinceCase 4:i∈N aiY ∈ {O, H}. Note also that all grafts from dc are disposed at aθ . Thus the induced allocation
is: for each i ∈ N , aθi = (θdc q , DiL ). If patient i’s assignment bθi is in Xi20 (θ)∪Xi10 (θ)∪ X̃i11 (θ)∪
Xi00 (θ) and bθi Pi aθi , then aθ is wasteful at (R; θ). Thus, bθi ̸∈ Xi20 (θ)∪Xi10 (θ)∪X̃i11 (θ)∪Xi00 (θ)
or aθi Ri bθi . Note that since Y ∈ {O, H}, bθi ̸∈ Xi20 (θ)∪Xi10 (θ)∪X̃i11 (θ)∪Xi00 (θ) is impossible.
Thus aθi Ri bθi . Because we assume that bθi Ri aθi , this implies aθi Ii bθi . Since Y ∈ {O, H},bθi = aθi . Thus bθ = aθ .
As bθ = aθ for all of the four cases, no patient prefers bθ to aθ . This completes the proof
of Item 2.
(Item 3) We show the statement by two examples. First, we show that Pareto eﬃciency
does not imply strong non-wastefulness. Obviously, allocation aθ described in Example 1 isPareto eﬃcient, while it is strongly wasteful. Next, we show that strong non-wastefulness
does not imply Pareto eﬃciency under any regime Y ∈ {E, HE}. Let (T, ) = (TB , B ).
Assume, without loss of generality, that patients 1 and 2 have multiple living donors. Let
d11 , d12 ∈ D1L and d21 , d22 ∈ D2L . Let θ ∈ Θ be such that θdc T = AB, θ(1) = θ(d21 ) =θ(d22 ) = A and θ(2) = θ(d11 ) = θ(d12 ) = B. Suppose that for each i ∈ N \{1, 2} and eachd ∈ DL \{d11 , d12 , d21 , d22 }, θ(i) = O and θ(d) = AB. Let R ∈ RN be such that
R1
R2

02 00
02 00

···
···

Consider the allocation aθ := ((0, ∅), (0, ∅)). The allocation is trivially non-wasteful at(R; θ). Note that no feasible allocation uses a graft from dc at all, since the deceased donor
is not compatible with any patients. Thus aθ is strongly non-wasteful at (R; θ). On theother hand, since it is Pareto dominated by allocation ((0, {d21 , d22 }), (0, {d11 , d12 })), aθ is
not Pareto eﬃcient at (R; θ).
Proof of Remark 4. (First half of Item 1: ⪰-fairness ̸⇒ individual rationality) We proveit by an example. Let (T, ) = (TB , B ). Let i be the highest-priority patient. Let θ ∈ Θ
be such that θdc = (2, A) and θ(i) = A. Let R ∈ RN be such that Ri · · · 00 20 · · · .
An allocation where i receives (2, ∅) is trivially ⪰-fair because the highest-priority patient
receives all grafts from dc . However, (2, ∅) is not acceptable for patient i, i.e., the allocation
is not in I Y (R; θ).
(The latter half of Item 1: Pareto eﬃciency and ⪰-fairness ̸⇒ individual rationality) We
prove it by an example. Let (T, ) = (TB , B ). Assume, without loss of generality, that39

patients 1 and 2 have multiple living donors. Let d11 , d12 ∈ D1L and d21 , d22 ∈ D2L . Letθ ∈ Θ be such that θdc T = AB, θ(1) = θ(d21 ) = θ(d22 ) = A and θ(2) = θ(d11 ) = θ(d12 ) = B.
Suppose that for each i ∈ N \{1, 2} and each d ∈ DL \{d11 , d12 , d21 , d22 }, θ(i) = O andθ(d) = AB. Let R ∈ RN be such that
R1
R2

02 00
00 02

···
···

Consider allocation aθ := ((0, {d21 , d22 }), (0, {d11 , d12 })) ∈ AY (θ). Note that aθ is notindividually rational at (R; θ) because aθ2 is not acceptable for patient 2.
We claim that aθ is Pareto eﬃcient and ⪰-fair at (R; θ). Since no patient is compatible with the grafts from dc , aθ is trivially ⪰-fair at (R; θ). Next we show the Paretoeﬃciency. Suppose that bθ ∈ AY (θ) is such that bθ1 R1 aθ1 and bθ2 R2 aθ2 . Note that
X102 = {(0, {d21 , d22 })}. Thus, since the living-donor dual-graft transplantation, 02, is the
top choice at R1 , bθ1 = aθ1 . By Proposition 1, patient 2 receives two grafts from other patients’living-donors because her own donors (d21 and d22 ) donate two grafts to other patient in
total. Thus bθ2 = (0, {d11 , d12 }). Thus bθ = aθ . This completes the proof of Pareto eﬃciency.
(Item 2) We show it by an example. Let (T, ) = (TB , B ). Assume, without loss ofgenerality, that 1 ≻ 2. Let θ ∈ Θ be such that θdc = (2, A) and θ(1) = θ(2) = A. Supposethat for each i ∈ N \{1, 2} and each d ∈ DL , θ(i) = O and θ(d) = AB. Let R ∈ RN be such
that
R1
R2

10 20
20 00

00
···

···

First, consider allocation aθ := ((0, ∅), (2, ∅)) ∈ AY (θ). This allocation is non-wasteful,strongly non-wasteful, and Pareto eﬃcient at (R; θ), because the two grafts from dc go topatient 2 whose top choice is (2, ∅) and the market has no living donor compatible with apatient. However, aθ is not ⪰-fair at (R; θ), because patient 1 can be better oﬀ by using a
graft from dc assigned to lower-priority patient (patient 2). Thus, neither non-wastefulness,strong non-wastefulness, nor Pareto eﬃciency implies ⪰-fairness.
Next, consider allocation bθ := ((2, ∅), (0, ∅)). Since the highest-priority patient 1 uses
all grafts from dc , bθ is trivially ⪰-fair at (R; θ). However, bθ is wasteful at (R; θ), because
patient 1 can be better oﬀ by disposing of one graft from dc without aﬀecting patient
2’s assignment. Formally, letting cθ1 := (1, ∅), (i) cθ1 P1 bθ1 , (ii) (cθ1 , bθ2 ) ∈ AY (θ) and (iii)θCθLθ= 1 ≤ b1 and cθLcθC
1
1 = ∅ ⊆ b1 . This means that b is wasteful at (R; θ). Thanks toRemark 3, bθ is not strongly non-wasteful at (R; θ), and not Pareto eﬃcient at (R; θ). Thus40⪰-fairness does not imply any one of non-wastefulness, strong non-wastefulness and Paretoeﬃciency.
Proof of Proposition 2. We prove it by an example. We use the same example as in
Example 1. Assume, without loss of generality, that the priority is given as 1 ≻ 2. Obviously,()()
I Y (R; θ) consists of just three allocations: aθ := (1, ∅), (0, ∅) , bθ := (0, ∅), (2, ∅) , and()
cθ := (0, ∅), (0, ∅) . Allocation aθ is ⪰-fair, but is not strongly non-wasteful, since the two
grafts from dc can be used at allocation bθ . Next, allocation bθ is strongly non-wasteful,but is not ⪰-fair, since agent 1 can be better oﬀ by using one graft from dc assigned toagent 2 who is of lower priority than agent 1. Finally, allocation cθ is wasteful, since one of
the agents 1 and 2 can be better oﬀ by using the grafts from dc that are disposed of at cθ .
Thus, no individually rational allocation satisfies ⪰-fairness and strong non-wastefulness at(R; θ).
Proof of Proposition 3. Item (i) is trivial. Items (iii) to (v) are shown in Example 2.
So it remains to show (ii). Since Pareto eﬃciency is equivalent to non-wastefulness underregime O by Remark 3, we show that φJ is non-wasteful. Note that under regime O, nonwastefulness only requires that no patient be better oﬀ by using a disposed graft from dc .
This is straightforward.
Proof of Remark 5. (Item 1) Trivial.
(Item 2) Let Y ∈ {O, H}. We show that for each (R; θ) ∈ RN × Θ, ΦY (R; θ) is a singleton.
Let aθ , bθ ∈ ΦY (R; θ). By Item 1, for each i ∈ N, aθi Ii bθi . Note that regimes O and H allow
only transplants in Xi20 (θ), Xi10 (θ), X̃i11 (θ), and Xi00 (θ). Thus, aθi Ii bθi implies aθi = bθi . Thusaθ = bθ .
(Item 3) Let Y ∈ {E, HE}. We show that for some (R; θ) ∈ RN × Θ, ΦY (R; θ) contains
at least two allocations. Let (T, ) = (TB , B ). Assume, without loss of generality, thatpatients 1 and 2 have multiple living donors. Let d11 , d12 ∈ D1L and d21 , d22 ∈ D2L . Let θ ∈ Θ
be such that θdc T = AB, θ(1) = θ(d21 ) = A, θ(2) = θ(d11 ) = B and θ(d12 ) = θ(d22 ) = O.
Suppose that for each i ∈ N \{1, 2} and each d ∈ DL \{d11 , d12 , d21 , d22 }, θ(i) = O andθ(d) = AB. Let R ∈ RN be such that
R1
R2

02 00
02 00

41

···
···

Note that the only compatible donors for patients in N \{1, 2} are d12 and d22 . Thus, if apatient i ∈ N \{1, 2} receives a non-null transplant at an allocation, it must be (0, {d12 , d22 }).
However, in that case, patients 1 and 2 also receive a non-null transplant with receiving atleast one graft from other patient’s living donor (Proposition 1). Because there are notenough compatible donors for patients 1 and 2 to receive a non-null transplant without d12
and d22 , every feasible allocation assigns the null transplant (0, ∅) to patients in N \{1, 2}.
For any priority order ⪰, ΦY (R; θ) contains all allocations where patients 1 and 2 receive()
living-donor transplants. Note that both ((0, {d12 , d21 }), (0, {d11 , d22 })) and (0, D2L ), (0, D1L )are in ΦY (R; θ).
Note that in the following proof, there is no specification of regime except for strategyproofness.
Proof of Theorem 1. We assume, without loss of generality, that 1 ≻ 2 ≻ . . . ≻ n.
(Individual rationality) Trivial.
(Pareto eﬃciency) Let (R; θ) ∈ RN × Θ. Suppose to the contrary that there is an allocationaθ ∈ AY (θ) such that for each i ∈ N , aθi Ri φPi (R; θ) and for some i ∈ N , aθi Pi φPi (R; θ).
Note that aθ ∈ I Y (R; θ) = ΦY0 (R; θ), since aθ Pareto-dominates an individually rational
allocation φP (R; θ). Let i ∈ N be the highest-priority patient among those who prefer aθto φP (R; θ). Note that this implies that for each j ∈ N with j ≻ i, aθj Ij φPj (R; θ). Thusaθ ∈ ΦYi−1 (R; θ). Since aθi Pi φPi (R; θ), φP (R; θ) ̸∈ ΦYi (R; θ) ⊇ ΦY (R; θ), a contradiction.
(⪰-fairness) Let (R; θ) ∈ RN × Θ. Let aθ := φP (R; θ). Suppose to the contrary that there
is an allocation bθ ∈ I Y (R; θ) such that for some i ∈ N , (i) bθi Pi aθi , (ii) bθC> aθCand for
i
i
θC
θ
θ
θC
θC
each j ∈ N with j ≻ i, bθCj = aj and (iii) for each j ∈ N , aj Pj bj implies aj > bj .
If for each j ∈ N with j ≻ i, bθj Rj aθj , then allocation aθ is excluded from the priority
correspondence at some step, the latest step i, of the algorithm. That is, there is j ∈{1, . . . , i} such that aθ ̸∈ ΦYj (R; θ) ⊇ ΦY (R; θ), a contradiction. Thus there is j ∈ N withθCj ≻ i such that aθj Pj bθj . By Item (iii), aθC
j > bj . This contradicts the second part of Item(ii).
(Strategy-proofness) Let Y ∈ {O, H}. Suppose to the contrary that there are (R; θ) ∈RN × Θ, i ∈ N and Ri′ ∈ R such that φPi (Ri′ , R−i ; θ) Pi φPi (R; θ). For notational simplicity,
let R′ := (Ri′ , R−i ).
Since regime Y does not allow for donor exchange, any preference misreporting cannot
aﬀect the individual assignment of higher-priority patients in the priority mechanism. Thatis, for each j ∈ N with j ≻ i, φPj (R; θ) Ij φPj (R′ ; θ). Thus, since indiﬀerent individual42assignments are identical in regime Y , for each j ∈ N with j ≻ i, φPj (R; θ) = φPj (R′ ; θ). Notethat φP (R′ ; θ) is individually rational at (R; θ) because φPi (R′ ; θ) Pi φPi (R; θ) Ri (0, ∅) and′R−i= R−i . Thus φP (R′ ; θ) ∈ I Y (R; θ) = ΦY0 (R; θ). Thus we obtain φP (R′ ; θ) ∈ ΦYi−1 (R; θ).
Hence φP (R; θ) ̸∈ ΦYi (R; θ) ⊇ ΦY (R; θ), a contradiction.
Proof of Proposition 4. The proof of individual rationality, Pareto eﬃciency, and ⪰fairness is identical with that of Theorem 1. Non-strategy-proofness is by Example 4.
Proof of Theorem 2. Suppose to the contrary that a mechanism under Y ∈ {E, HE}, φ,satisfies all axioms stated in Theorem 2. Let (T, ) = (TB , B ). Assume, without loss ofgenerality, that patients 1 and 2 have multiple living donors and that 1 ≻ 2. Let d11 , d12 ∈D1L and d21 , d22 ∈ D2L . Let θ ∈ Θ be such that θdc = (2, O), θ(1) = θ(d21 ) = θ(d22 ) = A
and θ(2) = θ(d11 ) = θ(d12 ) = B. Let R1 , R1′ , R2 , R2′ ∈ R be preferences of patients 1 and 2
described by the following table.
R1
R1′
R2
R2′

02
02
10
10

10 00
20 10
02 00
00 · · ·

···
00
···

···

Let R−{1,2} ∈ RN \{1,2} be a preference profile such that each patient j ∈ N \{1, 2} has(0, ∅) as the most preferred in Rj . Note that each patient in N \{1, 2} receives (0, ∅), no
matter when patients 1 and 2 submit any preference because φ is individually rational.
In the subsequent part of the proof, we omit their assignments in the description of an
allocation. First, we show the following claim.
Claim. φ(R1 , R2 , R−{1,2} ; θ) = ((1, ∅), (1, ∅)).
Suppose to the contrary that φ(R1 , R2 , R−{1,2} ; θ) ̸= ((1, ∅), (1, ∅)). Note that the
only individually rational and Pareto eﬃcient allocations at (R1 , R2 , R−{1,2} ; θ) are aθ :=((0, {d21 , d22 }), (0, {d11 , d12 })) and bθ := ((1, ∅), (1, ∅)). Thus, by the contradiction hypothesis, φ(R1 , R2 , R−{1,2} ; θ) = aθ . On the other hand, bθ is the only individually rational andPareto eﬃcient allocation at (R1 , R2′ , R−{1,2} ; θ). Thus φ(R1 , R2′ , R−{1,2} ; θ) = bθ . Therefore,
φ2 (R1 , R′2 , R−{1,2} ; θ) P2 φ2 (R1 , R2 , R−{1,2} ; θ), a violation of strategy-proofness of φ. This
completes the proof of Claim.

Next, we consider patient 1’s assignment at φ(R1′ , R2 , R−{1,2} ; θ). Note that since φ is individually rational, φ1 (R1′ , R2 , R−{1,2} ; θ) is one of the following assignments: (0, ∅), (1, ∅), (2, ∅), (0, {d21 , d22 }We separately derive a contradiction for each case.
43

Case 1: φ1 (R1′ , R2 , R−{1,2} ; θ) = (0, ∅). Then φ1 (R1 , R2 , R−{1,2} ; θ) = (1, ∅) P1′ (0, ∅) =φ1 (R1′ , R2 , R−{1,2} ; θ), a violation of strategy-proofness of φ.
Case 2: φ1 (R1′ , R2 , R−{1,2} ; θ) = (1, ∅). Since φ(R1′ , R2 , R−{1,2} ; θ) is Pareto eﬃcient at(R1′ , R2 , R−{1,2} ; θ), the assignment of patient 2 is φ2 (R1′ , R2 , R−{1,2} ; θ) = (1, ∅), i.e., φ(R1′ , R2 , R−{1,2} ; θ) =bθ . However, bθ is not ⪰-fair at (R1′ , R2 , R−{1,2} ; θ), because cθ := ((2, ∅), (0, ∅)) ∈ I Y (R1′ , R2 , R−{1,2} ; θ).
This violates the ⪰-fairness of φ.
Case 3: φ1 (R1′ , R2 , R−{1,2} ; θ) = (2, ∅). Note that no patient in N \{2} uses patient 2’sliving donor. By Proposition 1, patient 2’s assignment does not use any graft from other’sliving donor. Moreover, patient 2 cannot use a graft from dc , since all grafts from dc are
assigned to patient 1. Thus the assignment of patient 2 is φ2 (R1′ , R2 , R−{1,2} ; θ) = (0, ∅),i.e., φ(R1′ , R2 , R−{1,2} ; θ) = cθ . However, cθ is Pareto dominated by aθ at (R1′ , R2 , R−{1,2} ; θ).
This violates Pareto eﬃciency of φ.
Case 4: φ1 (R1′ , R2 , R−{1,2} ; θ) = (0, {d21 , d22 }). We have φ1 (R1′ , R2 , R−{1,2} ; θ) = (0, {d21 , d22 }) P1(1, ∅) = φ1 (R1 , R2 , R−{1,2} ; θ), a violation of strategy-proofness of φ.
Since the above four cases exhaust all possibilities of φ1 (R1′ , R2 , R−{1,2} ; θ), we conclude
that φ(R1′ , R2 , R−{1,2} ; θ) is not well-defined, a contradiction.
To prove Theorem 3, we need two lemmas. Lemma 2 says that if a patient can successfully manipulate a priority mechanism, then the assignment under the true preferencenecessarily contains a graft from other patient’s living donor. Consequently, the transplantis an acceptable one at the true preference. Moreover, at the false preference, the assignment
under the true preference is evaluated as unacceptable. That is, successful manipulation
forces the patient to pretend that she cannot accept a transplantation type which is actuallyan acceptable one.
Lemma 2. Under any regime Y ∈ {E, HE}, for each (R; θ) ∈ RN × Θ, each i ∈ N , andeach Ri′ ∈ R, if φPi (Ri′ , R−i ; θ) Pi φPi (Ri , R−i ; θ), then()(i) φPi (Ri , R−i ; θ) ∈ Xi11 (θ)\X̃i11 (θ) ∪ Xi02 (θ). Consequently, φPi (Ri , R−i ; θ) ̸= (0, ∅).
(ii) φPi (Ri′ , R−i ; θ) Pi′ (0, ∅) Pi′ φPi (Ri , R−i ; θ).

Proof. Let (R; θ) ∈ RN × Θ, i ∈ N and Ri′ ∈ R. Suppose φPi (Ri′ , R−i ; θ) Pi φPi (Ri , R−i ; θ).
For notational simplicity, let bθ := φP (Ri′ , R−i ; θ) and aθ := φP (Ri , R−i ; θ). Assume, without
loss of generality, that 1 ≻ 2 ≻ . . . ≻ n.
)
(
11
11
θ
Proof of Item (i). Suppose to the contrary that ai ̸∈ Xi (θ)\X̃i (θ) ∪Xi02 (θ). Namely,aθi is a deceased-donor dual-graft, deceased-donor single-graft, hybrid with own donor, ornull transplant. We claim∀j ∈ N with j ≻ i, bθj Ij aθj .
(4)44

To show (4), suppose to the contrary that at least one patient j ∈ N with j ≻ i is not
indiﬀerent between bθj and aθj , i.e., bθj Pj aθj or aθj Pj bθj . We derive a contradiction for eachcase separately. Without loss of generality, suppose that j is the highest-priority patient
who has such a preference.
Case 1: aθj Pj bθj . Let cθ be such thatcθk =(0, ∅) if k = i,
aθ if k ̸= i.
kNote that cθ ∈ AY (θ), since aθi does not use other’s donor. Moreover, cθ ∈ I Y (Ri′ , R−i ; θ),since the only diﬀerence between (Ri , R−i ; θ) and (Ri′ , R−i ; θ) is patient i’s preference. Thuscθ ∈ ΦY0 (Ri′ , R−i ; θ). By the definition of j, for each k < j, cθk = aθk Ik bθk . Thus cθ ∈
ΦYj−1 (Ri′ , R−i ; θ). Since aθj Pj bθj , bθ ̸∈ ΦYj (Ri′ , R−i ; θ) ⊇ ΦY (Ri′ , R−i ; θ). However, bθ =φP (Ri′ , R−i ; θ) ∈ ΦY (Ri′ , R−i ; θ), a contradiction.
Case 2: bθj Pj aθj . Since bθ ∈ I Y (Ri′ , R−i ; θ) and bθi Pi aθi Ri (0, ∅), bθ ∈ I Y (Ri , R−i ; θ).
Thus bθ ∈ ΦY0 (Ri , R−i ; θ). By the definition of j, for each k < j, aθk Ik bθk . Thus bθ ∈
ΦYj−1 (Ri , R−i ; θ). Thus, aθ ̸∈ ΦYj (Ri , R−i ; θ) ⊇ ΦY (Ri , R−i ; θ). However, aθ = φP (Ri , R−i ; θ) ∈ΦY (Ri , R−i ; θ), a contradiction.
Summing up Cases 1 and 2, we get (4).
Now we complete the proof of Item (i). Note that as we have seen in Case 2, bθ ∈I Y (Ri , R−i ; θ). Thus, by (4), bθ ∈ ΦYi−1 (Ri , R−i ; θ). Since bθi Pi aθi , aθ ̸∈ ΦYi (Ri , R−i ; θ) ⊇ΦY (Ri , R−i ; θ). However, aθ = φP (Ri , R−i ; θ) ∈ ΦY (Ri , R−i ; θ), a contradiction. □Proof of Item (ii): We show the first part of Item (ii). Since φP is individually rational, it
is obvious that bθi = φPi (Ri′ , R−i ; θ) Ri′ (0, ∅). If bθi = (0, ∅), then (0, ∅) Pi aθi = φPi (Ri , R−i ; θ),a violation to individual rationality of φP . Thus we obtain bθi Pi′ (0, ∅).
Next, we show the second part of Item (ii), i.e., (0, ∅) Pi′ aθi . Suppose to the contrary
that aθi Ri′ (0, ∅). Then, both aθ and bθ are individually rational at both (Ri , R−i ; θ) and(Ri′ , R−i ; θ), since the only diﬀerence between (Ri , R−i ; θ) and (Ri′ , R−i ; θ) is patient i’spreference. We consider the following two cases separately, and derive a contradiction for
each.
Case 1: ∀j ∈ N with j ≻ i, aθj Ij bθj . By bθ ∈ I Y (Ri , R−i ; θ) and the assumption forCase 1, bθ ∈ ΦYi−1 (Ri , R−i ; θ). Since bθi Pi aθi , aθ ̸∈ ΦYi (Ri , R−i ; θ) ⊇ ΦY (Ri , R−i ; θ). Thus,aθ = φP (Ri , R−i ; θ) ̸∈ ΦY (Ri , R−i ; θ), a contradiction.
Case 2: Let j ∈ N be the highest-priority patient with j ≻ i and not aθj Ij bθj .
Case 2.1: aθj Pj bθj . By aθ ∈ I Y (Ri′ , R−i ; θ) and the assumption for Case 2.1, aθ ∈45

ΦYj−1 (Ri′ , R−i ; θ). Since aθj Pj bθj , bθ ̸∈ ΦYj (Ri′ , R−i ; θ) ⊇ ΦY (Ri′ , R−i ; θ). Thus, bθ =φP (Ri′ , R−i ; θ) ̸∈ ΦY (Ri′ , R−i ; θ), a contradiction.
Case 2.2: bθj Pj aθj . By bθ ∈ I Y (Ri , R−i ; θ) and the assumption for Case 2.2, bθ ∈
ΦYj−1 (Ri , R−i ; θ). Since bθj Pj aθj , aθ ̸∈ ΦYj (Ri , R−i ; θ) ⊇ ΦY (Ri , R−i ; θ). Thus, aθ =φP (Ri , R−i ; θ) ̸∈ ΦY (Ri , R−i ; θ), a contradiction.
Lemma 3 says that a patient i has a profitable deviation only if she has a donor di with a
special medical type: a graft with patient i’s medical type is not compatible with a patientwith di ’s medical type. To see why this is true, let us take a look at Figure 8. Let i be apatient who has donors with identical type except for the blood type. In that figure, x, y,
and z represent the blood types of patient i, 1st donor of i, and 2nd donor of i, respectively.
Suppose that patient i has a profitable deviation. That is, she has a false preference withwhich she can get a more preferable transplant to the one with the true preference. In figure
8, the solid arrows represent the flow of living donors at the allocation under patient i’s true
preference. Let us call the allocation a. By Lemma 2, patient i gets a hybrid transplantwith other’s donor or living-donor dual-graft transplant at a. In either case, she uses a graftfrom other patient’s living donor, say dk . By Proposition 1, one of the patient i’s donors
donates to a patient, say j.
We claim that group i’s contribution at a must be critical to maintain the welfare levelof other patients. If x 1 z holds, then the donor dk can donate to patient j directly, because
the blood type compatibility relation 1 = B is transitive. This means that the patients in
N \{i} can attain the welfare level of a without the contribution of group i. Consequently,
even if patient i reports a preference which states that ai is unacceptable, other patients cankeep consuming transplants indiﬀerent with a−i . Thus patient i’s deviation has no eﬀect on
the priority mechanism. This contradicts that patient i has a profitable deviation. Thus, xcannot be blood-type-compatible with z, i.e., x ̸ 1 z.
Lemma 3. Let Y ∈ {E, HE}, (R; θ) ∈ RN × Θ and i ∈ N . Suppose that for each d ∈ DiL ,θ(d) is identical with θ(i) except for the blood type, i.e., θ2 (d) = θ2 (i). Then,
[ ′
]
[
]
∃Ri ∈ R s.t. φPi (Ri′ , R−i ; θ) Pi φPi (Ri , R−i ; θ) ⇒ ∃d ∈ DiL s.t. θ1 (i) ̸ 1 θ1 (d) .
Proof. Assume, without loss of generality, 1 ≻ 2 ≻ . . . ≻ n. Suppose to the contrary that∀d ∈ DiL , θ1 (i) 1 θ1 (d).

(5)

Fix patient i’s profitable deviation Ri′ ∈ R. For notational simplicity, let bθ := φP (Ri′ , R−i ; θ)46

Figure 8: Patient with a profitable deviation necessarily plays a critical role in the donor
exchange.

and aθ := φP (R; θ). The proof consists of three steps.
Step 1: Defining new allocations b′θ and a′θ . We define b′θ and a′θ in AY (θ) based on bθ
and aθ . Since the way to generate a′θ from aθ is the same as the one for b′θ from bθ , weonly describe the construction of b′θ in detail. The definition of b′θ varies according to thenumber of other patient’s living donors in bθL
i . Each case below corresponds to the casewhere the number is 0, 1 and 2, respectively.
Case 1: bθi ∈ Xi20 (θ) ∪ Xi10 (θ) ∪ X̃i11 (θ) ∪ Xi00 (θ). For each m ∈ N ,
b′θ
m :=


(0, ∅) if m = i,bθ if m ̸= i.
mObviously, b′θ ∈ AY (θ).
[]
L
L
Case 2: bθi ∈ Xi11 (θ)\X̃i11 (θ) or bθi ∈ Xi02 (θ) and bθLi ∩ Di ̸= ∅ . Let di ∈ Di be i’s donorL
who donates to other patient, say k ∈ N \{i}, at bθ , i.e., di ∈ bθL
k . Let dℓ ∈ Dℓ be other
patient’s donor who donates to i at bθ , i.e., ℓ ̸= i and dℓ ∈ bθL
i . For each m ∈ N ,
(0, ∅) if m = i,


′θ
θL
bm := (bθCk , (bk \{di }) ∪ {dℓ }) if m = k,bθ if m ̸∈ {i, k}.
m

We claim that b′θ ∈ AY (θ). To show this, it is suﬃcient to prove that dℓ is compatible with47

k, i.e., θ(dℓ )  θ(k). First, we show
θ2 (dℓ ) 2 θ2 (i) (∵ dℓ ∈ bθLi )2 θ2 (di ) (∵ Assumption of Lemma 3)
2 θ2 (k). (∵ di ∈ bθLk )Since the binary relation 2 is the equality “=”, it is transitive. Thus θ2 (dℓ ) 2 θ2 (k).
Similarly,θ1 (dℓ ) 1 θ1 (i) (∵ dℓ ∈ bθLi )1 θ1 (di ) (∵ The contradiction hypothesis (5))
1 θ1 (k). (∵ di ∈ bθLk )Since the binary relation 1 is transitive, θ1 (dℓ ) 1 θ1 (k). In sum, θ(dℓ )  θ(k). Thusb′θ ∈ AY (θ).
L
L
Case 3: bθi ∈ Xi02 (θ) and bθLi ∩ Di = ∅. Let di1 , di2 ∈ Di be i’s donor who donate to otherθL
L
L
patient(s), say k, ℓ ∈ N \{i}, at bθ , i.e., di1 ∈ bθL
k and di2 ∈ bℓ . Let dp , dq ∈ D \Di be′θother patient’s donors who donate to i at bθ , i.e., bθL
i = {dp , dq }. If k = ℓ, then let b besuch that for each m ∈ N ,
(0, ∅) if m = i,b′θ(0, {dp , dq }) if m = k,
m :=



bθ if m ̸∈ {i, k}.
m

If k ̸= ℓ, then let b′θ be such that for each m ∈ N ,

b′θ
m :=




(0, ∅) if m = i,(bθC , (bθL \{d }) ∪ {d }) if m = k,
k

k

i1

p

θL


(bθC

ℓ , (bℓ \{di2 }) ∪ {dq }) if m = ℓ,bθ if m ̸∈ {i, k, ℓ}.
m

In either case, the proof for b′θ ∈ AY (θ) is the same as the one given in Case 2. Thus weomit it.
In the same manner, we define a′θ based on aθ .41 Note that every patient, except for i,
receives the same transplantation type at b′θ and bθ in each case. This is true at a′θ and aθ .
41

By Lemma 2, aθi is a hybrid transplant with other’s donor or a living-donor dual-graft transplant. Thus
Case 1 is redundant to define a′θ .

48

Thus we haveθ′θθ∀k ∈ N \{i}, b′θ
k Ik bk and ak Ik ak .

(6)

Step 2: We show that for each j ∈ N with j ≻ i, bθj Ij aθj . Suppose to the contrary that forsome j ∈ N with j ≻ i, bθj Pj aθj or aθj Pj bθj . Let j be the highest-priority patient among
the patients who are not indiﬀerent between bθ and aθ .
′θFirst, suppose bθj Pj aθj . Note that b′θ ∈ I Y (R; θ) by b′θ
i = (0, ∅) and (6). Thus b ∈ΦY0 (R; θ). By the definition of j and (6), for each k ∈ N with k ≻ j, aθk Ik bθk Ik b′θ
k . Thus
′θ
Y
′θ
θ
θ
θ
Y
b ∈ Φj−1 (R; θ). By (6), bj Ij bj Pj aj . Thus we conclude a ̸∈ Φj (R; θ) ⊇ ΦY (R; θ),contradicting aθ = φP (R; θ) ∈ ΦY (R; θ).
Next, suppose that aθj Pj bθj . Note that a′θ ∈ I Y (Ri′ , R−i ; θ) by a′θ
i = (0, ∅) and (6).
Thus a′θ ∈ ΦY0 (Ri′ , R−i ; θ). By the definition of j and (6), for each k ∈ N with k ≻ j,′θθθbθk Ik aθk Ik a′θ∈ ΦYj−1 (Ri′ , R−i ; θ). By (6), a′θ
j Ij aj Pj bj . Thus we conclude
k . Thus abθ ̸∈ ΦYj (Ri′ , R−i ; θ) ⊇ ΦY (Ri′ , R−i ; θ). This contradicts bθ = φP (Ri′ , R−i ; θ) ∈ ΦY (Ri′ , R−i ; θ).
In either case, we obtain a contradiction. This completes the proof of Step 2.
Step 3: We complete the proof. Since bθ satisfies that bθi Pi aθi Ri (0, ∅) and bθk =φPk (Ri′ , R−i ; θ) Rk (0, ∅) for all k ∈ N \{i}, we have bθ ∈ I Y (R; θ) = ΦY0 (R; θ). Thus,
by Step 2, bθ ∈ ΦYi−1 (R; θ). Since bθi Pi aθi , we conclude aθ ̸∈ ΦYi (R; θ) ⊇ ΦY (R; θ). This
contradicts aθ = φP (R; θ) ∈ ΦY (R; θ).
Proof of Theorem 3. Without loss of generality, assume that 1 ≻ 2 ≻ . . . ≻ n. Supposeto the contrary that for some i ∈ N , (Ri∗ , θi∗ ) ∈ R × Θi , and Ri ∈ R,∑
(R−i ;θ−i )∈RN \{i} ×Θ−i

<

∑

)
(
pi (R−i ; θ−i | Ri∗ , θi∗ )u∗i φPi (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) Ri∗ , θi∗)(pi (R−i ; θ−i | Ri∗ , θi∗ )u∗i φPi (θdc ; (Ri , θi∗ ); (Rj , θj )j̸=i ) Ri∗ , θi∗ .

(7)(R−i ;θ−i )∈RN \{i} ×Θ−i′′
A direct consequence of the hypothesis (7) is that at least one (R−i; θ−i
) ∈ RN \{i} × Θ−i ,we have))((u∗i φPi (θd′ c ; (Ri∗ , θi∗ ); (Rj′ , θj′ )j̸=i ) Ri∗ , θi∗ < u∗i φPi (θd′ c ; (Ri , θi∗ ); (Rj′ , θj′ )j̸=i ) Ri∗ , θi∗(8)Thus, patient i is not the highest-priority patient, i.e., i ̸= 1. Since φPi (θd′ c ; (Ri∗ , θi∗ ); (Rj′ , θj′ )j̸=i )is at least as good as (0, ∅) at Ri∗ , patient i’s true preference Ri∗ has at least one acceptable49

transplantation type, i.e., Aci (Ri∗ ) ̸= ∅. Thus we can apply Assumption 2 to patient i. More()′′′
over, by Lemma 2, φPi (θd′ c ; (Ri∗ , θi∗ ); (Rj′ , θj′ )j̸=i ) ∈ Xi11 (θi∗ , θ−i)\X̃i11 (θi∗ , θ−i) ∪ Xi02 (θi∗ , θ−i
)
P
′
∗ ∗
′
′
and (0, ∅) Pi φi (θdc ; (Ri , θi ); (Rj , θj )j̸=i ). Consequently, at least one of the following two
statements holds:
02 is acceptable at Ri∗ , but not acceptable at Ri .

(9)

11 is acceptable at Ri∗ , but not acceptable at Ri .

(10)

In the subsequent part of the proof, we showφPi (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) ∈ Aci (Ri∗ )∃(R−i ; θ−i ) ∈ RN \{i} × Θ−i s.t. and.
φPi (θdc ; (Ri , θi∗ ); (Rj , θj )j̸=i ) = (0, ∅)(11)Note that (11) contradicts inequality (7) because Assumption 2 states that even if misreport()
ing Ri is successful for every (R̃−i ; θ̃−i ) ∈ RN \{i} × Θ−i \{(R−i ; θ−i )}, i.e., φPi (Ri , R̃−i ; θi∗ , θ̃−i ) Pi∗
φPi (Ri∗ , R̃−i ; θi∗ , θ̃−i ), the expected utility gain from misreporting is canceled out by the failure of misreporting at (R−i ; θ−i ) (See statement (11)).
In the following, we construct (R−i ; θ−i ) ∈ RN \{i} × Θ−i to show (11) for each caseseparately. For notational simplicity, we will use the following notation in every case.
a := φP (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) and b := φP (θdc ; (Ri , θi∗ ); (Rj , θj )j̸=i ).
That is, a denotes the allocation under i’s truth-telling at (R−i ; θ−i ) constructed in thecase under consideration, and b does the allocation under i’s misreporting at (R−i ; θ−i )constructed in the case under consideration.
By Assumption 4, let j, k ∈ N \{1, i} be distinct patients who have two living donors.
Let D1L = {d11 , d12 }, DjL = {dj1 , dj2 }, and DkL = {dk1 , dk2 }.
Case 1: Patient i has two living donors, i.e., |DiL | = 2. Let DiL = {di1 , di2 }.
Case 1.1: (9) holds.
∗∗∗(di2 )} | = 3. Without loss of generality, let θi∗ (i) = (x, I), θi∗ (di1 ) =(di1 ), θi2(i), θi2
Case 1.1.1: | {θi2(y, II), θi∗ (di2 ) = (z, III), where x, y, z ∈ B. Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i as follows:50

Figure 9: Allocations a and b in Case 1.1.1.

L• The definition of θ−i : Let m ∈ N \ {1, i, j} and d ∈ Dm.


θ1 (1) = (AB, II){() θdc = 2, (AB, IV )
θ1 (d11 ) = (O, II)θ1 (d12 ) = (O, I){θj (j) = (AB, III)θm (m) = (O, IV )θj (dj1 ) = (O, III)θm (d) = (AB, IV )θj (dj2 ) = (O, I)• The definition of R−i .42
R1
Rj

02 00
02 00

···
···

Claim 1.1.1a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,

am =




(0, {di1 , d11 }) if m = 1,(0, {d , d }) if m = i,
12

j2



(0, {di2 , dj1 }) if m = j,(0, ∅) if m ∈ N \{1, i, j}.

Proof. Since the above allocation is the only individually rational and Pareto eﬃcient
allocation at (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), φP selects it. □Claim 1.1.1b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,bm = (0, ∅).
Proof. Since 02 is unacceptable at Ri , patients 1 and j cannot receive living-donor dualgraft transplants. Moreover the grafts from the deceased donor are not compatible with any
patient. □∗∗∗(di2 )} | = 2.
(di1 ), θi2(i), θi2
Case 1.1.2: | {θi2
The preferences of patients in N \{1, i, j} are omitted because they are free. In the later cases, theomitted preferences are free, too.
42

51

Figure 10: Allocations a and b in Case 1.1.2.1.

∗∗
Case 1.1.2.1: θi2(di1 ) ̸= θi2(di2 ). Without loss of generality, let θi∗ (i) = (x, I), θi∗ (di1 ) =(y, I), θi∗ (di2 ) = (z, II), where x, y, z ∈ B. Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i as follows:L• The definition of θ−i : Let m ∈ N \ {1, i, j} and d ∈ Dm.


 θ1 (1) = (AB, I){() θdc = 2, (AB, III)
θ1 (d11 ) = (O, II)θ1 (d12 ) = (O, I){θj (j) = (AB, II)θm (m) = (O, IV )θj (dj1 ) = (O, I)θm (d) = (AB, IV )θj (dj2 ) = (O, I)• The definition of R−i .
R1
Rj

02 00
02 00

···
···

Claim 1.1.2.1a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,
X 02 (θ∗ , θ ) if m ∈ {1, i, j},
−i
m
i
am ∈
X 00 (θ∗ , θ ) if m ∈ N \{1, i, j}.
m

i

−i

Proof. Since the above allocation is the only individually rational and Pareto eﬃcient
allocation at (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), φP selects it. 2
Claim 1.1.2.1b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,bm = (0, ∅).
Proof. Since 02 is unacceptable at Ri , bi cannot be 02. Moreover the grafts from thedeceased donor are not compatible with patient i. Thus bi = (0, ∅). This implies that di2
does not donate to any patient (Proposition 1). Thus, bj = (0, ∅), since 02 is the only
acceptable transplantation type for patient j. This implies that dj1 and dj2 do not donate
to any patient. Thus b1 = (0, ∅). 2∗∗(di2 ). Without loss of generality, let θi∗ (i) = (x, I), θi∗ (di1 ) =(di1 ) = θi2Case 1.1.2.2: θi2(y, II), θi∗ (di2 ) = (z, II), where x, y, z ∈ B. Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i as follows:52

Figure 11: Allocations a and b in Case 1.1.2.2.

L• The definition of θ−i : Let m ∈ N \ {1, i, j} and d ∈ Dm.


 θ1 (1) = (AB, II){() θdc = 2, (AB, IIV )θ1 (d11 ) = (O, III)
θ1 (d12 ) = (O, III){θj (j) = (AB, III)θm (m) = (O, IV )θj (dj1 ) = (O, I)θm (d) = (AB, IV )θj (dj2 ) = (O, I)• The definition of R−i .
R1
Rj

02 00
02 00

···
···

Claim 1.1.2.2a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,

am =




(0, DiL ) if m = 1,(0, DL ) if m = i,j(0, D1L ) if m = j,





(0, ∅) if m ∈ N \{1, i, j}.

Proof. Since the above allocation is the only individually rational and Pareto eﬃcient
allocation at (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), φP selects it. 2
Claim 1.1.2.2b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,bm = (0, ∅).
Proof. Since 02 is unacceptable at Ri , bi cannot be 02. Moreover the grafts from thedeceased donor are not compatible with patient i. Thus, bi = (0, ∅). This implies that di1
and di2 do not donate to any patient (Proposition 1). Thus b1 = (0, ∅) since 02 is the only
acceptable transplantation type for patient 1. This implies that d11 and d12 do not donate
to any patient. Thus bj = (0, ∅). 2∗∗∗(di2 )} | = 1. Without loss of generality, let θi∗ (i) = (x, I), θi∗ (di1 ) =(di1 ), θi2(i), θi2
Case 1.1.3: | {θi2(y, I), θi∗ (di2 ) = (z, I), where x, y, z ∈ B. Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i as follows:53

Figure 12: Allocations a and b in Case 1.1.3.

L• The definition of θ−i : Let m ∈ N \ {1, i, j} and d ∈ Dm.


 θ1 (1) = (AB, I){() θdc = 2, (AB, III)
θ1 (d11 ) = (O, II)θ1 (d12 ) = (O, II){θj (j) = (AB, II)θm (m) = (O, III)θj (dj1 ) = (O, I)θm (d) = (AB, III)θj (dj2 ) = (O, I)• The definition of R−i .
R1
Rj

02 00
02 00

···
···

Claim 1.1.3a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,
X 02 (θ∗ , θ ) if m ∈ {1, i, j},
−i
m
i
am ∈
X 00 (θ∗ , θ ) if m ∈ N \{1, i, j}.
m

i

−i

Proof. Since the above allocation is the only individually rational and Pareto eﬃcient
allocation at (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), φP selects it. 2
Claim 1.1.3b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,
(0, DjL ) if m = 1,
bm = (0, D1L ) if m = j,(0, ∅) if m ∈ N \{1, j}.
Proof. Since 02 is unacceptable at Ri , bi cannot be 02. Moreover the grafts from thedeceased donor are not compatible with patient i. Thus bi = (0, ∅). The only individually
rational and Pareto eﬃcient allocation at (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), φP selects it. 2
Case 1.2: (10) holds.

54

∗
∗
∗
Case 1.2.1: | {θi2(i), θi2(di1 ), θi2(di2 )} | = 3. Without loss of generality, let θi∗ (i) = (x, I), θi∗ (di1 ) =(y, II), θi∗ (di2 ) = (z, III), where x, y, z ∈ B. Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i as follows:L• The definition of θ−i : For m ∈ N \ {1, i, j} and d ∈ Dm,
 θ1 (1) = (AB, I)() {θdc = 2, (O, I)θ1 (d11 ) = (O, I)θ1 (d12 ) = (O, II){θj (j) = (AB, II)θm (m) = (O, IV )θj (dj1 ) = (O, I)θm (d) = (AB, IV )θj (dj2 ) = (O, I)• The definition of R−i .
R1
Rj

02 20
02 00

00
···

···

Claim 1.2.1a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,

am ∈


02 ∗


Xm (θi , θ−i ) if m ∈ {1, j},


11 ∗
Xm
(θi , θ−i ) if m = i,
X 00 (θ∗ , θ ) if m ∈ N \{1, i, j}.
m

i

−i

Proof. Since the allocation in the left hand side of Figure 13 is in I Y (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) =ΦY0 (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), a1 ∈ X102 (θi∗ , θ−i ). Since a1 is 02, d12 donates to a patient(Proposition 1). Since only patient j can receive d12 ’s donation, d12 ∈ aLj . Since the only
acceptable transplantation type for j is 02, aj ∈ Xj02 (θi∗ , θ−i ). Since a1 and aj is 02, d11 ,dj1 and dj2 donate to a patient respectively (Proposition 1). Since two of them donate topatient 1, the remaining one donates to patient i. Since no other living donor is compatible
with patient i, ai ∈ Xi11 (θi∗ , θ−i ). 2
Claim 1.2.1b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,bm =(2, ∅) if m = 1,
(0, ∅) if m ∈ N \{1}.

Proof. In a similar manner to Claim 1.2.1a, we can show that b1 is 02 only if bi is 11.
However, since 11 is unacceptable at Ri , b1 is not 02. Thus b1 = (2, ∅). Thus each patientin N \{1} cannot use a graft from dc . Thus bm is not 20, 10 or 11 for each m ∈ N \{1}.
Since patient j cannot find two compatible living donors in DL \D1L , bj ̸∈ Xj02 (θi∗ , θ−i ).
Thus bj = (0, ∅). Since patient m ∈ N \{1, j} cannot find two compatible living donors in
02 ∗(θi , θ−i ). Thus bm = (0, ∅). 2
DL \(D1L ∪ DjL ), bm ̸∈ Xm
55

Figure 13: Allocations a and b in Case 1.2.1.

∗∗∗
Case 1.2.2: | {θi2(i), θi2(di1 ), θi2(di2 )} | = 2.
∗∗
Case 1.2.2.1: θi2(di1 ) ̸= θi2(di2 ). Without loss of generality, let θi∗ (i) = (x, I), θi∗ (di1 ) =(y, I), θi∗ (di2 ) = (z, II), where x, y, z ∈ B. We consider the following three cases separately.
Case 1.2.2.1.1: y ̸ 1 x. Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i as follows:L• The definition of θ−i : Let m ∈ N \ {1, i, j} and d ∈ Dm.


 θ1 (1) = (x, I){() θdc = 2, (O, I)θ1 (d11 ) = (O, II)θ1 (d12 ) = (O, III) θj (j) = (AB, II)θj (dj1 ) = (O, I)θj (dj2 ) = (O, III)θk (k) = (AB, III)θk (dk1 ) = (O, I)θk (dk2 ) = (O, I){

θm (m) = (O, IV )θm (d) = (AB, IV )• The definition of R−i .
R1
Rj
Rk

02
02
02

20
00
00

00
···
···

···

Claim 1.2.2.1.1a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,
X 02 (θ∗ , θ ) if m ∈ {1, j, k}, m i −i11 ∗am ∈ Xm(θi , θ−i ) if m = i,
X 00 (θ∗ , θ ) if m ∈ N \{1, i, j, k}.
m

i

−i

Proof. Since the allocation in the left hand side of Figure 14 is in I Y (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) =ΦY0 (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), a1 ∈ X102 (θi∗ , θ−i ). Since a1 is 02, d11 and d12 donate to a patient respectively (Proposition 1). Since only patients j and k can receive d11 ’s and d12 ’s
donation respectively, d11 ∈ aLj and d12 ∈ aLk . Since the only acceptable transplantation
56

Figure 14: Allocations a and b in Case 1.2.2.1.1.

type for j and k is 02, aj ∈ Xj02 (θi∗ , θ−i ) and ak ∈ Xk02 (θi∗ , θ−i ). Thus aLj = {d11 , di2 } andaLk = {d12 , dj2 }. Since aj and ak are 02, dj1 , dk1 and dk2 donate to a patient respectively(Proposition 1). Since two of them donate to patient 1, the remaining one donates to patient i (Recall that y ̸ 1 x). Since no other living donor is compatible with patient i,ai ∈ Xi11 (θi∗ , θ−i ). 2
Claim 1.2.2.1.1b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,bm =(2, ∅) if m = 1,
(0, ∅) if m ∈ N \{1}.

Proof. In a similar manner to Claim 1.2.2.1.1a, we can show that b1 is 02 only if bi is 11.
However, since 11 is unacceptable at Ri , b1 is not 02. Thus b1 = (2, ∅). Thus each patientin N \{1} cannot use a graft from dc . Thus bm is not 20, 10 or 11 for each m ∈ N \{1}.
Since patient k cannot find two compatible living donors in DL \D1L , bk ̸∈ Xk02 (θi∗ , θ−i ).
Thus bk = (0, ∅). Since patient m ∈ N \{1, k} cannot find two compatible living donors in
02 ∗DL \(D1L ∪ DkL ), bm ̸∈ Xm(θi , θ−i ). Thus bm = (0, ∅). 2
Case 1.2.2.1.2: y = x. Note that y = x implies that θi∗ (i) = (x, I) = (y, I) = θi∗ (di1 ).
Thus, by Assumption 5, this case is excluded.
Case 1.2.2.1.3: y 1 x and y ̸= x. Note that y 1 x and y ̸= x imply that the combinationof x and y is one of the following five: (O, A), (O, B), (O, AB), (A, AB), (B, AB). Note alsothat each of them satisfies x ̸ 1 y. Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i as follows:

57

L• The definition of θ−i : Let m ∈ N \ {1, i, j} and d ∈ Dm.


 θ1 (1) = (y, I){() θdc = 2, (O, I)θ1 (d11 ) = (O, III)
θ1 (d12 ) = (O, III){θj (j) = (AB, III)θm (m) = (O, IV )θj (dj1 ) = (x, I)θm (d) = (AB, IV )θj (dj2 ) = (y, I)• The definition of R−i .
R1
Rj

02 20
02 00

00
···

···

Claim 1.2.2.1.3a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,

am =




(0, {di1 , dj2 }) if m = 1,(1, {d }) if m = i,j1

(0, {d11 , d12 }) if m = j,(0, ∅) if m ∈ N \{1, i, j}.

Proof. Since the above allocation is in I Y (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) = ΦY0 (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ),a1 ∈ X102 (θi∗ , θ−i ). Since only di1 and dj2 are compatible with patient 1, a1 = (0, {di1 , dj2 })(Recall that x ̸ 1 y). Since a1 is 02, d11 and d12 donate to a patient respectively (Proposition 1). Since only patients j can receive d11 ’s and d12 ’s donation, aj = (0, {d11 , d12 }).
Since aj is 02, dj1 donates to a patient (Proposition 1). Since patient 1 cannot receive dj1 ’s
donation, it goes to i, i.e., dj1 ∈ aLi . Since no other living donor is compatible with patienti, ai = (1, {dj1 }). 2
Claim 1.2.2.1.3b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,bm =(2, ∅) if m = 1,
(0, ∅) if m ∈ N \{1}.

Proof. In a similar manner to Claim 1.2.2.1.3a, we can show that b1 is 02 only if bi is 11.
However, since 11 is unacceptable at Ri , b1 is not 02. Thus b1 = (2, ∅). Thus each patientin N \{1} cannot use a graft from dc . Thus bm is not 20, 10 or 11 for each m ∈ N \{1}.
Since patient j cannot find two compatible living donors in DL \D1L , bj ̸∈ Xj02 (θi∗ , θ−i ).
Thus bj = (0, ∅). Since patient m ∈ N \{1, j} cannot find two compatible living donors in
02 ∗(θi , θ−i ). Thus bm = (0, ∅). 2
DL \(D1L ∪ DjL ), bm ̸∈ Xm
58

Figure 15: Allocations a and b in Case 1.2.2.1.3.

∗∗
Case 1.2.2.2: θi2(di1 ) = θi2(di2 ). Without loss of generality, let θi∗ (i) = (x, I), θi∗ (di1 ) =(y, II), θi∗ (di2 ) = (z, II), where x, y, z ∈ B. Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i as follows:L• The definition of θ−i : Let m ∈ N \ {1, i, j} and d ∈ Dm.

(){
θdc = 2, (O, I){ θ1 (1) = (AB, I)
θ1 (d11 ) = (O, I)θ1 (d12 ) = (O, III) θj (j) = (AB, II)θj (dj1 ) = (O, I)θj (dj2 ) = (O, III)θk (k) = (AB, III)θk (dk1 ) = (O, II)θk (dk2 ) = (O, I)

θm (m) = (O, IV )θm (d) = (AB, IV )• The definition of R−i .
R1
Rj
Rk

02
02
02

20
00
00

00
···
···

···

Claim 1.2.2.2a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,
X 02 (θ∗ , θ ) if m ∈ {1, j, k} m i −i11 ∗am ∈ Xm(θi , θ−i ) if m = iX 00 (θ∗ , θ ) if m ∈ N \{1, i, j, k}.
m

i

−i

Proof. Since the allocation in the left hand side of Figure 16 is in I Y (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) =ΦY0 (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), a1 ∈ X102 (θi∗ , θ−i ). Since a1 is 02, d12 donates to a patient(Proposition 1). Since only patients k can receive d12 ’s donation, d12 ∈ aLk . Since theonly acceptable transplantation type for patient k is 02, ak ∈ Xk02 (θi∗ , θ−i ). Thus aLk ={d12 , dj2 }. Since dj2 donates to patient k, patient j receives an acceptable transplant, i.e.
aj ∈ Xj02 (θi∗ , θ−i ). Thus aLj consists of dk1 and one of di1 and di2 (Note that if aLj = DiL ,59

Figure 16: Allocations a and b in Case 1.2.2.2.

then dk1 cannot donate to any patient). Since a1 , aj and ak are 02, d11 , dj1 and dk2 donate
to a patient respectively (Proposition 1). Since two of them donate to patient 1, the remaining one donates to patient i, i.e., ai uses a living donor. Since no other living donor iscompatible with patient i, ai ∈ Xi11 (θi∗ , θ−i ). 2
Claim 1.2.2.2b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,bm =(2, ∅) if m = 1,
(0, ∅) if m ∈ N \{1}.

Proof. In a similar manner to Claim 1.2.2.2a, we can show that b1 is 02 only if bi is 11.
However, since 11 is unacceptable at Ri , b1 is not 02. Thus b1 = (2, ∅). Thus each patientin N \{1} cannot use a graft from dc . Thus bm is not 20, 10 or 11 for each m ∈ N \{1}.
Since patient k cannot find two compatible living donors in DL \D1L , bk ̸∈ Xk02 (θi∗ , θ−i ). Thus
bk = (0, ∅). Since patient j cannot find two compatible living donors in DL \(D1L ∪ DkL ), bj ̸∈
Xj02 (θi∗ , θ−i ). Thus bj = (0, ∅). Since patient m ∈ N \{1, j, k} cannot find two compatible
02 ∗living donors in DL \(D1L ∪ DjL ∪ DkL ), bm ̸∈ Xm(θi , θ−i ). Thus bm = (0, ∅). 2∗∗∗
Case 1.2.3: | {θi2 (i), θi2 (di1 ), θi2 (di2 )} | = 1. Without loss of generality, let θi∗ (i) = (x, I), θi∗ (di1 ) =(y, I), θi∗ (di2 ) = (z, I), where x, y, z ∈ B. By the definition of Θi , at least one of di1 and di2
is not compatible with patient i, i.e., y ̸ 1 x or z ̸ 1 x. Without loss of generality, assume
that y ̸ 1 x. Thus x ̸= AB. By Lemma 3, x ̸ 1 y or x ̸ 1 z. Thus x ̸= O. Summing
up, we have x ∈ {A, B}. Without loss of generality, we assume x = A till the end of Case
1.2.3.43
Note that since y ̸ 1 x, y ∈ {B, AB}. Moreover, we have the following two claims that43

The same argument works for the case with x = B by replacing A with B and B with A in the proof
given here.

60

narrow down the combination of x, y and z.
Claim 1.2.3: The combination of x, y and z, written as (x, y, z), is one of the following five:(i) (A, B, O), (ii) (A, B, B), (iii) (A, B, AB), (iv) (A, AB, O), and (v) (A, AB, B).
Proof. First, we show that y = B or z ∈ {O, B} by contradiction. Suppose to the contrary
that y ̸= B and z ̸∈ {O, B}. Since y ∈ {B, AB}, y = AB. Since z ∈ B\{O, B} = {A, AB},
we have x = A 1 AB = y and x = A 1 z, contradicting Lemma 3.
Now we complete the proof of Claim 1.2.3. Note that x = A and y ∈ {B, AB}. First
consider the case with y = B. Since z = A is impossible by Assumption 5, we have (i),(ii), and (iii). Next consider the case with y = AB. By the fact shown in the previous
paragraph, we have z ∈ {O, B}. Thus we have (iv) and (v). 2
We omit the proof for the case (v) because it is same as the one for case (iii). Let us
consider the following two cases of 1.2.3.1 and 1.2.3.2 separately.
Case 1.2.3.1: (x, y, z) is (i)(A, B, O) or (iv)(A, AB, O). Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i
as follows:L• The definition of θ−i : Let m ∈ N \ {1, i, j} and d ∈ Dm.


θ1 (1) = (AB, II){() θdc = 1, (O, I)θ1 (d11 ) = (O, II)θ1 (d12 ) = (O, I){ θj (j) = (O, I)
θm (m) = (O, III)θj (dj1 ) = (A, I)θm (d) = (AB, III)θj (dj2 ) = (O, II)• The definition of R−i .
R1
Rj

02 00
02 11

···
00

···

Claim 1.2.3.1a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,

am =




(0, {d11 , dj2 }) if m = 1,(1, {d }) if m = i,j1

(0, {d12 , di2 }) if m = j,





(0, ∅) if m ∈ N \{1, i, j}.

Proof. Since the allocation in the left hand side of Figure 17 is in I Y (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) =ΦY0 (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), a1 ∈ X102 (θi∗ , θ−i ). Since only d11 and dj2 are compatible withpatient 1, a1 = (0, {d11 , dj2 }). Note that this implies that aLj contains at least one living
donor, i.e., aj is 11 or 02.
61

Figure 17: Allocations a and b in Case 1.2.3.1.

Since θdc q = 1, ai cannot be 20. Moreover, ai cannot be 10 since it implies that aj is
not 11 (∵ patient j cannot use the graft from dc ) and not 02 (∵ patient j cannot receivea donation from di2 by Proposition 1). Moreover, ai cannot be 02 since it implies that di1
who has no compatible patient donates to a patient. Moreover, ai cannot be 00 (∵ Since 11
is acceptable at Ri∗ , the allocation described in the left hand side of Figure 17 excludes the
allocations that assign (0, ∅) to patient i). Summing up, ai ∈ Xi11 (θi∗ , θ−i ). The allocation
described in the left hand side of Figure 17 enable patient j to receive 02 under the condition
that a1 ∈ X102 (θi∗ , θ−i ) and ai ∈ Xi11 (θi∗ , θ−i ). Thus aj is 02. Thus aj = (0, {d12 , di2 }) (∵Only d12 and di2 are compatible living donors with patient j). Thus ai = (1, {dj1 }). 2
Claim 1.2.3.1b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,
(0, {d11 , dj2 }) if m = 1,
bm = (1, {d12 }) if m = j,(0, ∅) if m ∈ N \{1, j}.
Proof. In a similar manner to Claim 1.2.3.1a, we can show that b1 = (0, {d11 , dj2 }). Notethat this implies that bLj contains at least one living donor, i.e., bj is 11 or 02.
In a similar manner to Claim 1.2.3.1a, we can show that bi is not 20, 10 or 02. Moreover,since 11 is unacceptable at Ri , bi is not 11. Thus bi = (0, ∅). Since patient j cannot findcompatible living donors in DL \D1L , bj is not 02. Thus bj is 11 since the allocation describedin the right hand side of Figure 17 is available. Since it is the only allocation that assigns
02 to patient 1 and 11 to patient j, we are done. 2
Case 1.2.3.2: (x, y, z) is (ii)(A, B, B) or (iii)(A, B, AB). Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i
as follows:

62

L• The definition of θ−i : Let m ∈ N \ {1, i, j} and d ∈ Dm.


θ1 (1) = (AB, II){() θdc = 1, (O, I)θ1 (d11 ) = (O, II)θ1 (d12 ) = (B, I){ θj (j) = (B, I)
θm (m) = (O, III)θj (dj1 ) = (A, I)θm (d) = (AB, III)θj (dj2 ) = (O, II)• The definition of R−i .
R1
Rj

02 00
02 11

···
00

···

Claim 1.2.3.2a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,
(0, {d11 , dj2 }) if m = 1,






(1, {dj1 }) if m = i,am = (0, {d12 , di1 }) if m = j and (iii) holds,(0, {d , d }) or (0, {d , d }) if m = j and (ii) holds,

12 i1
12 i2




(0, ∅) if m ∈ N \{1, i, j}.
Proof. Since the allocation in the left hand side of Figure 18 is in I Y (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) =ΦY0 (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), a1 ∈ X102 (θi∗ , θ−i ). Since only d11 and dj2 are compatible withpatient 1, a1 = (0, {d11 , dj2 }). Note that this implies that aLj contains at least one living
donor, i.e., aj is 11 or 02.
Since θdc q = 1, ai cannot be 20. Moreover, ai cannot be 10 since it implies that aj is
not 11 (∵ patient j cannot use the graft from dc ) and not 02 (∵ patient j cannot receivea donation from a patient in DiL by Proposition 1). Moreover, ai cannot be 02 since it
implies that both di1 and di2 donate to a patient respectively. Note that d12 also donates
to a patient since a1 is 02. However, since the economy can receive donation from at mosttwo of di1 , di2 and d12 , one of di1 and di2 cannot donate any patient. Thus ai is not 02.
Moreover, ai cannot be 00 (∵ Since 11 is acceptable at Ri∗ , the allocation described in theleft hand side of Figure 18 excludes the allocations that assign (0, ∅) to patient i). In sum,ai ∈ Xi11 (θi∗ , θ−i ). The allocation described in the left hand side of Figure 18 enable patient
j to receive 02 under the condition that a1 ∈ X102 (θi∗ , θ−i ) and ai ∈ Xi11 (θi∗ , θ−i ). Thus aj is
02. Thus aLj consists of d12 and a donor in DiL (∵ Donors in DjL are not compatible withpatient j). Thus ai = (1, {dj1 }). 2

63Figure 18: Allocations a and b in Case 1.2.3.2.

Claim 1.2.3.2b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,(0, {d11 , dj2 }) if m = 1,bm =(1, {d12 }) if m = j,(0, ∅) if m ∈ N \{1, j}.

Proof. In a similar manner to Claim 1.2.3.2a, we can show that b1 = (0, {d11 , dj2 }). Notethat this implies that bLj contains at least one living donor, i.e., bj is 11 or 02.
In a similar manner to Claim 1.2.3.2a, we can show that bi is not 20, 10 or 02. Moreover,since 11 is unacceptable at Ri , bi is not 11. Thus bi = (0, ∅). Since patient j cannot findcompatible living donors in DL \D1L , bj is not 02. Thus bj is 11 since the allocation describedin the right hand side of Figure 18 is available. Since it is the only allocation that assigns
02 to patient 1 and 11 to patient j, we are done. 2
Case 2: Patient i has one living donors, i.e., |DiL | = 1. Let DiL = {di }. Note that, by
Proposition 1, patient i never receives a living-donor dual-graft transplant at any profile in
RN × Θ. Thus, (10) holds.
∗∗
Case 2.1: | {θi2(i), θi2(di )} | = 2. Without loss of generality, let θi∗ (i) = (x, I) and θi∗ (di ) =(y, II), where x, y ∈ B. Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i as follows:L.
• The definition of θ−i : Let m ∈ N \ {1, i, j} and d ∈ Dm{()
θdc = 2, (O, I){ θ1 (1) = (AB, I)
θ1 (d11 ) = (O, I)θ1 (d12 ) = (O, III)θm (m) = (O, IV )θm (d) = (AB, IV )• The definition of R−i .
64 θj (j) = (AB, II)θj (dj1 ) = (O, I)θj (dj2 ) = (O, III)θk (k) = (AB, III)θk (dk1 ) = (O, II)θk (dk2 ) = (O, I)

R1
Rj
Rk

02
02
02

20
00
00

00
···
···

···

Claim 2.1a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,
X 02 (θ∗ , θ ) if m ∈ {1, j, k}, m i −i11 ∗am ∈ Xm(θi , θ−i ) if m = i,
X 00 (θ∗ , θ ) if m ∈ N \{1, i, j, k}.
m

i

−i

Proof. Since the allocation in the left hand side of Figure 19 is in I Y (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) =ΦY0 (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ), a1 ∈ X102 (θi∗ , θ−i ). Since a1 is 02, d12 donates to a patient(Proposition 1). Since only patients k can receive d12 ’s donation, d12 ∈ aLk . Since theonly acceptable transplantation type for patient k is 02, ak ∈ Xk02 (θi∗ , θ−i ). Thus aLk ={d12 , dj2 }. Since dj2 donates to patient k, patient j receives an acceptable transplant, i.e.
aj ∈ Xj02 (θi∗ , θ−i ). Thus aLj = {di , dk1 } (∵ Only di and dk1 are compatible with patient j).
Thus patient i receives a donation from a living donor, i.e., ai ∈ Xi11 (θi∗ , θ−i ). 2
Claim 2.1b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,bm =(2, ∅) if m = 1,
(0, ∅) if m ∈ N \{1}.

Proof. In a similar manner to Case 2.1a, we can show that b1 is 02 only if bi is 11. Since 11
is unacceptable at Ri , b1 is not 02. Thus b1 = (2, ∅). Since b1 does not use a living donor,
d11 and d12 do not donate to any patient. Since patient k cannot find two compatible living
donors in DL \D1L , bk is not 02. Thus bk = (0, ∅). Since bk does not use a living donor, dk1
and dk2 do not donate to any patient. Since patient j cannot find two compatible living
donors in DL \(D1L ∪ DkL ), bj is not 02. Thus bj = (0, ∅). Since patient i cannot use a graftfrom dc , bi is not 20, 10 or 11. 2∗∗(di )} | = 1. Without loss of generality, let θi∗ (i) = (x, I) and θi∗ (di ) =(i), θi2
Case 2.2: | {θi2(y, I), where x, y ∈ B. Note that x ̸ 1 y by Lemma 3. Define (R−i ; θ−i ) ∈ RN \{i} × Θ−i asfollows:

65

Figure 19: Allocations a and b in Case 2.1.

L
• The definition of θ−i : For m ∈ N \ {1, i, j} and d ∈ Dm,{
 θ1 (1) = (y, I){() θm (m) = (O, III)
θdc = 2, (O, I)θ1 (d11 ) = (x, I)θm (d) = (AB, III)
θ1 (d12 ) = (O, II)• The definition of R−i .
R1

11 20

00

···

Claim 2.2a: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation a is, for each m ∈ N ,
(1, {di }) if m = 1,


am =

(1, {d11 }) if m = i,(0, ∅) if m ∈ N \{1, i}.

Proof. Since the above allocation is in I Y (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ) = ΦY0 (θdc ; (Ri∗ , θi∗ ); (Rj , θj )j̸=i ),a1 ∈ X111 (θi∗ , θ−i ). Since di is the only living donor compatible with patient 1, a1 = (1, {di }).
By Proposition 1, one of d11 and d12 donates to a patient. Since donor d12 has no compatible
patient, d11 donates to patient i. Thus ai = (1, {d11 }). 2
Claim 2.2b: For the above (R−i ; θ−i ) ∈ RN \{i} × Θ−i , allocation b is, for each m ∈ N ,bm =(2, ∅) if m = 1,
(0, ∅) if m ∈ N \{1}.

Proof. Note that patient 1 cannot receive a hybrid transplant with own donor since x ̸ 1 y.
Since 11 is unacceptable at Ri , b1 is not 11. Thus b1 = (2, ∅). Since patient 1 uses two grafts
66

Figure 20: Allocations a and b in Case 2.2.

from dc , patient i cannot use a graft from dc . Thus bi is not 20, 10 or 11. Thus bi = (0, ∅).
2Case 3: DiL contains no living donor. Note that, by Proposition 1, patient i never receives
a living-donor dual-graft transplant or a hybrid transplant at any profile in RN × Θ. Thus,by Lemma 2, patient i cannot manipulate φP .

References
Abdulkadiroğlu, A., and T. Sönmez (1999): “House Allocation with Existing Tenants,”
Journal of Economic Theory, 88, 233–260.
(2003): “School Choice: A Mechanism Design Approach,” Americal Economic
Review, 93, 729–747.
Anno, H., and M. Kurino (2016): “On the Operation of Multiple Matching Markets,”
Games and Economic Behavior, 100, 166–185.
Balinski, M., and T. Sönmez (1999): “A Tale of Two Mechanisms: Student Placement,”
Journal of Economic Theory, 84, 73–94.
Budish, E., and E. Cantillon (2012): “The Multi-unit Assignment Problem: Theory
and Evidence from Course Allocation at Harvard,” American Economic Review, 102(5),2237–2271.
D’Aspremont, C., and B. Peleg (1988): “Ordinal Bayesian Incentive Compatible Representation of Committees,” Social Choice and Welfare, 5, 261–280.
Ehlers, L., and J. Massó (2007): “Incomplete information and singleton cores in matching markets,” Journal of Economic Theory, 136, 587–600.

67

(2015): “Matching markets under (in)complete information,” Journal of Economic
Theory, 136, 295–314.
Ergin, H., T. Sönmez, and M. U. Ünver (2017): “Dual-Donor Organ Exchange,” Econometrica, 85(5), 1645–1671.
(2018): “Eﬃcient and Incentive-Compatible Liver Exchange,” Boston College Working Papers in Economics 951.
Hylland, A., and R. Zeckhauser (1979): “The Eﬃcient Allocation of Individuals to
Positions,” Journal of Political Economy, 87, 293–314.
Klaus, B., and E. Miyagawa (2001): “Strategy-proofness, Solidarity, and Consistency
for Multiple Assignment Problems,” International Journal of Game Theory, 30, 421–435.
Konishi, H., T. Quint, and J. Wako (2001): “On the Shapley-Scarf Economy: The Caseof Multiple Types of Indivisible Goods,” Journal of Mathematical Economics, 35, 1–15.
Lee, S., S. Hwang, K. Park, Y. Lee, D. Choi, C. Ahn, Y. Nah, K. Koh, S. Han,
S. Park, and P. Min (2001): “An adult-to-adult living donor liver transplant using dual
left lobe grafts,” Surgery, 129, 647–650.
Majumdar, D., and A. Sen (2004): “Ordinally Bayesian Incentive Compatibile Voting
Rules,” Econometrica, 72, 523–540.
Moulin, H. (1995): Cooperative Microeconomics: A Game-Theoretic Introduction. Princeton University Press.
Pápai, S. (2001): “Strategyproof and Nonbossy Multiple Assignments,” Journal of Public
Economic Theory, 3, 257–271.
(2007): “Exchange in a General Market with Indivisible Goods,” Journal of Economic Theory, 132, 208–235.
Rapaport, F. T. (1986): “The case for a living emotionally related international kidney
donor exchange registry,” Transplantation Proceedings, 18, 5–9.
Roth, A. E., T. Sönmez, and M. U. Ünver (2004): “Kidney Exchange,” Quarterly
Journal of Economics, 119, 457–488.
(2005): “Pairwise Kidney Exchange,” Journal of Economic Theory, 125, 151–188.
68

Roth, A. E., and M. A. O. Sotomayor (1990): Two-sided matching: a study in gametheoretic modeling and analysis. Econometric Society monographs, Cambridge.
Shapley, L., and H. Scarf (1974): “On Cores and Indivisibility,” Journal of Mathematical
Economics, 1, 23–37.
Soejima, Y., A. Taketomi, T. Ikegami, T. Yoshizumi, H. Uchiyama, Y. Yamashita, M. Meguro, N. Harada, M. Shimada, and Y. Maehara (2008): “Living
Donor Liver Transplantation Using Dual Grafts from Two Donors: A Feasible Option
to Overcome Small-for-Size Graft Problems?,” American Journal of Transplantation, 8,
887–897.
Song, G.-W., S.-G. Lee, D.-B. Moon, C.-S. Ahn, S. Hwang, K.-H. Kim, T.-Y. Ha,
and D.-H. Jung (2017): “Dual-graft Adult Living Donor Liver Transplantation: An
Innovative Surgical Procedure for Live Liver Donor Pool Expansion,” Annals of Surgery,
266, 10–18.
Ünver, M. U. (2010): “Dynamic Kidney Exchange,” Review of Economic Studies, 77,
372–414.

69