Задача о марьяже: как математика поможет найти идеальную пару?

Реалити-шоу о свиданиях с нетипичным подходом: на острове, где поселятся пять мужчин и пять женщин, создатели стремятся избежать любой драмы, в отличие от привычных шоу вроде «Love Island». Организаторы задумали, что все участники найдут себе пару и останутся вместе до конца программы без ревности и конфликтов. Этот необычный формат опирается на научную основу, известную как задача стабильного соответствия или задача стабильных браков.

Впервые эта задача была сформулирована математиками Дэвидом Гейлом и Ллойдом Шепли в 1962 году. Они показали, что при любом наборе мужчин и женщин, если у каждого из них есть свой список предпочтений, всегда можно найти стабильные пары, где никто не захочет сменить партнера, если только сам этот партнер не предпочтет другую пару. Основное условие стабильности — ни один участник не должен предпочитать кого-то другого, если этот другой также не предпочитает его.

Алгоритм, предложенный учеными, по сути работает так: каждый участник ранжирует всех представителей противоположного пола по степени предпочтения. Затем женщины (или мужчины) начинают предлагать «руку и сердце» своим топовым партнерам, а те, в свою очередь, отклоняют все предложения, кроме самого предпочтительного. Непарные участники продолжают делать предложения в следующем раунде, пока все не окажутся в стабильных отношениях.

Интересно, что тот, кто делает предложения первым, получает преимущество. Например, если женщины начнут первыми, они смогут получить более предпочтительных партнеров, чем мужчины. Это свойство алгоритма было замечено учеными при решении задач распределения студентов по университетам и студентов-медиков по больницам. Дальнейшие улучшения алгоритма также учитывали специальные случаи, например, когда студенты, состоящие в браке, хотят быть распределены в одно место.

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

Однако, как отмечают исследователи, алгоритм может унаследовать предвзятости из данных, на которых он основан. Например, исследования показывают, что в Нью-Йорке черные и латиноамериканские студенты реже получают доступ в топовые школы по сравнению с белыми и азиатскими сверстниками. Подобные проблемы наблюдаются и в распределении медицинских резидентов. Проблема кроется не в самом алгоритме, а в исходных данных и окружении, где он применяется. Решения включают использование более разнообразных и справедливых панелей для оценки кандидатов, а также корректировки алгоритма для учёта известных предвзятостей.

Несмотря на некоторые ограничения, этот алгоритм остается одним из самых надежных методов для поиска стабильных соответствий в различных сферах — от любви до образования.