
- Previous Article
- FoDS Home
- This Issue
-
Next Article
Particle filters for inference of high-dimensional multivariate stochastic volatility models with cross-leverage effects
Combinatorial Hodge theory for equitable kidney paired donation
1. | Department of Computational Mathematics, Science and Engineering, Michigan State University, East Lansing, MI 48824, USA |
2. | Department of Mathematics, University of Tennessee, Knoxville TN 37996, USA |
Kidney Paired Donation (KPD) is a system whereby incompatible patient-donor pairs (PD pairs) are entered into a pool to find compatible cyclic kidney exchanges where each pair gives and receives a kidney. The donation allocation decision problem for a KPD pool has traditionally been viewed within an economic theory and integer-programming framework. While previous allocation schema work well to donate the maximum number of kidneys at a specific time, certain subgroups of patients are rarely matched in such an exchange. Consequently, these methods lead to systematic inequity in the exchange, where many patients are rejected a kidney repeatedly. Our goal is to investigate inequity within the distribution of kidney allocation among patients, and to present an algorithm which minimizes allocation disparities. The method presented is inspired by cohomology and describes the cyclic structure in a kidney exchange efficiently; this structure is then used to search for an equitable kidney allocation. Another key result of our approach is a score function defined on PD pairs which measures cycle disparity within a KPD pool; i.e., this function measures the relative chance for each PD pair to take part in the kidney exchange if cycles are chosen uniformly. Specifically, we show that PD pairs with underdemanded donors or highly sensitized patients have lower scores than typical PD pairs. Furthermore, our results demonstrate that PD pair score and the chance to obtain a kidney are positively correlated when allocation is done by utility-optimal integer programming methods. In contrast, the chance to obtain a kidney through our method is independent of score, and thus unbiased in this regard.
References:
[1] |
Ethical Principles to be Considered in the Allocation of Human Organs; 2010. Organ Procurement and Transplantation Network, Available from: http://optn.transplant.hrsa.gov/resources/ethics. |
[2] |
TN and US Kidney Transplant Summary; 2015. Scientific Registry of Transplant Recipients, Available from: http://www.srtr.org. |
[3] |
Spring 2014 Regional Meeting Data; 2014. United Network for Organ Sharing, Available from: https://www.unos.org/wp-content/uploads/unos/DataSlides_Spring_2014.pdf?75608d. |
[4] |
D. J. Abraham, A. Blum and T. Sandholm, Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges, In: Proceedings of the 8th ACM conference on Electronic commerce. ACM, 2007, 295–304. |
[5] |
I. Ashlagi, D. Gamarnik, M. A. Rees and A. E. Roth, The need for (long) chains in kidney exchange, National Bureau of Economic Research, 2012. |
[6] |
G. M. Danovitch,
The high cost of organ transplant commercialism, Kidney International, 85 (2014), 248-250.
|
[7] |
J. P. Dickerson, A. D. Procaccia and T. Sandholm, Price of fairness in kidney exchange, In: Proceedings of the 2014 International Conference on Automous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 2014, 1013–1020. |
[8] |
H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, American Mathematical Society, 2010. |
[9] |
J. Edmonds,
Paths, trees, and flowers, Canadian Journal of Mathematics, 17 (1965), 449-467.
doi: 10.4153/CJM-1965-045-4. |
[10] |
W. V. D. Hodge, The Theory and Applications of Harmonic Integrals, Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1989. |
[11] |
X. Jiang, L. H. Lim, Y. Yao and Y. Ye,
Statistical ranking and combinatorial Hodge theory, Mathematical Programming, 127 (2011), 203-244.
doi: 10.1007/s10107-010-0419-x. |
[12] |
J. B. Kessler and A. E. Roth,
Organ allocation policy and the decision to donate, The American Economic Review, 102 (2012), 2018-2047.
|
[13] |
D. P. Ladner and S. Mehrotra,
Methodological challenges in solving geographic disparity in liver allocation, JAMA surgery, 151 (2016), 109-110.
|
[14] |
L. F. Ross and E. Woodle, Kidney exchange programs: An expanded view of the ethical issues, In: Organ Allocation, Springer, 1998, 285–295. |
[15] |
A. E. Roth, T. Sönmez and Uktu ÜM, Kidney Exchange, National Bureau of Economic Research, 2003. |
[16] |
S. L. Saidman, A. E. Roth, T. Sönmez, M. U. Ünver and F. L. Delmonico,
Increasing the opportunity of live kidney donation by matching for two-and three-way exchanges, Transplantation, 81 (2006), 773-782.
|
[17] |
D. L. Segev, S. E. Gentry, D. S. Warren, B. Reeb and R. A. Montgomery,
Kidney paired donation and optimizing the use of live donor organs, Journal of the American Medical Association, 293 (2005), 1883-1890.
|
[18] |
D. J. Taber, M. Gebregziabher, K. J. Hunt, T. Srinivas, K. D. Chavin and P. K. Baliga, et al., Twenty years of evolving trends in racial disparities for adult kidney transplant recipients, Kidney International, 2016. |
[19] |
S. Takemoto, F. K. Port, F. H. Claas and R. J. Duquesnoy,
HLA matching for kidney transplantation, Human Immunology, 65 (2004), 1489-1505.
|
[20] |
P.anagiotis Toulis and D. C. Parkes, A random graph model of kidney exchanges: efficiency, individual-rationality and incentives, In: Proceedings of the 12th ACM Conference on Electric commerce, ACM, 2011, 323–332. |
[21] |
S. A. Zenios,
Optimal control of a paired-kidney exchange program, Management Science, 48 (2002), 328-342.
|
show all references
References:
[1] |
Ethical Principles to be Considered in the Allocation of Human Organs; 2010. Organ Procurement and Transplantation Network, Available from: http://optn.transplant.hrsa.gov/resources/ethics. |
[2] |
TN and US Kidney Transplant Summary; 2015. Scientific Registry of Transplant Recipients, Available from: http://www.srtr.org. |
[3] |
Spring 2014 Regional Meeting Data; 2014. United Network for Organ Sharing, Available from: https://www.unos.org/wp-content/uploads/unos/DataSlides_Spring_2014.pdf?75608d. |
[4] |
D. J. Abraham, A. Blum and T. Sandholm, Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges, In: Proceedings of the 8th ACM conference on Electronic commerce. ACM, 2007, 295–304. |
[5] |
I. Ashlagi, D. Gamarnik, M. A. Rees and A. E. Roth, The need for (long) chains in kidney exchange, National Bureau of Economic Research, 2012. |
[6] |
G. M. Danovitch,
The high cost of organ transplant commercialism, Kidney International, 85 (2014), 248-250.
|
[7] |
J. P. Dickerson, A. D. Procaccia and T. Sandholm, Price of fairness in kidney exchange, In: Proceedings of the 2014 International Conference on Automous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 2014, 1013–1020. |
[8] |
H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, American Mathematical Society, 2010. |
[9] |
J. Edmonds,
Paths, trees, and flowers, Canadian Journal of Mathematics, 17 (1965), 449-467.
doi: 10.4153/CJM-1965-045-4. |
[10] |
W. V. D. Hodge, The Theory and Applications of Harmonic Integrals, Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1989. |
[11] |
X. Jiang, L. H. Lim, Y. Yao and Y. Ye,
Statistical ranking and combinatorial Hodge theory, Mathematical Programming, 127 (2011), 203-244.
doi: 10.1007/s10107-010-0419-x. |
[12] |
J. B. Kessler and A. E. Roth,
Organ allocation policy and the decision to donate, The American Economic Review, 102 (2012), 2018-2047.
|
[13] |
D. P. Ladner and S. Mehrotra,
Methodological challenges in solving geographic disparity in liver allocation, JAMA surgery, 151 (2016), 109-110.
|
[14] |
L. F. Ross and E. Woodle, Kidney exchange programs: An expanded view of the ethical issues, In: Organ Allocation, Springer, 1998, 285–295. |
[15] |
A. E. Roth, T. Sönmez and Uktu ÜM, Kidney Exchange, National Bureau of Economic Research, 2003. |
[16] |
S. L. Saidman, A. E. Roth, T. Sönmez, M. U. Ünver and F. L. Delmonico,
Increasing the opportunity of live kidney donation by matching for two-and three-way exchanges, Transplantation, 81 (2006), 773-782.
|
[17] |
D. L. Segev, S. E. Gentry, D. S. Warren, B. Reeb and R. A. Montgomery,
Kidney paired donation and optimizing the use of live donor organs, Journal of the American Medical Association, 293 (2005), 1883-1890.
|
[18] |
D. J. Taber, M. Gebregziabher, K. J. Hunt, T. Srinivas, K. D. Chavin and P. K. Baliga, et al., Twenty years of evolving trends in racial disparities for adult kidney transplant recipients, Kidney International, 2016. |
[19] |
S. Takemoto, F. K. Port, F. H. Claas and R. J. Duquesnoy,
HLA matching for kidney transplantation, Human Immunology, 65 (2004), 1489-1505.
|
[20] |
P.anagiotis Toulis and D. C. Parkes, A random graph model of kidney exchanges: efficiency, individual-rationality and incentives, In: Proceedings of the 12th ACM Conference on Electric commerce, ACM, 2011, 323–332. |
[21] |
S. A. Zenios,
Optimal control of a paired-kidney exchange program, Management Science, 48 (2002), 328-342.
|











Blood Type | US wait-list | US whole | Uniform | ||
O | 48.6% | 44% | 25% | ||
A | 32.7% | 42% | 25% | ||
B | 14.9% | 10% | 25% | ||
AB | 3.8 % | 4% | 25% | ||
CPRA level | US wait-list | Uniform | |||
Low | 81.3% | 10% | |||
Med | 11% | 70% | |||
High | 7.7% | 20% |
Blood Type | US wait-list | US whole | Uniform | ||
O | 48.6% | 44% | 25% | ||
A | 32.7% | 42% | 25% | ||
B | 14.9% | 10% | 25% | ||
AB | 3.8 % | 4% | 25% | ||
CPRA level | US wait-list | Uniform | |||
Low | 81.3% | 10% | |||
Med | 11% | 70% | |||
High | 7.7% | 20% |
[1] |
Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks and Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295 |
[2] |
M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks and Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201 |
[3] |
Barton E. Lee. Consensus and voting on large graphs: An application of graph limit theory. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 1719-1744. doi: 10.3934/dcds.2018071 |
[4] |
Luigi Fontana, Steven G. Krantz and Marco M. Peloso. Hodge theory in the Sobolev topology for the de Rham complex on a smoothly bounded domain in Euclidean space. Electronic Research Announcements, 1995, 1: 103-107. |
[5] |
Hanqing Jin, Shige Peng. Optimal unbiased estimation for maximal distribution. Probability, Uncertainty and Quantitative Risk, 2021, 6 (3) : 189-198. doi: 10.3934/puqr.2021009 |
[6] |
A. C. Eberhard, J-P. Crouzeix. Existence of closed graph, maximal, cyclic pseudo-monotone relations and revealed preference theory. Journal of Industrial and Management Optimization, 2007, 3 (2) : 233-255. doi: 10.3934/jimo.2007.3.233 |
[7] |
Shi Jin, Dongsheng Yin. Computational high frequency wave diffraction by a corner via the Liouville equation and geometric theory of diffraction. Kinetic and Related Models, 2011, 4 (1) : 295-316. doi: 10.3934/krm.2011.4.295 |
[8] |
Marta Marulli, Vuk Miliši$\grave{\rm{c}}$, Nicolas Vauchelet. Reduction of a model for sodium exchanges in kidney nephron. Networks and Heterogeneous Media, 2021, 16 (4) : 609-636. doi: 10.3934/nhm.2021020 |
[9] |
Marcin Mazur, Jacek Tabor. Computational hyperbolicity. Discrete and Continuous Dynamical Systems, 2011, 29 (3) : 1175-1189. doi: 10.3934/dcds.2011.29.1175 |
[10] |
Bruce Hughes. Geometric topology of stratified spaces. Electronic Research Announcements, 1996, 2: 73-81. |
[11] |
Guizhen Cui, Wenjuan Peng, Lei Tan. On the topology of wandering Julia components. Discrete and Continuous Dynamical Systems, 2011, 29 (3) : 929-952. doi: 10.3934/dcds.2011.29.929 |
[12] |
Fengbo Hang, Fanghua Lin. Topology of Sobolev mappings IV. Discrete and Continuous Dynamical Systems, 2005, 13 (5) : 1097-1124. doi: 10.3934/dcds.2005.13.1097 |
[13] |
Robert Cardona. The topology of Bott integrable fluids. Discrete and Continuous Dynamical Systems, 2022 doi: 10.3934/dcds.2022054 |
[14] |
Renato Soeiro, Abdelrahim Mousa, Tânia R. Oliveira, Alberto A. Pinto. Dynamics of human decisions. Journal of Dynamics and Games, 2014, 1 (1) : 121-151. doi: 10.3934/jdg.2014.1.121 |
[15] |
D. Alderson, H. Chang, M. Roughan, S. Uhlig, W. Willinger. The many facets of internet topology and traffic. Networks and Heterogeneous Media, 2006, 1 (4) : 569-600. doi: 10.3934/nhm.2006.1.569 |
[16] |
Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. |
[17] |
Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17 |
[18] |
J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413 |
[19] |
John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16. |
[20] |
Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]