Задача

В олимпиадах

Раздел

Баллы

30

Сложность

6
Средняя: 6 (1 оценка)
05.01.2017, 23:31 (Алёна Захарова)
26.03.2017, 12:35


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

Комментарии

Все задачи этой олимпиады

10-11 классы
ЗадачаБаллы
Задача 1 Московской олимпиады школьников — 201610
Задача 2 Московской олимпиады школьников — 201645
Задача 3 Московской олимпиады школьников — 201635
Задача 4 Московской олимпиады школьников — 201630
Задача 5 Московской олимпиады школьников — 201620
Задача 6 Московской олимпиады школьников — 201615
Новости на финансовом рынке35
Санаторий OLG45
5-7 классы
ЗадачаБаллы
Задача 1 Московской олимпиады школьников — 201615
Задача 2 Московской олимпиады школьников — 201620
Задача 3 Московской олимпиады школьников — 201615
Задача 4 Московской олимпиады школьников — 201615
Задача 5 Московской олимпиады школьников — 201620
8-9 классы
ЗадачаБаллы
Задача 1 Московской олимпиады школьников — 201615
Задача 2 Московской олимпиады школьников — 201615
Задача 3 Московской олимпиады школьников — 201630
Задача 4 Московской олимпиады школьников — 201630
Задача 5 Московской олимпиады школьников — 201620
Задача 6 Московской олимпиады школьников — 201615