Mohammad Akbarpour
email: mohamwad@stanford.edu

Julien Combe
email: julien.combe@polytechnique.edu

Yinghua He
email: yinghua.he@gmail.com

Victor Hiller
email: victor.hiller@u-paris2.fr

Robert Shimer
email: shimer@uchicago.edu

Olivier Tercieux
email: tercieux@pse.ens.fr

Nikhil Agarwal

Nick Arnosti

Itai Ashlagi

Eric Budish

Paul Milgrom

Michael Ostrovsky

Parag Pathak

Alvin Roth

Paulo Somaini

Tayfun Sonmez

Utku Unver

UNPAIRED KIDNEY EXCHANGE: OVERCOMING DOUBLE COINCIDENCE OF WANTS WITHOUT MONEY

For an incompatible patient-donor pair, kidney exchanges often forbid receipt-before-donation (the patient receives a kidney before the donor donates) and donation-before-receipt, causing a double-coincidence-of-wants problem. Our proposed algorithm, the Unpaired kidney exchange algorithm, uses "memory" as a medium of exchange to eliminate these timing constraints. In a dynamic matching model, we prove that Unpaired delivers a waiting time of patients close to optimal and substantially shorter than currently utilized state-of-the-art algorithms. Using a rich administrative dataset from France, we show that Unpaired achieves a match rate of 57 percent and an average waiting time of 440 days. The (infeasible) optimal algorithm is only slightly better (58 percent and 425 days); state-of-the-art algorithms deliver less than 34 percent and more than 695 days. We draw similar conclusions from the simulations of two large U.S. platforms. Lastly, we propose a range of solutions that can address the potential practical concerns of Unpaired.

Introduction

Transplantation is the treatment of choice for kidney failure. Yet, all around the world, many people struggle with dialysis while enduring long waits for transplantation and imposing substantial healthcare costs on society,1 with many thousands of patients dying each year, all due to the shortage of compatible organs. Kidney exchange is a recent innovation addressing this issue, especially when there are incompatible patient-donor pairs. An incompatible pair is formed when a donor is willing to donate a kidney to a patient but is unable to do so because she is biologically incompatible with the patient. Between two such pairs, if the donor of each pair is compatible with the patient in the other pair, the two pairs can exchange donor kidneys. While ingenious, this leads to the well-known "double-coincidence-of-wants" problem-you not only have to have the kidney that I want, but also have to want the kidney that I have [START_REF] Jevons | Money and the Mechanism of Exchange[END_REF].

Economists have proposed a solution to the kidney shortage: legalizing the exchange of money for kidneys [START_REF] Becker | Introducing incentives in the market for live and cadaveric organ donations[END_REF]. Such a marketplace would address two issues simultaneously.

First, it would break the double coincidence problem by allowing a donor to sell her kidney to any patient and permitting a patient to buy a kidney from any donor. Second, a kidney marketplace has the potential to increase the supply of kidneys. 2 While a kidney marketplace is appealing to some economists, many people find such a marketplace repugnant. [START_REF] Roth | Repugnance as a Constraint on Markets[END_REF] lists three reasons why a kidney marketplace might be repugnant.

First, giving a kidney to a loved one is intrinsically good, while giving one for money may be morally wrong because it objectifies the human body. Second, it is likely that disproportionately many poor people would sell a kidney, and this may be viewed as coercive. Third, a marketplace for kidneys can be a slippery slope into more ethically dubious arrangements, for example, those in which debtors could be forced to give a kidney in bankruptcy proceedings. We do not take a stance on whether a marketplace for kidneys is repugnant, but simply note that it is illegal everywhere in the world except Iran today, and that changing the law is probably not politically feasible in most countries.

Instead, we propose a new matching algorithm-Unpaired kidney exchange-to tackle the doublecoincidence-of-wants problem without creating a repugnant marketplace. The fundamental idea is that "memory" can serve as a medium of exchange [START_REF] Kocherlakota | Money is memory[END_REF]. In essence, we propose creating a market where patient i can receive the (compatible) object of donor j, even if donor i's object is not compatible with patient j. When such a trade happens, the system will "remember" that patient j has the right to receive an object in the future and that donor i's object can be given to some other patient in future.

While memory and money both break the double-coincidence-of-wants problem, money is likely to increase the supply of kidneys. In contrast, the Unpaired algorithm by design avoids encouraging kidney donation for pecuniary benefits, thereby avoiding the repugnance concerns. Donors give kidneys because they love someone who needs one, not because of money. Poor people cannot sell a kidney. Creditors cannot demand a kidney in return for discharging a debt. Technically, the key difference between money and memory is fungibility. The fungibility of money allows for potentially repugnant uses. The fact that memory is not fungible means that society can control how it is used to avoid concerns about repugnance.

In this paper, we investigate the Unpaired algorithm theoretically and empirically, and discuss its two incentive-related practical challenges. Section 2 develops a dynamic kidney exchange model with two types of patients. Patient-donor pairs arrive at some rate n. A fraction λ of patients are hard-to-match and the rest, 1 -λ, are easy-to-match. Hard-to-match and easy-to-match patients are compatible with a random donor with probabilities p H and p E , respectively, where p H < p E . This two-type assumption is a reasonable approximation to the continuous but bimodal distribution of match probability among the patients in kidney exchange in France and the U.S. Patients and donors stay until they are matched. The planner, everything else equal, wishes to match patients with donors as quickly as possible. Hence, the main objective of interest is minimizing the average waiting time of patients.

The Unpaired algorithm works as follows: whenever a new patient-donor pair arrives, match the patient to a compatible donor (if any), and match the donor to a compatible patient (if any), breaking ties in favor of hard-to-match patients. Therefore, a pair is allowed to engage in receiptbefore-donation (i.e., the patient receives a kidney before the donor donates) and donation-beforereceipt, solving the double coincidence problem by eliminating the timing constraints on the pair's kidney donation and receipt.

To evaluate the (relative) performance of the Unpaired algorithm, we study three alternative matching algorithms. The first-the Pairwise algorithm-matches two patient-donor pairs whenever they are pairwise compatible. The second-the Chain algorithm-starts with a finite number of altruistic donors and matches patients with donors whenever there exists a chain. These two algorithms and some combination of the two correspond to the state-of-the-art algorithms used in most countries. The third-the Optimal algorithm-minimizes patients' average waiting time in the class of all matching algorithms.

We prove the following results: First, for small values of p H , the Unpaired algorithm substantially outperforms the Pairwise algorithm. In particular, if the majority of patients are hard-to-match (i.e., λ ≥ 1/2), the ratio of the waiting times under the two algorithms is O(1/p H ). Even if there are more easy-to-match pairs (λ < 1/2), Unpaired still outperforms Pairwise. For instance, when only 30 percent of patients are hard-to-match, the waiting time of hard-to-match patients under Pairwise is at least twice as long as under Unpaired.

Second, when p H is small, the Unpaired algorithm outperforms the Chain algorithm; in particular, if the fraction of hard-to-match patients (λ) is large, the Chain algorithm's performance becomes substantially worse than Unpaired. For instance, if 60 percent of patients are hard-to-match, the Unpaired algorithm matches hard-to-match patients nearly twice as fast as Chain. We emphasize that this result (and only this result) is shown under the assumption that an easy-to-match patient is compatible with all donors (p E = 1). As noted in Ashlagi et al. (2019b), the Markov chain induced by the Chain algorithm is hard to analyze. However, our simulations and those in Ashlagi et al. (2019b) show that the average waiting time under the Chain algorithm when p E = 1 is a good approximation to the average waiting time for p E < 1; moreover, we theoretically show that the waiting time under Unpaired does not depend on p E . Finally, we compare the Unpaired algorithm with the Optimal algorithm. We prove that for small values of p H and any value of λ, the Optimal algorithm's waiting time is at least 50 percent of that under the Unpaired algorithm. In addition, if the Optimal algorithm is restricted to provide easyto-match patients with an average waiting time as short as their waiting time under the Unpaired algorithm, the waiting time under Unpaired is at most 38 percent more than under this restricted Optimal algorithm. Note that the Unpaired algorithm matches patients and donors greedily, while the Optimal algorithm is forward-looking and can in principle wait to thicken the market. This result, nevertheless, shows that the additional gains from thickening the market are relatively small. After presenting our theoretical results, we investigate empirically the performance and challenges of the Unpaired algorithm in Section 3. This is necessary because our theoretical model ignores many real-world details of the kidney exchange problem. For example, our assumption that a patient is compatible with a random donor with a high or low probability is only an approximation to the reality. Specifically, a patient's biological compatibility with a donor depends on blood type and tissue type compatibilities; the compatibility realizations are unlikely to be i.i.d. across patient-donor pairs in practice. The empirical analysis imposes no such assumptions on compatibilities. Instead, they directly come from data.

We rely on a dataset provided by the Agency of Biomedicine (Agence de la Biomédecine), a government agency that oversees all organ transplants in France. It covers the period of December 2013 to February 2018, including all transplants with deceased and living donors kidneys.

Our main simulation focuses on the 78 pairs who participated in France's kidney exchange program (KEP) in our sample period. This KEP is small relative to those in the U.S. but is comparable to many others in Europe, e.g., those in Austria, Belgium, Italy, Poland, and Portugal (see [START_REF] Biró | Building Kidney Exchange Programmes in Europe-An Overview of Exchange Practice and Activities[END_REF]. We also investigate how our results extend to larger platforms such as those in the U.S.. We run counterfactual simulations to compare four algorithms: Pairwise, Chain, Unpaired, and Optimal. We evaluate an algorithm's performance by the transplant rate (the fraction of the 78 patients receiving a transplant in the simulation period), as well as the average waiting time.

Computing the Optimal algorithm requires additional assumptions on the data generating process, so we instead simulate an even-better alternative, the Omniscient algorithm, which assumes that the planner has perfect foresight about all arrivals in our sample period. Given this perfect information, the planner simply minimizes the average waiting time of patients over our sample period.

Consistent with our theoretical results, the simulations show that Unpaired dominates the Pairwise and Chain algorithms and is very close to the Omniscient algorithm. In particular, both Pairwise and Chain have a transplant rate around 30 percent, while Unpaired obtains 57 percent, similar to Omniscient's transplant rate, 58 percent. The same pattern holds for waiting time-732 days for Pairwise, 701 days for Chain, 440 days for Unpaired, and 425 days for Omniscient.

We also find that the Unpaired algorithm improves hard-to-match patients' transplant rate and waiting time. A patient in the data is defined to be hard-to-match if she is hypersensitized, or tissue-type incompatible with more than 85 percent of the 13,622 donors, living or deceased, in our data. There are 21 such patients (out of 78) in our data. If one replaces Pairwise or Chain by Unpaired, the transplant rate among hard-to-match patients is doubled (from 15 or 16 percent to 32 percent), while their waiting time is significantly reduced (from 745 or 751 days to 591 days).

Again, the Omniscient algorithm does not significantly improve upon Unpaired. Similar results are found among patients with O bloody type, who are also relatively hard-to-match.

To show that these findings are not driven by the small size of the French KEP, we document similar performance advantages of Unpaired in three simulated large markets. In the first one, we identify and include 508 incompatible pairs who are likely to participate in an effective exchange. In the data, these are the incompatible pairs that went through desensitization, an immunosuppression procedure, for the transplant of an incompatible kidney. This creates a market with 586 pairs in our sample period, comparable to the U.K. KEP, the largest in Europe. We also simulate the two large platforms in the U.S., the Alliance for Paired Kidney Donation (APKD) and the National Kidney Registry (NKR). In the simulation, APKD has 781 pairs and NKR has 2320 pairs. As expected, all algorithms have a better performance in a larger market. Across all three large markets, Unpaired delivers an average transplant rate between 67-72 percent, close to Omniscient's performance and at least 16 percentage points higher than Pairwise, and an average waiting time 248-294 days, at least 156 days shorter than Pairwise. 3The Unpaired algorithm comes with two practical concerns. First, because of donation-beforereceipt, an unpaired patient may wait for a long time after her paired donor's donation. In our main simulation with the 78 French KEP pairs, the median waiting time among the 25 unpaired patients after their donors' donation is 220 days. A pair may find it unacceptable to donate a kidney in exchange for a kidney that may arrive so late. Second, due to receipt-before-donation, a donor may wait for a long time after her paired patient's transplantation, increasing the chance that she reneges or becomes unfit to donate. In our main simulation, the median waiting time among the 23 unpaired donors after their patients' transplant is 305 days. We also show that these waits decrease with market size in our simulations.

Similar challenges also exist in some current practices. The first concern, donation-before-receipt, is also observed in the voucher programs in the U.S. [START_REF] Veale | Vouchers for future kidney transplants to overcome chronological incompatibility between living donors and recipients[END_REF]. Donors in these programs donate their kidneys in exchange for a future kidney promise. Notably, some of their paired patients are not in an urgent need for a kidney, while some may not ever need one-their voucher will be used only if a member of their family needs a kidney. Yet, many donors are willing to participate, mitigating our first concern about the Unpaired algorithm.

The second concern, receipt-before-donation, is a challenge in the current practice of the Chain algorithm, where all donors donate after their paired patients' transplantation. As a robustness check, one of our counterfactual simulations allows donors to renege at a rate assumed in the medical literature [START_REF] Gentry | The roles of dominos and nonsimultaneous chains in kidney paired donation[END_REF], and we find that the impact of donor reneging on the performance of Unpaired is negligible.

These lessons from the current practices mitigate the two practical concerns. However, they may still be seen as obstacles, in particular, for small markets in which these concerns are more prominent. 4 Hence, we provide a practical solution by taking advantage of the flexibility of the Unpaired algorithm to introduce modifications that can (almost) fully address these concerns.

The first is to use the kidneys supplied to the deceased donor list (DDL), or DDL kidneys. We propose a modified Unpaired algorithm-Unpaired with DDL. We assign high-quality DDL kidneys to unpaired patients who are waiting after their donors' donation. For every DDL kidney used, an unpaired donor donates to a patient waiting on the DLL. We simulate this new version by combining the data on the French KEP and that on DDL kidneys in France. This algorithm reduces the median waiting time among unpaired patients to 2 days and that among unpaired donors to 8 days. These reductions are not at the expenses of the algorithm's overall performance: the transplant rate under Unpaired with DDL is 87 percent, while the waiting time among all patients falls to 143 days. Recall that Unpaired delivers 57 percent and 440 days.

The second modification prevents unpaired donors from reneging. In order to do so, the algorithm can have a donor donate to a patient on the DDL immediately after her paired patient's transplantation. Therefore, a donor has no time to renege after being unpaired from her patient.

Our simulations show that this modification does not significantly reduce the advantages of Unpaired with DDL.

Related works

The economics literature on kidney exchange starts with Roth et al. (2004). In a subsequent paper, [START_REF] Roth | Repugnance as a Constraint on Markets[END_REF] demonstrate the efficiency gains of creating a large kidney exchange, as well as those from allowing 3-way or larger cycles.

The double-coincidence-of-wants problem has been a known challenge since the beginning of kidney exchange. We now review the two approaches that have been used to tackle it in practice.

The first approach is to create a sufficiently thick market:

And we will show that, even without a medium of exchange, if the market is thick enough, the problem of the coincidence of wants can be substantially ameliorated by the organization of an appropriate clearinghouse. [START_REF] Roth | Repugnance as a Constraint on Markets[END_REF] Given the likelihood of biological compatibility, this approach requires an extremely thick market to be effective. The market is not thick in, for instance, France where the arrival rate of patient-donor pairs to the kidney exchange market has been less than 20 per year. Even on some US platforms with hundreds of pairs per year, thickening the market alone has not been enough to overcome the problem of coincidence of wants, largely due to the abundance of hard-to-match patients.

More recently, [START_REF] Sönmez | Incentivized kidney exchange[END_REF] propose an incentivized system to bring compatible pairs to participate in an exchange. This will not only increase the market thickness, but also help blood-type O patients who have a hard time finding a match.

The second approach is to authorize non-simultaneous exchanges by allowing receipt-beforedonation or donation-before-receipt. Non-simultaneous altruistic donor chains (Roth et al., 2006) allow for receipt-before-donation. A chain is initiated by an altruistic donor who donates a kidney to a patient whose paired donor then donates to another patient, and so on. Transplants may happen simultaneously or sequentially. Nowadays, such chains account for a large fraction of kidney exchange transplants. By allowing receipt-before-donation, a chain need not form a closed loop, and thus, can alleviate the problem of double-coincidence-of-wants:

Developing the capability to arrange trades in longer cycles and chains helps overcome this [double coincidences of wants] barrier... In the case of kidney exchange, long nonsimultaneous chains of the sort proposed in Roth et al. (2006) are proving increasingly important. (Ashlagi et al., 2012) While clever, the Chain algorithm confronts three practical challenges. First, its efficiency is limited by the number of available altruistic donors. Second, in places where altruistic donation is illegal (e.g., France and Germany), this algorithm is infeasible. Last but not the least, even with a reasonable number of altruistic donors, it goes only half-way in solving the double coincidence problem, because donation-before-receipt is not allowed. [START_REF] Ausubel | Sequential kidney exchange[END_REF] introduce the idea of "sequential kidney exchange" that allows donation-before-receipt but not receipt-before-donation, opposite to the Chain algorithm. They study this in an overlapping generations model. In this sense, our Unpaired algorithm combines Chain and sequential kidney exchange by allowing both donation-before-receipt and receipt-beforedonation.

Similar to the Unpaired algorithm is the voucher program that has been adopted by multiple hospitals in the U.S. [START_REF] Veale | Vouchers for future kidney transplants to overcome chronological incompatibility between living donors and recipients[END_REF]. This program allows donation-before-receipt; in particular, a donor can donate and receive a voucher that her paired recipient can use to receive a kidney in future. We compare this program with the Unpaired algorithm in Section 4.

Our theoretical model is related to those of dynamic kidney exchange. Ünver (2010) studies a model of dynamic exchange with blood-type considerations. [START_REF] Akbarpour | Thickness and information in dynamic matching markets[END_REF] consider a dynamic kidney exchange model with stochastic departures and show that optimal timing can be highly valuable; their focus, however, is only on pairwise exchanges. The two-type model studied here builds on the model of Ashlagi et al. (2019b), where they compare Chain and Pairwise.

Introducing memory as a medium of exchange relates our paper to the literature on the role of money in an economy [START_REF] Kocherlakota | Money is memory[END_REF]. In this sense, our paper demonstrates an application of classic monetary models.

Theoretical Analysis

Model

We now introduce a continuous-time, infinite-horizon model of a dynamic kidney exchange market.

Arrivals and types of patients. Incompatible patient-donor pairs arrive at the market at rate n.

A patient's objective is to receive a compatible donor kidney as early as possible and, in return, her paired donor is willing to donate a kidney to some patient. We assume that a patient's compatible donor kidneys are homogeneous to her.

There are two types of patients: hard-to-match and easy-to-match. We refer to these types as H and E, respectively. A fraction λ > 0 of patients are hard-to-match and a fraction (1 -λ) are easy-to-match. An H patient is compatible with any donor with probability p H , and an E patient is compatible with any donor with probability p E . We discuss the plausibility of this assumption in Section 2.3. does not require a donor d i and her paired patient p i to be in the same matching. Thus, there are algorithms that are illegal in some countries. For instance, the usual pairwise kidney exchangewhich is the only legal form of exchange in France-substantially limits the set of possible matchings:

A pairwise compatibility happens when two incompatible patient-donor pairs v i and v j are crosscompatible; that is, there are an edge between p i and d j and another edge between p j and d i . In pairwise kidney exchange, only pairwise compatible pairs can be matched.

A matching algorithm induces a stochastic process over the number of patients of each type remaining in the system. In this study, we restrict our attention to matching algorithms inducing a stochastic process with a unique invariant distribution. We consider three myopic matching algorithms, with the first two, the Pairwise and the Chain algorithms, from the literature [START_REF] Akbarpour | Thickness and information in dynamic matching markets[END_REF]Ashlagi et al., 2019b) and the third, the Unpaired algorithm, being the core contribution of this study.

Definition 2.1 (Pairwise). If any new patient-donor pair v i enters the market at time t, then match them with any cross-compatible patient-donor pair (if any), breaking ties in favor of hard-to-match patients.

For a pair, the Pairwise algorithm forbids donation-before-receipt (a donor donates before the paired patient receives a kidney) and receipt-before-donation (a patient receives a kidney before the paired donor donates). Therefore, it creates the problem of double-coincidence-of-wants.

The next one, the Chain algorithm, is feasible only in settings where altruistic donors exist. The definition is taken from Ashlagi et al. (2019b).

Definition 2.2 (Chain). There is a bridge or altruistic donor in the market at any given time.5

Consider a newly arriving pair v 1 = (p 1 , d 1 ). If p 1 does not have an edge to the bridge donor, then no match is formed. Otherwise, a chain-segment begins with matching the bridge donor with p 1 and advances as follows. First, we search for an H patient that has an edge to d 1 ; if there are multiple such H patients, we select one uniformly at random; otherwise, we search for an E patient that has an edge to d 1 (again breaking ties uniformly at random). With the paired donor of the selected patient available to be matched, the process repeats among the pairs without a selected patient, until we select a patient whose paired donor is incompatible with all never-selected patients, forming a disjoint path. All patients and donors in the disjoint path leave the market, and the paired donor of the last selected patient becomes a bridge donor.

Essentially, upon the arrival of a new patient-donor pair, the Chain algorithm identifies a chain in a greedy fashion. This policy does not necessarily pick the longest chain (since it is searching in a greedy fashion), but it does find a maximal size chain, i.e., a chain that is not properly contained in a longer chain, and at the same time gives priority to H patients. In that respect, we follow Ashlagi et al. (2019b); we further discuss this in Remark 2.9.

For a pair, the Chain algorithm still forbids donation-before-receipt but allows receipt-beforedonation if the patient is compatible with some donor in the chain. We are now ready to introduce the Unpaired algorithm that allow all possible donation-before-receipt and receipt-before-donation.

Definition 2.3 (Unpaired). If any new patient-donor pair v i = (p i , d i ) enters the market at time t, match p i to a compatible donor (if any), breaking ties arbitrarily, and match d i to a compatible patient (if any), breaking ties in favor of hard-to-match patients.

The Unpaired algorithm allows both donation-before-receipt and receipt-before-donation by memorizing all transactions in the market. Whenever a pair engages in donation-before-receipt, the algorithm will remember to match the pair's patient, defined as an unpaired patient, with a compatible kidney in the future. Similarly, if a pair does receipt-before-donation, the algorithm will remember to ask the pair's donor, defined as an unpaired donor, to donate a kidney in the future.

In other words, for a pair, the algorithm searches for a match for the patient while independently finding a match for the donor, as if they were unpaired. Hence, we call it the Unpaired algorithm.

By relaxing the timing constraints on kidney donation and receipt for a pair, the Unpaired algorithm may create two incentive issues. First, donation-before-receipt creates unpaired patients who need to wait to receive a compatible kidney after their donors' donation; if the wait is expected to be long, they may opt out of donation-before-receipt or quit the algorithm all together. Second, receipt-before-donation results in unpaired donors who will wait to donate after their paired patients' transplantation; they may renege or become unfit to donate if the wait is long. In Sections 3.3.1 and 3.5.1, we present an extensive empirical investigation of the consequences of these issues as well as several solutions addressing these issues. In short, as shown in the empirical analysis, these issues diminish with market size; even when some pairs opt out of donation-before-receipt or when some unpaired donors renege, the performance advantage of the Unpaired algorithm remains; if a policymaker is still concerned, our proposed solutions can effectively address these issues.

Below, we sometimes refer to these three algorithms as Pairwise, Chain, and Unpaired.

Objective. Patients and donors stay in the market until they are matched. For a patient p i who enters the market at time t 0 and gets matched at time t 1 , let w(p i ) = t 1 -t 0 be p i 's waiting time .

The planner's objective is to minimize the average waiting time at the invariant distribution (recall that we focus on matching algorithms inducing stochastic processes that have a unique invariant distribution). By Little's law, this is equivalent to minimizing the average number of patients in the system. 6,7 Let W(ALG) denote the average waiting time for a given matching algorithm ALG in steady state. This is equal to λW H (ALG) + (1 -λ)W E (ALG), where W H (ALG) and W E (ALG)

denote the expected waiting time of hard-to-match and easy-to-match patients, respectively.

Optimal solution. In the following, we sometimes compare the performance of a matching algorithm to an optimal algorithm that is a theoretical benchmark but practically infeasible. We define the Optimal algorithm as the one achieving the smallest average waiting time that can be achieved by a matching algorithm. Unlike the other algorithms we study, the optimal algorithm need not be greedy, i.e., it may delay matching a patient/donor if they may help pairs arriving in the future.

Formally, we define the average waiting time achieved by the Optimal algorithm, W(Optimal), as

inf W(ALG)
where the infimum is taken over all matching algorithms. Therefore, the optimal algorithm also induces an invariant distribution.

The optimal algorithm is practically infeasible for two reasons: First, it requires access to infinite computational power to solve a complex dynamic programming problem. Second, the algorithm needs knowledge of all future arrivals, which is impossible in practice as arrival rates evolve over time often in an unanticipated way.

Theoretical Results

This section compares the average waiting time of patients under the Unpaired algorithm with those under the Pairwise, Chain and optimal algorithms. We start with the following proposition.

Proposition 2.4. Under the Unpaired algorithm, the average waiting time of hard-to-match patient, W H (U npaired), and that of easy-to-match patients, W E (U npaired), satisfy

lim p H →0 p H W H (U npaired) = ln (1 + λ) λ • n and lim p H →0 p H W E (U npaired) = 0.
Hence,

lim p H →0 p H W(U npaired) = ln (1 + λ) n .
We prove this theorem in Appendix A. Here, we provide a sketch of the main idea behind the proof.

Proof overview. The key step behind the proof of this theorem is to carefully study the structure of the stochastic system induced by the Unpaired algorithm. First, note that the number of donors in the system is always equal to the number of patients. Thus, the state of the system can be tracked by the number of easy-to-match and hard-to-match patients that are currently in the system. For simplicity, let us first sketch the proof of the theorem for the case that p E = 1, which means that whenever an easy-to-match patient arrives, she will get matched immediately.8 In this case, the number of hard-to-match patients is a sufficient statistic for the state of the system.

Suppose the total number of hard-to-match patients in the system is k. When a patient-donor pair arrives, three events can change the state of the system:

1. The patient is hard-to-match, and neither the patient nor the donor are compatible to anyone in the pool. In this case, the system moves from state k to state k + 1. This happens at rate

λ((1 -p H ) k ) 2 .
2. The patient is hard-to-match, and both the donor and the patient are compatible to someone in the pool, in which case the system moves to state k -1. This happens at rate λ

(1-(1-p H ) k ) 2 .
3. The patient is easy-to-match, and both the donor and the patient are compatible to someone in the pool. Again, the system moves to state k -1. Since p E = 1, this happens at rate

(1 -λ)(1 -(1 -p H ) k ).
Thus, we are dealing with a standard birth-death Markov chain, where the birth event has rate λ((1 -p H ) k ) 2 and the death event has rate λ(1

-(1 -p H ) k ) 2 + (1 -λ)(1 -(1 -p H ) k ).
In the full proof, we show that E(k) is highly concentrated around the state where the birth and death forces balance; i.e., E(k) k * , where k * is the solution to:

λ((1 -p H ) k ) 2 = λ(1 -(1 -p H ) k ) 2 + (1 -λ)(1 -(1 -p H ) k )
Algebraic manipulations for the case where p H → 0 lead to k * ln(1+λ) p H . By the Little's law, the expected waiting time in a queue is equal to the pool size divided by the arrival rate:

E(W H ) = E(k)/λ k * λ ln(1 + λ) λp H
When p E < 1, we should keep track of both the number of hard-to-match and easy-to-match patients, which makes the analysis more tedious. Since easy-to-match agents only exert a negative externality on hard-to-match patients under Unpaired (by taking kidneys that would otherwise be assigned to hard-to-match patients), when p E gets smaller, this can only help hard-to-match patients.

Hence, intuitively, when p E < 1, the expected number of hard-to-match patients remaining in the system should be upper bounded by what we obtain when p E = 1. We show that this bound is actually tight. There is a simple intuition for why any constant p E , the behavior of the system is similar to p E = 1: as p H → 0, the number of patients (and thus donors) in the system explodes. If there are k donors in the system, a new arriving easy-to-match patient is compatible to some donor in the system with probability at least 1 -(1 -p E ) k , which goes to 1 for sufficiently large k. Thus, easy-to-match patients will get matched quickly as long as p E is a constant.9

Proposition 2.4 reveals several interesting comparative statics. First, increasing the total arrivals always decreases waiting time, because it thickens the market. Second, the average waiting time of hard-to-match patients is decreasing in λ. A larger λ means a higher arrival rate for hard-to-match patients and a lower one for easy-to-match patients. In other words, easy-to-match patients exert a negative externality on hard-to-match ones. Indeed, upon arrival, an easy-to-match patient is almost sure to be compatible with an existing donor. The departure of a donor makes the market smaller, reducing the opportunities for future hard-to-match patients and thus increasing their waiting time.

As we shall see below, this is in contrast to Pairwise and Chain under which easy-to-match patients can potentially help hard-to-match patients by increasing their likelihood of being cross-compatible or increase the likelihood of initiating a chain-segment (see Figure 1).

We note that matching patients with donors quickly, as does the Unpaired algorithm, may not be always beneficial due to the well-known tradeoff between thickening the market and matching

quickly. Indeed, one may construct realizations of the stochastic process under which the overall average waiting time is longer under Unpaired than under alternative algorithms. In particular, one may argue that the Pairwise algorithm can achieve a better outcome by matching patients with donors slowly and thus thickening the market. The following theorem answers this question.

Theorem 2.5 (Unpaired vs. Pairwise). If λ ≥ 1 2 , then:

lim p H →0 W(P airwise) W(U npaired) = lim p H →0 1 p H ln(2λ) ln(1 + λ) = ∞,
and if λ < 1 2 , then:

lim p H →0 W(P airwise) W(U npaired) = 1 p E ln 1-λ 1-2λ ln (1 + λ) > 1.
Proof. See Appendix B.1.

This theorem states that, when p H gets small, the average waiting time under the Unpaired algorithm is less than that under the Pairwise algorithm, irrespective of the value of λ. Moreover, when there are more hard-to-match patients (λ ≥ 1 2 ), the gap between the two algorithms goes to infinity at rate 1 p H . When there are strictly more easy-to-match patients (λ < 1 2 ), the gap is not always as large, but still Unpaired achieves a shorter average waiting time than Pairwise.

To gain some intuition of the result, let us recall that, under the Pairwise algorithm, for an arriving pair with a hard-to-match patient, the probability of being cross-compatible with a pair with an easy-to-match patient in the pool is proportional to p H (recall that p E is a constant), while its probability of being cross-compatible with an existing pair with a hard-to-match patient is p 2 H . When λ ≤ 1 2 , or easy-to-match patients arrive more frequently than hard-to-match ones, almost all hard-to-match agents are matched with easy-to-match agents under Pairwise algorithm. Hence, the scaling of the average waiting time under Pairwise is 1/p H . As shown in Proposition 2.4, the average waiting time under Unpaired is proportional to 1/p H , as well. When λ ≥ 1 2 , there are not enough pairs with an easy-to-match patient. Therefore, most of the pairs with a hard-to-match patient match with pairs with a hard-to-match patient and thus, as shown in Ashlagi et al. (2019b), the scaling of the average waiting time under Pairwise is 1/p 2 H . As shown in Proposition 2.4, the average waiting time under Unpaired is proportional to 1/p H , an order of magnitude smaller. Furthermore, the next theorem shows that the Unpaired algorithm's performance is not too far from the Optimal algorithm.

Theorem 2.6 (Unpaired vs. Optimal). For any λ, we have:

lim p H →0 sup W(U npaired) W(Optimal) ≤ 2 ln (1 + λ) λ ≤ 2. Proof. See Appendix B.2.
This theorem shows that the waiting time of patients under the Unpaired algorithm is reasonably close to that under the Optimal algorithm. 10 This is not true for Pairwise given as implied by Theorem 2.5, especially when λ ≥ 1 2 . Note that Unpaired is purely greedy and computationally simple, while the Optimal algorithm is forward looking and potentially computationally complex.

Yet, the Optimal algorithm does not substantially improve upon Unpaired.

Remark 2.7. One may be curious about how much we can decrease the waiting time of hard-to-match patients without increasing the waiting time of easy-to-match patients. The bound in Theorem 2.6 can be improved under this additional constraint on the waiting time of easy-to-match patients.

Appendix B.2 shows that for any matching algorithm ALG satisfying

W E (ALG) ≤ W E (Unpaired), lim p H →0 sup W(U npaired) W(ALG) ≤ (1 + λ) ln (1 + λ) λ ≤ 2 ln(2) 1.38.
So far, we have shown that the Unpaired algorithm performs substantially better than Pairwise, while being close to the Optimal algorithm. In practice, the Chain algorithm also plays an important role. Our next result compares Unpaired with Chain.

Theorem 2.8 (Unpaired vs. Chain). For any λ, if p E = 1, we have: 1+λ) is greater than one, when p H gets small, the average waiting time under Unpaired is smaller than under the Chain algorithm irrespective of the value of λ. Note also thatln(1-λ) ln( 1+λ) is an increasing function of λ and goes to infinity as λ → 1. In other words, the Unpaired algorithm performs increasingly better than the Chain algorithm as the fraction of hard-to-match patients increases; as this fraction approaches one, Chain delivers an average waiting time that is infinitely longer than what Unpaired achieves.

lim p H →0 W(Chain) W(U npaired) = - ln(1 -λ) ln(1 + λ) ≥ 1. Proof. See Appendix B.3. Since -ln(1-λ) ln(
Below is an intuition of this theorem. The Chain algorithm performs better when the probability of starting a new chain-segment is higher, which makes easy-to-match patients critical. When a pair with an easy-to-match patient arrives, the patient will be matched with the bridge donor and advance the chain-segment with probability p E . This probability reduces to p H , which is vanishing, if the arriving patient is hard-to-match. Note that the donor in the newly arriving pair cannot be considered for matching unless the paired patient finds a match. Therefore, when only a small minority of arrivals have an easy-to-match patient, the probability of starting a new chain-segment is small and Chain performs poorly.11 In contrast, the Unpaired algorithm does not crucially depend on the type of the arriving patient, because it allows donation-before-receipt (i.e., upon arrival, every donor is considered for matching with an existing patient, regardless of the paired patient's status).

Theorem 2.8 comes with an additional technical assumption: to provide a closed-form solution for the Chain algorithm, we assume p E = 1. Without this assumption, the Markov chain induced by the Chain algorithm seems too complicated to be analyzed. For the same reason, Ashlagi et al. (2019b) do not provide a formal proof for the performance of Chain when p E < 1. Our numerical simulations, as well as those in Ashlagi et al. (2019b), indicate that the closed-form solution for p E = 1 approximates well the simulated average waiting time for p E < 1. Based on these results, we conjecture that Theorem 2.8 holds even when p E < 1.

Remark 2.9. The Chain algorithm identifies a chain in a greedy fashion. It does not necessarily pick the longest chain. The Optimal Chain algorithm (selecting the longest chain) has been studied in a one-type model by [START_REF] Anderson | Efficient dynamic barter exchange[END_REF]. In that model (where λ = 1 and n is normalized to 1), it is easy to show that the waiting time of patients under Optimal Chain is always longer than that of Unpaired. Indeed, under Optimal Chain, an arriving patient has probability p H to be matched with the bridge donor right away. With the complement probability, this patient will be unmatched and enter the pool. In that event, she will have to wait for an arriving patient to be compatible with the bridge donor (which is necessary to initiate a chain-segment), which occurs with rate p H . Thus, in expectation, this patient will have a waiting time bounded below by 1/p H . This is larger than ln(2)/p H , the waiting time of patients under the Unpaired algorithm (see Proposition 2.4). We summarize our theoretical results in Figure 1 with p E = 1 and n = 1. For a given algorithm, taking p H to zero, a line in the figure depicts the limiting average waiting time for hard-to-match patients (panel A) and that for all patients (panel B), as a function of the fraction of hard-to-match patients (λ ∈ [0, 1]). In terms of these waiting times, the difference between Unpaired and Optimal is bounded and small for all λ (Theorem 2.6); the difference between Unpaired and Pairwise increases with λ and explodes when λ ≥ 1 2 (Theorem 2.5); last, the difference between Unpaired and Chain increases with λ and goes to infinite when λ = 1 (Theorem 2.8). We will evaluate the empirical relevance of these results in Section 3.

Discussion of the Assumptions

We now discuss some of the assumptions and modeling choices that we have adopted.

First, our model assumes two patient types each of which has a different probability of being compatible with a random donor. Below, we show some evidence that this can be a reasonable approximation in some settings. A real-life kidney exchange problem certainly has more than two types of patients, because a patient's biological compatibility with a donor depends on blood type and tissue type compatibilities. There are finitely many blood types with a known compatibility relation, but tissue compatibilities involve a more subtle comparison of the antibodies of a patient with the antigens in a donor's tissue. This information is usually summarized by a continuous measure, Panel Reactive Antibodies (PRA), quantifying the probability that a patient is tissue type incompatible with a random blood type compatible donor. The higher a patient's PRA, the more difficult it is to find a compatible donor for the patient. The distribution of PRA among patients is bimodal with high concentrations of patients at very low and very high PRA values in the U.S. [START_REF] Anderson | Efficient dynamic barter exchange[END_REF]. See Table 1 for more summary statistics on these patients.

Second, there is no death in our model, which can be overly simplifying for patients waiting for kidney transplant. 12 However, patients participating in a KEP are usually in better health conditions. In the sample period of more than four years, none of the patients who participated in the French KEP died while waiting for a kidney. Some of them did leave the KEP for a deceased donor kidney or an incompatible living donor kidney after going through desensitization (see Section 3.1).

Introducing pair exit decision would add a layer of complexity in our model, but we conjecture that our main results would hold. Intuitively, the longer the waiting time under an algorithm, the higher the probability that a patient exits. Compared with Pairwise and Chain, the Unpaired algorithm has a shorter average waiting time, and thus a model with exit may reinforce the advantage of the Unpaired algorithm. Moreover, our simulations in Section 3.5 show that our results are robust even when we allow pairs to exit.

Last, our main theoretical results are limiting results for p H → 0, with p H being the probability of a hard-to-match patient being compatible with a random donor. Working with limit results gives us more analytical tractability, but it also implies that our results provide a good approximation only when p H is sufficiently low. In our data, a patient with a PRA above 85 percent, who is considered hard-to-match by convention, is compatible with only 1.5 percent of the living donors, which is low. In contrast, a patient with a PRA below 85 percent is compatible with 24.5 percent of the living donors. Admittedly, our theoretical results do not give any insight about how small p H should be for the results to be a good approximation. 13 Ultimately, this is an empirical question and our empirical analysis in Section 3.5.2 confirms the relevance of our results in real life.

Counterfactual Analyses Using French Data

Our theoretical model investigates the steady-state performance of the algorithms in a stylized model. There are potential concerns about the empirical relevance of our theoretical results. First, it may take a long time for a given market to reach a steady state, provided that pair arrival rates do not change over time. Meanwhile, policymakers may also be interested in an algorithm's shortrun effects. Second, the two types assumption in our model is not exactly satisfied in the real world. For instance, while Figure E.1 suggests a bimodal pattern in the distribution of biological types of patients, this remains a rather crude approximation. Furthermore, a patient's biological compatibility with a donor depends on both blood type and tissue type compatibilities; in practice, for a given patient, the compatibility realizations are unlikely to be i.i.d. across donors.

With these considerations, we assess the algorithms with an administrative dataset on kidney transplants in France from December 13, 2013 to February 23, 2018. Specifically, we answer the following counterfactual question: What would have happened in this period had a given algorithm been implemented?

We proceed as follows. Section 3.1 describes the institutional background and our data. In Section 3.2, we detail some definitions and assumptions that are necessary in our simulations. Sec-tion 3.3 presents the performance of the four algorithms (Pairwise, Chain, Optimal, and Unpaired) in our baseline simulation. We highlight that the empirical results are consistent with the theoretical predictions. Moreover, after measuring the waiting times of patients/donors after being unpaired, we acknowledge that the potential incentive issues of Unpaired can be a concern in practice. As a solution, Section 3.3.1 introduces a modified version of the algorithm by integrating it with deceased donor kidneys. Our results show that it improves the performance of Unpaired while essentially removing the incentive issues. Section 3.4 repeats the analysis in larger markets comparable to those in the U.K. or the U.S. The performance advantages of Unpaired remain; more importantly, in these large markets, the potential incentive issues of Unpaired are significantly mitigated without the need to use any deceased donor kidneys. In Section 3.5, we conduct a wide range of robustness checks by relaxing some of the assumptions.

Institutional Background and Data

Our analysis relies on administrative data from France provided by the Agency of Biomedicine (Agence de la Biomédecine, ABM), a government agency that oversees all organ transplants in France. Our data covers the period of December 13, 2013 to February 23, 2018, including all transplants with deceased or living donor kidneys, as well as discarded kidneys from deceased donors.

We focus on three types of kidney transplants: kidney exchange, living donor with desensitization, and deceased donor kidneys. In France, when a patient is diagnosed as requiring a kidney transplant, her doctor must register her at the national deceased donor list (DDL) to join the waitlist. If a patient finds an incompatible living donor, she may either join the kidney exchange or go through a desensitization procedure whereby she can receive an incompatible kidney from her donor. Below, we provide institutional details and describe the data by transplant type.

Kidney Exchange Program. France's kidney exchange program (KEP) started in 2013, following the revision of the bioethics law (loi de bioéthique) that regulates the medical practices in France.

Unlike the U.S., France has a single KEP at the national level, administered by the ABM. By law, any exchange of living donors must be done through the KEP.

The KEP executes a match run every three months, leading to 15 in our sample period.14 Only 2way pairwise exchanges are allowed, while non-directed kidney donations and chains are prohibited.

The KEP's objective is to maximize the total number of transplants in each match run.

In total, there are 78 pairs participating in at least one of the 15 match runs. On average, a pair stays for 3.4 match runs, and a match run has 17.5 participating pairs. 12 pairs successfully engaged in an exchange in our sample period. A detailed summary can be found in [START_REF] Combe | Outlook on the Kidney Paired Donation Program in France[END_REF].

Columns (1) and (2) of Table 1 present more statistics on the 78 KEP pairs. Some patients receive a kidney from the DDL or a living donor kidney outside the KEP, leading to 69 percent of them receiving a transplant. 35 percent of the donors donate, with some of them donating outside Among all the pairs, 42 percent are blood type compatible, and 32 percent are human leukocyte antigen (HLA) compatible.

Desensitization Pairs. Desensitization is an immunosuppressive treatment that can eliminate immunological compatibility constraints. Once treated, a patient is able to receive a transplant from an incompatible donor. For a brief review of desensitization, please see [START_REF] Andersson | Pairwise kidney exchange over the blood group barrier[END_REF] and [START_REF] Heo | Kidney exchange with Immunosuppressants[END_REF] as well as the references therein.

In general, incompatible transplants facilitated by desensitization are more expensive than compatible ones,15 while leading to poorer patient outcomes. 16 Nonetheless, desensitization is a popular choice for incompatible pairs in France. During our sample period, there are 508 incompatible pairs that take this option without trying the KEP. These transplants, as well as the associated patients and donors, are recorded by the ABM. In some of our simulations (Section 3.5), we include these pairs in the exchange, because they could be incentivized to participate.

Columns (3) and ( 4) of Table 1 present summary statistics on desensitization pairs. Compared with the donors, the patients are less likely to be a female (37 percent vs. 62 percent), are of similar ages (45.9 vs. 45.8 years old), and are more likely to be have type O blood (59 percent vs. 29 percent).

24 percent of these patients are hypersensitized. Relative to the KEP pairs, the desensitization pairs are more likely to be blood type compatible (44 percent vs. 42 percent) or HLA compatible (48 percent vs. 32 percent).

Deceased Donor Kidneys. Our sample has 13, 036 deceased donor kidneys, which we call DDL kidneys, offered to patients on the DDL.17 Column (5) of Table 1 describes these DDL kidneys.

On average, they are 54.9 years old, and 43 percent are from a female donor. The top two blood types are A (44 percent) and O (43 percent). In some of our simulations (Sections 3.3.1 and 3.5),

we assume that some of the "high-quality" DDL kidneys can be used in the exchange, with "high quality" to be defined.

Definitions and Assumptions in the Simulations

The following definitions, assumptions, and data preparations are needed in our simulations.

"Waiting rooms" for unpaired patients (P) and donors (D). The Unpaired algorithm may have two incentive issues involving unpaired patients and donors due to donation-before-receipt and receipt-before-donation. Namely, a patient may not be willing to let her donor donate before she receives a kidney; a donor may renege if her patient has already received a transplant from someone else. Some definitions will be useful in our analysis: we let P be the "waiting room" for unpaired patients who are waiting for a kidney after their paired donors have donated; D is the "waiting room"

for unpaired donors who wait to donate after their paired patients have received a transplant.

Compatibility between a patient and a donor. Patient p i and donor d j are compatible unless they are either blood type incompatible or HLA incompatible. We have sufficient information to determine the compatibility between any patient and any donor in the data. Specifically, we compare p i and d j 's blood types to determine their blood type compatibility; if d j has at least one antigen that is unacceptable to p i , p i is HLA incompatible with d j .

Hard-to-match. A patient is defined to be hard-to-match if she is hypersensitized, i.e., tissue-type incompatible with more than 85 percent of the 13,622 donors, living or deceased, in our data. There are 21 such patients from the KEP pairs and another 120 from the desensitization pairs (Table 1).

As mentioned in Section 2.3, even when we abstract from blood type incompatibility, the probability of those patients finding a compatible kidney is low. Additionally, we separately report statistics on O patients who are also likely to be hard to match.

Tie-breaking in the algorithms. When selecting among multiple compatible donors/patients, an algorithm needs a tie-breaking rule. In their definitions (Definitions 2.1, 2.2, and 2.3), we sometimes allow for an arbitrary rule, as the theoretical results do not depend on that. Our simulation, however, complements the definitions with the following rule: when selecting among multiple donors, Arrival dates. For each KEP pair, we observe in which KEP match runs the pair participated as well as the date of the match run. If a KEP pair arrives between the k-th and (k + 1)-th match runs, we draw an arrival day uniformly between these two dates. For each pair in the first match run, we independently draw a date uniformly among the 110 days before the first match run, as any two consecutive match runs in our sample are on average 110 days apart.

Some simulations also include the desensitization pairs. We observe the date of each desensitization transplant. For each pair, similar to our assumption on the KEP pairs in the first match run, we uniformly draw a date from the 110 days before its transplant date as its arrival date.

Exit dates. Most departures of pairs from the KEP are due to desensitization or the paired patient accepting a DDL kidney. As discussed in Section 2.3, there is no death of a KEP patient, because patients who are allowed to participate in the KEP are in relatively good health.

In our baseline simulations (Section 3.3), we assume there is no exit. Equivalently, everyone who has not received a transplant or has not donated stays until the end of our simulation. Some of our simulations allow a KEP pair to exit without receiving a transplant. Exit dates are simulated as follows: for pairs that accepted a KEP kidney or participated in the last match run in the data, they are assumed to stay until the end of the time horizon for our simulation (defined below); for all other pairs, we draw an exit date uniformly between the k-th and (k + 1)-th match run, with the k-th being the last match run in which they participated. we then report the averages over the 1000 sets for a given policy.

Evaluating the Algorithms: Baseline Simulations

We start with the baseline in which there is neither pair exiting nor donor reneging. We apply an algorithm to each of the 1000 sets of randomly drawn arrival and exit dates. For a given set of dates, pairs are ordered by arrival date: i = 1, . . . , n. Let a(i) and e(i) be the dates of arrival and exit of pair i, respectively. Let T be the end of our simulation time horizon; obviously, T ≥ a(n). There is no exit, or equivalently e(i) = T for all i. That is, before the last day (T ), once a pair arrives, the patient leaves only if she receives a kidney, and the donor leaves only if she donates a kidney. This no-exit assumption is motivated by the discussion in Section 2.3 and is relaxed in Section 3.5.

We simulate Pairwise and Unpaired by following their definitions and applying the aforementioned tie-breaking rule (Section 3.2). To initiate Chain in the simulation, we select a DDL kidney as an altruistic donor available during the whole simulation time horizon. 18 In other words, every day there is one bridge donor. We relax this assumption to allow for multiple bridge donors in Section 3.5. Note that, following common practices, pairwise exchanges are still allowed in Chain in the simulation, contrary to our theoretical analysis.

A best-case, infeasible algorithm: Omniscient. In Section 2, we use the Optimal algorithm to provide the best-case scenario for average waiting time. Unfortunately, it is impossible to simulate Optimal without imposing assumptions, for example, on arrival rates beyond our simulation time horizon. We instead consider another algorithm, Omniscient, which provides the lowest possible average waiting time given the time horizon.

Specifically, the Omniscient algorithm assumes that the exchange has full information about all the patients and donors arriving in our simulation, including their arrival/exit dates and their characteristics. The exchange then minimizes the average waiting time of all patients up to date T (i.e., the end of our simulation), regardless of transplant status. Therefore, in terms of this average waiting time, it dominates all algorithms, including Unpaired. While Omniscient is practically infeasible, it helps us evaluate the potential of Unpaired.

Simulating Omniscient is feasible because it does not need assumptions on pair arrivals beyond our simulation time horizon. We formulate the Omniscient algorithm as an Integer Linear Programming problem as detailed in Appendix C, which is computationally easy. To ensure that a DDL kidney is "high quality" for a given patient, we require that the DDL kidney be compatible with the patient and have a Kidney Donor Profile Index (KDPI, lower is better), a risk index of post-transplant graft failure, below the Living Kidney Donor Profile Index (LKDPI) of the patient's paired incompatible donor. The LKDPI is an index for living donor kidneys corresponding to the KDPI, and they are of the same scale. See Appendix D for more details on KDPI and LKDPI. Among the DDL kidneys meeting this selection criterion for at least one KEP patient, we randomly pick one, regardless of its arrival date. We assume that this DDL kidney arrives on the first simulated arrival day, a(1), and remains until being transplanted or until the end of the simulation. We redraw a new DDL kidney for each set of simulated dates.

Results. Our simulation results in

outperform Unpaired (cf. Theorem 2.6). The statistics are from the 1000 sets of simulations, each of which contains a draw of arrival dates of the 78 pairs. The waiting time for a patient or a donor may be censored from above if she has not received or donated a kidney by the last date of the simulation. The same censoring applies to the number of days in P or D. P and D are waiting rooms for unpaired patients and donors, respectively. Pairwise (2-way exchange) (column 1) is defined in Definition 2.1, column (2) allows 3-way exchanges in addition to 2-way, Chain is defined in Definition 2.2 and is combined with Pairwise (column 3). In column (4), Unpaired, as defined in Definition 2.3, only uses living donors in the 78 pairs. Under Unpaired with DDL (column 5), defined in Definition 3.1, qualified DDL kidneys are used in the algorithm and, whenever a DDL kidney is used, a living donor in D gives a kidney to the DDL. A qualified DDL kidney for a given patient must have a KDPI below the LKDPI of her own paired donor. Omniscient (columns 6 and 7) uses full information on all pairs in the sample period to match patients and donors to minimize the total censored waiting time; column (6) does not use DDL kidneys, while column (7) use the same DDL kidneys used by Unpaired with DDL (column 5) in each simulation.

We first report the average censored waiting time for all patients, noting that some patients may still wait for a kidney at the end of our simulation. Omniscient (column 6), which minimizes this number, reaches 425 days, while Unpaired (column 4) achieves a similar level, 440 days. Pairwise and Chain (columns 1 and 3) perform significantly worse, delivering a waiting time at least 59 percent longer than Unpaired. This pattern also holds among hard-to-match patients (defined as either hypersensitized or O patients).

The close-to-minimum waiting of Unpaired is also observed in terms of the average waiting time for patients who have received a transplant. However, among transplanted hard-to-match patients, their average waiting time under Pairwise or Chain is lower than under Unpaired, which is due to the lower transplant rates under Pairwise and Chain.

In terms of transplant rate, Unpaired is still close to Omniscient (57 percent vs. 58 percent) and far above the other two algorithms (29 percent under Pairwise and 31 percent under Chain). The same conclusion is true among hard-to-match patients. 19 In practice, a KEP may allow both 2-way and 3-way pairwise exchanges. Including this possibility, column (2) shows that this more flexible algorithm performs better than Pairwise but remains significantly worse than Unpaired. 20

Potential Incentive Issues and a Solution

Table 2 confirms the two potential incentive issues under Unpaired. First, when we allow donationbefore-receipt, some patients enter in P after their donors have donated. Column (4) shows that patients going through P can wait a long time (median: 220 days), and hypersensitized patients wait even longer (median: 506 days). When anticipating a long waiting time in P, pairs may refuse donation-before-receipt, or even be discouraged from participating in the Unpaired algorithm.

The second potential issue is that receipt-before-donation make some donors enter D and possibly wait for a long time. Overall, their median waiting time is 305 days (column 4). Such a long wait in D can bring a non-negligible chance of losing an unpaired donor, because she may refuse or become unfit to donate, while no donor can be legally obliged to donate in any country, as far as we know.

To address these two potential issues, one may consider the following version of Unpaired, called

Unpaired with DDL, that integrates an exchange with DDL kidneys.

Definition 3.1 (Unpaired with DDL). In addition to the Unpaired procedure as in Definition 2.3, whenever a qualified DDL kidney arrives, match the kidney to a compatible unpaired patient in P (if any), while prioritizing patients by waiting time. Whenever a DDL kidney is taken by a patient, the unpaired donor in D who has the longest waiting time gives a kidney to some patient in the DDL.

Under Unpaired with DDL, only a patient in P can receive a DDL kidney, meaning her donor must have already donated. Moreover, P and D must have the same size at any point of time.

Therefore, if a patient in P takes a DDL kidney, there must be some donor in D who can donate to the DDL. By design, the algorithm balances the interaction between the DDL and the exchange.

Remark 3.2. A full-fledged theoretical analysis of Unpaired with DDL can be complicated since the dimension of the Markov chain induced by this algorithm is higher-we would have to keep track of 19 The transplant rate of either hypersensitized or O patients under any algorithm is significantly lower than that of other patients. This is consistent with our assumption that they are harder to match than others. 20 The Unpaired algorithm eliminates the timing constraints on the donation and receipt but, compared to the 2-way and 3-way pairwise exchanges, it also allows exchange cycles of arbitrary sizes. One may naturally wonder whether the performances of Unpaired relies on the relaxation of the constraints on the cycle sizes. To answer this question, we simulated pairwise exchanges allowing cycles of arbitrary size. Its performance is still significantly worse than Unpaired: the transplant rate is 38 percent (vs. 57 percent under Unpaired) and the (censored) average waiting time is 655 days (vs. 440 days under Unpaired).

the number of patients in P, whose donors have already donated, and the number of patients out of P, whose donors have not donated.

However, with a simplifying assumption, we have a conjecture. We assume that upon a donationbefore-receipt, the unpaired patient immediately finds a compatible DDL kidney, and at the same time, an unpaired donor in D donates to a patient on the DDL. Therefore, both P and D are always empty, reducing the dimension of the Markov chain. We conjecture that, in this case, the waiting time of (hard-to-match) patients under Unpaired with DDL is at most 50 percent of that under Unpaired.

This assumption is plausible due to the frequent arrival of DDL kidneys and the numerous patients on the DDL. As shown in column (5) of Table 2, the median waiting time is only 2 days among those in P and 8 days among those in D. Indeed, the comparison of waiting time is also consistent with our conjecture: the average waiting time of patients under Unpaired with DDL is less than 33 percent of that under Unpaired (143 vs. 440 days).

Remark 3.3. Unpaired with DDL integrates a KEP with a DDL and operates them under the Unpaired algorithm. This new algorithm has potential to be adopted by policymakers despite being unprecedented. Indeed, the recent proposed reform of the bioethics law in France allows for many features of the algorithm. For example, it allows donation-before-receipt (i.e., a donor donates before her paired patient receives a transplant); in return, the patient has a high priority to obtain a DDL kidney.21 Moreover, List Exchange, discussed in Section 4, also allows some interactions between incompatible pairs and the DDL.

Using the inflow of DDL kidneys in our sample period as described in Table 1, we simulate the outcomes of Unpaired with DDL and report the results in column (5) of Table 2. The algorithm only takes qualified DDL kidneys to ensure that they are high quality. As described in footnote 18, we use a standard risk index of post-transplant graft failure, namely KDPI, to screen DDL kidneys (see Appendix D for more details). Specifically, a DDL kidney is qualified for a patient in P if it has a KDPI below her incompatible donor's LKDPI (an index similar to KDPI but for living donors); we assume that a patient in P always accepts such a kidney. Each qualified DDL kidney is available in the algorithm only on the day of its arrival.

Results. Unpaired with DDL (column 5 of Table 2) successfully addresses the two potential incentive issues by substantially reducing the waiting times in P and D. Patients in P have a median waiting time of 2 days, while donors in D have a median waiting of 8 days. With such short waiting times, both donation-before-receipt and receipt-before-donation can be implemented without discouraging patients or losing donors.

Unpaired with DDL also has other advantages. It dominates Unpaired on every dimension reported in Table 2. The average waiting time among all patients or among hard-to-match patients (hypersensitized or O patients) is more than halved. The transplant rate is increased from 57 percent to 87 percent. The DDL kidneys help significantly, as 29 transplants use a DDL kidney. This implies that 29 living donor kidneys are donated to the DDL.

Unpaired with DDL also dominates Omniscient (column 6) on every dimension. In column (7), we show the performance of another version of Omniscient that, in each simulation, can use the same DDL kidneys used by Unpaired with DDL in that simulation. The results confirm that Unpaired with DDL performs almost as well as Omniscient in terms of waiting time and transplant rate.

Large-Market Results

One may conjecture that algorithms such as Pairwise and Chain perform better in larger markets, while the French KEP by no means is a large market. Moreover, this set of pairs might be a selected pool of patients, and one may be interested in the performance of the algorithms for a different pool of pairs such as those on large U.S. platforms. To this end, we investigate the performance of the algorithms in larger markets.

We consider two sets of simulations: i) we assume that the desensitization pairs in France participate in the exchange and ii) we simulate two large U.S. platforms: the Alliance for Paired Kidney Donation (APKD) and the National Kidney Registry (NKR). Our main findings are as follows:

Unpaired still significantly outperforms Pairwise and Chain while remaining close to Omniscient; moreover, the potential incentive issues diminish with market size, and DDL kidneys are not needed for tackling these issues in a large market such as NKR.

Desensitization Pairs Participating in the Exchange

In our data, desensitization pairs choose to undergo the desensitization procedure to facilitate an incompatible kidney transplant, despite patient outcomes being worse than a compatible living donation. As the Unpaired algorithm makes the exchange more efficient, it is plausible that these pairs would be incentivized to participate. Specifically, in addition to the 78 KEP pairs, we assume that the exchange now includes the 508 desensitization pairs (Table 1). This implies an arrival rate of 11.3 pairs per month, similar to the U.K. KEP, the largest in Europe with 11.8 pairs per month during April 2007 to April 2014 (see, for example, [START_REF] Ferrari | Kidney paired donation: principles, protocols and programs[END_REF][START_REF] Biró | Building Kidney Exchange Programmes in Europe-An Overview of Exchange Practice and Activities[END_REF]. Recall that we simulate the algorithms with 1000 sets of simulated arrival dates of the KEP pairs. Arrival dates of desensitization pairs are drawn as described in Section 3.2.

We now have a market that has 586 incompatible pairs, among which 141 have a hypersensitized patient and 342 have an O patient. Below, we no longer report the statistics on hypersensitized or O patients in a table, although they can be found in Appendix E.

Results. Table 3 shows the same pattern across Pairwise (column 1), Chain (column 3), and Unpaired (column 4) as in the baseline. The performance of Pairwise and Chain improves with market size, so does that of Unpaired. Unpaired continues to dominate the other two algorithms in this market. The increased market size significantly reduces the waiting time in P and D, mitigating the potential incentive issues. Compared with the baseline simulation (column 5, Table 2), the median waiting time of patients in P is reduced by 20 percent, and 36 percent for donors in D. Furthermore, Unpaired with DDL (column 5, Table 3) remains effective in shortening waiting times in P and D.

The differences between Unpaired and Omniscient (columns 4-7) are worth noting. Between Unpaired and Omniscient, without DDL kidneys, the differences in waiting time and transplant rate are negligible. However, Omniscient with DDL significantly improves upon Unpaired with DDL in terms of waiting time, although less so in terms of transplant rate. The reason is that the market size and the large number of DDL kidneys (172, on average) give Omniscient more room to optimize.

Simulating U.S. Platforms: APKD and NKR

The simulated market above is still smaller than some U.S. platforms. For example, APKD had 171 registered pairs in 2013 [START_REF] Agarwal | What Matters for the Productivity of Kidney Exchange?[END_REF], Table 2), an arrival rate of 14.25 pairs per month; in the same year, NKR had 468 registered pairs, an arrival rate of 24.8 pairs per month.

To simulate markets similar to APKD or NKR, we follow the method in Ashlagi et al. (2019a).

We assume that pair arrival follows a Poisson process with a daily arrival rate of 0.475 for APKD and 1.4109 for NKR (Agarwal et al., 2018, Table 2). Similar to our previous simulations, we assume that pairs do not exit exogenously.

The simulations have two steps for each platform. For example, to simulate APKD, we first construct a pool of 10,000 pairs that exhibit the type distribution of the APKD pairs during 2010-19 (Ashlagi and Roth, 2020, Table 2); in step two, we randomly sample (with replacement) a pair from the pool whenever a pair is to arrive in the simulation. The simulation of NKR is similar, except that the pool of 10,000 pairs follows the distribution of the NKR pairs during 2010-14 (Ashlagi and Roth, 2020, Table 1). The simulation time horizon is the same as the previous simulations, a total of 1,644 days. We simulate Pairwise, 2-way and 3-way pairwise exchanges, Unpaired, and Omniscient with 1000 sets of pair arrivals and report averages over the 1000 sets.22

Results. Table 4 shows that, even with larger market sizes and different pair characteristic distributions, the comparison among the algorithms has the same pattern as in our baseline simulation (Table 2). As reported in columns ( 1)-( 3), the simulated APKD has an average market size of 781 pairs, 1.33 times as large as the simulations with French KEP and desensitization pairs. Unpaired still dominates Pairwise in terms of transplant rate (68 percent vs. 46 percent) and average censored waiting time (294 vs. 493 days), while still being close to Omniscient.

For the simulated NKR (columns 4-6), the average market size is about four times as large as the one with French KEP and desensitization pairs. Even though both the transplant rate and the average censored waiting time under Pairwise improve further (56 percent and 404 days), it is still dominated by Unpaired (72 percent and 248 days). Omniscient (74 percent and 229 days) does not improve much upon Unpaired.

Although not reported in the table, allowing both 2-and 3-way pairwise exchanges increases transplant rates to 56 percent for APKD and 66 percent for NKR and lowers waiting time to 414 for APKD and 317 for NKR. This performance is still worse than what Unpaired can achieve, Importantly, the potential incentive issues are further mitigated as the market grows. Relative to the baseline, the median waiting times in P and D are reduced by at least 40 percent for APKD (column 2) and by more than 69 percent for NKR (column 5). In particular, for NKR, the median waiting times are merely 69 days in P and 90 days in D, which are unlikely to raise serious incentive concerns.

Robustness Checks

We now present an extensive set of robustness checks on the performance of Unpaired and Unpaired with DDL relative to other algorithms. In each of the checks, we introduce a unique change into the baseline (columns 4 and 5 of Table 2) that has the 78 KEP pairs.

In the following, Section 3.5.1 first investigates the consequences of the incentive issues of Unpaired by allowing patients to opt out of donation-before-receipt or by letting unpaired donors to renege. We then showcase how Unpaired with DDL can be modified to address additional considerations and that its performance is unaffected if a patient only accepts a DDL kidney of a very high quality. Section 3.5.2 relaxes the no-exit assumption and shows that our results are robust to this assumption. In Section 3.5.3, we implement multiple chains by providing 30 altruistic donors, which is plenty, to the exchange and find that it performs comparably to Unpaired but still dominated by Unpaired with DDL. Notes: For APKD and NKR, the arrival rates are those of 2013 [START_REF] Agarwal | What Matters for the Productivity of Kidney Exchange?[END_REF], Table 2). Pairs are sampled from the distributions from 2010 to 2019 for APKD (Ashlagi and Roth, 2020, Table 2) and from 2010 to 2014 for NKR (Ashlagi and Roth, 2020, Table 1). The algorithms are simulated for 1,644 days, the same as the simulations with French data. The statistics are averages across 1000 sets of simulations. A more detailed version including statistics on hypersensitized and O patients as well as AB donors is Table E.2 in Appendix E.

Further Quantifying and Addressing the Potential Incentive Issues of Unpaired

Below we perform four sets of simulations that quantify the incentive issues of the Unpaired algorithm and then evaluate some new algorithms that may be more acceptable to policymakers as solutions.

First, we measure the effect of certain patients opting out of donation-before-receipt. Hypersensitized patients or those with a very high PRA are likely to do so, because their wait in P would be longer than others. Our simulation shows that Unpaired is worsened by the opt-out policies but still dominates Pairwise and Chain on every dimension except for the outcomes of the opting-out patients. In other words, these opt-out policies harm those who choose to opt out, reducing their incentive to do so.

Second, we quantify the effect of unpaired donors reneging due to receipt-before-donation. We may lose an unpaired donor if she waits for a long time in D. Assuming unpaired donors renege at a rate assumed in the literature, we find reneging has virtually no effect on the performance of Unpaired and Unpaired with DDL.

Third, we evaluate two modified versions of Unpaired with DDL that can be more acceptable in practice as potential solutions to the incentive issues. The proposed reform in France already

shows that Unpaired with DDL can be acceptable to policymakers (see Remark 3.3), but there can be additional considerations. For instance, one may want to balance available donors and waiting patients in the exchange or to keep constant the supply of over-demanded donors (e.g., O donors) to the DDL. We define the modified versions and show in simulations that their performance is similar to Unpaired with DDL (without any modification).

Fourth, we investigate how sensitive the performance of Unpaired with DDL is to patients accepting only DDL kidneys with a higher quality. Our simulation shows that its performance remains close to the baseline even when patients are more selective.

Pairs opting out of donation-before-receipt. When a patient is hard-to-match, she may decide not to let her paired donor donate before she receives a transplant, while she is still willing to accept a transplant before her paired donor donates. We therefore consider the possibility of such patients opting out of donation-before-receipt (or entering P). We investigate the effects of three types of opt-out policies on the performance of the algorithms.

First, we let the 21 hypersensitive patients opt out. As shown in Second, the pairs with a hypersensitized patient and an AB donor are assumed to opt out of entering P. The rationale is that an AB donor is hard-to-match too, and an exchange may encourage them to opt out to reduce the overall donor waiting time in D. In our sample, there is only one such pair. As expected, the results with this opt-out policy (columns 5 and 6 of Table E.3) are almost identical to the baseline.

Last, we let the patients with a PRA above 0.98, who are the hardest to match, opt out of donation-before-receipt. There are in total 12 such pairs. Columns ( 7) and ( 8) shows that the performance is worse than the baseline (columns 1 and 2) but not as bad as the first opt-out policy; again, the negative effects are mostly on hypersensitized or O patients.

In sum, the performance of the Unpaired algorithms decreases with the number of patients opting out of donation-before-receipt. However, the worst-case results, which are from the first optout policy, still dominate Pairwise and Chain in the baseline (Table 2) on every dimension except the overall waiting time and transplant rate of hypersensitized patients. In other words, these opt-out policies harm those who choose to opt out, reducing their incentive to opt out.

Reneging of Donors in D.

Receipt-before-donation results in unpaired donors who may renege while waiting in D. To assess its effect, we allow a donor in D to renege with probability 0.17 percent per day when she is in D. Equivalently, a donor reneges with a probability of 5 percent in a month, the rate assumed by [START_REF] Gentry | The roles of dominos and nonsimultaneous chains in kidney paired donation[END_REF] This new algorithm maintains a balance between available donors and waiting patients. Higher-quality DDL kidneys in Unpaired with DDL. In the above simulations of Unpaired with DDL, we assume that a patient always accepts a DDL kidney when receives the offer. In practice, the algorithm should allow a patient to decide. Therefore, when a DDL kidney is not considered comparable to a living donor kidney, a patient may reject the DDL kidney. We test how sensitive our results are to this concern by screening DDL kidneys with a higher standard. To qualify for the algorithm, we now require a DDL kidney to have a KDPI below the median LKDPI among all compatible living donations in France in our sample period.

Column (7) of Table E.4 shows the results. The number of DDL kidneys that are used in the exchange drops from 29 (column 2) in the baseline to 28 (column 7). Consequently, the performance of the new version is only slightly worse than Unpaired with DDL in the baseline and remains

substantially better than Unpaired. The median waiting time of patients in P increases to 6 days, while that of donors in D is now 21 days. However, both numbers are still sufficiently low, implying that it still helps solve the incentive issues of Unpaired.

Allowing Pairs to Exit

We now relax the no-exit assumption. Recall that the exit date of pair i, (p i , d i ), denoted by e(i),

is simulated as described in Section 3.2. Furthermore, we make the following assumption: if

(p i , d i )
are still waiting at e(i), both of them exit at e(i); if d i donates before e(i) and if p i has not received a kidney by e(i), p i leaves at e(i); if p i receives a kidney from someone else before e(i), d i stays until the end of our simulation, T . Recall that for pairs who do not exit in our data, we set e(i) = T .

With these assumptions, we simulate the first three algorithms (i.e., Pairwise, Chain, Unpaired) in the same way as before, while taking into account some pairs and patients may exit. We again use the Integer Linear Programing problem described in Appendix C to simulate Omniscient, taking into account exit constraints.

Table E.5 in Appendix E shows the same pattern across algorithms as in the baseline (Table 2), which implies that pair exits do not affect the performance ranking of the algorithms. Most importantly, Unpaired (column 4) remains similar to Omniscient (Column 6) in terms of transplant rate (54 percent vs. 55 percent), although less so in terms of waiting time (218 vs. 158 days).

Compared with the baseline (column 4 of Table 2), the transplant rate of Unpaired is only slightly worsened when pairs may exit, 54 percent vs. 57 percent. The average (censored) waiting time is in fact lower when pairs may exit (218 vs. 440 days), because the waiting time is censored at exit date.

Multiple Chains

In practice, multiple altruistic donors may arrive, making multiple chains possible. To see how this can improve the performance of Chain, we draw 30 high-quality DDL kidneys as altruistic donors and assume that they arrive on the date they become a DDL kidney. A high-quality DDL kidney must have a KDPI below the LKDPI of one of the living donors in the KEP pairs. Similar to the previous simulations of Chain, we assume that after arrival, every DDL kidney remains available until either the end of our simulation or when it is transplanted. This may result in up to 30 chains.

At the same time, 2-way pairwise exchanges are still allowed.

We set 30 as the number of altruistic donors, slightly more the 29 DDL kidneys that Unpaired with DDL uses in the baseline (column 5, Table 2). Note that for every DDL kidney that Unpaired with DDL uses, a living donor donates a kidney to the DDL. By contrast, Chain does not require any living donor to donate to the DDL.

As expected, the results show that allowing for multiple chains improves upon the single-chain exchange. By using on average an extra of 18 altruistic donors, multiple chains reach a transplant rate of 63 percent, higher than the rate of 57 percent under Unpaired (not using any DDL kidneys).

However, allowing for multiple chains, the average (censored) waiting time among all patients is 453 days, and that among transplanted patients is 248 days; both are higher than those under Unpaired (440 and 180 days, respectively). We note that this is not a fair comparison, because Unpaired does not use the DDL kidneys. Furthermore, the performance of multiple chains is still substantially dominated by Unpaired with DDL in terms of waiting time and transplant rate.

Practices Related to the Unpaired Algorithm

Our proposed Unpaired algorithm eliminates the timing constraints on the donation and receipt for any incompatible pair. Specifically, it allows receipt-before-donation (i.e., a patient can receive a kidney before her paired donor donates to some other patient) as well as donation-before-receipt (i.e., a donor can donate before her paired patient receives a transplant). Recall that Pairwise allows neither; Chain does not allow donation-before-receipt but permits receipt-before-donation only if a patient is compatible with a bridge donor. Some recent practices also relax the timing constraints, as we discuss below.

Vouchers. As first studied by [START_REF] Veale | Vouchers for future kidney transplants to overcome chronological incompatibility between living donors and recipients[END_REF], a voucher program allows donation-before-

receipt. An example is the Advanced Donation Program (ADP) implemented by NKR, where a donor gifts a kidney before her paired-but-incompatible patient receives a kidney. 24 When an advance donation happens, the paired patient obtains a voucher that gives her a higher priority for a kidney in the future. In the ADP, a patient with a voucher will have a high priority for receiving a kidney from a donor who would otherwise end a chain.25

Combined with the Chain algorithm, the ADP allows both donation-before-receipt and receiptbefore-donation, but with important restrictions. For example, a patient with a voucher, similarly to an unpaired patient in the Unpaired algorithm, is offered a donor kidney only when the donor's paired patient has already received a transplant in a chain and when the donor kidney is incompatible with all patients in the remaining pairs. Moreover, an advanced donor can only donate to patients whose donors have not donated. As a result, patients with a voucher in ADP tend to wait for a long time. 26 In contrast, an unpaired patient in Unpaired can receive a kidney from any donor, paired or unpaired, while a donor can donate to any compatible patient, paired or unpaired. In this sense, the Unpaired algorithm generalizes advanced donation by relaxing the constraints on donation-beforereceipt and integrating it with receipt-before-donation.

List Exchange. In small KEPs like the French KEP, the waiting time of unpaired patients and unpaired donors can be long, creating potential incentive issues. One of our proposed solutions is to use Unpaired with DDL (Definition 3.1), which combines the Unpaired algorithm with the DDL. Certain integrations of DDL and living donation are already observed in practice. Upon the approval of United Network for Organ Sharing, the New England region implemented a program called List Exchange. It allows a living donor to donate to a patient on the DDL and, in return, her paired patient obtains a high priority on the DDL [START_REF] Delmonico | Donor kidney exchanges[END_REF]. In other words, it allows donation-before-receipt for donations to the DDL.

There are two important differences between List Exchange and Unpaired with DDL. First, List

Exchange may decrease the participation in the KEP, opposite to the effects of Unpaired with DDL.

List Exchange directly increases the supply of kidneys to the DDL by encouraging living donations to the DDL, potentially reducing the supply of incompatible pairs to the KEP. On the contrary, Unpaired with DDL keeps constant the supply to the DDL and that to the KEP, because a living donor donates to the DDL if and only if a DDL kidney can be used by an unpaired patient. Second, List Exchange does not incentivize patients to find a highly sought-after kidney to donate to the DDL. Any healthy kidney will be quickly accepted by some patient on the DDL due to the huge excess demand. In contrast, Unpaired with DDL may increase the supply of highly sought-after kidneys, because a patient can obtain a higher priority for a kidney, living donor or DDL, once her paired donor has donated. 27

In sum, the implementation of the voucher program and List Exchange in practice make us optimistic about the potential of Unpaired, as well as Unpaired with DDL, to promote kidney exchange. The innovations in our algorithm have been shown to be acceptable in practice, while our algorithms enjoy significant performance advantages relative to state-of-art algorithms. Indeed, the latest revision of the bioethics law in France proposes to allow the French KEP to implement many 26 Among NKR's 10 advanced donations during August 2011 to August 2014, by the end of that period, 8 of the 10 patients had received a kidney 178 days on average after their donors had donated [START_REF] Flechner | The incorporation of an advanced donation program into kidney paired exchange: initial experience of the National Kidney Registry[END_REF]. In our simulations of NKR, the Unpaired algorithm leads to an average waiting time in P, conditional on receiving a transplant, of 123 days. Moreover, [START_REF] Tenenbaum | Swaps and Chains and Vouchers, Oh My!: Evaluating How Saving More Lives Impacts the Equitable Allocation of Live Donor Kidneys[END_REF] reports that ADP notifies hard-to-match patients (typically hypersensitized) that the waiting time after their donor has donated may often exceed 1-2 years. In our simulations the mean waiting time in P (conditionally on receiving a transplant) for hypersensitized patients is only 136 days.

27 This incentive in our proposed algorithm resembles list-exchange chains proposed by Roth et al. (2006) that give a high priority on the DDL to patients whose paired donors have initiated a chain in the KEP. aspects of Unpaired with DDL (see Remark 3.3).

Conclusion

We have proposed a new matching algorithm, Unpaired kidney exchange, and argued that it significantly improves upon the outcome of currently utilized state-of-the-art algorithms. We have also proposed solutions to two practical challenges, the potentially long waiting times of a patient after her paired donor's donation and of a donor after her paired patient's transplantation. One thing we have not systematically examined is how to convince patients and donors to fully participate in markets which use this algorithm, i.e., to accept both receipt-before-donation and donation-beforereceipt. We see two potential concerns.

First, patients and donors may be concerned that few others will participate in the market. In an extreme case, a patient-donor pair may believe that they will be the last people to enter the market. In this case, if the donor is a match with an existing patient but the patient cannot receive a kidney from an existing donor, then participating in the market will not help the patient and will take a kidney from her paired donor. This may lead to the market unravelling. This is analogous to a non-monetary equilibrium, where no one accepts fiat money in exchange for goods and services because everyone believes that no one else will accept money from them ( [START_REF] Kiyotaki | A Search-Theoretic Approach to Monetary Economics[END_REF].

A guarantee that money has value, for example by permitting people to use it to pay taxes, can eliminate this equilibrium. Analogously, the Unpaired with DDL algorithm gives donors the right for their patient to get a kidney, which is enough to eliminate this non-participation equilibrium.

Second, patients and donors may be skeptical of new markets. Here we are hopeful that the combination of theory and evidence in this paper will alleviate this skepticism. We have shown that if Unpaired or Unpaired with DDL had been employed in existing markets, participants outcomes would have been meaningfully improved. We have also explained theoretically why we should expect this to be the case. This combination of evidence and theory gives us confidence that we will see similar improvements in any future application of the Unpaired algorithm.

A Proof of Proposition 2.4

This section is organized as follows. We first give the basic description of the Markov chain (over the number of patients of each type (k H , k E )) induced by the Unpaired algorithm as well as some basic definitions that will be used all along the proof (Section A.1). We define k * H as the number of hard-to-match patients which equalizes the transition rates from k * H to k * H + 1 and that from k * H to k * H -1 assuming that no easy-to-match patients is in the pool. Then, the formal argument is presented and we prove that, at the invariant distribution, as p H vanishes, the number of hardto-match patients waiting in the system is highly concentrated around k * H . We split the proof into two blocks. In a first block, we show that the number of hard-to-match patients remaining in the system at the invariant distribution puts vanishing weight above k * H (Section A.2). In the second block (Section A.3), we prove the concentration result, i.e., show that this upper bound is actually tight. In order to prove the tightness result, we need to prove that with probability going to 1, the number of easy-to-match patients remaining in the pool is "small", i.e., we show that it is of order smaller than 1/p H . Finally, we explain how we can use the bounds to obtain Proposition 2.4 (Section A.4).

A.1 Preliminaries

We make several preliminary remarks. First, under the unpaired exchange algorithm, one can easily check that the number of patients remaining in the system equals the number of donors remaining (S t = Z t for all t). This is useful since we can simply focus on the evolution of the number of patients of each type remaining in the system.

We denote by Q the transition rate matrix over states N × N. We will mainly focus on the following transition rates:

Q([k H , k E ], [k H + 1, k E ]) = nλ(1 -p H ) k E +k H (1 -p E ) k E (1 -p H ) k H Q([k H , k E ], [k H -1, k E ]) = n λ[1 -(1 -p H ) k E +k H ][1 -(1 -p H ) k H ]+ (1 -λ)[1 -(1 -p E ) k E +k H ][1 -(1 -p H ) k H ] Q([k H , k E ], [k H , k E + 1]) = n(1 -λ)(1 -p E ) k E +k H (1 -p E ) k E (1 -p H ) k H Q([k H , k E ], [k H , k E -1]) = n λ[1 -(1 -p H ) k E +k H ](1 -p H ) k H [1 -(1 -p E ) k E ]+ (1 -λ)[1 -(1 -p E ) k E +k H ](1 -p H ) k H [1 -(1 -p E ) k E ] Q([k H , k E ], [k H + 1, k E -1]) = nλ(1 -p H ) k E +k H (1 -p H ) k H [1 -(1 -p E ) k E ] Q([k H , k E ], [k H -1, k E + 1]) = n(1 -λ)(1 -p E ) k E +k H [1 -(1 -p H ) k H ]
Let also first recall that the Global Balance Equations (GBE) are a set of equations that characterize the invariant distribution of a Markov chain, when such a distribution exists. The above stochastic process is a Markov chain which has an invariant distribution as proved in Appendix B.4.

In the sequel, we let π be this invariant distribution. The GBE can be stated as follows: for any subset S ⊂ N × N, we must have:

j∈S π(j) i / ∈S Q(j, i) = i / ∈S π(i) j∈S Q(i, j) (A.1)
Finally, let us define k * H as the real number ensuring

λ(1 -p H ) 2k * H = λ 1 -(1 -p H ) k * H 2 + (1 -λ) 1 -(1 -p H ) k * H . (A.2)
Simple algebra shows that

(1 + λ)(1 -p H ) k * H = 1 (A.3)
and so

k * H = - ln (1 + λ) ln(1 -p H ) .
In what follows, we sometimes use the notation π H (resp. π E ) for the marginal of distribution π on the first (resp. second) dimension of the state space, i.e., π

H (k H ) := ∞ k E =0 π(k H , k E ).

A.2 Upper-bound result

In the sequel, we first prove the following result providing an upper-bound on the size of the number of hard-to-match patients.

Proposition A.1. Fix any δ > 0,

π H k H : k H 1/(-ln(1 -p H )) ≥ ln (1 + λ) + δ → 0 as p H vanishes.
In order to show this, the following intermediary result is useful.

Lemma A.2. The following must hold

λ 1 -(1 -p H ) k+1 2 + (1 -λ) 1 -(1 -p H ) k+1 λ(1 -p H ) 2k ≥ λ 1 -(1 -p H ) k+1 + (1 -λ) 1 -(1 -p H ) k+1 λ(1 -p H ) k if k ≥ k * H . The inequality holds in the other direction if k ≤ k * H -1.
Proof of Lemma A.2. Using simple algebra one can show that the inequality stated in Lemma A.2 is equivalent to

1 ≥ λ(1 -p H ) k+1 + λ(1 -p H ) k + (1 -λ)(1 -p H ) k . If k ≥ k * H , using (A.3), we have that (1 + λ)(1 -p H ) k ≤ 1. Since (1 + λ)(1 -p H ) k ≥ λ(1 -p H ) k+1 + λ(1 -p H ) k + (1 -λ)(1 -p H ) k ,
we are getting the above inequality for k

≥ k * H , as claimed. If k ≤ k * H -1, using (A.3) again, (1 + λ)(1 -p H ) k+1 ≥ 1. Since (1 + λ)(1 -p H ) k+1 ≤ λ(1 -p H ) k+1 + λ(1 -p H ) k + (1 -λ)(1 -p H ) k ,
we are getting the reverse inequality for k ≤ k * H -1, as claimed.

We can now show the following lemma.

Lemma A.3. For any ε > 0, there exists a constant ρ ∈ (0, 1) such that, for any p H > 0 and for

any integer k H ≥ k * H (1 + ε) π H (k H + 1) π H (k H ) ≤ ρ
Proof of Lemma A.3. Fix any ε > 0, and an arbitrary k H ≥ k * H (1 + ε) and let us consider the set

S = {0, 1, ..., k H } × N. The GBE (Equation (A.1)) gives us ∞ k E =0 π(k H , k E ) [Q([k H , k E ] , [k H + 1, k E ]) + Q([k H , k E ] , [k H + 1, k E -1])] = ∞ k E =0 π(k H + 1, k E ) [Q([k H + 1, k E ] , [k H , k E ]) + Q([k H + 1, k E ] , [k H , k E + 1])]
Using the expressions of the transition rates, this can be rewritten as:

∞ k E =0 π(k H , k E ) λ(1 -p H ) k E +k H (1 -p H ) k H = ∞ k E =0 π(k H + 1, k E ) λ 1 -(1 -p H ) k E +k H +1 1 -(1 -p H ) k H +1 + (1 -λ) 1 -(1 -p H ) k H +1 .
Observing that the term in brackets in left-hand side is maximized at k E = 0 while the term in brackets in the right-hand side is minimized at k E = 0, we get .4) where we recall that π

∞ k E =0 π(k H , k E ) λ(1 -p H ) 2k H ≥ ∞ k E =0 π(k H +1, k E ) λ 1 -(1 -p H ) k H +1 2 + (1 -λ) 1 -(1 -p H ) k H +1 . It implies that π H (k H ) π H (k H + 1) ≥ λ 1 -(1 -p H ) k H +1 2 + (1 -λ) 1 -(1 -p H ) k H +1 λ(1 -p H ) 2k H . ( A
H (k H ) = ∞ k E =0 π(k H , k E ).
From the inequality above, we deduce:

π H (k H + 1) π H (k H ) ≤ λ(1 -p H ) 2k H λ [1 -(1 -p H ) k H +1 ] 2 + (1 -λ) [1 -(1 -p H ) k H +1 ] ≤ λ(1 -p H ) k H 1 -(1 -p H ) k H +1 ≤ λ(1 -p H ) k * H (1+ε) 1 -(1 -p H ) k * H (1+ε) = λ 1 1+λ 1+ε 1 -1 1+λ 1+ε := ρ < λ 1 + λ 1 1 -1 1+λ = 1
where the first inequality comes from the Equation (A.4). The second inequality comes from Lemma A.2 and

k H ≥ (1 + )k * H ≥ k * H .
The third inequality comes from the fact that (1

-p H ) k H +1 ≤ (1 -p H ) k H ≤ (1 -p H ) (1+ )k *
H . The first equality comes from equation (A.3). Hence we obtain a positive constant, denoted by ρ, strictly smaller than one and independent of

p H , such that for all k H ≥ k * H (1 + ε): π H (k H +1) π H (k H ) ≤ ρ.
Using the result stated in Lemma A.3 we can show the following:

Lemma A.4. For any ε > 0, there exists a constant ρ ∈ (0, 1) such that, for any p H > 0 and for any integer z > 0:

π H {k H : k H ≥ k * H (1 + ε) + z} ≤ ρ z 1 -ρ Proof of Lemma A.4. We know from Lemma A.3 that for all k H ≥ k * H (1+ε), π H (k H +1) ≤ ρπ H (k H ) with ρ ∈ (0, 1).
Then by induction we get that:

π H (k * H (1 + ε) + i) ≤ ρ i π H (k * H (1 + ε)) (A.5) It implies that π H {k H : k H ≥ k * H (1 + ε) + z} = +∞ i=z π H (k * H (1 + ε) + i) ≤ +∞ i=z ρ i π H (k * H (1 + ε)) ≤ +∞ i=z ρ i = ρ z 1 -ρ
where the first inequality comes from the Equation (A.5), the second inequality immediately comes from the fact that π H (k * H (1 + ε)) ≤ 1 and the last equality is obtained using the fact that ρ < 1.

Completion of the proof of Proposition A.1. Fix any δ > 0. We want to show that

π H k H : k H 1/(-ln(1 -p H )) ≥ ln (1 + λ) + δ → 0
as p H vanishes. Let z = 1/ √ p H and fix ε > 0 and p H > 0 small enough so that ln (1 + λ) (1 + ε) +

√ p H ≤ ln (1 + λ) + δ. Hence, we obtain

π H k H : k H 1/(-ln(1 -p H )) ≥ ln (1 + λ) + δ ≤ π H k H : k H 1/(-ln(1 -p H )) ≥ ln (1 + λ) (1 + ε) + √ p H ≤ π H k H : k H ≥ k * H (1 + ε) + √ p H -ln(1 -p H ) ≤ ρ √ p H -ln(1-p H ) 1 -ρ → 0
where the first inequality is ensured by our choice of ε and p H while the last inequality is by Lemma A.4 and the convergence result holds since ρ ∈ (0, 1) (still by Lemma A.4) and since -ln(1p H )/p H goes to 1 as p H vanishes and so

√ p H -ln(1-p H ) explodes as p H vanishes.

A.3 Lower-bound result

Before providing a lower-bound on the size of the number of hard-to-match patients (Section A.3.2)

we need to establish an upper-bound on the size of the number of easy-to-match patients (Section A.3.1).

A.3.1 An upper-bound on the number of easy-to-match patients Lemma A.5. There is a constant k * E such that, for any k and for any p H small enough,

π E {k E : k E ≥ k * E + k} ≤ 3 + k (1 -ρ) 2 ρk
where ρ < 1.

Proof of Lemma A.5. Fix an arbitrary k E ≥ 0 and let us consider the set S = N×{0, 1, ..., k E }.

Then, the GBE (Equation (A.1)) writes as:

∞ k H =0 π(k H , k E ) [Q([k H , k E ] , [k H , k E + 1]) + Q([k H , k E ] , [k H -1, k E + 1])] = ∞ k H =0 π(k H , k E + 1) [Q([k H , k E + 1] , [k H , k E ]) + Q([k H , k E + 1] , [k H + 1, k E ])]
Using the expressions of the transition rates, this can be rewritten as:

∞ k H =0 π(k H , k E )(1 -λ) (1 -p E ) k E +k H (1 -p E ) k E (1 -p H ) k H + (1 -p E ) k E +k H [1 -(1 -p H ) k H ] = ∞ k H =0 π(k H , k E + 1)    λ[1 -(1 -p H ) k E +1+k H ](1 -p H ) k H [1 -(1 -p E ) k E +1 ] +(1 -λ)[1 -(1 -p E ) k E +1+k H ](1 -p H ) k H [1 -(1 -p E ) k E +1 ] +λ(1 -p H ) k E +1+k H (1 -p H ) k H [1 -(1 -p E ) k E +1 ]   
This can be simplified to

∞ k H =0 π(k H , k E ) (1 -λ)(1 -p E ) k E +k H ≥ ∞ k H =0 π(k H , k E + 1) λ(1 -p H ) k H [1 -(1 -p E ) k E +1 ]+ (1 -λ)[1 -(1 -p E ) k E +1+k H ](1 -p H ) k H [1 -(1 -p E ) k E +1 ]
Observing that the expression in brackets in the left hand side is maximized at k H = 0 and that the expression in brackets in right hand-side may be bounded below by disregarding the second term, we get that:

(1 -λ)(1 -p E ) k E π E (k E ) ≥ ∞ k H =0 π(k H , k E + 1)λ(1 -p H ) k H [1 -(1 -p E ) k E +1 ] (A.6)
where π E denotes the marginal of π on the number of easy-to-match patients in the pool, i.e.,

π E (k E ) = ∞ k H =0 π(k H , k E ).
In the sequel, for each k E and for any ε > 0, we define S(k

E ) := {k H : k H ≤ (1 + ε)k * H + ln(2)/p H + k E } as well as π S(k E ) (k E ) := k H ∈S(k E ) π(k H , k E ).
We must have:

π E (k E ) -π S(k E ) (k E ) = k H / ∈S(k E ) π(k H , k E ) ≤ ∞ k E =0 k H / ∈S(k E ) π(k H , k E ) = k H / ∈S(k E ) π H (k H ).
Hence, by Lemma A.4, for any k E ,

π E (k E ) -π S(k E ) (k E ) ≤ ρ ln(2)/p H +k E 1 -ρ (A.7)
where ρ ∈ (0, 1). Note that for each k H ∈ S(k E ), for p H small enough, we have

(1 -p H ) k H ≥ (1 -p H ) (1+ε)k * H +ln(2)/p H +k E ≥ 1 3 1 1 + λ 1+ε (1 -p H ) k E
where the second inequality comes from the fact that as p H vanishes, (1 -p H ) ln(2)/p H converges to 1 e ln(2) = 1 2 > 1 3 . Thus, we can rewrite Equation (A.6) as

(1 -λ)(1 -p E ) k E π S(k E ) (k E ) + (1 -λ)(1 -p E ) k E π E (k E ) -π S(k E ) (k E ) ≥ 1 3 1 1 + λ 1+ε λ(1 -p H ) k E [1 -(1 -p E ) k E +1 ]π S(k E +1) (k E + 1)
where the last inequality comes from the fact that π E (k E + 1) ≥ π S(k E +1) (k E + 1).

Let us denote

ρ(k E ) := (1 -λ)(1 -p E ) k E 1 3 1 1+λ 1+ε λ(1 -p H ) k E [1 -(1 -p E ) k E +1 ] .
The above inequality can be written as

ρ(k E )π S(k E ) (k E ) + ρ(k E ) π E (k E ) -π S(k E ) (k E ) ≥ π S(k E +1) (k E + 1). Since ρ(k E ) ≤ 1 -λ λ 3 1 1+λ 1+ε p E 1 -p E 1 -p H k E ,
it must be that for any p H small enough, there is k * E large enough (which does not depend on p H ) so that

sup k E ≥k * E ρ(k E ) =: ρ * < 1. A.1
Hence, from the definition of ρ * and from Equation (A.7) we obtain

ρ * π S(k E ) (k E ) + ρ * ρ ln(2)/p H +k E 1 -ρ ≥ π S(k E +1) (k E + 1)
for any k E ≥ k * E . Clearly, for p H small enough, ρ ln(2)/p H 1-ρ < 1, and since ρ * < 1, we have

ρ * π S(k E ) (k E ) + ρ k E ≥ π S(k E +1) (k E + 1)
holds for any k E ≥ k * E . Now, setting ρ := max(ρ * , ρ) < 1, we obtain

ρπ S(k E ) (k E ) + ρk E ≥ π S(k E +1) (k E + 1).
Now, proceeding inductively, we can rewrite for any

k E ≥ k * E ρi π S(k * E ) (k * E ) + iρ k * E +i ≥ π S(k * E +i) (k * E + i) (A.8)
A.1 k * E is simply defined as the smallest kE ensuring

1-λ λ 2 ( 1 1+λ ) 1+ε p E 1-p E 1-p k E
< 1 where p is an arbitrary number in (0, pE). We then require that pH is smaller than p.

Now, we have

∞

k E ≥k * E +k π E (k E ) = ∞ i=k π E (k * E + i) = ∞ i=k π S(k * E +i) (k * E + i) + ∞ i=k [π E (k * E + i) -π S(k * E +i) (k * E + i)] ≤ ∞ i=k π S(k * E +i) (k * E + i) + ∞ i=k ρ ln(2) p H +k * E +i 1 -ρ ≤ ∞ i=k π S(k * E +i) (k * E + i) + ∞ i=k ρi 1 - ρ ≤ ∞ i=k ρi π S(k * E ) (k * E ) + ρk * E ∞ i=k iρ i + ρk (1 -ρ) 2 ≤ ∞ i=k ρi + ∞ i=k iρ i + ρk (1 -ρ) 2 ≤ ρk 1 -ρ 1 + 1 + k 1 - ρ + 1 1 -ρ ≤ ρk 1 - ρ 3 + k 1 - ρ (A.9)
where the first inequality uses (A.7). The second uses ρ ≥ ρ. The third uses (A.8). The fourth uses the fact that both π S(k * E ) (k * E ) and ρ are smaller than one. The penultimate inequality uses the following fact:

n i=0 iρ i = ρ -(n + 1)ρ n+1 + nρ n+2 (1 -ρ) 2 (A.10)
and the fact that

+∞ i=k iρ i = +∞ i=0 iρ i - k-1 i=0 iρ i = ρ (1 -ρ) 2 - ρ -k ρk + (k -1)ρ k+1 (1 -ρ) 2 = k ρk + ρk+1 -k ρk+1 (1 -ρ) 2 (A.11) ≤ k ρk + ρk (1 -ρ) 2 (A.12)
where the second equality comes from equation (A.10) and ρ ∈ (0, 1) is used for this equality as well as for the inequality.

A.3.2 Completing of the lower-bound result for hard-to-match patients Proposition A.6. Fix any δ > 0, π H k H :

k H 1/(-ln(1-p H )) ≤ ln (1 + λ) -δ → 0 as p H vanishes.
In the sequel we define S := {k

E : k E ≤ k * E +1/ √ p H } and, as before, π S (k H ) = k E ∈S π(k H , k E ).
We first prove the following lemma.

Lemma A.7. For any ε ∈ (0, 1) and any p H small enough, there exist constants ρ ∈ (0, 1), ρ1 ∈ (0, 1)

and ρ2 > 0 such that, for any integer z > 0:

π S (k * H (1 -ε) -z) ≤ ρz 1 π S (k * H (1 -ε)) + φ(p H )ρ 2 1 -ρz 1 1 -ρ1 where φ(p H ) := 3 + 1 √ p H ρ1/ √ p H (1-ρ) 2 .
Proof of Lemma A.7. Let us recall that using the GBE we obtained

∞ k E =0 π(k H , k E ) λ(1 -p H ) k E +k H (1 -p H ) k H = k E ∈S π(k H + 1, k E ) λ 1 -(1 -p H ) k E +k H +1 1 -(1 -p H ) k H +1 + (1 -λ) 1 -(1 -p H ) k H +1 + k E / ∈S π(k H + 1, k E ) λ 1 -(1 -p H ) k E +k H +1 1 -(1 -p H ) k H +1 + (1 -λ) 1 -(1 -p H ) k H +1 .
Note that for p H small enough, (1 .2 This observation allows us to lower-bound the left-hand side of the above displayed equation. Thus, by upper-bounding the right-hand side as well (simply using the

-p H ) k E ≥ (1 -p H ) k * E .c √ p H with c ∈ (0, 1) whenever k E ∈ S = {k E : k E ≤ k * E + 1/ √ p H }. A
facts that for k E ∈ S, k E ≤ k * E + 1/ √ p H and 1 -(1 -p H ) k E +k H +1 ≤ 1), we get π S (k H ) λ(1 -p H ) k * E .c √ p H (1 -p H ) 2k H ≤ π S (k H + 1) λ 1 -(1 -p H ) k * E +1/ √ p H +k H +1 1 -(1 -p H ) k H +1 + (1 -λ) 1 -(1 -p H ) k H +1 +(π H (k H + 1) -π S (k H + 1)) λ 1 -(1 -p H ) k H +1 + (1 -λ) 1 -(1 -p H ) k H +1 .
In the sequel we fix ε ∈ (0, 1) and consider k H ≤ k * H (1 -ε). We will be using the following two inequalities which hold for p H small enough : k .2 Simply note that, for any kE ∈ S,

(1 -pH ) k E ≥ (1 -pH ) k * E (1 -pH ) 1/ √ p H = (1 -pH ) k * E (1 -pH ) 1/p H √ p H .
Since (1 -pH ) 1/p H converges from below to 1/e, we can ensure that for pH small enough, (1 -pH

) k E ≥ (1 - pH ) k * E 0.9 e √ p H .
(recall by Lemma A.5 that k * E is a constant which does not depend on p H ). Since we assumed that

k H ≤ k * H (1 -ε), we must have k * E + 1/ √ p H + k H + 1 ≤ k * E + 1/ √ p H + k * H (1 -ε) + 1 which is thus smaller than k *
H for p H small enough, as claimed. These two inequalities allow us to further bound the right-hand side of the above displayed equation:

π S (k H ) λ(1 -p H ) k * E .c √ p H (1 -p H ) 2k H ≤ π S (k H + 1) λ 1 -(1 -p H ) k * H 1 -(1 -p H ) k * H + (1 -λ) 1 -(1 -p H ) k * H +(π H (k H + 1) -π S (k H + 1)) λ 1 -(1 -p H ) k H +1 + (1 -λ) 1 -(1 -p H ) k H +1 ≤ π S (k H + 1) λ 1 -(1 -p H ) k * H 2 + (1 -λ) 1 -(1 -p H ) k * H + π H (k H + 1) -π S (k H + 1).
Then, using the fact that k H ≤ k * H (1 -ε), we can lower-bound the left-hand side of the above equation to get

π S (k H ) λ(1 -p H ) k * E .c √ p H (1 -p H ) 2k * H (1-ε) ≤ π S (k H + 1) λ 1 -(1 -p H ) k * H 2 + (1 -λ) 1 -(1 -p H ) k * H + (π H (k H + 1) -π S (k H + 1)).
This may be rewritten as:

π S (k H ) ≤ ρ1 (p H )π S (k H + 1) + ρ2 (p H )(π H (k H + 1) -π S (k H + 1)) (A.13) with ρ1 (p H ) := (1 -p H ) 2εk * H (1 -p H ) k * E c √ p H λ 1 -(1 -p H ) k * H 2 + (1 -λ) 1 -(1 -p H ) k * H λ(1 -p H ) 2k * H and ρ2 (p H ) := 1 λ(1 -p H ) k * E .c √ p H (1 -p H ) 2k * H (1-ε) .
Now, we claim that, for p H small enough, ρ1 (p H ) ≤ ρ1 where ρ1 < 1 does not depend on p H . Indeed,

ρ1 (p H ) = (1 -p H ) 2εk * H (1 -p H ) k * E c √ p H λ 1 -(1 -p H ) k * H 2 + (1 -λ) 1 -(1 -p H ) k * H λ(1 -p H ) 2k * H = (1 -p H ) 2εk * H (1 -p H ) k * E c √ p H = 1 (1 -p H ) k * E .c √ p H 1 1 + λ 2ε
where the penultimate equality holds by Equation (A.2) while the last one holds by Equation (A.3).

Now

, 1 (1 -p H ) k * E c √ p H
converges from above to 1 as p H vanishes (recall by Lemma A.5 that k * E is a constant which does not depend on p H ), thus, the above term converges from above to 1 1+λ 2ε < 1 as p H vanishes. So, for p H small enough, ρ1 (p H ) ≤ ρ1 where ρ1 < 1 does not depend on p H . A similar logic shows that for p H small enough, ρ2 (p H ) ≤ ρ2 where ρ2 is a positive number (potentially greater than 1). Indeed, using Equation (A.3), we have

ρ2 (p H ) = 1 λ(1 -p H ) k * E .c √ p H (1 -p H ) 2k * H (1-ε) = 1 λ(1 -p H ) k * E .c √ p H λ H +λ E 2λ H +λ E 2(1-ε) which converges to 1 λ 1 1+λ 2(1-ε)
as p H vanishes. Thus, from inequality (A.13) we get that for p H small enough,

π S (k H ) ≤ ρ1 π S (k H + 1) + ρ2 (π H (k H + 1) -π S (k H + 1))
Now, by Lemma A.5, for any k H ,

π H (k H + 1) -π S (k H + 1) = k E / ∈S π(k H + 1, k E ) ≤ ∞ k H =0 k E / ∈S π(k H , k E ) ≤ 3 + 1/ √ p H 1 -ρ ρ1/ √ p H 1 -ρ := φ(p H ) with ρ ∈ (0, 1). Hence, for k H ≤ k * H (1 -ε), we obtain π S (k H ) ≤ ρ1 π S (k H + 1) + ρ2 φ(p H ) An inductive argument yields π S (k * H (1 -ε) -i) ≤ ρi 1 π S (k * H (1 -ε)) + φ(p H )ρ 2 1 -ρi 1 1 -ρ1 . (A.14)
Completion of the proof of Proposition A.6. We fix δ > 0 and claim that

π H k H : k H 1/(-ln(1 -p H )) ≤ ln (1 + λ) -δ → 0 which is equivalent to showing that π H k H : k H ≤ 1 p H ln (1 + λ) - 1 p H δ → 0.
Pick p H and ε small enough so that 1

p H ln (1 + λ) -1 p H δ ≤ k * H (1 -ε) -1/ √ p H . Clearly, for our purpose, it is enough to show that π H {k H ≤ k * H (1 -ε) -1/ √ p H } → 0
as p H vanishes. In order to see this, observe that

π H {k H ≤ k * H (1 -ε) -1/ √ p H } = k * H (1-ε) i=1/ √ p H π H (k * H (1 -ε) -i) = k * H (1-ε) i=1/ √ p H [π H (k * H (1 -ε) -i) -π S (k * H (1 -ε) -i)] + k * H (1-ε) i=1/ √ p H π S (k * H (1 -ε) -i) ≤ ∞ k H =0 k E / ∈S π(k H , k E ) + k * H (1-ε) i=1/ √ p H π S (k * H (1 -ε) -i) ≤ φ(p H ) + k * H (1-ε) i=1/ √ p H π S (k * H (1 -ε) -i) ≤ φ(p H ) + k * H (1-ε) i=1/ √ p H ρi 1 π S (k * H (1 -ε)) + k * H (1-ε) i=0 φ(p H )ρ 2 1 -ρi 1 1 -ρ1 ≤ φ(p H ) + ∞ i=1/ √ p H ρi 1 + k * H (1-ε) i=0 φ(p H )ρ 2 1 -ρi 1 1 -ρ1 ≤ φ(p H ) + ρ1/ √ p H 1 1 -ρ1 + k * H (1 -ε)φ(p H ) ρ2 1 -ρ1 → 0
where the second inequality comes from Lemma A.5, the third from the Lemma A.7 and the convergence result holds since

* H (1 + ε)p H + z = ln (1 + λ) (1 + ε) + z where z ≥ 1 is an integer yet to be specified. Note that E [K H (p H )p H 1{K H (p H )p H ≥ M }] = p H ∞ i=z/p H π H (k * H (1 + ε) + i) [k * H (1 + ε) + i] ≤ p H ∞ i=z π H (k * H (1 + ε) + i) [k * H (1 + ε) + i] = ∞ i=z π H (k * H (1 + ε) + i) ln (1 + λ) (1 + ε) +p H ∞ i=z π H (k * H (1 + ε) + i) i ≤ ln (1 + λ) (1 + ε) ∞ i=z ρ i π H (k * H (1 + ε)) +p H ∞ i=z ρ i π H (k * H (1 + ε)) i ≤ ln (1 + λ) (1 + ε) ∞ i=z ρ i + ∞ i=z ρ i i ≤ ln (1 + λ) (1 + ε) ρ z 1 -ρ + zρ z + ρ z (1 -ρ) 2
where the second inequality uses (A.5) while the last inequality uses (A.12). Since ρ ∈ (0, 1), the above term is smaller than δ when z is large enough and so when M is large enough.

Hence, as stated in (A.15) we obtain

lim p H →0 E [p H K H (p H )] = ln(1 + λ).
Now, by Little's law we get that:

lim p H →0 p H W H (U npaired) = lim p H →0 p H E [K H (p H )] λ.n = lim p H →0 E [p H K H (p H )] λ.n = ln(1 + λ) λ.n .
Waiting time of easy-to-match patients. First, we prove that, at the invariant distribution, as p H vanishes, the number of easy-to-match patients is concentrated around the constant k * E as defined in Lemma A.5. This indeed comes from that lemma and parallels Proposition A.1 but now for easy-to-match patients.

Proposition A.8. Fix any δ > 0,

π E k E : k E 1/(-ln(1 -p H )) ≥ k * E 1/(-ln(1 -p H )) + δ → 0 as p H vanishes.
Proof. Fix any δ > 0 and let p H > 0 be small enough so that √ p H ≤ δ. We know that

π E k E : k E 1/(-ln(1 -p H )) ≥ k * E 1/(-ln(1 -p H )) + δ ≤ π E k E : k E 1/(-ln(1 -p H )) ≥ k * E 1/(-ln(1 -p H )) + √ p H = π E k E : k E ≥ k * E + √ p H -ln(1 -p H ) ≤ 3 + √ p H -ln(1-p H ) (1 -ρ) 2 ρ √ p H -ln(1-p H ) → 0 as p H vanishes
where the first inequality is ensured by our choice of p H while the last inequality is by Lemma A.5 and the convergence result holds since ρ ∈ (0, 1) (again by Lemma A.5)

E [K E (p H )p H 1{K E (p H )p H ≥ M }] = p H ∞ i=z/p H π E (k * E + i) [k * E + i] ≤ p H ∞ i=z π E (k * E + i) [k * E + i] ≤ k * E ∞ i=z π E (k * E + i) + ∞ i=z iπ E (k * E + i) ≤ k * E ρz 1 -ρ 3 + z 1 - ρ + ∞ i=z iπ E (k * E + i) (A.16)
where the last inequality comes from (A.9). Moreover, we have:

∞ i=z iπ E (k * E + i) = ∞ i=z iπ S(k * E +i) (k * E + i) + ∞ i=z i[π E (k * E + i) -π S(k * E +i) (k * E + i)] ≤ ∞ i=z iπ S(k * E +i) (k * E + i) + ∞ i=z i ρ ln(2) p H +k * E +i 1 -ρ ≤ ∞ i=z iπ S(k * E +i) (k * E + i) + ρk * E ∞ i=z iρ i 1 - ρ ≤ ∞ i=z iρ i π S(k * E ) (k * E ) + ρk * E ∞ i=z i 2 ρi + ρk * E ∞ i=z iρ i 1 - ρ ≤ ∞ i=z iρ i + ∞ i=z i 2 ρi + ∞ i=z iρ i 1 - ρ ≤ 2 1 - ρ ∞ i=z iρ i + ∞ i=z i 2 ρi ≤ 2(1 + z)ρ z (1 -ρ) 3 + ∞ i=z i 2 ρi (A.17)
where the first inequality uses (A.7). The second uses ρ ≤ ρ ≤ 1. The third uses (A.8). The fourth and the fifth use the fact that π S(k * E ) (k * E ) and ρ are smaller than one. The last inequality comes from (A.12). Finally, we have:

∞ i=z i 2 ρi = ρ ∞ i=z i 2 ρi-1 = ρ d dρ ∞ i=z iρ i = ρ d dρ z ρz + (1 -z)ρ z+1 (1 -ρ) 2 = ρ (1 -ρ) z 2 ρz-1 + (1 -z)(1 + z)ρ z + 2 z ρz + (1 -z)ρ z+1 (1 -ρ) 3 ≤ ρ z 2 ρz-1 + (1 + 3z)ρ z + 2ρ z+1 (1 -ρ) 3 ≤ ρ z 2 ρz-1 + (1 + 3z)ρ z-1 + 2ρ z-1 (1 -ρ) 3 = (3 + 3z + z 2 )ρ z (1 -ρ) 3 (A.18)
where the third equality comes from (A.11) and the last inequality uses the fact that ρ is smaller than one.

Combining (A.16), (A.17) and (A.18) we obtain:

E [K E (p H )p H 1{K E (p H )p H ≥ M }] ≤ (3 + z)k * E (1 -ρ) 2 + (5 + 5z + z 2 ) (1 -ρ) 3 ρz .
Since ρ ∈ (0, 1), the above term is smaller than δ when z is large enough and so when M is large enough. Thus, the collection {K E (p H )p H } is uniformly integrable.

Again, this together with Proposition A.8 imply (e.g., [START_REF] Williams | Probability with martingales[END_REF] that

lim p H →0 E [p H K E (p H )] ≤ lim p H →0 p H k * E = 0
Then, by Little's law we get that:

lim p H →0 p H W E (U npaired) = lim p H →0 p H E [K E (p H )] (1 -λ).n = 0.
B Other Proofs

p H →0 W(P airwise) W(U npaired) =    ln(2λ) ln(1+λ) • 1 p H if λ ≥ 1 2 ln( 1-λ 1-2λ ) ln(1+λ) • 1 p E if λ < 1 2 B.
2 Proof of Theorem 2.6 and Remark 2.7

The following result implies the statements in Theorem 2.6 as well as in Remark 2.7.

Proposition B.1. Fix a matching algorithm ALG inducing a stochastic process with an invariant distribution. (1) We must have

lim p H →0 sup W(U npaired) W(ALG) ≤ 2 ln (1 + λ) λ .
(2) Assume that lim p H →0 p H W E (ALG) = 0. Then,

lim p H →0 sup W(U npaired) W(ALG) ≤ (1 + λ) ln (1 + λ) λ .
Let us denote the size of the pool by k. In the sequel, W(ALG) is the random variable describing the average waiting time of an arriving patient. Note that a necessary condition for a patient to be matched is that he is compatible with a donor in the pool upon arriving or, in case this does not occur, he is compatible with a donor in the future. In the former case, his waiting time is simply 0 while in the latter case, by the Poisson thinning property, the expected waiting time is 1 np T if the patient is of type T ∈ {H, E}. A.4 Hence, we obtain

E W(ALG) k = k ≥ λ(1 -p H ) k 1 np H + (1 -λ) (1 -p E ) k 1 np E ≥ λ (1 -kp H ) 1 np H + (1 -λ) (1 -kp E ) 1 np E = λ np H + 1 -λ np E -k 1 n .
A .3 Theorem 1 enunciates the average waiting time for hard-to-match patients while Lemma 4 proposes an upper bound for the waiting time of easy-to-match patients. From this Lemma we get that limp H →0 pH WE(P airwise) = 0.

A .4 The argument below works for any pE ≤ 1.

Thus, using the fact that, by Little's law, W(ALG) =

E[ k]

n , we have

W(ALG) = E E W(ALG) k = k ≥ λ np H + 1 -λ np E - 1 n E k = λ np H + 1 -λ np E -W(ALG).
This gives us

W(ALG) ≥ λ 2np H + 1 -λ 2np E . (A.20)
Now, we are in a position to prove the point (1) of the proposition. Indeed,

lim p H →0 sup W(U npaired) W(ALG) = lim p H →0 p H W(U npaired) lim p H →0 inf p H W(ALG) ≤ ln(1+λ) n λ 2n = 2 ln (1 + λ) λ .
where the inequality holds by Proposition 2.4 and together with Equation (A.20). Now, to show point (2) of the proposition, further note that using a similar logic one can show that

W H (ALG) = E E WH (ALG) k = k ≥ λ np H - 1 n E k = λ np H -W(ALG) = λ np H -λW H (ALG) -(1 -λ)W E (ALG)
(where WH (ALG) is the random variable describing the average waiting time of an arriving hardto-match patient) which yields

(1 + λ)W H (ALG) ≥ λ np H -(1 -λ)W E (ALG)
Now, under the assumption that W E (ALG)p H goes to 0 when p H vanishes, obtain that

lim p H →0 p H W(ALG) = lim p H →0 p H W H (ALG) ≥ λ n(1 + λ) . Hence, lim p H →0 sup W(U npaired) W(ALG) ≤ ln(1+λ) n λ n(1+λ) = (1 + λ) ln (1 + λ) λ .
We now complete the proof of Theorem 2.6.

B.4 Existence of Stationary Distribution

We now prove that the Markov chain induced by the Unpaired algorithm has a unique stationary distribution.

Proposition B.2. The transition matrix Q has a unique stationary distribution.

Proof. As in Ashlagi et al. (2019b) we use the following lemma from [START_REF] Meyn | Stability of Markovian processes III: Foster-Lyapunov criteria for continuous-time processes[END_REF] which is especially useful in proving our proposition.

Lemma B.3 ( [START_REF] Meyn | Stability of Markovian processes III: Foster-Lyapunov criteria for continuous-time processes[END_REF]). Suppose that X t is an irreducible continuous time Markov It is clear that our Markov chain is irreducible, so our proof will focus on finding a suitable set C, functions V and w, and constants c, and b.

C The Omniscient Solution in the Counterfactual Analysis

This appendix explains how to formulate the "omniscient" solution in the counterfactual analysis as an integer linear programming (ILP) problem. The objective is to minimize the sum of the (censored) waiting times of all patients, regardless of transplant status.

We consider two version of the Omniscient solution-one uses deceased donor, or DDL kidneys, and the other does not. Recall that Unpaired with DDL uses DDL kidneys under two constraints. Let X ij ∈ {0, 1}, which is equal to 1 if d i donates a kidney to p j . For any donor kidney or patient i, we denote by a(i) and e(i) the arrival and the exit dates of i, respectively. For any two dates t and t , t < t means that date t is prior to date t and t -t is the number of days between any two dates (which can be negative if date t is after date t). For j ∈ D d , a(j) is the date of arrival of the DDL kidney and the exit date is e(j) = a(j) since a DDL kidney is only available for 24 hours.

Let T i ij be the number of days donor i waits if she gives to patient j and T j ij be the number of day patient j waits if he receives from donor i. Let T d := {a(j) : j ∈ D d } be the set of dates at which at least one DDL kidney arrives. Define T ij = max{0, a(i) -a(j)}, the number of days patient p j has to wait to receive a kidney from donor d i . Note that T ij = 0 if d i arrives before p j . For pair j, let T e j = e(j) -a(j) be the number of days between its arrival and departure dates. Under the assumption of no exit, T e j = T -a(j). Finally, let G be the compatibility matrix between donors and patients so that G ij = 1 if donor i ∈ D is compatible with patient j ∈ P. We also define M = |P| × |D |.

The omniscient solution, when it uses DDL kidneys, solves the following ILP problem: A.6

A .6 The total waiting time of all patients is j∈P:e(i)<e(j)

X ij ≤ j∈D X ji ∀i ∈ P :(DP i ) j∈P X ij × (T i ij + 1) +   1 - j∈P X ij   × ( T + 1) ≤ j∈D d X ji × T i ji +   1 - j∈D d X ji   × ( T + 2) ∀i ∈ P :(DD i ) j∈D X ji × T i ji +   1 - j∈D X ji   × ( T + 1) ≤ j∈P d X ij × (T i ij + 1) +   1 - j∈P d X ij   × ( T + 2)
The constraints are:

• C ij : Compatibility constraints. It takes into account that if a DDL kidney i ∈ D d gives to a patient j ∈ P, then this patient must arrive before the departure of the DDL kidney.

• F p j : Feasibility constraints for patients. Each patient can receive at most one kidney.

• F d i : Feasibility constraints for donors. Each donor kidney can give to at most one patient.

• E i : Exit constraints. A living donor leaves with her patient but stays if her patient has received a kidney. Hence, if p i does not receive a kidney, d i leaves with p i and thus cannot donate to any patient who arrives after their exit date. When we impose the no-exit assumption, this constraint is never binding.

• DP i : DDL kidney constraints for patients. A patient i can receive from a DDL kidney only if: i) her paired donor has donated to another patient, and ii) this donation must occur before patient i receives a DDL kidney. A.7 • DP i : DDL kidney constraints for donors. A DDL kidney i can give to a dummy DDL patient only if: i) her paired dummy patient receives a living donor kidney, and ii) this donation must occur after her paired patient received from a living donor.

When DDL kidneys are not used in the Omniscient algorithm, the constraints in DP i and DD i are ignored.

have higher risk of graft failure than x% of recovered deceased-donor kidneys (i.e., longer function than (100 -x)% of recovered deceased-donor kidneys) in the U.S. in a reference year (for which we choose 2017). The expected risk of graft failure is measured by the Kidney Donor Risk Index (KDRI) of the donor. Below we review the calculation of the KDRI; we then explain how it is applied to our French data; in particular, how we deal with missing values; and, finally, we describe how the KDPI is obtained from the KDRI.

Calculation of Kidney Donor Risk Index (KDRI).

                                
We apply this formula to our data and obtain a value of the KDRI for each deceased-donor kidney recovered in France during our sample period. [START_REF] Lehner | Assessment of the kidney donor profile index in a European cohort[END_REF] and Calvillo-Arbizu et al.

(2018) follow the same methodology, using German and Spanish data, respectively. They confirm that the above formula, despite being estimated from a U.S. dataset, provides an accurate prediction of graft failure in these two populations.

Missing values. Donor ethnicity is not recorded in our data. We assume that all deceased donors are Caucasian as in [START_REF] Lehner | Assessment of the kidney donor profile index in a European cohort[END_REF][START_REF] Calvillo-Arbizu | Does the Kidney Donor Profile Index (KDPI) predict graft and patient survival in a Spanish population?[END_REF]. Therefore, 1(African American) = 0 for all donors. For other variables, if there is a missing value, we set the variable at its sample mean in the calculation of the KDRI, as recommended by Organ Pro- curement and Transplant Network (2019). A.8 For instance, if History of Hypertension is missing for a donor, we replace the dummy variable 1(History of Hypertension) by the proportion of donors .8 The same imputation is also used by [START_REF] Lehner | Assessment of the kidney donor profile index in a European cohort[END_REF][START_REF] Calvillo-Arbizu | Does the Kidney Donor Profile Index (KDPI) predict graft and patient survival in a Spanish population?[END_REF]. 2), is copied from columns (4) and ( 5) of Table 2. Columns (3)-( 7) have the same simulations as in Table 2 but each has the following modification: columns (3) and (4) have the 21 hypersensitive patients opting out of entering P; columns (5) and ( 6) have the 1 pair with a hypersensitized patient and an AB donor opting out of entering P; columns (7) and ( 8) have the 12 patients with a PRA above 0.98 opting out of entering P. 2), is copied from columns (4) and ( 5) of Table 2. Columns (3)-( 7) have the same simulations as in Table 2 but each has the following modification: columns (3) and ( 4) allows each donor in D to renege with probability 0.17% per day; column (5) avoids the possibility of reneging by letting a donor immediately donate a kidney to the DDL whenever her paired patient receives a kidney; column (6) gives back a living O donor to the DDL whenever a DDL O donor is used by Unpaired with DDL, as defined in Definition 3.5; in column (7), a qualified DDL kidney for any patient must have a KDPI below the median LKDPI among all living donors (in both the KEP sample and the desensitization sample).

Figure 1 :

 1 Figure 1: Waiting Time under Each Algorithm and the Fraction of Hard-to-match Patients (λ)

  Figure 2 shows a similar bimodal pattern for the patients in the French kidney exchange program (KEP) that are used in our counterfactual analyses in Section 3. Adding blood type compatibility still induces a bimodal distribution for the probability of overall biological compatibility in our data (see Figure E.1 in Appendix E).

Figure 2 :

 2 Figure 2: Histogram of PRA (Panel Reactive Antibodies) Values among the French KEP Patients Notes: Calculated by the authors from the 78 patient-donor pairs who ever participated in the French kidney exchange program (KEP) during December 2013 to February 2018. The higher a PRA, the more difficult it is for a patient to find a compatible donor. See Table1for more summary statistics on these patients.

  the KEP. Many of the patients have blood type O (56 percent) or are hypersensitized (27 percent), consistent with the hypothesis that a large fraction of them are hard to match. The most common blood type among the donors is A (51 percent), while only 23 percent of them have type O blood.

  Unpaired favors those in D and breaks any remaining ties by their waiting time; when it chooses among multiple patients, hard-to-match patients enjoy the highest priority, and any remaining ties are broken first by whether a patient is in P and then by their waiting time. Pairwise and Chain also use this tie-breaking rule, although Pairwise involves neither P nor D and Chain has no P.

  Time horizon. We measure time in days. Due to the above specifications on arrivals, each simulation starts on August 25, 2013 (110 days before the first KEP match run) and ends in February 23, 2018 (the last KEP match run in our sample), a total of 1644 days. We independently draw 1000 sets of arrival and exit dates and use the same draws to calculate outcomes of all algorithms;

  23 Under either Unpaired or Unpaired with DDL, an imbalance can arise due to donor reneging: whenever a donor in D reneges, the difference between the number of waiting patients and the number of available donors increases by one. The simulation results (column 5, TableE.4) are slightly better than those in the baseline (column 2), even though the waiting time of unpaired donors is reduced to zero. Second, Unpaired with DDL can be modified to keep a balance between the DDL and the exchange. For instance, one may be concerned that Unpaired with DDL can reduce the total supply of O donors to the DDL. Because O donors are often highly demanded, it may be unfair to DDL patients if Unpaired with DDL takes too many O donors from the DDL. In this case, one may use the following version of Unpaired with DDL. Definition 3.5 (Unpaired with DDL & Balancing of O Donors). In addition to the Unpaired procedure as in Definition 2.3, this algorithm proceeds differently depending on the blood type of a DDL donor: (i) When a qualified DDL non-O kidney arrives, match the kidney to a compatible patient in P (if any), while prioritizing patients by waiting time. Whenever a non-O DDL kidney is taken by a patient, the donor in D who has the longest waiting time gives a kidney to some DDL patient. (ii) When a qualified DDL O kidney arrives and if there is at least one O donor in D, match the kidney to a compatible patient in P, while prioritizing patients by waiting time. The O donor with the longest waiting time donates a kidney to the DDL. This version of Unpaired with DDL keeps constant the supply of O donors to the DDL. Column (6) of Table E.4 shows the results which are almost identical to the baseline (column 2).

  .21) and the waiting time under unpaired derived in Proposition 2.4, we immediately get that lim

  chain with the transition matrix Q over states S = N × N. If there exist a nonnegative function V on S, a function w ≥ 1 on S, a finite set C ⊂ S, and constants c > 0 and b ∈ R such that, for alli = (k E , k H ) ∈ S: j∈S Q(i, j)V (j) ≤ -cw(i) + b.I C (i),where I C denotes the indicator function of the set C, then the Markov chain X is ergodic.

First, a patient

  can receive a DDL kidney only if the paired donor has already donated to another patient. Second, if we use a DDL kidney, we need to immediately give back a living donor kidney to the DDL. We will impose the same constraints in Omniscient when it uses DDL kidneys. Let P = P ∪ P d where P is the set of living patients and P D is the set of dummy patients attached to each DDL kidney. Let D = D ∪ D d denote the set of all kidneys to be donated, where D is the set of living donor kidneys and D d is the set of DDL kidneys. Below, we sometimes refer to a kidney in D as a donor, although a deceased donor may donate two kidneys. By definition, |D d | = |P d |.

  , j ∈ P :(C ij ) X ij ≤ G ij × 1 {e(j)≥a(i)} × 1 {(i∈D )∨(e(i)≥a(j

  The KDRI, developed by Rao et al. (2009), combines 10 donor factors to provide an estimated risk of graft failure after a transplant of a deceased donor kidney. The donor factors include the donor's age, height, weight, ethnicity, serum creatinine, comorbidities (diabetes, hepatitis C virus-HCV, and hypertension), cause of death being cebrovascular accident (CVA) or not, and DCD status (being 1 for a donation after cardiac death or 0 otherwise). The association between these variables and graft survival is estimated by a multivariate Cox proportional hazard model with graft outcomes from nearly 70,000 adults in the U.S. from 1995 to 2005. The estimated coefficients and the functional-form assumption lead to the following formula for the KDRI: × (age -40) -0.0194 × (age -18) × 1(age < 18) +0.0107 × (age -50) × 1(age > 50) -0.0464 × height-× 1(African American) + 0.1260 × 1(History of Hypertension) +0.1300 × 1(History of Diabetes) +0.0881 × 1(Cause of Death = CVA) + 0.2200 × (Creatinine -1) -0.2090 × (Creatinine -1.5) × 1(Creatinine > 1.5mg/dL) +0.2400 × 1(HCV positive) + 0.1330 × 1(DCD)

Figure E. 1 :

 1 Figure E.1: Distribution of Patients by the Fraction of Compatible Donors in the French KEP Notes: The histogram is calculated among the 78 patient-donor pairs who ever participated in the French KEP during December 2013 to February 2018. See Table1for more details about these pairs. A patient is compatible with a donor if they are both

Table 1 :

 1 Kidney Patients and Donors: Summary Statistics

		KEP Pairs Patient Donor	Desensitization Pairs Patient Donor	DDL Kidneys e
		(1)	(2)	(3)	(4)	(5)
	# of observations	78	78	508	508	13,036
	Patient grafted/Donor donated	69% b	35% b	100%	100%	100%
	Age a	46.1	48.1	45.9	45.8	54.9
		(12.9)	(10.5)	(14.4)	(11.8)	(18.5)
	Female	47% c	49% d	37%	62%	43%
	Blood type
	A	31%	51%	23%	49%	44%
	B	10%	18%	16%	16%	10%
	O	56%	23%	59%	29%	43%
	AB	3%	8%	2%	6%	4%
	Sensitization Status f
	Hypersensitized	27%		24%
	Sensitized	50%		47%
	Non-sensitized	23%		29%
	ABO Compatible within the pair	42%		44%
	HLA Compatible within the pair	32%		48%

Notes: This table presents characteristics of kidney patients and donors in France from December 2013 to February 2018. Columns (1) and (

2

) are on the 78 patient-donor pairs who ever participated in the KEP. Columns (3) and (

4

) are on pairs who did desensitization. Column (5) are all the DDL kidneys in the sample period. a An age in the table is calculated on January 1, 2012, except for a DDL kidney (calculated on its retrieval day). b Patients in the KEP can receive a transplant outside the KEP (e.g., from DDL or desensitization), and a donor can donate outside the KEP (i.e., by desensitization). There are 12 pairs (15.4%) engaged in an exchange in the KEP in the sample. c This percentage is calculated among the 70 patients with non-missing gender information. d This percentage is calculated among the 68 donors in the KEP with non-missing gender information. e A DDL donor may provide two kidneys, and the statistics in column (

5

) are calculated at the individual kidney level. f A patient's sensitization status measures how likely it is for her to find a deceased or living donor kidney that is compatible. The exact definition is provided in Appendix D.1.

  Table 2 are in line with our theoretical findings in Section 2.2. Waiting time under Unpaired is substantially lower than Pairwise and Chain (cf. Theorem 2.5 and Theorem 2.8). Although Omniscient achieves the lowest waiting time, it does not significantly

	18

Table 2 :

 2 Performance of Different Algorithms in the Baseline Simulations There are in total 78 incompatible pairs, among which 21 pairs have a hypersensitized patient and 44 have an O patient.

		Pairwise (2-way) exchange exchanges exchange 2-way & Chain & 3-way Pairwise	Unpaired	Unpaired Omniscient w/ DDL	Omniscient w/ DDL
		(1)	(2)	(3)	(4)	(5)	(6)	(7)
	Average waiting time (days)
	All patients (censored)	732	695	701	440	143	425	136
	hypersensitized patients	745	750	751	591	262	562	297
	O patients	883	831	863	646	174	631	150
	Patients receiving transplant	246	267	223	180	108	132	97
	hypersensitized patients	266	321	291	299	174	243	213
	O patients	320	333	357	375	152	266	123
	Transplants
	% patients receiving transplant	29%	34%	31%	57%	87%	58%	88%
	hypersensitized patients	16%	15%	15%	32%	72%	38%	74%
	O patients	15%	22%	17%	40%	87%	40%	89%
	# deceased donor kidneys used	0	0	1	0	29	0	25
	Patients going through P
	Total number	-	-	-	25	31	28	34
	hypersensitized patients	-	-	-	11	14	12	14
	O patients	-	-	-	20	22	23	25
	Waiting time of patients in P
	Median	-	-	-	220	2	471	73
	hypersensitized patients	-	-	-	506	19	476	136
	O patients	-	-	-	183	2	526	72
	Donors going through D
	Total number	-	-	4	23	33	28	32
	AB donors	-	-	1	3	5	4	4
	Waiting time of donors in D
	Median	-	-	89	305	8	471	66
	AB donors	-	-	706	806	20	816	31
	Notes:

Table 3 :

 3 Performance of the Algorithms in Large Markets-French KEP & Desensitization Pairs There are 586 incompatible pairs (including all the KEP and desensitization pairs), among which 141 pairs have a hypersensitized patient and 342 have an O patient. The statistics reported are from the 1000 sets of simulations. Except the market size, other configurations in the simulations are the same as in Table 2. For more details, please see the notes of Table 2. A more detailed version including statistics on hypersensitized and O patients as well as AB donors is Table E.1 in Appendix E.

		Pairwise (2-way) exchange exchanges exchange 2-way & Chain & 3-way Pairwise	Unpaired	Unpaired Omniscient w/ DDL	Omniscient w/ DDL
		(1)	(2)	(3)	(4)	(5)	(6)	(7)
	Average waiting time (days)
	All patients (censored)	470	413	461	269	87	254	53
	Patients receiving transplant	142	167	135	106	75	91	46
	Transplants
	% patients receiving transplant	44%	53%	45%	67%	92%	69%	97%
	# deceased donor kidneys used	0	0	1	0	174	0	172
	Patients going through P
	Total number	-	-	-	191	193	230	225
	Waiting time of patients in P
	Median	-	-	-	176	3	311	29
	Donors going through D
	Total number	-	-	9	190	305	232	286
	Waiting time of donors in D
	Median	-	-	75	196	22	305	40
	Notes:

Table 4 :

 4 Performance of the Algorithms in Large Markets-APKD and NKR

			APKD			NKR
		Pairwise Unpaired Omniscient	Pairwise Unpaired Omniscient
		(1)	(2)	(3)	(4)	(5)	(6)
	Number of pairs
	All patients	781	781	781	2320	2320	2320
	hypersensitized patients	315	315	315	836	836	836
	O patients	477	477	477	1309	1309	1309
	Average waiting time (days)
	All patients (censored)	493	294	273	404	248	229
	Patients receiving transplant	153	127	102	122	102	62
	Transplants
	% patients receiving transplant	46%	68%	70%	56%	72%	74%
	# deceased donor kidneys used	0	0	0	0	0	0
	Patients going through P
	Total number	-	260	300	-	706	833
	Waiting time of patients in P
	Median	-	90	312	-	69	266
	Donors going through D
	Total number	-	233	305	-	796	1011
	Waiting time of donors in D
	Median	-	182	346	-	90	252

  Table E.3 of Appendix E, relativeto the baseline of no opting out, the overall waiting time significantly increases under Unpaired from 440 (column 1) to 589 days (column 3), while more than doubling under Unpaired with DDL, from 143 (column 2) to 340 days (column 4). The drop in transplant rate is also noticeable-from 57 percent to 44 percent under Unpaired, 87 percent to 68 percent under Unpaired with DDL. The reduction is larger among hypersensitized patients-24 percentage points underUnpaired and 64 percentage points under Unpaired with DDL.

  For Unpaired, relative to the baseline (column 1), there is hardly any effect of reneging on transplant rate or waiting time (column 3). If anything, reneging reduces the waiting time of donors in D: the median reduces from 305 to 143. We observe the same comparison for Unpaired with DDL (column 2 vs. column 4). The possibility of reneging decreases the waiting time in D without affecting much either waiting time or transplant rate.Two Modified Versions of Unpaired with DDL. Unpaired with DDL can be further modified to address additional considerations that might emerge in practice. These modifications may make Unpaired with DDL more acceptable in practice. Below we consider two examples.First, the following version is designed to remove any possibility of renege for donors in D.Definition 3.4 (Unpaired with DDL & Empty D). In addition to the Unpaired procedure as in Definition 2.3, whenever a qualified DDL kidney arrives, match the kidney to a compatible patient in P (if any), while prioritizing patients by waiting time. Moreover, if a donor cannot donate to any patient when her paired patient receives a living donor kidney, the donor immediately donates to the DDL.

. In our simulation, there are on average 32 donors going through D, among them 1.38, or 4.3 percent, renege, higher than what is documented by Cowan et al. (2017), 1.5 percent, in a dataset from NKR in the U.S. The simulation results are reported in

Table E.4 of Appendix E.

  E +1/ √ p H +k H +1 ≤ k * H and k H +1 ≤ k * H .Since the second inequality holds if the first one holds, we just provide the argument for the first one. Since

	k * H goes to ln (1 + λ)/ p H as p H vanishes, we must have εk * H ≥ k * E + 1/	√ p H + 1 for p H small enough

*

  Here, we complete the proof of Proposition 2.4 by providing the expressions of p H W H (U npaired)and p H W E (U npaired) when p H vanishes.Waiting time of hard-to-match patients. Given p H , let us denote by K H (p H ) the random variable corresponding to the number of hard-to-match patients at the invariant distribution π H . Proposition A.1 and A.6 imply that, as p H vanishes, K H (p H )p H converges in probability to constant ln (1 + λ). One can show that {K H (p H )p H } is uniformly integrable, i.e., for a given δ > 0, there if and only if K H (p H )p H ≥ M . This implies (see for instance[START_REF] Williams | Probability with martingales[END_REF] that To see that the collection {K H (p H )p H } is uniformly integrable, fix δ, ε > 0 and let M :=

	k	ρ ( √ √ p H 1 p lim p H →0	E [K H (p H )p H ] = ln (1 + λ) .	(A.15)

H ) 3 , with ρ ∈ (0, 1), goes to zero as p H vanishes.

A.4 Completion of the proof of Proposition 2.4

exists M < ∞ large enough such that E [K H (p H )p H 1{K H (p H )p H ≥ M }] ≤ δ

for all the random variables in our collection {K H (p H )} where 1{K H (p H )p H ≥ M } stands for the indicator function equal to 1

  We deduce from the Theorem 1 and Lemma 4 inAshlagi et al. (2019b) A.3 that

	B.1 Proof of Theorem 2.5
	lim p H →0	p H W(P airwise) =	  	ln(2λ) np H ln( 1-λ 2λ-1 ) np E	if λ ≥ 1 2 2 if λ < 1	(A.19)
	Using (A.19) and the average waiting time under unpaired derived in Proposition 2.4, we immediately
	get that
	lim

  Completion of the proof of Theorem 2.6. Using the point (2) of Proposition B.1, we obtain We know from the Proposition 1 inAshlagi et al. (2019b) that, when p E = 1A.5

	that	lim p H →0	sup	W(U npaired) W(Optimal)	≤ 2	ln (1 + λ) λ	.
	Indeed, assume that lim p H →0 sup W(U npaired) W(Optimal) > 2 ln(1+λ) λ	. By definition, of OPT, there exists a se-
	quence of matching algorithms {ALG n } n≥1 such that W(ALG n ) → W(OPT). Then, this means
	that for n large enough, W(Unpaired) W(ALGn) > 2 ln(1+λ) λ	, a contradiction with point (2) of the above propo-
	sition.
	B.3 Proof of Theorem 2.8

  Table1for more details about these pairs. A patient is compatible with a donor if they are both blood type and tissue type compatible.Notes: There are in total 78 incompatible pairs, among which 21 pairs have a hypersensitized patient and 44 have an O patient. The statistics reported are from the 1000 sets of simulations. The Unpaired algorithm is defined in Definition 2.3 and does not use DDL kidneys; Unpaired with DDL is defined in Definition 3.1 with additional restrictions on patients entering P and uses DDL kidneys. The baseline, columns (1) and (

	Patients going through P
	Total number	25	31	15	23	25	31	20	27
	hypersensitized patients	11	14	0	0	11	14	5	6
	O patients	20	22	15	20	20	22	18	20
	Waiting time of patients in P
	Median	220	2	408	1	221	2	208	2
	hypersensitized patients	506	19	0	0	509	19	406	3
	O patients	183	2	411	1	186	2	211	1
	Donors going through D
	Total number	23	33	18	23	23	33	19	27
	AB donors	3	5	3	5	3	5	3	5
	Waiting time of donors in D
	Median	305	8	292	1	306	8	296	2
	AB donors	806	20	805	1	805	20	804	2

  There are in total 78 incompatible pairs, among which 21 pairs have a hypersensitized patient and 44 have an O patient. The Unpaired algorithm is defined in Definition 2.3 and does not use DDL kidneys; the Unpaired with DDL algorithm is defined in Definition 3.1 and uses DDL kidneys. The baseline, columns (1) and (

	Patients going through P
	Total number	25	31	29	31	33	30	30
	hypersensitized patients	11	14	11	15	15	14	14
	O patients	20	22	23	23	23	22	22
	Waiting time of patients in P
	Median	220	2	250	3	2	5	6
	hypersensitized patients	506	19	517	22	16	37	49
	O patients	183	2	214	2	2	4	4
	Donors going through D
	Total number	23	33	21	33	0	33	33
	AB donors	3	5	3	5	0	5	5
	Waiting time of donors in D
	Median	305	8	143	5	0	14	21
	AB donors	806	20	287	14	0	26	33
	Notes:

The U.S. Medicare's dialysis cost in

was more than 1.2 percent of the entire federal budget. 2 Indeed, in the only legal kidney market in the world in Iran, there is a large supply (nearly 45% of kidney donors are paid living donors), which in turn has led to low transplant waiting times for kidney patients (less than one year). A drawback of the market is that it has almost completely crowded out family donations. See[START_REF] Akbarpour | Thickness and information in dynamic matching markets[END_REF] for a detailed analysis of the Iranian market for kidneys.

Lacking information on altruistic donors, we do not simulate the Chain algorithm in the last two large markets. In the first market, its transplant rate is 22 percentage points lower than Unpaired, while the waiting time is 192 days longer.

As we already mentioned, the waiting times of unpaired patients (after their donors' donation) and unpaired donors (after their patients' transplant) decrease with market size.

As inAshlagi et al. (2019b), we may assume that there are finitely many d ≥ 1 bridge or altruistic donors at any given time. The results will remain essentially the same.

Little's law states that the long-term average number of agents in a stationary system is equal to the long-term average effective arrival rate multiplied by the average time that an agent spends in the system.

Note that, unlike in[START_REF] Akbarpour | Thickness and information in dynamic matching markets[END_REF], our patients and donors do not depart. This makes our analysis less tedious, without creating any difference in the objective function. Our goal here is to minimize the total waiting time, whereas in a model with departures the goal is a mix of waiting time and deaths. With linear waiting cost and Poisson departures, Little's law implies that both of these objectives are minimized by minimizing the pool size.

The only exception is when there are no other donors in the system. Thus, it is possible to be in the state that there is only one easy-to-match patient and one donor in the system, but as our full analysis in Appendix A shows, this is exponentially unlikely.

For a new arriving easy-to-match patient the likelihood of being compatible to some donor in the system goes to 1 as pH vanishes. However, conditional on the small probability event that this patient does not get matched upon arriving, given the priority rule under Unpaired, he will have to wait for an arriving donor to be incompatible with all hard-to-match patients remaining in the system. Given that the number of hard-to-match patients in the system explodes, one may expect the conditional waiting time to be very long. However, at an intuitive level, the rate of arrival of such donors should be upper bounded by n(1 -pH ) k * which converges to a constant as pH vanishes. This suggests that the conditional waiting time does not explode. We make this precise in our argument in Appendix A.

To obtain this result, we show that for any algorithm ALG inducing a stochastic process with an invariant distribution we must have: limp H →0 pH W(ALG) ≥ λ 2n . This gives us a lower bound for the waiting time that can be achieved under the Optimal algorithm.

If there are finitely many bridge donors at each point in time, the same argument applies, and therefore Theorem 2.8 still holds, as mentioned in footnote 5.

In the U.S., in 2014, 4,761 patients died while waiting for a kidney transplant; another 3,668 patients became too sick to receive a kidney transplant. Source: National Kidney Donation (www.kidney.org).

The problem is similar to large market matching models (see, e.g.,[START_REF] Azevedo | A supply and demand framework for two-sided matching markets[END_REF][START_REF] Hatfield | Improving schools through school choice: A market design approach[END_REF][START_REF] Che | Efficiency and stability in large matching markets[END_REF] Tercieux, 2019). Some results hold only when the number of participants is large enough. It is difficult to answer "how large the market should be," but empirical analyses can help evaluate the relevance of such theoretical results in finite markets.

In the sample period, December 2013 to February 2018, the first match run happened in December 2013. There were only three match runs in each of the years 2014, 2015 and 2017 and four match-runs in 2016. Additionally, our data covers one match run in February 2018.

Compared with a compatible living donor transplant, on average, a blood-type incompatible transplant is $100,000 more expensive, and an HLA incompatible transplant is $180,000 more expensive[START_REF] Axelrod | An economic assessment of contemporary kidney transplant practice[END_REF].

In a recent survey,[START_REF] Scurt | Clinical outcomes after ABO-incompatible renal transplantation: a systematic review and meta-analysis[END_REF] conclude that blood-type incompatible transplants result in an excess of mortality and loss of kidney grafts compared to compatible transplants. The outcomes of HLA incompatible transplants are even worse[START_REF] Marfo | Desensitization protocols and their outcome[END_REF].

On any given day in our sample period, there are about 9, 000 patients waiting on the DDL. In our sample period, there are 389 deceased donors whose kidneys are offered to the DDL patients but discarded in the end due to either refusals or last-minute cancellations. For some of the deceased donors, we do not know how many kidneys are available for the DDL; in that case, we assume such a donor has only one kidney available.

For more details, see http://www.senat.fr/rap/l19-237/l19-2378.html.

We do not run Chain or Unpaired with DDL, because they would require information on altruistic or deceased donors in the U.S.

We note that Unpaired with DDL & Empty D is even closer to the algorithm described in Remark 3.2 than the Unpaired with DDL algorithm.

[START_REF] Flechner | The incorporation of an advanced donation program into kidney paired exchange: initial experience of the National Kidney Registry[END_REF] report 10 advanced donations within NKR from August 2011 to August 2014. Since then, ADP has expanded. As of April 27, 2020, there have been about 500 advanced donations. Half of these donations are from donors whose paired incompatible patient is in urgent need of a kidney (see NKR's quarterly report on paired kidney exchange for Q1 2020; available at https://www.kidneyregistry.org/pages/c6/nkr_quarterly_reports).

In the priority order, the patients with a voucher are right after former NKR donors in need of a kidney transplant and patients involved in real-time swap failures where the donor has donated but the patient did not receive a kidney; see[START_REF] Tenenbaum | Swaps and Chains and Vouchers, Oh My!: Evaluating How Saving More Lives Impacts the Equitable Allocation of Live Donor Kidneys[END_REF].

A.5 Note that, when pE = 1, an arriving easy-to-match patient is immediately matched by the bridge donor so that limp H →0 pH W(Chain) = limp H →0 pH λWH (Chain).

A.7 This constraint indeed captures the two elements. If patient i does not receive a DDL kidney, the right hand side of the inequality is equal to T + 2, and thus the inequality never binds. If patient i receives DDL kidney j but her paired donor has not donated to a patient, the inequality becomes T + 1 ≤ T i ji , which cannot be satisfied.

seminar participants for valuable comments. Combe is grateful for the support from the ERC Grant No. 682417, Frontiers in Design -Frontiers in Mechanism Design: Methodology and Applications. Hiller is grateful for the support from ANR grant PAIRED_KIDNEY_DONATION (ANR-17-CE36-0004-01) and Labex MME-DII (ANR11-LBX-0023-01). All errors remain our own. The views expressed herein are those of the authors and do not necessarily reflect the views of the National Bureau of Economic Research. NBER working papers are circulated for discussion and comment purposes. They have not been peer-

Recall that for a continuous Markov chain, j =i Q(i, j) = -Q(i, i). Hence, we must have j∈S

For any state i = (k E , k H ) ∈ S, we have:

Let λ H = λn and λ E = (1 -λ)n. Then the above is equal to: andc = 1 3 . Now take M such that (1 -p H ) M ≤ 1 3 and (1 -p E ) M ≤ 1 3 , and set

For any i = (k E , k H ) ∈ C, note that either k E ≥ M or k H ≥ M . Hence, we must have:

For any i = (k E , k H ) ∈ C, we have:

Thus, the Markov chain is ergodic, which means that it has a unique stationary distribution.

D Data on Patients and Donors

We use administrative data from the Agence de la Biomedecine (ABM) who is in charge of organ allocation in France. Our sample period is December 2013 to February 2018. The dataset contains information on all the donors (deceased and living) who have been retrieved, all the patients who have been transplanted, and all the patient-donor pairs having participated in the Kidney Exchange Program (KEP) in France. We focus on the patient-donor pairs having ever participated in the KEP, the patient-donor pairs who have gone through a desensitization procedure, and the deceased donors. For our simulations, we use three types of information:

(i) the compatibility between any patient and any donor in our data;

(ii) the quality of a kidney from any donor in the data for any patient who has participated in the KEP or for a patient who has gone through desensitization;

(iii) the arrival date of each deceased donor kidney, the transplant date of each patient-donor pair who has gone through a desensitization procedure, and the registration date and the exit date of each patient-donor pair who have ever participated in the KEP.

In the following, we detail how we construct the relevant variables.

D.2 Quality Measure for Deceased-Donor Kidneys

We use the Kidney Donor Profile Index (KDPI) as a quality measure for deceased-donor kidneys.

The KDPI, which lies in [0, 100], is a relative measure. A kidney with a KDPI of x% is expected to having a history of hypertension; if the information on a donor's serum creatinine is missing, we assume that this donor has a serum creatinine at the mean level of serum creatinine among all the deceased donors in our sample.

Calculation of Kidney Donor Profile Index (KDPI) from KDRI The KDPI is a mapping of the KDRI from a relative risk scale to a cumulative percentage scale (Organ Procurement and Transplant Network, 2019). The reference population used for this mapping is all deceased donors in the U.S. with a kidney recovered for the purpose of transplantation in the prior calendar year.

We use the year 2017 as the reference year. In other words, we use the OPTN mapping table 2018 to map a KDRI to a KDPI. A.9 The median value for the KDRI in our data is 1.3357. This corresponds to a KDPI equal to 78, meaning that 78 percent of the deceased-donor kidneys proposed in the U.S. are of a better quality than the median deceased-donor kidney in France. It is well-known that more kidneys, and thus some kidneys of a lower quality, are proposed to patients in France than in the U.S. This is also the case in other European countries, although at various degrees. A.10

D.3 Quality Measure for Living-donor Kidneys

We use the Living Kidney Donor Profile Index (LKDPI) as a quality measure for living-donor kidneys. The LKDPI is developed by [START_REF] Massie | A risk index for living donor kidney transplantation[END_REF] who use U.S. data to identify living donor characteristics associated with the risk of post-transplant graft failure. Importantly, the LKDPI is graft-specific, since it depends on characteristics of both the donor and the patient; by contrast, the KDPI is only donor-specific. We calculate an LKDPI for each incompatible patient-donor pair having ever participated in the KEP and for all desensitization pairs. The LKDPI is expressed on the same scale as the KDPI such that the two indices can be directly compared: if, for a given patient, the KDPI associated with a deceased-donor kidney is lower than the LKDPI associated with a living-donor kidney, the living-donor kidney has a higher expected graft failure risk.

Below we review the calculation of the LKDPI, explain how we deal with missing values, and describe how we assign an LKDPI to HLA incompatible pairs.

Calculation of the Living Kidney Donor Profile Index (LKDPI). The LKDPI, developed by [START_REF] Massie | A risk index for living donor kidney transplantation[END_REF], combines 12 donor and patient factors to provide an index of graft failure risk after a living donation. The factors include the donor's age, estimated glomerular filtration (eGFR), Body Mass Index (BMI), ethnicity, history of cigarette use, and systolic blood pressure (SBP). There are also pair-specific factors: donation from a male donor to a male recipient, number of HLA-B mismatches, number of HLA-DR mismatches, donor/recipient weight ratio (D/R WR), and blood-type incompatibility.

A .9 The table is available at https://optn.transplant.hrsa.gov/media/2150/kdpi_mapping_table.pdf; retrieved on October 5, 2019. A.10 Using German data, [START_REF] Lehner | Assessment of the kidney donor profile index in a European cohort[END_REF] conclude that 66 percent of the deceased-donor kidneys proposed in the U.S. are of a better quality than the median deceased-donor kidney in their data.

The association between these factors and graft survival is estimated in a multivariate Cox proportional hazard model with graft outcomes from 36, 025 living-donor kidney recipients in the U.S. during 2005-2013. The estimated coefficients and the functional-form assumption lead to the following formula for the LKDPI:

+22.34 × 1(African American) + 14.33 × 1(history of cigarette use) +0.44 × SBP -21.68 × 1(donor recipient both males) +27.30 × 1(donor-recipient blood-type incompatible) -10.61 × 1(donor recipient unrelated) + 8.57 × (#HLA-B mismatches)

We apply this formula to our data to calculate the LKDPI for each blood-type incompatible patient-donor pair who have ever participated in the KEP or went through a desensitization. [START_REF] Rehse | Validation of the Living Kidney Donor Profile Index in a European cohort and comparison of long-term outcomes with US results[END_REF] apply the same methodology to a German dataset and validate the results in [START_REF] Massie | A risk index for living donor kidney transplantation[END_REF] in the German population. However, the above formula cannot be used to assess the quality of an HLA incompatible graft, which we discuss below.

Missing values. Similar to the calculation of the KDRI, missing values are replaced by the corresponding sample mean (see Section D.2 for more details). A.11 Note that, even if we are only interested in the pairs that have participated in the KEP or desensitization, the reference population we use to calculate the sample means is all the pairs in our dataset, including 2, 737 pairs that have ever participated in the KEP or whose patient has received a donated kidney from the paired donor.

The history of cigarette use is missing for the vast majority of patients in our data. For this variable, similar to [START_REF] Rehse | Validation of the Living Kidney Donor Profile Index in a European cohort and comparison of long-term outcomes with US results[END_REF], we assume that this variable is zero when cigarette use is not mentioned in the patient's medical record. For the 8 pairs from Switzerland, our dataset contains a lot of missing values. However, these pairs are HLA incompatible and hence must be considered as special cases, as discussed below. Finally, for three blood-type incompatible pairs, most of the donor information is missing. These missing values are replaced by the corresponding sample means.

LKDPI for HLA incompatible pairs. HLA incompatibility is not taken into account in the LKDPI formula estimated by [START_REF] Massie | A risk index for living donor kidney transplantation[END_REF]. However, HLA incompatibility has a significantly negative association with graft survival (see, e.g., [START_REF] Bentall | Five-year outcomes in living donor kidney transplants with a positive crossmatch[END_REF]. In particular, an HLA incompatible graft is considered as being of a poorer quality than a blood-type incompatible graft.

For this reason, we assign HLA incompatible pairs an LKDPI equal to the highest value of the LKDPI among HLA compatible pairs that have ever participated in the KEP (i.e., 80.35).

A.11 [START_REF] Rehse | Validation of the Living Kidney Donor Profile Index in a European cohort and comparison of long-term outcomes with US results[END_REF] use the same imputation in their study using German data.

D.4 Selection of Deceased-Donor Kidneys

In Section 3.3.1, we allow deceased-donor kidneys, or DDL kidneys, to be proposed to unpaired patients. We require such DDL kidneys to be of a sufficiently high quality and acceptable to unpaired patients. We consider two alternative ways for the selection:

• In the baseline simulations (Section 3.3), we consider that a DDL kidney d j is acceptable to patient p i if d j 's KDPI is lower than the LKDPI of the pair (p i , d i ). In other words, a DDL kidney is considered as acceptable to p i if the risk of graft failure associated with this kidney is lower than that associated with an incompatible graft between p i and her paired living donor

• As a robustness check (Section 3.5), we define that a DDL kidney d j is acceptable to a patient if d j 's KDPI is lower than the median LKDPI in our sample. In other words, a DDL kidney is acceptable to p i if the risk of graft failure associated with this kidney is lower than the median risk of graft failure associated with a compatible living donor transplant. In our sample, this median LKDPI is 50.9, meaning that the median quality of a compatible living donation in France is very close to the median quality of a deceased donor in the US. Notes: This table is a detailed version of Table 4 in the main text. For APKD and NKR, the arrival rates are those of 2013 (Agarwal et al., 2018, Table 2). Pairs are sampled from the distributions from 2010 to 2019 for APKD (Ashlagi and Roth, 2020, Table 2) and from 2010 to 2014 for NKR (Ashlagi and Roth, 2020, Table 1). The algorithms are simulated for 1,694 days, the same as the simulations with French data. The statistics are averages across 1000 sets of simulations. The statistics reported are from the 1000 sets of simulations. The simulations are the same as in Table 2, except that pairs may exit before their patient receives a kidney. For more details, please see the notes of Table 2.