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

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

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

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

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

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

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

Приведем пример работы механизма 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.

Но очевидно, что лучше было бы распределить студентов, как показано в графе «Лучше». Этот исход Парето-доминирует исход 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.

Шаг 2.

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

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

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

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