Finding MAX-SMTI for Stable Marriage with Ties and Bounded Preference Lists

We consider a variant of the classical stable marriage problem in which preference lists may involve ties and the length of the lists may be bounded. Under the weak stability, stable matchings in such setting of preference lists can have different sizes. In this paper, a constraint satisfaction based algorithm to find a maximum cardinality weakly stable matching for a given instance of the problem is presented. From the constraint satisfaction point of view, the most constrained variable is defined to be the man who creates the maximum number of blocking pairs in the current matching, while the least constrained variable is the woman who is most preferred among women making blocking pairs with the man. Our algorithm starts with the initialization of a random matching. It then iteratively determines the most and the least constrained variables to remove all blocking pairs. We conducted experiments on various datasets. We offer a comparison against a well-known algorithm in the field (LTIU). Our experimental results confirm the efficiency of the proposed algorithm.