Ученые ВШЭ доказали существование равновесия Нэша для нового класса задач в теории игр
Ученые Санкт-Петербургской школы экономики и менеджмента НИУ ВШЭ изучают способы эффективного распределения ресурсов в системах со множеством участников. Исследователи доказали существование выгодных стратегий выбора в условиях конкуренции за ограниченные неделимые ресурсы в четырех случаях. Созданную математическую модель можно использовать в различных сферах — от образования и медицины до управления сетями и вычислительными мощностями. Работа опубликована в Games and Economic Behavior.
В мире постоянно идет борьба за разнообразные ресурсы, и человеку приходится выбирать оптимальную стратегию, чтобы их получить. Абитуриенты выбирают вуз для поступления, компании конкурируют за лучшие проекты, в спортивном зале люди спешат занять свободный тренажер.
Ученые стремятся найти такие методы, которые помогут системам с большим количеством участников работать эффективно, избегая перегрузок или нерационального использования ресурсов. Эти задачи можно свести к математической модели, в которой участники-агенты принимают решения на основе потенциальной выгоды, доступных ресурсов и своих возможностей. В теории игр такие модели изучаются с точки зрения равновесия Нэша — состояния, в котором никто из участников не хочет менять свой выбор, потому что это не принесет увеличения выгоды.
Исследователи Санкт-Петербургской школы экономики и менеджмента НИУ ВШЭ доказали существование равновесия Нэша в некоторых типах игр с неделимыми ресурсами, такими как место в самолете, квартира, книги в библиотеке или место в вузе. (Дискретные они потому, что нельзя взять половину места в самолете у окошка и половину — в проходе).
Для доказательства существования равновесия Нэша ученые создали математическую модель, в которой каждый участник (агент) выбирает один из доступных ресурсов. Участники стремятся к тому, чтобы получить наибольшую выгоду, максимизировать свою долю от ресурса. Так образуется система, в которой на выбор агента влияет не только сам ресурс, но и то, сколько других участников выбрали этот же ресурс.
В модели важное значение имеет такая характеристика участников, как вес. Например, когда абитуриенты выбирают вуз, они ориентируются на параметры образовательной программы, на транспортную доступность вуза, на его статус и др. Они оценивают величину этого ресурса и свою способность его освоить. Собственные возможности агента по отношению к определенному ресурсу и называются его весом.
Исследователи доказали, что равновесие Нэша, выгодное для всех агентов, действительно существует для четырех случаев. Первый случай — когда вес агента не зависит от ресурса, а величины ресурсов различны. Например, абитуриент с высшими баллами ЕГЭ выбирает из вузов с разным рейтингом.
Во втором случае вес агента зависит от ресурса, но величины всех ресурсов одинаковы: в одном из топовых вузов абитуриент выиграл внутреннюю олимпиаду и имеет приоритетное право поступления.
В третьем варианте вес агента зависит от ресурса, величины ресурсов различны, но ресурсов только два: абитуриент может легко поступить в неизвестный вуз по внутренней олимпиаде или на общих основаниях — в именитый университет.
И четвертый случай — особый. Если количество участников в системе велико, агентов больше 20, то система стремится к равновесию и подходит к нему очень близко, но не достигает его. Это асимптотический результат, он хорошо отражает действительность. В таких случаях каждый участник действует почти оптимально. Даже если изменить стратегию, ситуацию не удастся существенно улучшить.
Василий Гусев
«Доказательство для четвертого случая мы не сразу нашли, его предложил слушатель школы стажеров, которую проводит наша лаборатория. Это Михаил Решетов, он стал нашим соавтором», — рассказал один из авторов статьи, старший научный сотрудник Международной лаборатории теории игр и принятия решений НИУ ВШЭ — Санкт-Петербург Василий Гусев.
По мнению исследователей, созданная математическая модель открывает возможности для улучшения систем распределения ресурсов в различных областях — от образования и медицины до распределения вычислительных мощностей и управления большими сетями.
Александр Нестеров
«Мы показали, что соревнования за ресурсы не ведут к хаосу, а стабилизируются без внешнего вмешательства. Мы математически доказали, что, если дать агентам свободу выбора, все найдут для себя выгодный результат», — комментирует соавтор статьи, заведующий Международной лабораторией теории игр и принятия решений НИУ ВШЭ — Санкт-Петербург Александр Нестеров.