I heard that the stable matching of a roomate problem might not exist.
My question is, what is a simple example illustrating the non-existence, and if there is simpler matching problem where stable matching does not exist?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Consider three individuals with preferences $\succ_1, \succ_2$ and $\succ_3$.
Consider the following preferences (for matchings) $$ \begin{align*} &2 \succ_1 3 \succ_1 \emptyset\\ &3 \succ_2 1 \succ_2 \emptyset\\ &1 \succ_3 2 \succ_3 \emptyset. \end{align*} $$ Here $\emptyset$ is the situation where the individual is not matched.
- If 1 is matched with 2, the couple (2,3) forms a blocking pair.
- If 1 is matched with 3, the couple (1,2) forms a blocking pair.
- If 2 is matched with 3, the couple (1,3) forms a blocking pair.
