Это может звучать больше как вопрос социальных наук, чем вопрос TCS, но это не так. Читая « Рандомизированные алгоритмы », описывающие проблему стабильного брака, можно прочитать следующее (p54)
«Можно показать, что для каждого списка предпочтений существует, по крайней мере, один стабильный брак. (Любопытно, что это не так в гомосексуальном моногамном обществе с четным числом жителей) ....»
Существуют ли какие-либо очень простые расширения проблемы стабильного брака, которая допускает некоторый тип устойчивого состояния, который включает гомосексуальное моногамное общество или общество, в котором определенная часть населения следует другому набору правил, чем большая группа?
Утвердительно, есть ли алгоритмы, которые выполняют такое сопоставление?
источник
Ответы:
Существует открытая гипотеза о 3 типах людей. Предположим, у вас есть мужчины, женщины и собаки, поэтому у мужчин есть списки предпочтений для женщин, для женщин - списки предпочтений для собак, а для собак - списки предпочтений для мужчин. Всегда ли стабильный брак?
(Для других структур предпочтений в обществе с 3 типами ответы известны как отрицательные).
Другой комментарий заключается в том, что стабильный брак представляет собой непустое ядро, и у Скарфа есть хорошо известное условие, подразумевающее существование непустого ядра. Известно, что условия Шарфа удовлетворяются для первоначальной проблемы стабильного брака и проблемы с распределением домов. (Но не удалось из-за проблемы мужчины / женщины / собаки).
Некоторые ссылки:
источник
То, что вы спрашиваете, больше не называется «проблема стабильного брака». Напротив, это называется «проблема стабильных соседей по комнате». Согласно Википедии :
Википедия обсуждает ответ на ваш вопрос. В нем говорится, что стабильный случай не всегда может быть найден, однако существует эффективный алгоритм, согласно Ирвингу (1985), который найдет такое соответствие, если оно есть.
Редактировать:
Несколько естественных расслаблений возможны для SRP: вместо того, чтобы требовать, чтобы «не было двух участников x и y, каждый из которых предпочитает другого своему партнеру в M», можно потребовать, чтобы:
источник
источник