Game-Theoretic Analysis of the Hegselmann-Krause Model for Opinion Dynamics in Finite Dimensions

Research output: Contribution to journalArticle

Abstract

We consider the Hegselmann-Krause model for opinion dynamics and study the evolution of the system under various settings. We first analyze the termination time of the synchronous Hegselmann-Krause dynamics in arbitrary finite dimensions and show that the termination time in general only depends on the number of agents involved in the dynamics. To the best of our knowledge, that is the sharpest bound for the termination time of such dynamics that removes dependency of the termination time from the dimension of the ambient space, and connects the convergence speed of the dynamics to the eigenvalues of the adjacency matrix of the connectivity graph in the Hegselmann-Krause dynamics. This answers an open question in the paper by Bhattacharyya et al. on how to obtain a tighter upper bound for the termination time. Furthermore, we study the asynchronous Hegselmann-Krause model from a novel game-theoretic approach and show that the evolution of an asynchronous Hegselmann-Krause model is equivalent to a sequence of best response updates in a well-designed potential game. We then provide a polynomial upper bound for the expected time and expected number of switching topologies until the dynamic reaches an arbitrarily small neighborhood of its equilibrium points, provided that the agents update uniformly at random. This is a step toward analysis of heterogeneous Hegselmann-Krause dynamics. Finally, we consider the heterogeneous Hegselmann-Krause dynamics and provide a necessary condition for the finite termination time of such dynamics. In particular, we sketch some future directions toward more detailed analysis of the heterogeneous Hegselmann-Krause model.

Original languageEnglish (US)
Article number7024142
Pages (from-to)1886-1897
Number of pages12
JournalIEEE Transactions on Automatic Control
Volume60
Issue number7
DOIs
StatePublished - Jul 1 2015

Fingerprint

Topology
Polynomials

Keywords

  • Multidimensional Hegselmann-Krause model
  • asynchronous
  • best response dynamics
  • heterogeneous
  • homogeneous
  • opinion dynamics
  • potential game
  • strategic equivalence
  • synchronous

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this

@article{18b695ca587d4944a49967ba681ec0fa,
title = "Game-Theoretic Analysis of the Hegselmann-Krause Model for Opinion Dynamics in Finite Dimensions",
abstract = "We consider the Hegselmann-Krause model for opinion dynamics and study the evolution of the system under various settings. We first analyze the termination time of the synchronous Hegselmann-Krause dynamics in arbitrary finite dimensions and show that the termination time in general only depends on the number of agents involved in the dynamics. To the best of our knowledge, that is the sharpest bound for the termination time of such dynamics that removes dependency of the termination time from the dimension of the ambient space, and connects the convergence speed of the dynamics to the eigenvalues of the adjacency matrix of the connectivity graph in the Hegselmann-Krause dynamics. This answers an open question in the paper by Bhattacharyya et al. on how to obtain a tighter upper bound for the termination time. Furthermore, we study the asynchronous Hegselmann-Krause model from a novel game-theoretic approach and show that the evolution of an asynchronous Hegselmann-Krause model is equivalent to a sequence of best response updates in a well-designed potential game. We then provide a polynomial upper bound for the expected time and expected number of switching topologies until the dynamic reaches an arbitrarily small neighborhood of its equilibrium points, provided that the agents update uniformly at random. This is a step toward analysis of heterogeneous Hegselmann-Krause dynamics. Finally, we consider the heterogeneous Hegselmann-Krause dynamics and provide a necessary condition for the finite termination time of such dynamics. In particular, we sketch some future directions toward more detailed analysis of the heterogeneous Hegselmann-Krause model.",
keywords = "Multidimensional Hegselmann-Krause model, asynchronous, best response dynamics, heterogeneous, homogeneous, opinion dynamics, potential game, strategic equivalence, synchronous",
author = "Etesami, {Seyed Rasoul} and Basar, {M Tamer}",
year = "2015",
month = "7",
day = "1",
doi = "10.1109/TAC.2015.2394954",
language = "English (US)",
volume = "60",
pages = "1886--1897",
journal = "IEEE Transactions on Automatic Control",
issn = "0018-9286",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "7",

}

TY - JOUR

T1 - Game-Theoretic Analysis of the Hegselmann-Krause Model for Opinion Dynamics in Finite Dimensions

AU - Etesami, Seyed Rasoul

AU - Basar, M Tamer

PY - 2015/7/1

Y1 - 2015/7/1

N2 - We consider the Hegselmann-Krause model for opinion dynamics and study the evolution of the system under various settings. We first analyze the termination time of the synchronous Hegselmann-Krause dynamics in arbitrary finite dimensions and show that the termination time in general only depends on the number of agents involved in the dynamics. To the best of our knowledge, that is the sharpest bound for the termination time of such dynamics that removes dependency of the termination time from the dimension of the ambient space, and connects the convergence speed of the dynamics to the eigenvalues of the adjacency matrix of the connectivity graph in the Hegselmann-Krause dynamics. This answers an open question in the paper by Bhattacharyya et al. on how to obtain a tighter upper bound for the termination time. Furthermore, we study the asynchronous Hegselmann-Krause model from a novel game-theoretic approach and show that the evolution of an asynchronous Hegselmann-Krause model is equivalent to a sequence of best response updates in a well-designed potential game. We then provide a polynomial upper bound for the expected time and expected number of switching topologies until the dynamic reaches an arbitrarily small neighborhood of its equilibrium points, provided that the agents update uniformly at random. This is a step toward analysis of heterogeneous Hegselmann-Krause dynamics. Finally, we consider the heterogeneous Hegselmann-Krause dynamics and provide a necessary condition for the finite termination time of such dynamics. In particular, we sketch some future directions toward more detailed analysis of the heterogeneous Hegselmann-Krause model.

AB - We consider the Hegselmann-Krause model for opinion dynamics and study the evolution of the system under various settings. We first analyze the termination time of the synchronous Hegselmann-Krause dynamics in arbitrary finite dimensions and show that the termination time in general only depends on the number of agents involved in the dynamics. To the best of our knowledge, that is the sharpest bound for the termination time of such dynamics that removes dependency of the termination time from the dimension of the ambient space, and connects the convergence speed of the dynamics to the eigenvalues of the adjacency matrix of the connectivity graph in the Hegselmann-Krause dynamics. This answers an open question in the paper by Bhattacharyya et al. on how to obtain a tighter upper bound for the termination time. Furthermore, we study the asynchronous Hegselmann-Krause model from a novel game-theoretic approach and show that the evolution of an asynchronous Hegselmann-Krause model is equivalent to a sequence of best response updates in a well-designed potential game. We then provide a polynomial upper bound for the expected time and expected number of switching topologies until the dynamic reaches an arbitrarily small neighborhood of its equilibrium points, provided that the agents update uniformly at random. This is a step toward analysis of heterogeneous Hegselmann-Krause dynamics. Finally, we consider the heterogeneous Hegselmann-Krause dynamics and provide a necessary condition for the finite termination time of such dynamics. In particular, we sketch some future directions toward more detailed analysis of the heterogeneous Hegselmann-Krause model.

KW - Multidimensional Hegselmann-Krause model

KW - asynchronous

KW - best response dynamics

KW - heterogeneous

KW - homogeneous

KW - opinion dynamics

KW - potential game

KW - strategic equivalence

KW - synchronous

UR - http://www.scopus.com/inward/record.url?scp=84934325685&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84934325685&partnerID=8YFLogxK

U2 - 10.1109/TAC.2015.2394954

DO - 10.1109/TAC.2015.2394954

M3 - Article

AN - SCOPUS:84934325685

VL - 60

SP - 1886

EP - 1897

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

SN - 0018-9286

IS - 7

M1 - 7024142

ER -