Сегодня хотим рассказать вам про задачу о стабильных браках. Ещё её называют задачей о марьяже.

Несмотря на то, что её классическая формулировка описывает поиск наилучшего супруга/супруги, в реальности эта задача нашла широчайшее применение. Недаром в 2012 за её решение авторов удостоили Нобелевской премии по экономике (хотя решение было опубликовано аж в 1962 году).

С помощью описанного алгоритма ординаторы и интерны находят потенциальные больницы для работы, студенты выбирают школы/колледжи, команды нанимают спортсменов, фирмы — стажёров или работников, интернет-пользователям назначается сервер. А ещё адаптация этого алгоритма помогает находить попутчиков или соседей по квартире.

Итак, пусть есть N мужчин и N женщин, все гетеросексуальны (иначе нужен другой алгоритм). Пусть у всех есть свой список предпочтений, то есть они могут упорядочить особей противоположного пола в порядке убывания привлекательности вот лично для себя.
Требуется составить устойчивые пары, из которых никто не хочет сбежать с кем-то другим. То есть не должно быть ситуаций, когда вам нравится чужая жена больше, чем своя, и при этом чужая жена тоже предпочитает вас своему мужу.

И было доказано, что алгоритм нахождения устойчивых пар существует! Правда счастья он никому не обещает.
Но зато теорема утверждает, что решение есть для любого N, оно находится за конечное (хотя и довольно большое) количество шагов, и что оно подбирает наилучшую пару для «активной стороны» — то есть для того пола, который делает предложение.

Наглядно данный алгоритм описан в этом видео, а в дополнении к нему поясняют доказательство и рассказывают про применения алгоритма в реальности. Советуем посмотреть оба видео. 😊

И пусть любой выбор в вашей жизни будет не только оптимальным, но и счастливым! 🥂