Стабильный брак с безразличием

Стабильный брак с безразличием — это вариант задачи о стабильном браке . Как и в исходной задаче, цель состоит в том, чтобы сопоставить всех мужчин со всеми женщинами таким образом, чтобы ни одна пара мужчины и женщины, не состоящих в браке друг с другом, не захотела бы одновременно оставить своих нынешних партнеров и вместо этого объединиться друг с другом.

В классической версии задачи каждый человек должен ранжировать представителей противоположного пола в строгом порядке предпочтения. Однако в реальной обстановке человек может предпочесть двух или более человек в качестве одинаково благоприятных партнеров. Такое связанное предпочтение называется безразличием .

Ниже приведен такой пример, где безразлично между и безразлично между .${\displaystyle m_{2}}$${\displaystyle w_{3}\&w_{1}}$${\displaystyle w_{2}}$${\displaystyle m_{1}\&m_{2}}$

${\displaystyle m_{1}[\ w_{2}\ w_{1}\ w_{3}\ ]\ \ \ \ \ \ w_{1}[\ m_{3}\ m_{2}\ m_{1}\ ]}$

${\displaystyle m_{2}[\left(w_{3}\ w_{1}\right)w_{2}]\ \ \ \ \ \ w_{2}[\left(m_{1}\ m_{2}\right)m_{3}]}$

${\displaystyle m_{3}[\ w_{1}\ w_{2}\ w_{3}\ ]\ \ \ \ \ \ w_{3}[\ m_{2}\ m_{3}\ m_{1}\ ]}$

Если допускаются связанные списки предпочтений, то проблема стабильного брака будет иметь три понятия стабильности, которые обсуждаются в следующих разделах.

1. Соответствие называется слабо стабильным, если только нет пары, каждая из которых строго предпочитает другую своему партнеру в соответствии. Роберт У. Ирвинг ^[1] расширил алгоритм Гейла–Шепли , как показано ниже, чтобы обеспечить такое слабо стабильное соответствие во времени, где n — размер проблемы стабильного брака. Связи в списках предпочтений мужчин и женщин разрываются произвольно. Списки предпочтений сокращаются по мере выполнения алгоритма.${\displaystyle O(n^{2})}$

Назначьте каждого человека свободным ;​​      в то время как ( некоторый человек свободен ) делать       начинать w : = первая женщина в списке m ;​​       m делает предложение и обручается с w ;​​       если ( некоторый мужчина m ' помолвлен с w ) то​         назначить m ' свободным ;​​     для каждого ( последователя m ' ' из m в списке w ) сделать​          удалить пару ( m ' ' , w )     конец ; вывести занятые пары , которые образуют устойчивое соответствие​​        

2. Соответствие называется сверхстабильным, если нет пары, каждая из которых либо строго предпочитает другую своему партнеру, либо безразлична к ним. Роберт У. Ирвинг ^[1] модифицировал приведенный выше алгоритм, чтобы проверить, существует ли такое сверхстабильное соответствие, и выводит соответствие со временем, если оно существует. Ниже приведен псевдокод.${\displaystyle O(n^{2})}$

назначить каждого человека свободным ;​​     повторить в то время как ( некоторый человек свободен ) делать       для каждой ( женщина w во главе списка m ) сделать​​​​           начинать m делает предложение и обручается с w ;​​       для каждого ( строгий преемник m ' из списка w ) сделать​​​​           начинать если ( m ' помолвлен ) с w , то       разорвать помолвку ;​   удалить пару ( m ' , w )​     конец конец для каждой ( женщины , которая многократна помолвлена ) сделать​         начинать разорвать все обязательства, связанные с w ;     для каждого ( человек m в конце списка w ) сделать​​​​           удалить пару ( м , ж )​     конец ;пока ( список какого - то мужчины не пуст ) или ( все не заняты );         если все вовлечены , то     отношение взаимодействия - это супер - стабильное соответствие​      еще супер - стабильного соответствия не существует   

3. Соответствие строго устойчиво, если нет пары x, y такой, что x строго предпочитает y своему партнеру, а y либо строго предпочитает x своему партнеру, либо безразличен между ними. Роберт У. Ирвинг ^[1] предоставил алгоритм, который проверяет, существует ли такое строго устойчивое соответствие, и выводит соответствие, если оно существует. Алгоритм вычисляет идеальное соответствие между наборами мужчин и женщин, тем самым находя критический набор мужчин, которые помолвлены с несколькими женщинами. Поскольку такие помолвки никогда не бывают стабильными, все такие пары удаляются, и последовательность предложений будет повторяться снова, пока 1) список предпочтений какого-либо мужчины не станет пустым (в этом случае строго устойчивого соответствия не существует) или 2) не будет получено строго устойчивое соответствие. Ниже приведен псевдокод для поиска строго устойчивого соответствия. Он выполняется во времени, которое объясняется в лемме 4.6 из . ^[1]${\displaystyle O(n^{4})}$

Назначьте каждого человека свободным ;​​     повторить в то время как ( некоторый человек свободен ) делать       для каждой ( женщина w во главе списка m ) сделать​​​​           начинать m делает предложение и обручается с w ;​​       для каждого ( строгий преемник m ' из списка w ) сделать​​​​           начинать если ( m ' помолвлен ) с w , то       разорвать помолвку ;​   удалить пару ( m ' . w )​     конец конец если ( отношение взаимодействия не содержит идеального соответствия ) , то​​           начинать найти критическое множество Z мужчин ;​​       для каждой ( женщины w , которая помолвлена ​​с мужчиной в Z ) сделать​             начинать разорвать все обязательства, связанные с w ;     для каждого человека m в конце списка w сделать​​​​           удалить пару ( м , ж )​     конец ; конец ;пока ( список какого - то мужчины не пуст ) или ( все не заняты );         если все вовлечены , то     отношение взаимодействия - это супер - стабильное соответствие​      еще не существует сильно устойчивого соответствия    

Во многих задачах может быть несколько различных устойчивых паросочетаний. Множество устойчивых паросочетаний имеет особую структуру. Дэвид Ф. Мэнлав ^[2] доказал, что как множество сильных устойчивых паросочетаний, так и множество суперустойчивых паросочетаний образуют дистрибутивную решетку .