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

9081
4

Формула любви — это совсем не о цветочках, сердечках и ужинах при свечах. Это — математический алгоритм, который вывели двое ученых, пытаясь создать схему для подбора идеальных брачных партнеров. Но оказалось, что решение задачи о марьяже не применимо в делах сердечных, зато показывает очень хорошие результаты в других областях — к примеру, в трансплантологии или образовании. О том, как «формула любви» работает на благо человечества, в колонке на Medium рассказали ученые из Калифорнийского университета. Мы же предлагаем вам ее перевод.

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

Позволили бы вы экономисту организовать ваше свидание?

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

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

1 KyXDDH007fDh2pZ0GA81Tw

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

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

1 uD6C_sJORbJ6jFBZqOkH6Q

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

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

1 T_wJcwVUPkB2I-IyAW2yXg

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

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

1 mNtOmBvaWPI0h-ujmh2mNA

Затем их сортируют, используя алгоритм.

1 4LMVIviLozFECMLkTHKZWQ

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

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

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

Так в чем же ценность этого исследования? Оказывается, она огромна.

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

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

Назначение врачей в больницы

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

1 CG9GPE_JNo95clfIIoNKpw

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

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

Рот использовал алгоритм, чтобы переделать схему подбора врачебного персонала, которую использовали в NRMP, так чтобы получившиеся пары «врач-больница» были более стабильны.

Назначение учащихся в государственные школы

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

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

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

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

Но базовый принцип отложенного согласия, определенного Гейлом и Шепли, оставался тем же самым.

Подбор доноров органов пациентам, нуждающимся в пересадке

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

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

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

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

1 EI4SVLKYx1bT6bRt5opnqQ

Группы крови: А, В, AB и O

 

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

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

Формуле сейчас нашли другое применение: помогать детям в приютах находить семьи. А в XXI столетии ее даже начали применять «по назначению»: на дейтинговых сайтах и в спид-дейтинге.

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

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

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

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

Сегодня каждый год около 5000 пациентов в США получают почки от живых доноров. Эти счастливые совпадения были бы невозможны без работ Гейла, Шепли и Рота.

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

Оставить комментарий

Комментарии | 4

  • не читал, но у меня 2 вопроса:
    1. на первом изображении пример идеальной пары?
    2. рассчитан ли алгоритм на то что людям временами хочется иметь других разных людей

  • «В 1960-х исследователи Девид Гейл и Ллойд Шепли приступили к федеральному исследованию по подбору идеальной пары. Им была интересна математика»

    В этой области с начала прошлого века существует предельно эффективный метод решения задачи о назначениях — венгерский алгоритм (описанный в англоязычной литературе в 1955 году). Он позволяет найти точное решение задачи оптимального паросочетания (например, разбить на оптимальные пары 50 невест и 50 женихов) за полиномиальное время.

Поиск