AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home CAAI Artificial Intelligence Research Article
PDF (1.2 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

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
Show Author Information

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 gamesmulti-agent systemsoptimization and decision makingcyber-physical systemsNash equilibriumdistributed computation

References

1

A. Nedić and J. Liu, Distributed optimization for control, Annu. Rev. Control Robot. Auton. Syst., vol. 1, pp. 77–103, 2018.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref 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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
20

I. Menache and A. Ozdaglar, Network games: Theory, models, and dynamics, Synth. Lect. Commun. Networks, vol. 4, no. 1, pp. 1–159, 2011.
Crossref Google Scholar
21
L. Pavel, Game Theory for Control of Optical Networks. Boston, MA, USA: Springer, 2012.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
33

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

Y. Nesterov, Stable traffic equilibria: Properties and applications, Optim. Eng., vol. 1, no. 1, pp. 29–50, 2000.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
40
D. P. Palomar and Y. C. Eldar, Convex Optimization in Signal Processing and Communications. Cambridge, UK: Cambridge University Press, 2010.
Crossref
41
F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems. New York, NY, USA: Springer, 2003.
Crossref
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.
Crossref 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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
48

F. Salehisadaghiani and L. Pavel, Distributed Nash equilibrium seeking: A gossip-based algorithm, Automatica, vol. 72, pp. 209–216, 2016.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
68

N. Brown and T. Sandholm, Superhuman AI for multiplayer poker, Science, vol. 365, no. 6456, pp. 885–890, 2019.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
81

M. Zhu and E. Frazzoli, Distributed robust adaptive equilibrium computation for generalized convex games, Automatica, vol. 63, pp. 82–91, 2016.
Crossref 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.
Crossref 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.
Crossref Google Scholar
85
J. von Neumann, Zur theorie der Gesellschaftsspiele, (in German), Math. Ann., vol. 100, no. 1, pp. 295−320, 1928.
Crossref
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.
Crossref 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.
Crossref
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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref
95

R. Zhu, J. Zhang, K. You, and T. Basar, Asynchronous networked aggregative games, Automatica, vol. 136, p. 110054, 2022.
Crossref 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.
Crossref
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.
Crossref
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.
Crossref
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.
Crossref 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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
104

D. Monderer and L. S. Shapley, Potential games, Games Econ. Behav., vol. 14, no. 1, pp. 124–143, 1996.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
112

M. Ye and G. Hu, Solving potential games with dynamical constraint, IEEE Trans. Cybern., vol. 46, no. 5, pp. 1156–1164, 2016.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref
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.
Crossref
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.
Crossref
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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref
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.
Crossref
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.
Crossref
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.
Crossref 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.
Crossref
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.
Crossref
140

M. Bianchi, G. Belgioioso, and S. Grammatico, Fast generalized Nash equilibrium seeking under partial-decision information, Automatica, vol. 136, p. 110080, 2022.
Crossref 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.
Crossref
142

B. Franci and S. Grammatico, Stochastic generalized Nash equilibrium seeking under partial-decision information, Automatica, vol. 137, p. 110101, 2022.
Crossref 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.
Crossref
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.
Crossref
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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
151

Z. Deng, Distributed Nash equilibrium seeking for aggregative games with second-order nonlinear players, Automatica, vol. 135, p. 109980, 2022.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
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.
Crossref
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.
Crossref
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.
Crossref
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
172

Y. Pang and G. Hu, Nash equilibrium seeking in N-coalition games via a gradient-free method, Automatica, vol. 136, p. 110013, 2022.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
CAAI Artificial Intelligence Research
Volume 1 Issue 1,
September 2022
Pages 8-27
DOI: 10.26599/AIR.2022.9150002
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

4083

Views

916

Downloads

4

Crossref

Altmetrics
Received: 27 November 2021
Revised: 03 March 2022
Accepted: 17 June 2022
Published: 28 August 2022
© The author(s) 2022

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