The Stable Marriage problem (SM)

Posted on 24th April 2019

What is SM?

In an instance of the Stable Marriage problem (SM) we have a set of men U and a set of women W. Each man ranks every women in strict preference order, and vice versa. A matching M in this context is an assignment of men to women such that no man or woman is assigned to more than one partner. Let M(mi) denote the woman man mi is assigned to in M and similarly, let M(wj) be the man woman wj is assigned to in M. A blocking pair of M is defined as a pair (mi, wj) such that mi is either unassigned or prefers wj to their currently assigned partner M(mi) and wj is either unassigned or prefers mi to their currently assigned partner M(wj). Were a blocking pair such as this to exist, mi and wj would have reason to break off their respective assignments and marry each other - hence the term blocking. A matching is stable if no blocking pairs exist.

Extensions

  • The Stable Marriage problem with Incomplete lists (SMI): SMI extends SM by allowing men to rank only a subset of women and vice versa.
  • The Stable Marriage problem with Ties and Incomplete lists (SMTI): An instance of SMTI allows men to be indifferent between two or more women on their preference list and vice versa. In SMTI there are several definitions of a blocking pair, which give rise to three different stability definitions:
    • Weak stability: A blocking pair has the same definition as in the SM case.
    • Strong stability: Either:
      • A pair (mi, wj) is a blocking pair of M if (1) mi is either unassigned in M or prefers wj to M(mi), and, (2) wj is either unassigned or prefers mi to M(wj) or is indifferent between them.
      • A pair (mi, wj) is a blocking pair of M if (1) mi is either unassigned in M or prefers wj to M(mi) or is indifferent between them, and, (2) wj is either unassigned or prefers mi to M(wj).
    • Super stability: A pair (mi,wj) is a blocking pair of M if (1) mi is either unassigned in M or prefers wj to M(mi) or is indifferent between them, and, (2) wj is either unassigned in M or prefers mi to M(wj) or is indifferent between them.

Posts