Strategyproof mechanisms for Friends and Enemies Games

We investigate strategyproof mechanisms for Friends and Enemies Games, a subclass of Hedonic Games in which every agent classifies any other one as a friend or as an enemy. In this setting, we consider the two classical scenarios proposed in the literature, called Friends Appreciation (FA) and Enemies Aversion (EA). Roughly speaking, in the former each agent gives priority to the number of friends in her coalition, while in the latter to the number of enemies. We focus on the objective of maximizing the sum of the utilities of the agents and provide strategyproof mechanisms for both settings. More precisely, for FA we first present a deterministic n-approximation mechanism, n being the number of agents, and then show that a much better approximation can be achieved by resorting to randomization. Namely, we provide a randomized mechanism whose expected approximation ratio is 4, and arbitrarily close to 4 with high probability. For EA, we give a simple (1+2)n-approximation mechanism, and show that its performance is asymptotically tight by proving that it is NP-hard to approximate the optimal solution within O(n1−ε) for any fixed ε>0. We also show that, if computational efficiency is not a concern, it is possible to achieve a (1+2)-approximation by means of a deterministic strategyproof mechanism with exponential runtime. Finally, we show how to extend our results in the presence of neutrals, i.e., when agents can also be indifferent about other agents.