Алгоритмы спасают людей: как алгоритм подбора пар сохраняет жизни

Задолго до возникновения сайтов знакомств двое экономистов решили отыскать формулу поиска совместимых пар и натолкнулись на формулу с применениями, выходящими далеко за рамки романтики.

Вы бы доверили экономисту устроить вам свидание?

Экономика часто ассоциируется с деньгами. Однако эта область выходит за пределы того, что можно (или нужно) монетизировать.

В 1960-е исследователи Дэвид Гейл и Ллойд Шапли занялись неожиданным предметом: подбором пар.

Частично финансируемые Управлением военно-морских исследований, они были заинтересованы в математике, которая помогла бы свести подходящих друг другу людей.

Предположим, есть группа мужчин и есть группа женщин, которые хотят пожениться. Гейл и Шепли хотели узнать, смогут ли они разработать формулу, по которой можно будет свести всех друг с другом настолько благополучно, насколько это возможно.

Вот пример, вдохновлённый романом Джейн Остин «Гордость и предубеждение»:

Цель состоит в том, чтобы найти устойчивые пары между двумя наборами людей с разными предпочтениями и мнением о том, кто лучше всего им подходит. Эта задача известна как задача о марьяже.

Основная мысль заключается в том, что пары должны быть стабильными: не должно быть двух человек, которые предпочитают друг друга их реальным партнёрам.

Гейл и Шепли разработали алгоритм отложенного согласия (также известный как алгоритм Гейла-Шепли).

Он вводит систему, посредством которой каждый может найти наиболее предпочитаемого человека среди тех, кто его предпочитает.

Мужчины и женщины оценивают свои предпочтения:

А затем они сортируются с помощью алгоритма:

Для любого числа партнёров, вне зависимости от того, как они оценивают друг друга, можно использовать алгоритм Гейла-Шепли, чтобы найти как минимум одну стабильную пару для каждого.

Весь алгоритм можно записать следующим образом:

• Мужчины делают предложение наиболее предпочитаемой женщине;
• Каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»;
• Мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
• Если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
• Если женщине пришло наилучшее предложение, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «да» и далее предложений не принимает;
• Шаги повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.

Максимальное количество шагов для реализации алгоритма: n² шагов, где n — число мужчин и женщин.

Но жизнь не роман Джейн Остин

Возможно, вы обратили внимание на то, что свидания и женитьба в реальном мире так не работают. Например, модель не учитывает гей-пары, бисексуальность или людей, которые предпочитают быть без пары.

Есть ли тогда толк от такого исследования? Оказывается, есть.

Гейл и Шепли на самом деле не пытались подчинить законы романтики. Они искали подход к так называемым сопоставимым рынкам — там, где есть спрос и предложение, но деньги не переходят из одних рук в другие. Брак был просто способом проиллюстрировать проблему.

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

Назначение новых докторов в больницы

В 1980-х экономист из Гарварда Эвлин Рот интересовался подходом к экономике как к инженерной дисциплине, который использовал бы теоретические идеи для улучшения реальных систем.

Он хотел определять сопоставимые рынки, которые не работали, и адаптировать алгоритм Гейла-Шепли, чтобы помочь им работать эффективнее.

При поддержке Национального научного фонда Рот решил взглянуть на Национальную программу распределения по ординатурам (National Residency Match Program, NRMP) — систему, которая назначает новых докторов в больницы по всей стране.

В 1990-е у NRMP были проблемы, так как и доктора, и больницы зачастую не были довольны назначениями.

Рот использовал работу Гейла и Шепли для изменения алгоритма распределения NRMP таким образом, чтобы получались наиболее стабильные назначения.

Распределение учеников по школам

Алгоритм Гейла-Шепли также пригодился крупным городским школьным округам в назначении новых учащихся в школы.

В Нью-Йорке, как и во многих других городах, ученики могут выбрать среднюю школу, дав оценку своим предпочтениям среди всех школ.

До того как Рот и его коллеги переработали процесс назначения, происходил сущий беспорядок. Около 30 000 учащихся в год попадали в школы, в которых совсем не планировали учиться.

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

Однако лежащий в основе принцип отложенного согласия, определённый Гейлом и Шепли, тот же самый.

Помощь в поиске доноров

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

В то время менее 20 человек в год получали почки от живых доноров, хотя трансплантаты от живых доноров дают гораздо лучшие результаты.

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

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

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

Это был прорыв, который принёс Шепли и Роту Нобелевскую премию в 2012 (Дэвид Гейл скончался в 2008).

Данный алгоритм теперь используется для разных целей, например, помогает детям-сиротам найти приёмных родителей.

В 21 веке ему нашлось применение даже в романтике, где он повлиял на подход к онлайн-знакомствам и быстрым свиданиям.

Путешествие открытия

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

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

Когда Гейл и Шепли начали свою работу, она была теоретической и абстрактной. Их исследования могли показаться странными и даже бессмысленными, но идеи, которые они выдвинули, создали основу для прорывов, которые улучшили жизни бесчисленного количества людей.

Сегодня около 5 500 пациентов в США, нуждающихся в пересадке, получают почки от живых доноров ежегодно.

Это не было бы возможным без работы Рота, Гейла и Шепли.

Как и в случае с любовью, пути исследований неисповедимы. Результаты и последствия порой неожиданны и непредсказуемы — и именно это делает эти исследования настолько важными.