Задача о соседях по комнате

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

Задача обычно формулируется следующим образом:

Имеется 2n участников, и каждый выстраивает строгое предпочтение для остальных участников (сортирует остальных участников по уменьшению предпочтения); заметьте, что два участника не могут иметь одинаковое предпочтение: они отличаются хотя бы предпочтением друг друга. Нужно найти множество из n пар с лучшим соответствием: соответствие M стабильно, если никакие два участника из разных пар не предпочитают друг друга своим настоящим соседям.

Решение

В отличие от задачи о супружеских парах, задача о соседях по комнате может и не иметь, вообще говоря, решения. Например, пусть имеется четверо лиц — A, B, C и D, имеющих предпочтения:

A:(B,C,D), B:(C,A,D), C:(A,B,D), D:(A,B,C)

В любом решении кто-нибудь из A, B или C должен быть назначен в пару D, а оставшиеся два образуют вторую пару (например, AD и BC). Но партнер D и кто-нибудь из второй пары будут предпочитать друг друга. В нашем примере такой парой будет AC.

Алгоритм

Эффективный алгоритм решения предложен Ирвингом в 1985 году. Алгоритм определяет, существует ли решение задачи и, если существует, находит его.

Алгоритм Ирвинга имеет сложность O(n²). Он определяет подходящие структуры данных для манипуляции со списками предпочтения и перестановками (смотрите ниже).

Алгоритм содержит 2 этапа. На первом этапе участники делают предложение друг другу, примерно так же, как это делается в алгоритме Гейла — Шепли для задачи о марьяже. Участники предлагают создать пару последовательно каждому лицу из своего списка предпочтения, переходя к следующему лицу в списке в случае отказа создать пару. Участник отказывает создать пару, если он уже имеет предложение от лица, которое он предпочитает больше. На этом этапе один участник может быть отвергнут всеми остальными участниками, что свидетельствует об отсутствии стабильного решения. В противном случае этап 1 завершается тем, что каждый участник имеет предложение от какого-либо участника. Эта ситуация может быть представлена как набор S упорядоченных пар вида (p,q), где q имеет предложение от p, и мы говорим, что q является текущим фаворитом p. Если этот набор является решением, то есть для любого (q,p) из S (p,q) тоже содержится в S, алгоритм завершается и это решение стабильно.

В противном случае переходим к этапу 2, на котором набор S последовательно изменяется с помощью так называемых перестановок. Пусть (p,q) принадлежит S, но (q,p) не принадлежит. Для каждого такого p определяем его текущего второго фаворита, являющегося следующим участником в списке предпочтений участника p после q, который может принять предложение p. Перестановка в S — это последовательность (p₀,q₀), (p₁,q₁),. . ., (p_k-1,q_k-1), такая, что (p_i,q_i) входит в S для любого i, и q_i+1 является вторым фаворитом участника p_i (здесь i + 1 берётся по модулю k). Если такая перестановка (p₀,q₀), . . . , (p_2k,q_2k) имеет нечетную длину, мы нашли так называемый нечетный набор, который показывает, что стабильного соответствия нет. В противном случае заменяем пары (p_i,q_i) на (p_i,q_i+1) (где i + 1 берётся по модулю k).

Этап 2 алгоритма можно представить следующим образом:

	S = output of Phase 1;
	while (true) {
	    identify a rotation r in S;
	    if (r is an odd party)
		return null; (there is no stable matching)
	    else
		apply r to S;
	    if (S is a matching)
		return S; (guaranteed to be stable)
	}

Пример

Задан список предпочтений для шести участников p₁, p₂, p₃, p₄, p₅, p₆.

p₁ :   p₃   p₄   p₂   p₆   p₅
p₂ :   p₆   p₅   p₄   p₁   p₃
p₃ :   p₂   p₄   p₅   p₁   p₆
p₄ :   p₅   p₂   p₃   p₆   p₁
p₅ :   p₃   p₁   p₂   p₄   p₆
p₆ :   p₅   p₁   p₃   p₄   p₂

Возможное выполнение этапа состоит из следующих предложений и отказов, где → представляет предложение и × представляет отказ.

p₁ → p₃
p₂ → p₆
p₃ → p₂
p₄ → p₅
p₅ → p₃;   p₃ × p₁
p₁ → p₄
p₆ → p₅;   p₅ × p₆
p₆ → p₁

Таким образом, этап 1 завершается набором S = {(p₁,p₄), (p₂,p₆), (p₃,p₂), (p₄,p₅), (p₅,p₃), (p₆,p₁)}.

На этапе 2 обнаруживается перестановка r₁ = (p₁,p₄), (p₃,p₂). Это вытекает из того, что p₂ является вторым фаворитом участника p₁, а p₄ является вторым фаворитом участника p₃. Используем r₁ для получения нового набора S = {(p₁,p₂), (p₂,p₆), (p₃,p₄), (p₄,p₅), (p₅,p₃), (p₆,p₁)}. Теперь обнаруживается перестановка r₂ = (p₁,p₂), (p₂,p₆), (p₄,p₅), и она дает набор S = {(p₁,p₆), (p₂,p₅), (p₃,p₄), (p₄,p₂), (p₅,p₃), (p₆,p₁)}. Наконец, перестановка r₃ = (p₂,p₅), (p₃,p₄) дает S = {(p₁,p₆), (p₂,p₄), (p₃,p₅), (p₄,p₂), (p₅,p₃), (p₆,p₁)}. Последнее соответствие является стабильным решением.

Ссылки

• Robert W. Irving, David F. Manlove. The Stable Roommates Problem with Ties // Journal of Algorithms. — 2002. — Т. 43, вып. 1. — С. 85—105. — doi:10.1006/jagm.2002.1219.