Двусторонние рынки и теория паросочетаний

Рынки, где «деньги не всё»

На большинстве рынков цена уравновешивает спрос и предложение. Но существуют рынки, где денежные переводы невозможны или нежелательны по этическим или правовым причинам: распределение студентов по школам, резидентов по больницам, донорских органов по пациентам. Здесь нужны механизмы, обеспечивающие «справедливое» и «стабильное» распределение без ценового сигнала.

Теория паросочетаний — математический инструмент для таких рынков. Алвин Рот и Ллойд Шепли получили Нобелевскую премию 2012 года за её развитие и практическое применение.

Формальная постановка задачи о стабильном браке

Дано n мужчин M = {m₁, ..., mₙ} и n женщин W = {w₁, ..., wₙ}. Каждый мужчин mᵢ имеет строгое линейное упорядочение предпочтений над W; каждая женщина wⱼ — над M.

Паросочетание μ: M → W ∪ {∅} — взаимно однозначное отображение (каждый получает не более одного партнёра).

Стабильное паросочетание: μ стабильно, если не существует «блокирующей пары» (m, w) такой, что m предпочитает w своей партнёрше μ(m) И w предпочитает m своему партнёру μ(w).

Блокирующая пара — это два агента, которые предпочтут друг друга текущим партнёрам и «уйдут» вместе — нестабильность в том смысле, что паросочетание не удержится.

Алгоритм Гейла–Шепли

Версия с предложениями от мужчин (DA — Deferred Acceptance):

1. Каждый мужчина делает предложение наиболее предпочтительной женщине из ещё не отклонивших
2. Каждая женщина «откладывает» (но не принимает!) лучшее полученное предложение, отклоняет остальные
3. Отклонённые мужчины переходят к следующей в списке
4. Итерация до стабилизации

Теорема Гейла–Шепли (1962): Алгоритм DA всегда завершается за конечное число шагов и возвращает стабильное паросочетание. При предложениях от мужчин: результат M-оптимален (лучший для всех мужчин среди всех стабильных паросочетаний) и W-пессимален.

Числовой пример (полное решение)

3 мужчины (m₁, m₂, m₃), 3 женщины (w₁, w₂, w₃):

Предпочтения мужчин: m₁: w₁ > w₂ > w₃; m₂: w₁ > w₂ > w₃; m₃: w₁ > w₂ > w₃.

Предпочтения женщин: w₁: m₁ > m₂ > m₃; w₂: m₂ > m₁ > m₃; w₃: m₃ > m₂ > m₁.

Раунд 1: m₁ → w₁ (принимает: лучший кандидат); m₂ → w₁ (w₁ сравнивает: m₁ > m₂ → держит m₁, отклоняет m₂); m₃ → w₁ (отклоняет m₃, т.к. w₁: m₁ > m₃).

Раунд 2: m₂ → w₂ (принимает); m₃ → w₂ (w₂: m₂ > m₃ → держит m₂, отклоняет m₃).

Раунд 3: m₃ → w₃ (принимает).

Финал: μ = {m₁−w₁, m₂−w₂, m₃−w₃}. Стабильность проверим: (m₂, w₁)? m₂ предпочитает w₁ (w₁ > w₂), но w₁ предпочитает m₁ (m₁ > m₂) → не блокирующая. (m₃, w₁)? w₁: m₁>m₃ → не блокирующая. Паросочетание стабильно ✓.

Стратегические свойства

Инцентивная совместимость: При DA с предложениями от мужчин истинные предпочтения — доминантная стратегия для мужчин (нет стимула лгать). Женщины могут выиграть от стратегического искажения.

Теорема Рота (1982): Нет стабильного механизма паросочетания, инцентивно совместимого для обеих сторон. Это фундаментальное ограничение.

Реальные применения

NRMP (США, медицинские резиденты): С 1952 года — DA-подобный алгоритм. В 1990-х Рот исправил проблему с парами резидентов (совместное распределение пар). Ежегодно распределяет ~40 000 резидентов.

Школы NYC (2003): Заменён нестабильный механизм «Boston» → DA. Стабильность устранила «стратегические» заявки от родителей. ~80 000 учеников в год.

Биржа почек (Kidney Exchange, Рот, 2004): Несовместимая пара донор–реципиент обменивается с другой несовместимой парой → стабильное паросочетание, спасающее жизни. Рот разработал алгоритм для цепочек из нескольких пар.

Интернет-платформы: Airbnb (арендодатель–арендатор), LinkedIn (работодатель–кандидат), Tinder (взаимный матч) — онлайн-версии задачи паросочетания.

Нобелевская премия 2012: Ллойд Шепли и Элвин Рот получили премию по экономике «за теорию стабильного распределения и практику проектирования рынков». Рот создал алгоритмы для рынка медицинской резидентуры (NRMP, ~40 000 врачей в год), распределения учеников в нью-йоркские школы (~80 000 детей ежегодно) и биржи почек — прямое применение абстрактной математической теории к задачам, затрагивающим сотни тысяч людей.

Двусторонние рынки: платформенная экономика и стратегический дизайн

Теория паросочетаний лежит в основе платформенной экономики и проектирования рынков. Uber и Lyft — двусторонние рынки, соединяющие водителей и пассажиров: алгоритм сопоставления оптимизирует стабильность паросочетаний в реальном времени, учитывая рейтинги, расстояние и предпочтения. Рынки труда в медицине (ординатура в США — NRMP), юриспруденции и академии устроены как стабильные паросочетания. Алгоритм Гейла–Шепли, применённый в NRMP с 1952 года, резко снизил число «несанкционированных» прямых контрактов, обходящих официальный рынок — признак нестабильности системы. Amazon, Airbnb и другие маркетплейсы решают задачу «толщины рынка» — привлечения достаточного числа участников с обеих сторон, чтобы паросочетания давали высокое качество и низкую безработицу рынка. В рекламных аукционах поисковых систем позиции назначаются через обобщённый аукцион второй цены (GSP), который аппроксимирует устойчивое паросочетание рекламодателей с рекламными слотами. Нобелевская премия Алвина Рота (2012) признала дизайн рынков с использованием теории паросочетаний практическим вкладом в благосостояние общества.

Помимо классического применения, алгоритм Гейла–Шепли используется в многосторонних рынках с ограничениями: в распределении ординаторов с парными предпочтениями (couples problem), где два партнёра хотят работать в одном городе. Это расширение делает задачу NP-трудной и требует специализированных эвристик, применяемых NRMP с 1997 года. Децентрализованные рынки (рынок MBA-выпускников) без DA-алгоритма показывают типичные признаки нестабильности: ранние офферы («эксплозия»), унравление (unraveling), низкое качество паросочетаний.

Задание: Решите задачу о стабильном браке для 3 мужчин и 3 женщин со следующими предпочтениями: m₁: w₂>w₁>w₃; m₂: w₁>w₃>w₂; m₃: w₃>w₁>w₂; w₁: m₂>m₃>m₁; w₂: m₁>m₂>m₃; w₃: m₂>m₁>m₃. Найдите M-оптимальное и W-оптимальное стабильные паросочетания. Совпадают ли они?