Mechanism design in kidney exchange programs

The Gale-Shapley algorithm (to compute a stable two sided matching) is a popular example of the use of elegant mathematics to solve an important real world problem. The algorithm led to tremendous growth in the field of matching theory. Research was conducted both on the strategic (see for example Alvin Roth’s book) and algorithmic aspects of  matching theory (see for example Gusfield and Irving’s book). The results have had impact such as on hospital-resident matching and kidney-exchange programs.

A major research problem has been to get a handle on honesty and incentive to lie in various matching settings. As Malkevitch states:

Another issue with respect to the honesty of the expressed preferences which are produced by the participants in the two-sided market has emerged from the analysis of what was done with choice mechanisms in the past...Researchers are now trying to study how to avoid this situation and get more "transparency."

In the kidney exchange setting, there can be an incentive for hospitals to conceal some of their patient and not enter them in a centralized kidney-exchange program with the aim to maximize the number of their own patients who get matched. One would ideally want a kidney matching mechanism which is strategy-proof, i.e., in which hospitals have no incentive to hide some of their patients. However, it is known that there can be no strategy-proof mechanism which is efficient (matches the possible number of patients). A natural question then is to seek a strategy-proof mechanism which at least guarantees a fraction of the maximum efficiency possible and where no exchange of money is allowed (for ethical or legal reasons). In this regard, there are some interesting results in a recent paper:

I. Ashlagi, F. Fischer, I. A. Kash, and A. D. Procaccia. Mix and match. 2010. 

The authors prove that if there are at least two agents, no deterministic strategy-proof mechanism can be more than 50% efficient and no randomized strategy-proof mechanism can be more than 75% efficient. The authors also present a polynomial time randomized 'MIX-AND-MATCH' mechanism which is strategy-proof and achieves at least 50% efficiency (in expectation). The authors also mention a few unanswered questions in the final section.

Comments

Post a Comment

Popular posts from this blog

Smart Lotteries in School Choice Ex-ante Pareto-Improvement with Ex-post Stability

Image
Working Paper: https://cgi.cse.unsw.edu.au/~haziz/PIRMES.pdf  Abstract: In a typical school choice application, the students have strict preferences over the schools while the schools have coarse priorities over the students based on their distance and their enrolled siblings. The outcome of a centralized admission mechanism is then usually obtained by the Deferred Acceptance (DA) algorithm with random tie-breaking. Therefore, every possible outcome of this mechanism is a stable solution for the coarse priorities that will arise with certain probability. This implies a probabilistic assignment, where the admission probability for each student-school pair is specified. In this paper, we propose a new efficiency-improving stable `smart lottery' mechanism. We aim to improve the probabilistic assignment ex-ante in a stochastic dominance sense, while ensuring that the improved random matching is still ex-post stable, meaning that it can be decomposed into stable matchings regarding the ...
Read more

Proportionally Representative Clustering

Image
H. Aziz, B. Lee, S. Morota Chu, and J. Vollen. Proportionally Representative Clustering.  WINE 2024 .  [  Pdf  ]  In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering— one of the fundamental tasks in unsupervised machine learning. We pro- pose a new axiom “proportionally representative fairness” (PRF) that is designed for clustering problems where the selection of centroids re- flects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair cluster- ing algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approxi- mation algorithm for the well-studied Proportional Fairness (PF) axiom [ 13 ]. Our algorithm for the discrete setting also matches the best kn...
Read more

Fair budgets from ranked ballots: PB-EAR

How do you split a shared budget fairly when people rank projects that cost very different amounts? PB-EAR, from our AAAI 2021 paper  Proportionally Representative Participatory Budgeting with Ordinal Preferences  ( AAAI version ), gives every voter an equal slice of the budget and lets groups pool their slices to fund the projects they rank highest, looking further down the ballots only when nothing is yet affordable. Every cohesive group is guaranteed its proportional share, and the rule extends our  Expanding Approvals Rule  for elections to budgets with project costs, ties and unequal voter weights.  That makes it a natural fit for DAO grant rounds such as   TheDAO Security Fund 's ETHSecurity Initiatives, where badge holders will rank the security initiatives listed on   the app  to allocate the fund's budget. The two-minute video below walks through a worked example. Here's an educational tool someone built to show how PB-EAR works. 
Read more