На практике часто возникает задача распределения объектов или людей в пары друг с другом. Например, распределение сотрудников по вакансиям, формирование комитетов, распределение абитуриентов по вузам. Сегодняшняя лекция посвящена теории и практике построения механизмов такого распределения с учетом предпочтений индивидов. Она была прочитана на факультете компьютерных наук, открытом в Вышке при поддержке Яндекса.



Лектор – Софья Геннадьевна Кисельгоф, младший научный сотрудник Международной научной лаборатории анализа и выбора решений НИУ ВШЭ. Преподаватель департамента математики экономического факультета. На факультете компьютерных наук читает курс Operations Research and Game Theory. Защитила кандидатскую диссертацию на тему «Обобщенные паросочетания при предпочтениях, не являющихся линейными порядками». Софья Геннадьевна проводила исследование механизма зачисления абитуриентов в российские вузы в результате которого была построена модель, описывающая поведения абитуриента при выборе вуза.

Под катом – подробная стенограмма лекции.

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

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

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

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

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

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

В этом примере известно, что второй мужчина М2 может вступать в пары (танцевать, вступать в брак) либо с женщиной W2 или с женщиной W4. Задача обобщенного паросочетания позволяет этого мужчине сообщить свои предпочтения.Он может высказать свои пожелания: какая-то женщина симпатична, какая-то нет. Есть некий центральный планировщик, который заключает эти браки или ставит их танцевать, то он как свободный человек просто откажется от такого предложения. В самом простом случае каждый мужчина и каждая женщина могут упорядочить всех потенциальных партнеров.

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

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

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

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

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

Более того, это все результат первой задачи, которая была поставлена Гейлу и Шепли. Они предложили именно механизм, который позволяет найти это паросочетание. Он работает следующим образом. Поскольку на уровне теории группы мужчины и женщины симметричны. На первом шаге мужчина делает предложение той женщине, которая ему больше всего нравится. Если есть такой мужчина, который не хочет вступать в брак, то он даже не рассматривается. Какие-то женщины могут за раз получить больше одного предложения, что она делает: она рассматривает все предложения, которые ей поступили и выбирает то, которое нравится больше всего. Выбирает того мужчину, который ей нравится больше всего. И дальше она принимает его предложение, но временно. Все остальные мужчины узнают, что с ней брак невозможен, они начинают действовать дальше. На втором шаге история повторяется: мужчины делают предложение той женщине, которая у них следующая по списку. Опять же некоторые женщины могут получить несколько предложений, она опять выбирает лучшее.

Единственное, о чем бы хотелось сказать еще волнует экономическую составляющую. Хорошо, мы предложили такой механизм, чтобы его реализовать в реальной жизни или в вычислительном плане, нам нужны предпочтения участников. Возникает вопрос, скажут ли они нам правду, мы ведь не знаем, что у них в голове, и нам нужно узнать, что они думают. Вопрос: будут ли они говорить правду? Хорошим ответом было бы, что да – будут, но он, к сожалению, не такой. Если мы рассмотрим механизм с предлагающими мужчинами, то мужчины заинтересованы в том, чтобы сказать правду, для них слабо доминирующей стратегией является то, что они желают сообщить настоящие предпочтения. Они могут сообщить что-то другое. Это не изменит их результат или ухудшит. К сожалению, про женщин этого сказать нельзя, потому что женщины, сообщив неправильные сведения механизму, могут улучшить свой результат. Первое но. Если они будут манипулировать в своих интересах, то паросочетание, которое будет построено, будет устойчиво при исходных предпочтениях. Если они даже соврали, паросочетание будет устойчиво, потому что женщины улучшили свое положение, видимо, за счет мужчин, но результат, который получился, все равно устойчив.

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

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

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

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

Что касается примеров, где это все используется. Система распределения выпускников — интернов в больницы. Теоретический механизм был придуман случайно и активно сейчас применяется на практике. Распределение детей в детские сады. И другие.

Начнем с первой программы National Resident Program. Как проиходит распределение. Медик заканчивает обучение в вузе, затем, чтобы получить медицинскую лицензию, он должен еще пройти интернатуру. Это работа, заключается контракт с медицинской ассоциацией, которая его нанимает. Система распределения вузов и больниц предложили установить единую дату подписания контрактов с выпускниками текущего года. Когда были установлены контрольные даты, немедленно самые смекалистые руководители больниц стремились заключить контракты до этих дат, чтобы заполучить лучших выпускников как можно раньше. Все это происходило по телефону, интернета еще не было. Единая медицинская ассоциация использовала разные способы (кодекс чести, который запрещал делать предложения раньше установленной даты; разные алгоритмы использовал). Мучались лет 6. Потом начали предлагать централизованные процедуры (каждый выпускник высказывал свои пожелания насчет больницы, где бы он хотел работать). Больницы сообщали, кого они хотели бы взять. Сначала был предложен механизм, который строил паросочетания. Когда уже исследователи постфактум анализировали тот механизм, который они предложили, выяснили, что он строил распределения, но неустойчивые, то есть образовывались блокирующие пары. Этот механизм не продержался и двух лет. При отсутствии открытой информации о предпочтениях, о свободных местах, механизм не работал. Все свелось к предварительному заключению контрактов.

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

В 1950-х, когда все это начиналось уровень эмансипации был низким, было 3-5% женщин. К 1980-м стало примерно 50\50. Стали образовываться семьи, а предпочтения семьи это не предпочтения одного индивида, это гораздо сложнее (учитываются личные интересы каждого из супругов, плюс совместные, насчет того, чтобы оказаться в одном регионе). Такие семейные пары пытались договариваться в обход, чтобы получить работу в одном месте и поскольку здесь фигурируют частные клиники и выпускники, которые никому ничего не должны, то больницы имели право не заявить о части своих мест в централизованную процедуру и договориться с людьми в обход системы.

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

Если вернуться к словам абитуриент-вуз, то централизованная схема приема используется в разных странах. Чтобы такая система существовала, необязательно нужны единые госэкзамены или единая система оценивания. Это могут быть и предварительные собеседования. Если вернуться к вопросу манипулирования, то вузы не манипулируют предпочтениями на этапе ранжирования тех, с кем провели собеседовние. Могут играть на этапе отбора тех абитуриентов, которых будут собеседовать.Это работает.

Сейчас стоит вопрос, как этап собеседования включить в механизм, ухудшает ли общее манипулирование ситуацию, влияет ли на общую эффективность? Лично я по этому вопросу ничего не могу сказать: вредит ли это, портит ли эффективность.

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

Здесь возникает вопрос: есть школьники, которые хотят попасть в определенную школу, но количество мест ограничено размерами классов и количеством учителей. Нужно ли здесь говорить об устойчивости? Здесь предпочтений нет, потому что школам все равно, кого брать. Можно подумать, что концепция устойчивости вообще не нужна здесь, но любопытно, что когда задумали переделывать систему распределения и были озвучены чиновником образования, они сказали, что подумают. Подумали и сказали, что им нужна устойчивость. Аргумент был такой: попарная устойчивость не является причиной физического отказа людям, а является проблемой в смысле справедливости. Что такое блокирующая пара. Я хочу в школу А, я туда не попала, но в школе А есть какой-то ученик, который имеет более низкий приоритет по каким-то социально-демографическим характеристикам, чем я. В развитых странах в таких ситуациях идут в суд, так как здесь нарушение прав и закона. Школы не заинтересованы в том, чтобы выгнать этого ученика и взять меня, проблема возникает в понимании справедливости. Есть приоритеты, установленные законом, и они должны учитываться. Хотя по сути это приводит к потери эффективности потому, что может быть такая ситуация: 1-й ученик хочет во 2-ю школу, а 2-й ученик хочет в 1-ю школу, но имеют низкие приоритете в тех школах, в которые хотят попасть, и они могли бы просто поменяться местами, но если они поменяются, то некий третий ученик начнет предъявлять претензии. В конечном итоге, для школьного распределения используются механизмы, которые строят устойчивые паросочетания.