Two Sided Matching with Indifferences

NOELIA MARIEL JUAREZ

Buenos Aires

Congreso; IV Congreso de Matemática Aplicada, Computacional e Industrial; 2013

Universidad Tecnologica (UTN) Almagro

    We study the lattice structure on equivalence classes of stable matchings in the marriage model with indifferences. This result is one of the most significant in the matching literature. This structure is important for at least two reasons. First, it indicates that even if agents of the side of market compete for agents of the other side, this conflict is attenuated since, on the set of stable matchings, agents of the same side have a coincidence of interests. Second, it has proved to be very useful: many algorithms that yield stable matchings (and are used in real centralized markets) are based on this lattice structure. The lattice structure of the stable matching set for the marriage model (with strict preferences) was first established by Knuth (1976), who attributed the result to Conway.    Let us consider a bilateral market with two finite disjoint sets M and W, the sets of men and women respectively. Each man has preferences over the women, and each woman has preferences over the men. We allow indifferences in these preferences.    Roth and Sotomayor (1990) exhibited examples in which, under indifferences, the results of the classical model are not valid.    A matching μ is called stable if all agents have acceptable partners and there is no unmatched men-women pair who both would strictly prefer to be matched to each other rather than staying with their current partners.    Two matchings defined a cycle if the agents forms a closed set, who are indifferent between both matchings. A model with indifferences (M,W,R), satisfies the cycle property if for all pair of stable matchings forms a cycle.    Let (M,W,R) a model with indifferences that satisfies the cycle property, we define an equivalence relation over stable matching set. Since the relation defined over the stable matching set is an equivalence relation this define a partition (of stable matching set) on the representative of each partition. We show the lattice structure and the hospital rural theorem over equivalence classes of the stable matching set of the model with indifferences.    The classical model (with strict preferences) satisfies the cycle property trivially because each representative class only has one stable matching.    A matching μ is called strongly stable if all agents have acceptable partners and there is no unmatched men-women pair who either one of them would weakly prefer to be matched and the other strictly prefer to be matched to each other rather than staying with their current partners.    Manlove (2002) studied the strongly stable matching set, he proved that this set forms a distributive lattice, when it is partitioned by a suitable equivalence relation. In this paper, we show that this lattice, on equivalence classes of the strongly matching set, is a sublattice to the lattice on equivalence classes of the stable matchings.