Let's say we have a problem that:

We have a set of n men and n women

M = {m1,m2...., mn} n men

W= {w1, ....., wn} n women

Def: "Perfect" matching is an 1-1 mapping between men and women

I.E : m1 — w1 m2 — w2 etc.

Any one to one mapping would be consider as perfect matching

Can use a set to denote perfect matching like

S = { (m1,w1),(m2,w2) }

In addition, each man/women can have a preference list

If we have this case:

Each man / women has a preference of others

 Intuitively, stable matching is a matching that for each pair, there's no desire in swtiching

So in the case above, {(m1,w2),(m2,w1)} will be a stable matching while {(w1,m1),(w1,m2)} won't be

Note: if only one of the person(node) prefer a new edge, the matching would still be stable

let's say we have the preference like this:

In this case, only w1 wants to switch to the dotted edge, so this matching is still stable

Formal Definition:

  A perfect matching S is unstable if there exists (m,w), (m', w') in S such that m prefers w' to w and w' prefers m to m' yet m is matched to w and m' is matched to w'