Занимательная экономика. Теория экономических механизмов от А до Я

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

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

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

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

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

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

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

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

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

Несмотря на, казалось бы, незначительное усложнение условий, задача сразу же становится неимоверно трудной. Никаких общих выводов здесь до сих пор не получено. При этом полный перебор даже для случая три на три (девять выпивающих, распределяющихся по трем компаниям) весьма сложен, а для случая четыре на три (12 выпивающих в четырех компаниях) в полном объеме просто не проведен, поскольку без серьезного сокращения числа рассматриваемых вариантов он находится за гранью вычислительных возможностей современной техники. Так что можно вполне честно признаться: случай трехполых браков является открытой нерешенной задачей, в которой имеется некоторое количество любопытных примеров, но отсутствует общая теория.

Зато решена в положительном смысле задача с традиционными двумя полами, но разрешенным многоженством. Есть обобщение алгоритма Гейла-Шепли, приводящее к устойчивому разбиению на группы, в каждой из которых единственный «мужчина» женат на нескольких «девушках». Эта задача является особенно актуальной в контексте ряда практических приложений данной теории, к изучению которых мы сейчас и перейдем.

7.3. Приложения теории мэтчинга

7.3.1. Распределение абитуриентов по вузам