Distributed sensing, swarm sensing, adaptive social learning

Local versus global design
Incentive design
Graph topology
Misc links
As metaphor for human systems
References

Is this is a real field separate from all the things that looks similar to it? e.g.probability collectives (are they a thing?) and the nature-inspired algorithms people get disturbingly enthusiastic about (ant colonies, particle swarms, that one based on choirs…), and reliability engineering (Byzantine generals etc), …and quorum sensing? How about that?

Local versus global design

I’m particular interested in the constraints on what global organising can be done using local information. There are formal approaches to this, e.g. Wang and Rubenstein (2020) and more fun and even cheap ones like Mordvintsev et al. (2020).

Incentive design

If your network has autonomous agents that need to cooperate, how do you design their private utility? Although this looks a little bit like collective decisions, I am thinking here of more incentive design-oriented questions. When we say “multi agent systems” there is usually a presumption that the individual agents are fairly simple, not whole human beings. Special case: flocking. The barriers betwixt these are permeable.

Graph topology

If the graph topology of connections is not 1:N but something more complicated, what happens to learnability? What if you need to discover something controlling for graph topology? I have arbitrarily filed that under inference on social graphs.

Misc links

Yoav Shoham and Kevin Leyton-Brown’s textbook, Multiagent Systems Algorithmic, Game-Theoretic, and Logical Foundations is downloadable
Distributed information processing in biological and computational systems
Yujian, Digest: Consensus Filters is a quick intro to signal analysis using consensus filters

As metaphor for human systems

See wisdom of crowds versus groupthink, or possible weaponized social media.

References

Acemoglu, Daron, and Asuman Ozdaglar. 2011. “Opinion Dynamics and Learning in Social Networks.” Dynamic Games and Applications 1 (1): 3–49. https://doi.org/10.1007/s13235-010-0004-1.

Achlioptas, Dimitris, Aaron Clauset, David Kempe, and Cristopher Moore. 2005. “On the Bias of Traceroute Sampling: Or, Power-Law Degree Distributions in Regular Graphs.” In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, 694–703. STOC ’05. New York, NY, USA: ACM. https://doi.org/10.1145/1060590.1060693.

Akyildiz, Ian F., Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci. 2002. “A Survey on Sensor Networks.” Communications Magazine, IEEE 40 (8): 102–14. https://doi.org/10.1109/MCOM.2002.1024422.

Bianchi, P., and J. Jakubowicz. 2013. “Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization.” IEEE Transactions on Automatic Control 58 (2): 391–405. https://doi.org/10.1109/TAC.2012.2209984.

Bieniawski, Stefan, and David H. Wolpert. 2004. “Adaptive, Distributed Control of Constrained Multi-Agent Systems.” In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 3, 4:1230–31. IEEE Computer Society. https://ti.arc.nasa.gov/m/profile/dhw/papers/7.pdf.

Cattivelli, Federico S., Cassio G. Lopes, and Ali H. Sayed. 2008. “Diffusion Recursive Least-Squares for Distributed Estimation over Adaptive Networks.” IEEE Transactions on Signal Processing 56 (5): 1865–77.

Cattivelli, Federico S., and Ali H. Sayed. 2009. “Diffusion LMS Strategies for Distributed Estimation.” IEEE Transactions on Signal Processing 58 (3): 1035–48.

———. 2010. “Diffusion Strategies for Distributed Kalman Filtering and Smoothing.” IEEE Transactions on Automatic Control 55 (9): 2069–84.

Chen, Jianshu, and Ali H. Sayed. 2012. “Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks.” IEEE Transactions on Signal Processing 60 (8): 4289–4305.

Codenotti, Bruno, and Kasturi Varadarajan. 2004. “Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities.” In ICALP, 371–82. Springer. https://doi.org/10.1007/978-3-540-27836-8_33.

Degroot, Morris H. 1974. “Reaching a Consensus.” Journal of the American Statistical Association 69 (345): 118–21. https://doi.org/10.1080/01621459.1974.10480137.

Deng, Xiaotie, Christos Papadimitriou, and Shmuel Safra. 2002. “On the Complexity of Equilibria.” In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, 67–71. STOC ’02. New York, NY, USA: ACM. https://doi.org/10.1145/509907.509920.

Di Lorenzo, Paolo, and Ali H. Sayed. 2013. “Sparse Distributed Learning Based on Diffusion Adaptation.” IEEE Transactions on Signal Processing 61 (6): 1419–33. https://doi.org/10.1109/TSP.2012.2232663.

Freeman, R.A., Peng Yang, and K.M. Lynch. 2006. “Stability and Convergence Properties of Dynamic Average Consensus Estimators.” In 2006 45th IEEE Conference on Decision and Control, 338–43. San Diego, CA, USA: IEEE. https://doi.org/10.1109/CDC.2006.377078.

Galesic, Mirta, Daniel Barkoczi, and Konstantinos Katsikopoulos. 2018. “Smaller Crowds Outperform Larger Crowds and Individuals in Realistic Task Conditions.” Decision 5 (1): 1–15. https://doi.org/10.1037/dec0000059.

Hong, Lu, and Scott E. Page. 2004. “Groups of Diverse Problem Solvers Can Outperform Groups of High-Ability Problem Solvers.” Proceedings of the National Academy of Sciences 101 (46): 16385–89. https://doi.org/10.1073/pnas.0403723101.

Lalitha, Anusha, Tara Javidi, and Anand Sarwate. 2014. “Social Learning and Distributed Hypothesis Testing.” arXiv:1410.4307 [cs, Math, Stat], October. http://arxiv.org/abs/1410.4307.

Lopes, Cassio G., and Ali H. Sayed. 2007. “Incremental Adaptive Strategies over Distributed Networks.” IEEE Transactions on Signal Processing 55 (8): 4064–77.

———. 2008. “Diffusion Least-Mean Squares over Adaptive Networks: Formulation and Performance Analysis.” IEEE Transactions on Signal Processing 56 (7): 3122–36.

Mann, Richard P., and Dirk Helbing. 2016. “Minorities Report: Optimal Incentives for Collective Intelligence.” arXiv:1611.03899 [cs, Math, Stat], November. http://arxiv.org/abs/1611.03899.

Mateo, David, Nikolaj Horsevad, Vahid Hassani, Mohammadreza Chamanbaz, and Roland Bouffanais. 2019. “Optimal Network Topology for Responsive Collective Behavior.” Science Advances 5 (4). https://doi.org/10.1126/sciadv.aau0999.

Mordvintsev, Alexander, Ettore Randazzo, Eyvind Niklasson, and Michael Levin. 2020. “Growing Neural Cellular Automata.” Distill 5 (2): e23. https://doi.org/10.23915/distill.00023.

Navlakha, Saket, and Ziv Bar-Joseph. 2014. “Distributed Information Processing in Biological and Computational Systems.” Communications of the ACM 58 (1): 94–102. https://doi.org/10.1145/2678280.

Olfati-Saber, R. 2005. “Distributed Kalman Filter with Embedded Consensus Filters.” In 44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC ’05, 8179–84. Seville, Spain: IEEE. https://doi.org/10.1109/CDC.2005.1583486.

Olfati-Saber, R. 2006. “Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory.” Automatic Control, IEEE Transactions on 51 (3): 401–20.

Olfati-Saber, R., J.A. Fax, and R.M. Murray. 2007. “Consensus and Cooperation in Networked Multi-Agent Systems.” Proceedings of the IEEE 95 (1): 215–33. https://doi.org/10.1109/JPROC.2006.887293.

Ren, W, and R W Beard. 2005. “Consensus Seeking in Multiagent Systems Under Dynamically Changing Interaction Topologies.” Automatic Control, IEEE Transactions on 50 (5): 655–61.

Samuelson, Larry. 2001. “Analogies, Adaptation, and Anomalies.” Journal of Economic Theory 97 (2): 320–66. https://doi.org/10.1006/jeth.2000.2754.

Sayed, Ali H. 2014a. “Adaptation, Learning, and Optimization over Networks.” Foundations and Trends in Machine Learning 7 (ARTICLE): 311–801.

———. 2014b. “Adaptive Networks.” Proceedings of the IEEE 102 (4): 460–97. https://doi.org/10.1109/JPROC.2014.2306253.

Spanos, Demetri P., Reza Olfati-Saber, and Richard M. Murray. 2005. “Dynamic Consensus on Mobile Networks.” In IFAC World Congress, 1–6. Citeseer.

Stiglitz, Joseph E. 2006. “The Contributions of the Economics of Information to Twentieth Century Economics.” The Quarterly Journal of Economics 115 (4). https://doi.org/10.1162/003355300555015.

Tumer, Kagan, and David H Wolpert. 2004. “Coordination in Large Collectives- Chapter 1.” In.

Wang, Hanlin, and Michael Rubenstein. 2020. “Shape Formation in Homogeneous Swarms Using Local Task Swapping.” IEEE Transactions on Robotics, 1–16. https://doi.org/10.1109/TRO.2020.2967656.

Wolpert, David H. 2004. “Information Theory - The Bridge Connecting Bounded Rational Game Theory and Statistical Physics,” February. https://arxiv.org/abs/cond-mat/0402508v1.

Wolpert, David H. 2006. “Advances in Distributed Optimization Using Probability Collectives.” Advances in Complex Systems 9.

Wolpert, David H., and Kagan Tumer. 1999. “An Introduction to Collective Intelligence.” arXiv:cs/9908014, August. http://arxiv.org/abs/cs/9908014.

Wolpert, David H, Stefan R Bieniawski, and Dev G Rajnarayan. 2011. “Probability Collectives in Optimization.”

Wolpert, David H, and John W Lawson. 2002. “Designing Agent Collectives for Systems with Markovian Dynamics.” In, 1066–73. https://doi.org/10.1145/545056.545074.

Wolpert, David H, Kevin R Wheeler, and Kagan Tumer. 1999. “General Principles of Learning-Based Multi-Agent Systems.” In, 77–83. https://doi.org/10.1145/301136.301167.

———. 2000. “Collective Intelligence for Control of Distributed Dynamical Systems.” EPL (Europhysics Letters) 49: 708. https://doi.org/10.1209/epl/i2000-00208-x.

Ye, Yinyu. 2008. “A Path to the Arrow–Debreu Competitive Market Equilibrium.” Mathematical Programming 111 (1-2): 315–48. https://doi.org/10.1007/s10107-006-0065-5.

Zhang, Rui, and Quanyan Zhu. 2017. “Game-Theoretic Design of Secure and Resilient Distributed Support Vector Machines with Adversaries.” arXiv:1710.04677 [cs, Stat], October. http://arxiv.org/abs/1710.04677.