Solving Overlapping Coalition Structure Generation in Task-Based Settings

Abstract

The overlapping coalition structure generation problem (OCSGP) is a challenging computational problem in multi-agent systems. It focuses on selecting possibly overlapping coalitions from a set of agents to maximize the social welfare of all coalitions while containing all agents. However, in practical applications, coalitions may be formed to selectively respond to tasks from a pool of potential tasks assigned to agents. Consequently, this study considers OCSGP in a task-based setting, where each agent has finite resources and can only respond to tasks of interest, and each coalition can only take on mutually disjoint subsets of tasks. Specifically, we first present a model of the task-based OCSGP and investigate its computational complexity. Our theoretical results demonstrate that this specific OCSGP remains intractable even under restrictive assumptions. Subsequently, we develop a generic evolutionary algorithm framework (EAF) to find an approximately optimal overlapping coalition structure (OCS) in time quartic polynomial in the size of the instance. Particularly, we devise a specific solution-repair based heuristic of cubic time complexity to generate a feasible OCS. Finally, we compare the proposed EAF with a task-oriented heuristic and a hybrid algorithm for OCSGP, and examine its applicability in the pursuit-evasion problem. The experimental results reveal that the proposed EAF exhibits superior performance in finding feasible OCSs and demonstrates flexible adaptability to problem size and resource status.