Paper Info
Title
Egalitarian pairwise kidney exchange: fast algorithms vialinear programming and parametric flow.
Abstract
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 matching on an undirected graph, that Lorenz-dominates any other fractional matching. The Lorenz-dominant fractional matching, which can be implemented as a lottery of integral matchings, 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 practically efficient polynomial time algorithms for finding the Lorenz-dominant fractional matching. We start with a conceptually very simple algorithm, coined the water-filling algorithm. The water-filling algorithm is natural and allows us to present a simpler constructive proof that there exists a unique Lorenz-dominant fractional matching. The algorithm can be readily realized by a series of linear programs, each having an exponential number of constraints, and thus can be solved by the ellipsoid algorithm in polynomial time. However, it is known that the ellipsoid algorithm is not efficient in practice. To make the algorithm practical, we propose the second implementation based on a parametric flow computation on a carefully constructed flow network. Notably, the evolution of the parametric flow simulates exactly the water-filling algorithm. The second implementation only consists of a maximum matching computation and a parametric flow computation, both of which admit very efficient algorithms in practice.
Year
DOI
Venue
2014
10.5555/2615731.2615804
AAMAS
Keywords
Field
DocType
ellipsoid algorithm,fractional matching,algorithms vialinear programming,simple algorithm,maximum fractional matching,efficient algorithm,parametric flow computation,lorenz-dominant fractional matching,egalitarian pairwise kidney exchange,original algorithm,water-filling algorithm,efficient polynomial time algorithm
Graph theory,Flow network,Constructive proof,Dinic's algorithm,Computer science,Algorithm,Matching (graph theory),Parametric statistics,Time complexity,Ellipsoid method
Conference
Citations 
PageRank 
References 
8
0.61
12
Authors
4
Name
Order
Citations
PageRank
Jian Li181152.97
Yi-Cheng Liu24113.29
Lingxiao Huang3378.55
Pingzhong Tang413332.06