Свойство 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 взяли какого-то друг…

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

Доказывать будем по индукции.

База. В р нет проблемной пары шага 1.

И опять же от противного. Пусть есть. Обозначим эту пару за (i₁, s₁). Заметим, что так как i₁ был отвергнут школой s₁ на первом шаге работы алгоритма GSM, то школа s₁ заполнена отображением м₁. Значит, есть студент i₂, который попал в s₁ по результатам м₁, но не попал в s₁ по результатам р. Так как р Парето-доминирует м₁, значит, i₂ попал в более предпочтительную для себя школу s₂ по итогам р. Так как для i₂ школа s₂ более предпочтительна, чем s₁, значит, на первом шаге GSM он был отвергнут этой школой. Значит, она заполнена при м₁. Продолжаем аналогичное рассуждение, пока не образуется цикл — найдется студент i_m, который попал в школу s₁ по результатам р, которая для него более предпочтительна, чем s_m-1.

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

Тогда рассмотрим подробнее работу первого шага механизма GSM. Возьмем из студентов цикла того, кто был последним (или одним из нескольких последних — если они поступали в свои школы на одном этапе) принят школой из цикла (в которой он оказался в конце по итогам м₁). Обозначим его i. Студент из цикла, который предпочитал эту школу, уже был отвергнут этой школой (так как иначе, ему бы еще только предстояло поступать в свою конечную школу, что противоречит предположению о том, что рассматриваемый студент i был последним, поступающим в свою школу). Значит, данная школа заполнена на момент поступления рассматриваемого студента i. Но тогда, чтобы принять студента i, она должно отвергнуть какого-то другого студента j, что делает его смутьяном. Причем смутьян j был выгнан из школы позже, чем смутьян i₁ (который, как студент из цикла, уже поступил (или поступает на данном этапе) в свою конечную школу). Противоречие.

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

Переход. Пусть в р нет проблемных пар первых t шагов. Тогда в р нет проблемной пары шага t+1.

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

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

Так как р Парето-доминирует м, то есть студент i₁, для которого отображение р предлагает лучшую школу s₁, чем школа, куда его отправило м. Тогда он подавал заявку в м на последнем шаге механизма GSM (так как i₁ распределен в s₁ по итогам р и в р нет проблемных пар, то s₁ не была вычеркнута из списка предпочтений i₁) и был отвергнут, значит, школа s₁ заполнена при м, значит, есть студент i₂, поступивший в s₁ по итогам м и попавший в какую-то другую школу s₂ по итогам р, которая должна быть для него лучше, чем s₁ и т. д. Опять получаем цикл студентов. И так как никто из них не является смутьяном для школы, в которую он больше хочет попасть (школу из р), то он должен подавать в нее заявку при м. Тогда опять рассмотрим последнего принятого механизмом GSM студента i; так как в эту школу уже поступал студент из цикла, то она должна быть заполнена, значит, поступая, студент i «выгоняет» какого-то студента j, который становится смутьяном, что противоречит тому, что это последний шаг работы алгоритма.

Таким образом, противоречие, и мы доказали, что GSM — Парето-эффективен.