Игры и графы: как прошла третья стажировка в Международной лаборатории теории игр

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

Это третий год, когда мы проводим стажировку, об итогах предыдущих вы можете узнать здесь. В этом году стажировка была в полтора раза больше: мы пригласили 32 стажера и почти 30 руководителей-лекторов. Также мы значительно расширили тематику исследований: к классическим теоретическим задачам из областей теории игр, дизайна механизмов и принятия решений добавились индустриальные проекты сотрудников московской Лаборатории сложных сетей, гиперграфов и их приложений. 

Лучшие результаты по проектам были поданы на конкурсы от индустриальных партнеров и международные конференции - подробнее о проектах и итогах стажировки вы можете прочитать в конце статьи.  

Программа

1. Первая неделя: знакомство с сотрудниками лаборатории и приглашенными исследователями, лекции по темам теории игр и прикладной математики.  В этом году из-за большего количества проектов все лекции на первой теоретической неделе были распределены на два трека - «экономический» и «математический». У каждого стажера была возможность выбрать предпочитаемый трек, все лекции по которому становились для него обязательными - прочие можно было посещать по желанию.  

Темы лекций 

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

2. Этап распределения: в конце первой недели мы попросили каждого студента проранжировать все предложенные руководителями задачи и выбрать самые предпочитаемые. Это было нужно, чтобы максимально, насколько это возможно, эффективно и справедливо распределить проекты. Мы старались сделать так, чтобы:

• большему количеству студентов досталась их самая предпочитаемая задача
• проект соответствовал исследовательскому опыту студента
• все задачи были распределены  

После подведения итогов распределения стажеры знакомились со своими руководителями и начинали работу по проектам, которая шла непрерывно до конца стажировки. 

Стажеры с указанием руководителей и задач

3. Работа по проектам, дополнительные внутренние семинары, общие дискуссии. 

4. Четвертая неделя: доработка проектов согласно рекомендациям руководителей и финальные презентации.

Финальная презентация представляла из себя короткое выступление с результатами, полученными за время стажировки. Руководители указывали на недочеты в решениях и предлагали, как можно построить работу по проектам в дальнейшем, чтобы довести их до препринта.

Участники мероприятия

Лекторами и научными руководителями стажировки стали:

• сотрудники Международной лаборатории теории игр и принятия решений 
• сотрудники Центра теории рынков и пространственной экономики
• доценты Факультета экономических наук московского кампуса НИУ ВШЭ
• сотрудники научно-учебной лаборатории сложных сетей, гиперграфов и их приложений
• сотрудники других российских университетов:

Российской Экономической Школы, Новосибирского Государственного Университета и МФТИ

• профессоры многих зарубежных исследовательских центров:  
  • BIMSA - Beijing Institute of Mathematical Sciences and Applications (Пекинский Институт Математики и ее приложений)
  • Delhi Statistical Institute (Индийский Статистический Институт),  
  • University of Glasgow (Университет Глазго)
  • Университет Рима Тор Вергада
  •  Университет Озейгин в Турции. 

Результаты стажировки

Каждая задача была сложной по-своему: часто много времени уходило на изучение литературы, иногда нужно было программировать или проводить симуляции, а с некоторыми теоретическими задачи и вовсе непонятно было, как подступиться. Ясно всегда одно - стандартного решения не существует, нужен творческий подход, поддержка руководителя, товарищей и много терпения.  

Итоговые презентации проектов оказались очень удачными: несмотря на крайне сжатые сроки работы по задачам, всем студентам удалось глубоко погрузиться в свои темы и представить продвижения. Особенно выдающиеся результаты представила 
Стажеры 2024 года вместе с организаторами группа студентов, занимавшаяся в рамках стажировки задачами математической оптимизации и моделями сложных сетей.  

Было получено решение прикладной оптимизационной задачи Юрия Андреевича Кочетова (стажер - Борис Гавриш, экономический факультет МГУ), результаты которой будут продемонстрированы на международной конференции MOTOR(Methods of Optimization and Operations Research). Также были совершены существенные продвижения по ряду теоретических задач (стажер Степан Бондарь под руководством Алексея Суздальцева) и по проектам под руководством Ивана Самойленко, Олега Баранова и Максима Бекетова (стажеры - Максим Клименко, МФТИ, Антон Зудин - экономический факультет МГУ, Степан Спирин - математический факультет НИУ ВШЭ). 
 

Примеры постановок решенных задач

 Задача поиска расстояний на графе с помощью DomiRank (открытая задача конференции MOTOR)

Описание: поиск кратчайших путей в графе - классическая задача теории графов, которая имеет огромное количество приложений в самых разных областях, от построения путей в навигаторе до вопросов логистики. В задаче со стажировки предлагалось оптимизировать имеющиеся на сегодняшний день алгоритмы, которые отталкиваются от «важных» вершин графа (вершин с высокой метрикой центральности), и вершины обрабатываются в некотором порядке возрастания их важности. Для этого использовалась недавно появившаяся мера центральности DomiRank, которая позволяет выбирать в графе «важные» вершины более равномерно.  

Итог: Метрика DomiRank показала себя хорошо по сравнению с другими способами ранжирования вершин, в некоторых случаях алгоритмы получилось значительно ускорить. 

Предложенное решение получило первое место на конкурсе открытых задач конференции по методам оптимизации и исследованию операций MOTOR 

Задача логистики заправочных станций

Описание: задача заключалась в разработке алгоритма маршрутизации бензовозов при пополнении запасов АЗС. При этом в качестве отправной точки берется специфика работы российских топливных компаний, которая слабо исследована в научной литературе. 

Итог: реализованный алгоритм позволяет получать маршруты высокого качества за меньшее время, гарантируя в большинстве случаев минимальное отклонение от оптимума. 

Модели устойчивого образования сетей

Описание: для торговли между странами важно, чтобы расстояние, которое проходит груз, было минимальным из возможных при заданных ограничениях. Это важно не только в стандартных ситуациях, но также и при ограниченном количестве сбоев в сети (например, разрушении связей, то есть падении какого-то числа рёбер). В задаче на стажировке предлагалось описать все равновесные графы в модифицированной модели Bala & Goyal, 2000, где вместо классического расстояния используется устойчивое расстояние – максимальное из расстояний от исходной вершины до другой при падении 1 ребра. 

Итог: получилось доказать несколько теоретических утверждений, а также найти архитектуру графа, который является “хорошим” в том смысле, что он является единственным решением задачи о минимизации числа ребер при том, что устойчивое расстояние между любыми ребрами равно 2. В симуляциях, когда “хороший” граф является равновесием по Нэшу, графы сходятся к этой “хорошей” архитектуре. 
 

Задача поиска константы Чигера для моделей образования сетей

Описание: пусть дана полная геометрическая сеть попарных расстояний между вершинами. Чтобы не работать с полным графом, можно убрать часть рёбер так, чтобы расстояние между любыми двумя вершинами ухудшилось не более чем в t раз. Получившаяся сеть называется t-остовом изначального графа, и такие конструкции применяются в телекоммуникационных сетях и планировании маршрутов.  
Нашей задачей было изучить, как в зависимости от параметра растяжения t зависит кластеризуемость сети, то есть то, насколько хорошо она разбивается на две компоненты связности. Для этого мы проводили компьютерные симуляции и смотрели на нормализованный разрез tостовов. 

Итог: было получено, что при небольшом t (около 2-х) уже достигается как очень малое значение нормализованного разреза, так и небольшая суммарная длина всех рёбер. В дальнейшем к задаче можно применить теоретический подход или использовать другую меру вместо нормализованного разреза. 

Организатор мероприятия

Организатор мероприятия - Международная лаборатория теории игр и принятия решений