Coalition Lattice: A Data Structure considering Robustness for Robust Coalition Structure Generation Problem
中野克哉, 白松俊, 大囿忠親, 新谷虎松


Forming effective coalitions is a major problem in multiagent systems. Coalition structure generation (CSG) involves partitioning a set of agents into teams, i.e. coalitions. A coalition structure is a set of coalitions. In the context of the CSG research, our goal is forming the coalition structure that maximizes the social surplus. The social surplus is the sum of utilities obtained by forming coalitions. Calculating the optimal coalition structure is time consuming, therefore recalculating the optimal coalition structure should be avoided when an agent leaves a coalition structure because of sudden reasons such as an accident or an illness. Robust coalition structure generation (RCSG) is a variant of CSG focused on the robustness of a coalition structure. The robustness of coalition structure is the property that the social surplus is kept at the maximum when any agents leave the coalition structure. We focused on the robustness of each coalition in a coalition structure to solve an RCSG problem. Our method finds the optimal coalition structure considering the robustness of each coalition in the optimal coalition structure. We proposed a coalition lattice, which is a novel data structure to represent the robustness of coalitions. The paper presents an algorithm to construct the coalition lattice from a CSG problem and the result of our evaluation.