Question 9: Recall the Stable Matching problem: Stable Matching Input…

Recall the Stable Matching problem:

Stable Matching

Input: Two sets given by

• $M = \{m_1, \ldots, m_n\}$ (the men) and
• $W = \{w_1, \ldots, w_n\}$ (the women);

and two collections of rankings

• $\{\sigma_1, \ldots, \sigma_n\}$ (the ranking of the men over the women) and
• $\{\tau_1, \ldots, \tau_n\}$ (the ranking of the women over the men),

where for all $1 \leqslant i \leqslant n$, $\sigma_i$ is a strict ranking over $W$ and $\tau_i$ is a strict ranking over $M$.

Question: Find a permutation $\pi$ over $\{1, \ldots, n\}$ such that $\{m_i, w_{\pi(i)}\}_{i \in [n]}$ is a stable matching.

For completeness, we recall the definition of a stable matching.

Consider the matching $M := \{m_i, w_{\pi(i)}\}$ given by a permutation $\pi$ of $[n]$. A pair $(m_k, w_\ell)$ is said to be a blocking pair with respect to $M$ if:

• $\ell \neq \pi(k)$,
• $w_\ell$ is ranked higher than $w_{\pi(k)}$ in $\sigma_i$,
• $m_k$ is ranked higher than $m_q$ in $\tau_\ell$, where $\pi(q) = \ell$;

in other words, $m_k$ and $w_\ell$ are not matched by $M$, and they rank each other higher than their respective matched partners in $M$.

If $M$ is a matching for which there are no blocking pairs with respect to $M$, then $M$ is said to be a stable matching.

Consider the following instance of the stable matching problem for 4 men (PQRS) and 4 women (WXYZ).

P: W > X > Y > Z
Q: X > Y > Z > W
R: W > X > Z > Y
S: X > Y > W > Z

and

W: S > Q > R > P
X: P > S > Q > R
Y: R > P > Q > S
Z: R > P > S > Q

Consider the following matching: M = {(P, W), (Q, X), (R, Z), (S, Y)}.

Which of the following is a blocking pair in the matching above?