Алгоритм завершается, когда все мужчины нашли себе спутниц (и, поскольку обе группы численно равны, все женщины на этой стадии тоже помолвлены). А значит, нашими финалистами становятся:
Брэд – Скарлетт, Рассел – Адриана, Джордж – Рианна, Дэнни – Кира
И жили они счастливо (по крайней мере в чудесной стабильности) с тех самых пор.
Довольно легко принять то, что пары, сформированные по алгоритму Гейла – Шепли, останутся стабильными; но, чтобы устранить все сомнения, давайте это докажем. Если вам, мои читатели, не слишком по душе логический анализ и доказательства и если вы верите в то, что алгоритм Гейла – Шепли работает безупречно, приглашаю вас перейти сразу к следующей части.
Рад видеть, что вы решили остаться. Итак:
1. Ясно, что алгоритм не может продолжаться до бесконечности. В самом неблагоприятном варианте все мужчины сделают предложение всем женщинам.
2. Ясно, что число помолвленных мужчин всегда будет равняться числу помолвленных женщин. Также ясно и то, что, как только женщина помолвлена, она остается помолвленной (даже если меняется спутник). Кроме того, никто из группы по завершении процесса не может остаться вне помолвки. Достаточно сказать вот что: если Рон напишет «Нина» в своем списке предпочтений (пускай и на последнем месте), а никто другой с ней быть не захочет, она в конце концов Рону и достанется. И потому алгоритм гарантирует, что никто не останется без пары.
3. Но гарантирует ли он стабильность пар? Да – и мы это докажем. Представьте, что Йоко замужем за Джорджем, а Нина – за Полом. Возможно ли, что Йоко предпочтет Пола своему нынешнему супругу – и при этом понравится ему больше его жены, что поставит пары на грань предательства?
Ниже мы предположим, что это возможно, а потом коса найдет на камень – и логическое противоречие докажет, что это на самом деле невозможно.
Итак, предположим, у нас есть нестабильность – иными словами, две пары, Пол – Нина и Джон – Йоко, где Пола влечет к Йоко, а ее – к нему и оба желают быть друг с другом сильнее, чем со своими нынешними супругами. Согласно алгоритму, Полу следовало сделать Йоко предложение еще до того, как он отправился повидаться с Ниной (поскольку Йоко, по нашей предпосылке, получила более высокую оценку в его списке предпочтений). Теперь могут произойти два события:
А. Йоко соглашается на предложение Пола.
Б. Йоко отвечает отказом.
Если произошло событие А, то почему Йоко не живет с Полом? А потому, что выбрала того, кому поставила более высокую оценку, – Джона или кого-либо еще. В любом случае, если она сейчас с Джоном, значит, она оценила его выше, нежели Пола. Вот и обещанное логическое противоречие. Если случилось событие Б, тогда, выходит, Йоко отвергает Пола, поскольку у нее есть лучший спутник (Джон или кто другой), – и при этом тот факт, что сейчас она с Джоном, доказывает, что Джон получил более высокую оценку, нежели Пол, и наша исходная предпосылка вновь оказывается противоречивой.
