In this thesis, we examine the search for stable matchings and the search for fair stable matchings. We formulate the problem itself and describe the Gale–Shapley algorithm for finding a stable matching. We look at the extreme matchings obtained by the algorithm and demonstrate their optimality for each side, as well as the ordering of the other matchings between them. Using rotations on the preference lists, we explore how to find other stable matchings and how to enumerate them. Finally, we focus on finding stable matchings that are fair. We present four different measures of fairness, the egalitarian measure, the balanced measure, the gender-equal measure, and the minimum regret measure. We compare these measures to one another and evaluate their fairness. For each measure, we explain how to find such a matching using the procedures described in the previous chapter, which define the different time complexities for finding each matching.
|
