Войти
В математике, экономике и информатике, проблема стабильного брака (также проблема стабильного соответствия или SMP ) - это проблема нахождения устойчивого соответствия между двумя наборами элементов одинакового размера с учетом порядка предпочтения для каждого элемента. Соответствие - это биекция от элементов одного набора к элементам другого набора. Сопоставление является нестабильным, если:
Другими словами, сопоставление является стабильным, когда не существует никакого совпадения (A, B), которое оба предпочитают друг друга своему текущему партнеру при сопоставлении.
Проблема стабильного брака была сформулирована следующим образом:
Учитывая n мужчин и n женщин, где каждый оценил всех представителей противоположного пола в порядке предпочтений, женитесь на мужчинах и женщинах вместе так, чтобы не существует двух людей противоположного пола, которые предпочли бы друг друга, а не своих нынешних партнеров. Когда таких пар людей нет, совокупность браков считается стабильной.
Существование двух классов, которые необходимо объединить в пары (в данном примере гетеросексуальные мужчины и женщины), отличает эту проблему от проблема соседей по комнате в конюшне.
Алгоритмы поиска решений проблемы стабильного брака находят применение во множестве реальных ситуаций, возможно, наиболее известными из них являются направление студентов-медиков на первые приёмы в больнице. В 2012 г. Нобелевская мемориальная премия по экономическим наукам была присуждена Ллойду С. Шепли и Элвину Э. Роту за теорию стабильного распределения и практику рыночный дизайн ».
Важное и крупномасштабное применение стабильного брака заключается в назначении пользователей на серверы в большой распределенной интернет-службе. Миллиарды пользователей получают доступ к веб-страницам, видео и другим службам в Интернете, требуя, чтобы каждый пользователь был сопоставлен с одним из (потенциально) сотен тысяч серверов по всему миру, которые предлагают эту услугу. Пользователь предпочитает серверы, которые находятся достаточно близко друг к другу, чтобы обеспечить более быстрое время отклика для запрашиваемой услуги, что приводит к (частичному) предпочтительному упорядочиванию серверов для каждого пользователя. Каждый сервер предпочитает обслуживать пользователей, что может, с меньшими затратами, что приводит к (частичному) предпочтительному упорядочиванию пользователей для каждого сервера. Сети доставки контента, которые распространяют большую часть мирового контента и услуг, решают эту большую и сложную проблему стабильного брака между пользователями и серверами каждые десятки секунд, чтобы миллиарды пользователей могли быть сопоставлены с их соответствующими серверами, которые могут предоставить запрошенные веб-страницы, видео или другие службы.
В общем, может быть много разных стабильных совпадений. Например, предположим, что есть три мужчины (A, B, C) и три женщины (X, Y, Z), которые имеют предпочтения:
Существует три стабильных решения этой схемы согласования:
Все три стабильны, потому что нестабильность требует обоих участников, чтобы они были довольны альтернативным матчем. Предоставление одной группе возможности первого выбора гарантирует, что матчи будут стабильными, потому что они будут недовольны любым другим предложенным матчем. Предоставление каждому возможности второго выбора гарантирует, что любой другой матч не понравится одной из сторон. В общем, семейство решений любого экземпляра проблемы стабильного брака может иметь структуру конечной распределительной решетки, и эта структура приводит к эффективным алгоритмам для нескольких проблем стабильных браков.
В равномерно-случайном примере проблемы стабильного брака с n мужчинами и n женщинами среднее количество стабильных совпадений асимптотически 
Анимация, показывающая пример алгоритма Гейла – Шепли В 1962 году Дэвид Гейл и Ллойд Шепли доказал, что для любого равного числа мужчин и женщин всегда возможно решить SMP и сделать все браки стабильными. Для этого они представили алгоритм .
алгоритм Гейла – Шепли (также известный как алгоритм отложенного принятия) включает в себя ряд «раундов» (или « итераций "):
Этот алгоритм гарантирует стабильный брак для всех участников во времени 
Среди всех возможных различных стабильных совпадений оно всегда дает лучшее для всех мужчин среди всех стабильных совпадений и худшее для всех женщин. Это правдивый механизм с точки зрения мужчин (предлагающей стороны). То есть ни один мужчина не может добиться лучшего соответствия для себя, искажая свои предпочтения. Более того, алгоритм GS является доказательством даже групповой стратегии для мужчин, т. Е. Никакая коалиция мужчин не может координировать искажение своих предпочтений таким образом, чтобы все мужчины в коалиции были строго в лучшем положении. Тем не менее, некоторая коалиция может искажать свои предпочтения так, что одни мужчины живут лучше, а другие мужчины сохраняют того же партнера. Алгоритм GS не соответствует действительности для женщин (проверяющая сторона): каждая женщина может исказить свои предпочтения и получить лучшее соответствие.
Теорема о сельских больницах касается более общего варианта задачи стабильного сопоставления, например, применяемой в задаче сопоставления врачей должностям в больницах, отличающиеся следующими способами от основной формы n-to-n проблемы стабильного брака:
В этом случае условие стабильности заключается в том, что ни одна несовпадающая пара не предпочитает друг друга их ситуация в сопоставлении (независимо от того, является ли эта ситуация другим партнером или нет). При этом условии стабильное соответствие все еще будет существовать, и его все еще можно будет найти с помощью алгоритма Гейла – Шепли.
Для такого рода задач стабильного сопоставления теорема о сельских больницах утверждает, что:
В стабильном сопоставлении с безразличием, некоторые мужчины могут безразлично относиться к двум или более женщинам и наоборот.
Задача соседи по комнате аналогична проблеме стабильного брака, но отличается тем, что все участники принадлежат к одному пулу (вместо того, чтобы быть разделенными на равное количество "мужчины и женщины").
Проблема больниц / резидентов - также известная как проблема поступления в колледж - отличается от проблемы стабильного брака тем, что больница может принять несколько резидентов или колледж могут принять входящий класс из более чем одного студента. Алгоритмы решения проблемы больниц / жителей могут быть ориентированы на больницу (как NRMP до 1995 года) или на резидента. Эта проблема была решена с помощью алгоритма в той же оригинальной статье Гейла и Шепли, в которой решалась проблема стабильного брака.
Проблема больниц / резидентов с парами позволяет включать в набор резидентов пары, которые должны быть распределены вместе либо в одну и ту же больницу, либо в конкретную пару больниц, выбранных парой (например, супружеская пара хочет быть уверенной, что они останутся вместе и не будут застрял в программах, которые находятся далеко друг от друга). Добавление пар к проблеме больниц / резидентов делает задачу NP-завершенной.
Задача назначения пытается найти соответствие во взвешенном двудольном графе с максимальным весом. Максимально взвешенное сопоставление не обязательно должно быть стабильным, но в некоторых приложениях максимальное взвешенное сопоставление лучше, чем стабильное.
Задача сопоставления с контрактами является обобщением задачи сопоставления, в которой участники могут быть сопоставлены с различными условиями контрактов. Важным частным случаем контрактов является сопоставление с гибкой заработной платой.
