Sample Complexity of Opinion Formation on Networks
Haolin Liu Rajmohan Rajaraman Ravi Sundaram Anil Vullikanti Omer Wasim Haifeng Xu
Consider public health officials aiming to spread awareness about a new
vaccine in a community interconnected by a social network. How can they
distribute information with minimal resources, ensuring community-wide
understanding that aligns with the actual facts? This concern mirrors numerous
real-world situations. In this paper, we initialize the study of sample
complexity in opinion formation to solve this problem. Our model is built on
the recognized opinion formation game, where we regard each agent's opinion as
a data-derived model parameter, not just a real number as in prior studies.
Such an extension offers a wider understanding of opinion formation and ties
closely with federated learning. Through this formulation, we characterize the
sample complexity bounds for any network and also show asymptotically tight
bounds for specific network structures. Intriguingly, we discover optimal
strategies often allocate samples inversely to the degree, hinting at vital
policy implications. Our findings are empirically validated on both synthesized
and real-world networks.