Coalition Structure Generation with Priority Order of Agent Types
Tenda Okimoto, Katsutoshi Hirayama · 2024
Coalition Structure Generation (CSG) is a fundamental problem that can formalize various applications related to multi-agent cooperation. CSG involves partitioning a set of agents into coalitions so that the social surplus (i.e. the sum of the values of all coalitions) is maximized. In a traditional CSG, since the value of a coalition is assumed to be given by a characteristic function, the representation size for it becomes exponential in the number of agents. In order to solve this problem, several compact representation schemes for a characteristic function have been proposed. Agent Type based Coalition Structure Generation (CSGt) is a CSG where a characteristic function is compactly represented by utilizing the agent types. When we apply the CSGtto real world problems, it is natural to consider the priority of agent types. In this paper, the focus is laid on the Priority Order of Agent Types based Coalition Structure Generation (PO-CSGt) problem. A formal framework for the PO-CSGtis first defined. Furthermore, two novel solution criteria called Pareto optimal and lexicographically Pareto optimal muster lists for the PO-CSGtare provided. In the experiments, the number of Pareto optimal and lexicographically Pareto optimal muster lists of PO-CSGtproblems are reported in the number of benchmarks.