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

Три школьника – Анна, Борис и Василий – хотят поступить в университеты – 1, 2, и 3. При этом, каждый школьник по-разному оценивает для себя эти три университета:

Полезность от приёма в университет для школьников:

Университеты, в свою очередь, по-разному оценивают привлекательность абитуриентов:

Полезность от приёма в университет для университетов:

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

Пусть школьники и университеты отправляют свои предпочтения, перечисленные выше, в Центральную Приёмную Комиссию. Найдите кого в итоге зачислят в какой университет, если ЦПК будет использовать механизм «алгоритм отложенного согласия» при распределении школьников по университетам:

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

2). На следующем шаге, школьники с отклонёнными заявками подаются в следующий по их предпочтениям университет (где данного школьника ещё не отклоняли). Университеты смотрят на свою отложенную заявку и новые заявки и снова выбирают одного самого предпочтительного школьника, «откладывая» его заявку и отклоняя все остальные.

3). Процедура заканчивается, когда все школьники распределены и новых заявок не подаётся.

Является ли полученное распределение устойчивым, т. е. найдётся ли такая пара школьника и университета, что и школьник, и университет получают полезность выше, чем в результате применения такого алгоритма? Существует ли такое распределение, что в нём хотя бы одному школьнику строго лучше, а всем остальным не хуже, чем в распределении, получившёмся в результате применения алгоритма отложенного согласия? Если да, то является ли оно устойчивым?

Пусть школьники и университеты отправляют свои предпочтения, перечисленные выше, в Центральную Приёмную Комиссию. Найдите кого в итоге зачислит каждый университет, если ЦПК будет использовать «бостонский механизм» распределения студентов:

1). Сначала каждый школьник подаётся в свой самый «любимый» университет, и университеты принимают абитуриентов в соответствии со своими предпочтениями до тех пор, пока есть места;

2). Далее, если остались не зачисленные школьники, то они подаются в свой следующий по предпочтениям университет (на втором шаге – во второй, на третьем – в третий), и они зачисляются в соответствии с пред- почтениями университетов, если в университете остались места;

3). Механизм останавливается, если все школьники распределены по университетам.

Покажите, что Борис может предоставить в ЦПК «ложные» предпочтения, и быть зачисленным в университет, который нравится ему больше (по сравнению со случаем, когда отправляются правдивые предпочтения). Опишите в общих чертах, как каждый студент может манипулировать своими предпочтениями, чтобы быть распределённым в университет, который нравится ему больше (по сравнению с правдивым представлением предпочтений).