Развитие методов управления многоагентными системами в условиях конфликта

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

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

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 22-11-00051

НазваниеРазвитие методов управления многоагентными системами в условиях конфликта

Руководитель Петросян Леон Аганесович, Доктор физико-математических наук

Организация финансирования, регион федеральное государственное бюджетное образовательное учреждение высшего образования "Санкт-Петербургский государственный университет" , г Санкт-Петербург

Конкурс №68 - Конкурс 2022 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-209 - Теория игр

Ключевые слова Многоагентная система, сетевое взаимодействие, управление, динамическая игра, равновесие, кооперация

Код ГРНТИ28.29.05

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Многие процессы, протекающие в информационно-коммуникационных и социально-экономической сферах, в военном деле и международной деятельности, в задачах экологического и природоохранного характера, моделируются посредством многоагентных систем (МАС) и, зачастую, носят конфликтный характер. В таких системах предполагается присутствие интеллектуальных агентов, которые своим поведением могут влиять на состояние самой системы. Одним из важных качеств МАС является децентрализация агентов, позволяющая управлять системой лишь едиными координированным механизмом, а также их ограниченное представление о системе, что позволяет агентам «наблюдать» только некоторую часть системы, а не всю систему полностью. В проекте предлагается исследовать вопросы управления МАС с интеллектуальными агентами, используя аппарат математической теории игр и ее наиболее актуальный подраздел – теорию дифференциальных и динамических игр. Важной особенностью этих задач является конфликтный характер взаимодействия агентов, что делает необходимым использование методов и подходов математической теории принятия решений в условиях конфликта (математической теории игр). Дополнительно для точного анализа конфликтного процесса взаимодействия необходимо исследовать его во времени. Важным и нетривиальным вопросом в проекте является формализация, казалось бы, таких очевидных понятий как “оптимальное поведение” интеллектуальных агентов МАС (выработка принципа оптимальности), нахождение условий его существования и единственности, а при исследовании процессов в динамике нахождение условий его динамической устойчивости (состоятельности во времени), и наконец создание программного продукта для нахождения решений, соответствующих принятым принципам оптимальности. В зависимости от характеристик МАС в качестве основного аппарата исследования можно использовать математическую теорию оптимального управления, и такие ее разделы как теория динамических, дифференциальных, стохастических, сетевых, а также в ряде случаев и эволюционных игр. В частности, ограниченное представление агента о системе может быть хорошо формализовано в терминах сетевой игры, где агент взаимодействует не со всеми элементами МАС, а лишь со своими соседями (прямыми или уровня k). Предполагается рассматривать коллективное поведение МАС, при котором внешний арбитр централизованным образом определяет поведение интеллектуальных агентов, ориентируясь на достижение наилучших показателей для всей системы в целом. При разработке такого поведения желательно обеспечить также индивидуальную рациональность агентов для их мотивации придерживаться заданного поведения. Это позволит использовать результаты кооперативной теории динамических игр для определения в некотором смысле оптимального поведения агентов внутри системы. В то же время интересными являются исследования поведения, допускающего объедение агентов в некоторые группы (коалиции) внутри МАС. Подобное допущение встречается в литературе, например, в задачах группового консенсуса – такого поведения агентов, которое однотипно внутри одной группы, но может различаться от группы к группе внутри МАС. Таким образом, возможно построение принципов оптимальности для определения поведения внутри МАС в предположении, что агенты могут формировать группы-кластеры (коалиции). Здесь может быть предложен подход, основанный на двухуровневой оптимизации: для агентов внутри группы используется кооперативное поведения, найденное как решение соответствующей кооперативной дифференциальной или динамической игры, а на уровне МАС - более общие решения, которые могут представлять собой равновесия между группами или их кооперация. В теории кооперативных динамических игр хорошо известно, что для сохранения кооперации и принятых соглашений внутри МАС требуется выполнение более жесткого условия: в процессе реализации решения принцип оптимальности, на основе которого вырабатывалось первоначальное решение, должен оставаться состоятельным в течение всего процесса принятия решений. Это условие носит название “динамической устойчивости” или “состоятельности во времени”. Именно вопросу построения динамически устойчивых (состоятельных во времени) решений будет уделено особое внимание. В частности, аналогичная проблема возникает и при решении задачи двухуровневой оптимизации в МАС, когда возможна кластеризация агентов. Здесь в зависимости от принятых принципов оптимальности (равновесия или кооперативного решения) предполагается провести анализ его динамической устойчивости. Стоит отметить, что в случае выбора равновесия по Нэшу в качестве принципа оптимальности, такое равновесное поведение в подавляющем большинстве случаев является динамически устойчивым, но может таковым не быть в случае выбора кооперативных решений. Поэтому на первом этапе мы ограничимся равновесными решениями для определения взаимодействия между элементами (самими агентами или кластерами) МАС. Используя математический аппарат теории динамических и дифференциальных игр, предполагается построить новые модели поведения МАС во времени и построение принципов оптимальности (в том числе двухуровневых, включающих в себя как оптимизацию поведения агентов внутри кластеров, так и между кластерами). Основной задачей проекта является разработка новых динамически устойчивых (состоятельных во времени) механизмов управления, соответствующих выработанным принципам оптимальности, в указанных задачах, в том числе и в сетевой постановке, нахождение условий их существования, получение решений в явном виде, а при невозможности явного аналитического представления – нахождение эффективных вычислительных алгоритмов, а также исследование вопросов стратегической поддержки принципа оптимальности.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Петросян Л. А., Панкратова Я. Б. Two Level Cooperation in Dynamic Network Games with Partner Sets Lecture Notes in Computer Science, 13367, pp. 250–263, 2022 (год публикации - 2022)
10.1007/978-3-031-09607-5_18

2. Дамуни И., Парилина Е. М., Заккур Дж. Great fish war with moratorium Mathematical Biosciences, 355, 108939 (год публикации - 2023)
10.1016/j.mbs.2022.108939

3. Гао Ц., Парилина Е. Optimal control in a multiagent opinion dynamic system Contributions to Game Theory and Management, XV, 51–59 (год публикации - 2022)
10.21638/11701/spbu31.2022.05

4. Парилина Е., Тампиери А. Faking Patience with Tacit Collusion International Game Theory Review, 2022 (год публикации - 2023)
10.1142/S0219198923500032

5. Реттиева А. Н. Multicriteria Dynamic Games with Asymmetric Horizons Lecture Notes in Computer Science, 13367, pp. 264–278, 2022 (год публикации - 2022)
10.1007/978-3-031-09607-5_19

6. Ли Ц., Тур А., Завражнов М. Importance of Agents in Networks: Clique Based Game-Theoretic Approach Contributions to Game Theory and Management, XV, 189–199 (год публикации - 2022)
10.21638/11701/spbu31.2022.14

7. Тур А., Петросян Л. The Core of Cooperative Differential Games on Networks Lecture Notes in Computer Science, LNCS 13367, pp. 295–314, 2022 (год публикации - 2022)
10.1007/978-3-031-09607-5_21

8. Мазалов В. В., Яшин В. В. Равновесие в задаче выбора момента встречи Вестник СПбГУ. Прикладная математика. Информатика. Процессы управления (год публикации - 2022)

9. Чиркова Ю. В., Мазалов В. В. Optimal Arrivals to Preemptive Queueing System Lecture Notes in Computer Science, 13367, pp. 169–181, 2022 (год публикации - 2022)
10.1007/978-3-031-09607-5_12

10. Гриних А. Л. Cooperation in the Multi-Agent System with Different Types of Interactions Contributions to Game Theory and Management, XV, 60–80 (год публикации - 2022)
10.21638/11701/spbu31.2022.06

11. Булгакова М. А. The τ-value in Multistage Games with Pairwise Interactions Contributions to Game Theory and Management, XV, 32–40 (год публикации - 2022)
10.21638/11701/spbu31.2022.03

12. Петросян Л. А., Панкратова Я. Б. Owen Value for Dynamic Games on Networks Contributions to Game Theory and Management, XV, 218–225 (год публикации - 2022)
10.21638/11701/spbu31.2022.16

Публикации

1. Петросян Л., Янг Д., Панкратова Я. Characteristic functions in cooperative differential games on networks Journal of Dynamics and Games, 16 p. (год публикации - 2023)
10.3934/jdg.2023017

2. Петросян Л., Янг Д., Панкратова Я. Power Degrees in Dynamic Multi-Agent Systems Труды Института математики и механики УрО РАН, vol. 29, no. 3, pp. 128–137 (год публикации - 2023)
10.21538/0134-4889-2023-29-3-128-137

3. Мазалов В. В., Ивашко А. А. Harmonic Numbers in Gambler’s Ruin Problem Lecture Notes in Computer Science, Lecture Notes in Computer Science, vol 13930 (год публикации - 2023)
10.1007/978-3-031-35305-5_19

4. Алхалед Х., Петросян Л. А. Game Theoretic Approach to Multi-Agent Transportation Problems on Network Contributions to Game Theory and Management, Contributions to Game Theory and Management, XV, 8–17 (год публикации - 2023)
10.21638/11701/spbu31.2022.01

5. Мазалов В. В., Реттиева А. Н. Exploitation and Recovery Periods in Dynamic Resource Management Problem Lecture Notes in Computer Science, LNCS 13930 (год публикации - 2023)
10.1007/978-3-031-35305-5_20

6. Ндиайе С. М., Парилина Е. М. Одна коалиционная дифференциальная игра производителей вакцин Математическая теория игр и её приложения, т. 15, в. 3, с. 21-40 (год публикации - 2023)

7. Гао Цзинцзин, Парилина Е. М. Динамика мнений в мультиагентных системах с оптимальным выбором моментов проверки мнений Математическая теория игр и ее приложения, т. 14, в. 4, с.3-23 (год публикации - 2023)

8. Су Шимай, Парилина Е. М. Trade-Off Mechanism to Sustain Cooperation in Pollution Reduction Lecture Notes in Computer Science, LNCS 13930, pp. 300–313, 2023 (год публикации - 2023)
10.1007/978-3-031-35305-5_21

9. Парилина Е. М., Заккур Дж. Payment schemes for sustaining cooperation in dynamic games played over event trees European Journal of Operational Research, 313 (2024) 1200–1216 (год публикации - 2024)
10.1016/j.ejor.2023.10.016

10. Мазалов В. В., Реттиева А. Н. Применение арбитражных схем для определения равновесий в динамических играх Математическая теория игр и ее приложения, т. 15, в. 2, с.75-88 (год публикации - 2023)

11. Кочевадов В. А., Седаков А. А. Динамическая сетевая модель производства с инвестированием Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления, Т. 19, вып. 1 (год публикации - 2023)
10.21638/11701/spbu10.2023.102

12. Кочевадов В. А., Седаков А. А. Динамические модели конкуренции с эндогенным формированием сетевой структуры Математическая теория игр и ее приложения, т. 15, в. 2, с. 53-74 (год публикации - 2023)

13. Тур А. В., Петросян Л. А. Решение усредненного дерева в многоагентных системах с сетевой структурой Математическая теория игр и ее приложения, т. 15, в. 1, с.73-89 (год публикации - 2023)

14. Тур А., Петросян Л. Communication Restriction-Based Characteristic Function in Differential Games on Networks Lecture Notes in Computer Science, LNCS 13930, pp. 314–324, 2023. (год публикации - 2023)
10.1007/978-3-031-35305-5_22

15. Петросян Л. А., Панкратова Я. Б. Решения кооперативных дифференциальных игр с партнерскими множествами Математическая теория игр и ее приложения, т.15, в.2, с. 105–121 (год публикации - 2023)

Аннотация результатов, полученных в 2024 году
Впервые показано, что в дифференциальных сетевых играх со многими участниками и с предписанной продолжительностью первоначальная сеть, определяющая оптимальное с точки зрения получения суммарного выигрыша агентами (игроками) в какой-то промежуточный момент развития процесса взаимодействия, может быть перестать быть таковой, и потребуется пересмотр сети, определяющей взаимодействие агентов (игроков). Предложен новый способ кооперативного поведения, учитывающий возможность изменения сети и обеспечивающий больший суммарный выигрыш игроков. Проверена его динамическая устойчивость (временная состоятельность), что является важнейшим свойством оптимальных решений. В случае, когда агенты (игроки), связанные в сеть, демонстрируют различные формы поведения (кооперативное, индивидуально-рациональное, безразличное), предложен принцип оптимальности, учитывающий данную ситуацию, показана его реализуемость и временная состоятельность. В конкретных дифференциальных играх на сетях с попарным взаимодействием типа охраны окружающей среды и оптимального распределения ресурсов в явном виде построены характеристические функции, вычислены значения векторов Шэпли и Тау вектора, доказана непустота ядра и в ряде случаев его выпуклость. В задачах с возможностью изменения сетевой структуры во времени с целью повышения эффективности МАС построен субоптимальный способ кооперативного поведения, корректирующего в конечные моменты изменения сетевой структуры. В этих же задачах построен субоптимальный способ кооперативного поведения, являющийся композицией локально-оптимальных кооперативных поведений на интервалах постоянства сетевой структуры. Исследована возможность построения аналога характеристической функции и вектора Шепли для указанных выше двух субоптимальных способах кооперативного поведения. Предложена математическая модель МАС со сложной сетевой структурой, в которой агенты связаны многоуровневой сетью, где они могут создавать или удалять связи на любом из уровней. Функции полезностей агентов заданы в общем и частных формах, которые отражают многоуровневость связей игроков. Рассмотрены различные подходы к определению устойчивых многоуровневых сетей, получены условия, гарантирующие устойчивость некоторых специальных многоуровневых сетей, включая звезду, полный граф и структуры, одинаковые на каждом уровне. В качестве примера простой МАС рассмотрена модель конечно повторяющейся игры типа «Дилемма заключенного». Для поддержания кооперации предлагается новый класс стратегий агентов таких, что отклонение игроков наказывается не до конца игры, а на период заданной продолжительности в зависимости от шага игры. Доказано существование приближенного равновесия в данных стратегиях, и найдено максимальное значение выигрыша агента при отклонении от данной ситуации приближенного равновесия. Разработана обобщенная модель динамики мнений в МАС, названная обобщенная модель скрытого избирателя (GCVM). Модель применима для любой двухслойной сети (с внутренним и внешним слоями). Проведена серия численных экспериментов с различными сетевыми структурами и получены результаты о взаимосвязи времени достижения консенсуса и вероятности победы определенного мнения от количественных характеристик сети. Также проведена серия численных экспериментов для наблюдения за тем, как динамика мнений зависит от структуры внутреннего слоя. Предложена математическая модель взаимодействия между странами или компаниями, загрязняющими общий регион, когда страны по-разному относятся к проблеме охраны окружающей среды. Рассмотрены все возможные сценарии кооперации или ее отсутствие. Сформулированы условия устойчивости всех возможных коалиционных структур. В случае, когда структура или сценарий не являются устойчивыми, предложено несколько способов создания устойчивой коалиционной структуры. Предложенные подходы могут быть основаны на трансферных платежах, ограничениях на формирование коалиций и введении дополнительных издержек при переходе игроков из одной коалиции в другую. В качестве примера МАС, функционирующей в экономической среде в присутствии неопределенности, рассмотрена система фирм, конкурирующих на рынке при неизвестном предложении. Агенты или фирмы (ритейлеры) принимают свои решения о продажах и заказах товаров в условиях неопределенности в параметрах спроса и предложения. Модель описывается игрой, разыгрываемой на дереве событий. Найдено нормализованное равновесие для данной игры, описана двухэтапная процедура поиска этого равновесия, получены необходимые условия равновесия и исследованы различные сценарии неопределенности в МАС с помощью численного моделирования. Разработаны методы управления многоагентными динамическими системами, находящимися под влиянием нескольких несимметричных участников с собственными интересами, выраженными векторными функциями выигрыша. Кооперативное и некооперативное поведение агентов получены в динамических бикритериальных моделях управления ресурсами. Для поддержания кооперативного поведения использована концепция регулируемого равновесия, где контроль над соблюдением кооперативного договора является стратегией центра. В многокритериальной динамической задаче управления ресурсами показано, что при применении предложенного подхода наказание отклоняющих от кооперативного договора участников линейно зависит от величины отклонения. Предложена новая концепция динамически стабильных по Нэшу коалиционных разбиений в динамических играх, которая определяется с использованием процедуры распределения дележа в кооперативной динамической игре.

Публикации

1. Су Ш. Парилина Е. DESIGNING STABLE COALITION STRUCTURES FOR INTERNATIONAL ENVIRONMENTAL AGREEMENTS Journal of Dynamics and Games, 2024, Volume 11, Issue 2: 197-217 (год публикации - 2024)
10.3934/jdg.2024004

2. Алёна М. Писарева, Елена М. Парилина Приближенное равновесие в конечно повротяющейся игре "Дилемма заключенного" Математическая теория игр и ее приложения, МТИП, 2024, том 16, выпуск 2, 45–65 (год публикации - 2024)

3. Чжоу Ц., Мазалов В. Dynamic Stability of Coalition Structures in Network-Based Pollution Control Games Lecture Notes in Computer Science, MOTOR 2024, LNCS 14766, pp. 315–333, 2024. (год публикации - 2024)
10.1007/978-3-031-62792-7_22

4. Мазалов В., Чжоу Ц. Dynamic stability of coalition formation in dynamic games Operations Research Letters, 55(2024)107138 (год публикации - 2024)
10.1016/j.orl.2024.107138

5. Парилина Е., Врачек С., Заккур Дж. Dynamic Oligopolistic Competition with Uncertainty and Supply Disruption Effects International Game Theory Review, (2024) 2440009 (год публикации - 2024)
10.1142/S0219198924400097

6. Ндиайе С. М., Парилина Е. М. A Coalitional Differential Game of Vaccine Producers Automation and Remote Control, 85, 200–212 (2024) (год публикации - 2024)
10.1134/S0005117924020073

7. Мазалов В. В., Реттиева А. Н. Application of Bargaining Schemes for Equilibrium Determination in Dynamic Games Doklady Mathematics, 2023, Vol. 108, Suppl. 1, pp. S133–S138 (год публикации - 2024)
10.1134/S1064562423600677

8. Чжао Ч., Парилина Е. Network structure properties and opinion dynamics in two-layer networks with hypocrisy Lecture Notes in Computer Science, vol 14766. Springer, Cham (год публикации - 2024)
10.1007/978-3-031-62792-7_21

9. Кочевадов В. А., Седаков А. А. Dynamic Models of Competition with Endogenous Network Formation Doklady Mathematics, Volume 108, pages S56–S65, (2023) (год публикации - 2024)
10.1134/S1064562423600756

10. Хе Я., Петросян Л. А. A note on cooperative differential games with pairwise interactions Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления, 2024. Т. 20. Вып. 1 (год публикации - 2024)
10.21638/11701/spbu10.2024.108

11. Чжао Ч., Парилина Е. Analysis of consensus time and winning rate in two-layer networks with hypocrisy of different structures Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления, 2024. Т. 20. Вып. 2 (год публикации - 2024)
10.21638/spbu10.2024.204

12. Петросян Л. А., Панкратова Я. Б. Differential Network Games with Different Types of Players Behavior Lecture Notes in Computer Science, Lecture Notes in Computer Science, vol 14766. Springer (год публикации - 2024)
10.1007/978-3-031-62792-7_20

13. Ма Ц., Парилина Е. Stable multiplex networks: definitions and characterizations Journal of Complex Networks, 2024, 5, 1–24 (год публикации - 2024)
10.1093/comnet/cnae040

14. Петросян Л., Тур А. DIFFERENTIAL GAMES WITH ADDITIVE PAYOFFS International Game Theory Review, Vol. 26, No. 02, 2440010 (2024) (год публикации - 2024)
10.1142/S0219198924400103

15. Реттиева А. Н. Кооперативные многокритериальные динамические игры: применение в транспортных задачах Математическая теория игр и ее приложения, т.16, в.3, с. 58–76 (год публикации - 2024)

16. Тур А. В. C-ядро в дифференциальных играх на сетях с коммуникационными ограничениями Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления, 2023. Т. 19. Вып. 4 (год публикации - 2023)
10.21638/11701/spbu10.2023.406

17. Тур А. В., Петросян Л. А. Average Tree Solution in Multi-Agent Systems with Network Structure Doklady Mathematics, Dokl. Math. 108 (Suppl 1), S100–S106 (2023) (год публикации - 2024)
10.1134/S1064562423600707

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