Journal Home > Volume 1 , Issue 1
CAAI Artificial Intelligence Research 2022, 1(1): 8-27 https://doi.org/10.26599/AIR.2022.9150002
Open Access | Issue | Published: 28 August 2022

A Survey on Noncooperative Games and Distributed Nash Equilibrium Seeking over Multi-Agent Networks

Show Author's Information Peng Yi1,2,  Jinlong Lei1,2( ),  Xiuxian Li1,2,  Shu Liang1,2,  Min Meng1,2,  Jie Chen1,2
Department of Control Science and Engineering, Tongji University, Shanghai 201804, China
Shanghai Research Institute for Intelligent Autonomous Systems, Shanghai 201210, China
Keywords:
noncooperative games, multi-agent systems, optimization and decision making, cyber-physical systems, Nash equilibrium, distributed computation
Cite this article:
Yi P, Lei J, Li X, et al. A Survey on Noncooperative Games and Distributed Nash Equilibrium Seeking over Multi-Agent Networks. CAAI Artificial Intelligence Research, 2022, 1(1): 8-27. https://doi.org/10.26599/AIR.2022.9150002
Download citation
EndNote(RIS)
BibTeX

1125

Views

369

Downloads

Citations

0

Crossref

N/A

WoS

N/A

Scopus

N/A

CSCD

Abstract Full text About this article

The work gives a review on the distributed Nash equilibrium seeking of noncooperative games in multi-agent networks, which emerges as one of the frontier research topics in the area of systems and control community. Firstly, we give the basic formulation and analysis of noncooperative games with continuous action spaces, and provide the motivation and basic setting for distributed Nash equilibrium seeking. Then we introduce both the gradient-based algorithms and best-response based algorithms for various type of games, including zero-sum games, aggregative games, potential games, monotone games, and multi-cluster games. In addition, we provide some applications of noncooperative games.


menu
Abstract
Full text
Outline
About this article

A Survey on Noncooperative Games and Distributed Nash Equilibrium Seeking over Multi-Agent Networks

Show Author's information Peng Yi1,2, Jinlong Lei1,2( ), Xiuxian Li1,2, Shu Liang1,2, Min Meng1,2, Jie Chen1,2
Department of Control Science and Engineering, Tongji University, Shanghai 201804, China
Shanghai Research Institute for Intelligent Autonomous Systems, Shanghai 201210, China

Abstract

The work gives a review on the distributed Nash equilibrium seeking of noncooperative games in multi-agent networks, which emerges as one of the frontier research topics in the area of systems and control community. Firstly, we give the basic formulation and analysis of noncooperative games with continuous action spaces, and provide the motivation and basic setting for distributed Nash equilibrium seeking. Then we introduce both the gradient-based algorithms and best-response based algorithms for various type of games, including zero-sum games, aggregative games, potential games, monotone games, and multi-cluster games. In addition, we provide some applications of noncooperative games.

Keywords: noncooperative games, multi-agent systems, optimization and decision making, cyber-physical systems, Nash equilibrium, distributed computation

References(184)

1

A. Nedić and J. Liu, Distributed optimization for control, Annu. Rev. Control Robot. Auton. Syst., vol. 1, pp. 77–103, 2018.
DOI Google Scholar
2

T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson, A survey of distributed optimization, Annu. Rev. Control, vol. 47, pp. 278–305, 2019.
DOI Google Scholar
3

G. Notarstefano, I. Notarnicola, and A. Camisa, Distributed optimization for smart cyber-physical networks, Found. Trends Syst. Control, vol. 7, no. 3, pp. 253–383, 2019.
DOI Google Scholar
4

R. Xin, S. Pu, A. Nedić, and U. A. Khan, A general framework for decentralized optimization with first-order methods, Proc. IEEE, vol. 108, no. 11, pp. 1869–1889, 2020.
DOI Google Scholar
5
B. Yang and M. Johansson, Distributed optimization and games: A tutorial overview, in Networked Control Systems, A. Bemporad, M. Heemels, and M. Johansson, eds. London, UK: Springer, 2010, pp. 109−148.
DOI
6

P. Yi and Y. G. Hong, Distributed cooperative optimization and its applications, (in Chinese), Sci. Sinica Math., vol. 46, no. 10, pp. 1547–1564, 2016.
Google Scholar
7

Y. Chen, S. Mei, F. Zhou, S. H. Low, W. Wei, and F. Liu, An energy sharing game with generalized demand bidding: Model and properties, IEEE Trans. Smart Grid, vol. 11, no. 3, pp. 2055–2066, 2020.
DOI Google Scholar
8

W. Wei, L. Wu, J. Wang, and S. Mei, Network equilibrium of coupled transportation and power distribution systems, IEEE Trans. Smart Grid, vol. 9, no. 6, pp. 6764–6779, 2018.
DOI Google Scholar
9
M. Wang, N. Mehr, A. Gaidon, and M. Schwager, Game-theoretic planning for risk-aware interactive agents, in Proc. 2020 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, Las Vegas, NV, USA, 2020, pp. 6998−7005.
DOI
10

A. Zanardi, G. Zardini, S. Srinivasan, S. Bolognani, A. Censi, F. Dörfler, and E. Frazzoli, Posetal games: Efficiency. existence.and refinement of equilibria in games with prioritized metrics, IEEE Robot. Autom. Lett., vol. 7, no. 2, pp. 1292–1299, 2022.
DOI Google Scholar
11
F. Laine, D. Fridovich-Keil, C. Y. Chiu, and C. Tomlin, Multi-hypothesis interactions in game-theoretic motion planning, in Proc. 2021 IEEE Int. Conf. on Robotics and Automation, Xi'an, China, 2021, pp. 8016−8023.
DOI
12

M. H. Manshaei, Q. Zhu, T. Alpcan, T. Bacşar, and J. P. Hubaux, Game theory meets network security and privacy, ACM Comput. Surv., vol. 45, no. 3, p. 25, 2013.
DOI Google Scholar
13

Q. Zhu and T. Basar, Game-theoretic methods for robustness, security, and resilience of cyberphysical control systems: Games-in-games principle for optimal cross-layer resilient control systems, IEEE Control Syst., vol. 35, no. 1, pp. 46–65, 2015.
DOI Google Scholar
14
F. Farnia and A. Ozdaglar, Do GANs always have Nash equilibria? in Proc. 37th Int. Conf. on Machine Learning, 2020, pp. 3029−3039.
15

S. Nardi, F. Mazzitelli, and L. Pallottino, A game theoretic robotic team coordination protocol for intruder herding, IEEE Robot. Autom. Lett., vol. 3, no. 4, pp. 4124–4131, 2018.
DOI Google Scholar
16

D. Shishika, J. Paulos, and V. Kumar, Cooperative team strategies for multi-player perimeter-defense games, IEEE Robot. Autom. Lett., vol. 5, no. 2, pp. 2738–2745, 2020.
DOI Google Scholar
17
R. Vidal, S. Rashid, C. Sharp, O. Shakernia, J. Kim, and S. Sastry, Pursuit-evasion games with unmanned ground and aerial vehicles, in Proc. 2001 ICRA. IEEE Int. Conf. on Robotics and Automation, Seoul, Republic of Korea, 2001, pp. 2948−2955.
18
J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior. Princeton, NJ, USA: Princeton University Press, 1944.
19
T. Başar and G. J. Olsder, Dynamic Noncooperative Game Theory. Philadelphia, PA, USA: SIAM, 1999.
DOI
20

I. Menache and A. Ozdaglar, Network games: Theory, models, and dynamics, Synth. Lect. Commun. Networks, vol. 4, no. 1, pp. 1–159, 2011.
DOI Google Scholar
21
L. Pavel, Game Theory for Control of Optical Networks. Boston, MA, USA: Springer, 2012.
DOI
22
S. W. Mei, F. Liu, and W. Wei, Foundations of Engineering Game Theory and its Applications in Power Systems, (in Chinese). Beijing, China: Science Press, 2016.
23

G. Chalkiadakis, E. Elkind, and M. Wooldridge, Computational aspects of cooperative game theory, Synth. Lect. Artif. Intell. Mach. Learn., vol. 5, no. 6, pp. 1–168, 2011.
DOI Google Scholar
24
R. Branzei, D. Dimitrov, and S. Tijs, Models in Cooperative Game Theory. 2nd ed. Berlin, Germany: Springer, 2008.
25

F. Fele, J. M. Maestre, and E. F. Camacho, Coalitional control: Cooperative game theory and control, IEEE Control Syst. Mag., vol. 37, no. 1, pp. 53–69, 2017.
DOI Google Scholar
26

A. Nedić and D. Bauso, Dynamic coalitional TU games: Distributed bargaining among players' neighbors, IEEE Trans. Autom. Control, vol. 58, no. 6, pp. 1363–1376, 2013.
DOI Google Scholar
27

I. Alvarez, V. Alexander, and S. Poznyak, Urban traffic control via Stackelber-Nash equilibria, IFAC Proc. Vol., vol. 42, no. 15, pp. 582–587, 2009.
DOI Google Scholar
28
U. O. Candogan, I. Menache, A. Ozdaglar, and P. A. Parrilo, Near-optimal power control in wireless networks: A potential game approach, in Proc. 2010 IEEE INFOCOM, San Diego, CA, USA, 2010, pp. 1−9.
DOI
29

N. B. Mandayam, S. B. Wicker, J. Walrand, T. Basar, J. W. Huang, and D. P. Palomar, Game theory in communication systems [guest editorial], IEEE J. Sel. Areas Commun., vol. 26, no. 7, pp. 1042–1046, 2008.
DOI Google Scholar
30

A. Attar, T. Basar, M. Debbah, H. V. Poor, and Q. Zhao, Guest editorial game theory in wireless communications, IEEE J. Sel. Areas Commun., vol. 30, no. 1, pp. 1–3, 2012.
DOI Google Scholar
31

H. Sandberg, S. Amin, and K. H. Johansson, Cyberphysical security in networked control systems: An introduction to the issue, IEEE Control Syst. Mag., vol. 35, no. 1, pp. 20–23, 2015.
DOI Google Scholar
32

J. F. Nash Jr, Equilibrium points in n-person games, Proc. Natl Acad. Sci. USA, vol. 36, no. 1, pp. 48–49, 1950.
DOI Google Scholar
33

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems, Ann. Oper. Res., vol. 175, no. 1, pp. 177–211, 2010.
DOI Google Scholar
34

Y. Nesterov, Stable traffic equilibria: Properties and applications, Optim. Eng., vol. 1, no. 1, pp. 29–50, 2000.
DOI Google Scholar
35

A. Kannan, U. V. Shanbhag, and H. M. Kim, Addressing supply-side risk in uncertain power markets: Stochastic Nash models, scalable algorithms and error analysis, Optim. Methods Software, vol. 28, no. 5, pp. 1095–1138, 2013.
DOI Google Scholar
36

J. S. Pang, G. Scutari, D. P. Palomar, and F. Facchinei, Design of cognitive radio systems under temperature-interference constraints: A variational inequality approach, IEEE Trans. Signal Process., vol. 58, no. 6, pp. 3251–3271, 2010.
DOI Google Scholar
37
T. Alpcan and T. Basar, A game-theoretic framework for congestion control in general topology networks, in Proc. 41st IEEE Conf. on Decision and Control, 2002, Las Vegas, NV, USA, 2002, pp. 1218−1224.
38
D. Fudenberg and D. K. Levine, The Theory of Learning in Games. Cambridge, MA, USA: MIT Press, 1998.
39
N. Nisan, M. Schapira, G. Valiant, and A. Zohar, Best response mechanisms, in Proc. Conf. on Innovations in Computer Science, Beijing, China, 2011, pp. 155−165.
DOI
40
D. P. Palomar and Y. C. Eldar, Convex Optimization in Signal Processing and Communications. Cambridge, UK: Cambridge University Press, 2010.
DOI
41
F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems. New York, NY, USA: Springer, 2003.
DOI
42

D. Monderer and L. S. Shapley, Fictitious play property for games with identical interests, J. Econ. Theory, vol. 68, no. 1, pp. 258–265, 1996.
DOI Google Scholar
43
J. Chen, H. Fang, and B. Xin, Cooperative Cluster Motion Control for Multi-Agent Systems, (in Chinese). Beijing, China: Science Press, 2017.
44
M. Zhu and S. Martínez, Distributed Optimization-Based Control of Multi-Agent Networks in Complex Environments. Cham, Switzerland: Springer, 2015.
DOI
45

Y. Lou, Y. Hong, L. Xie, G. Shi, and K. H. Johansson, Nash equilibrium computation in subnetwork zero-sum games with switching communications, IEEE Trans. Autom. Control, vol. 61, no. 10, pp. 2920–2935, 2016.
DOI Google Scholar
46

S. Grammatico, F. Parise, M. Colombino, and J. Lygeros, Decentralized convergence to Nash equilibria in constrained deterministic mean field control, IEEE Trans. Autom. Control, vol. 61, no. 11, pp. 3315–3329, 2016.
DOI Google Scholar
47

J. Koshal, A. Nedić, and U. V. Shanbhag, Distributed algorithms for aggregative games on graphs, Oper. Res., vol. 64, no. 3, pp. 680–704, 2016.
DOI Google Scholar
48

F. Salehisadaghiani and L. Pavel, Distributed Nash equilibrium seeking: A gossip-based algorithm, Automatica, vol. 72, pp. 209–216, 2016.
DOI Google Scholar
49

M. Ye and G. Hu, Game design and analysis for price-based demand response: An aggregate game approach, IEEE Trans. Cybern., vol. 47, no. 3, pp. 720–730, 2017.
DOI Google Scholar
50

M. Ye and G. Hu, Distributed Nash equilibrium seeking by a consensus based approach, IEEE Trans. Autom. Control, vol. 62, no. 9, pp. 4811–4818, 2017.
DOI Google Scholar
51

S. Liang, P. Yi, and Y. Hong, Distributed Nash equilibrium seeking for aggregative games with coupled constraints, Automatica, vol. 85, pp. 179–185, 2017.
DOI Google Scholar
52

P. Yi and L. Pavel, Distributed generalized Nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms, IEEE Trans. Control Network Syst., vol. 6, no. 1, pp. 299–311, 2019.
DOI Google Scholar
53

K. Lu, G. Jing, and L. Wang, Distributed algorithms for searching generalized Nash equilibrium of noncooperative games, IEEE Trans. Cybern., vol. 49, no. 6, pp. 2362–2371, 2019.
DOI Google Scholar
54

J. Lei and U. V. Shanbhag, Distributed variable sample-size gradient-response and best-response schemes for stochastic Nash equilibrium problems, SIAM J. Optim., vol. 32, no. 2, pp. 573–603, 2022.
DOI Google Scholar
55

W. Liu, W. Gu, J. Wang, W. Yu, and X. Xi, Game theoretic non-cooperative distributed coordination control for multi-microgrids, IEEE Trans. Smart Grid, vol. 9, no. 6, pp. 6986–6997, 2018.
DOI Google Scholar
56

T. Tatarenko, W. Shi, and A. Nedić, Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking, IEEE Trans. Autom. Control, vol. 66, no. 11, pp. 5342–5353, 2021.
DOI Google Scholar
57

D. Paccagnan, B. Gentile, F. Parise, M. Kamgarpour, and J. Lygeros, Nash and wardrop equilibria in aggregative games with coupling constraints, IEEE Trans. Autom. Control, vol. 64, no. 4, pp. 1373–1388, 2019.
DOI Google Scholar
58

P. Yi and L. Pavel, An operator splitting approach for distributed generalized Nash equilibria computation, Automatica, vol. 102, pp. 111–121, 2019.
DOI Google Scholar
59
Z. Li and Z. Ding, Distributed Nash equilibrium searching via fixed-time consensus-based algorithms, in Proc. 2019 American Control Conf., Philadelphia, PA, USA, 2019, pp. 2765−2770.
DOI
60

F. Salehisadaghiani, W. Shi, and L. Pavel, Distributed Nash equilibrium seeking under partial-decision information via the alternating direction method of multipliers, Automatica, vol. 103, pp. 27–35, 2019.
DOI Google Scholar
61

C. X. Shi and G. H. Yang, Distributed Nash equilibrium computation in aggregative games: An event-triggered algorithm, Inf. Sci., vol. 489, pp. 289–302, 2019.
DOI Google Scholar
62

Z. Deng and S. Liang, Distributed algorithms for aggregative games of multiple heterogeneous Euler-Lagrange systems, Automatica, vol. 99, pp. 246–252, 2019.
DOI Google Scholar
63
D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA, USA: MIT Press, 1991, pp. 80.
64
W. Y. Zhang, Game Theory and Information Economics, (in Chinese). Shanghai, China: Shanghai People's Publishing House, 2004.
65

T. Basar, Control and game-theoretic tools for communication networks, Appl. Comput. Math., vol. 6, no. 2, pp. 104–125, 2007.
Google Scholar
66

H. Yin, U. V. Shanbhag, and P. G. Mehta, Nash equilibrium problems with scaled congestion costs and shared constraints, IEEE Trans. Autom. Control, vol. 56, no. 7, pp. 1702–1708, 2011.
DOI Google Scholar
67

D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, and T. Graepel, et al., A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, vol. 362, no. 6419, pp. 1140–1144, 2018.
DOI Google Scholar
68

N. Brown and T. Sandholm, Superhuman AI for multiplayer poker, Science, vol. 365, no. 6456, pp. 885–890, 2019.
DOI Google Scholar
69
M. Kearns, M. L. Littman, and S. Singh, Graphical models for game theory. arXiv preprint arXiv: 1301.2281, 2013.
70

A. Fischer, M. Herrich, and K. Schönefeld, Generalized Nash equilibrium problems-recent advances and challenges, Pesq. Oper., vol. 34, no. 3, pp. 521–558, 2014.
DOI Google Scholar
71
F. Parise, S. Grammatico, B. Gentile, and J. Lygeros, Network aggregative games and distributed mean field control via consensus theory, arXiv preprint arXiv: 1506.07719, 2015.
72

B. Swenson, R. Murray, and S. Kar, On best-response dynamics in potential games, SIAM J. Control Optim., vol. 56, no. 4, pp. 2734–2767, 2018.
DOI Google Scholar
73
F. Facchinei and J. S. Pang, Nash equilibria: The variational approach, in Convex Optimization in Signal Processing and Communications, D. Palomar, and Y. Eldar, eds. Cambridge, UK: Cambridge University Press, 2009, pp. 443−493.
DOI
74

G. Scutari, D. P. Palomar, F. Facchinei, and J. S. Pang, Convex optimization, game theory, and variational inequality theory, IEEE Signal Process. Mag., vol. 27, no. 3, pp. 35–49, 2010.
DOI Google Scholar
75

F. Facchinei, A. Fischer, and V. Piccialli, On generalized Nash games and variational inequalities, Oper. Res. Lett., vol. 35, no. 2, pp. 159–164, 2007.
DOI Google Scholar
76

A. Dreves, F. Facchinei, C. Kanzow, and S. Sagratella, On the solution of the KKT conditions of generalized Nash equilibrium problems, SIAM J. Optim., vol. 21, no. 3, pp. 1082–1108, 2011.
DOI Google Scholar
77

J. S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Comput, Comput. Manage. Sci., vol. 2, no. 1, pp. 21–56, 2005.
DOI Google Scholar
78

F. Parise and A. Ozdaglar, A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis, Games Econ. Behav., vol. 114, pp. 47–82, 2019.
DOI Google Scholar
79

G. Gürkan and J. S. Pang, Approximations of Nash equilibria, Math. Program, vol. 223, no. 1−2, pp. 117–253, 2009.
DOI Google Scholar
80

S. Li and T. Başar, Distributed algorithms for the computation of noncooperative equilibria, Automatica, vol. 23, no. 4, pp. 523–533, 1987.
DOI Google Scholar
81

M. Zhu and E. Frazzoli, Distributed robust adaptive equilibrium computation for generalized convex games, Automatica, vol. 63, pp. 82–91, 2016.
DOI Google Scholar
82

G. Belgioioso and S. Grammatico, Semi-decentralized Nash equilibrium seeking in aggregative games with separable coupling constraints and non-differentiable cost functions, IEEE Control Syst. Lett., vol. 1, no. 2, pp. 400–405, 2017.
DOI Google Scholar
83
G. W. Brown, Activity analysis of production and allocation, in Iterative Solutions of Games by Fictitious Play, T. C. Koopmans, Ed. New York, NY, USA: Wiley, 1951, pp. 374−376.
84

F. Facchinei, V. Piccialli, and M. Sciandrone, Decomposition algorithms for generalized potential games, Comput. Optim. Appl., vol. 50, no. 2, pp. 237–262, 2011.
DOI Google Scholar
85
J. von Neumann, Zur theorie der Gesellschaftsspiele, (in German), Math. Ann., vol. 100, no. 1, pp. 295−320, 1928.
DOI
86

B. Gharesifard and J. Cortés, Distributed convergence to Nash equilibria in two-network zero-sum games, Automatica, vol. 49, no. 6, pp. 1683–1692, 2013.
DOI Google Scholar
87
Y. Xiao, X. Hou, and J. Hu, Distributed solutions of convex-concave games on networks, in Proc. 2019 American Control Conf., Philadelphia, PA, USA, 2019, pp. 1189−1194.
DOI
88
S. Huang, J. Lei, Y. Hong, U. V. Shanbhag, and J. Chen, No-regret distributed learning in subnetwork zero-sum games, arXiv preprint arXiv: 2108.02144, 2021.
DOI
89

J. Hofbauer and S. Sorin, Best response dynamics for continuous zero-sum games, Discrete Contin. Dyn. Syst. Ser. B, vol. 6, no. 1, pp. 215–224, 2006.
DOI Google Scholar
90
R. Selten and C. C. Berg, Experimentelle oligopolspielserien mit kontinuierlichem zeitablauf, in Beiträge zur experimentellen Wirtschaftsforschung, H. Sauermann, ed. Tübingen, Germany: J. C. B. Mohr, 1970, pp. 162−221.
91

J. Ghaderi and R. Srikant, Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate, Automatica, vol. 50, no. 12, pp. 3209–3215, 2014.
DOI Google Scholar
92

M. Y. Huang, P. E. Caines, and R. P. Malhamé, Large-population cost-coupled LQG problems with nonuniform agents: Individual-mass behavior and decentralized ε-Nash equilibria, IEEE Trans. Autom. Control, vol. 52, no. 9, pp. 1560–1571, 2007.
DOI Google Scholar
93
P. E. Caines, Mean field games, in Encyclopedia of Systems and Control, J. Baillieul and T. Samad, eds. London, UK: Springer, 2019, pp. 706−712.
DOI
94
J. Lei and U. V. Shanbhag, Linearly convergent variable sample-size schemes for stochastic Nash games: Best-response schemes and distributed gradient-response schemes, in Proc. 2018 IEEE Conf. on Decision and Control, Miami, FL, USA, 2018, pp. 3547−3552.
DOI
95

R. Zhu, J. Zhang, K. You, and T. Basar, Asynchronous networked aggregative games, Automatica, vol. 136, p. 110054, 2022.
DOI Google Scholar
96
S. Huang, J. Lei, and Y. Hong, A linearly convergent distributed Nash equilibrium seeking algorithm for aggregative games, IEEE Trans. Autom. Control, doi: 10.1109/TAC.2022.3154356.
DOI
97
J. Lei, P. Yi, and L. Li, Distributed no-regret learning for stochastic aggregative games over networks, in Proc. 2021 40th Chinese Control Conf., Shanghai, China, 2021, pp. 7512−7519.
DOI
98
J. Lei, U. V. Shanbhag, and J. Chen, Distributed computation of Nash equilibria for monotone aggregative games via iterative regularization, in Proc. 2020 59th IEEE Conf. on Decision and Control, Jeju, Korea, 2020, pp. 2285−2290.
DOI
99

M. Ye, G. Hu, L. Xie, and S. Xu, Differentially private distributed Nash equilibrium seeking for aggregative games, IEEE Trans. Autom. Control, vol. 67, no. 5, pp. 2451–2458, 2022.
DOI Google Scholar
100
D. Paccagnan, M. Kamgarpour, and J. Lygeros, On aggregative and mean field games with applications to electricity markets, in Proc. 2016 European Control Conf., Aalborg, Denmark, 2016, pp. 196−201.
DOI
101

H. Kebriaei, S. J. Sadati-Savadkoohi, M. Shokri, and S. Grammatico, Multipopulation aggregative games: Equilibrium seeking via mean-field control and consensus, IEEE Trans. Autom. Control, vol. 66, no. 12, pp. 6011–6016, 2021.
DOI Google Scholar
102

Z. Deng and X. Nian, Distributed generalized Nash equilibrium seeking algorithm design for aggregative games over weight-balanced digraphs, IEEE Trans. Neural Networks Learn. Syst., vol. 30, no. 3, pp. 695–706, 2019.
DOI Google Scholar
103

Y. Zhang, S. Liang, X. Wang, and H. Ji, Distributed Nash equilibrium seeking for aggregative games with nonlinear dynamics under external disturbances, IEEE Trans. Cybern., vol. 50, no. 12, pp. 4876–4885, 2020.
DOI Google Scholar
104

D. Monderer and L. S. Shapley, Potential games, Games Econ. Behav., vol. 14, no. 1, pp. 124–143, 1996.
DOI Google Scholar
105

O. Candogan, A. Ozdaglar, and P. A. Parrilo, Near-potential games: Geometry and dynamics, ACM Trans. Econ. Comput., vol. 1, no. 2, p. 11, 2013.
DOI Google Scholar
106

N. Li and J. R. Marden, Designing games for distributed optimization, IEEE J. Sel. Top. Signal Process., vol. 7, no. 2, pp. 230–242, 2013.
DOI Google Scholar
107

F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, Rate control for communication networks: Shadow prices, proportional fairness and stability, J. Oper. Res. Soc., vol. 49, no. 3, pp. 237–252, 1998.
DOI Google Scholar
108

Y. Yang, F. Rubio, G. Scutari, and D. P. Palomar, Multi-portfolio optimization: A potential game approach, IEEE Trans. Signal Process., vol. 61, no. 22, pp. 5590–5602, 2013.
DOI Google Scholar
109

P. Yi, Y. Zhang, and Y. Hong, Potential game design for a class of distributed optimisation problems, J. Control Decis., vol. 1, no. 2, pp. 166–179, 2014.
DOI Google Scholar
110

J. Lei and U. V. Shanbhag, Asynchronous schemes for stochastic and misspecified potential games and nonconvex optimization, Oper. Res., vol. 68, no. 6, pp. 1742–1766, 2020.
DOI Google Scholar
111
X. Wang, N. Xiao, T. Wongpiromsarn, L. Xie, E. Frazzoli, and D. Rus, Distributed consensus in noncooperative congestion games: An application to road pricing, in Proc. 2013 10th IEEE Int. Conf. on Control and Automation, Hangzhou, China, 2013, pp. 1668−1673.
DOI
112

M. Ye and G. Hu, Solving potential games with dynamical constraint, IEEE Trans. Cybern., vol. 46, no. 5, pp. 1156–1164, 2016.
DOI Google Scholar
113

J. Zhang, W. Liang, B. Yang, H. Shi, K. Wang, and Q. Wang, A potential game approach for decentralized resource coordination in coexisting IWNs, IEEE Trans. Cognit. Commun. Netw., vol. 8, no. 2, pp. 1118–1130, 2022.
DOI Google Scholar
114

A. Kannan and U. V. Shanbhag, Distributed computation of equilibria in monotone Nash games via iterative regularization techniques, SIAM J. Optim., vol. 22, no. 4, pp. 1177–1205, 2012.
DOI Google Scholar
115
L. M. Briceno-Arias and P. L. Combettes, Monotone operator methods for Nash equilibria in non-potential games, in Computational and Analytical Mathematics, D. H. Bailey, H. H. Bauschke, P. Borwein, F. Garvan, M. Théra, J. D. Vanderwerff, H. Wolkowicz, Eds. New York, NY, USA: Springer, 2013, pp. 143−159.
DOI
116

G. Scutari, F. Facchinei, J. S. Pang, and D. P. Palomar, Real and complex monotone communication games, IEEE Trans. Inf. Theory, vol. 60, no. 7, pp. 4197–4231, 2014.
DOI Google Scholar
117

J. Koshal, A. Nedic, and U. V. Shanbhag, Regularized iterative stochastic approximation methods for stochastic variational inequality problems, IEEE Trans. Autom. Control, vol. 58, no. 3, pp. 594–609, 2013.
DOI Google Scholar
118

F. Yousefian, A. Nedić, and U. V. Shanbhag, Self-tuned stochastic approximation schemes for non-Lipschitzian stochastic multi-user optimization and Nash games, IEEE Trans. Autom. Control, vol. 61, no. 7, pp. 1753–1766, 2016.
DOI Google Scholar
119
J. R. Marden, Learning in Large-Scale Games and Cooperative Control. Los Angeles: University of California, 2007.
120
W. Shi and L. Pavel, LANA: An ADMM-like Nash equilibrium seeking algorithm in decentralized environment, in Proc. 2017 American Control Conf., Seattle, WA, USA, 2017, pp. 285−290.
DOI
121
J. Zhou, Y. Lv, and M. Ye, Appointed-time distributed Nash equilibrium seeking for networked games, in Proc. 2021 60th IEEE Conf. on Decision and Control, Austin, TX, USA, 2021, pp. 203−208.
DOI
122
X. Fang, G. Wen, J. Zhou, and W. Zheng, Distributed adaptive Nash equilibrium seeking over multi-agent networks with communication uncertainties, in Proc. 2021 60th IEEE Conf. on Decision and Control, Austin, TX, USA, 2021, pp. 3387−3392.
DOI
123
D. Gadjov and L. Pavel, Distributed Nash equilibrium seeking resilient to adversaries, in Proc. 2021 60th IEEE Conf. on Decision and Control, Austin, TX, USA, 2021, pp. 191−196.
DOI
124
G. Shao, R. Wang, M. Ye, and X. F. Wang, Distributed Nash equilibrium seeking under input dead-zone, IEEE Trans. Autom. Control, doi: 10.1109/TAC.2021.3133182.
DOI
125

J. Lei, U. V. Shanbhag, J. S. Pang, and S. Sen, On synchronous, asynchronous, and randomized best-response schemes for stochastic Nash games, Math. Oper. Res., vol. 45, no. 1, pp. 157–190, 2019.
DOI Google Scholar
126

D. Gadjov and L. Pavel, A passivity-based approach to Nash equilibrium seeking over networks, IEEE Trans. Autom. Control, vol. 64, no. 3, pp. 1077–1092, 2019.
DOI Google Scholar
127
A. R. Romano and L. Pavel, Dynamic gradient play for NE seeking with disturbance rejection, in Proc. 2018 IEEE Conf. on Decision and Control, Miami, FL, USA, 2018, pp. 346−351.
DOI
128

S. Huang and P. Yi, Distributed best response dynamics for Nash equilibrium seeking in potential games, Control Theory Technol., vol. 18, no. 3, pp. 324–332, 2020.
DOI Google Scholar
129
S. Liang, P. Yi, Y. Hong, and K. Peng, Distributed Nash equilibrium seeking for aggregative games via a small-gain approach, arXiv preprint arXiv: 1911.06458, 2019.
130

Y. Zhu, W. Yu, G. Wen, and G. Chen, Distributed Nash equilibrium seeking in an aggregative game on a directed graph, IEEE Trans. Autom. Control, vol. 66, no. 6, pp. 2746–2753, 2021.
DOI Google Scholar
131

M. Ye, L. Yin, G. Wen, and Y. Zheng, On distributed Nash equilibrium computation: Hybrid games and a novel consensus-tracking perspective, IEEE Trans. Cybern., vol. 51, no. 10, pp. 5021–5031, 2021.
DOI Google Scholar
132
Z. Deng, Distributed algorithm design for aggregative games of Euler-Lagrange systems and its application to smart grids, IEEE Trans. Cybern., doi: 10.1109/TCYB.2021.3049462.
DOI
133
Y. Tang and P. Yi, Nash equilibrium seeking for high-order multi-agent systems with unknown dynamics, arXiv preprint arXiv: 2101.02883, 2021.
134
M. Ye, J. Yin, and L. Yin, Distributed Nash equilibrium seeking for games in second-order systems without velocity measurement, IEEE Trans. Autom. Control, doi: 10.1109/TAC.2021.3131553.
DOI
135
B. Gao and L. Pavel, Second-order mirror descent: Exact convergence beyond strictly stable equilibria in concave games, in Proc. 2021 60th IEEE Conf. on Decision and Control, Austin, TX, USA, 2021, pp. 948−953.
DOI
136
M. Zhu and E. Frazzoli, On distributed equilibrium seeking for generalized convex games, in Proc. 2012 IEEE 51st IEEE Conf. on Decision and Control, Maui, HI, USA, 2012, pp. 4858−4863.
DOI
137

P. Yi and L. Pavel, Asynchronous distributed algorithms for seeking generalized Nash equilibria under full and partial-decision information, IEEE Trans. Cybern., vol. 50, no. 6, pp. 2514–2526, 2020.
DOI Google Scholar
138
C. Cenedese, G. Belgioioso, S. Grammatico, and M. Cao, An asynchronous, forward-backward, distributed generalized Nash equilibrium seeking algorithm, in Proc. 2019 18th European Control Conf., Naples, Italy, 2019, pp. 3508−3513.
DOI
139
L. Pavel, A doubly-augmented operator splitting approach for distributed GNE seeking over networks, in Proc.2018 IEEE Conf. on Decision and Control, Miami, FL, USA, 2018, pp. 3529−3534.
DOI
140

M. Bianchi, G. Belgioioso, and S. Grammatico, Fast generalized Nash equilibrium seeking under partial-decision information, Automatica, vol. 136, p. 110080, 2022.
DOI Google Scholar
141
W. Xu, S. Yang, S. Grammatico, and W. He, An event-triggered distributed generalized Nash equilibrium seeking algorithm, in Proc. 2021 60th IEEE Conf. on Decision and Control, Austin, TX, USA, 2021, pp. 4301−4306.
DOI
142

B. Franci and S. Grammatico, Stochastic generalized Nash equilibrium seeking under partial-decision information, Automatica, vol. 137, p. 110101, 2022.
DOI Google Scholar
143
S. Zou and J. Lygeros, Semi-decentralized zeroth-order algorithms for stochastic generalized Nash equilibrium seeking, IEEE Trans. Autom. Control, doi: 10.1109/TAC.2022.3151225.
DOI
144
G. Belgioioso and S. Grammatico, Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games, IEEE Trans. Autom. Control, doi: 10.1109/TAC.2021.3135360.
DOI
145
F. Fabiani, M. A. Tajeddini, H. Kebriaei, and S. Grammatico, Local stackelberg equilibrium seeking in generalized aggregative games, IEEE Trans. Autom. Control, doi: 10.1109/TAC.2021.3077874.
DOI
146

D. Gadjov and L. Pavel, Single-timescale distributed GNE seeking for aggregative games over networks via forward-backward operator splitting, IEEE Trans. Autom. Control, vol. 66, no. 7, pp. 3259–3266, 2021.
DOI Google Scholar
147

M. Bianchi and S. Grammatico, Continuous-time fully distributed generalized Nash equilibrium seeking for multi-integrator agents, Automatica, vol. 129, p. 109660, 2021.
DOI Google Scholar
148

Y. Zhu, W. Yu, W. Ren, G. Wen, and J. Gu, Generalized Nash equilibrium seeking via continuous-time coordination dynamics over digraphs, IEEE Trans. Control Netw. Syst., vol. 8, no. 2, pp. 1023–1033, 2021.
DOI Google Scholar
149

Y. Zou, B. Huang, Z. Meng, and W. Ren, Continuous-time distributed Nash equilibrium seeking algorithms for non-cooperative constrained games, Automatica, vol. 127, p. 109535, 2021.
DOI Google Scholar
150

G. Chen, Y. Ming, Y. Hong, and P. Yi, Distributed algorithm for ε-generalized Nash equilibria with uncertain coupled constraints, Automatica, vol. 123, p. 109313, 2021.
DOI Google Scholar
151

Z. Deng, Distributed Nash equilibrium seeking for aggregative games with second-order nonlinear players, Automatica, vol. 135, p. 109980, 2022.
DOI Google Scholar
152

S. Krilašević and S. Grammatico, Learning generalized Nash equilibria in multi-agent dynamical systems via extremum seeking control, Automatica, vol. 133, p. 109846, 2021.
DOI Google Scholar
153

X. Xu and Q. Zhao, Distributed no-regret learning in multiagent systems: Challenges and recent developments, IEEE Signal Process. Mag., vol. 37, no. 3, pp. 84–91, 2020.
DOI Google Scholar
154
M. Zinkevich, Online convex programming and generalized infinitesimal gradient ascent, in Proc. 20th Int. Conf. on Machine Learning, Washington, DC, USA, 2003, pp. 928−935.
155
E. Hazan, A. Agarwal, and S. Kale, Logarithmic regret algorithms for online convex optimization, Mach. Learn., vol. 69, nos. 2&3, pp. 169−192, 2007.
DOI
156
P. L. Bartlett, E. Hazan, and A. Rakhlin, Adaptive online gradient descent, in Proc. 20th Int. Conf. on Neural Information Processing Systems, Vancouver, Canada, 2007, pp. 65−72.
157
S. Shalev-Shwartz and Y. Singer, Convex repeated games and fenchel duality, in Proc. 19th Int. Conf. on Neural Information Processing Systems, Vancouver, Canada, 2006, pp. 1265−1272.
158
Z. Zhou, P. Mertikopoulos, A. L. Moustakas, N. Bambos, and P. Glynn, Mirror descent learning in continuous games, in Proc. 2017 IEEE 56th Annu. Conf. on Decision and Control, Melbourne, Australia, 2017, pp. 5776−5783.
DOI
159
G. J. Gordon, A. Greenwald, and C. Marks, No-regret learning in convex games, in Proc. 25th Int. Conf. on Machine Learning, Helsinki, Finland, 2008, pp. 360−367.
DOI
160
M. Bravo, D. Leslie, and P. Mertikopoulos, Bandit learning in concave N-person games, in Proc. 32nd Int. Conf. on Neural Information Processing Systems, Montréal, Canada, 2018, pp. 5666−5676.
161
A. Héliou, P. Mertikopoulos, and Z. Zhou, Gradient-free online learning in continuous games with delayed rewards, in Proc. 37th Int. Conf. on Machine Learning, 2020, pp. 4172−4181.
162
J. Cohen, A. Héliou, and P. Mertikopoulos, Learning with bandit feedback in potential games, in Proc. 31st Int. Conf. on Neural Information Processing Systems, Long Beach, CA, USA, 2017, pp. 6372−6381.
163
Y. Shi and B. Zhang, No-regret learning in cournot games, arXiv preprint arXiv: 1906.06612, 2019.
164
I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, Generative adversarial nets, in Proc. 27th Int. Conf. on Neural Information Processing Systems, Montreal, Canada, 2014, pp. 2672−2680.
165
C. Daskalakis, A. Deckelbaum, and A. Kim, Near-optimal no-regret algorithms for zero-sum games, in Proc. 22nd Annu. ACM-SIAM Symp. on Discrete Algorithms, San Francisco, CA, USA, 2011, pp. 235−254.
DOI
166
E. A. Kangarshahi, Y. P. Hsieh, M. F. Sahin, and V. Cevher, Let's be honest: An optimal no-regret framework for zero-sum games, in Proc. 35th Int. Conf. on Machine Learning, Stockholm, Sweden, 2018, pp. 2493−2501.
167
C. Daskalakis and I. Panageas, Last-iterate convergence: Zero-sum games and constrained min-max optimization, in Proc. 10th Innovations in Theoretical Computer Science Conf., Dagstuhl, Germany, 2018, pp. 27.
168

M. Ye, G. Hu, and F. L. Lewis, Nash equilibrium seeking for N-coalition noncooperative games, Automatica, vol. 95, pp. 266–272, 2018.
DOI Google Scholar
169

X. Zeng, J. Chen, S. Liang, and Y. Hong, Generalized Nash equilibrium seeking strategy for distributed nonsmooth multi-cluster game, Automatica, vol. 103, pp. 20–26, 2019.
DOI Google Scholar
170

M. Ye, G. Hu, F. L. Lewis, and L. Xie, A unified strategy for solution seeking in graphical N-coalition noncooperative games, IEEE Trans. Autom. Control, vol. 64, no. 11, pp. 4645–4652, 2019.
DOI Google Scholar
171
C. Sun and G. Hu, Distributed generalized Nash equilibrium seeking of N-coalition games with full and distributive constraints, arXiv preprint arXiv: 2109.12515, 2021.
DOI
172

Y. Pang and G. Hu, Nash equilibrium seeking in N-coalition games via a gradient-free method, Automatica, vol. 136, p. 110013, 2022.
DOI Google Scholar
173
M. Meng and X. Li, On the linear convergence of distributed Nash equilibrium seeking for multi-cluster games under partial-decision information, arXiv preprint arXiv: 2005.06923, 2020.
174

N. S. Kukushkin, Best response dynamics in finite games with additive aggregation, Games EcoBehav., vol. 48, no. 1, pp. 94–110, 2004.
DOI Google Scholar
175

B. Swenson, S. Kar, and J. Xavier, Empirical centroid fictitious play: An approach for distributed learning in multi-agent games, IEEE Trans. Signal Process., vol. 63, no. 15, pp. 3888–3901, 2015.
DOI Google Scholar
176

B. Swenson, C. Eksin, S. Kar, and A. Ribeiro, Distributed inertial best-response dynamics, IEEE Trans. Autom. Control, vol. 63, no. 12, pp. 4294–4300, 2018.
DOI Google Scholar
177

B. Wang, Y. Wu, and K. J. R. Liu, Game theory for cognitive radio networks: An overview, Comput. Netw., vol. 54, no. 14, pp. 2537–2561, 2010.
DOI Google Scholar
178

L. Duan, J. Huang, and B. Shou, Investment and pricing with spectrum uncertainty: A cognitive operator's perspective, IEEE Trans. Mobile Comput., vol. 10, no. 11, pp. 1590–1604, 2011.
DOI Google Scholar
179

X. Liu, R. Zhu, B. Jalaian, and Y. Sun, Dynamic spectrum access algorithm based on game theory in cognitive radio networks, Mobile Netw. Appl., vol. 20, no. 6, pp. 817–827, 2015.
DOI Google Scholar
180

X. Cao, Y. Chen, and K. J. R. Liu, Cognitive radio networks with heterogeneous users: How to procure and price the spectrum? IEEE Trans. Wireless Commun., vol. 14, no. 3, pp. 1676–1688, 2015.
DOI Google Scholar
181

G. S. Kasbekar and S. Sarkar, Spectrum white space trade in cognitive radio networks, IEEE Trans. Autom. Control, vol. 61, no. 3, pp. 585–600, 2016.
DOI Google Scholar
182

W. Tushar, T. K. Saha, C. Yuen, D. Smith, and H. V. Poor, Peer-to-peer trading in electricity networks: An overview, IEEE Trans. Smart Grid, vol. 11, no. 4, pp. 3185–3200, 2020.
DOI Google Scholar
183

Y. Chen, C. Zhao, S. H. Low, and S. Mei, Approaching prosumer social optimum via energy sharing with proof of convergence, IEEE Trans. Smart Grid, vol. 12, no. 3, pp. 2484–2495, 2021.
DOI Google Scholar
184

Z. Wang, F. Liu, Z. Ma, Y. Chen, M. Jia, W. Wei, and Q. Wu, Distributed generalized Nash equilibrium seeking for energy sharing games in prosumers, IEEE Trans. Power Syst., vol. 36, no. 5, pp. 3973–3986, 2021.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 27 November 2021
Revised: 03 March 2022
Accepted: 17 June 2022
Published: 28 August 2022
Issue date: September 2022

Copyright

© The author(s) 2022

Acknowledgements

Acknowledgment

The authors would like to thank Xiaoyu Ma and Wenting Liu for their help in preparing the figures and tables. This work was supperted by Shanghai Sailing Program (Nos. 20YF1453000 and 20YF1452800), the National Science Foundation of China (Nos. 62003239, 62003240, 62003243, and 61903027), Shanghai Municipal Science and Technology Major Project (No. 2021SHZDZX0100), and Shanghai Municipal Commission of Science and Technology (No. 19511132101).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return