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 provide strategyproof mechanisms for both settings. More precisely, for FA we first present a deterministic n-approximation mechanism, and then show that a much better result can be accomplished 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(n^{1−ɛ}) for any fixed ɛ > 0. Finally, we show how to extend our results in the presence of neutrals, i.e., when agents can also be indifferent about other agents, and we discuss anonymity.

Strategyproof mechanisms for friends and enemies games

Kodric B.;
2020-01-01

Abstract

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 provide strategyproof mechanisms for both settings. More precisely, for FA we first present a deterministic n-approximation mechanism, and then show that a much better result can be accomplished 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(n^{1−ɛ}) for any fixed ɛ > 0. Finally, we show how to extend our results in the presence of neutrals, i.e., when agents can also be indifferent about other agents, and we discuss anonymity.
2020
The Thirty-Fourth {AAAI} Conference on Artificial Intelligence, {AAAI} 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, {IAAI} 2020, The Tenth {AAAI} Symposium on Educational Advances in Artificial Intelligence, {EAAI} 2020, New York, NY, USA, February 7-12, 2020
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/5035728
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact