Расширение проблемы стабильного брака?

11

Это может звучать больше как вопрос социальных наук, чем вопрос TCS, но это не так. Читая « Рандомизированные алгоритмы », описывающие проблему стабильного брака, можно прочитать следующее (p54)

«Можно показать, что для каждого списка предпочтений существует, по крайней мере, один стабильный брак. (Любопытно, что это не так в гомосексуальном моногамном обществе с четным числом жителей) ....»

Существуют ли какие-либо очень простые расширения проблемы стабильного брака, которая допускает некоторый тип устойчивого состояния, который включает гомосексуальное моногамное общество или общество, в котором определенная часть населения следует другому набору правил, чем большая группа?

Утвердительно, есть ли алгоритмы, которые выполняют такое сопоставление?

IgorCarron
источник
1
Звучит как забавный вопрос, особенно если вы живете в штате Юта!
Дэйв Кларк
1
Вопрос немного открытый. Естественно, вы можете гарантировать, что решение проблемы стабильных соседей по комнате существует, если вы измените определение блокирующей пары и / или ограничите структуру соответствующих предпочтений. В качестве тривиального примера вы можете придумать формулировку задачи, в которой любое максимальное совпадение является «стабильным», а затем существует простой жадный алгоритм для нахождения такого совпадения. Но я не думаю, что это то, что вы хотели бы услышать; не могли бы вы уточнить немного больше?
Юкка Суомела
1
Две прекрасные книги о проблеме стабильного брака и ее родственниках: «Двустороннее сопоставление» Элвина Рота и Марильды Сотомайор и «Устойчивая проблема брака» Дэна Гусфилда и Роберта У. Ирвинга.
Иосиф Малкевич
1
Кнут также рекомендует «стабильный брак и его связь с другими комбинаторными проблемами». Вы можете найти отсканированную версию французского издания на сайте: www-cs-faculty.stanford.edu/~uno/ms.html
Dai Le

Ответы:

11

Существует открытая гипотеза о 3 типах людей. Предположим, у вас есть мужчины, женщины и собаки, поэтому у мужчин есть списки предпочтений для женщин, для женщин - списки предпочтений для собак, а для собак - списки предпочтений для мужчин. Всегда ли стабильный брак?

(Для других структур предпочтений в обществе с 3 типами ответы известны как отрицательные).

Другой комментарий заключается в том, что стабильный брак представляет собой непустое ядро, и у Скарфа есть хорошо известное условие, подразумевающее существование непустого ядра. Известно, что условия Шарфа удовлетворяются для первоначальной проблемы стабильного брака и проблемы с распределением домов. (Но не удалось из-за проблемы мужчины / женщины / собаки).

Некоторые ссылки:

  • N
  • В статье показаны различные применения критической леммы Скарфа и приведено несколько других цитат: (В частности, приводится дробная версия теоремы Гейла-Шепли для гиперграфов Аарони и Хольцмана): Р. Ахарони и Т. Флейнер. О лемме. шарф, Дж. Комбин. Теория Сер. B 87 (2003), 72--80.
  • Решение проблемы мужчин-женщин-собак, когда существует не более 4-х каждого пола, представлено в статье Eriksson et al. (Math Soc Sci 2006).
Гил Калай
источник
@Prof. Калай: Не могли бы вы указать мне хорошую ссылку на непустое основное условие Скарфа в случае стабильного брака?
Дай Ле
Попробуйте оригинальную статью Скарфа, которую я добавил к ответу.
Гил Калай
10

То, что вы спрашиваете, больше не называется «проблема стабильного брака». Напротив, это называется «проблема стабильных соседей по комнате». Согласно Википедии :

В математике, особенно в области теории игр и комбинаторики, проблемой стабильного соседа по комнате (SRP) является проблема поиска стабильного соответствия - соответствия, в котором нет пары элементов, каждый из другого сопоставленного набора, где каждый член пары предпочитает другого своему совпадению. Это отличается от проблемы стабильного брака тем, что проблема стабильных соседей по комнате не требует разбивки набора на мужские и женские подмножества. Любой человек может предпочесть кого-либо в том же наборе.

Это обычно заявляется как:

В данном случае проблемы стабильных соседей по комнате (SRP) каждый из 2n участников ранжирует остальных в строгом порядке предпочтений. Совпадение - это набор из n непересекающихся (неупорядоченных) пар участников. Сопоставление M в экземпляре SRP является стабильным, если нет двух участников x и y, каждый из которых предпочитает другого своему партнеру в M. Говорят, что такая пара блокирует M или является блокирующей парой по отношению к М.

Википедия обсуждает ответ на ваш вопрос. В нем говорится, что стабильный случай не всегда может быть найден, однако существует эффективный алгоритм, согласно Ирвингу (1985), который найдет такое соответствие, если оно есть.


Редактировать:

Несколько естественных расслаблений возможны для SRP: вместо того, чтобы требовать, чтобы «не было двух участников x и y, каждый из которых предпочитает другого своему партнеру в M», можно потребовать, чтобы:

  1. По крайней мере, определенная часть людей будет довольна своими соседями по комнате. Здесь выполнимость может интерпретироваться по-разному. Например:
    • Пара (x, y) называется удовлетворенной, если y является первым выбором x, и наоборот.
    • Пара (x, y) называется удовлетворенной, если один из x или y является первым выбором другого.
    • Пара (x, y) называется неудовлетворенной, если существует пара (z, w) такая, что x любит z больше, чем y, и z любит x больше, чем w.
    • ...
  2. По крайней мере, определенная часть людей будет недовольна своими соседями по комнате. (Это требование может отличаться от приведенного выше в зависимости от интерпретации выполнимости .)
М.С. Дусти
источник
Я думаю, что OP уже знает все это, и вопрос был в том, как изменить правила игры, чтобы гарантировать стабильное соответствие.
Юкка Суомела
Кроме того, самый простой контрпример включает в себя 4 вершины, в которых первое и второе предпочтения 3 из них определяют 3-цикл.
Per Vognsen
2
Я предполагаю, что люди обычно используют термин «стабильное соответствие» для обозначения любого варианта проблемы и «стабильный брак» против «стабильных соседей по комнате», если они хотят подчеркнуть, что они изучают двудольную и небипартийную версию проблемы. , Но, как обычно, лучше определить ваши термины и не предполагать, что они стандартизированы ...
Юкка Суомела
Я не решаюсь поддержать этот ответ из-за первого абзаца, который, похоже, просто оскорбляет некоторых людей.
Цуёси Ито
@ Tsuyoshi Ito: я не хотел никого обидеть. После второй мысли я полностью удалил первый абзац.
MS Dousti
7

nm

mhum
источник
Но это опять-таки двустороннее сопоставление: у вас есть два разных типа сущностей: «люди» и «дома» (точно так же, как у вас «мужчины» и «женщины» в традиционной проблеме стабильного брака). Вопрос, казалось, был конкретно о не двудольном сопоставлении.
Юкка Суомела
Вы можете иметь точку. Я думал, что эта проблема могла бы решить «общество, в котором определенная часть населения придерживается иного набора правил, чем большая группа».
mhum
Понятно, я думал, что это относится к обществу, в котором у нас гомосексуальное население. Посмотрим, получим ли мы разъяснения по этому вопросу.
Юкка Суомела
Да, я имел в виду общество, в котором у нас есть подмножество этого населения, которое ведет себя с другими наборами правил.
IgorCarron