# optimal_kidney_exchange_with_immunosuppressants__0b3c191d.pdf

Optimal Kidney Exchange with Immunosuppressants

Haris Aziz,1 Agnes Cseh,2 John P. Dickerson,3 Duncan C. Mc Elfresh3

1 UNSW Sydney and Data61 CSIRO 2 Hasso-Plattner-Institute, University of Potsdam and Institute of Economics, Centre for Economic and Regional Studies 4 University of Maryland haris.aziz@unsw.edu.au, agnes.cseh@hpi.de, john@cs.umd.edu, dmcelfre@umd.edu

Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body s ability to reject a transplanted organ up to the point that a transplant across bloodor tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.

Introduction

The deployment of centralized matching algorithms for efficient exchange of donated kidneys is a major success story of market design (Bir o et al. 2019a,b). The theory and practice of kidney exchange have benefited from active research within artificial intelligence (e.g. Abraham, Blum, and Sandholm 2007; Manlove and O Malley 2014; Mc Elfresh, Bidkhori, and Dickerson 2019; Mc Elfresh and Dickerson 2018; Farina, Dickerson, and Sandholm 2017). The standard model for kidney exchange involves information about recipients compatibility with kidneys in the market. A recipient can only be given a kidney that is compatible with the recipient. The goal is to enable exchanges of kidneys via a centralized algorithm to satisfy the maximum number of recipients. We consider a new kidney exchange model which has an interesting feature that is informed by significant technological advances in organ transplant. The technology concerns immunosuppressants which if given to a recipient can make her receptive to kidneys which she is not receptive to by default (Montgomery et al. 2011). We will refer to the model

Copyright c 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

as Kidney Exchange with Immunosuppressants (KEI). Immunosuppressants (abbreviated as suppressants from here onwards) have been successfully used in Japan and Korea for several years, and increasingly being considered and utilized in other countries (Heo, Hong, and Chun 2020), even though they are costly and may have side effects. Due to these costs or side effects, it is desirable to match as many recipients to kidneys while minimizing the number of recipients who are given immunosuppressants. In this paper, the fundamental research problem that we explore is that of designing mechanisms for kidney exchange with suppressants that satisfy desirable computational, incentive and monotonicity properties. A naive way of using suppressants is to clear the classic kidney exchange market without using them and then give suppressant to the recipients who are left. However, there can be more efficient ways of giving suppressant to particular recipients and then implementing exchanges of kidneys to facilitate as many transplants as possible, as we will demonstrate in Figure 1. At first sight, the two-stage and connected process of using foresight to first giving suppressants to suitable recipients and then finding a matching that satisfies suitable social objectives appears to be a complex problem. We design a flexible algorithmic approach for the problem.

Contributions We formalize a general model of KEI that features compatible, half-compatible, and incompatible kidneys, and which allows for allocations as a result of multiway exchanges. We then initiate a computational study of kidney exchange with suppressants. Prior mechanism design work on the subject either only allows pairwise exchanges or focuses on a restricted model. One of our central contributions is modeling important KEI problems in terms of an underlying graph with different classes of edges. One of the edge classes represents organ compatibility that is dependent on administering immunosuppressants. Depending on how we set the edge weights in the graph problem, we can find in polynomial time, allocations corresponding to several important objectives. The objectives include maximizing the total number of transplants and given that, maximizing the number of compatible transplants. Among the list of objectives captured by our algorithmic framework, we defer the choice of the exact objective to the policy-makers.

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

Then, we focus on the problem where there is an upper bound on the number of suppressants that can be used. We present a polynomial-time algorithm for maximizing the number of transplants for a restricted model that we refer to as the Silver Bullet model. In the model, once a recipient has been given a suppressant, then the recipient can take any kidney. For our general model in which certain kidneys are inherently incompatible, we show that the problem of maximizing the number of transplants reduces in polynomialtime to an interesting generalized matching problem whose complexity has been open for years. Finally, we present a flexible integer linear program (ILP) formulation that allows us to optimize objectives subject to bounds on the length of exchange cycles. We validate that model on realistic data from a large, fielded kidney exchange in the United States, and show significant gains in the number of matches made even when the central clearinghouse is only able to use a small number of suppressants. Some of the techniques that we use such as to capture strong individual rationality or handle pairwise exchanges etc. are of independent interest and can be applied to a host of other problems in matching markets. Although we present our model and result in the language of kidney exchange and suppressants, our model and algorithms also apply to any exchange model in which agents have trichotomous preferences (Manjunath and Westkamp 2021) and for any halfcompatible match to materialize, the social designer needs to use some resource such as money to facilitate such a match. The goal is to implement desirable exchanges subject to minimum use of additional resources.

Related Work

Kidney exchange is one of the major research topics in matching market design (Abraham, Blum, and Sandholm 2007; Ashlagi and Roth 2021; Hatfield 2005; Bir o, Manlove, and Rizzi 2009; Dickerson, Procaccia, and Sandholm 2014; Li et al. 2019; Roth, S onmez, and Unver 2005; S onmez and Unver 2011). In many of the papers, the algorithms only allow exchange cycles of limited size due to logistical and other constraints. In this paper, we first allow exchange cycles of any size, and then discuss the bounded case. Note that for any exchange cycle bounds that are three or more, even the kidney exchange problem in the traditional model without suppressants is NP-hard (Abraham, Blum, and Sandholm 2007). The use of suppressants to facilitate more efficient kidney exchange has been discussed in medical circles (see, e.g. Abramowicz et al. (2018)). The two market design papers directly relevant to our work are the ones where kidney exchange with suppressants has been mathematically modeled (Heo, Hong, and Chun 2020; Andersson and Kratz 2020). Heo, Hong, and Chun (2020) prove a couple of impossibility results as well as an exchange mechanism with some desirable monotonicity properties. They assume that once suppressants are administered to a recipient, she can take a kidney from any donor. We consider a more general model in which half-compatibility is specific to particular recipient-donor pairs.

Andersson and Kratz (2020) consider a model more general than that of Heo, Hong, and Chun (2020) in which only certain donor-recipient pairs can be made compatible after giving suppressants to the recipient. They focus on pairwise kidney exchange (Roth, S onmez, and Unver 2005) and demonstrate through experiments that adding suppressant treatment to the pairwise exchange model results in a larger increase in transplant numbers than allowing short cycles. Considering both cycles and suppressants was discussed as important future work by Andersson and Kratz (2020). Our paper presents experimental results in this setting.

Model and Concepts

A kidney exchange market is a tuple (R, D, C, H, I) where R = {r1, r2, . . . , rn} is a set of n recipients (agents) and D is the set of donors. Some recipients and donors come in pairs; others come single. Generous donors who offer their kidney to the pool instead of a specific recipient in it are called altruistic donors. Each recipient ri partitions the donors D into sets Ci, Hi, and Ii. The set Ci is the set of donors whom recipient ri is compatible with. The set Hi is the set of donors ri is half-compatible with. Half-compatibility means that if a suppressant is given to ri, then ri can accept a kidney from any donor in Hi. Donors in the set Ii are incompatible with recipient ri even if ri is given a suppressant. These partitions at each recipient form the collections of sets C = (C1, . . . , Cn), H = (H1, . . . , Hn), and I = (I1, . . . , In) in the input. An allocation assigns each recipient ri at most one donor who is either in Ci or in Hi. Recipients who are assigned a half-compatible donor receive suppressants. We consider three models.

1. BM (Baseline model): for each ri R, Hi = .

2. SBM (Silver Bullet model): for each ri R, Ii = .

3. GM (General model).

The baseline model coincides with the traditional kidney exchange model in which suppressants are not considered. SBM is the model in which we assume that if a recipient is given a suppressant then she will be able to receive any kidney in the market (Heo, Hong, and Chun 2020). GM is the general model that also allows for some kidneys being inherently incompatible for a recipient even if she has been given suppressants. Unless specified, we will focus on GM. In some cases, we will present some results that hold for the Silver Bullet model (SBM). The SBM assumption was made by Heo, Hong, and Chun (2020) so we keep it as an important intermediate model between the baseline model and general model. Except for Theorems 3 and 4, all of our results and discussions hold for the general model. As far as a recipient or the social designer is concerned, there are two types of preferences. We will treat matching with incompatible donors to be infeasible.

1. Coarse preferences: a recipient is indifferent between a compatible donor and a half-compatible donor with a suppressant, and prefers both options over no transplant at all.

2. Refined preferences: a recipient prefers compatible donors over half-compatible donors along with a suppressant, which are preferred over no transplant at all.

Coarse preferences have the underlying assumption that a recipient has no significant cost (in terms of money or sideeffects) when receiving a half-compatible kidney. Based on the preference relation one can define concepts such as Pareto optimality. Heo, Hong, and Chun (2020) considered SBM and coarse preferences. They consider refined preferences when defining a monotonicity property. Andersson and Kratz (2020) considered GM and refined preferences. A recipient who is assigned a compatible donor or a halfcompatible donor along with a suppressant is referred to as satisfied. Our general goal is to satisfy the maximum number of recipients while minimizing the need of suppressants. We will consider the following feasibility condition for all allocations, which captures a natural individual rationality requirement: either a recipient donates her donor s kidney to the market and gets a strict improvement or she and her donated kidney are not part of any allocation. We will refer to this condition as strong individual rationality (strong-IR). A recipient who enters the market with a half-compatible donor improves her situation if she is assigned to her own or another half-compatible donor along with a suppressant. Also, strong-IR implies that a donor arriving in a pair with a recipient will only donate a kidney if her recipient also receives one. A weaker requirement is individual rationality (IR) whereby no recipient whose own donor is compatible ends up with no transplant or a half compatible kidney. Example 1. Consider a kidney exchange problem in which there are three recipients r1, r2, r3 with corresponding donors d1, d2, d3. No recipient s donor has a kidney compatible with the recipient. Recipient r1 finds the kidney of d2 compatible, while d3 H2 and d1 H3. The problem is captured in Figure 1. If suppressants are not allowed, then no recipient will be able to get a kidney without violating strong-IR. This remains the case if only one suppressant is allowed. Suppose now that the system has 2 suppressants available. In that case, one suppressant can be given r2 and another to r3. Then r1 can take a compatible kidney of d2, r2 takes a halfcompatible kidney of d1 and r3 takes a half-compatible kidney of d3.

Figure 1: A bipartite matching view of KEI. Dashed lines indicate half-compatible edges. Solid edges indicate compatibility edges. Dotted edges indicate a recipient-donor pair.

A General Graph Theoretic Approach We construct a general bipartite matching based model capturing the most basic features of kidney exchange markets.

It guarantees that each donor gives at most one kidney, each recipient receives at most one kidney, and the donor in a pair is only part of the exchange if her recipient receives a kidney. This framework gives us a set of feasible solutions for the problem. Then, by adding edge weights to the graph and finding a maximum weight matching, an optimal solution can be calculated. We specify a set of possible edge weights that can serve a large variety of goals of the decision maker, such as cost-efficiency or saving as many lives as possible.

Matching Model We build a bipartite graph to the instance (R, D, C, H, I), see Figure 2. For convenience, we distinguish between recipients with and without a related donor, who will form the sets R2 and R1, respectively. Analogously, D1 is the set of altruistic donors, while donors in D2 enter the market along with their related recipient in R2. We construct the following three types of vertices for our graph: a recipient vertex ri to each recipient ri R; a donor vertex di to each donor di D; a dummy donor vertex dj to each recipient rj R1, and a dummy recipient vertex rj to each donor dj D1. If a donor-recipient pair who applies for the scheme together, then the recipient and donor are given the same index: we refer to them as ri and di for some fixed i. Recipients without a donor share the same index with their dummy donor vertex, and an analogous notation is applied for altruistic donors and their dummy counterparts. Dummy donors form the set D0, while dummy recipients form the set R0. The edges of the graph are as follows. Each recipient ri R is connected to the donor with the same index di D via a private edge. Each dummy recipient rj R0 is connected to all donors via dummy edges. A donor di has a compatible edge to a recipient rj, where i might be equal to j, if di Ci. A donor di has a half-compatible edge to a recipient rj, where i might be equal to j, if di Hi. The four kinds of edges will play distinct roles when assigning weights to them. Private and dummy edges represent no transplant, while compatible and half-compatible edges stand for compatible and half-compatible transplants. Notice that a recipient and her donor forming a half-compatible (or compatible) pair are connected by two parallel edges, one private and one half-compatible (or compatible). Our goal is to calculate a perfect matching in the constructed graph. A matching and the corresponding allocation are in trivial one-to-one correspondence with each other. A recipient matched along her private or dummy edge represents no transplant. The matching property ensures that each recipient in R1 R2 receives one kidney at most, and each donor in D1 D2 also donates one kidney at most. Since a recipient ri R2 is only connected to di Ci Hi, and we restrict our attention to perfect matchings only, ri is either satisfied or she participates in no transplant, keeping her donor di. Perfectness thus ensures the following natural consequence of strong-IR: either a recipient uses her donor s kidney and gets a strict improvement, or she and her donor are not part of the allocation.

Figure 2: Example instance for our bipartite graph. Here, R1 = {r1}, and thus, d1 is a dummy donor. The only altruistic donor is d5, forming set D1, and her dummy recipient is r5. Dotted black edges are private, dotted gray edges are dummy, dashed edges mark half-compatible donations, and finally, solid edges mark compatible donations.

Objective func. compatible half-compatible private

1. TR 1 1 0

2. CO (BM) 1 0

3. (CO, TR) N 1 0

4. (CO, HC) N 1 0

5. (TR, HC) N N 1 0

6. cost-optimal comp. gain half-comp. g. waiting g.

Table 1: A set of weight functions serving different goals.

To guarantee that a compatible pair only participates in a pairwise exchange or a cycle if and only if the recipient receives a compatible kidney, we only need to delete the edges running from the recipient to all half-compatible donors. This could be a natural requirement from a compatible recipient-donor pair who enter the market together which actually often happens in practice, for example in the two largest exchange pools in Europe, in the Netherlands and in the UK (Bir o et al. 2019a).

We offer a variety of different weight functions defined on the edges of our graph. Each weight function serves a justifiable goal, as we argue later. Table 1 summarizes the options for defining the weight function on each edge (ri, dj), depending on the type of the edge. Dummy edges always carry zero weight, therefore they are omitted from the table. We assume N to be a sufficiently large integer, n for example. In an allocation, we denote the number of recipients receiving a kidney from a compatible donor by CO, the number of recipients receiving a kidney from a half-compatible donor by HC, while the total number of recipients receiving a kidney by TR = CO + HC. Our objective functions are to be maximized in the lexicographic sense, e.g. (TR, HC) maximizes the number of transplants in total, and subject to this, it minimizes the number of half-compatible transplants. Our objective functions can achieve the following. 1. The number of transplants is maximized if each pair cho-

sen for surgery contributes weight 1, while no transplant adds no weight to the matching. 2. The number of transplants is maximized in the baseline model, if half-compatible donations are forbidden due to their infinitely large negative weight, and each compatible donation contributes weight 1. 3. If a compatible transplant carries a larger weight than the weight of all half-compatible transplants that can be carried out, then the main goal is to maximize the number of compatible donations. Since half-compatible donations do carry some small weight, their number will be maximized, but only subject to the first objective. 4. Since half-compatible donations now carry a small negative weight, they are only to be planned if they enable extra compatible transplants. However, any number of halfcompatible donations are welcome if they make only one more compatible donation happen, because we gain a lot in our objective function by adding N just one more time to it. 5. If compatible and half-compatible donations both carry a large weight, but the latter ones are somewhat less profitable, then the maximum number of donations will be calculated, and subject to this, as few half-compatible donations will be planned as possible. 6. The most general version is when we set an arbitrary, possibly negative weight to each transplant. This weight can express the expected utility in terms of life expectancy, risks, healthcare savings, and it can differ for each pair. This objective is thus able to replace the trichotomous metric by a finely scaled one. Private edges represent withdrawal from donation, which can also be expressed in utilities, for example as loss due to health deterioration. On the positive side, sparing an exceptionally valuable donor in order to wait for a better match in the next round is also an entirely realistic scenario. A max weight solution corresponds to a maximum utility allocation.

Theorem 1. For each of the objectives 1) to 6), there exists a strongly polynomial-time algorithm to find an allocation achieving those objectives.

Proof. Our goal is to compute a maximum weight perfect matching in the graph. A maximum weight matching can be computed in strongly polynomial time (Munkres 1957). To take care of perfectness, or equivalently, maximum size, one only needs to apply the standard weight modification (Korte and Vygen 2012), in which each edge gets an additional uniform weight that is larger than the sum of the original weights in any matching. For this uniform addition, n wmax(e) + 1 suffices.

w (e) := w(e) + n wmax(e) + 1

The weight of matching M is thus w (M) := w(M) + (n wmax(e)+1) |M|. Since (n wmax(e)+1) |M| > w(M) for any matching M, larger matchings have a larger weight as well, thus w (M) is maximized by a perfect matching. Within the set of perfect matchings, (n wmax(e)+1) |M| = (n wmax(e) + 1) n is identical, and thus w is maximized in the maximum weight matching according to w.

Fixed Upper Bound on HC Suppressants are highly useful to allow half-compatible kidneys to be allocated. However, they are not only extremely expensive but they also have undesirable side-effects. Given these issues, the market designer may wish to specify a fixed upper quota on HC = h, and wishes to maximize the number of transplants subject to h. We show that even with an upper bound, we can solve the following central problem.

h-ALLKEI Input: KEI instance G = (R, D, C, H, I) and integer h. Question: Is there an allocation satisfying all the recipients with at most h recipients using suppressants?

Theorem 2. h-ALLKEI can be solved in polynomial time even for the general model.

Proof. Construct the corresponding graph as defined in section on the matching model, with vertex sets R and D. For the edges, here we only keep the edges of vertices in R0, compatible, and half-compatible edges. In particular, we delete the private edges between same-index couples in (R1 R2) (D0 D2). We want to check whether there exists an allocation such that every single recipient in R1 R2 gets either a compatible or a half-compatible kidney, and at most h of them receives a half-compatible kidney. In graph-theoretic terms, this question translates to deciding whether a perfect matching M exists in the constructed graph, so that M contains at most h edges from the special edge set E of half-compatible edges. This question can be answered by solving a simple weighted perfect matching problem. In the reduced graph, we give each compatible edge weight 1, and to all other edges, weight 0. The weight of any perfect matching M is n |M E |. The maximum weight matching in this instance has weight at least n h if and only if there is an allocation using at most h suppressants.

Our next problem, h-MAXKEI is a more general version of h-ALLKEI:

h-MAXKEI Input: KEI instance (R, D, C, H, I) and integers t and h. Question: Is there an allocation giving at least t recipients a compatible donor with at most h recipients using suppressants?

Our next result is that h-MAXKEI can be solved in polynomial time in the Silver Bullet model. Theorem 3. h-MAXKEI can be solved in polynomial time in the Silver Bullet model.

Proof. If we have a model that excludes incompatibility, as the Silver Bullet model, then a modification of the constructed graph solves this problem. We assume that each recipient in R1 R2 is connected to each donor in D1 D2 either via a half-compatible or via a compatible edge. Besides these edges, private and dummy edges are also present.

Figure 3: Substituting half-compatible edges by a gadget allowing at most 2 half-compatible donations. Compatible edges (r1, d2), (r2, d4), and the dotted private/dummy edges remain intact.

The modification of the graph is as follows. The goal is to decompose each half-compatible edge into a set of paths, and then lead these paths through a gadget that will regulate the maximum number of used halfcompatible edges through its size. First we add this gadget, which consists of 2h new vertices in sets A and B, and a set of h disjoint edges of weight 0 between them: {(a1, b1), (a2, b2) . . . , (ah, bh)}. Then we replace each edge (ri, dj) in the half-compatible class by a set of edges connecting ri to each of a1, a2, . . . , ah, and dj to each of b1, b2, . . . , bh. The weight on these edges are set to be half of the original weight of the replaced half-compatible edges. The rest of the graph remains unchanged. Notice that vertex sets R B and D A build a bipartition of the new graph. For an example, see Figure 3. The instance originates from our earlier example instance from Figure 2, with h = 2. The difference from that instance is that while (r1, d2) and (r2, d4) are compatible edges as before, all other recipientdonor pairs are half-compatible unless the recipient or the donor is a dummy, so that the input suits the Silver Bullet model. Figure 3 depicts the graph after vertex sets A, B, and the gadget on them are added to it.

Claim 1. A maximum weight perfect matching in the abovedescribed graph corresponds to an allocation maximizing the weight subject to HC h, if half-compatible donations are less desirable than compatible donations according to the weight function.

Proof. Due to the size of the gadget, no perfect matching allows more than h vertices in R to be matched along their edges to the gadget. Moreover, the number of vertices in R that are matched to a vertex in A equals the number of vertices in D that are matched to a vertex in B, because a perfect matching covers all vertices in the gadget. These vertices in R and D will be the agents participating in halfcompatible donations. Due to the assumptions of the Silver Bullet model, any perfect matching on them is a set of executable transplants. The rest of the transplants are chosen based on the maximum weight matching criterion. Notice that it is possible that a donor in D1 D2 and a recipient in R1 R2 are connected via a 3-path through the gadget and via a direct compatible edge as well, but for all weight functions where half-compatible donations are less desirable than compatible donations (all our weight func-

tions except for 1 and possibly 6), the path will carry the lower weight. Therefore, no perfect matching using such edges in the gadget can be of maximum weight.

This construction in the proof of Theorem 3 answers a question more general than h-MAXKEI. It actually decides whether there is an allocation of weight at least t while using at most h suppressants.

Theorem 4. In the Silver Bullet model, a maximum weight strong-IR allocation can be computed in polynomial-time even if there is an upper bound on the number of suppressants that can be used.

Next, we identify connections of h-MAXKEI with a special case of budgeted matching, a well-studied graph problem of unknown complexity.

UNIT-COST BUDGETED MATCHING Input: Bipartite graph G = (A B, E), E E, edge weights, and integers h and t. Question: Is there a maximum weight matching M of weight at least t such that |M E | h?

UNIT-COST BUDGETED MATCHING is a restricted variant of BUDGETED MATCHING, where in addition to the edge weights, edge costs c(e) are also present, and the budget |M E | h is substituted by c(M) h. If costs are 0 or 1, then BUDGETED MATCHING is identical to UNITCOST BUDGETED MATCHING, where E is the set of edges with cost 1. UNIT-COST BUDGETED MATCHING admits a PTAS (Berger et al. 2011; Mastrolilli and Stamoulis 2012). Berger et al. (2011) observe that for polynomial weights and costs (here we set the costs to be 1), BUDGETED MATCHING is very unlikely to be NP-hard, because it would imply RP=NP. However, after several decades, the problem of finding a deterministic algorithm to solve this problem is still open. We now show how h-MAXKEI reduces to UNIT-COST BUDGETED MATCHING.

Lemma 1. h-MAXKEI polynomial-time reduces to UNITCOST BUDGETED MATCHING.

Proof. We set E to be the set of half-compatible edges, while G and the upper bound h are identical in the two problems. To make sure that the maximum weight matching in UNIT-COST BUDGETED MATCHING is perfect, we modify the edge weights w(e) from h-MAXKEI in an analogous manner to our method in the proof of Theorem 1: w (e) := w(e) + n. The weight of matching M is thus w (M) := w(M) + n|M|. For w(e) 1, larger matchings have a larger weight as well, thus w (M) is maximized by a perfect matching. Within the set of perfect matchings, w is maximized in the maximum weight matching according to w.

Regarding parametrized complexity, our trivial parameter is h, the number of suppressants available. If h is small, then one can try which h half-compatible edges are used, and then search for a maximum weight allocation in the rest of the instance built out of compatible and private edges only.

Restrictions on the Exchange Cycle Length In kidney exchange, the length of the exchange cycles is typically required to be small for logistical reasons and to reduce the risk of a cycle being disrupted if someone backs out of the exchange. In this section, we focus our attention to short exchange cycles. Maximizing kidney exchange under the restriction on the size of the exchange cycles is NP-hard (Abraham, Blum, and Sandholm 2007; Bir o, Manlove, and Rizzi 2009). A practical approach to solving the problem involves formulating it as an ILP (Integer Linear Program).1 We present an ILP based on PICEF (Dickerson et al. 2016), given in (1) below. First we construct the graph to the instance as described in the section on the matching model. Edges are equipped with the edge weight w(e) serving any chosen objective in Table 1. To construct the corresponding ILP, we create the following binary variables: yek: 1 if edge e is matched at position k in a chain, and 0 otherwise zc: 1 if cycle c is matched and 0 otherwise ue: 1 if edge e is matched and 0 otherwise (not part of the original PICEF model). Following this, we define additional parameters (aligning with those described earlier in the paper, as well as new formulation-specific parameters): E, P, N: the set of edges, patient-donor pair vertices, and NDD vertices H E: the set of half-compatible edges h Z+: the maximum number of immunosuppressants w : E R: the edge weight for edge e K(e) {1, . . . , L}: the set of positions that edge e can take in a chain, where K is the maximum chain length C: the set of feasible cycles (up to length D). With some abuse of notation, we denote membership in a cycle using for both edges and vertices: e.g., if edge e is used in cycle c then e c; if vertex i participates in c, then i c. Finally, we construct ILP (1) below as follows.

k K(e) yek + P

e δ (i) k K(e)

e δ+(i) ye,k+1 i P, k {1, ..., L 1}

e δ+(i) ye1 1 i N

k K(e) yek + P

yek {0, 1} e E, k K(e) zc {0, 1} c C ue {0, 1} e E (1)

1Additionally, we address the case of pairwise exchange in the supplemental material, and give a polynomial-time clearing algorithm for just that special case.

The final two constraints are not part of the original PICEF model: the first new constraint defines variables ue, which is 1 if edge e is matched; the second new constraint requires that at most h half-compatible edges are matched. This ILP model is powerful, because it can deal with bounded cycle length and a budget on the number of suppressants at the same time. Even though it does not provide a polynomial method to solve the problem (since such an algorithm cannot exist unless P=NP), ILP formulations have proved to work well in practical scenarios (Constantino et al. 2013; Bir o et al. 2019a,b).

Experimental Results

In this section, we demonstrate the utility of immunosuppressants, with computational experiments on simulated kidney exchange graphs generated using data from the United Network for Organ Sharing (UNOS). For each UNOS graph, we begin with all vertices V and fully-compatible edges EF . Then we add new half-compatible edges by enumerating every blood-type-compatible pair of vertices that are not already connected; we randomly create edges between fraction α [0, 1] of these pairs. Let these half-compatible edges be denoted by EH; they can be matched only with an immunosuppressant. We denote the full set of edges as E = EF EH. All edges have weight 1. For each graph we find the optimal matching by solving ILP (1) with a budget of h {0, . . . , 100} suppressants. Results. For each immunosuppressant budget h {0, . . . , 100}, we find the optimal matching by solving Problem 1; then, let Mh denote the matching weight (objective value) of this optimal matching using at most h suppressants. Then, for each graph and each h {1, . . . , 100} we calculate %Baseline 100 Mh M0

M0 . In other words, %OPTh is the percentage-difference between the matching weight with budget h, and with budget 0 (no half-compatible edges). Figure 4 shows %Baseline for each set of random graphs, and for α {0.05, 0.1, 0.2}. Figure 5 shows the median percentage of each patient type matched. Additional figures in the supplemental material give further information about the spread of results over all the simulated runs. Figure 4 shows the immediate benefit of matching halfcompatible edges. Unsurprisingly, increasing the budget h results in diminishing marginal returns; the greatest marginal benefit comes from the first 10 edges. For the smalland medium-sized (i.e., 64 and 128-node) graphs, that relatively small budget nearly doubles the match size (weight); for the largest size (i.e., 256-node) graphs, that relative gain is 50% more still a substantial gain. There is also a trailing off effect such that, given enough immunosuppressant budget, no additional gain can be achieved. Recall that we are only able to activate potential edges between blood-type-compatible vertices; thus, many pairs of vertices may never be connected directly (e.g., O-type patients and AB-type donors), and graph structure may prevent vertices from ever being matchable at all. Figure 5 shows this behavior: relatively more of the easier-to-match blood types (AB, A, and B) are matched than the O-type patients, i.e., those with the hardest-to-match blood type. Still, Fig-

α = 0.05 α = 0.1

0 100 HC Edge Budget

Figure 4: Median %Baseline for each set of graphs (top: 64-node graphs, middle: 128-node graphs, bottom: 256node graphs), and each α {0.05, 0.1, 0.2}. Shading is between the min and max values of %Baseline.

Edge budget: 0 Edge budget: 10 Edge budget: 20

Edge budget: 50

Sens.A B AB O Patient Type

Sens.A B AB O Patient Type

Sens.A B AB O Patient Type

Sens.A B AB O Patient Type

Figure 5: Median percentage of each patient type: highlysensitized (Sens.), and blood type (A, B, AB, O), for each set of random graphs (top: 64-node graphs, middle: 128node graphs, bottom: 256-node graphs), and α = 0.2. Each column shows a different edge budget (0, 10, 20, 50).

ure 5 shows that in aggregate patients of each blood type are helped again, exhibiting diminishing marginal returns as immunosuppressant budget increases. Real-world kidney exchange pools range in size from a few dozen patient-donor pairs and altruistic donors either at individual transplant centers or in burgeoning but stillnascent multi-center programs to a few hundred in larger exchanges in the US, UK, and (soon) multinational exchanges. Our experimental results support that application of even a small number of suppressants results in large gains on realistic kidney exchange graphs of varying, realistic size.

Acknowledgements Cseh was supported by the Hungarian Academy of Sciences under its Momentum Programme (LP2016-3/2020), OTKA grant K128611, and COST Action CA16228 European Network for Game Theory. Dickerson and Mc Elfresh were supported in part by NSF CAREER Award IIS-1846237, NSF Award CCF-1852352, NSF D-ISN Award #2039862, NIST MSE Award #20126334, NIH R01 Award NLM-01303901, DARPA GARD Award #HR00112020007, Do D WHS Award #HQ003420F0035, DARPA Disruptioneering Award (SI3-CMD) #S4761, and a Google Faculty Research Award.

Ethical Impact Kidney exchanges save lives and are broadly viewed as beneficial to humanity; however, as in many resourceconstrained settings, decision-makers must make morallyladen decisions when designing the objective functions, constraints, and other modeling concerns that increasingly run modern exchange programs. The economics, AI, operations research, bioethics, medical, and legal communities have long discussed the moral implications of different approaches to the allocation of organs (see, e.g., Cohen 1989), including kidney exchanges (see, e.g., Ross et al. 1997; Minerva, Savulescu, and Singer 2019; Torres et al. 2019). Broadly speaking, our proposed work falls into the category of creating a more general, and thus potentially more powerful, model for the exchange of organs, and thus may come with many of the same positive and negative potential ethical impacts. Positives are clear: those who could not previously receive a kidney may now be afforded that opportunity, and those who would have been matched to a relative worse kidney donor are now afforded the opportunity to match to a relatively better one. Specific to our model, though, is the potential ethical implication of applying a suppressant to one patient so that another patient matched elsewhere in a cycle or chain might receive a kidney. There is a cost both monetary and in terms of quality of health to immunosuppression; thus, an open and morally-laden question lies in determining the tradeoffs between, and level of agency given to, participants in exchanges that run immunosuppression schemes. As in many such scenarios, there is no globally correct answer, but rather only an answer that can be arrived at after careful consideration by stakeholders: patients, donors, doctors, ethicists, lawyers, and possibly others. We do not prescribe a specific solution here, but rather note that our model is general and could, with input from domain experts, be augmented to address some of these concerns.

References Abraham, D.; Blum, A.; and Sandholm, T. 2007. Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. In ACM Conference on Electronic Commerce (EC), 295 304. ACM Press. Abramowicz, D.; Oberbauer, R.; Heemann, U.; Viklicky, O.; Peruzzi, L.; Mariat, C.; Crespo, M.; Budde, K.; and Oniscu, G. C. 2018. Recent advances in kidney transplantation: a viewpoint from the Descartes advisory board. Nephrology Dialysis Transplantation 33(10): 1699 1707.

Andersson, T.; and Kratz, J. 2020. Pairwise kidney exchange over the blood group barrier. The Review of Economic Studies 87(3): 1091 1133.

Ashlagi, I.; and Roth, A. E. 2021. Kidney Exchange: An Operations Perspective. doi:10.3386/w28500. URL http: //www.nber.org/papers/w28500.

Berger, A.; Bonifaci, V.; Grandoni, F.; and Sch afer, G. 2011. Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Mathematical Programming 128(1-2): 355 372.

Bir o, P.; Haase-Kromwijk, B.; Andersson, T.; Asgeirsson, E. I.; Baltesov a, T.; Boletis, I.; Bolotinha, C.; Bond, G.; B ohmig, G.; Burnapp, L.; et al. 2019a. Building kidney exchange programmes in Europe an overview of exchange practice and activities. Transplantation 103(7): 1514 1522.

Bir o, P.; Manlove, D. F.; and Rizzi, R. 2009. Maximum weight cycle packing in optimal kidney exchange programs. Discrete Mathematics, Algorithms and Applications 1(4): 499 517.

Bir o, P.; van de Klundert, J.; Manlove, D.; Pettersson, W.; Andersson, T.; Burnapp, L.; Chromy, P.; Delgado, P.; Dworczak, P.; Haase, B.; et al. 2019b. Modelling and optimisation in European Kidney Exchange Programmes. European Journal of Operational Research ISSN 0377-2217.

Cohen, L. R. 1989. Increasing the Supply of Transplant Organs: The Virtues of a Futures Market. George Washington Law Review 58(1): 1 51.

Constantino, M.; Klimentova, X.; Viana, A.; and Rais, A. 2013. New insights on integer-programming models for the kidney exchange problem. European Journal of Operational Research 231(1): 57 68. ISSN 0377-2217.

Dickerson, J. P.; Manlove, D.; Plaut, B.; Sandholm, T.; and Trimble, J. 2016. Position-Indexed Formulations for Kidney Exchange. In ACM Conference on Electronic Commerce.

Dickerson, J. P.; Procaccia, A. D.; and Sandholm, T. 2014. Price of fairness in kidney exchange. In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems, 1013 1020. International Foundation for Autonomous Agents and Multiagent Systems.

Farina, G.; Dickerson, J. P.; and Sandholm, T. 2017. Operation Frames and Clubs in Kidney Exchange. In Proc. of 26th AAAI Conference, 199 205.

Hatfield, J. W. 2005. Pairwise kidney exchange: Comment. Journal of Economic Theory 125: 189 193.

Heo, E. J.; Hong, S.; and Chun, Y. 2020. Kidney exchange with immunosuppressants. Economic Theory 1 19.

Korte, B.; and Vygen, J. 2012. Combinatorial Optimization, volume 21 of Algorithms and Combinatorics. Springer, 5 edition.

Li, Z.; Lieberman, K.; Macke, W.; Carrillo, S.; Ho, C.-J.; Wellen, J.; and Das, S. 2019. Incorporating Compatible Pairs in Kidney Exchange: A Dynamic Weighted Matching Model. In Proceedings of the 2019 ACM Conference on Economics and Computation, 349 367. ACM.

Manjunath, V.; and Westkamp, A. 2021. Strategy-proof exchange under trichotomous preferences. Journal of Economic Theory 193: 105197. ISSN 0022-0531. doi:https: //doi.org/10.1016/j.jet.2021.105197. URL https://www. sciencedirect.com/science/article/pii/S0022053121000144. Manlove, D. F.; and O Malley, G. 2014. Paired and altruistic kidney donation in the UK: Algorithms and experimentation. Journal of Experimental Algorithmics (JEA) 19: 2 6. Mastrolilli, M.; and Stamoulis, G. 2012. Constrained matching problems in bipartite graphs. In International Symposium on Combinatorial Optimization, 344 355. Springer. Mc Elfresh, D. C.; Bidkhori, H.; and Dickerson, J. P. 2019. Scalable Robust Kidney Exchange. In Proc. of 33rd AAAI Conference, 1077 1084. Mc Elfresh, D. C.; and Dickerson, J. P. 2018. Balancing Lexicographic Fairness and a Utilitarian Objective With Application to Kidney Exchange. In Proc. of 32nd AAAI Conference, 1161 1168. Minerva, F.; Savulescu, J.; and Singer, P. 2019. The ethics of the Global Kidney Exchange programme. The Lancet 394(10210): 1775 1778. Montgomery, R. A.; Lonze, B. E.; King, K. E.; Kraus, E. S.; Kucirka, L. M.; Locke, J. E.; Warren, D. S.; Simpkins, C. E.; Dagher, N. N.; Singer, A. L.; et al. 2011. Desensitization in HLA-incompatible kidney recipients and survival. New England Journal of Medicine 365(4): 318 326. Munkres, J. 1957. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics 5(1): 32 38. Ross, L. F.; Rubin, D. T.; Siegler, M.; Josephson, M. A.; Thistlethwaite, J. R.; and Woodle, E. S. 1997. Ethics of a Paired-Kidney-Exchange Program. New England Journal of Medicine 336(24): 1752 1755. doi:10.1056/ NEJM199706123362412. URL https://doi.org/10.1056/ NEJM199706123362412. PMID: 9180096. Roth, A. E.; S onmez, T.; and Unver, M. U. 2005. A Kidney Exchange Clearinghouse in New England. American Economic Review 95(2): 376 380. Roth, A. E.; S onmez, T.; and Unver, M. U. 2005. Pairwise kidney exchange. Journal of Economic Theory 125(2): 151 188. S onmez, T.; and Unver, M. U. 2011. Matching, Allocation, and Exchange of Discrete Resources. In Benhabib, J.; Jackson, M. O.; and Bisin, A., eds., Handbook of Social Economics, volume 1, chapter 17, 781 852. Elsevier. Torres, A.-M.; Wong, F.; Pearson, S.; Weinberg, S.; Roberts, J. P.; Ascher, N. L.; Freise, C. E.; and Lee, B. K. 2019. Bi-organ paired exchange? Sentinel case of a liver-kidney swap. American Journal of Transplantation 19(9): 2646 2649.