💍Алгоритм Гейла-Шепли и 100 стабильных пар

Ну вот допустим, задумаемся, а зачем все эти названия, «задача о разборчивой невесте», «дилемма заключенного», «ошибка выжившего»? Ну вот смотрите, возьмём определение одной задачки:

Задача о нахождении стабильного паросочетания принимает в качестве входных данных равное количество участников двух типов (например, n мужчин и n женщин или n студентов-медиков и n стажёров), а также порядок предпочтений для каждого участника. Паросочетание называется стабильным, когда нет ни одной пары элементов разных типов, не входящей в это паросочетание, в которой оба предпочитают друг друга своей текущей паре.

Довольно скучно, да? Надо уже ценить математику чтобы с такого угорать. Поэтому приходится выкручиваться! Сравните:

100 мужчин и 100 женщин, у каждого есть список предпочтений всех представителей противоположного пола. Задача — составить пары так, чтобы никто не хотел сбежать с кем-то другим!

Веселее, да? :) Звучит как сущий кошмар для организаторов свадеб (да, такие люди тоже бывают), но два математика — Гейл и Шепли — в 1962 году придумали элегантное решение. А в 2012 получили за неё Нобелевку

Но расскажу я про решение завтра, а пока предагаю подумать, какая стратегия могла бы быть оптимальной. Как говорила одна нарисованная женщина, если есть Isle of Man, то должен быть и Isle of Woman, да?