Operation Frames and Clubs in Kidney Exchange

1 Introduction

Kidney transplantation is the most effective treatment for kidney failure. However, the demand for donor kidneys far exceeds the supply. The United Network for Organ Sharing (UNOS) reported that as of October 28th, 2016, the waiting list for kidney transplant had 99,382 patients.

Roughly two thirds of transplanted kidneys are sourced from cadavers, while the remaining one third come from willing healthy living donors. Patients who are fortunate enough to find a willing living donor must still contend with compatibility issues, including blood and tissue type biological com-

Tuomas Sandholm

Computer Science Department Carnegie Mellon University sandholm@cs.cmu.edu

patibility. If a willing donor is incompatible with a patient, the transplantation cannot take place.

This is where kidney exchange comes in. A kidney exchange is a centrally-administered barter market where patients swap their willing yet incompatible donors. Modern kidney exchanges use 2-cycles, 3-cycles, and chains initiated by non-directed donors (altruists who are willing to give a kidney to anyone) as the means for swapping.

The idea of kidney exchange was introduced by Rapaport [1986], and the first organized kidney exchanges started around 2003 [Roth et al., 2004; 2005]. Today there are kidney exchanges in the US, Canada, UK, the Netherlands, Australia, and many other countries. In the US, around 10% of live-donor kidney transplants now take place via exchanges.

Kidney exchanges started as matching markets where one donor-patient pair would give to, and receive from, another donor-patient pair. In other words, 2-cycles [Roth et al., 2005] were the structures used. Then, kidney exchange was generalized to also use 3-cycles [Roth et al., 2007], and then short and finally never-ending chains initiated by nondirected donors (altruists who are willing to give to anyone without needing an organ in return) [Roth et al., 2006; Rees et al., 2009].

Significant work has been invested into scaling the market clearing algorithms, that is, the algorithms that find the optimal combination of non-overlapping (because any one donor can give at most one kidney) cycles and chains [Abraham et al., 2007; Constantino et al., 2013; Manlove and O'Malley, 2015; Anderson et al., 2015b; Dickerson et al., 2016].

We propose a significantly generalized, more expressive, approach to kidney exchange. We allow more than one donor to donate in exchange for their desired patient receiving a kidney. We also allow for the possibility of a donor willing to donate if any of a number of patients receive kidneys. Furthermore, we combine these notions and generalize them.

Our generalization can be formalized around the concept of exchange among organ clubs, where, roughly speaking, a club is willing to donate organs outside the club if and only if the club receives organs from outside the club according to given specifications. More specifically, exchange clubs extend the notion of a donor-patient pair, allowing for a set of healthy donors equally willing to donate one of their kidneys in exchange for an equal (or greater) number of kidneys received by a target set of patients.

Forms of organ clubs already exist-under an arrangement where one gets to be in the club as a potential recipient if one is willing to donate one's organs to the club upon death. For example, there was such a club called LifeSharers in the US for several years [Hennessey, 2006]. It shut down in 2016 amid controversy regarding whether an organ club would actually hurt the nationwide organ allocation. Similarly, there is an organ club in the military "that allows families of activeduty troops to stipulate that their loved ones' organs go to another military patient or family [Kime, 2016]." Also, Israel started an organ club where those who have given consent to become organ donors upon death (or whose family members have donated an organ in the past) get priority on the organ waitlist if they need organs; this increased organ donation in Israel by 60% in just one year [Stoler et al., 2016; Ofri, 2012]. One way to think of the approach that we are proposing is as an inter-club exchange mechanism that increases systemwide good-and can also be applied to live donation.

Our approach is beneficial also in a setting where there are no organ clubs in the traditional sense. We will nevertheless find the notion of a club useful in a technical sense to define the constraints, as we will detail later. We propose a formalization of this new kind of organ exchange, and propose an organ exchange approach where clubs are conceptually the primary agents-whether they are actually clubs, altruists, or donor-patient pairs, or a combination thereof. We support both intra-club and inter-club donations. We prove that unlike in the standard model, the uncapped clearing problem is NP-complete.

To address the issues that (1) a club (of which a donorpatient pair is a special case, as is an altruist donor) wants to receive no later than it gives, and (2) there are logistical limits as to how many operations can be conducted simultaneously, we introduce the concept of operation frames. They provide a convenient framework for handling the problem of synchronizing different transplants, by imposing a partial order on them. We propose a linear integer program for this.

Experiments show that in the single-donation setting, operation frames improve planning by 34%-51%. Allowing up to two donors to donate in exchange for one kidney donated to their designated patient yields a further welfare increase.

2 The StandardModel

Today's kidney exchanges (and other modern barter exchanges) can be modeled as follows. There is a directed compatibility graph G = (V,E), where vertices represent participating parties and edges representing potential transactions [Roth et al., 2007; Abraham et al., 2007]. In the kidney exchange context, the set of vertices V is partitioned as V = Vp ∪ Vn, where Vp is the set of donor-patient pairs, and Vn is the set of non-directed donors (NDDs).

For sake of simplicity, we will consider all non-directed donor vertices as formal donor-patient pairs, where the patient is an artificial object-denoted by ⊥-that is incompatible with any donor in the system. Vertices u and v are connected by a directed edge u → v if the donor in u is compatible with the patient in v. The exchange administrator can also define a weight function w : E → R representing, for each edge e = (u, v) ∈ E, the underlying quality or priority given to a potential transplant from u → v.

Given the model above, we wish to solve the clearing problem, that is, we wish to select some subset of edges with maximum total weight subject to underlying feasibility constraints. For example, a donor d in a donor-patient pair v = (d, p) ∈ Vp will donate a kidney if and only if a kidney is allocated to his or her paired patient p. Non-directed donors have no such constraint. In the model described so far, any solution consists of only two kinds of structure:

• chains, that is paths in G initiated by NDDs and then consisting entirely of donor-patient pairs; and
• cycles, that is loops in G consisting of vertices in Vpand not non-directed donors in Vn.

Furthermore, in any feasible solution, these structures cannot share vertices: no donor can give more than one kidney.

In kidney exchange, a length cap L is imposed on cycles for logistical reasons. All transplants in a cycle must be performed simultaneously so that no donor can back out after his patient has received a kidney but before he has donated his kidney. In most fielded exchanges worldwide, L = 3, so only 2-cycles and 3-cycles are allowed.

Chains do not need to be constrained in length, because it is not necessary to enforce that all transplants in the chain occur simultaneously. There is a chance that a donor backs out of her commitment to donate, but this event is less catastrophic than the equivalent in cycles. Indeed, a donor backing out in a cycle results in some other patient in the pool losing his donor while not receiving a kidney-that is, a participant in the pool is strictly worse off than before-while a donor backing out in a chain simply results in the chain ending. While that latter case is unfortunate, no participant in the pool is strictly worse off than before. In practice, however, a chain length cap is used, in order to make the planned solution more robust to last-minute failures [Dickerson et al., 2012b; 2016].

The problem can be formulated as an integer program to find the optimal solution, and indeed there has been significant work on developing increasingly scalable integer programming algorithms and formulations for this problem (e.g., [Roth et al., 2007; Abraham et al., 2007]). The state of the art formulation is called PICEF [Dickerson et al., 2016]. Its number of variables is polynomial in chain length cap and exponential in cycle length cap, which is not a problem in practice because the latter cap is small. Furthermore, the LP relaxation is very tight, causing good upper bounding in the search tree and therefore fast run time.

3 Exchange Clubs as aModeling Construct

We propose significant generalizations to (kidney) exchange. We allow more than one donor to donate in exchange for their desired patient receiving a kidney. We also allow for the possibility of a donor willing to donate if any of a number of patients receive kidneys. Furthermore, we combine these notions and generalize them. We formalize this by introducing the modeling concept of exchange clubs.

Definition 1. (Exchange club) An exchange club c is a tuple (Dc, Pc, αc, γc) composed of

• a (possibly empty) set of donors Dc;
• a real αc ≥ 1 called "matching multiplier". Intuitively, this means that for each matched patient in Pc, the club is willing to donate (in expectation) αc kidneys to the pool;
• a (possibly empty) set of patients Pc;
• a real γc ≥ 0 called "matching debt".

The idea of exchange clubs is that donors in Dc are willing to donate kidneys only if doing so results in a tangible benefit (that is, kidneys donated) to patients in Pc. More precisely, let next d (t) be the number of kidneys donated from donors in Dc to clubs other that c by time t, and let next p (t) be the number of kidneys donated from donors outside of c to patients in Pc; then the following inequality must hold for all time t in order for club c to be willing to participate in the solution:

For now, we ignore parameter γc, whose role and motivation will become clear later.

We can now formalize the uncapped generalized clearing problem as follows.

Definition 2. (Disjoint clubs) We say that two exchange clubs c and c′ are disjoint if Pc ∩Pc′ = ∅ and Dc ∩Dc′ = ∅.

Problem 1. (Uncapped generalized clearing problem) Let C be a set of mutually disjoint exchange clubs; let D = ∪c∈CDc and P = ∪c∈CPc denote the overall set of donors and patients respectively. Furthermore, let E ⊆ D × P be the set of compatibility edges, and let w : E → R a weighting function assigning a weight to every compatibility edge. We want to find a set of edges that maximizes the sum of weights and satisfies Inequality 1 assuming all the selected transplants occur simultaneously.

Matching Debts. We now explain the meaning of γc. Suppose a number next p of patients in club c receive kidneys from other clubs, and that the optimal solution of the problem requires that next d donors from club c donate a kidney to other clubs. If next d < αcnext p , we say that club c owes αcnext p -next d kidneys to the system. This is exactly the meaning of the "matching debt" of a club. It reflects the sum of all debts that a club has cumulated in the past. Except for clubs defined by non-directed donors (which start with a debt of 1), each club typically starts with a debt of 0 at the beginning, and potentially increases or decreases its debt to the system over time.

The kidney exchange pool changes over time as the exchange conducts transplants. Debts allow the exchange to keep track of the state, which is then used as the input in the next optimization.

3.1 The StandardModel is a Special Case

The (uncapped) standard model is a special case of our model:

• each non-directed donor defines a club c with no patient, and where he or she is the only donor. Furthermore, the club has γc = 1 (the value of αc is irrelevant);
• each (d, p) donor-patient pair in the standard models defines a club c, where Dc = {d}, Pc = {p} and αc = 1.

At the same time, our new model allows for some important generalizations. For instance, consider the case where one patient p has a set of two donors both willing to donate a kidney in exchange for only one kidney donated to p. In this case, the two donors and p form a club with αc = 2.

The introduction of exchange clubs as a modeling construct calls for a different representation of the problem because the traditional donor-patient pairs cannot capture all the new aspects. Therefore, we explicitly represent donors and patients as different types of vertices in the graph. Figure 1 illustrates this under the further assumption that αc = 1, γc = 0 for all clubs. We represent donor vertices with a square and patient vertices with a circle. Observe that in Figure 1 it is not possible to extend the given solution with an edge from Donor 8 to Patient 7, as doing so would violate Inequality 1: Club D does not receive any kidney from other clubs, and therefore it cannot be asked to donate.

3.2 Uncapped ProblemFormulation

It is not clear how one could apply an integer program formulation like the state-of-the-art PICEF formulation for the standard kidney exchange problem [Dickerson et al., 2016] in this new setting. This is because, in our setting, the feasibility (in the sense of Inequality 1) of a particular donation depends on what transplants have already been conducted. It does not seem immediate how such aspects could be encoded in a formulation like PICEF. However, one can easily write an integer linear program for the uncapped clearing problem that selects edges so as to maximize total weight of the selected edges subject to satisfying Constraint 1.

Theorem 1 shows that the decision problem associated with this problem is is NP-complete. This is in stark contrast to the standard model where the uncapped version can be solved in polynomial time [Abraham et al., 2007]. This increase in hardness is the cost of our increased expressiveness.

Theorem 1. The decision problem associated with the uncapped generalized clearing problem is NP-complete.

Proof sketch. Membership in NP: Given a set of mutually disjoint exchange clubs C and set of k trades, it is trival to check in polynomial time if they satisfy Inequality 1. NP-hardness: We reduce from SET-PACKING (SP). An instance of SP takes a set of items U, a family S of subsets of U, and an integer k as input; the task is to find a disjoint subfamily X ⊆ S such that |X| = k.

Assume that we are given an instance of SP. We will now build an instance of our problem. Let n = |U| be the number of items and m = |S| be the number of subsets. Index the items {u1, . . . , un} ∈ U and the subsets {S1, . . . , Sm} ∈ S. Construct a disjoint set of clubs C as follows. For each ui ∈ U, construct a club ai with no patient, one donor, and γai = 1. For each subset Sj ∈ S, construct a club cj with one patient and no donor. Furthermore, for each subset Sj, construct a club bj with one donor and ℓ = |Sj| patients, γbj = 0, and αbj = 1/ℓ. Intuitively, this club will donate its one kidney iff each of the ℓ patients receives a kidney.

We now specify the set of legal transplants. Let M = |U|+ 1. For each subset Sj ∈ S, draw a directed edge with weight M from the single donor in club bj to the single patient in club cj. Furthermore, for each item ui ∈ U and subset Sj ∈ S such that ui ∈ Sj, draw one directed edge with weight 1 from the single donor in club ai to the patient corresponding to item ui in club bj. Figure 2 shows the final construction.

We will now show that a solution exists for the instance of SC if and only if our problem has a legal matching with weight in [kM, (k + 1)M).

(⇒) Suppose there exists some solution S ′ = {S′1 , . . . , S ′k } to the SP problem; that is, there exists some disjoint subfamily of S of size k. Then, for each subset S′j ∈ S ′ , for each element ui in S′j , use the edge from club ai to club bj . By the disjointness of the subfamily S ′ , each single-donor club ai for i ∈ [n] donates to at most one club. Furthermore, each club bj corresponding to S′j ∈ S ′ receives one kidney for each patient in its club; by construction, their matching multiplier is now satisfied. Thus, for each S′j ∈ S ′ , include the edge with weight M from the one donor in bj to the one patient in cj. This results in a matching of weight at least kM, but no more than kM + n < (k + 1)M.

(⇐) Suppose there exists a matching in our problem such that the weight of the matching is in [kM, (k + 1)M). Then exactly k of the edges between exactly k pairs of clubs b· and c· are used, at total weight kM. Let j ′ ∈ [m′ ] index those clubs bj ′ that use their one outgoing edge to club cj ′ . Each club bj ′ uses that edge if and only if every one of its internal patients receives a kidney; since each single-donor club a· can give at most one kidney, they are used at most once. Since at most n clubs a· can be used, each at additional weight 1, the final matching is of weight at most km+ n < (k + 1)M; further, exactly k clubs bj ′ were fulfilled completely, corresponding to exactly k disjoint subsets Sj ′ ∈ S being packed.

4 Operation Frames

While the above modeling approach is promising, it has a major shortcoming: it might require that a potentially large number of operations happen at the same time so as to honor the condition that the donors not be operated on strictly before patients in their clubs receive kidneys. An example is provided in Figure 3, where we would need patients {1, 2, 3, 6, 7} and donors {1, 2, 3, 5, 6} to be operated on at the same time.

This is not practically viable for at least two reasons:

• the success probability of all the planned transplants in the structure succeeding in their pre-operation blood type compatibility tests (aka. crossmatch test) and other pre-transplant testing decreases multiplicatively with the number of edges in the planned structure, 1 and
• the logistic (and financial) details are hard to executeten people to operate on have to be coordinated, together with the surgeons and staff needed for ten surgeries.

In order to solve this synchronization issue, we introduce the concept of operation frames. An operation frame t is an edge set of size up to Kt, representing operations to be performed at the same time. The introduction of operation frames enables us to reason in terms of order in which the operations will be carried out. The chronological order imposed on the operation frames is partial. For this reason, we can formalize the set and relationships among operation frames by means of a directed acyclic graph (DAG) F = (T, B), where the set of vertices (i.e., T) coincides with the set of operation frames, while the set of edges B ⊆ T × T denotes the happensstrictly-before chronological (partial) order. We say that operation frame u happens strictly before operation frame v, denoted u⇝v, if there exists a directed path in F from u to v.

The introduction of operation frames enables Inequality 1 to be written in terms of logical time, that is, substituting the notion of time with the partial happens-strictly-before order. Thus, for any frame τ ∈ T, the number of kidneys that were surely (i.e., for any possible linearization of the DAG F) donated to and from club c at the time when τ is executed is nd(τ) = ∑τ ′⇝τ d(c, τ ′ ), np(τ) = ∑τ ′⇝τ p(c, τ ′ ), where d(c, τ ′ ) and p(c, τ ′ ) represent the number of transplants from and to club c scheduled for operation frame τ ′ .

We argue that operation frames provide a richer problem structure, as it is now possible to assign a (partial) chronological order to the operations we plan to perform. Furthermore, they encode the condition that "no more than Kt people get ber of kidneys donated to club c from other clubs, before or at operation frame t. The objective function ensures that a maximum-weight solution is found. 2

1 For further details about pre-transplant test failures, see Dickerson, Procaccia, and Sandholm [2013] and Blum et al. [2015].

4.2 Operation Frames Counter Myopia

standard batch-based one also in the sense that it inherently

breaks long structures into shorter ones that execute sequen4.2 Operation Frames Counter Myopia

Finally, operation frames allow an integer programming formulation of the problem that (unlike PICEF) uses a number of variables that is polynomial in the maximum size cap maxt Kt. We present that formulation in the next section. operations that can be accommodated. Different frames can have different size constraints. Finally, operation frames allow an integer programming formulation of the problem that (unlike PICEF) uses a number of variables that is polynomial in the maximum size cap

operated on at the same time" in a very natural way: every operating frame has a parameter Kt. Indeed, operation frames guarantee that not too many surgeries are planned to happen at the same time. Conceptually, they are equivalent to imposing chain and cycle length caps, as it is done in standard model. However, here we are allowing much richer exchange structures (and, as presented so far, there is no way of specifying a different cap on the size of chains versus cycles versus other structures). This is because the operation frame size cap Kt represents an actual limit on the number of simultaneous operations that can be accommodated. Different frames can have different size constraints. and to club c scheduled for operation frame ⌧ 0 . We argue that operation frames provide a richer problem structure, as it is now possible to assign a (partial) chronological order to the operations we plan to perform. Furthermore, they encode the condition that "no more than Kt people get operated on at the same time" in a very natural way: every operating frame has a parameter Kt. Indeed, operation frames guarantee that not too many surgeries are planned to happen at the same time. Conceptually, they are equivalent to imposing chain and cycle length caps, as it is done in standard model. However, here we are allowing much richer exchange structures (and, as presented so far, there is no way of specifying a different cap on the size of chains versus cycles versus other structures). This is because the operation frame size cap Kt represents an actual limit on the number of simultaneous

4.1 Capped ProblemFormulation maxt Kt. We present that formulation in the next section.

The idea of operation frames can be plugged into the uncapped integer program, leading to the following formulation. 4.1 Capped ProblemFormulation The idea of operation frames can be plugged into the uncapped integer program, leading to the following formulation.

Formulation 1: MIP formulation for the capped problem. Formulation 1: MIP formulation for the capped problem.

tially. Figure 4 shows an example compatibility graph where our model will return a higher-value solution than the optimal solution in the traditional model. Figure 4: An example graph where Formulation 1 returns a higher-value solution than the standard batch approach, even with only the standard kinds of vertices available. Given a cap K = 2, the standard approach will choose the lower 2chain over the upper 2-chain for utility 3, while our solver will choose to match the upper 3-chain across two frames for Present-day kidney exchanges operate in a batch setting, potentially planning in a single shot long chains that will, in practice, execute in segments over many months. Solvers for the standard problem (e.g., those based on PICEF) optimize on a batch-by-batch basis, selecting the global optimum solution only inside of a single batch, and not considering future batches. Our approach is more powerful than the standard batch-based one also in the sense that it inherently breaks long structures into shorter ones that execute sequentially. Figure 4 shows an example compatibility graph where our model will return a higher-value solution than the optimal solution in the traditional model.

greater overall utility of 6. Figure 1 shows that the capped approach in the standard model cannot consider certain solutions; yet, our capped approach-based on the concept of operations framesoptimizes across all the operation frames at the same time, resulting in less myopic behavior. Under the assumption that the kidney exchange pool is not affected by any exogenous behavior (e.g., compatibility failures, deaths of donors or patients, dynamic insertions and deletions of edges and vertices), our formulation is guaranteed to find a globally optimal allocation of transplants across all operation frames. In contrast, even under these strong assumptions, present-day solvers for the standard model will (by design) fail to find a globally optimal solution across batches. Figure 1 shows that the capped approach in the standard model cannot consider certain solutions; yet, our capped approach-based on the concept of operations framesoptimizes across all the operation frames at the same time, resulting in less myopic behavior. Under the assumption that the kidney exchange pool is not affected by any exogenous behavior (e.g., compatibility failures, deaths of donors or patients, dynamic insertions and deletions of edges and vertices), our formulation is guaranteed to find a globally optimal allocation of transplants across all operation frames. In contrast, even under these strong assumptions, present-day solvers for the standard model will (by design) fail to find a globally optimal solution across batches.

5 Experiments 5 Experiments

We let xtdp be a binary value (Constraint 5 ) indicating whether the transplant represented by the edge (d, p) 2 E is scheduled for operation frame t. Analogous to the uncapped case, Constraints 1 and 2 ensure that each donor donates at most one kidney and that each patient receives at most one kidney, respectively. Constraint 4 ensures that in any operation frame t 2 T , no more than K transplants are scheduled. Constraint 3 enforces that at any time t, for each club c 2 C, the total number of kidneys donated from club c does We let xtdp be a binary value (Constraint 5 ) indicating whether the transplant represented by the edge (d, p) ∈ E is scheduled for operation frame t. Analogous to the uncapped case, Constraints 1 and 2 ensure that each donor donates at most one kidney and that each patient receives at most one kidney, respectively. Constraint 4 ensures that in any operation frame t ∈ T , no more than K transplants are scheduled. Constraint 3 enforces that at any time t, for each club c ∈ C, the total number of kidneys donated from club c does not exceed ⌊γc + αcnext p (t)⌋, where next p (t) is the total number of kidneys donated to club c from other clubs, before or at operation frame t. The objective function ensures that a maximum-weight solution is found. 2

2 One can also model temporal preferences by multiplying the edge weights by discounts h(t), which depend on which operation frame t the surgery is conducted. (This assumes that the time between frames is exogenous-but not necessarily constant-that is,

Also, around 70% of edges in kidney exchanges fail due to various pre-transplant tests, so the planned transplant cannot occur after all [Dickerson et al., 2013]. We take this into account by randomly removing 70% of the edges independently from the master graph. In each experiment, we subsample

We conducted experiments to evaluate the techniques. The experiments are conducted using the real data from the UNOS kidney exchange that started in 2010. In that data we have the vertices that have a patient and one or more donors, and 2 One can also model temporal preferences by multiplying the edge weights by discounts h(t), which depend on which operation frame t the surgery is conducted. (This assumes that the time between frames is exogenous-but not necessarily constant-that is, the time between frames does not depend on what transplants the optimizer decides to put in each frame.) This discounting is already include in the objective in Formulation 1. We conducted experiments to evaluate the techniques. The experiments are conducted using the real data from the UNOS kidney exchange that started in 2010. In that data we have the vertices that have a patient and one or more donors, and vertices that represent altruists. We also have patient and donor attributes, and we use the UNOS rules for determining compatibility of potential transplants (these rules take into account blood type, tissue type, creatinine, acceptable transplant centers, etc). So, in this master data set we effectively have a graph that has as its vertices all the vertices that have been in the UNOS exchange. All edges have unit weight.

the time between frames does not depend on what transplants the optimizer decides to put in each frame.) This discounting is already include in the objective in Formulation 1.

vertices from this master graph (and keep the edges between the selected vertices) to generate multiple problem instances, i.e., input graphs. For each value of the pool size, we repeat the experiment with 50 different random seeds. The operation frames DAG was chosen to be a total order.

The first experiment compares the standard model (Section 3.1) to our capped operation-frame-based model. In both cases, at most one donor from each pair is used. In both cases, the cap is four; this is a conservative experimental design because often in the standard model cycles are further capped to be at most length three, which would disadvantage the standard model compared to our approach. In both cases, we sample around 5% of the vertices to be altruists from the master graph and the rest are sampled uniformly from the nonaltruist vertices. Figure 5 shows that our approach yields a 34%-51% improvement via better-less myopic-planning even in this static setting.

In the UNOS pool, 5.7% of the non-altruist vertices have multiple willing donors, but at most one from each vertex will be used. The second experiment is exactly like the first, except that in the capped operation-frame-based model, up to two of the donors from each vertex can be used (i.e., αc = 2 for clubs c that have more than one donor). Figure 6 shows that this leads to a larger increase over the standard approach.

In the third experiment we sample more multi-donor pairs-roughly 10% of the entire pool. We do this to test how the system would perform if more multi-donor pairs would be present-as is conceivable in the future as knowledge about kidney exchange spreads and possibly also as multiple donors could actually be used. Figure 7 shows that allowing for up to

Pool size (number of clubs)

Figure 7: Improvement in the number of matches from allowing up to two donors to be used from each vertex compared to allowing only one donor from each vertex to be used.

two donors to be used from a vertex leads to an improvement over allowing only up to one to be used. In both cases, we use our capped operation-frame approach.

6 Conclusions and Future Research

Motivated by the reality of fielded kidney exchanges, in this paper we proposed significant generalizations to kidney exchange-and barter markets more generally. Specifically, we moved the model from individual and independent patient-donor pairs to the modeling concept of multi-donor and multi-patient organ clubs, where a club is willing to donate organs outside the club if and only if the club receives organs from outside the club according to expressed preferences. We proved that unlike in the standard model, the uncapped clearing problem is NP-complete.

We presented the notion of operation frames that sequence the operations across batches, and gave IP formulations that optimally clear these new types of markets. Experiments show that in the single-donation setting, operation frames improve planning by 34%-51%. Allowing up to two donors to donate in exchange for one kidney donated to their designated patient yields a further increase in social welfare.

Operation frames include a notion of time via the happensbefore ordering; yet, this does not capture the full dynamics of kidney exchange, where vertices and edges arrive and disappear over time. Finding an optimal matching policy for fully dynamic kidney exchange is an open problem from both the theoretical [ ¨Unver, 2010; Akbarpour et al., 2014; Anderson, 2014; Anderson et al., 2015a] and computational [Awasthi and Sandholm, 2009; Dickerson et al., 2012a; 2013; Dickerson and Sandholm, 2015; Glorie et al., 2015] points of view. Perhaps operation frames-with or without clubs-can be used to enhance planning even in those contexts as we showed it can in the static setting.

Exploring incentive issues in this new model is also interesting. Generalizations to the basic kidney exchange model have already enabled mechanisms that circumvent strong impossibility results [Hajaj et al., 2015; Ashlagi and Roth, 2014; Ashlagi et al., 2015; Toulis and Parkes, 2011]. The more expressive models presented in this paper could similarly result in advances in mechanism design.

Acknowledgments

This work was supported by NSF grants IIS-1617590, IIS1320620, IIS-1546752, and ARO awards W911NF-17-10082, W911NF-16-1-0061.