Social Learning: Opinion Formation and Decision-Making over Graphs

V. Matta, V. Bordignon, and A. H. Sayed, Social Learning: Opinion Formation and Decision-Making over Graphs, NOW Publishers, 2025.

Description:

Complex cognitive systems, such as social networks, robotic swarms, or biological networks, are composed of individual entities (the agents) whose actions typically arise from some sophisticated form of “social” interaction with other agents. For example, consider how humans form their opinions about a certain phenomenon. The opinions take shape via repeated interactions with other individuals, whether through physical contact or virtually. A diffusion mechanism emerges through which opinions, information, or fake news propagate.

Social learning also arises over man-made systems as decision-making strategies by multiple agents interacting over a network. Consider a robotic swarm deployed over a hazardous area, where some robots operating under disadvantageous conditions (e.g., with limited visibility or partial information) would only be able to perform their task (such as saving a life during a rescue operation) by leveraging significant cooperation from other robots that have better access to critical information. Nature itself provides many other excellent examples of cooperative learning in the form of biological networks.

The main topic of this book relates to mechanisms for information diffusion and decision-making over graphs, and the study of how agents’ decisions evolve dynamically through interactions with neighbors and the environment.

About the Authors

Vincenzo Matta is a Full Professor in Telecommunications at the Department of Information and Electrical Engineering and Applied Mathematics, University of Salerno, Italy. An author of nearly 150 articles published in reputed journals and proceedings of international conferences,  his research interests include adaptation and learning over networks, social learning, statistical inference on graphs, and security in communication networks. Dr. Matta has served IEEE in multiple capacities, including as a member of the editorial boards of several journals.

Virginia Bordignon received the Ph.D. degree in electrical engineering in 2022 from École Polytechnique Federale de Lausanne (EPFL), Switzerland, for which she was awarded the 2023 Best Dissertation Award from the IEEE Signal Processing Society. She served as a post-doctoral scholar with the Adaptive Systems Laboratory at EPFL until early 2024. Her research interests include statistical inference, distributed learning, and information processing over networks.

Ali H. Sayed is Dean of Engineering at EPFL, Switzerland, where he also directs the Adaptive Systems Laboratory. He served before as Distinguished Professor and Chair of Electrical Engineering at UCLA. He is a member of the US National Academy of Engineering and the World Academy of Sciences. He served as President of the IEEE Signal Processing Society in 2018 and 2019. An author of over 650 scholarly publications and 9 books, his research involves several areas, including adaptation and learning theories, statistical inference, and multi-agent systems. His work has been recognized with several major awards, including the 2022 IEEE Fourier Technical Field Award and the 2020 IEEE Wiener Society Award. He is a Fellow of IEEE, EURASIP, and the American Association for the Advancement of Science.

Table of Contents

Dedication

Preface

Chapter 1: Introduction. 1.1 Examples of Social Learning, 1.2 Building Blocks, 1.3 Book Organization, 1.4 Notation, Symbols, and Conventions

Chapter 2: Bayesian Learning. 2.1 The Bayesian Way, 2.2 Properties of Bayes’ Rule, 2.3 Information Theoretic Interpretations, 2.4 Stochastic Optimization Interpretation

Chapter 3: From Single-Agent to Social Learning. 3.1 Bayesian versus Non-Bayesian Learning, 3.2 Non-Bayesian Social Learning, 3.3 Information-Theoretic Viewpoint, 3.4 Behavioral Viewpoint, 3.5 Unifying Framework

Chapter 4: Network Models. 4.1 Network Graphs, 4.2 Combination Matrices, 4.3 Strong and Primitive Graphs, 4.4 Stochastic Combination Matrices, 4.5 Weak Graphs, 4.6 Combination Policies

Chapter 5: Social Learning with Geometric Averaging. 5.1 Belief Convergence, 5.2 Learning over Connected Graphs, 5.3 Objective Evidence, 5.4 Subjective Evidence, 5.5 Fake Evidence, 5.6 Learning over Weak Graphs.

Chapter 6: Error Probability Performance. 6.1 Useful Statistical Descriptors, 6.2 Normal Approximation for Large t, 6.3. Large Deviations for Large t

Chapter 7: Social Learning with Arithmetic Averaging. 7.1 Modeling Assumptions, 7.2 Belief Convergence.

Chapter 8: Adaptive Social Learning. 8.1 Stubbornness of Agents, 8.2 Adaptive Update, 8.3 Learning versus Adaptation, 8.4 Adaptive Setting, 8.5 Variation on ASL

Chapter 9: Learning Accuracy under ASL. 9.1 Steady-State Analysis, 9.2 Small-delta Regime, 9.3 Consistency of Adaptive Social Learning, 9.4 Normal Approximation for Small delta, 9.5 Large Deviations for Small delta, 9.6 Main Performance Characteristics

Chapter 10: Adaptation under ASL. 10.1 Qualitative Description of the Transient Phase, 10.2 Quantitative Transient Analysis, 10.3 Adaptation Time, 10.4 Summary: Learning and Adaptation under ASL

Chapter 11: Partial Information Sharing. 11.1 Partial Information Framework, 11.2 Decoding Strategies, 11.3 Asymptotic Learning Objectives, 11.4 Memoryless Strategy, 11.5 Memory in Partial Information, 11.6 Comparing Strategies, 11.A Appendix: Preliminary Results, 11.B Appendix: Proof of Theorem 11,2, 11.C Appendix: Proof of Theorem 11.3

Chapter 12: Social Machine Learning. 12.1 Social Machine Learning Model, 12.2 General Decision Statistics, 12.3 Training Phase, 12.4 Performance Guarantees, 12.5 Sample Complexity, 12.6 Illustrative Examples, 12.A Appendix: Notation for Binary Decision Problems, 12.B Appendix: Bounds for Consistent Learning, 12.C Appendix: Proof of Theorem 12.1, 12.D Appendix: Proof of Theorem 12.2, 12.E Appendix: Auxiliary Results

Chapter 13: Extensions and Conclusions. 13.1 Non-Bayesian Updates, 13.2 Censored Beliefs, 13.3 Learning the Social Graph.

Appendix A: Convex Functions

Appendix B: Entropy and KL Divergence

Appendix C: Probabilistic Inequalities

Appendix D: Stochastic Convergence. D.1 Types of Stochastic Convergence, D.2 Fundamental Asymptotic Results, D.3 Convergence of Sums and Recursions, D.4 Martingales

Appendix E: Large Deviations. E.1 Empirical Averages, E.2 Large Deviation Principle

Appendix F: Random Sums and Series. F.1 Convergence Random Series, F.2 Random Sums Relevant to Adaptive Social Learning, F.3 Vector Case for Network Behavior

Appendix G: Rademacher Complexity. G.1 General Case, G.2 Multilayer Perceptrons.

References

About the Authors