Алгоритм Гейла-Шепли
- Автор метода
- David Gale, Lloyd Shapley
- Год
- 1962
- Тип
- algorithm
- Семейство
- Game-theoretic
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Алгоритм Гейла-Шепли решает задачу стабильного брака: как сопоставить две группы (например, ординаторов с больницами, студентов со школами) таким образом, чтобы ни одна пара не предпочла друг друга своим назначенным партнерам.
Представленный Дэвидом Гейлом и Ллойдом Шепли в 1962 году, алгоритм гарантирует стабильное сопоставление за полиномиальное время посредством процесса отложенного принятия, в котором одна сторона делает предложения последовательно, а другая сторона отвечает, пересматривая выбор по мере появления лучших вариантов.
Интуиция метода
Представьте себе сопоставление врачей с больницами. Алгоритм работает как игра в "музыкальные стулья": каждый врач делает предложение наиболее предпочтительной для него больнице; каждая больница предварительно принимает лучшего доступного врача. По мере того как больницы получают лучшие предложения, они пересматривают свой выбор, потенциально отказываясь от предыдущих принятий. Отклоненные врачи делают предложения следующей по предпочтительности больнице. Процесс продолжается до тех пор, пока ни один врач не захочет делать дальнейшие предложения, и ни одна больница не захочет менять своего текущего партнера. Результат стабилен: ни одна пара врач-больница не предпочла бы быть сопоставленной друг с другом, а не со своими назначенными партнерами.
История
Дэвид Гейл и Ллойд Шепли опубликовали свое решение задачи стабильного брака в 1962 году, доказав, что стабильные сопоставления всегда существуют для двусторонних рынков. Их алгоритм породил обширную литературу по теории сопоставлений с приложениями в медицине, образовании и на рынках труда. В 2012 году Элвин Рот получил Нобелевскую премию по экономике за экспериментальную и теоретическую работу по применению теории сопоставлений к дизайну реальных рынков, подтвердив практическую важность фреймворка Гейла-Шепли.
Когда применять
Применяйте алгоритм Гейла-Шепли при сопоставлении двусторонних рынков, где стабильность имеет решающее значение: распределение медицинских ординаторов, распределение студентов по школам, обмен почками, сопоставление на рынке труда или рынки онлайн-знакомств. Используйте, когда существует риск нестабильности сопоставления (блокирующих пар), которая может разрушить сопоставление после назначения. Алгоритм идеален, когда одна сторона может действовать первой со стратегическим преимуществом.
Ограничения и замечания
- Не является Парето-оптимальным: сопоставление может не максимизировать общее благосостояние; могут существовать блокирующие пары, которые могли бы выиграть от обмена партнерами
- Стратегическая уязвимость: предлагающая сторона может получить выгоду, искажая предпочтения, в то время как отвечающая сторона действует правдиво
- Асимметрия: результаты сильно зависят от того, какая сторона предлагает первой
- Не обрабатывает ограничения: сложно включить сложные предпочтения (например, пары, региональные предпочтения) без модификации алгоритма
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Гарантированная стабильность: в конечном сопоставлении отсутствуют блокирующие пары
- Полиномиальное время: сложность O(n^2), что делает его эффективным для больших популяций
- Простая реализация: легко выполняется на практике с прозрачным сбором предпочтений
- Стратегические стимулы: предлагающая сторона имеет стратегическое преимущество, предпочитая ранние предложения поздним
- Универсальная применимость: работает для любых профилей предпочтений без предположений о выпуклости или транзитивности
Применение
- Сопоставление медицинских ординаторов: сопоставление выпускников медицинских вузов с программами ординатуры в больницах через NRMP
- Выбор школы: распределение учащихся по государственным школам на основе предпочтений и ограничений по вместимости
- Обмен почками: сопоставление доноров и реципиентов органов для максимизации совместимых трансплантаций
- Сопоставление на рынке труда: соединение соискателей с работодателями на двусторонних рынках труда
- Онлайн-знакомства: сопоставление пользователей на платформах знакомств для повышения стабильности сопоставлений и удовлетворенности пользователей
Как это работает
Как это работает
Создайте списки предпочтений для всех индивидов в обеих группах, отражающие их ранжирование другой стороны.
В каждом раунде каждый неженатый/незамужняя osoba со стороны предлагающего делает предложение наиболее высокоранжированному лицу другой стороны, которому он/она еще не делал(а) предложения.
Каждое лицо на принимающей стороне предварительно принимает предложение, если оно не занято, или если предлагающий ранжируется выше его/ее текущего партнера, в этом случае оно отзывает предыдущее обязательство.
Алгоритм останавливается, когда каждый человек сопоставлен, и дальнейшие предложения не происходят, что приводит к стабильному сопоставлению.
Частые ошибки
- Предположение, что одной лишь стабильности достаточно для справедливости или благосостояния; стабильные сопоставления могут быть сильно смещены в сторону одной стороны
- Смешение стабильности с оптимальностью; стабильное сопоставление не обязательно является максимизирующим благосостояние
- Упущение стратегического преимущества предлагающей стороны: члены предлагающей стороны, как правило, получают более высокоранжированных партнеров
- Забывание о том, что алгоритм предполагает полные списки предпочтений; неполные предпочтения требуют модификации
Часто задаваемые вопросы
Почему стабильность важна в сопоставлении?
Без стабильности сопоставленные пары могут позже обнаружить, что они предпочитают друг друга своим назначенным партнерам, что создает стимул для разрыва сопоставления. Стабильные сопоставления предотвращают такие блокирующие пары, гарантируя, что сопоставление сохраняется без пересмотра.
Всегда ли алгоритм Гейла-Шепли дает одно и то же сопоставление?
Нет. Различные списки предпочтений или порядок предложений могут привести к различным стабильным сопоставлениям. Однако всегда существует "мужское оптимальное" сопоставление (лучшее для всех предлагающих) и "женское оптимальное" сопоставление (лучшее для всех отвечающих).
Как Гейл-Шепли обрабатывает предпочтения над группами (например, парами)?
Стандартный алгоритм напрямую не обрабатывает пары или другие ограничения. Существуют расширения, такие как алгоритм для пар, но они более сложны и могут не гарантировать стабильность для всех профилей предпочтений.
Похожие методы
Источники
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
Открыть ссылку DOIСкопировано.Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
Открыть ссылку DOIСкопировано.