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