Research Publications

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 (for example, in matching residents to hospitals in the US, priority is given to the residents). Uniqueness means that the solution is optimal, since it is as good as possible for all the participat- ing agents. Uniqueness of solution is also a barrier against manipulation. We give an algorithm to nd stable marriages that are male optimal. We also provide a sucient condition on the preferences that guarantees that there is a male optimal stable marriage. Finally, we give another sucient condition on the preferences (that is also necessary in some special case), that occurs often in real-life scenarios, which guarantees the uniqueness of a stable marriage.