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 образуют блокирующую пару.