бы на ход, а лучше на два-три хода вперед. И второе – нужно обладать необходимой для этого информацией. И теперь мы можем вернуться в классическую ситуацию кавалеров, поющих серенады, и девушек, жестоко отказывающих одним и благосклонно динамящих других. Мужское население может сколь угодно долго иронизировать над девичниками, насквозь пропитанными сплетнями, однако именно девичьи сплетни могут позволить за счет стратегического поведения превратить патриархальный исход в матриархальный, даже если предлагать продолжают мужчины. Правда, проверить данное соображение на практике довольно проблематично.
7.2.3. Некоторые особые ситуации
В изначальной постановке было два множества участников – парни и девушки, однако в некоторых случаях, например при распределении студентов по комнатам общежития или работников компании по офисам с учетом пожеланий о соседях, приходится изучать «ситуацию однополых браков», когда представители обеих сторон принадлежат одному множеству, что бы под этим ни подразумевалось. Приведем неполиткорректный пример.
Пусть имеется компания, состоящая из четырех гомосексуалистов – Арчибальда (A), Вольдемара (B), Сигизмунда (C) и Дионисия (D). Пусть их предпочтения заданы следующим образом (рис. 7.2).
Рис. 7.2. Пример предпочтений четырех гомосексуалистов
Для каждого из первой тройки Дионисий стоит на последнем месте, хоть и выше нуля. При этом Арчибальд предпочитает Вольдемара Сигизмунду, Вольдемар предпочитает Сигизмунда Арчибальду, а Сигизмунд – Арчибальда Вольдемару. Предпочтения Дионисия, как мы увидим дальше, не имеют значения, главное, чтобы все трое для него тоже были выше нулевой черты.
Можно доказать утверждение, в корне противоположное тому, что мы узнали выше про «двудольную ситуацию»: в данной системе может не быть никакого устойчивого разбиения на пары. Продемонстрируем, что это действительно так. Для начала подумаем, сколько вообще систем паросочетаний возможно среди четырех людей. Их будет несколько меньше, чем кажется на первый взгляд – всего три. Действительно, например, выбор Арчибальдом любого из трех партнеров (здесь мы считаем, что отказаться нельзя) по сути задает не только его пару, но и пару двух оставшихся людей, поскольку им попросту не из кого останется выбирать. Поэтому достаточно просто проверить неустойчивость всех этих трех разбиений AB + CD, AC + BD и AD + BC.
Результат будет всегда одним и тем же: тот, кто в текущей ситуации находится с «изгоем» Дионисием, приходит к тому, у кого он находится на первом месте, и говорит: «Давай поженимся!» Сигизмунд придет к Вольдемару, Вольдемар – к Арчибальду, а Арчибальд – к Сигизмунду. Заметим, что каждому от этого становится лучше. Один получает самого желанного партнера, а второй уходит от нежеланного Дионисия. Таким образом, все три разбиения являются неустойчивыми и будут по циклу сменять друг друга.
Вывод: если разбивка на пары идет не между элементами двух различных непересекающихся множеств, а между элементами одного и того же множества, то красивый механизм, гарантированно приводящий к равновесию, перестает работать, и все заканчивается бардаком. Таков строгий математический результат, ставящий под сомнение необходимость легализовывать однополые браки. Смайл!
Тем не менее в 1985 году Роберт Ирвинг предложил эффективный алгоритм решения самой общей задачи. Алгоритм, имеющий сложность порядка квадрата от числа разбивающихся на пары людей, определяет, существует ли устойчивое разбиение, и находит его.
Еще одним интереснейшим обобщением, открывающим сложнейшую область науки, являются трехполые системы, которыми, в частности, одно время занимался ведущий российский специалист в области теории игр Владимир Иванович Данилов. В качестве запоминающейся аналогии с бракосочетаниями здесь можно привести распитие на троих бутылки водки, если в каждой выпивающей компании четко распределены роли – например, обязан быть «разливающий», «тостующий» и «нарезающий колбасу». Как и в случае парней и девушек, все эстеты-алкоголики имеют четкие предпочтения и не готовы выпивать «с кем попало». Однако если произвольный участник процесса желает перейти в другую компанию, а оба собутыльника оттуда готовы принять его взамен собственного третьего, то исходная ситуация не является устойчивым разбиением на тройки.
Несмотря на, казалось бы, незначительное усложнение условий, задача сразу же становится неимоверно трудной. Никаких общих выводов здесь до сих пор не получено. При этом полный перебор даже для случая три на три (девять выпивающих, распределяющихся по трем компаниям) весьма сложен, а для случая четыре на три (12 выпивающих в четырех компаниях) в полном объеме просто не проведен, поскольку без серьезного сокращения числа рассматриваемых вариантов он находится за гранью вычислительных возможностей современной техники. Так что можно вполне честно признаться: случай трехполых браков является открытой нерешенной задачей, в которой имеется некоторое количество любопытных примеров, но отсутствует общая теория.
Зато решена в положительном смысле задача с традиционными двумя полами, но разрешенным многоженством. Есть обобщение алгоритма Гейла-Шепли, приводящее к устойчивому разбиению на группы, в каждой из которых единственный «мужчина» женат на нескольких «девушках». Эта задача является особенно актуальной в контексте ряда практических приложений данной теории, к изучению которых мы сейчас и перейдем.
7.3. Приложения теории мэтчинга
7.3.1. Распределение абитуриентов по вузам
Конечно, несмотря на красивую историю о поиске невест, столь цинично спаривать математику и чувства в реальности не предлагается, и описанные выше механизмы используются для решения совсем иных практических задач. Этим, в частности, объясняется то, что модель жива, несмотря на многочисленные претензии к ее предпосылкам.
Например, модифицированный алгоритм Гейла-Шепли для случая многоженства может быть использован при поступлении выпускников школ в высшие учебные заведения. У каждого из выпускников в голове имеется упорядоченный список вузов, в которые он готовится поступать. Важно, что списки разных абитуриентов могут сильно различаться. Кто-то хочет уехать в столицы, а кто-то остаться дома (к сожалению, в провинции такое случается крайне редко); кто-то стремится поступить в топовый вуз и впахивать там, а кто-то предпочитает с минимальными издержками получить диплом; есть выбор друзей (этот факт ситуацию сильно осложняет, делая совсем игровой) и мнение родителей, с которыми нельзя не считаться, и т. д.
Аналогично большинство вузов предпочло бы принять сильных и мотивированных на обучение студентов. Конечно, информации об абитуриентах у вузов не так много, но даже ЕГЭ (при всех его недостатках) довольно много говорит о знаниях и серьезности намерений поступающего (кстати, заметим, что не все практики понимают, что информация о баллах ЕГЭ тоже многомерная и для одних вузов ЕГЭ по русскому языку важнее ЕГЭ по математике, а для других – наоборот). Ну а добавкой может выступать портфолио – победы на олимпиадах и конкурсах, спортивные достижения, рекомендации уважаемых людей и прочая дополнительная информация.
Таким образом, мы оказываемся в условиях классической задачи о марьяжах в ее множественной постановке – нужно «поженить» вузы на абитуриентах наилучшим образом, то есть так, чтобы ни один абитуриент
