On the Convergence Properties of Social Hegselmann-Krause Dynamics

• 成果类型: Article
• 署名作者: Parasnis, Rohit Yashodhar; Franceschetti, Massimo; Touri, Behrouz
• 署名单位: University of California System; University of California San Diego
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3052748
• 发表日期: 2022
• 页码: 589-604
• 关键词: multiagent systems; networked control systems; network theory (graphs); Nonlinear systems

摘要

We study the convergence properties of social Hegselmann-Krause (HK) dynamics, a variant of the HK model of opinion dynamics where a physical connectivity graph that accounts for the extrinsic factors that could prevent interaction between certain pairs of agents is incorporated. As opposed to the original HK dynamics (which terminates in finite time), we show that for any underlying connected and incomplete graph, under a certain mild assumption, the expected termination time of social HK dynamics is infinity. We then investigate the rate of convergence to the steady state, and provide bounds on the maximum epsilon-convergence time in terms of the properties of the physical connectivity graph. We extend this discussion and observe that for almost all n, there exists an n-vertex physical connectivity graph on which social HK dynamics may not even epsilon-converge to the steady state within a bounded time frame. We then provide nearly tight necessary and sufficient conditions for arbitrarily slow merging (a phenomenon that is essential for arbitrarily slow epsilon-convergence to the steady state). Using the necessary conditions, we show that complete r-partite graphs have bounded epsilon-convergence times.