Во многих странах абитуриенты распределяются по вузам и факультетам с помощью централизованных алгоритмов. Рассмотрим один из них.

Допустим, есть m абитуриентов и n факультетов. На факультете с номером i есть q_i мест, суммарное количество мест на всех факультетах не меньше m. Каждый абитуриент подает для обработки компьютерной программой информацию о том, какой факультет является для него первым по предпочтительности, вторым по предпочтительности, и т. д. до последнего. Затем программа на основе этой информации определяет, на какой факультет пойдет каждый абитуриент, с помощью следующей процедуры:

Шаг 1. Каждый абитуриент рассматривается как кандидат на наилучший для себя (согласно поданным предпочтениям) факультет. Если на факультете достаточно мест, чтобы принять всех таких кандидатов, то он принимает их всех. Если мест на факультете i недостаточно, то он принимает q_i абитуриентов из числа кандидатов согласно некоторым общеизвестным правилам, которые могут быть разными для разных факультетов. (Например, факультет может быть обязан принимать абитуриентов с наибольшим суммарным баллом ЕГЭ, при равенстве баллов обязан сравнивать абитуриентов по неким другим четко прописанным критериям и т. д.)

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

Поскольку суммарное количество мест на всех факультетах не меньше, чем общее количество абитуриентов, на каком-то шаге все абитуриенты будут распределены по факультетам. Тогда работа программы заканчивается.

Анализируя работу этого алгоритма, экономисты заметили, что абитуриентам может быть выгодно искажать информацию о своих истинных предпочтениях. Рассмотрим эту проблему на следующем «игрушечном» примере.

Предположим, есть три факультета, a, b и c, в каждом по одному месту, и три абитуриента — Петя, Юля и Надя. Предпочтения Пети и Юли относительно факультетов выглядят как a > b > c (a лучше, чем b, а b лучше, чем c), предпочтения Нади как b > c > a. Каждый факультет обязан выбирать абитуриентов с наибольшим количеством баллов на заключительном этапе Всероссийской олимпиады школьников, причём общеизвестно, что балл Пети больше балла Юли, а тот, в свою очередь, больше, чем балл Нади.

а) (5 баллов) Найдите распределение абитуриентов по факультетам, которое реализуется в результате работы алгоритма, описанного выше, если абитуриенты честно сообщат свои предпочтения.

б) (5 баллов) Докажите, что одному из трех абитуриентов выгодно солгать, то есть сообщить алгоритму предпочтения, отличающиеся от его истинных (при условии, что другие два абитуриента будут сообщать свои истинные предпочтения).

в) (8 баллов) Считается, что возникновение у абитуриентов стимулов искажать информацию о предпочтениях — проблема. Какие издержки (потери экономической эффективности) могут быть вызваны возникновением таких стимулов?

г) (12 баллов) Вернёмся к общему случаю с n факультетами и m абитуриентами. Будем говорить, что некий алгоритм распределения устраняет обоснованную зависть, если он всегда производит распределение абитуриентов по факультетам, обладающее следующим свойством: не существует такой пары абитуриентов, что (1) первый абитуриент предпочитает факультет, куда попал второй, своему факультету; (2) первый абитуриент лучше второго с точки зрения правил приема на факультет второго. Допустим, по закону все факультеты упорядочивают абитуриентов одинаково. Придумайте алгоритм распределения абитуриентов по факультетам, который одновременно устраняет как обоснованную зависть, так и стимулы лгать о своих предпочтениях (никакой абитуриент не сможет, солгав, попасть на более предпочтительный для себя факультет, каковы бы ни были предпочтения, сообщенные алгоритму другими абитуриентами). Докажите, что для вашего алгоритма в общем случае выполняются указанные свойства и проиллюстрируйте его работу на примере с Петей, Юлей и Надей.