Unknown Agents in Friends Oriented Hedonic Games: Stability and Complexity

  • Nathanaël Barrot Riken AIP, Kyushu University
  • Kazunori Ota Kyushu University
  • Yuko Sakurai National Institute of Advanced Industrial Science and Technology
  • Makoto Yokoo Kyushu University, Japan

Abstract

We study hedonic games under friends appreciation, where each agent considers other agents friends, enemies, or unknown agents. Although existing work assumed that unknown agents have no impact on an agent’s preference, it may be that her preference depends on the number of unknown agents in her coalition. We extend the existing preference, friends appreciation, by proposing two alternative attitudes toward unknown agents, extraversion and introversion, depending on whether unknown agents have a slightly positive or negative impact on preference. When each agent prefers coalitions with more unknown agents, we show that both core stable outcomes and individually stable outcomes may not exist. We also prove that deciding the existence of the core and the existence of an individual stable coalition structure are respectively NPNP-complete and NP-complete.

Published
2019-07-17
Section
AAAI Technical Track: Game Theory and Economic Paradigms