In this thesis we present stable and popular matchings in graphs with a strict preference function, some of their properties, and the connections between these two types of matchings. We also provide a step-by-step description and a proof of correctness for three algorithms for bipartite graphs with strict preferences: the Gale-Shapley algorithm for computing a stable matching, an algorithm for computing a maximum-size popular matching, and an algorithm for computing a matching that is popular among all matchings of at least the same size. We also prove that the sizes of the matchings returned by the algorithms are bounded from below in relation to the maximum matching of the graph.
|
