Стабильные мэтчинги в игре паросочетаний
Дана игра четырех мужчин и четырех женщин с предпочтениями $P$:
$$
\begin{align*}
P(m_1)&=w_1, w_4, w_2, w_3, & P(w_1)&=m_1, m_3, m_4, m_2, \\
P(m_2)&=w_3, w_1, w_2, w_4, & P(w_2)&=m_2, m_3, m_4, m_1, \\
P(m_3)&=w_2, w_3, w_4, w_1, & P(w_3)&=m_3, m_2, m_4, m_1, \\
P(m_4)&=w_1, w_2, w_3, & P(w_4)&=m_3, m_4, m_1, m_2.
\end{align*}
$$
$$
\begin{align*}
P(m_1)&=w_1, w_4, w_2, w_3, & P(w_1)&=m_1, m_3, m_4, m_2, \\
P(m_2)&=w_3, w_1, w_2, w_4, & P(w_2)&=m_2, m_3, m_4, m_1, \\
P(m_3)&=w_2, w_3, w_4, w_1, & P(w_3)&=m_3, m_2, m_4, m_1, \\
P(m_4)&=w_1, w_2, w_3, & P(w_4)&=m_3, m_4, m_1, m_2.
\end{align*}
$$
Подпункты
а)
Предъявите любой стабильный мэтчинг.
б)
Покажите, что результат работы алгоритма Гейла-Шепли зависит от того, кто делает первое предложение: мужчины или женщины.
в)
Найдите все стабильные мэтчинги.