Computing desirable partitions in additively separable hedonic games

摘要

An important aspect in systems of multiple autonomous agents is the exploitation of synergies via coalition formation. Additively separable hedonic games are a fundamental class of coalition formation games in which each player has a value for any other player and the value of a coalition to a particular player is simply the sum of the values he assigns to the members of his coalition. In this paper, we consider a number of solution concepts from cooperative game theory, welfare theory, and social choice theory as criteria for desirable partitions in hedonic games. We then conduct a detailed computational analysis of computing, checking the existence of, and verifying stable, fair, optimal, and popular partitions for additively separable hedonic games.