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

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

Решатель задачи о стабильных браках — это интерактивная реализация алгоритма Гейла-Шепли с отложенным принятием. Этот алгоритм сопоставления, представленный в 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 года — Шепли и Рот

Продвинутые математические операции:

• Калькулятор матрицы смежности Новый
• Антилогарифмический Калькулятор
• Калькулятор бета-функции
• Калькулятор биномиального коэффициента
• Калькулятор биномиального распределения Популярное
• Побитовый калькулятор Популярное
• Упроститель Булевой Алгебры Новый
• Калькулятор центральной предельной теоремы
• Калькулятор китайской теоремы об остатках
• Комбинированный калькулятор
• Калькулятор дополнительной функции ошибки
• Калькулятор комплексных чисел Популярное
• Калькулятор цепных дробей
• Калькулятор беспорядков (субфакториал)
• Калькулятор кратчайшего пути Дейкстры
• Калькулятор Энтропии
• Калькулятор функции ошибки
• Калькулятор функции Эйлера
• Калькулятор экспоненциального распада
• Калькулятор экспоненциального роста: высокая точность
• Калькулятор экспоненциального интеграла
• Калькулятор показателей (высокая точность)
• Калькулятор расширенного алгоритма Евклида
• Калькулятор факториала
• Калькулятор гамма-функции
• Калькулятор золотого сечения
• Калькулятор раскраски графов Новый
• Валидатор последовательности степеней графа
• Калькулятор Порядка в Теории Групп Новый
• Калькулятор полураспада
• Проверка Гамильтонова Пути Новый
• Калькулятор формулы включений-исключений Новый
• Решатель Карты Карно (K-Map) Популярное
• Решатель Линейного Программирования Новый
• Калькулятор стационарного распределения цепи Маркова
• Калькулятор минимального остовного дерева
• Калькулятор Модульного Возведения в Степень Новый
• Калькулятор модулярного мультипликативного обратного
• Калькулятор отрицательного биномиального распределения Новый
• Калькулятор сетевого потока (Максимальный поток) Новый
• Калькулятор процентного роста
• Калькулятор перестановок
• Калькулятор перестановок с повторениями Новый
• Калькулятор принципа голубятни
• Проверка планарного графа Новый
• Калькулятор распределения Пуассона
• Калькулятор корней многочленов с подробными шагами
• Калькулятор первообразного корня
• Калькулятор вероятности
• Калькулятор распределения вероятностей
• Калькулятор пропорций Популярное
• Калькулятор квадратичных формул
• Калькулятор Колец и Полей Новый
• Калькулятор округления Новый
• Научный Калькулятор
• Калькулятор экспоненциальной записи
• Калькулятор теории множеств Популярное
• Калькулятор значащих цифр Новый
• Решатель задачи о стабильных браках Новый
• Калькулятор чисел Стирлинга
• Калькулятор суммы кубов
• Калькулятор суммы последовательных чисел
• Калькулятор суммы квадратов Популярное
• Калькулятор топологической сортировки Новый
• Решатель задачи коммивояжёра (TSP) Новый
• Генератор таблицы истинности
• Генератор диаграммы Венна (3 множества)