Правила приёма
Во многих странах абитуриенты распределяются по вузам и факультетам с помощью централизованных алгоритмов. Рассмотрим один из них.
Допустим, есть 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) первый абитуриент лучше второго с точки зрения правил приема на факультет второго. Допустим, по закону все факультеты упорядочивают абитуриентов одинаково. Придумайте алгоритм распределения абитуриентов по факультетам, который одновременно устраняет как обоснованную зависть, так и стимулы лгать о своих предпочтениях (никакой абитуриент не сможет, солгав, попасть на более предпочтительный для себя факультет, каковы бы ни были предпочтения, сообщенные алгоритму другими абитуриентами). Докажите, что для вашего алгоритма в общем случае выполняются указанные свойства и проиллюстрируйте его работу на примере с Петей, Юлей и Надей.
а) Петя попадет на факультет a, Юля на факультет c, а Надя на факультет b.
б) Очевидно, что этим абитуриентом будет Юля, так как только она не получает лучший для себя факультет в распределении выше. Если она заявит, что ее предпочтения имеют вид b > a > c (что неправда), то она попадет на факультет b (поменявшись местами с Надей), что для нее c точки зрения ее истинных предпочтений лучше, чем факультет c.
в) Правда только одна, а лгать можно по-разному. Действительно, со стимулами лгать возникает также вопрос о том, как именно оптимально лгать. Ответ на него может зависеть от предпочтений других участников (и того, как они будут их искажать!). Это может заставить участников инвестировать время и деньги в поиск такой информации (что является чистой потерей с точки зрения общества), а также повышает степень неопределенности в системе. Кроме того, если каждый абитуриент говорит правду, координаторы системы автоматически получают информацию об истинной популярности разных факультетов, которую затем можно использовать, например, для оценки их деятельности. Если информация о предпочтениях искажена, сделать этого нельзя.
В качестве верных ответов засчитывались, например, следующие:
- Абитуриенты подают факультетам неверный сигнал о качестве последних. За счёт этого менее престижные факультеты получают большее финансирование.
- Можно предположить, что предпочтения абитуриентов устроены следующим образом: наибольшую ценность представляет первый указанный выбор. Остальные не значимы. В этом случае даже в исходном примере ложь Юли приводит к уменьшению общественного благосостояния.
- В реальности абитуриенты наблюдают лишь свои предпочтения. Для того, чтобы узнать предпочтения других участников, абитуриентам придётся потратить на это время и деньги.
г) Алгоритм этот прост. Занумеруем абитуриентов в едином порядке ранжирования их факультетами. После того, как участники подали свои предпочтения в систему: (1) отправим первого (лучшего) абитуриента на лучший с его точки зрения факультет; (2) будем отправлять каждого следующего по списку на лучший для него факультет среди тех, в которых еще остались места. Очевидно, что никому не будет выгодно лгать (сказав правду, каждый попадет в лучший из оставшихся факультет). При этом любая зависть может быть только необоснованной: на любой факультет, лучший, чем тот, что достался абитуриенту j, попадут только те, кто стоит выше в рейтинге, чем j.
При этом важно заметить, что существуют и другие алгоритмы, позволяющие одновременно устранить и обоснованную зависть, и стимулы лгать. Участник мог привести пример любого работающего алгоритма.
Примечание: В 2012 году Ллойд Шепли и Элвин Рот получили Нобелевскую премию по экономике, в том числе, за создание алгоритма распределения, который имеет указанные свойства, даже если правила приема на разные факультеты различны. Этот алгоритм, впервые описанный в 1962 г., получил известность как алгоритм Гейла-Шепли. Алгоритм, описанный в решении выше, является частным случаем алгоритма Гейла-Шепли. В условии же описывается работа так называемого Бостонского алгоритма, который является популярным способом распределять учеников по школам на практике во многих городах. В 2003 г. команда Элвина Рота приняла участие в реформе процедуры распределения учеников по школам в Бостоне, в результате чего действовавший там до этого (Бостонский) алгоритм был заменен на алгоритм Гейла-Шепли. В результате этого степень удовлетворенности работой системы в городе возросла, что связано, в том числе, с устранением проблем, описанных в пункте в). Подробнее об этом и других успешных примерах «дизайна рынков» можно почитать в книге Элвина Рота «Кому что достанется — и почему», вышедшей на русском языке