Weak Stable Matchings with Tenants and Ties
(Extended Abstract)

Ana Paula Tomás

DCC-FC & LIACC, Universidade do Porto
R. do Campo Alegre 823, 4150-180 Porto, Portugal
Phone: 351 22 6078830, Fax: 351 22 6003654
April 2006

Abstract

The paper addresses a variant of the stable marriage problem that models a job recruitment problem in which applicants are strictly ordered by priority but their preference lists may have ties. Some applicants may hold a post initially. These posts may be assigned to other applicants if their holders get another post. By reducing the problem to a sequence of maximal cardinality bipartite matching problems, combined with an effective propagation of the stability constraints, we show that applicant-optimal stable matchings may be found efficiently.