March  2019, 1(1): 87-101. doi: 10.3934/fods.2019004

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

* Corresponding author

Published  March 2019

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.

Citation: Joshua L. Mike, Vasileios Maroulas. Combinatorial Hodge theory for equitable kidney paired donation. Foundations of Data Science, 2019, 1 (1) : 87-101. doi: 10.3934/fods.2019004
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.Google Scholar

[2]

TN and US Kidney Transplant Summary; 2015. Scientific Registry of Transplant Recipients, Available from: http://www.srtr.org.Google Scholar

[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.Google Scholar

[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.Google Scholar

[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.Google Scholar

[6]

G. M. Danovitch, The high cost of organ transplant commercialism, Kidney International, 85 (2014), 248-250. Google Scholar

[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.Google Scholar

[8]

H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, American Mathematical Society, 2010. Google Scholar

[9]

J. Edmonds, Paths, trees, and flowers, Canadian Journal of Mathematics, 17 (1965), 449-467. doi: 10.4153/CJM-1965-045-4. Google Scholar

[10]

W. V. D. Hodge, The Theory and Applications of Harmonic Integrals, Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1989. Google Scholar

[11]

X. JiangL. H. LimY. Yao and Y. Ye, Statistical ranking and combinatorial Hodge theory, Mathematical Programming, 127 (2011), 203-244. doi: 10.1007/s10107-010-0419-x. Google Scholar

[12]

J. B. Kessler and A. E. Roth, Organ allocation policy and the decision to donate, The American Economic Review, 102 (2012), 2018-2047. Google Scholar

[13]

D. P. Ladner and S. Mehrotra, Methodological challenges in solving geographic disparity in liver allocation, JAMA surgery, 151 (2016), 109-110. Google Scholar

[14]

L. F. Ross and E. Woodle, Kidney exchange programs: An expanded view of the ethical issues, In: Organ Allocation, Springer, 1998, 285–295.Google Scholar

[15]

A. E. Roth, T. Sönmez and Uktu ÜM, Kidney Exchange, National Bureau of Economic Research, 2003.Google Scholar

[16]

S. L. SaidmanA. E. RothT. SönmezM. 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. Google Scholar

[17]

D. L. SegevS. E. GentryD. S. WarrenB. 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. Google Scholar

[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.Google Scholar

[19]

S. TakemotoF. K. PortF. H. Claas and R. J. Duquesnoy, HLA matching for kidney transplantation, Human Immunology, 65 (2004), 1489-1505. Google Scholar

[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.Google Scholar

[21]

S. A. Zenios, Optimal control of a paired-kidney exchange program, Management Science, 48 (2002), 328-342. Google Scholar

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.Google Scholar

[2]

TN and US Kidney Transplant Summary; 2015. Scientific Registry of Transplant Recipients, Available from: http://www.srtr.org.Google Scholar

[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.Google Scholar

[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.Google Scholar

[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.Google Scholar

[6]

G. M. Danovitch, The high cost of organ transplant commercialism, Kidney International, 85 (2014), 248-250. Google Scholar

[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.Google Scholar

[8]

H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, American Mathematical Society, 2010. Google Scholar

[9]

J. Edmonds, Paths, trees, and flowers, Canadian Journal of Mathematics, 17 (1965), 449-467. doi: 10.4153/CJM-1965-045-4. Google Scholar

[10]

W. V. D. Hodge, The Theory and Applications of Harmonic Integrals, Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1989. Google Scholar

[11]

X. JiangL. H. LimY. Yao and Y. Ye, Statistical ranking and combinatorial Hodge theory, Mathematical Programming, 127 (2011), 203-244. doi: 10.1007/s10107-010-0419-x. Google Scholar

[12]

J. B. Kessler and A. E. Roth, Organ allocation policy and the decision to donate, The American Economic Review, 102 (2012), 2018-2047. Google Scholar

[13]

D. P. Ladner and S. Mehrotra, Methodological challenges in solving geographic disparity in liver allocation, JAMA surgery, 151 (2016), 109-110. Google Scholar

[14]

L. F. Ross and E. Woodle, Kidney exchange programs: An expanded view of the ethical issues, In: Organ Allocation, Springer, 1998, 285–295.Google Scholar

[15]

A. E. Roth, T. Sönmez and Uktu ÜM, Kidney Exchange, National Bureau of Economic Research, 2003.Google Scholar

[16]

S. L. SaidmanA. E. RothT. SönmezM. 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. Google Scholar

[17]

D. L. SegevS. E. GentryD. S. WarrenB. 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. Google Scholar

[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.Google Scholar

[19]

S. TakemotoF. K. PortF. H. Claas and R. J. Duquesnoy, HLA matching for kidney transplantation, Human Immunology, 65 (2004), 1489-1505. Google Scholar

[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.Google Scholar

[21]

S. A. Zenios, Optimal control of a paired-kidney exchange program, Management Science, 48 (2002), 328-342. Google Scholar

Figure 1.  A three-way kidney exchange cycle. The PD pairs are numbered 1, 2, and 3 with P for patient and D for donor indicating an individual's role. Potential donations are indicated by red arrows from the donor to patient
Figure 2.  A graph with vertices $ a $ through $ e $ and an edge flow $ h $ defined on it via weights. For example, $ h(a,b) = 5 $ and $ h(b,e) = 11 $
Figure 3.  An edge flow and the process used to Hodge decompose it. (a) Original edge flow $ U $. (b) Space of cyclic flows, $ \ker(\Delta_1) $. (c) The globally cyclic portion $ V $ minimizing $ \left\| U-V \right\| $. (d) The gradient portion, $ W = U-V $. (e) A scoring made by assigning 0 to one vertex value. (f) A new scoring with mean 0
Figure 4.  The progression of Hodge Cycle on a tiny KEG. Green nodes are patients while red nodes are donors. Recorded cycles are dark and blue. Removed edges are unlabeled. (a) Initial KEG, $ U $. (b) Initial cyclic KEG, $ V_0 $. (c) One cycle allocated, $ V_1 $. (d) Two cycles allocated (empty)
Figure 5.  (Left) Patient score and CPRA. (Right) Donor score and representing patient CPRA. A comparison of vertex scores with patient CPRA values in KEGs with US proportions (Table 1). Both plots represent 50 random KEGs with 100 PD pairs each and show every PD pair. Underdemanded PD pairs with AB donors are marked with red Xs
Figure 6.  (Left) Patient score and CPRA. (Right) Donor score and representing patient CPRA. A comparison of vertex scores with patient CPRA values in KEGs with uniform proportions (Table 1). Both plots represent 10 random KEGs with 100 PD pairs each, and show every PD pair. Underdemanded PD pairs with AB donors are marked with red Xs
Figure 7.  (Left) Score pdfs for US average blood type and CPRA. (Right) Scoring probability densities for uniform blood type and CPRA. Probability density functions for the score of a random PD pair, given allocation by HC, TTCC, rCM, or WF. Each plot represents 50 random KEGs with (left) 50 PD pairs each or (right) 100 PD pairs each. Pairs without an obtainable cycle have been removed from the score determination
Figure 8.  (Left)US average blood type and CPRA. (Right) Uniform blood type and CPRA. Both plots show the chance to obtain a kidney via HC, TTCC, rCM, or WF as a function of PD pair scores (patient score minus donor score). The solid blue line indicates the range of occuring PD pair scores. These plots are likelihood ratios of the densities seen in Fig 7; specifically, these values are the conditional probabilities of being allocated a kidney given a particular score
Figure 9.  (Left) KEGs with US proportions and varying numbers of PD pairs. (Right) KEGs with 150 PD pairs and varying patient sensitivity. Both plots describe the average time for Hodge Cycle to find an allocation with one standard deviation error bars. Non-high CPRA patients are split evenly between low (0-10%) and medium (10-80%) CPRA
Figure 10.  (Left) KEGs with US proportions and 50 PD pairs each. (Right) KEGs with uniform proportions and 100 PD pairs each. Both plots show cross comparison of the percentage of patients who were allocated kidneys by HC to TTCC, rCM, and WF algorithms. Each point represents a single randomly generated KEG and its solution with the marked method
Figure 11.  (Left) KEGs with US proportions and 50 PD pairs each. (Right) KEGs with uniform proportions and 100 PD pairs each. Both plots compare average donation utility to number of patients allocated. Each point represents a single randomly generated KEG and its solution with the marked method. 0.75 is the expected average of all donation utilities in a KEG, since they are chosen uniformly between 0.5 and 1. The same KEGs are used for each solution method, and are the same as those used in Fig 10
Table 1.  (Top) Blood type proportions for generated KEGs. (Bottom) CPRA level proportions for generated KEGs. These are the multinomial probabilities used in practice. US averages from [2]. Specific CPRA is chosen uniformly within level range (0-10, 10-80, or 80-100%)
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 & 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 & 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 & Continuous Dynamical Systems - A, 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]

A. C. Eberhard, J-P. Crouzeix. Existence of closed graph, maximal, cyclic pseudo-monotone relations and revealed preference theory. Journal of Industrial & Management Optimization, 2007, 3 (2) : 233-255. doi: 10.3934/jimo.2007.3.233

[6]

Shi Jin, Dongsheng Yin. Computational high frequency wave diffraction by a corner via the Liouville equation and geometric theory of diffraction. Kinetic & Related Models, 2011, 4 (1) : 295-316. doi: 10.3934/krm.2011.4.295

[7]

Marcin Mazur, Jacek Tabor. Computational hyperbolicity. Discrete & Continuous Dynamical Systems - A, 2011, 29 (3) : 1175-1189. doi: 10.3934/dcds.2011.29.1175

[8]

Renato Soeiro, Abdelrahim Mousa, Tânia R. Oliveira, Alberto A. Pinto. Dynamics of human decisions. Journal of Dynamics & Games, 2014, 1 (1) : 121-151. doi: 10.3934/jdg.2014.1.121

[9]

Bruce Hughes. Geometric topology of stratified spaces. Electronic Research Announcements, 1996, 2: 73-81.

[10]

Guizhen Cui, Wenjuan Peng, Lei Tan. On the topology of wandering Julia components. Discrete & Continuous Dynamical Systems - A, 2011, 29 (3) : 929-952. doi: 10.3934/dcds.2011.29.929

[11]

Fengbo Hang, Fanghua Lin. Topology of Sobolev mappings IV. Discrete & Continuous Dynamical Systems - A, 2005, 13 (5) : 1097-1124. doi: 10.3934/dcds.2005.13.1097

[12]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[13]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17

[14]

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

[15]

John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.

[16]

Ioannis Baltas, Anastasios Xepapadeas, Athanasios N. Yannacopoulos. Robust portfolio decisions for financial institutions. Journal of Dynamics & Games, 2018, 5 (2) : 61-94. doi: 10.3934/jdg.2018006

[17]

Ying Li, Miyuan Shan, Michael Z.F. Li. Advance selling decisions with overconfident consumers. Journal of Industrial & Management Optimization, 2016, 12 (3) : 891-905. doi: 10.3934/jimo.2016.12.891

[18]

Feng Tao, Hao Shao, KinKeung Lai. Pricing and modularity decisions under competition. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2018152

[19]

Peter Giesl, Sigurdur Hafstein. Computational methods for Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : i-ii. doi: 10.3934/dcdsb.2015.20.8i

[20]

Shu Liao, Jin Wang, Jianjun Paul Tian. A computational study of avian influenza. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1499-1509. doi: 10.3934/dcdss.2011.4.1499

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]