MSC: 91A23, 91A12, 91A43
DOI: 10.21538/0134-4889-2023-29-3-128-137
Supported by the Russian Science Foundation (grant no. 22-11-00051), https://rscf.ru/en/project/22-11-00051/.
Полный текст статьи (Full text)
Dynamic multi-agent systems connected in network are considered. To define the power of each agent the analogue of characteristic function is introduced. The values of this characteristic function for each coalition (subset of agents) are calculated as joint payoff of players from this coalition plus payoffs (multiplied on some discount factor) of players which do not belong to the coalition $S$ but have connections with players from $S$. We suppose that the dynamic of the system is prescribed (this maybe cooperation, Nash equilibrium or any other behaviour). Thus, the characteristic function is evaluated along the prescribed trajectory of agents. And it measures the worth of coalitions under the motion along this trajectory instead of under minimax confrontation or the Nash non-cooperative stance. As solution we consider the proportional solution and introduce Power degrees of an agent based on proportional solution. It is shown that the Power degree (PD) belongs to the Core. PD rank agents according to their importance.
Keywords: multi-agent system and proportional solution and power degree
REFERENCES
1. Wie B.W. A differential game approach to the dynamic mixed behavior traffic network equilibrium problem. Eur. J. Oper. Res., 1995, vol. 83, no. 1, pp. 117–136. doi: 10.1002/net.3230230606
2. Pai H.M. A differential game formulation of a controlled network. Queueing SY., 2010, vol. 64, no. 4, pp. 325–358.
3. Meza M.A.G., Lopez-Barrientos J.D. A differential game of a duopoly with network externalities. In: eds. L. Petrosyan, V. Mazalov. Recent Advances in Game Theory and Applications, Ser. Static & Dynamic Game Theory: Foundations & Applications, pp. 49–66. Cham: Birkhäuser, 2016. doi: 10.1007/978-3-319-43838-2
4. Bulgakova M., Petrosyan L. About one multistage non-antagonistic network game, Vestnik S.-Petersburg Univ., Ser. 10. Prikl. Mat. Inform. Prots. Upr., 2019, vol. 5, no. 4, pp. 603–615 (in Russian). doi: 10.21638/11702/spbu10.2019.415
5. Wie B.W. A differential game model of Nash equilibrium on a congested traffic network. Networks, 1993, vol. 23, pp. 557–565.
6. Petrosyan L.A. Cooperative differential games on networks. Trudy Inst. Mat. Mekh. UrO RAN, 2010, vol. 16, no. 5, pp. 143–150 (in Russian).
7. Petrosyan L.A., Yeung D.W.K. Shapley value for differential network games: Theory and application. Journal of Dynamics and Games, vol. 8, no. 2, 2020, pp. 151–166. doi: 10.3934/jdg.2020021
8. Tur A., Petrosyan L. The core of cooperative differential games on networks. In: eds. P. Pardalos, M. Khachay, V. Mazalov. Mathematical Optimization Theory and Operations Research (MOTOR 2022), Ser. Lecture Notes Comp. Sci., vol. 13367, Cham: Springer, 2022. doi: 10.1007/978-3-031-09607-5_21
9. Petrosyan L., Pankratova Y. Owen value for dynamic games on networks. In: eds. Leon A. Petrosyan, Nickolay A. Zenkevich.Contributions to Game Theory and Management, 2022, vol. 15, pp. 218–225. doi: 10.21638/11701/spbu31.2022.16
10. Yeung D.W.K. Time consistent Shapley value imputation for cost-saving joint ventures. Mat. Teor. Igr Pril., 2010, vol. 2, no. 3, pp. 137–149.
11. Petrosyan L., Yeung D.W.K., Pankratova Y. Cooperative differential games with partner sets on networks. Trudy Inst. Mat. Mekh. UrO RAN, 2021, vol. 27, no. 3, pp. 286–295. doi: 10.21538/0134-4889-2021-27-3-286-295
12. Petrosyan L., Yeung D.W.K., Pankratova Y. Dynamic cooperative games on networks. In: eds. A. Strekalovsky, Y. Kochetov, T. Gruzdeva and A. Orlov. Mathematical Optimization Theory and Operations Research: Recent Trends (20th Internat. Conf. MOTOR 2021), Berlin: Springer Nature, 2021, pp. 403-416. doi: 10.1007/978-3-030-86433-0_28
13. Cao H., Ertin E., Arora A. MiniMax equilibrium of networked differential games. ACM TAAS, 1963, vol. 3, no. 4. doi: 10.1145/1452001.1452004
14. Mazalov V., Chirkova J. Networking games. Network forming games and games on networks. 1st edn. Amsterdam: Elsevier Inc., 2019. doi: 10.1016/C2017-0-04296-9
15. Shapley L.S. A value for N-person games. In: eds. H. Kuhn, A. Tucker. Contributions to the theory of games. Princeton: Princeton University Press, 1953, pp. 307–317.
Received April 14, 2023
Revised June 7, 2023
Accepted June 12, 2023
Funding Agency: This work was supported by the Russian Science Foundation, grant no. 22-11-00051, https://rscf.ru/en/project/22-11-00051/.
Leon Aganesovich Petrosyan, Dr. Phys.-Math. Sci., Prof., Saint Petersburg State University, St. Petersburg, 199034 Russia, e-mail: l.petrosyan@spbu.ru
David W.K. Yeung, Prof. Dr. Dr.h.c., Hong Kong Shue Yan University, Hong Kong, China, e-mail: dwkyeung@hksyu.edu
Yaroslavna Borisovna Pankratova, Cand. Sci. (Phys.-Math.), Saint Petersburg University, St. Petersburg, 199034 Russia, e-mail: y.pankratova@spbu.ru
Cite this article as: L.A. Petrosyan, D. Yeung, Y.B. Pankratоva. Power Degrees in Dynamic Multi-Agent Systems. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 128–137.
Русский
Л.А. Петросян, Д.В.К. Янг, Я.Б. Панкратова. Индекс значимости в динамических многоагентных системах
Рассматриваются динамические мультиагентные системы на сети. Для определения силы игрока вводится аналог характеристической функции. Значения этой характеристической функции для каждой коалиции (подмножества агентов) рассчитываются как совместный выигрыш игроков (агентов) из этой коалиции при движении вдоль предписанной заранее траектории плюс выигрыши, умноженные на некоторый коэффициент дисконтирования, игроков (агентов), которые не принадлежат коалиции S, но имеют связи с игроками из S. Предполагается, что динамика системы предписана заранее (это может быть кооперативной поведение, движение в равновесии по Нэшу, или какой либо другое движение). Характеристическая функция, вычисляемая вдоль предписанной траектории агентов, измеряет значимость коалиций при движении вдоль этой траектории, а не в условиях минимаксного подхода или равновесия по Нэшу. В качестве решения мы рассматриваем пропорциональное решение и вводим понятие индекса значимости агента, основанное на пропорциональном решении. Вектор, составленный из индексов значимости, ранжирует агентов в соответствии с их важностью. Показано, что вектор, составленный из индексов значимости агентов, принадлежит C-ядру. Исследуется вопрос устойчивости ранжирования агентов при развитии мультиагентной системы вдоль предписанной траектории.
Ключевые слова: мультиагентная система, пропорциональное решение и индекс значимости
