2
$\begingroup$

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?
  2. What else can we say about this instance?
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 24 '15 at 16:37
  • $\begingroup$ What have you tried? What are your thoughts? Have you tried working through a few examples to get some intuition? $\endgroup$ – D.W. Oct 25 '15 at 3:48
3
$\begingroup$

I will answer your first question.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.