Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games

Hedonic Games are a well-established model for describing the formation of coalitions. In this work, we considered the design of Non-Obviously Manipulable (NOM) mechanisms, that are mechanisms that bounded rational agents may fail to recognize as manipulable, for two relevant classes of succinctly representable Hedonic Games, namely Additively Separable and Fractional Hedonic Games. In these classes, agents have cardinal scores towards other agents, and their preferences towards different coalitions are determined by aggregating these scores. Moreover, the quality of an outcome can also be easily evaluated through these scores by means of the utilitarian social welfare. We first prove that, when scores can be arbitrary, every welfare-maximizing mechanism is NOM, and, when scores are limited in a continuous interval, then there exist tie-breaking rules making welfare-maximizing mechanisms NOM. Next, we focus on efficient NOM mechanisms, since there is no known polynomial-time algorithm to compute welfare-maximizing outcomes in the considered classes of hedonic games. To this aim, we first prove a characterization of NOM mechanisms that simplifies the class of mechanisms of interest. Then, we design a NOM mechanism returning approximations that essentially match the best-known approximation achievable in polynomial time. Finally, we turn our attention to discrete scores, and specifically, the case that scores are $\{-x, 0, 1\}$ for $x > 0$. We prove that the ability to design welfare-maximizing NOM mechanisms depends on the magnitude of the scores. In particular, for $x > 1$, we prove that a welfare-maximizing NOM mechanism exists only when $x$ is very large. For $x \leq 1$, instead, we observe that a welfare-maximizing NOM mechanism always exists except when $x$ lies in the interval $[a, b]$ where $a \approx 2/n^2$ and $b \approx 1/n$.