Male optimality and uniqueness in stable matching problems with partial orders

The stable marriage problem has a wide variety of practical applications, including matching resident doctors to hospitals, and stu- dents to schools. In the classical stable marriage problem, both men and women express a strict order over the members of the other sex. Here we consider a more realistic case, where both men and women can express their preferences via partial orders, i.e., by allowing ties and incompa- rability. This may be useful, for example, when preferences are elicited via compact preference representations like soft constraint or CP-nets that produce partial orders, as well as when preferences are obtained via multi-criteria reasoning. We study male optimality and uniqueness of stable marriages in this setting. Male optimality gives priority to one gender over the other, while uniqueness means that the solution is op- timal, since it is as good as possible for all the participating agents. Uniqueness of solution is also a barrier against manipulation. We give an algorithm to nd stable marriages that are male optimal. Moreover, we give suffcient conditions on the preferences (that are also necessary in some special case), that occur often in real-life scenarios, which guarantee the uniqueness of a stable marriage.