Abstract
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 of a coalition in a competitive marketplace, where self-interested agents must cooperate by forming a coalition in order to complete a task. Agents must reach a consensus on both the monetary amount to charge for completion of a task as well as the distribution of the required workload. The problem is further complicated because different subtasks have various degrees of difficulty and each agent is uncertain of the payment another agent requires for performing specific subtasks. These complexities, coupled with the self-interested nature of agents, can inhibit or even prevent the formation of coalitions in such a real-world setting. As a solution, a novel auction-based protocol called ACCORD is proposed here. ACCORD manages real-world complexities by promoting the adoption of cooperative behaviour amongst agents. Through extensive empirical analysis we analyse the ACCORD protocol and demonstrate that cooperative and fair behaviour is dominant and any agents deviating from this behaviour perform less well over time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Wooldridge, M.: Computational aspects of cooperative game theory. In: O’Shea, J., Nguyen, N.T., Crockett, K., Howlett, R.J., Jain, L.C. (eds.) KES-AMSTA 2011. LNCS, vol. 6682, pp. 1–1. Springer, Heidelberg (2011)
Sim, K.M.: Agent-based cloud computing. IEEE Trans. Serv. Comput. 5(4), 564–577 (2012)
Ye, D., Zhang, M., Sutanto, D.: Self-adaptation-based dynamic coalition formation in a distributed agent network: a mechanism and a brief survey. Parallel Distrib. Sys. 24(5), 1042–1051 (2013)
Vassileva, J., Breban, S., Horsch, M.: Agent reasoning mechanism for long-term coalitions based on decision making and trust. Comput. Intell. 18(4), 583–595 (2002)
Sen S., Dutta, P.: Searching for optimal coalition structures. In: Proceedings Fourth International Conference on MultiAgent Systems, pp. 287–292 (2000)
Bachrach, Y., Kohli, P., Kolmogorov, V., Zadimoghaddam, M.: Optimal coalition structure generation in cooperative graph games finding the optimal coalitional structure. In: Twenty-Seventh AAAI Conference on Artificial Intelligence, pp. 81–87 (2013)
Rahwan, T., Ramchurn, S.: An anytime algorithm for optimal coalition structure generation. J. Artif. Intell. 34, 521–567 (2009)
Iwasaki, A., Ueda, S., Yokoo, M.: Finding the core for coalition structure utilizing dual solution. In: IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT), pp. 114–121 (2013)
Dan, W., Cai, Y., Zhou, L., Wang, J.: A cooperative communication scheme based on coalition formation game in clustered wireless sensor networks. IEEE Trans. Wirel. Commun. 11(3), 1190–1200 (2012)
Xu, B., Zhang, R., Yu, J.: Improved multi-objective evolutionary algorithm for multi-agent coalition formation. J. Softw. 8(12), 2991–2995 (2013)
Sandholm, T., Lesser, V.: Coalitions among computationally bounded agents. Artif. Intell. (Special Issue on Economic Principles of Multi-Agent Systems) 94, 99–137 (1997)
Tošić, P.T., Ordonez, C.: Distributed protocols for multi-agent coalition formation: a negotiation perspective. In: Huang, R., Ghorbani, A.A., Pasi, G., Yamaguchi, T., Yen, N.Y., Jin, B. (eds.) AMT 2012. LNCS, vol. 7669, pp. 93–102. Springer, Heidelberg (2012)
Smirnov, A., Sheremetov, L.: Models of coalition formation among cooperative agents: the current state and prospects of research. Sci. Tech. Inf. Process. 39(5), 283–292 (2012)
Tsvetovat, M., Sycara, K.: Customer coalitions in the electronic marketplace. In: Fourth International Conference on Autonomous Agents, pp. 263–274 (2000)
Shehory, O.: Coalition formation for large-scale electronic markets. In: Proceedings of the Fourth International Conference on MultiAgent Systems, pp. 167–174 (2000)
Kraus, S., Shehory, O., Taase, G.: Coalition formation with uncertain heterogeneous information. In: Second International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1–8 (2003)
Kraus, S., Shehory, O., Taase, G.: The advantages of compromising in coalition formation with incomplete information. In: Third International Joint Conference on Autonomous Agents and MultiAgent Systems, pp. 588–595 (2004)
Ghaffarizadeh, A., Allan, V.: History based coaliton formation in hedonic conext using trust. Int. J. Artif. Intell. Appl. 4(4), 1 (2013)
Aziz, H., Brandt, F., Seedig, H.: Stable partitions in additively separable hedonic games. Auton. Agents Multiagent Sys. 1, 183–190 (2011)
Genin, T., Aknine, S.: Constraining self-interested agents to guarantee pareto optimality in multiagent coalition formation problem. In: IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, pp. 369–372 (2011)
Bellifemine, F.L., Caire, G., Greenwood, D.: Developing Multi-agent Systems with JADE, vol. 6. Wiley, Chichester (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Scully, T., Madden, M.G. (2015). Forming Coalitions in Self-interested Multi-agent Environments Through the Promotion of Fair and Cooperative Behaviour. In: Bulling, N. (eds) Multi-Agent Systems. EUMAS 2014. Lecture Notes in Computer Science(), vol 8953. Springer, Cham. https://doi.org/10.1007/978-3-319-17130-2_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-17130-2_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-17129-6
Online ISBN: 978-3-319-17130-2
eBook Packages: Computer ScienceComputer Science (R0)