×

A simple framework for stability analysis of state-dependent networks of heterogeneous agents. (English) Zbl 1422.91610

Summary: Stability and analysis of multiagent network systems with state-dependent switching typologies have been a fundamental and longstanding challenge in control, social sciences, and many other related fields. These already complex systems become further complicated once one accounts for asymmetry or heterogeneity of the underlying agents/dynamics. Despite extensive progress in analysis of conventional networked decision systems where the network evolution and state dynamics are driven by independent or weakly coupled processes, most of the existing results fail to address multiagent systems where the network and state dynamics are highly coupled and evolve based on status of heterogeneous agents. Motivated by numerous applications of such dynamics in social sciences, in this paper we provide a new direction toward analysis of dynamic networks of heterogeneous agents under complex time-varying environments. As a result we show Lyapunov stability and convergence of several challenging problems from opinion dynamics using a simple application of our framework. In particular, we introduce a new class of asymmetric opinion dynamics, namely, nearest neighbor dynamics, and show how our framework can be used to analyze their behavior. Finally, we extend our results to game-theoretic settings and provide new insights toward analysis of complex networked multiagent systems using exciting field of sequential optimization.

MSC:

91D30 Social networks; opinion dynamics
93D05 Lyapunov and other classical stabilities (Lagrange, Poisson, \(L^p, l^p\), etc.) in control theory
93A14 Decentralized systems
91B69 Heterogeneous agent models
91A10 Noncooperative games

Software:

AS 136

References:

[1] H. Attouch, J. Bolte, P. Redont, and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35 (2010), pp. 438-457. · Zbl 1214.65036
[2] T. Başar, S. R. Etesami, and A. Olshevsky, Convergence time of quantized Metropolis consensus over time-varying networks, IEEE Trans. Automat. Control, 61 (2016), pp. 4048-4054. · Zbl 1359.81082
[3] A. Bhattacharyya, M. Braverman, B. Chazelle, and H. L. Nguyen, On the convergence of the Hegselmann-Krause system, in Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ACM, 2013, pp. 61-66. · Zbl 1361.68106
[4] V. D. Blondel, J. M. Hendrickx, and J. N. Tsitsiklis, On the 2R conjecture for multi-agent systems, in Proceedings of the European Control Conference, IEEE, 2007, pp. 874-881.
[5] F. Bullo, J. Cortes, and S. Martinez, Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms, Princeton Ser. Appl. Math. 27, Princeton University Press, Princeton, NJ, 2009. · Zbl 1193.93137
[6] B. Chazelle, The total s-energy of a multiagent system, SIAM J. Control Optim., 49 (2011), pp. 1680-1706. · Zbl 1226.93007
[7] B. Chazelle and C. Wang, Inertial Hegselmann-Krause systems, IEEE Trans. Automat. Control, 62 (2017), pp. 3905-3913. · Zbl 1375.91066
[8] M. H. DeGroot, Reaching a consensus, J. Amer. Statist. Assoc., 69 (1974), pp. 118-121. · Zbl 0282.92011
[9] Y. Dong, X. Chen, H. Liang, and C.-C. Li, Dynamics of linguistic opinion formation in bounded confidence model, Inform. Fusion, 32 (2016), pp. 52-61.
[10] S. R. Etesami, Potential-Based Analysis of Social, Communication, and Distributed Networks, Springer, New York, 2017.
[11] S. R. Etesami and T. Başar, Game-theoretic analysis of the Hegselmann-Krause model for opinion dynamics in finite dimensions, IEEE Trans. Automat. Control, 60 (2015), pp. 1886-1897. · Zbl 1360.91116
[12] S. R. Etesami and T. Başar, Convergence time for unbiased quantized consensus over static and dynamic networks, IEEE Trans. Automat. Control, 61 (2016), pp. 443-455. · Zbl 1359.60094
[13] S. R. Etesami, T. Başar, A. Nedić, and B. Touri, Termination time of multidimensional Hegselmann-Krause opinion dynamics, in Proceedings of the American Control Conference, IEEE, 2013, pp. 1255-1260.
[14] N. E. Friedkin and E. C. Johnsen, Social positions in influence networks, Social Networks, 19 (1997), pp. 209-222.
[15] N. E. Friedkin and E. C. Johnsen, Social influence networks and opinion change, Adv. Group Processes, 16 (1999), pp. 1-29.
[16] N. E. Friedkin and E. C. Johnsen, Social Influence Network Theory: A Sociological Examination of Small Group Dynamics, Structural Anal. Social Sci. 33, Cambridge University Press, Cambridge, UK, 2011. · Zbl 1228.91001
[17] J. Hartigan and M. Wong, A k-means clustering algorithm, J. Roy. Statist. Soc. Ser. C Appl. Statist., 28 (1979), pp. 100-108. · Zbl 0447.62062
[18] R. Hegselmann and U. Krause, Opinion dynamics and bounded confidence models, analysis and simulation, J. Artificial Societies Social Simulation, 5 (2002), pp. 1-33.
[19] J. M. Hendrickx, Graphs and Networks for the Analysis of Autonomous Agent Systems, Ph.D. thesis, Universite Catholique de Louvain, 2011.
[20] J. M. Hendrickx and A. Olshevsky, On symmetric continuum opinion dynamics, SIAM J. Control Optim., 54 (2016), pp. 2893-2918. · Zbl 1348.93225
[21] J. M. Hendrickx and J. N. Tsitsiklis, Convergence of type-symmetric and cut-balanced consensus seeking systems, IEEE Trans. Automat. Control, 58 (2013), pp. 214-218. · Zbl 1369.93025
[22] H. Howson and N. Sancho, A new algorithm for the solution of multi-state dynamic programming problems, Math. Program., 8 (1975), pp. 104-116. · Zbl 0311.90080
[23] A. Jadbabaie, J. Lin, and A. S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Trans. Automat. Control, 48 (2003), pp. 988-1001. · Zbl 1364.93514
[24] J. Lorenz, Continuous opinion dynamics under bounded confidence: A survey, Internat. J. Modern Phys. C, 18 (2007), pp. 1819-1838. · Zbl 1151.91076
[25] J. Lorenz, Heterogeneous bounds of confidence: Meet, discuss and find consensus!, Complexity, 15 (2010), pp. 43-52.
[26] J. Lorenz, Repeated Averaging and Bounded-Confidence, Modeling, Analysis and Simulation of Continuous Opinion Dynamics, Ph.D. thesis, University of Bremen, 2007. · Zbl 1196.93003
[27] A. Mirtabatabaei and F. Bullo, Opinion dynamics in heterogeneous networks: Convergence conjectures and theorems, SIAM J. Control Optim., 50 (2012), pp. 2763-2785. · Zbl 1258.91191
[28] D. Monderer and L. S. Shapley, Potential games, Games Econom. Behavi., 14 (1996), pp. 124-143. · Zbl 0862.90137
[29] A. Nedić and A. Olshevsky, Distributed optimization over time-varying directed graphs, IEEE Trans. Automat. Control, 60 (2015), pp. 601-615. · Zbl 1360.90262
[30] A. Nedic, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis, On distributed averaging algorithms and quantization effects, IEEE Trans. Automat. Control, 54 (2009), pp. 2506-2517. · Zbl 1367.93405
[31] A. Nedić, A. Olshevsky, and M. G. Rabbat, Network topology and communication-computation tradeoffs in decentralized optimization, Proc. IEEE, 106 (2018), pp. 953-976.
[32] R. Olfati-Saber and R. M. Murray, Consensus problems in networks of agents with switching topology and time-delays, IEEE Trans. Automat. Control, 49 (2004), pp. 1520-1533. · Zbl 1365.93301
[33] A. Olshevsky and J. Tsitsiklis, On the nonexistence of quadratic Lyapunov functions for consensus algorithms, IEEE Trans. Automat. Control, 53 (2008), pp. 2642-2645. · Zbl 1367.93611
[34] A. Olshevsky and J. N. Tsitsiklis, Convergence speed in distributed consensus and averaging, SIAM J. Control Optim., 48 (2009), pp. 33-55. · Zbl 1182.93008
[35] M. Pineda, R. Toral, and E. Hernández-García, The noisy Hegselmann-Krause model for opinion dynamics, Eur. Phys. J. B, 86 (2013), pp. 1-10. · Zbl 1518.91197
[36] A. V. Proskurnikov and R. Tempo, A tutorial on modeling and analysis of dynamic social networks. Part I, Annu. Rev. Control, 43 (2017), pp. 65-79.
[37] A. V. Proskurnikov and R. Tempo, A tutorial on modeling and analysis of dynamic social networks. Part II, Annu. Rev. Control, 45 (2018), pp. 166-190.
[38] M. Razaviyayn, M. Hong, and Z.-Q. Luo, A unified convergence analysis of block successive minimization methods for nonsmooth optimization, SIAM J. Optim., 23 (2013), pp. 1126-1153. · Zbl 1273.90123
[39] M. Roozbehani, A. Megretski, and E. Frazzoli, Lyapunov analysis of quadratically symmetric neighborhood consensus algorithms, in Proceedings of the 47th IEEE Conference on Decision and Control, IEEE, 2008, pp. 2252-2257.
[40] J. B. Rosen, Existence and uniqueness of equilibrium points for concave \(n\)-person games, Econometrica, 33 (1965), pp. 520-534. · Zbl 0142.17603
[41] I. M. Sonin, The decomposition-separation theorem for finite nonhomogeneous Markov chains and related problems, in Markov Processes and Related Topics: A Festschrift for Thomas G. Kurtz, Institute of Mathematical Statistics, 2008, pp. 1-15. · Zbl 1168.60357
[42] W. Su, Y. Gu, S. Wang, and Y. Yu, Partial convergence of heterogeneous Hegselmann-Krause opinion dynamics, Sci. China Technol. Sci., 60 (2017), pp. 1433-1438.
[43] T. Tatarenko and B. Touri, Non-convex distributed optimization, IEEE Trans. Automat. Control, 62 (2017), pp. 3744-3757. · Zbl 1373.90123
[44] B. Touri, Product of Random Stochastic Matrices and Distributed Averaging, Springer, New York, 2012. · Zbl 1244.15023
[45] B. Touri and A. Nedić, On existence of a quadratic comparison function for random weighted averaging dynamics and its implications, in Proceedings of the 50th Conference on Decision and Control and European Control Conference, IEEE, 2011, pp. 3806-3811.
[46] H.-T. Wai, A. Scaglione, and A. Leshem, Identifying trust in social networks with stubborn agents, with application to market decisions, in Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing, IEEE, 2015, pp. 747-754.
[47] M. B. Ye, J. Liu, B. D. Anderson, C. B. Yu, and T. Basar, Evolution of social power in social networks with dynamic topology, IEEE Trans. Automat. Control, 63 (2018), pp. 3793-3808. · Zbl 1425.91382
[48] H. Zhang, F. L. Lewis, and Z. Qu, Lyapunov, adaptive, and optimal design techniques for cooperative systems on directed communication graphs, IEEE Trans. Industrial Electronics, 59 (2012), pp. 3026-3041.
[49] M. Zhu and S. Martínez, On the convergence time of asynchronous distributed quantized averaging algorithms, IEEE Trans. Automat. Control, 56 (2011), pp. 386-390. · Zbl 1368.68043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.