Куда пойти учиться
Сложный момент для каждого учёного наступает, когда пленарный докладчик на крупной конференции оказывается моложе. Что ж, Параг Патак из МТИ, четвёртый пленарный докладчик на конгрессе по теории игр (три остальных - Маскин, Майерсон и Милгром - титаны, с которыми невозможно равняться), младше меня и даже намного.
Тема - каким образом распределить детей по школам? Но не теория, как можно было бы ожидать на конгрессе по теории, а эмпирика.
В последние пятьдесят лет, начавшихся с математических работ Гейла, Шепли, Скарфа об эффективном распределении выпускников по местам работы (первый механизм на национальном уровне - для выпускников медицинских факультетов - был создан в 1952 году) , экономисты не только получили сотни теорем, но и разработали десятки практических механизмов для больших и маленьких рынков. Можно посмотреть на страничке Эла Рота, который, наверное, получит Нобелевскую премию за свои работы в этой области.
В математическом изложении - «задача о марьяже» звучит так: есть N парней и M девушек и у каждого человека есть предпочтения относительно противоположного пола (то есть, например, для каждого парня девушки упорядочены - от той, на которой он хотел бы жениться сильнее всего, до той, на которой - меньше всего). Задача - алгоритм, который бы дал такое («стабильное») разбиение на пары, что нельзя было бы, разбив и перемешав две пары, сделать новую пару более счастливой. Задачу решили Гейл и Шепли в 1962 году, а на практике «парни» и «девушки», конечно, разные. Иногда «парни» это парни и девушки, а «девушки» - почки и другие человеческие органы. В данном случае у школьников есть предпочтения относительно школ, у школ - относительно школьников. (Например, если речь идёт о средней школе, предпочтения школ определяются результатами обучения в младших классах.)
У нас в РЭШ такой механизм, в одностороннем варианте, используется для распределения второкурсников-магистров по исследовательским семинарам второго года. Одностороннем - потому что у профессоров, как правило, нет предпочтений относительно студентов (я, например, в последний год не преподавал на первом курсе магистратуры и практически никого не знаю). Первый по рейтингу выбирает проект первым, после чего в каком-то из семинаров остаётся на одно свободное место меньше, второй - вторым, и т.д.
В отношении школ в XXI веке крупные американские города стали переходить на механизмы, основанные на алгоритме Гейла-Шепли: Нью-Йорк в 2003, Бостон в 2005, Денвер, Ньюарк и Новый Орлеан - в 2011. (Схемы распределения, учитывающие какие-то комбинаторные соображения этого же класса, есть во многих городах, в том числе Лондоне и Чикаго.)
Работа Патака - эмпирический анализ последствий перехода Нью-Йорка и Бостона на эти алгоритмы. Используются микроданные из бостонских и нью-йоркских школ: опросы (понятно, наименее информативный тип данных) + данные о тех школьниках, которые по каким-то причинам имели возможность выбирать + данные о добровольном выбытии (опять-таки, в случае возможности). Понятно, что это адова, требующего исключительного мастерства эмпирическая работа (впрочем, профессор-географ Михайлова, эмпирик, сидящий рядом, говорит, что профессор Косенок делает такие упражнения шутя) - нужно исключить огромное количество посторонних факторов, которые могут повлиять на результат.
Последствия введения новой системы есть, и значимые: более вероятно, что не покидают школу, более вероятно, что не нарушают то, что предписано алгоритмом (при возможности). Плюс сократилось расстояние до школы (само по себе, самой собой, это не означает, что школьникам стало лучше - плохая школа может быть ближе, но это - косвенный показатель того, что результат стал ближе к предпочитаемому). Нет последствий для успеваемости (Бостон и Нью-Йорк - города в нижних 25% по успеваемости в стране).
Хорошие новости и для экономики общественного сектора (есть технические решения, улучшающие жизнь людей), и для теории игр.
Тема - каким образом распределить детей по школам? Но не теория, как можно было бы ожидать на конгрессе по теории, а эмпирика.
В последние пятьдесят лет, начавшихся с математических работ Гейла, Шепли, Скарфа об эффективном распределении выпускников по местам работы (первый механизм на национальном уровне - для выпускников медицинских факультетов - был создан в 1952 году) , экономисты не только получили сотни теорем, но и разработали десятки практических механизмов для больших и маленьких рынков. Можно посмотреть на страничке Эла Рота, который, наверное, получит Нобелевскую премию за свои работы в этой области.
В математическом изложении - «задача о марьяже» звучит так: есть N парней и M девушек и у каждого человека есть предпочтения относительно противоположного пола (то есть, например, для каждого парня девушки упорядочены - от той, на которой он хотел бы жениться сильнее всего, до той, на которой - меньше всего). Задача - алгоритм, который бы дал такое («стабильное») разбиение на пары, что нельзя было бы, разбив и перемешав две пары, сделать новую пару более счастливой. Задачу решили Гейл и Шепли в 1962 году, а на практике «парни» и «девушки», конечно, разные. Иногда «парни» это парни и девушки, а «девушки» - почки и другие человеческие органы. В данном случае у школьников есть предпочтения относительно школ, у школ - относительно школьников. (Например, если речь идёт о средней школе, предпочтения школ определяются результатами обучения в младших классах.)
У нас в РЭШ такой механизм, в одностороннем варианте, используется для распределения второкурсников-магистров по исследовательским семинарам второго года. Одностороннем - потому что у профессоров, как правило, нет предпочтений относительно студентов (я, например, в последний год не преподавал на первом курсе магистратуры и практически никого не знаю). Первый по рейтингу выбирает проект первым, после чего в каком-то из семинаров остаётся на одно свободное место меньше, второй - вторым, и т.д.
В отношении школ в XXI веке крупные американские города стали переходить на механизмы, основанные на алгоритме Гейла-Шепли: Нью-Йорк в 2003, Бостон в 2005, Денвер, Ньюарк и Новый Орлеан - в 2011. (Схемы распределения, учитывающие какие-то комбинаторные соображения этого же класса, есть во многих городах, в том числе Лондоне и Чикаго.)
Работа Патака - эмпирический анализ последствий перехода Нью-Йорка и Бостона на эти алгоритмы. Используются микроданные из бостонских и нью-йоркских школ: опросы (понятно, наименее информативный тип данных) + данные о тех школьниках, которые по каким-то причинам имели возможность выбирать + данные о добровольном выбытии (опять-таки, в случае возможности). Понятно, что это адова, требующего исключительного мастерства эмпирическая работа (впрочем, профессор-географ Михайлова, эмпирик, сидящий рядом, говорит, что профессор Косенок делает такие упражнения шутя) - нужно исключить огромное количество посторонних факторов, которые могут повлиять на результат.
Последствия введения новой системы есть, и значимые: более вероятно, что не покидают школу, более вероятно, что не нарушают то, что предписано алгоритмом (при возможности). Плюс сократилось расстояние до школы (само по себе, самой собой, это не означает, что школьникам стало лучше - плохая школа может быть ближе, но это - косвенный показатель того, что результат стал ближе к предпочитаемому). Нет последствий для успеваемости (Бостон и Нью-Йорк - города в нижних 25% по успеваемости в стране).
Хорошие новости и для экономики общественного сектора (есть технические решения, улучшающие жизнь людей), и для теории игр.