research-article

Fostering Cooperation through Dynamic Coalition Formation and Partner Switching

Authors:

Juan C. Burguillo,

Josep Ll. Arcos,

Juan A. Rodriguez-AguilarAuthors Info & Claims

ACM Transactions on Autonomous and Adaptive Systems (TAAS), Volume 9, Issue 1

Article No.: 1, Pages 1 - 31

https://doi.org/10.1145/2567928

Published: 01 March 2014 Publication History

Abstract

In this article we tackle the problem of maximizing cooperation among self-interested agents in a resource exchange environment. Our main concern is the design of mechanisms for maximizing cooperation among self-interested agents in a way that their profits increase by exchanging or trading with resources. Although dynamic coalition formation and partner switching (rewiring) have been shown to promote the emergence and maintenance of cooperation for self-interested agents, no prior work in the literature has investigated whether merging both mechanisms exhibits positive synergies that lead to increase cooperation even further. Therefore, we introduce and analyze a novel dynamic coalition formation mechanism, that uses partner switching, to help self-interested agents to increase their profits in a resource exchange environment. Our experiments show the effectiveness of our mechanism at increasing the agents’ profits, as well as the emergence of trading as the preferred behavior over different types of complex networks.

References

[1]

Adamic, L. A. and Huberman, B. A. 2000. Power-law distribution of the World Wide Web. Science 287, 5461, 2115.

[2]

Aumann, R. J. 1959. Acceptable points in general cooperative n-person games. In Contribution to the Theory of Game IV, Annals of Mathematical Study 40, R. D. Luce and A. W. Tucker Eds., University Press, 287--324.

[3]

Axelrod, R. 1997. The Complexity of Cooperation: Agent-Based Models of Competition and Collaboration 1st Ed. Princeton University Press.

[4]

Axelrod, R. M. 1984. The Evolution of Cooperation. Basic Books, New York.

[5]

Aziz, H., Brandt, F., and Seedig, H. G. 2011. Stable partitions in additively separable hedonic games. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’11). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 183--190.

Digital Library

[6]

Bachrach, Y. and Rosenschein, J. S. 2008. Coalitional skill games. In Proceedings of the 7th International Joint Conference on Autonomous agents and Multiagent Systems (AAMAS’08). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1023--1030.

Digital Library

[7]

Batagelj, V. and Mrvar, A. 2003. Pajek - Analysis and visualization of large networks. In Proceedings of the 9th International Symposium on Graph Drawing. Lecture Notes in Computer Science, vol. 2265, 77--103.

[8]

Bazzan, A., Peleteiro, A., and Burguillo, J. 2011. Learning to cooperate in the iterated prisoner’s dilemma by means of social attachments. J. Braz. Comp. Soc. 17, 3, 163--174.

[9]

Brandt, F., Conitzer, V., and Endriss, U. 2013. Computational social choice. In Multiagent Systems, G. Weiss Ed., MIT Press, 213--283.

[10]

Burguillo, J. and Peleteiro, A. 2010. Ownership and trade in spatial evolutionary memetic games. In Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN’10). Springer, 455--464.

Digital Library

[11]

Burguillo-Rial, J. 2009. A memetic framework for describing and simulating spatial prisoner’s dilemma with coalition formation. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’09). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 441--448.

Digital Library

[12]

Chalkiadakis, G., Elkind, E., Markakis, E., Polukarov, M., and Jennings, N. 2010. Cooperative games with overlapping coalitions. J. Artif. Intell. Research 39, 179--216.

Digital Library

[13]

Chevaleyre, Y., Endriss, U., Lang, J., and Maudet, N. 2007. A short introduction to computational social choice. In Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science. J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, and F. Plasil Eds., Lecture Notes in Computer Science, vol. 4362, Springer, 51--69.

Digital Library

[14]

Doran, J. E., Franklin, S., Jennings, N. R., and Norman, T. J. 1997. On cooperation in multi-agent systems. Knowledge Engin. Rev. 12, 309--314.

Digital Library

[15]

Eguiluz, V. M., Zimmermann, M. G., Cela-Conde, C. J., and San Miguel, M. 2005. Cooperation and the emergence of role differentiation in the dynamics of social networks. Amer. J. Sociol. 110, 4, 977.

[16]

Fu, F., Wu, T., and Wang, L. 2009. Partner switching stabilizes cooperation in coevolutionary prisoner’s dilemma. Phys. Rev. E 79, 3, 036101.

[17]

Fu, F., Tarnita, C. E., Christakis, N. A., Wang, L., Rand, D. G., and Nowak, M. A. 2012. Evolution of in-group favoritism. Scientific Rep. 2, 480.

[18]

Griffiths, N. and Luck, M. 2010. Changing neighbours: Improving tag-based cooperation. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’10). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 249--256.

Digital Library

[19]

Gross, T. and Blasius, B. 2008. Adaptive coevolutionary networks: A review. J. R. Soc. Interface 5, 20, 259--271.

[20]

Hogg, T. 1995. Social dilemmas in computational ecosystems. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI’95). Morgan Kaufmann, San Mateo, CA, 711--716.

Digital Library

[21]

Jackson, M. O., Demange, G., Goyal, S., and Nouwel, A. V. D. 2003. A survey of models of network formation: Stability and efficiency. In Group Formation in Economics: Networks, Clubs and Coalitions, Cambridge University Press.

[22]

Kniesburges, S., Koutsopouplos, A., and Scheideler, C. 2012. A self-stabilization process for small-world networks. In Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium. 1261--1271.

Digital Library

[23]

Langer, P., Nowak, M., and Hauert, C. 2008. Spatial invasion of cooperation. J. Theor. Biol. 250, 4, 634--641.

[24]

Maynard Smith, J. and Price, G. R. 1973. The logic of animal conflict. Nature 246, 5427, 15--18.

[25]

Narendra, K. S. and Thathachar, M. A. L. 1989. Learning Automata: An Introduction. Prentice-Hall, Inc., Upper Saddle River, NJ.

Digital Library

[26]

Newman, M. E. J. 2003. The structure and function of complex networks. SIAM Rev. 45, 2, 167--256.

Digital Library

[27]

Nguyen, D.-T. and Ishida, Y. 2009. Spatial dilemma strategies of intelligent agents: Coalition formation in environmental game. In Proceedings of the International Conference on Knowledge and Systems Engineering (KSE’09). IEEE, 126--129.

Digital Library

[28]

Nowak, M. A. and May, R. M. 1992. Evolutionary games and spatial chaos. Nature 359, 6398, 826--829.

[29]

Nowak, M. A. and May, R. M. 1993. The spatial dilemmas of evolution. Int. J. Bifurcation Chaos 3, 1, 35--78.

[30]

Ostrom, E. 1990. Governing the Commons: The Evolution of Institutions for Collective Action. Political Economy of Institutions and Decisions, Cambridge University Press.

[31]

Pacheco, J. M., Traulsen, A., and Nowak, M. A. 2006. Coevolution of strategy and structure in complex networks with dynamical linking. Phys. Rev. Lett. 97, 25, 258103+.

[32]

Pastor-Satorras, R. and Vespignani, A. 2001. Epidemic dynamics and endemic states in complex networks. Phys. Rev. E 63, 066117.

[33]

Peleteiro, A., Burguillo, J., and Bazzan, A. 2011. Emerging cooperation in the spatial IPD with reinforcement learning and coalitions. In Intelligent Decision Systems in Large-Scale Distributed Environment, Studies in Computational Intelligence, Springer.

[34]

Peleteiro, A., Burguillo, J., and Bazzan, A. 2012. How coalitions enhance cooperation in the IPD over complex networks. In Proceedings of the 3rd Brazilian Workshop on Social Simulation. IEEE.

Digital Library

[35]

Perc, M. and Szolnoki, A. 2010. Coevolutionary games--A mini review. Biosystems 99, 2, 109--125.

[36]

Pitt, J., Schaumeier, J., and Artikis, A. 2011. The axiomatisation of socio-economic principles for self-organising systems. In Proceedings of the IEEE 6th International Conference on Self-Adaptive and Self-Organizing Systems. 138--141.

Digital Library

[37]

Pitt, J., Schaumeier, J., and Artikis, A. 2012a. Axiomatization of socio-economic principles for self-organizing institutions: Concepts, experiments and challenges. ACM Trans. Auton. Adapt. Syst. 7, 4, Article 39.

Digital Library

[38]

Pitt, J., Schaumeier, J., Busquets, D., and Macbeth, S. 2012b. Self-organising common-pool resource allocation and canons of distributive justice. In Proceedings of the IEEE 6th International Conference on Self-Adaptive and Self-Organizing Systems. 119--128.

Digital Library

[39]

Pujol, J. M., Delgado, J., Sangesa, R., and Flache, A. 2005. The role of clustering on the emergence of efficient social conventions. In Proceedings of the International Joint Conference on Artificial Intelligence. 965--970.

Digital Library

[40]

Rahwan, T. and Jennings, N. 2008a. Coalition structure generation: Dynamic programming meets anytime optimisation. In Proceedings of the 23rd Conference on Artificial Intelligence. 156--161.

Digital Library

[41]

Rahwan, T. and Jennings, N. R. 2008b. An improved dynamic programming algorithm for coalition structure generation. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multi-agent Systems (AAMAS’08). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1417--1420.

Digital Library

[42]

Rahwan, T., Ramchurn, S., Jennings, N., and Giovannucci, A. 2009. An anytime algorithm for optimal coalition structure generation. J. Artif. Intell. Research 34, 521--567.

Digital Library

[43]

Rahwan, T., Michalak, T., and Jennings, N. R. 2012. A hybrid algorithm for coalition structure generation. In Proceedings of the 26th Conference on Artificial Intelligence (AAAI’12). 1443--1449.

[44]

Reka, A. and Barabási, A. 2002. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47--97.

[45]

Salazar, N., Rodriguez-Aguilar, J. A., Arcos, J. L., Peleteiro, A., and Burguillo-Rial, J. C. 2011. Emerging cooperation on complex networks. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’11). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 669--676.

Digital Library

[46]

Sandholm, T., Larson, K., Andersson, M., Shehory, O., and Tohmé, F. 1999. Coalition structure generation with worst case guarantees. Artif. Intell. 111, 1--2, 209--238.

Digital Library

[47]

Seo, Y.-G., Cho, S.-B., and Yao, X. 1999. Emergence of cooperative coalition in nipd game with localization of interaction and learning. In Proceedings of the Congress on Evolutionary Computation (CEC’99).

[48]

Seo, Y.-G., Cho, S.-B., and Yao, X. 2000. Exploiting coalition in co-evolutionary learning. In Proceedings of the Congress on Evolutionary Computation (CEC’00). 1268--1275

[49]

Service, T. C. and Adams, J. A. 2011. Constant factor approximation algorithms for coalition structure generation. Autonomous Agents Multi-Agent Syst. 23, 1, 1--17.

Digital Library

[50]

Shehory, O. and Kraus, S. 1993. Coalition formation among autonomous agents: Strategies and complexity. In Proceedings of the Conference on Modelling Autonomous Agents in a MultiAgent World. 56--72.

[51]

Shehory, O. and Kraus, S. 1995. Task allocation via coalition formation among autonomous agents. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI’95). Morgan Kaufmann Publishers Inc., San Francisco, CA, 655--661.

Digital Library

[52]

Shehory, O. and Kraus, S. 1996. Formation of overlapping coalitions for precedence-ordered task execution among autonomous agents. In Proceedings of the 2nd International Conference on Multiagent Systems (ICMAS’96). 330--337.

[53]

Shehory, O. and Kraus, S. 1998. Methods for task allocation via agent coalition formation. Artif. Intell. 101, 1, 165--200.

Digital Library

[54]

Shehory, O., Sycara, K., and Jha, S. 1998. Multi-agent coordination through coalition formation. In Intelligent Agents IV Agent Theories, Architectures, and Languages, M. Singh, A. Rao, and M. Wooldridge Ed., Lecture Notes in Computer Science, vol. 1365, Springer, 143--154.

[55]

Shrot, T., Aumann, Y., and Kraus, S. 2010. On agent types in coalition formation problems. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’10). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 757--764.

Digital Library

[56]

Tanimoto, K. 2002. Coalition formation interacted with transitional state of environment. In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics.

[57]

Voice, T., Ramchurn, S. D., and Jennings, N. R. 2012. On coalition formation with sparse synergies. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’12). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 223--230.

Digital Library

[58]

Watts, D. J. and Strogatz, S. 1998. Collective dynamics of ‘small-world’ networks. Nature 393, 6684, 440--442.

[59]

Wooldridge, M. and Dunne, P. E. 2006. On the computational complexity of coalitional resource games. Artif. Intell. 170, 10, 835--871.

Digital Library

[60]

Yee, K. 2003. Ownership and trade from evolutionary games. Int. Rev. Law. Econ. 23, 2, 183--197.

[61]

Zimmermann, M. G., Eguiluz, V. M., and San Miguel, M. 2004. Coevolution of dynamical states and interactions in dynamic networks. Phys. Rev. E 69, 065102.

Cited By

Gergely M(2022)Finding Cooperation in the N-Player Iterated Prisoner's Dilemma with Deep Reinforcement Learning Over Dynamic Complex NetworksProcedia Computer Science10.1016/j.procs.2022.09.101207(465-474)Online publication date: 2022
https://doi.org/10.1016/j.procs.2022.09.101
Su ZZhang GYue FHe JLi MLi BYao X(2020)Finding the Largest Successful Coalition under the Strict Goal Preferences of AgentsACM Transactions on Autonomous and Adaptive Systems10.1145/341237014:4(1-33)Online publication date: 13-Sep-2020
https://doi.org/10.1145/3412370
Chowdhary KChowdhary K(2020)Intelligent AgentsFundamentals of Artificial Intelligence10.1007/978-81-322-3972-7_16(471-505)Online publication date: 5-Apr-2020
https://doi.org/10.1007/978-81-322-3972-7_16
Show More Cited By

Index Terms

Fostering Cooperation through Dynamic Coalition Formation and Partner Switching
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems

Recommendations

Coalition formation through motivation and trust
AAMAS '03: Proceedings of the second international joint conference on Autonomous agents and multiagent systems

Cooperation is the fundamental underpinning of multi-agent systems, allowing agents to interact to achieve their goals. Where agents are self-interested, or potentially unreliable, there must be appropriate mechanisms to cope with the uncertainty that ...
Promoting Cooperation and Fairness in Self-interested Multi-Agent Systems
ICAART 2016: Proceedings of the 8th International Conference on Agents and Artificial Intelligence

The issue of collaboration amongst agents in a multi-agent system (MAS) represents a challenging research problem. In this paper we focus on a form of cooperation known as coalition formation. The problem we consider is how to facilitate the formation ...
Experiments on robustness and deception in a coalition formation model: Research Articles
Coordination Models and Systems

In the last few years coalition formation algorithms have been proposed as a possible way of modeling autonomous agent cooperation in multi-agent systems. This work is based on a previously proposed coalition formation model founded on game theory for a ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Autonomous and Adaptive Systems

ACM Transactions on Autonomous and Adaptive Systems Volume 9, Issue 1

March 2014

121 pages

ISSN:1556-4665

EISSN:1556-4703

DOI:10.1145/2597760

Editors:
Manish Parashar
Rutgers University, USA
,
Franco Zambonelli
University of Modena e Reggio Emilia, Italy

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2014

Accepted: 01 January 2014

Revised: 01 September 2013

Received: 01 October 2012

Published in TAAS Volume 9, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

EVE
COR
AT
Generalitat de Catalunya
MECER
Formación de Profesorado Universitario (FPU)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
443
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gergely M(2022)Finding Cooperation in the N-Player Iterated Prisoner's Dilemma with Deep Reinforcement Learning Over Dynamic Complex NetworksProcedia Computer Science10.1016/j.procs.2022.09.101207(465-474)Online publication date: 2022
https://doi.org/10.1016/j.procs.2022.09.101
Su ZZhang GYue FHe JLi MLi BYao X(2020)Finding the Largest Successful Coalition under the Strict Goal Preferences of AgentsACM Transactions on Autonomous and Adaptive Systems10.1145/341237014:4(1-33)Online publication date: 13-Sep-2020
https://doi.org/10.1145/3412370
Chowdhary KChowdhary K(2020)Intelligent AgentsFundamentals of Artificial Intelligence10.1007/978-81-322-3972-7_16(471-505)Online publication date: 5-Apr-2020
https://doi.org/10.1007/978-81-322-3972-7_16
Li MLi KLiu JLiao XZhou X(2019)New concept to improve cooperation in dynamic complex networkNeurocomputing10.1016/j.neucom.2018.11.080332(80-90)Online publication date: Mar-2019
https://doi.org/10.1016/j.neucom.2018.11.080
Morris-Martin ADe Vos MPadget J(2019)Norm emergence in multiagent systems: a viewpoint paperAutonomous Agents and Multi-Agent Systems10.1007/s10458-019-09422-033:6(706-749)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1007/s10458-019-09422-0
Skiba GStarzec MByrski ARycerz KKisiel-Dorohinicki MTurek WKrzywicki DLenaerts TBurguillo J(2018)Flexible asynchronous simulation of iterated prisoner’s dilemma based on actor modelSimulation Modelling Practice and Theory10.1016/j.simpat.2017.12.01083(75-92)Online publication date: Apr-2018
https://doi.org/10.1016/j.simpat.2017.12.010
Ren YChen XWang ZShi BCui GWu TChoo K(2018)Neighbor-considered migration facilitates cooperation in prisoners dilemma gamesApplied Mathematics and Computation10.1016/j.amc.2017.11.043323:C(95-105)Online publication date: 15-Apr-2018
https://dl.acm.org/doi/10.1016/j.amc.2017.11.043
Starzec GStarzec MByrski AKisiel-Dorohinicki MBurguillo JLenaerts T(2018)Towards Large-Scale Optimization of Iterated Prisoner Dilemma StrategiesTransactions on Computational Collective Intelligence XXXII10.1007/978-3-662-58611-2_4(167-183)Online publication date: 19-Dec-2018
https://doi.org/10.1007/978-3-662-58611-2_4
Mali GMisra S(2017)Topology Management-Based Distributed Camera Actuation in Wireless Multimedia Sensor NetworksACM Transactions on Autonomous and Adaptive Systems10.1145/301443012:1(1-33)Online publication date: 11-Apr-2017
https://dl.acm.org/doi/10.1145/3014430
Blanchini FCasagrande DGiordano GViaro U(2016)A switched system approach to dynamic race modellingNonlinear Analysis: Hybrid Systems10.1016/j.nahs.2015.12.00621(37-48)Online publication date: Aug-2016
https://doi.org/10.1016/j.nahs.2015.12.006
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents