A Synergy Coalition Group based Dynamic Programming Algorithm for Coalition Formation

Riley, L, Atkinson, K ORCID: 0000-0002-5683-4106, Dunne, P ORCID: 0000-0002-6033-3742 and Payne, T ORCID: 0000-0002-0106-8731 (2016) A Synergy Coalition Group based Dynamic Programming Algorithm for Coalition Formation. In: 2016 International Conference on Autonomous Agents & Multiagent Systems, Singapore.

Text aamas2016v11.pdf - Author Accepted Manuscript Download (275kB)

Abstract

Coalition formation in characteristic function games entails agents partitioning themselves into a coalition structure and assigning the numeric rewards of each coalition via a payoff vector. Various coalition structure generation algorithms have been proposed that guarantee that an optimal coalition structure is found. We present the Synergy Coalition Group-based Dynamic Programming (SCG-DP) algorithm that guarantees that an optimal coalition structure and a least core stable payoff vector is found. This is completed by extending the existing results for the Synergy Coalition Group (SCG) representation to show that only coalitions in the SCG are needed to find a weak-least core stable payoff vector. The SCG-DP algorithm builds on this result by performing only the search operations necessary to guarantee that coalitions in the SCG of the given characteristic function game are found. The number of operations required is significantly less for many coalition-value distributions compared to the original Dynamic Programming (DP) algorithm [34] that finds an optimal coalition structure (e.g. only ∼60% of DP's coalition lookup operations are performed in SCG-DP for 18 agents using a normal coalition-value distribution). Our experimental results show that a lower bound for these operations in SCG-DP converges onto 50%. This is an increase on the ∼33% bound of the optimal dynamic programming (ODP) algorithm [14], but ODP does not search for a stable solution.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	Coalition Formation, Dynamic Programming, Synergy Coalition Groups, Cooperative Game Theory
Depositing User:	Symplectic Admin
Date Deposited:	26 Sep 2016 08:40
Last Modified:	19 Jan 2023 07:36
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3001450