Algorithm to verify stable matching?

Question

I know using Gale-Shapley is guarantee to find a stable matching, but for a given matching, how do we verify that it is a stable matching? In other words, what conditions should I consider to validate that it is a stable matching?

Answer 1

First of all, if you obtained the matching through GS algorithm, it is guaranteed that :

the Gale-Shapley algorithm in which men propose to women always yields a stable matching that is the best for all men among all stable matchings

So there is no need to verify stability.

If you have a random matching and want to check if it is stable or not, you may refer to the definition of stable matching:

Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.

So it comes down to verify that no such pair exists. We only need to check every person's current partner against those higher in their ranking list. If one of those higher rank choices also prefers this person, then the matching is not stable.

Pseudo code:

for w in women:
    for m in [men w would prefer over current_partner(w)]:
        if m prefers w to current_partner(m) return false

return true

Answer 2

A matching mu is stable if two conditions are met:

• there is no agent i who prefers being unmatched to being matched to mu(i)

• there is no pair (i,j) such that i prefers j to mu(i) and j prefers i to mu(j).

In layman terms, a matching is stable if no divorce happens.

Then a pseudo code to check the stability of an arbitrary mu would be:

for w in women:
    if mu(w) in [men who are in w's preference list]:
        for m in [men w prefers over mu(w)]:
            if m prefers w to mu(m):
                return False
    else:
        return False

for m in men:
    if mu(m) not in [women who are in m's preference list]:
        return False

return True

Answer 3

Currently, I can think of three ways of doing so (in a two-sided matching market):

1. Doing a brutal force search like what provided by the previous answer by @jrook.
2. You run the Gale-Shapely algorithm twice, one is man-proposing, the other woman-proposing, as you probably know,

the man-proposing deferred acceptance is man-optimal, that it matches each man to his most favorable possible stable female partner, and is also woman-worst, that it matches each woman to her worst possible stable male partner. For the woman-proposing deferred acceptance algorithm, vice versa.

with this, you can get a range of possible stable partners on each man and woman's list, then you check whether your current matching partner lies in that range for each man and woman.

3. If you know the stable roommate problem or read the paper The Complexity of Counting Stable Marriages, you could apply an analogy of phase-I of that algorithm to get a range of possible stable partners, then check whether your current matching partner lies in that range for each man and woman.

In summary, they are pretty rough ideas of mine, as I haven't think carefully about how to implement it in code and evaluate their running time complexity. As far as I know, all of the above method could run in O(n^2) time, so considering the simplicity of implementing it, method one is not bad. I guess there shall be a more efficient way (maybe making use of the idea of the top-trading cycle). Please feel free to point out if I made any mistakes.

P.S.: the term "possible stable partner" refers to the case as described in the following example: if man m and woman w are matched in a stable matching, we say w is m's possible stable partner.