Non-obvious Manipulability in Hedonic Games with Friends Appreciation Preferences

We study non-obvious manipulability (NOM), a relaxed form of strategyproofness, in the context of Hedonic Games (HGs) with Friends Appreciation (FA) preferences. In HGs, the aim is to partition agents into coalitions according to their preferences, which solely depend on the coalition they are assigned to. Under FA preferences, agents consider any other agent either a friend or an enemy, preferring coalitions with more friends and, in case of ties, the ones with fewer enemies. Prior research established that computing a welfare maximizing (optimum) partition for FA preferences is not strategyproof, and the best-known approximation to the optimum subject to strategyproofness is linear in the number of agents. In this work, we explore NOM to improve approximation results. We first prove the existence of a NOM mechanism that always outputs the optimum; however, we also demonstrate that the computation of an optimal partition is NP-hard. In turn, we also propose a NOM mechanism guaranteeing a (4 + 𝑜(1))-approximation in polynomial time. Finally, we briefly discuss NOM in the case of Enemies Aversion (EA) preferences, the counterpart of FA, where agents give priority to coalitions with fewer enemies and show that no mechanism computing the optimum can be NOM.