Алгоритм романтических отношений
11 августа в лектории «Александрийская библиотека» прошла лекция математика Сергея Доценко «Экономика романтических отношений». Сергей рассказал про алгоритм Гейла-Шепли, разработанный в 1962 году как решение задачи устойчивых паросочетаний. Решение оказалось мало применимым для браков, зато полезным в найме сотрудников и даже трансплантологии!
Нобелевская премия по экономике 2012 года стала самой экстравагантной премией в истории. Её вручили американским учёным Дэвиду Гейлу и Ллойду Шепли за теорию устойчивого распределения и моделирование некоммерческих рынков. Некоммерческий рынок — это пространство, в котором действуют разные агенты, и каждый пытается достигнуть максимальной выгоды для себя. При этом на таком рынке нет денег. В результате своих исследований Гейл и Шепли вывели механизм справедливого распределения доходов и расходов, а также формулу устойчивого паросочетания. Однако применение полученных результатов ушло далеко за пределы любовной сферы.
Итак, Гейл и Шепли поставили задачу вывести такой алгоритм, который позволит из двух групп агентов (мужчин и женщин) создать такие пары, которые будут стабильны (устойчивы).
Возьмем пример. Допустим, у нас есть четыре женщины и четыре мужчины. В рамках подхода Гейла и Шепли каждый агент ранжирует агентов другого пола в порядке убывания симпатий. Далее алгоритм работает следующим образом:
- Каждый мужчина делает предложение женщине, которая стоит во главе его списка.
-
Женщине было сделано предложение: она соглашается, если этот мужчина есть в её списке (возможно, соглашается временно, то есть говорит «может быть»). Если женщине было сделано несколько предложений, она выбирает наиболее предпочтительного мужчину, а остальных отвергает.
-
В следующем туре: отвергнутые мужчины вычеркивают отказавшим им женщин из своего списка, делают предложение следующей кандидатуре. Мужчины, помолвленные в предыдущем туре, делают предложение тем же женщинам. Женщины, получившие несколько предложений, вновь выбирают наилучшее и отвергают остальные.
- И так до тех пор, пока все мужчины либо не будут иметь стабильные помолвки, либо не дойдут до конца списка.
В результате такого распределения гарантированно не будет блокирующих пар, то есть таких, где партнеры предпочитают чужих партнеров своим. При этом экономисты выяснили, что подобный механизм является наилучшим для каждого мужчины и наихудшим для каждой женщины. Такой алгоритм называется man-optimal. Если инициативу начнут проявлять женщины, то также будут обнаружены устойчивые паросочетания, но уже наилучшие для женщин и наименее выгодные для мужчин — woman-optimal алгоритм.
Сегодня по алгоритму американских учёных работают многие сайты знакомств, а американские вузы с опорой на него набирают студентов. Но Нобелевскую премию по экономике Гейл и Шепли получили после того, как учёный Элвин Рот адаптировал их алгоритм для распределения органов при трансплантации.
Как найденная формула помогает спасать тысячи жизней — смотрите в записи лекции Сергея Доценко.