资源论文Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals

Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals

2019-10-29 | |  40 |   46 |   0
Abstract We investigate hedonic games under enemies aversion and friends appreciation, where every agent considers other agents as either a friend or an enemy. We extend these simple preferences by allowing each agent to also consider other agents to be neutral. Neutrals have no impact on her preference, as in a graphical hedonic game. Surprisingly, we discover that neutral agents do not simplify matters, but cause complexity. We prove that the core can be empty under enemies aversion and the strict core can be empty under friends appreciation. Furthermore, we show that under both preferences, deciding whether the strict core is nonempty, is NPNP-complete. This complexity extends to the core under enemies aversion. We also show that under friends appreciation, we can always find a core stable coalition structure in polynomial time

上一篇:Bounded Timed Propositional Temporal Logic with Past Captures Timeline-based Planning with Bounded Constraints

下一篇:Deceptive Path-Planning

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...