IIAE CONFERENCE SYSTEM, The 3rd International Conference on Industrial Application Engineering 2015 (ICIAE2015)

Font Size: 
Coalition Lattice: A Data Structure considering Robustness for Robust Coalition Structure Generation Problem
Katsuya Nakano, Shun Shiramatsu, Tadachika Ozono, Toramatsu Shintani

Last modified: 2015-02-05


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. The set of coalitions is a coalition structure. 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 CSG focused on the robustness of coalition structures. The robustness of coalition structures 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 to solve an RCSG problem. Our method finds the optimal coalition structure by 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.


robust coalition structure generation; robustness of coalitions; partial linear model; coalition lattice

Full Text: PDF