Математика · объяснение и практика
Отложенное принятие: почему устойчивое назначение существует
Строим паросочетание по строгим полным предпочтениям, доказываем остановку алгоритма Гейла–Шепли и отсутствие пары, желающей совместно сменить партнёров.

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