Изменения
→Анализ полученного алгоритмом паросочетания
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин.
|proof=
# Предположим <tex>A</tex>-<tex>c </tex> (<tex>A</tex>, <tex>B </tex> — мужчины; с, <tex>d </tex> — женщины; <tex>A </tex> женат на <tex>d</tex>, <tex>B </tex> женат на <tex>c</tex>) — стабильная пара в паросочетании <tex>S'</tex>, найденном алгоритмом Гейла-Шепли, но <tex>A </tex> не самый худший выбор для <tex>c</tex>. # Тогда существует стабильная пара в паросочетании <tex>S</tex>, в которой <tex>c </tex> замужем за <tex>B</tex>, который ''менее привлекателен'', чем <tex>A</tex>. Тогда пусть мужем <tex>d </tex> будет <tex>A </tex> в паросочетании <tex>S</tex># Получается <tex>A </tex> считает <tex>c </tex> ''более привлекательной'', чем <tex>d</tex>. Соответсвенно <tex>A</tex>-<tex>c </tex> — нестабильная пара в паросочетании <tex>S</tex>.
}}
