| We study the notion of stability in two-sided matching models which allow ties. It has been known that much of the structure associated with the set of stable matchings for the case without ties does not carry over to the general framework with ties. In particular, despite potential real life applications such as in school choice mechanisms, there has not been a computationally feasible algorithm to find a student-optimal stable matching, in contrast with the classical Gale-Shapley algorithm which achieves such optimality when there are no ties.;Our main result is a polynomial-time algorithm to compute a student-optimal stable matching when ties are allowed in students' and schools' preferences. |
