.png)
Что общего между свахой и экономистом? Оба они могут решать одну задачу – свести людей. Идеальная пара для экономистов – это оптимальная пара, а романтический союз двух сердец – это алгоритм мэтчинга. Помочь людям создать семью, спасти жизнь человеку, нуждающемуся в пересадке органа, распределить детей по школам – решением этих задач занимаются экономисты, изучающие мэтчинги.
Анастасия Небольсина
Представьте себе группу мужчин и женщин, которых нужно разбить по парам так, чтобы все остались довольны, никому не было обидно, а союзы были стабильными. Экономисты называют это задачей о марьяже и решают ее с помощью алгоритма Гейла – Шепли, разработанного американскими экономистами Дэвидом Гейлом и Ллойдом Шепли, которые в 1960-е начали заниматься изучением мэтчингов.
Этот алгоритм создания оптимальных пар из группы мужчин и женщин выглядит следующим образом. Допустим, первый ход делают мужчины – выбирают женщин, которые им нравятся больше прочих, и предлагают создать пару. Тому, кто ей приглянулся, женщина обещает подумать, а остальных отвергает. Затем все отвергнутые мужчины идут к женщинам под № 2 в их рейтинге, и те выбирают фаворита между вновь пришедшими и тем, на ком остановили свой выбор на прошлом этапе. И так процедура будет повторяться до тех пор, пока все не разобьются по парам. Если предложения делают мужчины, то они получают наилучшую для себя партнершу. Если бы инициатива исходила от женщин, то итог мог бы быть иным.
Преимущество алгоритма в том, что он помогает создать стабильные пары: и женщины, и мужчины получают наилучшего партнера из всех, на кого могли рассчитывать, и если, допустим, мужчина захочет уйти к женщине, которая ему нравилась больше, чем его партнерша, то он будет отвергнут.
В жизни мы не выбираем партнера по алгоритму Гейла – Шепли (хотя и такое случается, о чем ниже). Но он применяется во множестве ситуаций. В 1980-е Элвин Рот, специалист в области теории игр и дизайна рынков, применил алгоритм Гейла – Шепли для распределения докторов по больницам в США. В то время больницы и врачи были не удовлетворены мэтчингом, и работа Рота помогла исправить ситуацию (о его книге «Кому что достанется – и почему» вы можете прочитать здесь).
Также Рот занимался разработкой алгоритма распределения органов для пересадки. Во многих странах продажа органов незаконна, поэтому их рынка не существует. В начале 2000-х очереди на пересадку почек были очень большими, и немногие пациенты получали органы, которые должны были спасти им жизнь. Рот предложил создать цепочки обмена почками: пару донор – реципиент, где органы были неподходящими, сопоставляли с другой такой парой, пока не удавалось найти две подходящие пары. Обе операции проводились примерно одновременно, чтобы избежать отказов доноров в последний момент. Это позволило выстраивать цепочки, в которых вплоть до 70 пациентов получали органы, что серьезно улучшило ситуацию с донорством.
Другой сферой применения мэтчинга стала система образования. Когда в 2004 г. Рот и его коллеги взялись за задачу распределить детей по школам, в Нью-Йорке с этим были большие проблемы – только около 50 000 из 100 000 школьников получили приглашения от школ, 17 000 из них – несколько приглашений, около 30 000 учащихся попали не туда, куда хотели, а то и вовсе не были записаны в школу. Рот с коллегами применили алгоритм Гейла – Шепли, и около 70 000 учащихся оказались именно в тех школах, где хотели учиться (т. е. указывали в своем списке предпочтений). После повторного уточнения предпочтений и распределения между школами, где остались места, еще 7600 учащихся получили места в школах, куда хотели попасть.
За свои достижения Шепли и Рот получили Нобелевскую премию по экономике в 2012 г. (Гейл скончался несколькими годами ранее). Сейчас алгоритм Гейла – Шепли и его модификации применяются в самых разных сферах, в том числе для выбора партнера в приложениях для знакомств. Иными словами, любовь по алгоритму все же возможна…
(О работе приложений для знакомств можно почитать в колонке выпускницы РЭШ Анны Щеткиной, которая учится на PhD в Уортонской школе бизнеса при Пенсильванском университете. Также мы рекомендуем лекцию профессора Массачусетского технологического института Парага Патака, соавтора Элвина Рота, о том, как внедрялся алгоритм распределения детей по школам, и лекцию профессора Калифорнийского университета в Беркли Халука Эргина о методах дизайна экономических механизмов, которые позволяют оптимально организовывать одновременные пересадки органов, когда доноры не подходят друг другу напрямую).
