# Stable Marriage Problem unique match

I'm having some thoughts and I'd like to have your opinion about it. Given a basic, normal instance of SMP (men-women, men choose), we define $\mu$ to be the set of all stable matches.

Each member of $\mu$ consists of men-rank, which describes the satisfaction index of the men - which in this case the member with the highest rank is the male-optimal match.

So if we run the stable-match known algorithm, the output would be the match with the highest rank, because the algorithm always returns the men-optimal and female-pessimal match - lets denote this match by $A$.

Now, lets replace the roles, and run the algorithm again. We denote the output match by $B$ - which is the female-optimal and male-pessimal match.

Assuming $A=B$:

1. Can we say that this instance has a unique stable match?
• Indeed, in this case there is a unique stable matching. This follows immediately from the definitions. You might want to work it out yourself to make sure you understand the definitions correctly. Oct 24 '15 at 16:37
• What have you tried? What are your thoughts? Have you tried working through a few examples to get some intuition?
– D.W.
Oct 25 '15 at 3:48

By definition, a matching $A$ is male-optimal if for any male $m$ and stable matching $C$, $A(m) \succeq_m C(m)$, that is, $m$ prefers $A(m)$ at least as much as $C(m)$, where $A(m)$ is the female assigned to $m$ by $A$.
Similarly, by definition, a matching $B$ is male-pessimal if for any male $m$ and stable matching $C$, $B(m) \preceq_m C(m)$.
Now suppose that $A$ is male-optimal, $B$ is male-pessimal, and $A = B$. Take any male $m$ and any stable matching $C$. By definition, $A(m) \succeq_m C(m) \succeq_m B(m) = A(m)$, and so $C(m) = A(m)$. In other words, $C = A$, and so the stable matching is unique.