Two-sided Matching with Indifferences

    Aytek Erdil and Haluk Ergin
    September 2006

    In two-sided matching literature it has been a standard assumption that agents are not indifferent between any two members of the opposite side, despite the existence of such indifferences in various actual settings. A number of issues arise if such an assumption is abandoned and weak preferences are allowed. Most importantly, stability no longer implies Pareto efficiency, and the deferred acceptance algorithm can not be applied to produce a Pareto efficient or a worker/firm optimal stable matching.

    In this paper, we allow ties in preference rankings and explore the Pareto domination relation on stable matchings, as well as the two relations defined via workers’ welfare and firms’ welfare. Our structural results lead to fast algorithms to compute a Pareto efficient and stable matching, and a worker [or firm] optimal stable matching.