Теория игр
Теория матчинга и алгоритм Гейла-Шепли
Каждый год тысячи студентов-медиков в США не знают, куда попадут на интернатуру. Каждый год тысячи детей в Нью-Йорке идут в школу. Как распределить их честно и стабильно? Ответ - алгоритм, придуманный математиками ради красивой задачи, - теперь управляет судьбами миллионов людей.
- **NRMP**: 50,000+ американских врачей-интернов ежегодно распределяются через алгоритм Гейла-Шепли - работает с 1952 года
- **NYC Schools**: 90,000 нью-йоркских восьмиклассников каждый год получают место в школе через централизованный матчинг
- **Kidney Exchange**: Элвин Рот создал биржи почек - цепочки обменов без денег, которые ежегодно спасают сотни жизней
Предварительные знания
Задача сопоставления (matching problem)
Tinder algorithm (2024, 75M+ активных пользователей) использует Gale-Shapley для matching: stable matching за O(n²) проверок. NRMP (National Resident Matching Program) ежегодно распределяет 40 000 ординаторов по больницам США через алгоритм Гейла-Шепли - стабильное паросочетание гарантировано математически. Задача матчинга - это распределение агентов из двух групп в пары, при котором каждый агент имеет **предпочтения** над агентами другой группы. В отличие от обычного рынка, здесь нет денежных трансфертов - только предпочтения.
Что значит «хорошее» паросочетание? Требуется **устойчивость** (stability) - ключевое понятие теории матчинга.
Паросочетание M называется **устойчивым**, если не существует **блокирующей пары** - пары (a, b) такой, что: • a предпочитает b своему текущему партнёру в M • b предпочитает a своему текущему партнёру в M Если блокирующая пара существует - a и b покинут своих партнёров и объединятся. Устойчивость = нет такого взаимного желания «сбежать».
Паросочетание: Анна-Иван, Катя-Петр. При этом Анна предпочитает Петра, а Петр предпочитает Анну. Является ли это паросочетание устойчивым?
Алгоритм Гейла-Шепли
Дэвид Гейл и Ллойд Шепли (1962)
Математики Дэвид Гейл и Ллойд Шепли опубликовали статью «College Admissions and the Stability of Marriage» в 1962 году. Они доказали существование устойчивого паросочетания для любого набора предпочтений и дали конструктивный алгоритм для его нахождения. Ллойд Шепли получил Нобелевскую премию по экономике в 2012 году (совместно с Элвином Ротом). Гейл скончался в 2008 году до присуждения премии.
Алгоритм завершается за конечное число шагов (не более n² предложений) и гарантированно возвращает устойчивое паросочетание. При этом алгоритм **оптимален для предлагающей стороны** - каждый мужчина получает лучшую возможную партнёршу из всех устойчивых паросочетаний.
В алгоритме Гейла-Шепли женщина получает предложение и у неё уже есть «предварительный партнёр». Что она делает?
Свойства и ограничения алгоритма
Алгоритм Гейла-Шепли обладает несколькими замечательными свойствами, но также имеет важное ограничение - асимметрию результата.
| Свойство | Описание |
|---|---|
| Существование | Устойчивое паросочетание существует ВСЕГДА для любых предпочтений |
| Полнота | Все агенты сопоставлены (при равных размерах групп) |
| Оптимальность предлагающих | Каждый предлагающий получает лучшего партнёра из ВСЕХ устойчивых паросочетаний |
| Пессимальность принимающих | Каждый принимающий получает ХУДШЕГО партнёра из всех устойчивых паросочетаний |
| Strategy-proofness | Честный список предпочтений - доминирующая стратегия для предлагающей стороны |
| Манипулируемость | Принимающая сторона МОЖЕТ извлечь выгоду, исказив предпочтения |
Кто предлагает - тот выигрывает. В реальных системах это важно: • NRMP (врачи-больницы): долгое время больницы предлагали → больницы в выигрыше. После реформы 1995 - врачи предлагают → лучше для врачей. • Школы vs семьи: кто предлагает первым, тот получает преимущество.
Почему алгоритм Гейла-Шепли strategy-proof для предлагающих, но не для принимающих?
Приложения: рынки без цен
Элвин Рот (Нобелевская премия 2012) превратил теорию матчинга в прикладную науку - **market design**. Он разработал механизмы распределения для реальных рынков, где деньги не работают или социально неприемлемы.
Урок Рота: **рынки должны быть спроектированы**. Стихийно возникающие рынки часто нестабильны, не strategy-proof и дают плохие результаты. Теория матчинга - инструмент для их улучшения.
Почему на рынке распределения почек от живых доноров нельзя просто использовать денежные платежи вместо сложного алгоритма матчинга?
Ключевые идеи
- **Устойчивое паросочетание** - нет блокирующей пары; оба хотят сбежать от своих партнёров друг к другу
- **Алгоритм Гейла-Шепли** (Deferred Acceptance) - предлагающие делают предложения по убыванию, принимающие держат лучшего
- **Оптимален для предлагающих** - каждый получает лучшую возможную пару; **пессимален для принимающих**
- **Strategy-proof для предлагающих** - честный список - доминирующая стратегия; принимающие могут манипулировать
- **Market design (Рот)** - алгоритмы матчинга применяются к школам, больницам, биржам почек
Связанные темы
Теория матчинга - пересечение теории игр и алгоритмики:
- Механизм-дизайн — Матчинг - приложение механизм-дизайна: как спроектировать правила для желаемого результата
- Теория аукционов — Аукционы - матчинг с деньгами; Рот противопоставляет их «рынкам без денег»
- Algorithmic Game Theory — GS-алгоритм - O(n²), используется в реальных системах; computational complexity матчинга
Вопросы для размышления
- В системе поступления в вузы в России - является ли она стабильной? Кто предлагает, кто принимает?
- Что произойдёт, если все знают, что другие тоже могут манипулировать предпочтениями? Возникнет ли равновесие?
- Рот говорит о «repugnant markets» - рынках, которые общество считает неэтичными. Где граница между допустимым и недопустимым?