Алгоритм Гейла-Шепли: Как математика создает идеальные пары
Рынки бывают разные. Если вы хотите купить яблоко, все решает цена: у кого есть деньги, тот и забирает товар. Но как быть с рынками, где деньги запрещены или не работают? Как распределить абитуриентов по ВУЗам, доноров почек — по пациентам, а женихов — по невестам?
Мэтчинги: Экономика без денег
В классической экономике цены балансируют спрос и предложение. Но в задачах, где важны взаимные симпатии (matching markets), ценового механизма нет. Университет ВШЭ не продает бюджетные места с аукциона — он хочет лучших студентов. А студент хочет в лучший ВУЗ. Возникает сложнейшая задача: как спарить элементы двух множеств так, чтобы все остались максимально довольны?
Чтобы распределение было успешным, оно должно быть стабильным (устойчивым). Что это значит на примере свадебного рынка?
Блокирующая пара (Угроза побега)
Мэтчинг называется нестабильным, если в нем существует хотя бы одна пара (Мужчина А и Женщина Б), которые сейчас не вместе, но при этом они оба предпочитают друг друга своим текущим партнерам. Если такая пара есть, они просто сбегут вместе (заблокируют распределение), и система рухнет.
Алгоритм отсроченного согласия (Deferred Acceptance)
В 1962 году математики Дэвид Гейл и Ллойд Шепли доказали потрясающую теорему: для любого набора предпочтений женихов и невест всегда существует хотя бы один стабильный мэтчинг. И они придумали элегантный алгоритм, как его найти (за что в 2012 году была вручена Нобелевская премия по экономике Элвину Роту и Ллойду Шепли).
Алгоритм Гейла-Шепли работает так:
- Шаг 1: Каждый свободный мужчина делает предложение своей самой любимой женщине.
- Шаг 2: Каждая женщина рассматривает все поступившие ей предложения. Она выбирает лучшего (для нее) мужчину из предложенных и говорит ему: «Возможно. Подожди на скамейке запасных» (отсроченное согласие). Остальным она жестко отказывает.
- Шаг 3: Отвергнутые мужчины вычеркивают отказавшую им женщину из своего списка и делают предложение следующей по приоритету женщине.
- Алгоритм повторяется, пока не останется отвергнутых мужчин. Пары, оставшиеся на «скамейке запасных», объявляются мужем и женой.
Интерактив: Свадебный рынок
Шаг 0: Старт: Все свободны
Мужчины готовы делать предложения своим самым любимым женщинам.
Мужчины
Женщины
Кто выигрывает в этом алгоритме?
Интересная особенность алгоритма Гейла-Шепли заключается в том, что он всегда благосклонен к той стороне, которая делает предложения.
В нашем симуляторе мужчины делали предложения. В результате образовавшийся стабильный мэтчинг является наилучшим из возможных для мужчин и наихудшим из возможных стабильных мэтчингов для женщин! Женщины пассивно ждали предложений, и им приходилось выбирать из того, что есть. Если бы мы перевернули алгоритм и заставили женщин делать предложения, пары могли бы получиться совсем другими (выгодными уже для женщин).
🧠 Олимпиадная задача: Общежитие Высшей школы экономики
Алексей, Борис, Владимир и Георгий поступили в университет и получили право жить в общежитии. На данный момент свободны 4 места в 4 разных комнатах (1, 2, 3 и 4). Ребята имеют различные предпочтения относительно комнат:
- Алексей: 1 > 2 > 3 > 4
- Борис: 1 > 3 > 4 > 2
- Владимир: 3 > 1 > 2 > 4
- Георгий: 4 > 1 > 2 > 3
Назовем распределение эффективным (по Парето), если они не могут поменяться комнатами так, чтобы никому не стало хуже и хотя бы одному стало лучше.
Задание:
а) Является ли эффективным распределение: Алексей—2, Борис—3, Владимир—4, Георгий—1?
б) Используйте алгоритм отсроченного согласия, чтобы найти хотя бы одно эффективное распределение, если ребята делают предложения комнатам, а комнаты отдают приоритет по алфавиту (А > Б > В > Г).
Математический разбор:
Часть А. Проверка на эффективность
Посмотрим на текущее распределение: (А-2, Б-3, В-4, Г-1).
У Бориса комната 3 (это его 2-й выбор). У Владимира комната 4 (это его 4-й выбор, самый худший!). У Георгия комната 1 (это его 2-й выбор).
Если Борис переедет в 1, Владимир в 3, а Георгий в 4, то:
- Борис получит 1 (его топ-1). Стало лучше!
- Владимир получит 3 (его топ-1). Стало лучше!
- Георгий получит 4 (его топ-1). Стало лучше!
Алексею (в комнате 2) не станет хуже. Значит, можно провести Парето-улучшение. Текущее распределение неэффективно.
Часть Б. Алгоритм Гейла-Шепли
Используем алгоритм. Студенты — "мужчины", комнаты — "женщины" (предпочитают по алфавиту А>Б>В>Г).
Шаг 1: Каждый подает заявку в топ-1 комнату.
Алексей ➔ 1. Борис ➔ 1. Владимир ➔ 3. Георгий ➔ 4.
Комната 1 получает заявки от А и Б. По алфавиту А лучше. Комната 1 удерживает Алексея и отказывает Борису. Комнаты 3 и 4 удерживают Владимира и Георгия.
Шаг 2: Отвергнутый Борис подает заявку в свой топ-2: Комнату 3.
Комната 3 получает заявку от Бориса. У нее уже есть Владимир. По алфавиту Б > В. Комната 3 бросает Владимира и забирает Бориса!
Шаг 3: Отвергнутый Владимир подает заявку в свой топ-2: Комнату 1.
Комната 1 имеет Алексея. По алфавиту А > В. Отказ Владимиру.
Шаг 4: Владимир подает заявку в топ-3: Комнату 2.
Она свободна. Владимир занимает комнату 2.
Вывод для олимпиады: Отвергнутых больше нет. Мы нашли стабильное (и Парето-эффективное) распределение: Алексей—1, Борис—3, Владимир—2, Георгий—4. В реальности для задач распределения студентов по общежитиям часто используют механизм TTC (Top Trading Cycles) или Диктаторство, но Гейл-Шепли также генерирует Парето-оптимальный исход для предлагающей стороны.
Жизнь спасает алгоритм
В 2004 году экономист Элвин Рот использовал модифицированный алгоритм Гейла-Шепли (Top Trading Cycles) для создания системы обмена донорскими почками в США (New England Program for Kidney Exchange).
Если жена хочет отдать почку умирающему мужу, но они не совместимы по группе крови, алгоритм находит огромные цепочки обменов по всей стране: жена отдает почку другому пациенту, жена того пациента — третьему, а третий донор — исходному мужу. Этот механизм, основанный на строгой математике мэтчингов, спас десятки тысяч жизней, доказав, что экономика — это не только про деньги.
Укротите теорию игр
Задачи на мэтчинги, цепочки обменов и блокирующие пары — это визитная карточка финалов Высшей Пробы по экономике. Научитесь распутывать их с n2tutor.
Дизайн рынков
Изучаем TTC, сериальную диктатуру и стратегическое манипулирование.
Поступление БВИ
Системная подготовка к перечневым олимпиадам I уровня.