Математика · объяснение и практика
Лучший устойчивый партнёр: что даёт сторона предложений
Доказываем, что отложенное принятие даёт каждому предлагающему лучшего доступного в устойчивых решениях партнёра, а принимающим — худшего среди устойчивых; различаем это с первым выбором вообще.

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
При равных группах, строгих полных списках и предложениях стороны P каждый её участник получает в алгоритме Гейла–Шепли лучшего партнёра среди всех партнёров, возможных для него в каком-либо устойчивом решении. Это не обещание первого места во всём списке. Для принимающей стороны тот же результат является худшим среди устойчивых решений.
Сначала ограничиваем круг сравниваемых партнёров
Назовём пару достижимой в устойчивом смысле, если существует хотя бы одно устойчивое паросочетание, где эти двое назначены друг другу. Хороший результат для предлагающего сравнивается только с такими партнёрами. Слишком желанная, но не входящая ни в одно устойчивое решение пара не является упущенной возможностью этой теоремы.
Алгоритм уже гарантирует устойчивость и полное назначение. Теперь требуется более сильное утверждение: все предлагающие одновременно получают своих лучших устойчиво достижимых партнёров. Наличие нескольких устойчивых решений не позволяет выбрать произвольную комбинацию хороших пар без проверки; дополнительное доказательство показывает, что именно эта комбинация реализуется.
Важна сторона, имеющая право последовательно делать предложения. Перестановка порядка обработки свободных предлагающих и обмен ролями двух сторон — разные изменения. Первое при текущих строгих списках не меняет итог, второе может привести к другому устойчивому решению.
Первый отказ достижимой паре приводит к противоречию
Предположим, что во время работы впервые отвергнута достижимая пара p,r. В этот момент r сохраняет кандидата q, которого предпочитает p. Рассмотрим устойчивое паросочетание M′, содержащее p−r, и обозначим через s партнёра q в M′.
Если q предпочитает r участнику s, пара q,r блокирует M′: r тоже предпочитает q своему назначенному p. Это противоречит устойчивости. Если q предпочитает s участнику r, он должен был обратиться к s раньше, поскольку до r алгоритм дошёл по порядку списка. Чтобы стать доступным для r, q уже получил отказ от s.
Но q−s входит в устойчивое M′, значит, это была более ранняя отвергнутая достижимая пара. Снова противоречие выбору первого такого отказа. Совпадение s=r невозможно, поскольку в M′ r уже назначен p, а q отличен от p. Строгость списков исчерпывает оставшиеся два сравнения.
Пример
У А предпочтения x>y, у Б — y>x. У x предпочтения Б>А, у y — А>Б. Сравните результаты при смене предлагающей стороны.
Если предлагают А и Б, сразу получаются А−x и Б−y: оба предлагающих имеют первое место. Если предлагают x и y, получаются Б−x и А−y: первые места получают принимающие прежней схемы. Оба результата устойчивы. В первом x хотел бы Б, но Б предпочитает y; y хотел бы А, но А предпочитает x. Во втором обратные неназначенные пары отвергаются x и y. Разные результаты не опровергают однозначность при фиксированной стороне предложений.
Как из отсутствия таких отказов получаются оптимальность и единственность
Ни один предлагающий не потеряет достижимого партнёра вследствие отказа. Если он завершил работу с r, то любой стоящий выше кандидат уже отверг его и потому не мог быть устойчиво достижимым. Сам итог устойчив, следовательно, r достижим и является лучшим в этом классе.
Строгий список имеет единственное лучшее место в любом непустом подмножестве. Поэтому результат со стороной P в роли предлагающих однозначен: каждый её участник должен получить одного и того же лучшего достижимого партнёра независимо от порядка очереди свободных участников. Это не утверждение, что вся задача имеет лишь одно устойчивое паросочетание.
Теперь пусть принимающий r в результате имеет p и якобы в другом устойчивом M′ получает менее желанного q. Предлагающий p в M′ получает иного партнёра s. По уже доказанной оптимальности p предпочитает свой результат r участнику s. Тогда p и r взаимно предпочли бы друг друга в M′ и блокировали его. Значит, ни один устойчивый вариант не даёт r партнёра хуже итогового: принимающая сторона получает свой худший устойчивый вариант.
От чтения к действию
А теперь — вы
Частые вопросы
Каждый предлагающий обязательно получает самое первое имя списка?
Нет. Более желанные кандидаты могут быть недостижимы во всех устойчивых решениях. Оптимальность сравнивает только устойчиво достижимых партнёров.
Худший для принимающих означает хуже любого мыслимого назначения?
Нет. Сравнение также ограничено устойчивыми паросочетаниями. Неустойчивое назначение может оцениваться иначе.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Доминирующая стратегия и равновесие Нэша
Различаем стратегию, лучшую при любом ответе другого игрока, и устойчивость одной пары действий, проверяем строгие сравнения и не объявляем равновесие максимумом общей выгоды.
Открыть темуПаросочетание: как чередующийся путь увеличивает число пар
Увеличивающий путь в двудольном паросочетании: перестановка занятых назначений вместо жадного отказа свободной вершине.
Открыть тему