Как правильно всех переженить? Лекция

В рамках проекта «Публичные лекции „Полит.ру“» профессор экономики Российской экономической школы, обладатель гранта национального исследовательского фонда США (NSF) Сергей Измалков прочитал лекцию «Как правильно всех переженить?». Slon публикует сокращенную версию этой лекции.

Тема, как ни странно, связана с Нобелевской премией по экономике, которую присудили в этом году американским ученым Ллойду Шепли и Элвину Роту за теорию стабильных размещений и применение ее на практике.

Представьте, что вам досталось некоторое место в самолете – 25А. А другой человек получил, например, место 17С. Возникает вопрос: может ли случиться такая ситуация, что люди захотят поменяться? И существует ли такой механизм обмена, при использовании которого всем станет лучше? Основная проблема здесь – проблема текущего распределения, разбиения по парам. Устойчиво ли это разбиение? Подобные вопросы и лежат в основе исследований Шепли и Рота.

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

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

Алгоритм Шепли – Скарфа и квартирный вопрос

Разберем сначала более простой вопрос – квартирный. Есть люди, которые владеют жилплощадью. Что, если мне нравится квартира соседа, а ему – моя? Или чья-то еще. Здесь вступает в действие алгоритм Шепли – Скарфа.

Предположим, что есть шесть домов, в которых живет шесть человек. Первый предпочел бы жить в доме третьего, на втором месте в его предпочтениях – дом пятого человека, на третьем – его собственный домик, на четвертом – второй, потом – открытое небо (ну не нравится ему дом №6), наконец, на последнем месте – шестой дом. И у каждого владельца есть какие-то свои предпочтения.

Как работает алгоритм? Берем любого из этих людей, например первого, и спрашиваем: «Какой дом тебе нравится больше всего?» Он называет третий. Тогда мы спрашиваем человека из третьего дома, где бы он хотел жить. Допустим, он говорит, что хочет себе дом №2. Владелец этого дома хочет себе дом №4, а хозяин четвертого дома отдает предпочтение дому №3. Если выстроить такую цепочку, то получится цикл: 1 – 3 – 2 – 4 – 3. Если мы устроим обмен между владельцами третьего, второго и четвертого домов, то каждый из них получит наилучший для себя дом. Цикл завершен, эти дома вычеркиваем.

Тогда спрашиваем первого человека опять, какой дом он выберет, раз третий уже занят. Он говорит, что пятый. Если бы владелец пятого дома сказал, что желает оставить свой дом, то цикл был бы завершен. Но пятый показывает на шестой дом, а человек из дома №6 – на пятый. Они меняются. Все поменялись, кроме первого, он остается жить в своем доме.

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

Алгоритма Гейла – Шепли и поиск мужа

Теперь главный вопрос: как найти мужа или жену? Вернемся к нашей деревне. Один из вариантов алгоритма Гейла – Шепли можно представить следующим образом. Все мужчины делают предложение тем девушкам, которые нравятся больше всего. Затем все девушки (кто-то из них получает много предложений) эти предложения рассматривают и отвергают худшие из них, оставляя по одному. Это не значит, что предложение принято, но на данный момент у каждой девушки по одному предложению. Соответственно, отвергнутые мужчины должны делать новые предложения. Девушки, у которых несколько предложений, отвергают самые худшие и т.д. Как только новых предложений нет, текущие предложения принимаются, – и все счастливы.

Как это работает? Предположим, есть 4 парня: Андрей, Сергей, Олег и Макар. Есть 4 девушки: Оля, Лена, Катя и Наташа. У всех опять же свои предпочтения, которые иногда могут совпадать. Они представлены в таблицах.

Андрей и Олег делают предложения Оле, а Сергей и Макар – Лене. Это их наилучшие варианты. Что происходит дальше? Оля предпочитает Олега Андрею, поэтому оставляет его предложение (но это не значит, что она занята!), Лена принимает предложение Макара. Андрей и Сергей отвергнуты, то есть на следующем шаге они делают новые предложения: Андрей – Лене, а Сергей – Наташе.

Таким образом, у Оли и Наташи по одному предложению, у Лены – два, худшее из которых она должна отвергнуть. Она отвергает Макара, и он делает новое предложение – Оле (потому что она у него вторая в списке). Оля выбирает между Олегом и Макаром и отвергает Олега, который делает теперь предложение Кате. У каждой девушки по одному предложению, получаются пары: Андрей – Лена, Сергей – Наташа, Олег – Катя, Макар – Оля. На этом алгоритм завершен.

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

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

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