Механизмы распределения учеников по школам

Размещено на http://www.allbest.ru/

Оглавление

• Введение
• 1. Дизайн механизмов
• 1.1 Основные понятия и определения (теория игр)
• 1.2 Основные понятия и определения (теория дизайна механизмов)
• 1.3 Применение дизайна механизмов в различных задачах
• 1.4 Применение дизайна механизмов в задачах распределения
• 1.4.1 Распределение студентов по курсам
• 1.4.1.1 The HBS Draft Mechanism
• 1.4.1.2 The U of M Auction Mechanism
• 1.4.1.3 The CU Auction Mechanism
• 1.4.2 Распределение студентов по школам
• 1.4.2.1.GS Mechanism
• 1.4.2.2 TTC Mechanism
• 1.4.2.3 Boston Mechanism
• 1.4.2.4 Serial Dictatorship Mechanism
• 2. Эффективный механизм распределения студентов по школам
• 2.1 Создание механизма
• 2.2 Свойства механизма
• Заключение
• Список литературы

• Введение
• Теория дизайна механизмов в экономике ассоциируется с понятием планировщика, создающего механизм, работа которого позволяет эффективно решить различного рода задачи, в которых практически важно достижение определенного результата.
• Несмотря на свою сложность, в последние годы появилось множество экономических применений дизайна механизмов в самых различных областях: задачах о пробках (congestion games) (Fujishima, 2011; Sandholm, 2005), задачах об аукционах (Noam Nisan, 2014), задачах о распределении (Pathak, 2011; Kominers, Ruberry, Ullman, 2010; Budish, Che, Kojima, Milgrom, 2012) и т. д.
• Как можно видеть, применение дизайна механизмов широко распространено (в иностранной литературе). Две часто встречающиеся проблемы - проблема распределения студентов университетов (колледжей) по курсам (предметам) (Budish, Cantillon, 2012; Ghosh, 2013) и проблема распределения учеников по школам (Abdulkadiroрlu et al, 2009; Pathak, 2011). Количество мест в школах и на различных курсах в университетах ограничено, что может привести к неэффективному распределению студентов. Данная проблема может стать серьезным препятствием для студентов, которым необходимо пройти определенные курсы для выпуска из университета (колледжа). Таким образом, администрация несет особую ответственность за механизм распределения студентов.
• В данной выпускной квалификационной работе применение дизайна механизмов будет направлено на создание механизма, который бы эффективно распределял учеников по школам. Будут рассмотрены недостатки существующих механизмов и построен новый механизм, создающий Парето-оптимальные распределения.
• Целью исследования является выявление слабых сторон существующих механизмов, способов их устранения. Задачи исследования - изучение возможностей применения дизайна механизмов, создание механизма, который бы лучше соответствовал предпочтениям учеников относительно школ, чем существующие механизмы.
• Объектом исследования являются механизмы распределения учеников по школам. Предметом исследования является эффективность данных механизмов.
• В первом разделе рассматриваются основные понятия и определения из области дизайна механизмов и теории игр, описываются существующие механизмы, приводятся примеры, помогающие читателю войти в курс проблемы. Во втором разделе строится механизм эффективного распределения студентов по школам, выявляются его преимущества и недостатки.
• Результат данной работы может быть применен администрацией районов (городов) для эффективного распределения учеников по школам.


1. Дизайн механизмов

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

1.1 Основные понятия и определения (теория игр)

Начнем с определения игры.

Игра - это тройка {I, {S_i}_i?I, {u_i}_i?I}, где:

1) I = {1, …, N} - множество игроков;

2) S_i - множество доступных игроку i действий (стратегий) s_i; S = {S_i}_i?I;

3) {u_i}_i?I - множество функций выплат u_i: S > R.

Вектор, состоящий из стратегий игроков, {s₁, …, s_n} будем называть профилем стратегий.

За s_-i примем профиль стратегий всех игроков, не считая игрока i (s_-i = {s₁, …, s_i-1, s_i+1, …, s_n}). S_-i - множество всех возможных s_-i.

Обозначим O за множество исходов игры.

Стратегия s ? S_i агента i называется доминируемой, если существует такая стратегия s' ? S_i, что ? s_-i ? S_-i:

u_i(s', s_-i) ? u_i(s, s_-i).

Также говорят, s' доминирует над s.

Стратегия s ? S_i агента i называется доминантной, если любая другая стратегия s' ? S_i ею доминируется, то есть ? s' ? S_i и ? s_-i ? S_-i:

u_i(s, s_-i) ? u_i(s', s_-i).

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

Равновесие в доминантных стратегиях для игры {I, {S_i}_i?I, {u_i}_i?I} - это профиль стратегий s^* = {s₁^*, …, s_n^*} ? S, такой что для любого агента i ? I стратегия s_i^* является доминантной.

Равновесие в доминантных стратегиях - это самое устойчивое равновесие, но существует оно далеко не всегда. Существуют и другие равновесия.

Равновесие Нэша в чистых стратегиях для игры {I, {S_i}_i?I, {u_i}_i?I} - это профиль стратегий s^* = {s₁^*, …, s_n^*} ? S, такой что для любого агента i ? I выполняется следующее условие:

? s_i ? S_i: u_i(s_i^*, s_-i^*) ? u_i (s_i, s_-i^*)

То есть никакому игроку не выгодно отклоняться от выбранной стратегии, если и другие не отклоняются.

Смешанная стратегия для игрока i в игре {I, {S_i}_i?I, {u_i}_i?I} - это распределение вероятностей у_i ? У_i, где У_i - множество распределений вероятностей над S_i.

Равновесия Нэша в чистых стратегиях может не быть, но оно всегда существует в конечном случае в смешанных стратегиях (Kakutani, 2004).

Дополним модель игры.

Игра с неполной информацией - это четверка {I, {S_i}_i?I, {И_i}_i?I, {u_i}_i?I}, где:

1) I = {1, …, N} - множество игроков;

2) S_i - множество доступных игроку i действий (стратегий) s;

3) И_i - множество типов игрока i. Обозначим И = И₁ x … x И_N. Каждому игроку известен его собственный тип и_i и общее распределение p(И), из которого берутся типы всех остальных (p(и_-i | и_i) = p(и) / p(и_i)), где и = {и₁, …, и_N}.

4) {u_i}_i?I - множество функций выплат u_i: S x И > R (функции выплат теперь зависят не только от стратегий, но и от типов).

1.2 Основные понятия и определения (теория дизайна механизмов)

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

Функция социального выбора f: И₁ x … x И_N > O - это функция, выбирающая тот или иной желаемый исход f(и) при данных типах и = (и₁, …, и_N).

То есть это то, что нам бы хотелось получить от механизма, который мы создаем.

Теперь, наконец, определим, что такое механизм.

Механизм M = (S₁, …, S_N, g) состоит из наборов стратегий агентов S_i и функции исхода g: S₁ x … x S_N > O, которая определяет исход, предусмотренный механизмом для данного профиля стратегий.

Для простоты работа механизма представлена на рис.1.

Рис.1 - принцип работы механизмов.

Механизм M = (S₁, …, S_N, g) реализует функцию социального выбора f(и), если для всех и = (и₁, …, и_N) ? И₁ x … x И_N:

g(s₁^*(и₁), …, s_N^*(и_N)) = f(и),

где профиль стратегий (s₁^*, …, s_N^*) находится в равновесии в игре, порожденной M.

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

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

Введем еще несколько определений.

Функция социального выбора f(и) называется оптимальной по Парето, если для любого набора типов и = (и₁, …, и_N) и любого исхода O ' ? f(и):

u_i (O ', и_i ) > u_i (f(и), и_i ) ? ? j: u_j (O ', и_j ) < u_j (f(и), и_j ).

То есть, не существует исхода, в котором бы всем агентам было не хуже (а кому-то лучше), чем в исходе, предлагаемом функцией социального выбора.

Механизм называется оптимальным по Парето, если он реализует оптимальную по Парето функцию социального выбора.

На самом деле дизайн механизмов можно рассматривать в трех разных временных постановках:

1) Ex ante - до появления типов агентов. Агенты знают только распределения и обладают одинаковой информацией.

2) Interim - после появления типов, для каждого агента. Ситуация рассматривается с точки зрения одного агента, знающего свой тип и распределения типов других агентов.

3) Ex post - после того, как типы всех агентов стали известны.

Прямой механизм M = (и₁, …, и_N, g) реализует функцию социального выбора f(и), если для всех и = (и₁, …, и_N) ? И₁ x … x И_N:

g(и₁, …, и_N) = f(и),

где профиль стратегий (и₁, …, и_N) находится в равновесии в игре, порожденной M.

Такой механизм будет называться правдивым.

Функция социального выбора правдиво реализуема, если профиль стратегий (s₁^*, …, s_N^*), где s_i^*(и_i) = и_i, находится в равновесии в игре, порожденной механизмом M = (и₁, …, и_N, f).

1.3 Применение дизайна механизмов в различных задачах

Как уже отмечалось во введении, дизайн механизмов применяется в самых различных областях. Данная секция предназначена для ознакомления читателя с тем, какие вообще бывают механизмы, какие задачи они позволяют решать. В качестве примера будет рассмотрено применение дизайна механизмов для задачи о пробках (congestion games).

Впервые задачи о пробках стал изучать Rosenthal (1973). Он рассматривал задачи следующего вида: имеется n игроков и t факторов. У каждого игрока есть набор стратегий, который соответствует выбору подмножества факторов. Затраты игрока от стратегии рассчитываются как сумма затрат от использования выбранных факторов, которые в свою очередь зависят от количества людей, использующих данный фактор (чем больше людей его использует, тем больше затраты).

В статье Fujishima (2011) планировщик, хотел бы создать такие платежные схемы (price schemes), при которых экономика бы сходилась к общественному оптимуму из любого начального состояния. При этом у планировщика есть доступ к функциям спроса, но не к функциям затрат агентов. В этой статье рассматриваются как случай с одинаковыми функциями затрат агентов, так и с разными. В первом случае планировщик может привлечь игроков к оптимуму используя свойства потенциальных игр. Во втором, планировщик не может создать потенциальную игру, и исследователь изучает динамику в терминах стратегий наилучшего отклика.

Модель задается следующим образом.

Есть одно благо, которое каждый агент может или потреблять, или не потреблять. Потребление блага увеличивает затраты, которые зависят от среднего уровня потребления блага. Затраты могут различаться, но количество возможных функций затрат ограничено. За R обозначается множество индексов возможных функций затрат. Агенты делятся на группы по типу функции затрат (у двух агентов из одной группы - одинаковые функции затрат). За m_r (r ? R) принимаются доли групп относительно общего числа людей. То есть, ?m_r = 1.

z_r ? [0; m_r] - доля людей в группе r, потребляющих благо.

Z = {z ? R^|R| || ? r ? R, z_r ? m_r} - множество состояний населения.

x = ?z_r ? [0; 1] - общая доля людей, потребляющих благо.

Если агент i, принадлежащий группе r ? R, потребляет благо, то его выигрыш составляет v_i - и_r •T(x), где v_i - индивидуальная выгода от потребления блага; T - издержки (строго возрастающая, выпуклая функция); и_r - параметр, соответствующий группе r. Если агент не потребляет благо, то его выигрыш составляет 0.

За D_r : R > [0; m_r] обозначается функция совокупного спроса на благо группы r. (•) - обратная функция спроса. (y) отображает наивысшую готовность y платить за благо в группе r.

В каждой группе предельным агентом называют агента, который получает наименьший выигрыш из всех, кто потребляет благо в этой группе. Его выигрыш F_r(z) = (z_r) - и_r •T(x).

Также предполагается, что для каждой группы r и_r лежит в закрытом интервале [; ].

Как уже говорилось, в модели предполагается, что планировщик знает T и {D_r}_{r ? R}, но не знает {и_r}_{r ? R}.

Игра задается как G = (F, и), где F = {F_r}_{r ? R}.

Состояние населения z ? Z - равновесие по Нэшу, если ? r ? R:

,

Fujishima предлагает в качестве блага рассматривать вождение (индивиды выбирают ездить или нет, x - общее количество трафика на дорогах, T(x) - время в пути) или пользование Интернетом (индивиды выбирают подключать Интернет или нет, T(x) - время соединения, если общий объем подключившихся x).

Далее автор изучает динамику и вводит ценовую схему P(x) - налог, установленный на людей, потребляющих благо. Планировщик хочет достичь социальный оптимум. Вводится функция общественного благосостояния:

,

Таким образом, планировщик хочет применить функцию социального выбора f ^* И > Z:

,

Fujishima решает эту задачу для различных видов динамики.

Sandholm (2005) наоборот рассматривал случай, где планировщик знает функции затрат агентов, но не знает функции спроса.

В действительности же, планировщику обычно неизвестны ни функция спроса, ни функция затрат. Han et al (2010) пытались разобраться с этой проблемой. Они свели задачу о пробках к вариационным неравенствам и решали ее с помощью созданного ими итерационного алгоритма. Но, во-первых, в их модели у планировщика есть оценка функций затрат в каждом периоде и предполагается, что она сходится к действительной функции затрат. Во-вторых, в их модели транспортное движение находится в равновесии в каждом периоде (это предположение для вариационных неравенств), но в действительности агентам требуется время, чтобы прийти к равновесию.

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

Также существует довольно много статей, посвященных другим вопросам. Например, Fujishima (2011) рассматривает эволюционное внедрение (evolutionary implementation) оптимального числа и размера городов, где планировщик приводит экономику к оптимуму в долгосрочном периоде без “комовой” (lumpy) миграции и не зная предпочтений.

1.4 Применение дизайна механизмов в задачах распределения

Среди задач, решаемых с использованием дизайна механизмов, можно выделить, так называемые, задачи распределения.

В целом, задачи распределения можно описать следующим образом.

Есть множество агентов {1, …, N}, а также множество объектов распределения {1, …, M}, которые надлежит распределить. У агентов есть предпочтения относительно предметов, но и у объектов распределения могут быть предпочтения относительно агентов. У каждого объекта распределения m есть свой объем q_m, который отвечает за количество агентов, которым может достаться данный объект распределения. Задача планировщика состоит в том, чтобы эффективно распределить объекты распределения агентам в связи с их заявленными предпочтениями, не превышая объемы объектов распределения.

В данной секции будут рассмотрены примеры использования механизмов в задачах распределения. Две распространённые проблемы данного типа - распределение студентов университетов и колледжей по курсам (предметам) и распределение учеников по школам. По сути, задача распределения учеников по школам является частным случаем задачи распределения студентов по курсам университета. Данные задачи эквиваленты, если предположить, что студенты должны быть распределены ровно на 1 курс.

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

1.4.1 Распределение студентов по курсам

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

В этой подсекции будут рассмотрены три механизма, используемые для распределения студентов (источник - Ghosh, 2013). Первый (Draft Mechanism) используется в Гарвардской Бизнес Школе (часть Гарвардского университета, Бостон). Два других основаны на аукционах и используются в Мичиганском университете (Энн-Арбор) и Колумбийском университете (Нью-Йорк). Также будут приведены примеры.

1.4.1.1 The HBS Draft Mechanism

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

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

Для понимания приведем пример работы этого механизма.

Предположим, есть пять студентов: 1, 2, 3, 4, 5; и 6 курсов: Экономика (E), Статистика (S), Менеджмент (M), Коммерческое право (B), Бухгалтерский учет (A) и Финансы (F).

На каждом курсе 4 места, списки предпочтений студентов выглядят следующим образом:

1: E, S, M, B, A, F

2: M, F, A, B, S, E

3: M, E, B, S, F, A

4: A, E, B, F, M, S

5: F, A, B, S, E, M

(например, студент 1 предпочитает курс E курсу S и т.д.)

Для простоты предположим, что расписание курсов не пересекается.

В примере будет 4 раунда, и каждый студент будет распределен на 4 курса. 1 и 3 раунд будут проходить в порядке возрастания номеров студентов, а 2 и 4 в порядке убывания.

Таким образом, запишем результаты раундов.

Раунд 1: 1E, 2M, 3M, 4A, 5F

Раунд 2: 5A, 4E, 3E, 2F, 1S

Раунд 3: 1M, 2A, 3B, 4B, 5B

Раунд 4: 5S, 4F, 3S, 2B, 1A

Заметим, что в раунде 4 после того, как студент 2 был записан на курс B, курс B оказался заполнен, таким образом, студент 1, следующим предпочтением которого также был курс B, был записан на следующий курс в его списке предпочтений - курс А.

Таким образом, итоговое распределение по курсам: 1(E, S, M, A), 2(M, F, A, B), 3(M, E, B, S), 4(A, E, B, F), 5(F, A, B, S).

Данный механизм обладает интересными свойствами. Как отмечают Budish и Cantillon (2012), он справедлив в терминах ex-ante, и эффективен. C другой стороны этот механизм не правдив. Он стимулирует студентов к изменению своих списков предпочтений таким образом, чтобы наиболее популярные классы оказывались в начале списка, а наименее популярные - в конце.

1.4.1.2 The U of M Auction Mechanism

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

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

Опять же для наглядности приведем пример.

Пусть есть 5 студентов и 4 курса. Студенты могут попасть максимум на 2 курса, на каждом курсе 3 места, а стартовые капиталы студентов 1000.

Ставки студентов представлены в таблице.

Табл.1 - ставки студентов (U of M)

	Курс 1	Курс 2	Курс 3	Курс 4
Студент 1	600	375	25	0
Студент 2	475	300	225	0
Студент 3	450	275	175	100
Студент 4	200	325	350	125
Студент 5	400	250	170	180

Ставки рассматриваются от наибольшей к наименьшей:

600 - студент 1 зачисляется на курс 1;

475 - студент 2 зачисляется на курс 1;

450 - студент 3 зачисляется на курс 1; курс 1 заполнен;

400 - студент 5 не зачисляется на курс 1, так как курс заполнен;

375 - студент 1 зачисляется на курс 2; расписание студента 1 заполнено;

350 - студент 4 зачисляется на курс 3;

325 - студент 4 зачисляется на курс 2; расписание студента 4 заполнено;

300 - студент 2 зачисляется на курс 2; расписание студента 2 заполнено; курс 2 заполнен;

275 - студент 3 не зачисляется на курс 2, так как курс заполнен;

250 - студент 5 не зачисляется на курс 2, так как курс заполнен;

225 - студент 2 не зачисляется на курс 3, так как его расписание заполнено;

200 - студент 4 не зачисляется на курс 1, так как его расписание заполнено;

180 - студент 5 зачисляется на курс 4;

175 - студент 3 зачисляется на курс 3; расписание студента 3 заполнено;

170 - студент 5 зачисляется на курс 3; расписание студента 5 заполнено;

Таким образом, расписание всех студентов заполнено.

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

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

1.4.1.3 The CU Auction Mechanism

Аукционный механизм, применяемый в Колумбийском университете довольно похож на механизм Мичиганского университета. Главное различие - он проводится в несколько раундов. Стартовый капитал дается студентам на основе их статуса (например, на основе накопленных кредитов). Стартовый капитал присваивается с самого начала и не сгорает. Ставки можно изменять до конца раунда. В конце раунда ставки обрабатываются. После первого раунда студенты могут узнать оставшееся количество мест на курсах. Далее, студенты могут отказаться от не желаемых курсов и получить очки обратно. Записаться на курсы, на которых еще есть места, можно “бесплатно”. Также можно обмениваться курсами с другими студентами. Если какой-то курс заполнен, то организуется лист ожидания, отсортированный по ставкам. Все очередности между одинаковыми ставками разрешаются лотереями. В начале обучения, студенты получают 1000 очков, и для стимулирования студентов брать необязательные курсы, даются бонусы.

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

Рассмотрим ту же ситуацию, что и в предыдущей подсекции.

Теперь в каждый семестр проводится 3 раунда ставок. Студент может ставить только на ограниченное количество курсов, предположим, что студент может ставить только на 2 курса. Также предположим, что студент 5, опираясь на результаты равновесных цен в предыдущие года решил ставить больше на курсы 1 и 2, зная, что они популярные (допустим, он поставил 425 на курс 1 и 350 на курс 2). Все ставки приведены в таблице 2.

Табл. 2 - ставки студентов (CU)

	Курс 1	Курс 2	Курс 3	Курс 4
Студент 1	600	375	-	-
Студент 2	475	300	-	-
Студент 3	450	275	-	-
Студент 4	-	325	350	-
Студент 5	425	350	-	-

Таким образом, студент 1 получит курсы 1 и 2; студент 2 - курс 1; студент 3 - курс 1; студент 4 - курсы 2 и 3; студент 5 - курс 2. Непрошедшие ставки будут возвращены. Равновесная цена для курса 1 будет 450, для курса 2 - 325 и для курса 3 - 350.

После первого раунда и до начала, следующего, у студентов будет возможность пересмотреть свои курсы и отказаться от тех, за которые заплатили слишком много. Таким образом, студент 5 может пересмотреть свою ставку 325 за курс 2, а студент 3 наверняка не захочет платить 350 за курс 3, так как он единственный, кто делал ставку на этот курс.

Курс 1 и 2 заполнены, если только никто не захочет вернуть свою ставку. Таким образом, курсы 3 и 4 будут единственными представленными на аукцион в раунде 2. Предположим, что студент 4 заберет свою ставку на курс 3. Тогда студентам 2, 3, 4 и 5 останется получить 1 курс. Каждому будет разрешено сделать одну ставку или они могут подождать конца раунда, чтобы попасть на курс “забесплатно”, так как наверняка будут пустые места хотя бы на одном из двух курсов.

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

Интересно бы, конечно, было посмотреть на реальные данные аукционов распределения студентов по курсам, проведенных в университетах и оценить их успешность. На практике же получить такие данные будет довольно сложно.

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

1.4.2 Распределение студентов по школам

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

Обычно задача распределения студентов по школам имеет следующие исходные данные.

1. Множество студентов I = {1, …, K} и их предпочтения относительно школ P = (P₁, …, P_K).

2. Множество школ S = {1, …, N} и количество мест в них {q₁, …, q_N}.

3. Список приоритетов студентов для каждой из школ {, …, }.

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

Во многих городах США данная задача рассматривается как односторонняя, то есть у школ нет предпочтений относительно студентов. Обычно приоритеты задаются как экзогенный критерий (например, расстояние до школы). Например, в Бостоне поступающие в школу получают первый приоритет, если проживают на расстоянии не больше одной мили от школы (walk-zone priority) и имеют братьев или сестер в школе; второй - если только имеют родственников в школе; третий - если только близко проживают; четвертый приоритет получают все остальные. Приоритетность студентов, находящихся в одной группе определяется лотереей.

В Чикаго данная задача рассматривается как двусторонняя, а предпочтения школ относительно студентов формируется на основе результатов вступительного теста.

Решением задачи распределения студентов по школам является отображение м: I > S, где м(i) - школа, в которую был распределен студент i. Отображение м может обладать несколькими важными свойствами, которые мы сейчас рассмотрим.

Отображение м - Парето-эффективно, если не существует другого распределения студентов, такого что все студенты слабо предпочитают результат нового распределения старому, и хотя бы 1 студент строго.

Отображение м - стабильно, если не существует такой пары студент-школа (i, s), что:

1) Студент i предпочитает школу s школе, куда его распределили м (i).

2) Существует другой студент j, которого распределили в s и имеющего меньший приоритет по отношению к s.

Такая пара называется блокирующей парой. Иногда данное свойство называют не стабильностью, а свойством устранения обоснованной зависти (elimination of justified envy). Рассматривая одностороннюю проблему, стабильность олицетворяет понятие справедливости - студент не должен быть назначен в худшую школу, если лучшая школа взяла менее предпочтительного для нее студента.

Отображение м - оптимально для студентов, если не существует другого стабильного отображения, которое не хуже для всех студентов и для кого-то лучше.

Механизмом ц в данной задаче называется процедура построения отображения для решения задачи распределения студентов по школам.

Механизм ц - правдив, если говорить правду доминантная стратегия для всех студентов.

Теперь перейдем к рассмотрению существующих механизмов (источник - Pathak, 2011).

1.4.2.1 GS Mechanism

Первый механизм основан на алгоритме, предложенном Gale и Shapley (1962). Будем называть его GS. Он работает следующим образом.

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

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

Алгоритм заканчивается, когда больше нет заявок.

Gale и Shapley показывают, что механизм, основанный на этом алгоритме выдает оптимальное для студентов отображение. Dubins и Freedman (1981), а также Roth (1982) доказывают, что данный механизм правдив. Тем не менее отображения, полученные при данном механизме могут быть не Парето-эффективными.

Рассмотрим пример.

Пусть есть три студента i₁, i₂, i₃ и три школы s₁, s₂, s₃. В каждой школе по одному месту. Предпочтения студентов и школ:

P:

i₁: s₂ s₁ s₃

i₂: s₁ s₂ s₃

i₃: s₁ s₂ s₃

:

s₁: i₁ i₃ i₂

s₂: i₂ i₁ i₃

s₃: i₃ i₁ i₂

Механизм выдаст следующее отображение:

µ_GS =

Заметим, что ни один студент не был распределен в школу первого приоритета. Данное отображение не является Парето-эффективным, но является стабильным.

1.4.2.2 TTC Mechanism

Другой механизм, предложен Abdulkadiroрlu и Sцnmez (2003) и основан на top trading cycles (TTC). Работает данный механизм, который мы будем называть TTC, следующим образом.

Шаг 1. Каждый студент выбирает наилучшую для себя школу. Каждая школа выбирает студента с наивысшим для нее приоритетом. Есть как минимум один цикл. Каждый студент может быть частью только одного цикла. Каждого студента в цикле распределяем в школу, которая его выбрала, и убираем из общего списка студентов. Количество мест в школе уменьшаем на 1, и если оно достигает 0, убираем школу из общего списка школ.

Шаг t. Каждый оставшийся студент выбирает наилучшую для себя школу из оставшихся, и каждая оставшаяся школа выбирает студента с наивысшим для себя приоритетом. Есть как минимум один цикл. Каждый студент может быть частью только одного цикла. Каждого студента в цикле распределяем в школу, которая его выбрала, и убираем из общего списка студентов. Количество мест в школе уменьшаем на 1, и если оно достигает 0, убираем школу из общего списка школ.

Алгоритм заканчивается, когда все студенты распределены.

Данный механизм правдив (Abdulkadiroрlu, Sцnmez, 2003; Roth, Postlewaite, 1977). Также он выдает Парето-эффективное отображение, но не обязательно стабильное.

В качестве примера рассмотрим те же входные данные.

Пусть есть три студента i₁, i₂, i₃ и три школы s₁, s₂, s₃. В каждой школе по одному месту. Предпочтения студентов и школ:

P:

i₁: s₂ s₁ s₃

i₂: s₁ s₂ s₃

i₃: s₁ s₂ s₃

:

s₁: i₁ i₃ i₂

s₂: i₂ i₁ i₃

s₃: i₃ i₁ i₂

TTC механизм выдаст следующее отображение:

µ_TTS =

Данное отображение является Парето-эффективным, и студенты i₁ и i₂ попали в школу первого приоритета. Оно не является стабильным, так как студент i₃ и школа s1 образуют блокирующую пару.

1.4.2.3 Boston Mechanism

Третий рассматриваемый механизм - Бостонский механизм. Работает следующим образом.

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

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

Алгоритм заканчивается, когда больше нет заявок.

В отличие от двух предыдущих механизмов данный не является правдивым.

Опять же рассматриваем те же входные данные.

Пусть есть три студента i₁, i₂, i₃ и три школы s₁, s₂, s₃. В каждой школе по одному месту. Предпочтения студентов и школ:

P:

i₁: s₂ s₁ s₃

i₂: s₁ s₂ s₃

i₃: s₁ s₂ s₃

:

s₁: i₁ i₃ i₂

s₂: i₂ i₁ i₃

s₃: i₃ i₁ i₂

µ_BOSTON =

Данное отображение является Парето-эффективным. Студент i₂ и школа s₂ образуют блокирующую пару, таким образом, оно не стабильно.

Кроме того, если бы студент i₂ заявил школу s₂ своим первым приоритетом, то он бы попал в нее. Это демонстрирует, что механизм не является правдивым.

1.4.2.4 Serial Dictatorship Mechanism

Последний рассматриваемый в данной секции механизм называется механизмом серийной диктатуры (serial dictatorship mechanism). Будем называет его сокращенно SD.

Данный механизм ставит всех студентов в очередь. Очередной студент выбирает наилучшую для себя школу из всех еще доступных. Если очередь составляется произвольно, то механизм называют random serial dictatorship mechanism.

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



2. Эффективный механизм распределения студентов по школам

Данный раздел посвящен созданному автором механизму распределения студентов по школам и его анализу.

Как можно было заметить в разделе 1.4, все существующие механизмы не обладают всеми желаемыми свойствами сразу. Механизм GS - оптимален для студентов, стабилен и правдив, но не Парето-эффективен. Механизм TTC - Парето-эффективен, правдив, но не стабилен. Механизм BOS - Парето-эффективен, но не стабилен и не правдив.

Хотелось бы создать механизм, который был бы Парето-эффективен, стабилен и правдив. К сожалению, доказано, что такого механизма не существует (Hamada et al., 2011).

Наиболее популярный из этих механизмов GS может приводить к большим потерям общественного благосостояния, так как он не Парето-эффективен. Abdulkadiroрlu, Pathak и Roth (2009) показывают, что данный механизм неэффективен и на практике.

В данной работе будет приведен механизм, который является улучшением механизма GS. Он Парето-эффективен, но его эффективность достигается в ущерб стабильности и правдивости.

2.1 Создание механизма

Приведем пример работы механизма GS, на котором будет видна причина его неэффективности.

Пусть есть 5 студентов и 5 школ, в каждой по 1 месту. Предпочтения студентов задаются следующим образом:

i₁: s₁ s₄

i₂: s₂ s₁

i₃: s₃ s₂

i₄: s₄ s₅

i₅: s₄ s₃

Предпочтения школ задаются следующим образом:

s₁: i₂ i₁

s₂: i₃ i₂

s₃: i₅ i₃

s₄: i₁ i₄ i₅

s₅: …

Поэтапная работа механизма GS.

Табл.3 - пример неэффективности механизма GS

	Школа 1	Школа 2	Школа 3	Школа 4	Школа 5
Этап 1	i1	i2	i3	i4, i5
Этап 2			i3, i5
Этап 3		i2, i3
Этап 4	i1, i2
Этап 5				i1, i4
Этап 6					i4
Итог GS	i2	i3	i5	i1	i4
Лучше	i1	i2	i3	i5	i4

Но очевидно, что лучше было бы распределить студентов, как показано в графе “Лучше”. Этот исход Парето-доминирует исход GS, так как в предложенном варианте все студенты распределяются в школу первого приоритета, кроме студента 4, который в обоих случаях распределяется в школу второго приоритета.

Заметим, что если бы студент 4 не указал в своем списке предпочтений школу 4, то результатом работы механизма, как раз бы и стал вариант “Лучше”, который, очевидно, является Парето-эффективным.

Введем определение.

Применительно к результату работы алгоритма GS, пусть агент i на шаге t₁ временно поступил в школу s, а на шаге t₂ был отвергнут этой школой. Если существует хотя бы один студент, который был отвергнут это школой на шаге t ? [t₁; t₂ -1], то студента i будем называть смутьяном, а пару (i, s) - проблемной.

Очень важным является то, что не рассматривая школу s в списке предпочтений агента-смутьяна, мы не делаем ему хуже, а другим агентам можем сделать лучше. Более того, рассматривая другие проблемные пары мы можем сделать и агенту-смутьяну.

Опишем, наконец, механизм. Он немного сложнее и основан на GS.

Шаг 0. Запускаем механизм GS.

Шаг t. Рассматриваем механизм, запущенный на предыдущем шаге. Если при его работе был обнаружен хотя бы один смутьян (проблемная пара), то берется последний смутьян и из его списка предпочтений удаляется школа, входящая в последнюю проблемную пару с этим смутьяном. После этого для обновленных списков предпочтений заново запускается механизм GS.

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

Будем называть данный механизм GSM.

Очевидно, что GSM не бесконечен, так как списки предпочтений студентов конечны.

Рассмотрим работу механизма на том же примере, на котором показывали неэффективность GS.

Пусть есть 5 студентов и 5 школ, в каждой по 1 месту. Предпочтения студентов задаются следующим образом:

i₁: s₁ s₄

i₂: s₂ s₁

i₃: s₃ s₂

i₄: s₄ s₅

i₅: s₄ s₃

Предпочтения школ задаются следующим образом:

s₁: i₂ i₁

s₂: i₃ i₂

s₃: i₅ i₃

s₄: i₁ i₄ i₅

s₅: …

Поэтапная работа механизма GSM:

Шаг 1.

Табл.4 - Шаг 1. GSM

	Школа 1	Школа 2	Школа 3	Школа 4	Школа 5
Этап 1	i1	i2	i3	i4, i5
Этап 2			i3, i5
Этап 3		i2, i3
Этап 4	i1, i2
Этап 5				i1, i4
Этап 6					i4
Итог	i2	i3	i5	i1	i4

Шаг 2.

На шаге 1 последним смутьяном является студент i₄. Проблемная пара - (i₄, s₄). Вычеркиваем ее из списка предпочтений студента i₄ и запускаем GS заново.



Табл.5 - Шаг 2. GSM

	Школа 1	Школа 2	Школа 3	Школа 4	Школа 5
Этап 1 / Итог	i1	i2	i3	i5	i4

Больше проблемных пар нет. Работа алгоритма завершена.

Получилась графа “Лучше” из исходного примера. Таким образом, на данном примере механизм GSM работает лучше. Но это ничего не доказывает. Перейдем к рассмотрению свойств данного механизма.

2.2 Свойства механизма

Cвойство 1. Механизм GSM - не стабилен.

Док-во.

Казалось бы, основанный на работе стабильного механизма GS, механизм GSM должен быть стабилен. Но это не так. Напрашивается доказательство от противного верное для механизма GS. Пусть есть студенты i, j и школа s, такие что студент i попал в менее предпочтительную для себя школу, чем s, студент j попал в школу s, а для школы s студент i для школы s предпочтительнее, чем j. Но тогда студент i должен был подавать заявку в школу s, которая выше в его списке предпочтений, чем та, в которой он оказался. Так как его в конечном счете отвергли, то был пул студентов, полностью заполняющих школу s и более предпочтительных, чем i. Но, следовательно, этот пул более предпочтителен для школы s и чем j. Таким образом, j не мог быть определен в s. Противоречие. Тем не менее, школа s могла быть вычеркнута из списка предпочтений студента i в ходе работы механизма GS, и студент j все-таки мог попасть в эту школу. Таким образом, блокирующими парами могут быть только проблемные пары. В примере который мы уже рассматривали (пример 8), блокирующей парой является (i₄, s₄), а студент, который был назначен в s₄ (i₅) менее приоритетный для школы s₄, чем i₅.

Свойство 2. Механизм GSM - Парето-эффективен. Также отображение, полученное на шаге t+1, слабо предпочитается всеми студентами отображению, полученному на шаге t.

Док-во.

Доказательство начнем со второй части. Докажем, что для любого студента отображение, полученное на шаге t+1, как минимум не хуже, чем отображение, полученное на шаге t.

Доказываем от противного. Пусть нашелся студент i₁, для которого школа, в которую его распределили на шаге t+1 хуже, чем школа s₁, в которую его распределили на шаге t. Это значит, что на шаге t+1, он подавал заявку в школу s₁, но его в итоге не приняли (так как школа s₁ выше в его списке предпочтений, чем та, в которую его в и тоге определили, и s₁ не могла быть вычеркнута, так как на прошлом шаге t она еще была в списке предпочтений и раз студента i₁ в нее приняли, то (i₁, s₁) - не проблемная пара на шаге t). Тогда в школу s₁ на этом шаге взяли какого-то другого студента i₂. Если для него школа s₂, в которую его распределили на шаге t, более предпочтительна, чем школа s₁, то применяем аналогичное рассуждение. Таким образом, мы получаем цепочку студентов. Пусть мы остановились на студенте i_m, для которого школа, в которую он поступил на шаге t, s_m лучше, чем школа s_m-1, в которую он попал на шаге t+1.

Рассмотрим, два случая.

1) Студент i_m - не смутьян на шаге t. Тогда его список предпочтений на шаге t+1 такой же, как и на предыдущем шаге t. Значит он подавал заявку в школу s_m на шаге t+1, но в итоге был отклонен. Значит в школу s_m взяли какого-то другого студента (более предпочтительного для школы s_m) на шаге t+1, который был распределен в другую школу s_m+1 на шаге t, причем для него s_m более предпочтительна, чем s_m+1 (иначе мы бы добавили его в цепочку). Но тогда на шаге t он должен был подавать заявку в школу s_m (она выше в его списке предпочтений, чем s_m+1, в которую он был распределен), и в конечном счете его отклонили. Значит был пул более предпочтительных для s_m студентов. Но так как студент im+1 более предпочтителен для школы s_m, чем i_m, то и студента i_m должны были в конечном счете отклонить. Противоречие.

2) Студент i_m - смутьян на шаге t. Пусть проблемной парой была пара (i_m, s). Списки предпочтений студента отличаются только тем, что теперь s вычеркнута. Изменения в работе алгоритме по сравнению с предыдущим шагом начнутся, только когда дойдет до школы s в списке предпочтений студента i_m. Пусть следующая школа в его списке предпочтений s'. Заметим, что он также подавал в нее заявку на шаге t (так как в определённый момент был отвергнут школой s (по определению проблемной пары)). Школа s_m в его списке предпочтений стоит после s (от s' и далее). Таким образом, ничто не мешает нам провести аналогичное предыдущему случаю рассуждение.

Таким образом, мы доказали, что для любого студента отображение, полученное на шаге t+1, как минимум не хуже, чем отображение, полученное на шаге t. Это также доказывает, что исход механизма GSM слабо предпочитается всеми студентами исходу механизма GS (на каждом шаге мы для каждого из них не ухудшали распределение).

Теперь докажем Парето-эффективность итогового распределения.

Опять же от противного. Предположим, что отображение м, получившееся в результате работы механизма GSM не Парето-эффективно. Значит, есть отображение р, которого Парето-доминирует отображение м. Также пусть наш алгоритм проделал T шагов, отображение, полученное на шаге t, обозначим м_t. Таким образом, для любого t: р Парето-доминирует м_t.

...