Пресса об РФФИ
Мозги, бумага и перо. Плюс поддержка РЦНИ позволили исследовать концепции оптимальности
Газета «Поиск» (г. Москва), 09.07.2023
Дата публикации: 10.07.2023
На многих рынках нельзя использовать деньги. «Как так?» — спросите вы. Это происходит, потому что там не работают обычные, широко используемые и изученные ценовые механизмы. Такие бесценовые рынки прежде всего можно найти в системе образования: при распределении школьников по школам, зачислении абитуриентов в вузы, записи студентов на те или иные программы и курсы внутри их учебного заведения. Эти и подобные им рынки моделируются так называемой задачей о сочетаниях (matching problem).
Взять, например, рынок студентов и вузов. У каждого имеются предпочтения относительно участников со второй стороны рынка. К этой задаче можно применять стандартные экономические требования оптимальности (можно ли изменить данное сочетание так, чтобы кому-то стало лучше, не сделав никому хуже?) и справедливости: завидуют ли участники сочетаниям других участников? Является ли эта зависть обоснованной в том смысле, что участники не только хотят, но и заслуживают выстроить другое сочетание (как если бы абитуриент набрал баллы выше проходного, но не был зачислен на желаемый факультет)? На практике каждый такой рынок регулируется особыми правилами и процедурами, которые предписывают участникам, в каком порядке им следует действовать и каких результатов стоит ожидать. Язык науки такие правила и процедуры величает «механизмами сочетания». Участники рынка в каком-то виде сообщают механизму свои предпочтения и прочую приватную информацию, а механизм выдает на основе этой информации итоговое сочетание. Наконец, помимо оптимальности и справедливости третьим важным свойством механизма сочетания является неманипулируемость: участникам должно быть выгодно сообщать личную информацию правдиво, а не хитрить или сговариваться, то есть манипулировать.
Собственно, поэтому люди и придумывают реформы, чтобы сделать жизнь более прогнозируемой и справедливой. Получается? Не всегда. Почему так выходит, «Поиску» рассказал доцент Национального исследовательского университета «Высшая школа экономики» в Санкт-Петербурге Александр НЕСТЕРОВ. Он заведует международной лабораторией теории игр и принятия решений в этом вузе и руководит рабочей группой, выполняющей проект «Новые концепции эффективности и манипулируемости в задачах о сочетаниях», поддержанный грантом Российского центра научной информации (№20-01-00687).
Как объяснил ученый, концепции эти должны быть интуитивными и удобными для оценки сочетаний и механизмов их сочетаний на практике. Лучшими объектами таких сравнений являются механизмы, используемые в системах распределения и приема разных стран мира: например, реформа на рынке труда врачей начального уровня в США (1998), реформа системы приема в школы в Нью-Йорке (2004), Чикаго (2009-2010), Денвере (2012), некоторых городах Ганы (2007-2008) и графствах Англии (2005-2010), реформы в системе приема в вузы в провинциях Китая. Все эти перемены люди инициировали потому, что старые механизмы являлись, строго говоря, несправедливыми или манипулируемыми. Однако и новые механизмы также получились не более справедливыми.
Разработанные учеными критерии позволяют сравнить механизмы до и после этих реформ и таким образом оценить эффект нововведений. Причем показано, что некоторые из перемен были очень благотворными: снизили число участников-манипуляторов (то есть тех, кто может получить лучшее сочетание, если сообщит неправдивую информацию) и число участников с обоснованной завистью. Следует отметить, что посчитать и назвать число не представляется возможным, поскольку неизвестны истинные предпочтения. Однако доказано, что при новых механизмах это число стало или будет ниже, что делает механизм очень сильным, а результат — впечатляющим.
— Наш проект исследует свойства таких механизмов, как оптимальность, справедливость и манипулируемость (иными словами, какие стимулы дает участникам механизм правдиво сообщать свои предпочтения, а не привирать). Важно, что мы разрабатываем относительные критерии для сравнения механизмов. Это не абсолютные свойства, пригодные для проверки механизмов на «идеальность» (идеально оптимальных, справедливых и неманипулируемых), а предназначенные для выбора лучшего из имеющихся неидеальных механизмов. Подчеркну, это важно потому, что в жизни все доступные механизмы далеки от совершенства и обычные абсолютные критерии неприменимы. И для выбора лучшего из имеющегося нам нужны именно относительные критерии сравнения, — рассказал Александр Нестеров.
— Как определяют эти критерии, Александр Сергеевич?
— Целью первого этапа нашего проекта стала разработка фундаментальных концепций оптимальности, манипулируемости для задач о сочетаниях. Эти задачи о сочетаниях сегодня — самое актуальное направление исследований устройств экономических механизмов (mechanism design — объяснение и создание стандартных процедур) и дизайна рынков (market design — объяснение и создание платформ и механизмов сочетания спроса и предложения). Кстати, успехи в их решении и создании приложений отмечены Нобелевской премией (Элвин Рот и Ллойд Шепли, 2012) и — второй по престижности — медалью Джона Бейтса Кларка (Параг Патак, 2018). Результаты этих и других исследователей помогли объяснить многочисленные эмпирические наблюдения и улучшить реальные механизмы и рынки.
Основными желательными свойствами механизмов сочетаний являются стабильность (гарантирует, что механизм даст устойчивое сочетание и никакой агент не сможет улучшить его вне рынка; в теории это эквивалентно понятию «справедливость»), оптимальность и неманипулируемость (невозможность получить лучшее сочетание за счет искажения истинных своих предпочтений).
В рамках проекта мы расширили концепции оптимальности и неманипулируемости. Критерием оптимальности сочетаний обычно принимается эффективность по Парето. Это очень слабый критерий: ему может соответствовать сразу большое количество сочетаний, и выбор из них представляет теоретический и практический интерес. Мы предложили использовать критерий популярности сочетаний. Популярным сочетанием называется то, которое выбирает большинство агентов по сравнению с любым другим. Это и есть усиление критерия эффективности по Парето.
Мы предложили новую характеризацию популярного сочетания, необходимым и достаточным условием которого является локальная популярность. Иначе говоря, ни одна тройка агентов не хочет обменяться своими сочетаниями по большинству голосов в этой тройке. Пока существовал только один алгоритм поиска популярного сочетания — централизованный (стартует с пустого сочетания). Мы разработали децентрализованный алгоритм поиска популярного сочетания, модернизировав исходное непопулярное сочетание за счет обмена в тройках. И свели этот процесс к популярному сочетанию. Однако популярное сочетание может не существовать.
— Что же такое популярное сочетание в общем случае?
— «Наиболее популярным сочетанием» мы назвали то, которое будет предпочтительным среди наибольшего подмножества агентов. То есть если в задаче не существует популярного сочетания, мы спрашиваем, какое минимальное число агентов надо исключить, чтобы популярное сочетание стало существовать. Получившееся сочетание и будет наиболее популярным. Мой коллега Егор Яновский невесело пошутил, назвав это «критерием Сталина»: если какие-то агенты мешают существованию популярного сочетания, можно этих агентов убрать.
Что касается манипулируемости, здесь у нас две серии результатов. Во-первых, прежние наблюдения в литературе показали, что сотни манипулируемых механизмов по всему миру были заменены на менее манипулируемые, если судить по одному базовому критерию. Это результаты упоминавшегося Парага Патака и ведущего теоретика в задачах о сочетаниях Тайфуна Сенмеза. Однако нами была обнаружена критическая ошибка в одном из их основных результатов: ни одна из 50 реформ механизмов сочетаний, проведенных в Великобритании, не может быть объяснена посредством их критерия манипулируемости. Поэтому мы разработали свой критерий для этого случая — критерий стратегической доступности. Механизм называется более стратегически доступным, если при нем каждый агент (школьник, абитуриент, студент) получает большее множество объектов (школ, вузов), в которые он может поступить благодаря манипуляции. Наши результаты показывают, что этот критерий сможет объяснить все описанные реформы механизмов сочетаний в Великобритании, США, Китае, странах Африки и на Тайване.
— То есть разработанные вами в рамках гранта критерии позволяют сравнить механизмы до и после этих реформ и таким образом оценить эффект перемен?
— Да. Но есть и более точный и интуитивный критерий, с ним мы получили вторую серию результатов. Мы показываем, что некоторые из этих реформ были очень благотворными: они снизили число агентов-манипуляторов (то есть тех, кто может получить лучшее сочетание, если отклонится от правдивой стратегии) и число агентов с обоснованной завистью. Отметим, что посчитать число не представляется возможным, поскольку неизвестны истинные предпочтения, однако мы доказываем, что, какими бы ни были истинные предпочтения, при новых механизмах число обманщиков и недовольных будет ниже, что делает наш результат очень сильным. Эти и другие исследования мы публикуем в двух статьях: одна вышла в ведущем журнале по экономической теории Theoretical Economics (2021), другая принята в печать в Theoretical Economics (2023).
— Ваши разработки применимы только к рынкам образования?
— Не только. Мы смогли получить несколько результатов, связанных с нашей основной программой. Во-первых, мы оценили аукцион по продаже квот на краба в России в 2019 году, крупнейший ресурсный аукцион в истории рыболовства, и предоставили инструменты для разработки менее манипулируемого аукциона. Использованный формат аукциона давал участникам значительные стимулы к манипулированию, и потому его результаты могут быть не столь желательными, как при иных механизмах. Результаты опубликованы в «Экономическом журнале ВШЭ» (2021).
Во-вторых, нами исследованы балльные правила, которые применяют в спортивных соревнованиях и состязаниях в других областях. Статья про эту работу вышла в нынешнем году в лучшем журнале по менеджменту и исследованию операций Operations Research.
В-третьих, разработан полиномиальный алгоритм для вычисления полезного правила социального выбора, называемого пропорциональным вето-ядром, результаты готовятся к публикации.
Ну, а материалы по концепции популярности, о которой мы говорили выше, опубликованы в ведущем журнале по менеджменту и исследованию операций European Journal of Operational Research (2022).
— А каким образом, с помощью каких программ, на каком оборудовании производится весь этот анализ?
— Все наши результаты — это математические теоремы, так что все программы и оборудование — это мозги, бумага и перо.
— Сколько человек работает в команде?
— Основных исполнителей было трое: мои коллеги по лаборатории — Алексей Кондратьев, Сомуага Бонкунгу — и я. С Алексеем мы получили результаты о популярных сочетаниях, с Сомуагой — о сравнении механизмов сочетаний, а результаты о крабовом аукционе были получены мною вместе с компьютерным ученым Дмитрием Ивановым, математиком Никитой Калининым и экономистом Иваном Сусиным. Алексей Кондратьев и Егор Яновский получили результаты по вето-ядру, и мы втроем получили результаты о балльных правилах.
— С кем сотрудничаете при выполнении гранта?
— Со всеми коллегами-теоретиками. В нашем департаменте собралась большая и сильная команда экономистов-теоретиков и математиков, и все результаты мы сначала обсуждаем с коллегами за чаем и на научных семинарах. Помимо упомянутых выше профессионалов в статьях мы благодарим Елену Яновскую, Федора Сандомирского, Константина Сорокина, Мишу Гавриловича, Михаила Панова, Анну Богомольную, Рустамджана Хакимова, стажера Оксану Нырку и ряд иностранных коллег.
В целом наши результаты помогают разрабатывать механизмы сочетаний и аукционы с доказательно лучшими свойствами. Так мы подготовили свои предложения по улучшению системы приема в вузы и аукционов по продаже прав на добычу ценных ресурсов.
Андрей Субботин
Источник: Газета «Поиск»
Фото: Южные горизонты
