Stable Matching Problem and an Application of Three Way Kidney Exchange Problem to 3-sided Cyclic Networks

Abstract

In the field of computer science, we study a lot of things, theoretically, which are not really implementable in the physical world. The concept of binary trees is one of many instances of such non-implementable CSE topics, as always we do not have the things getting recursively divided into two parts. Contrary to this, Stable Matching Problem (SMP), first introduced by two economists David Gale and Lloyd Shapley in the year 1962, provides us with a huge range of real world application areas. The justification of the name comes from the fact that in SMP we make stable pairings/matches between the entities of one set to the other retaining the stability between the matched pair. The root problem SMP, further gave rise to many child problems such as: (i) College Admissions Problem (ii) Stable Marriage Problem (iii) Stable Roommate Problem (iv) Hospital Resident Problem (v) Three Way Kidney-Exchange Problem (vi) Matching inputs/outputs in Switch Schedulers (vii) Processors/task matching (viii) Compiler/Register matching and so on.