Yanqi Lake Beijing Institute of Mathematical Sciences and Applications (BIMSA)
399
0
0
Date
Time
Local Time
Room
Session
Role
Topic
2023-07-28
10:30-11:30
2023-07-28,10:30-11:30
LR8 (A3-4 3F)
07-28 Morning Math Lecture Room 8 (A3-4 3F)
Speaker
Asynchronous opinion Dynamics
We analyze the asynchronous averaging dynamics: In a connected graph $G$ with $n$ nodes, each node has an initial opinion. and an independent Poisson clock. When a clock at a node $v$ rings, the opinion at $v$ is replaced by the average opinion of its neighbors. It is well known that the opinions converge to a consensus. We show that the expected time to reach a near consensus is poly($n$) in undirected graphs and in Eulerian digraphs, but for some digraphs of bounded degree it is exponential. Our main result is that in undirected graphs and Eulerian digraphs, if the degrees are uniformly bounded and the initial opinions are i.i.d., then $E$ the convergence time is polylog($n$). We give sharp estimates for the variance of the limiting consensus opinion, which measures the ability to aggregate information (``wisdom of the crowd''). We also prove generalizations to non-reversible Markov chains and infinite graphs. New results of independent interest on fragmentation processes and coupled random walks are crucial to our analysis. Joint work with D. Elboim and R. Peretz