Stable marriage and kidney exchange problems

Abstract

The purpose of this research thesis is to illustrate the concept of matching, with a special focus on matching algorithms. To do so, the paper deals with two matching problems, the stable marriage problem and the kidney exchange problem. A more theoretical part introduces the reader to the main notions of matching. It demonstrates the wealth of the stable marriage model through its numerous extensions and illustrates the progress that has been made so far in the exchange of kidneys. For both problems that have as a main objective to provide a solution that incites people to take part in the matching, models and algorithms are presented. The research thesis shows that for the stable marriage problem and its generalizations algorithms exist that provide stable allocations. For the kidney exchange problem, on the other hand, there are still disagreements on how an optimal solution can be obtained. Here, the models and algorithms have to make a trade-off between the efficiency and the fairness of the matching. A more practical chapter studies the performance of heuristics on a simplified version of the kidney exchange problem, the cycle formulation problem with cycles of size k ≤ 3 and of size k ≤ 4. Instances of up to 600 incompatible patient/donor pairs have been tested for cycles of size k ≤ 3 and up to 250 pairs for cycles of size k ≤ 4. The heuristics’ performance is compared to the performance of the cycle formulation problem’s integer programming model. The study of the optimization model and the study of four different heuristics, a random heuristic, a random ascent heuristic with destroy and repair method, and two list processing heuristics, one that establishes a ranking on the possible cycles and one that establishes a ranking on the participating pairs showed that (1) the inclusion of four-way exchanges has no big impact on the quality of the solutions, (2) a trade-off between quality and time has to be made for the four heuristics, and (3) due to the tight linear programming relaxation of the cycle formulation problem, the four heuristics have difficulty to outperform the runtimes of the integer programming model.