Stable Marriages with Multiple Partners: Efficient Search for an optimal solution.

We consider the many-to-many version of the original stable marriage problem posed by Gale and Shapley.

In our setup each man or woman has a strict preference ordering on the members of the opposite sex and wishes to be matched to upto his or her specified number of partners. We give a polynomial time algorithm for finding stable matching, which minimizes the combined sum of the ranks of partners across all men and women. We argue that this sum can be used as an optimality criterion for minimizing the total dissatisfaction if the preferences of individuals over partner combinations satisfy a no-complementary condition.

The technique used in the paper revolves around a new concept, meta-rotation, which extends the concept of rotation used for one-to-one matching problem. The results of this paper extend those known for the one-to-one version of the problem by Irving and Leather amongst others.