Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userKidney exchange and endless paths: On the optimal use of an altruistic donor
145
0
0.0
(
0
)
Added by
Avrim Blum
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider a well-studied online random graph model for kidney exchange, where nodes representing patient-donor pairs arrive over time, and the probability of a directed edge is p. We assume existence of a single altruistic donor, who serves as a start node in this graph for a directed path of donations. The algorithmic problem is to select which donations to perform, and when, to minimize the amount of time that patients must wait before receiving a kidney. We advance our understanding of this setting by (1) providing efficient (in fact, linear-time) algorithms with optimal O(1/p) expected waiting time, (2) showing that some of these algorithms in fact provide guarantees to all patients of O(1/p) waiting time {em with high probability}, (3) simplifying previous analysis of this problem, and (4) extending results to the case of multiple altruistic donors.
rate research
Read More
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 bodys ability to reject a transplanted organ up to the point that a transplant across blood- or 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.
To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient-donor pools. We consider a recent credit system where in each round, countries are given an initial kidney transplant allocation which is adjusted by a credit function yielding a target allocation. The goal is to find a solution in the patient-donor compatibility graph that approaches the target allocation as closely as possible, to ensure long-term stability of the international pool. As solutions, we use maximum matchings that lexicographically minimize the country deviations from the target allocation. We first give a polynomial-time algorithm for computing such matchings. We then perform, for the first time, a computational study for a large number of countries. For the initial allocations we use, besides two easy-to-compute solution concepts, two classical concepts: the Shapley value and nucleolus. These are hard to compute, but by using state-of-the-art software we show that they are now within reach for IKEPs of up to fifteen countries. Our experiments show that using lexicographically minimal maximum matchings instead of ones that only minimize the largest deviation from the target allocation (as previously done) may make an IKEP up to 52% more balanced.
Motivated by kidney exchange, we study the following mechanism-design problem: On a directed graph (of transplant compatibilities among patient-donor pairs), the mechanism must select a simple path (a chain of transplantations) starting at a distinguished vertex (an altruistic donor) such that the total length of this path is as large as possible (a maximum number of patients receive a kidney). However, the mechanism does not have direct access to the graph. Instead, the vertices are partitioned over multiple players (hospitals), and each player reports a subset of her vertices to the mechanism. In particular, a player may strategically omit vertices to increase how many of her vertices lie on the path returned by the mechanism. Our objective is to find mechanisms that limit incentives for such manipulation while producing long paths. Unfortunately, in worst-case instances, competing with the overall longest path is impossible while incentivizing (approximate) truthfulness, i.e., requiring that hiding nodes cannot increase a players utility by more than a factor of $1 + o(1)$. We therefore adopt a semi-random model where a small ($o(n)$) number of random edges are added to worst-case instances. While it remains impossible for truthful mechanisms to compete with the overall longest path, we give a truthful mechanism that competes with a weaker but non-trivial benchmark: the length of any path whose subpaths within each player have a minimum average length. In fact, our mechanism satisfies even a stronger notion of truthfulness, which we call matching-time incentive compatibility. This notion of truthfulness requires that each player not only reports her nodes truthfully but also does not stop the returned path at any of her nodes in order to divert it to a continuation inside her own subgraph.
In barter exchanges, participants directly trade their endowed goods in a constrained economic setting without money. Transactions in barter exchanges are often facilitated via a central clearinghouse that must match participants even in the face of uncertainty---over participants, existence and quality of potential trades, and so on. Leveraging robust combinatorial optimization techniques, we address uncertainty in kidney exchange, a real-world barter market where patients swap (in)compatible paired donors. We provide two scalable robust methods to handle two distinct types of uncertainty in kidney exchange---over the quality and the existence of a potential match. The latter case directly addresses a weakness in all stochastic-optimization-based methods to the kidney exchange clearing problem, which all necessarily require explicit estimates of the probability of a transaction existing---a still-unsolved problem in this nascent market. We also propose a novel, scalable kidney exchange formulation that eliminates the need for an exponential-time constraint generation process in competing formulations, maintains provable optimality, and serves as a subsolver for our robust approach. For each type of uncertainty we demonstrate the benefits of robustness on real data from a large, fielded kidney exchange in the United States. We conclude by drawing parallels between robustness and notions of fairness in the kidney exchange setting.
Current kidney exchange pools are of moderate size and thin, as they consist of many highly sensitized patients. Creating a thicker pool can be done by waiting for many pairs to arrive. We analyze a simple class of matching algorithms that search periodically for allocations. We find that if only 2-way cycles are conducted, in order to gain a significant amount of matches over the online scenario (matching each time a new incompatible pair joins the pool) the waiting period should be very long. If 3-way cycles are also allowed we find regimes in which waiting for a short period also increases the number of matches considerably. Finally, a significant increase of matches can be obtained by using even one non-simultaneous chain while still matching in an online fashion. Our theoretical findings and data-driven computational experiments lead to policy recommendations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
