Opinion dynamics with median aggregation

Artificial Intelligence, vol. 355, pp. 104527

Abstract

Understanding the formation and evolution of opinions is of broad interdisciplinary interest. Many classical models for opinion formation focus on the impact of different notions of locality , e.g., locality due to network effects among agents or the role of the proximity of opinions. In practice, however, opinion formation is often governed by the interplay of local and global influences. In this paper, we study these influences with a model for opinion formation of agents embedded in a social network. Each agent has a static intrinsic opinion as well as a public opinion that is updated asynchronously over time. Moreover, agents have access to a global aggregate (e.g., the outcome of a vote) of all public opinions. We focus on the popular median voting rule and show that pure Nash equilibria always exist. For every initial state of the dynamics, a pure equilibrium can be reached. The set of reachable equilibria forms a complete lattice, and extremal equilibria can be computed in polynomial time. We show that by uniformly increasing the influence of the global median we can enforce that the median opinion is the same in every reachable equilibrium. We can compute the increase scheme that achieves this property in polynomial time. In contrast, when we can increase the influence of the global median for a set of at most k agents, finding the set that leads to a unique median opinion in every reachable equilibrium is NP -complete.

Authors 6

1. Petra Berenbrink

   Universität Hamburg

   Affiliation as printed

   Dept. of Computer Science, University of Hamburg, Vogt-Kölln-Str. 30, Hamburg, 22527, Germany

2. Martin Hoefer Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Dept. of Computer Science, RWTH Aachen University, Ahornstrasse 55, Aachen, 52074, Germany

3. Dominik Kaaser

   Hamburg University of Technology

   Affiliation as printed

   Inst. for Data Engineering, TU Hamburg, Blohmstraße 15, Hamburg, 21079, Germany

4. Marten Maack

   Universität Hamburg

   Affiliation as printed

   Dept. of Computer Science, University of Hamburg, Vogt-Kölln-Str. 30, Hamburg, 22527, Germany

5. Malin Rau

   Chalmers University of Technology

   Affiliation as printed

   Division of Applied Mathematics and Statistics, Chalmers University of Technology, Gothenburg, 412 96, Sweden

6. Lisa Wilhelmi corresponding Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Dept. of Computer Science, RWTH Aachen University, Ahornstrasse 55, Aachen, 52074, Germany