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 napproximation 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)napproximation 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. 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

Flammini, Michele;Kodric, Bojana;Varricchio, Giovanna
2020

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 napproximation 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)napproximation 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. 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
978-1-57735-823-7
File in questo prodotto:
File Dimensione Formato  
2020_34AAAIConfArtIntell_34_1950_Flammini.pdf

accesso aperto

Descrizione: Articolo principale
Licenza: Dominio pubblico
548.73 kB Adobe PDF Visualizza/Apri

I documenti in IRIS 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: http://hdl.handle.net/20.500.12571/14383
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact