Optimizing for Fairness in Generalized Kidney Exchange: Theory and Computations

Claire S. Chang, Arin Khare, David B. Shmoys · 2026

Read Optimizing for Fairness in Generalized Kidney Exchange: Theory and Computations by Claire S. Chang, Arin Khare, David B. Shmoys (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-20070.txt.

Introduction

Claire Chang, Arin Khare and David Shmoys seek fairer kidney exchange beyond simple matching. Building on Roth, Sönmez and Ünver's use of the Edmonds-Gallai structure theorem, they ask how randomised matching can maximise fairness objectives such as Nash social welfare. They show strongly polynomial algorithms keep those fairness properties in weighted settings for matching and two-paths. A general bootstrapping result then extends fairness to any allowed structure via polynomial calls to an optimisation subroutine, backed by synthetic and real-data computations.

Catalog record

CREATORClaire S. Chang, Arin Khare, David B. Shmoys
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75826
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.20070

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimizing for Fairness in Generalized Kidney Exchange: Theory and Computations Claire S. Chang, Arin Khare, David B. Shmoys Abstract The seminal work of Roth, Sönmez, & Ünver shows that the Edmonds-Gallai structure theorem for non-bipartite matching can be leveraged to yield a randomized algorithm to match patient-donor pairs in kidney exchange with extraordinarily strong properties. This breakthrough led to randomized polynomial-time algorithms to find a maximum-cardinality matching maximizing individual fairness objectives—measured by the probability that nodes are matched—such as Nash social welfare. But the exchanges allowed in practice go beyond cardinality matching, generalizing to weighted variants and allowing structures such as paths and 3-cycles. We show that strongly polynomial algorithms guaranteeing the same fairness properties can be obtained in weighted settings for matching and 2-paths. While even maximum cardinality coverage with cycles and paths of length at least three is NP-hard, we provide a general result showing that any optimization subroutine (for whichever structure is allowed) can be bootstrapped using a polynomial number of calls to yield a mechanism that has analogous fairness properties to those obtained for matching. We complement these theoretical results with computational results, both on well-studied synthetic data-sets and on samples drawn from real data, that demonstrate the striking advantages of adding fairness considerations to more general kidney-exchange mechanisms. 1 Introduction To hasten the process for kidney transplants (with over 90,000 on the waiting list as of 2025 and most people waiting for deceased donors for 3-5 years [ 30 ] ), waiting list patients can look for living donors. However, many patients have willing but incompatible donors. To tackle this issue, kidney paired donation programs, such as the National Kidney Registry (NKR), the Alliance for Paired Kidney Donation (APKD), and UNOS’s kidney paired donation program in the United States, have been established in which incompatible patient-donor pairs can exchange donors with other incompatible pairs to find compatible matches. These exchanges are typically limited to pairs or triples of patient-donor pairs due to logistical and medical constraints: surgeries must be performed simultaneously to prevent reneging, so each pair that is included requires an additional operating room and surgical team. Another option is to include altruistic or nondirected donors (NDDs), who are willing to donate a kidney to any compatible patient. NDDs can start chains of donations that do not need to be performed simultaneously, allowing for longer chains and more transplants. The organizations use algorithms based on integer programming to match patient-donor pairs and NDDs based on compatibility and other factors [ 29 , 28 , 5 , 8 ] . However, an integer program yields only one solution, and it is left up to the whims of solvers to determine which pairs are included. Instead, we wish to randomize over the set of optimal solutions so that pairs can be included in an exchange with probabilities aimed to optimize a specified fairness function. The kidney exchange problem can be modeled as a directed graph where vertices represent patient-donor pairs or NDDs, and there is a directed edge from vertex A to vertex B if the donor of A is compatible with the patient of B. There may be weights on the arcs which represent, for example, the quality of the matches. An exchange corresponds to a collection of vertex-disjoint cycles and paths in this graph. Typically, the length of the cycle or path is bounded to be at most an \ell -cycle or \ell -path, where \ell is the number of arcs or exchanges made. In the context of exchanges with only 2-cycles, we can also view the graph as undirected with edges representing mutual compatibility, and exchanges as matchings. Two possible goals for this problem include (G1) finding a single packing that optimizes some objective or satisfies some constraints, or (G2) finding a lottery over the set of optimal packings that further optimizes some fairness criterion. The fairness criteria we consider will be a function of the probabilities with which each vertex is included in an exchange in the lottery. For instance, we may wish to maximize the smallest probability any vertex is included (maximin), or more generally lexicographically maximize the probabilities sorted in nondecreasing order (leximin). We can also try to maximize the sum of the probabilities (utilitarian, although this is equivalent to constraining to maximum-cardinality packings) or their product (Nash social welfare). One of the seminal works on paired kidney exchange by 29 focused on exchanges including only pairs of patient-donor pairs with dichotomous valuations (i.e., an unweighted undirected nonbipartite graph). Their goal falls into (G2): constructing a lottery over the set of all maximum-cardinality matchings with the goal of leximin fairness. This work builds on earlier work of 12 , who explained how to find the leximin solution for bipartite graphs. By leveraging the Edmonds-Gallai decomposition [ 17 ] , 29 were able to extend the algorithm to the nonbipartite setting. Furthermore, they proved that the leximin solution is Lorenz dominant over the space of maximum-cardinality exchanges in this space, so it also maximizes the Nash social welfare and any other concave function of the probabilities. Polynomial-time algorithms for finding the leximin solution in nonbipartite graphs were later presented in [ 20 , 23 ] using results on edge coloring and parametric flow. Unfortunately, allowing much more than 2-cycles makes the problem much more difficult. A later stream of work focuses on (G1), and considers the problem of finding a single packing of length at most \ell -cycles or \ell -paths, as well as incorporating edge weights. 13 present a polynomial-time algorithm for packing 1-paths and 2-paths, but show that the problem is NP-complete for almost any other family of graphs. However, for any constant \ell\geq 3 , finding a maximum-cardinality packing of \ell -cycles, even in undirected graphs, is NP-complete and APX-complete [ 1 , 11 ] . Thus as mentioned earlier, the focus has been on computational approaches involving integer programming formulations [ 29 , 28 , 5 , 6 , 8 ] . Other goals for (G1) arise from economics, where researchers have focused on incentive compatibility for hospitals to ensure truthful reporting of all patients [ 9 , 7 ] . Since (G2) is even more challenging than (G1), it is no surprise that literature in this area for the more general kidney exchange graph has also been focused on computational approaches for these more general settings. Integer programming techniques with constraint programming, and more successfully column generation, can be used to construct lotteries over the set of all optimal solutions [ 18 , 14 ] . This approach has found success not only in kidney exchange, but also in other areas such as selecting citizens’ assemblies [ 19 ] . Besides the computational hardness, there is also tension between the utilitarian and fairness objectives when we move past matching. In matching, it is well known that any non-isolated node can be included in some maximum matching. In the kidney exchange literature, 15 target highly sensitized patients that are hard to match, and explore the “price of fairness” to see what loss in efficiency results from prioritizing these patients, and 25 propose a hybrid mechanism that balances the two objectives. Our contributions. We show that given an

Read the complete text