Roles and Teams Hedonic Game

Abstract. We introduce a new variant of hedonic coalition formation games in which agents have two levels of preference on their own coali-tions: preference on the set of “roles ” that makes up the coalition, and preference on their own role within the coalition. We define several sta-bility notions and optimization problems for this model. We prove the hardness of the decision problems related to our optimization criteria and show easiness of finding individually stable partitions. We introduce a heuristic optimizer for coalition formation in this setting. We evalu-ate results of the heuristic optimizer and the results of local search for individually stable partitions with respect to brute-force MaxSum and MaxMin solvers