Variants of Stable Marriage Problem

In this article, we will take a look at the variants of stable marriage problem. We have already discussed the Stable Marriage problem and it's solution (Gale Shapley Algorithm) in detail in a seperate article. Here, we will be looking at certain parameters or conditions that are added to the existing problem to make it more generic and real world. This includes indifference and incomplete lists.

Gale and Shapley proved that for any instance of the Classical Stable Marriage problem, there exists at least one solution which can be obtained using the Gale Shapley Algorithm. This algorithm takes O(n^2) time for an input of size n. They also noted that the result came out to be man optimal i.e every man was paired with the best partner he could have in any possible matching.
McVitie and Wilson later noted that the man-optimality was at the cost of women's choice. Each women was paired with the worst partner that she could have in any possible matching. Hence, a man optimal matching can be considered a woman pessimal matching.
Gusfield and Irving noted that whatever be the order of proposals by men, the resulting matching will always be same.

Egalitarian Stable Matching

If M(m,w) is the rank of woman w in man m's list, and
W(m,w) is the rank of man m in woman w's list, then the 'man optimal matching algorithm' (obtained by Gale Shapley) will try to:

Minimize sigma (M(m,w))
and
Maximize sigma(W(m,w)).
To obtain a stable matching that does not discrimiate participants on the basis of theeir gender, egalitarian stable matching is used.

According to this,
sigma of(M(m,w) + W(m,w)) is minimized
giving the benfit to both parties by minimizing the cummalative ranks. An egalitarian matching can be found out in O(n^4) time, although an optimized aith O(n^2.5 * logn) exists.

Minimum Regret Stable Matching

For a person x, regret can be defined as the rank of x's partner(obtained by stable matching algorithm) in x's preference list. Regret, of a stable matching M, is defined as the maximum regret of a person in the match. It is a parameter to describe the condition of the worst affected person in the matching. A matching with minimum regret makes sure that all the participants have low regret values, making it a successful match.
Minimum regret Stable matching can be found in O(n^2) time.

Indifference

Stable marriage problem with indifference is a slight variation of the classical stable marriage problem. By indifference we mean that, there is a possibility of a person having no top preference, meaning that more than one people can be ranked at the same position. This is quite plausible in our day to day life. Hence, introducing indifference in stable matching problem makes it more intutive and apt for general usage.
For example: Suppose you love chocolate and butterscotch flavors equally, we can say that you are indifferent to both the flavours or maybe you cannot decide which one you like more.
The most natural form of indifference involves Ties.

Stable marriage with ties

To re-evaluate the stable marriage with blocking pairs. A pair can be viewed as a blocking pair if:

• If both the people are better off, or
• Neither would be worse off, or
• One would be better off and the other no worse off.

These 3 possibilities give rise to the notions of

1. Weak stability
2. Super stablility
3. Strong stability, respectively.

Weak Stability

This notion is the weakest of the 3.In this case, a pair which does not appear in a stable matching M, blocks M, if each member of the pair prefers the other to their partner in M. If there is no blocking pair for M, M is said to be weakly stable.

Super Stability

This notion is the strongest of the 3. In this case, a pair which does not appear in a stable matching M, blocks M, if each member of the pair prefers the other to their partner in M, or is indifferent between them. If there is no such blocking pair for M, M is said to be super-stable.

Strong Stability

This is notion lies between the other 2. It can be considered of intermediate strength. In this case, a pair which does not appear in a stable matching M, blocks M, if one member of the pair prefers the other to their partner in M while the other is at least indifferent. If there is no such blocking pair for M, M is said to be strongly stable.

Stable marriage with incomplete lists

When the preference lists are incomplete, the 3 notions of stability yield a slightly different result.
Incomplete lists mean that the lists can contain less than n people where n is the number of participants in each set. This give rise to the possibility that a person can remain unmatched even after participating the matching.

1. Weak Stability
2. Super Stability
3. Strong Stability

Some other useful algorithms

1. HRT
2. SRTI
3. SF
4. SFT Super
5. MinReg
6. POSET2
7. SUPER2