Gathering Self-Interested People Together: a Strategic Perspective

Over the past decades, the understanding of how individuals spontaneously gather together received particular attention leading to the definition of several variants of Coalition Formation Games, including the so-called Hedonic Games. In such games, the individuals (or agents) have to be split into disjoint coalitions and express preferences only on the coalition they belong to, and not on how the others aggregate. Subsequently, the more general class of the Group Activity Selection Problem, where agents’ preferences depend also on the activity they are performing, has been introduced. In both these classes of games, the study of the existence, the computability, and the efficiency of suitable stability solution concepts as well as the elicitation of agents’ preferences through strategyproof mechanisms have been addressed. In this work, we consider both the aforementioned research directions. In particular, we put our attention on classes of games in which agents’ preferences are expressed by a utility function and we evaluate the global agents’ satisfaction in a given outcome by means of the utilitarian social welfare. Moreover, we often compare the social welfare of the considered solutions with the social optimum, that is the maximum achievable value of the social welfare. We first introduce and study a new model in the Hedonic Games setting, called Distance Hedonic Games, and we focus on the computation and the efficiency of Nash stable outcomes, i.e. coalition structures in which no agent can unilaterally improve her gain by deviating to another coalition. We then turn our attention to the design of strategyproof mechanisms for two specific classes of games: namely, Friends and Enemies Games and the Additively Separable Group Activity Selection Problem. In both cases, we measure the performances of the proposed mechanisms by considering their approximation ratio with respect to the social optimum.