7.2.3. Некоторые особые ситуации

7.2.3. Некоторые особые ситуации

В изначальной постановке было два множества участников – парни и девушки, однако в некоторых случаях, например при распределении студентов по комнатам общежития или работников компании по офисам с учетом пожеланий о соседях, приходится изучать «ситуацию однополых браков», когда представители обеих сторон принадлежат одному множеству, что бы под этим ни подразумевалось. Приведем неполиткорректный пример.

Пусть имеется компания, состоящая из четырех гомосексуалистов – Арчибальда (A), Вольдемара (B), Сигизмунда (C) и Дионисия (D). Пусть их предпочтения заданы следующим образом (рис. 7.2).

Рис. 7.2. Пример предпочтений четырех гомосексуалистов

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

Можно доказать утверждение, в корне противоположное тому, что мы узнали выше про «двудольную ситуацию»: в данной системе может не быть никакого устойчивого разбиения на пары. Продемонстрируем, что это действительно так. Для начала подумаем, сколько вообще систем паросочетаний возможно среди четырех людей. Их будет несколько меньше, чем кажется на первый взгляд – всего три. Действительно, например, выбор Арчибальдом любого из трех партнеров (здесь мы считаем, что отказаться нельзя) по сути задает не только его пару, но и пару двух оставшихся людей, поскольку им попросту не из кого останется выбирать. Поэтому достаточно просто проверить неустойчивость всех этих трех разбиений AB + CD, AC + BD и AD + BC.

Результат будет всегда одним и тем же: тот, кто в текущей ситуации находится с «изгоем» Дионисием, приходит к тому, у кого он находится на первом месте, и говорит: «Давай поженимся!» Сигизмунд придет к Вольдемару, Вольдемар – к Арчибальду, а Арчибальд – к Сигизмунду. Заметим, что каждому от этого становится лучше. Один получает самого желанного партнера, а второй уходит от нежеланного Дионисия. Таким образом, все три разбиения являются неустойчивыми и будут по циклу сменять друг друга.