Proceedings

Co-Learning of Strategy and Structure Achieves Full Cooperation in Complex Networks with Dynamical Linking

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 72-80.

https://doi.org/10.24963/ijcai.2025/9

Abstract

Social dilemmas are an important benchmark to study the emergence of cooperation among autonomous learning agents and impressive results were recently achieved in two-player games by reinforcement learning agents equipped with a partner selection module. However, the same cannot be said for games on networks. When surrounded by many other defectors, cooperators suffer harsher punishments and find it hard to replicate, making mass defection quickly take over. The frameworks studied so far for the emergence of cooperation in social dilemmas on networks have shown the key role of dynamical linking, the capacity of agents to select their own neighbours, but they have also relied on hard-wired heuristics, such as imitation dynamics, designed to favour cooperation. In this paper, we remove this constraint and study a population of agents that can autonomously learn whether to cooperate or defect with any of their neighbours in a social dilemma, as well as whether to form or sever social ties with others. Building on a seminal framework for the emergence of cooperation in complex social networks with dynamical linking, we implement our agents as Sarsa learners with Boltzmann exploration and equipped with partner selection actions. We show, for the first time, that these agents can reach a fully cooperative society without requiring ad-hoc heuristics. In doing so, we confirm the fundamental role of timescales, the relative speed at which strategy and structure updates occur, for the emergence of cooperation, highlighting the intricate interplay between network dynamics and decision-making in agent societies.

  1. [Anastassacos et al., 2020] Nicolas Anastassacos, Stephen Hailes, and Mirco Musolesi. Partner selection for the emergence of cooperation in multi-agent systems using re- inforcement learning. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, pages 7047-7054. AAAI Press, 2020.
  2. [Axelrod, 1984] Robert Axelrod. The Evolution of Coopera- tion. Basic, New York, 1984.
  3. [Bara et al., 2022] Jacques Bara, Paolo Turrini, and Giulia Andrighetto. Enabling imitation-based cooperation in dy- namic social networks. Auton. Agents Multi Agent Syst., 36(2):34, 2022.
  4. [Bloembergen et al., 2015] Daan Bloembergen, Karl Tuyls, Daniel Hennes, and Michael Kaisers. Evolutionary dy- namics of multi-agent learning: A survey. J. Artif. Intell. Res., 53:659-697, 2015.
  5. [Börgers and Sarin, 1997] Tilman Börgers and Rajiv Sarin. Learning through reinforcement and replicator dynamics. Journal of economic theory, 77(1):1-14, 1997.
  6. [Fatima et al., 2024] Shaheen Fatima, Nicholas R. Jennings, and Michael J. Wooldridge. Learning to resolve social dilemmas: A survey. J. Artif. Intell. Res., 79:895-969, 2024.
  7. [Foley et al., 2018] Michael Foley, Patrick Forber, Rory Smead, and Christoph Riedl. Conflict and convention in dynamic networks. Journal of The Royal Society Inter- face, 15(140):20170835, 2018.
  8. [Fulker et al., 2021] Zachary Fulker, Patrick Forber, Rory Smead, and Christoph Riedl. Spite is contagious in dy- namic networks. Nature Communications, 12(1):260, 2021.
  9. [Gilbert, 1995] Nigel Gilbert. Emergence in social simula- tion. In Nigel Gilbert and Rosaria Conte, editors, Artificial Societies: The Computer Simulation Of Social Life. Rout- ledge, 1995.
  10. [Leung and Turrini, 2024] Chin-wing Leung and Paolo Tur- rini. Learning partner selection rules that sustain cooper- ation in social dilemmas with the option of opting out. In Mehdi Dastani, Jaime Simão Sichman, Natasha Alechina, and Virginia Dignum, editors, Proceedings of the 23rd In- ternational Conference on Autonomous Agents and Mul- tiagent Systems, AAMAS 2024, Auckland, New Zealand, May 6-10, 2024, pages 1110-1118. ACM, 2024.
  11. [Leung et al., 2024] Chin-wing Leung, Tom Lenaerts, and Paolo Turrini. To promote full cooperation in social dilem- mas, agents need to unlearn loyalty. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI 2024, Jeju, South Korea, August 3-9, 2024, pages 111-119. ijcai.org, 2024. IJCAI
  12. [Nowak, 2006] Martin A. Nowak. Five rules for the evolu- tion of cooperation. Science, 314(5805):1560-1563, 2006.
  13. [Pacheco et al., 2006] Jorge M Pacheco, Arne Traulsen, and Martin A Nowak. Coevolution of strategy and structure in complex networks with dynamical linking. Physical re- view letters, 97(25):258103, 2006.
  14. [Pérolat et al., 2017] Julien Pérolat, Joel Z. Leibo, Vinícius Flores Zambaldi, Charles Beattie, Karl Tuyls, and Thore Graepel. A multi-agent reinforcement learning model of common-pool resource appropriation. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Ro- man Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 3643-3652, 2017.
  15. [Perreau de Pinninck et al., 2010] Adrian Perreau de Pin- ninck, Carles Sierra, and Marco Schorlemmer. A multi- agent network for peer norm enforcement. Autonomous Agents and Multi-Agent Systems, 21(3):397-424, Nov 2010.
  16. [Pujol et al., 2002] Josep M. Pujol, Ramon Sangüesa, and Jordi Delgado. Extracting reputation in multi agent sys- tems by means of social network topology. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems: Part 1, AAMAS '02, page 467-474, New York, NY, USA, 2002. Association for Computing Machinery.
  17. [Rand et al., 2011] David G. Rand, Samuel Arbesman, and Nicholas A. Christakis. Dynamic social networks promote cooperation in experiments with humans. Proceedings of the National Academy of Sciences, 108(48):19193-19198, 2011.
  18. [Roca et al., 2009] Carlos P Roca, José A Cuesta, and Angel Sánchez. Evolutionary game theory: Temporal and spatial effects beyond replicator dynamics. Physics of life reviews, 6(4):208-249, 2009.
  19. [Sabater and Sierra, 2002] Jordi Sabater and Carles Sierra. Reputation and social network analysis in multi-agent sys- tems. In Proceedings of the first international joint confer- ence on Autonomous agents and multiagent systems part 1 -AAMAS '02, New York, New York, USA, 2002. ACM Press.
  20. [Salazar et al., 2011] Norman Salazar, Juan A. Rodriguez- Aguilar, Josep Ll. Arcos, Ana Peleteiro, and Juan C. Burguillo-Rial. Emerging cooperation on complex net- works. In The 10th International Conference on Au- tonomous Agents and Multiagent Systems -Volume 2, AA- MAS '11, page 669-676, Richland, SC, 2011. Interna- tional Foundation for Autonomous Agents and Multiagent Systems.
  21. [Santos and Pacheco, 2005] Francisco C Santos and Jorge M Pacheco. Scale-free networks provide a unifying frame- work for the emergence of cooperation. Physical review letters, 95(9):098104, 2005.
  22. [Santos et al., 2006a] Francisco C. Santos, Jorge M. Pacheco, and Tom Lenaerts. Cooperation prevails when individuals adjust their social ties. PLoS Comput. Biol., 2(10), 2006.
  23. [Santos et al., 2006b] Francisco C. Santos, Jorge M. Pacheco, and Tom Lenaerts. Evolutionary dynamics of social dilemmas in structured heterogeneous popula- tions. Proceedings of the National Academy of Sciences, 103(9):3490-3494, 2006.
  24. [Santos et al., 2018] Fernando P. Santos, Jorge M. Pacheco, and Francisco C. Santos. Social norms of cooperation with costly reputation building. In Sheila A. McIlraith and Kil- ian Q. Weinberger, editors, Proceedings of the AAAI Con- ference on Artificial Intelligence, pages 4727-4734. AAAI Press, 2018.
  25. [Segbroeck et al., 2009] Sven Van Segbroeck, Francisco C. Santos, Ann Nowé, Jorge M. Pacheco, and Tom Lenaerts. The coevolution of loyalty and cooperation. In Proceed- ings of the IEEE Congress on Evolutionary Computation, CEC 2009, Trondheim, Norway, 18-21 May, 2009, pages 500-505. IEEE, 2009.
  26. [Segbroeck et al., 2010] Sven Van Segbroeck, Steven de Jong, Ann Nowé, Francisco C. Santos, and Tom Lenaerts. Learning to coordinate in complex networks. Adapt. Behav., 18(5):416-427, 2010.
  27. [Sutton and Barto, 2018] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
  28. [Trivedi et al., 2023] Rakshit Trivedi, Akbir Khan, Jesse Clifton, Lewis Hammond, Edgar A Duéñez-Guzmán, Di- pam Chakraborty, John P Agapiou, Jayd Matyas, Sasha Vezhnevets, Barna Pásztor, et al. Melting pot contest: Charting the future of generalized cooperative intelli- gence. In The Thirty-eight Conference on Neural Informa- tion Processing Systems Datasets and Benchmarks Track, 2023.
  29. [Tuyls et al., 2003] Karl Tuyls, Katja Verbeeck, and Tom Lenaerts. A selection-mutation model for q-learning in multi-agent systems. In The Second International Joint Conference on Autonomous Agents & Multiagent Systems, AAMAS 2003, July 14-18, 2003, Melbourne, Victoria, Aus- tralia, Proceedings, pages 693-700. ACM, 2003.
  30. [Wang et al., 2012] Jing Wang, Siddharth Suri, and Dun- can J. Watts. Cooperation and assortativity with dynamic partner updating. Proceedings of the National Academy of Sciences, 109(36):14363-14368, 2012.
  31. [Zhang et al., 2016] Bo-Yu Zhang, Song-Jia Fan, Cong Li, Xiu-Deng Zheng, Jian-Zhang Bao, Ross Cressman, and Yi Tao. Opting out against defection leads to stable co- existence with cooperation. Scientific reports, 6:35902, October 2016.
  32. [Zheng et al., 2017] Xiu-Deng Zheng, Cong Li, Jie-Ru Yu, Shi-Chang Wang, Song-Jia Fan, Bo-Yu Zhang, and Yi Tao. A simple rule of direct reciprocity leads to the stable co- existence of cooperation and defection in the prisoner's dilemma game. Journal of Theoretical Biology, 420:12- 17, 2017.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards