Strategyproof Mechanisms for Friends and Enemies Games

Authors

  • Michele Flammini Gran Sasso Science Institute
  • Bojana Kodric Gran Sasso Science Institute
  • Giovanna Varricchio Gran Sasso Science Institute

DOI:

https://doi.org/10.1609/aaai.v34i02.5565

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(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.

Downloads

Published

2020-04-03

How to Cite

Flammini, M., Kodric, B., & Varricchio, G. (2020). Strategyproof Mechanisms for Friends and Enemies Games. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1950-1957. https://doi.org/10.1609/aaai.v34i02.5565

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms