Проблема стабильного брака - пустые списки предпочтений

Question

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

Я прочитал о проблеме в отношении на неполные списки и связи et c. но я не вижу специфического c упоминания о пустом списке. Мои первоначальные мысли были бы в соответствии с этим лечением, так как все оценивали его как ie, но я не уверен, что это был бы лучший способ увидеть вещи. Как бы это было обработано?

Извинения, если об этом спросили / ответили в другом месте. Я также прошу прощения, если есть очень очевидный ответ на этот вопрос, мой мозг в настоящее время жарен в любом случае. Заранее спасибо за любую помощь.

Answer 1

Пустой список - это крайний случай неполного списка: человек указал, что нет совпадений для него приемлемы, поэтому гарантировано , что (а) он в конечном итоге не имеет себе равных.

Кстати, небольшая терминологическая заметка: термин «стабильный брак [проблема]», когда он не изменен, обычно обозначает исходную версию проблемы, где есть равное количество мужчин и женщины и каждый человек предоставляет полный упорядоченный список всех представителей противоположного пола. Таким образом, нет «неполных списков и связей и т. Д. c.» И, следовательно, нет пустых списков. Расширение проблемы стабильного брака может вводить поддержку неполных списков и / или связей и / или разного количества мужчин и женщин, и в этом случае они получают имена, такие как "стабильный брак [проблема] с неполными списками" и скоро. Мы могли бы даже представить себе разные расширения, у которых у всех есть «неполные списки», но им присвоены разные значения, хотя на практике я думаю, что все расширения с «неполными списками» присваивают им одинаковое значение.

Answer 2

Я полагаю, что если кто-то не заполняет свой список предпочтений, то это будет означать, что этот человек не против того, с кем его сравнивают. Действительно, алгоритм был бы немного застрял в этом особом случае, но логичным решением было бы - в самом конце алгоритма - сопоставить их с тем, кого еще никто не сравнивал (если мы предположим, что этот человек - единственный человек, который не заполнил их список предпочтений вообще).

Это чисто предположение, но, на мой взгляд, это был бы логичный подход к этой ситуации.