Coalition Formation Strategies for Multiagent Hedonic Games

In a multiagent system, coalition formation is a coordination method for agents aiming to form groups of interest. In this paper, we focus on the particular context of hedonic games. In hedonic games, the objective of the agents is to form coalitions, which are groups of agents. The satisfaction of an agent depends on other members of its coalition. In this context, autonomous agents need strategical behaviors to efficiently form their coalitions. In this article, we describe two types of strategies which could be used by agents: proposal acceptance strategies, used by agents to decide to join a coalition and proposal selection strategies, based on the analysis of the history of a negotiation, used by agents to select interesting coalitions to propose to other agents. Then we present our experiments and discuss the results we have obtained. We underline that a compromise between high and low selectivity allows agents to obtain a higher probability to form coalitions with a satisfying utility. Our proposal selection strategies allow agents to reduce the number of proposals to send during the coalition formation process without losing much utility. This speeds up considerably the process.