Egalitarian pairwise kidney exchange: fast algorithms vialinear programming and parametric flow
Jian Li, Yicheng Liu, Lingxiao Huang, Pingzhong Tang · 2014
We revisit the pairwise kidney exchange problem established by Roth Sonmez and Unver [23]. Our goal, explained in terms of graph theory, is to find a maximum fractional match-ing on an undirected graph, that Lorenz-dominates any other fractional matching. The Lorenz-dominant fractional match-ing, which can be implemented as a lottery of integral match-ings, is in some sense the fairest allocation and also enjoys the property of being incentive compatible. The original algorithm by Roth et al. runs in time exponential in the size of input. In this paper, we target at designing prac-tically efficient polynomial time algorithms for finding the Lorenz-dominant fractional matching. We start with a con-ceptually very simple algorithm, coined the water-filling al-gorithm. The water-filling algorithm is natural and allows