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 =.

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