Здравствуйте! На этой неделе мы с вами поговорим об одной из самых актуальных теоретико-игровых задач. В 2012 году Нобелевскую премию по экономике получили Эл Рот и Ллойд Шепли за теорию стабильных размещений и её имплементацию на практике в дизайне рынков. Мы с вами поговорим о теоретических основаниях этой задачи и обсудим её применение на практике. Итак, общая постановка задачи выглядит следующим образом. Пусть у нас есть агенты двух типов. У агентов одного типа есть предпочтения на множестве агентов другого типа. Например, мы можем говорить о мужчинах и женщинах, об университетах и абитуриентах, о донорах и реципиентах. У каждого мужчины могут быть предпочтения на множестве женщин и наоборот. Университеты хотят отобрать как можно более сильных студентов. В то же время у абитуриентов есть предпочтения по качеству университетов. Не каждому донору подойдёт любой реципиент и наоборот. Итак, общая постановка задачи состоит в том, чтобы распределить агентов одного типа по агентам другого типа. Причём нужно сделать это так, чтобы все были довольны. Можно ли так сделать, мы обсудим сегодня. Эта задача была формализована в работе Гейла и Шепли, которая вышла в 1962 году. Они рассмотрели в этой работе две, на первый взгляд, похожие модели. Первая модель была моделью свадебного рынка. О ней мы особенно подробно поговорим сегодня. Вторая модель касалась распределения студентов по колледжам. Разница состоит в том, что в случае свадебного рынка нам нужно поставить в соответствие каждому агенту одного типа одного агента другого типа. В случае распределения студентов по колледжам нам нужно агенту одного типа, то есть колледжу, поставить в соответствие сразу несколько агентов другого типа, то есть студентов. Как мы увидим, разница между двумя этими постановками задачи достаточно серьёзная. Для начала нам нужно дать несколько определений. Пусть у нас зафиксировано некоторое множество альтернатив A. Пока это абстрактное множество альтернатив. Мы будем называть предпочтениями произвольное множество упорядоченных пар альтернатив (x, y). Упорядоченная пара — это означает, что мы зафиксировали, какая альтернатива из этой пары является первой, какая альтернатива из этой пары является второй. Тот факт, что пара (x, y) принадлежит предпочтениям, также может быть записан в виде отношения x ≻ y. Читать такое отношение мы будем так: альтернатива x лучше альтернативы y. Давайте рассмотрим пример. Пусть у нас множество альтернатив такое: куда пойти сегодня вечером? Можно пойти на футбол, можно пойти в кабак, можно пойти на балет. Давайте рассмотрим первого агента. Пусть у Ивана Петровича предпочтения устроены следующим образом. Если Ивану Петровичу предложить выбор между футболом и балетом, то он предпочтёт футбол, а если ему предложить выбор между балетом и кабаком, то он предпочтёт балет. Это набор упорядоченных пар альтернатив, и он является предпочтениями Ивана Петровича. У другого агента, у Семёна Тимофеевича, предпочтения могут быть такими: если ему предложить выбор между футболом и балетом, то он выберет футбол. Если ему предложить выбрать между балетом и кабаком, то он пойдёт на балет. А если ему предложить выбор между кабаком и футболом, то он выберет кабак. Таким образом, Семён Тимофеевич может сравнить абсолютно любую пару альтернатив. Теперь мы определим несколько свойств предпочтений. Мы не можем изучать произвольных агентов, нам нужно, чтобы предпочтения этих агентов были достаточно хорошими, чтобы их поведение можно было описать с помощью рациональных предпосылок. Итак, мы будем говорить, что предпочтения, заданные на множестве альтернатив, называются полными, если для любых двух альтернатив a и b выполняется хотя бы одно из двух соотношений: либо a ≻ b, либо b ≻ a. Например, если у нас есть то же самое множество альтернатив, которое мы только что рассмотрели, и рассмотрим того же самого агента Ивана Петровича, и рассмотрим его предпочтения. Так вот, предпочтения Ивана Петровича полными не будут, потому что если мы предложим Ивану Петровичу выбор между кабаком и футболом, то он этот выбор сделать не сможет: для него ни одна из этих альтернатив не является лучше, чем другая. А вот если мы предложим какой-нибудь выбор Семёну Тимофеевичу, то он этот выбор на основе своих предпочтений сделать сможет. Какую бы пару альтернатив Семёну Тимофеевичу ни предложить, для него одна из них будет лучше, чем другая. Если мы ему предложим выбор между футболом и балетом, он пойдёт на футбол, если между балетом и кабаком, то на балет, а если между кабаком и футболом, то в кабак. Предпочтения Семёна Тимофеевича являются полными. Еще одно определение. Предпочтения, заданные на множестве альтернатив A, называются транзитивными, если какие бы три альтернативы a, b и c мы ни взяли, такие, что выполняются соотношения a ≻ b и b ≻ c, то вот для таких трёх альтернатив обязано выполняться соотношение a ≻ c. Давайте опять рассмотрим наши примеры. Предпочтения у Ивана Петровича не являются транзитивными, потому что мы можем рассмотреть три альтернативы: футбол, балет и кабак. Для этих трёх альтернатив выполняются такие соотношения: футбол лучше балета, а балет лучше кабака. Значит, по определению транзитивности, должно было бы выполняться соотношение, что футбол лучше кабака. Однако если предложить Ивану Петровичу выбор между футболом и кабаком, он этот выбор сделать не сможет. Такая пара не входит в набор его предпочтений. Поэтому условие, которое фигурирует в определении транзитивности предпочтений, не выполняется. И это означает, что предпочтения Ивана Петровича транзитивными не являются. У Семёна Тимофеевича предпочтения тоже нетранзитивны. Мы опять можем взять ту же тройку альтернатив: футбол лучше балета, балет лучше кабака, — значит, по определению транзитивности, должно было бы выполняться, что футбол для Семёна Тимофеевича лучше кабака. Однако предпочтения у Семёна Тимофеевича устроены таким образом, что если ему предложить выбор между кабаком и футболом, то он выберет кабак, а вовсе не футбол. Поэтому определение транзитивности снова не выполняется для этих предпочтений, и они у Семёна Тимофеевича тоже нетранзитивны.