Математика смешанного разряда

В первых двух пунктах полезно заметить, что так как Валентина для Бориса и Борис для Валентины является наилучшим партнером, то в любом устойчивом разбиении на пары они будут вместе.

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

Первый способ подойти к решению предложенных задач — «в лоб».

В первых двух пунктах, как говорилось в подсказке, Валентина должна быть в паре с Борисом. После этого остается шесть возможных разбиений на пары, из которых перебором несложно найти один устойчивый вариант: «Анна+Георгий», «Белла+Андрей», «Валентина+Борис», «Галина+Виктор».

В третьем пункте, так как у юношей первые по предпочтению девушки разные, то разбиение на пары «Андрей+Анна», «Борис+Белла», «Виктор+Валентина», «Георгий+Галина» будет устойчивым (поскольку никто из юношей не откажется от своей пары). Так как у девушек первые по предпочтению юноши разные, то разбиение на пары «Андрей+Галина», «Борис+Валентина», «Виктор+Белла», «Георгий+Анна» также будет устойчивым.

Другой подход хорошо работает при любом количестве разбиваемых на пары спортсменов и при этом избавляет от перебора (который с ростом числа юношей и девушек быстро становится слишком трудоемким). Оказывается, что для произвольного количества девушек и юношей и для любых предпочтений всегда существует устойчивое разбиение на пары. Более того, имеется алгоритм нахождения такого разбиения, придуманный американскими математиками и экономистами Дэвидом Гейлом и Ллойдом Шепли в 1962 году.

Этот алгоритм состоит из следующих шагов.

Сначала мы выбираем одну из сторон, например юношей.

    1) Юноша делает предложение (пишет сообщение) первой девушке в своем списке. Если девушка получила несколько предложений, то она отказывает всем, кто не самый лучший с ее точки зрения. А сообщение от самого лучшего пока оставляет у себя.
    2) В каждом последующем раунде сначала каждый юноша, которой получил отказ, делает предложение наиболее предпочтительной девушке, которая ему не отказала. И снова девушки, получившие несколько сообщений (учитывая предыдущие раунды) отказывает всем, кроме самого лучшего.
    3) Продолжаем этот процесс, пока он не закончится. В конце все текущие пары объявляем окончательными.

В условиях первого пункта этот алгоритм работает так:

Раунд 1. Анна получает сообщение от Андрея, Белла — от Георгия, Валентина от Виктора и Бориса. Валентина отказывает Виктору (для Валентины Борис предпочтительнее), остальные юноши отказов не получают. Текущие «пары»: «Анна+Андрей», «Белла+Георгий», «Валентина+Борис».

Раунд 2. Виктор пишет Белле (она — следующая после Валентины в списке предпочтений Виктора). У Беллы теперь два сообщения — от Георгия и от Виктора. Она отказывает Георгию (он менее предпочтителен для нее, чем Виктор). Текущие «пары»: «Анна+Андрей», «Белла+Виктор», «Валентина+Борис».

Раунд 3. Георгий пишет Анне. Анна отказывает Андрею. Текущие «пары»: «Анна+Георгий», «Белла+Виктор», «Валентина+Борис».

Раунд 4. Андрей пишет Белле. Белла отказывает Виктору. Текущие «пары»: «Анна+Георгий», «Белла+Андрей», «Валентина+Борис».

Раунд 5. Виктор пишет Галине. Теперь у каждой девушки по одному предложению. Алгоритм заканчивается.

Окончательное разбиение на пары: «Анна+Георгий», «Белла+Андрей», «Валентина+Борис», «Галина+Виктор».

Данный алгоритм можно провести и со стороны девушек: девушки пишут сообщения, а юноши отказывают. Для этой же ситуации это будет выглядеть так:

Раунд 1. Андрей получает сообщение от Анны, Борис — от Валентины и Беллы, Виктор — от Галины. Борис отказывает Белле.

Раунд 2. Белла пишет сообщение Георгию, алгоритм заканчивается.

Итоговые пары: «Анна+Георгий», «Белла+Андрей», «Валентина+Борис», «Галина+Виктор».

Как мы видим, в обоих случаях получилось одно и тоже разбиение на пары. Это означает, что существует единственное устойчивое разбиение на пары для данных списков предпочтений.

Этот вывод верен в общей ситуации. Верна следующая теорема:

Теорема. В результате работы описанного алгоритма получается устойчивое разбиение на пары. Более того, данное разбиение на пары является наилучшим со стороны тех, кто пишет сообщения, и наихудшим для тех, кто их получает.

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

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

Более интересный вопрос — как найти все возможные разбиения на пары? Ведь если предложенные разбиения плохи либо для девушек, либо для юношей, то хочется найти «золотую середину». На самом деле и такой алгоритм есть. Идея в следующем: в имеющемся разбиении на пары (к примеру, оптимальном для юношей) положим, что в одной из пар девушка отказала юноше и продолжим работу того же алгоритма. Если он остановится, и у каждого будет пара, то мы получим новое устойчивое разбиение на пары. Запуская таким образом алгоритм, вычеркивая разные пары, можно найти все устойчивые разбиения.

На примере третьего пункта это выглядит так.

Имеющееся разбиение: «Андрей+Анна», «Борис+Белла», «Виктор+Валентина», «Георгий+Галина».

Допустим, Анна отказывает Андрею. Тогда Андрей пишет Белле, Белла отказывает Борису, Борис пишет Анне.

Новое разбиение: «Андрей+Белла», «Борис+Анна», «Виктор+Валентина», «Георгий+Галина».

Если в изначальной ситуации Валентина отказывает Виктору, то Виктор пишет Галине, Галина отказывает Георгию, и получается новое разбиение: «Андрей+Анна», «Борис+Белла», «Виктор+Галина», «Георгий+Валентина».

На самом деле в данной задаче всего имеется 10 устойчивых разбиений на пары и это максимально возможное количество устойчивых разбиений для 4 юношей и 4 девушек.

Описанная выше задача (в литературе она известна под названием «задача о марьяже») является наиболее упрощенной моделью формирования двусторонних рынков. Здесь под двусторонним рынком подразумевается некоторая совокупность экономических агентов, которая разбита на два множества, взаимодействующие между собой. Эта конструкция позволяет эмулировать (а значит, и исследовать с точки зрения экономики и социологии) самые разнообразные типы взаимодействий: рынок труда (работники и фирмы), образование (школьники/студенты и школы/вузы), распределение нагрузки в интернете (пользователи и сервера), товарооборот в торговле (поставщики и магазины) и так далее.

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

Естественный вопрос для таких рынков: «Кто с кем окажется в паре?». Более существенные вопросы: существует ли устойчивое размещение агентов на этих рынках? Если существует, единственно ли оно? Если их несколько, какое из них естественно выбрать?

Приведенный в решении алгоритм Гейла — Шепли отвечает на первый вопрос. Более того, он легко обобщается на случай рынка «один на много». Что интересно, на практике похожий алгоритм применялся немного ранее, чем Гейл и Шепли его сформулировали и доказали корректность его работы. Эта история подробно описана в статье Е. Железовой, С. Измалкова, К. Сонина и И. Хованской Теория и практика двусторонних рынков. В ней обсуждаются основные идеи теории, за развитие которой Ллойд Шепли и Элвин Рот получили Нобелевскую премию по экономике в 2012 году. Вот отрывок из этой статьи:

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

    1. Будущие интерны и больницы обменивались информацией друг о друге.
    2. Каждый из участников эксперимента составлял собственный лист предпочтений.
    3. После выполнения первых двух этапов, на основании списка предпочтений каждого из участников эксперимента алгоритм автоматически распределял студентов по больницам.

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

Данная система распределения не была обязательной, но в эксперименте приняли участие больше 95% студентов и больниц. Эта цифра оставалась неизменной до 1970 года. Чем дольше алгоритм использовался, тем больше росло недовольство им со стороны студентов. С одной стороны, алгоритм был составлен так, чтобы оптимизировать распределение с точки зрения госпиталей. А с другой стороны, достаточно много участников (порядка 1000 из 20 000) хотели найти работу вместе с кем-то еще (например, мужем или женой). В базовом виде алгоритм не учитывал совместные предпочтения. В 1995 году Роту предложили модифицировать алгоритм, чтобы учесть семейные связи, и с 1997 года используется новый модифицированный алгоритм (A. E. Roth, E. Peranson, 1999. The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design).