Задача 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). Сначала каждый школьник подаётся в свой самый «любимый» университет, и университеты принимают абитуриентов в соответствии со своими предпочтениями до тех пор, пока есть места; 2). Далее, если остались не зачисленные школьники, то они подаются в свой следующий по предпочтениям университет (на втором шаге – во второй, на третьем – в третий), и они зачисляются в соответствии с пред- почтениями университетов, если в университете остались места; 3). Механизм останавливается, если все школьники распределены по университетам. Покажите, что Борис может предоставить в ЦПК «ложные» предпочтения, и быть зачисленным в университет, который нравится ему больше (по сравнению со случаем, когда отправляются правдивые предпочтения). Опишите в общих чертах, как каждый студент может манипулировать своими предпочтениями, чтобы быть распределённым в университет, который нравится ему больше (по сравнению с правдивым представлением предпочтений).