Решатель задачи о стабильных браках

О Решатель задачи о стабильных браках

Решатель задачи о стабильных браках — это интерактивная реализация алгоритма Гейла-Шепли с отложенным принятием. Этот алгоритм сопоставления, представленный в 1962 году Дэвидом Гейлом и Ллойдом Шепли, доказывает, что всегда можно составить стабильные пары между двумя группами равного размера, если каждый участник предоставил полный список своих предпочтений. Инструмент принимает списки предпочтений, пошагово выполняет алгоритм и визуализирует результат в виде стабильного сопоставления, анимации двудольного графа, тепловых карт и подтвержденного доказательства отсутствия блокирующих пар.

Что такое задача о стабильных браках?

Даны два непересекающихся множества одинакового размера — например, n мужчин и n женщин, или n кандидатов и n вакансий. У каждого участника есть полный список предпочтений относительно участников другой группы. Сопоставление — это разбиение всех на пары «один-к-одному». Сопоставление называется стабильным, если не существует пары (a, b) вне сопоставления, которая предпочла бы быть друг с другом больше, чем со своими назначенными партнерами.

Формально, сопоставление M стабильно, если нет блокирующей пары — пары (a, b), где a в паре с b', а b в паре с a', таких что:

Если оба условия выполняются, a и b бросят своих партнеров, что делает сопоставление нестабильным. Стабильное сопоставление — это такое, где подобных пар нет.

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

Гейл и Шепли конструктивно доказали, что стабильное сопоставление существует для любого набора предпочтений. Алгоритм проходит в раундах:

1. Каждый свободный предлагающий делает предложение самому предпочтительному кандидату из своего списка, который его еще не отвергал.
2. Каждый принимающий, получивший одно или несколько предложений, выбирает наиболее предпочтительного (сравнивая его с текущим временным партнером) и временно принимает его; остальные отвергаются.
3. Отвергнутые предлагающие снова становятся свободными и переходят к следующему выбору в следующем раунде.
4. Алгоритм завершается, когда все предлагающие заняты — это гарантированно происходит максимум за n² предложений.

Ключевые теоретические свойства

Существование и уникальность

Стабильное сопоставление существует всегда (Гейл и Шепли, 1962), но не всегда уникально. Для одного набора предпочтений может быть несколько вариантов стабильных пар.

Оптимальность для предлагающих

Когда одна сторона предлагает, алгоритм Гейла-Шепли выдает стабильное сопоставление, оптимальное для предлагающих: каждый предлагающий получает лучшего партнера, который возможен при условии стабильности. По симметрии это также наихудшее (пессимальное) сопоставление для принимающих. Смена предлагающей стороны в этом калькуляторе часто меняет результат.

Устойчивость к стратегиям

В алгоритме Гейла-Шепли предлагающим невыгодно лгать о своих предпочтениях: говорить правду — доминирующая стратегия. Однако принимающие иногда могут получить выгоду от стратегического искажения списка.

Формат ввода

Калькулятор ожидает по одной строке на участника: имя, двоеточие и полный ранжированный список предпочтений через запятую:

Требования:

• Обе группы должны иметь одинаковое количество участников.
• У каждого участника должен быть ранжирован каждый представитель другой группы.
• В именах можно использовать буквы, цифры, пробелы и стандартные символы Unicode.
• Поддерживается до 15 участников с каждой стороны для корректной анимации.

Как пользоваться калькулятором

1. Введите предпочтения Группы А в левое поле — по строке на человека.
2. Введите предпочтения Группы Б в правое поле в том же формате.
3. Выберите предлагающую сторону. Попробуйте оба варианта, чтобы сравнить А-оптимальный и Б-оптимальный результаты.
4. Нажмите «Решить задачу о стабильных браках». Вы получите список пар, статистику, анимацию и проверку стабильности.
5. Используйте плеер анимации (пуск, шаг, сброс), чтобы увидеть каждое предложение, принятие и замену в деталях.
6. Изучите тепловую карту. Желтым обведены итоговые пары — посмотрите, насколько высоко или низко они находятся в списках предпочтений.

Медицинская резидентура и Нобелевская премия

В 2012 году Шведская королевская академия наук присудила Нобелевскую премию по экономике Ллойду Шепли (за теорию, вместе с Дэвидом Гейлом, который не дожил до этого момента) и Элвину Роту (за применение теории на практике, включая редизайн систем сопоставления врачей и доноров почек). Награда была вручена за «теорию стабильного распределения и практику проектирования рынков».

Часто задаваемые вопросы

Что такое задача о стабильных браках?

Это задача поиска соответствия между двумя группами, где никто не захочет «изменить» своему партнеру, так как не найдет взаимного интереса у более предпочтительного кандидата. Алгоритм Гейла-Шепли всегда находит такое решение.

Должны ли группы быть равными?

В классической модели — да. Для несбалансированных групп (например, больше студентов, чем мест в вузах) используются модификации алгоритма, такие как задача о больницах и резидентах.

Дополнительные материалы

• Задача о стабильном выборе — Википедия
• Алгоритм Гейла — Шепли — Википедия
• Нобелевская премия по экономике 2012 года — Шепли и Рот