Задача 4 Московской олимпиады школьников — 2016

Три школьника – Анна, Борис и Василий – хотят поступить в университеты – 1, 2, и 3. При этом, каждый школьник по-разному оценивает для себя эти три университета:
Полезность от приёма в университет для школьников:
$$\begin{array}{|c|c|c|c|}
\hline \\
& \text{Университет 1} & \text{Университет 2} & \text{Университет 3} \\
\hline \\
\text{Анна} & 30 & 40 & 20 \\
\hline \\
\text{Борис} & 40 & 30 & 20 \\
\hline \\
\text{Василий} & 40 & 30 & 20 \\
\hline
\end{array}$$
Университеты, в свою очередь, по-разному оценивают привлекательность абитуриентов:
Полезность от приёма в университет для университетов:
$$\begin{array}{|c|c|c|c|}
\hline \\
& \text{Университет 1} & \text{Университет 2} & \text{Университет 3} \\
\hline \\
\text{Анна} & 40 & 30 & 30 \\
\hline \\
\text{Борис} & 20 & 40 & 40 \\
\hline \\
\text{Василий} & 30 & 20 & 20 \\
\hline
\end{array}$$
Каждый университет может принять только одного школьника. Ни школьники, ни университеты не хотят остаться ни с чем (в этом случае их полезность нулевая).

Пусть школьники и университеты отправляют свои предпочтения, перечисленные выше, в Центральную Приёмную Комиссию. Найдите кого в итоге зачислят в какой университет, если ЦПК будет использовать механизм «алгоритм отложенного согласия» при распределении школьников по университетам:
1). Сначала каждый школьник выбирает свой самый «любимый университет», после чего каждый университет откладывает себе заявку самого предпочитаемого школьника, и отклоняет всех остальных.
2). На следующем шаге, школьники с отклонёнными заявками подаются в следующий по их предпочтениям университет (где данного школьника ещё не отклоняли). Университеты смотрят на свою отложенную заявку и новые заявки и снова выбирают одного самого предпочтительного школьника, «откладывая» его заявку и отклоняя все остальные.
3). Процедура заканчивается, когда все школьники распределены и новых заявок не подаётся.
Является ли полученное распределение устойчивым, т. е. найдётся ли такая пара школьника и университета, что и школьник, и университет получают полезность выше, чем в результате применения такого алгоритма? Существует ли такое распределение, что в нём хотя бы одному школьнику строго лучше, а всем остальным не хуже, чем в распределении, получившёмся в результате применения алгоритма отложенного согласия? Если да, то является ли оно устойчивым?
1. Пусть школьники и университеты отправляют свои предпочтения, перечисленные выше, в Центральную Приёмную Комиссию. Найдите кого в итоге зачислит каждый университет, если ЦПК будет использовать «бостонский механизм» распределения студентов:
   1). Сначала каждый школьник подаётся в свой самый «любимый» университет, и университеты принимают абитуриентов в соответствии со своими предпочтениями до тех пор, пока есть места;
   2). Далее, если остались не зачисленные школьники, то они подаются в свой следующий по предпочтениям университет (на втором шаге – во второй, на третьем – в третий), и они зачисляются в соответствии с пред- почтениями университетов, если в университете остались места;
   3). Механизм останавливается, если все школьники распределены по университетам.
   Покажите, что Борис может предоставить в ЦПК «ложные» предпочтения, и быть зачисленным в университет, который нравится ему больше (по сравнению со случаем, когда отправляются правдивые предпочтения). Опишите в общих чертах, как каждый студент может манипулировать своими предпочтениями, чтобы быть распределённым в университет, который нравится ему больше (по сравнению с правдивым представлением предпочтений).