论文标题
与朋友，敌人和中立的享乐游戏：解决开放问题和细粒度的复杂性
Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity
论文作者
论文摘要
我们研究了与朋友，敌人的享乐游戏中突出稳定概念的验证和存在问题，以及中性的[8，16]。我们解决了几个（长期存在的）公开问题[4、16、20、23]，并表明，对于以朋友和敌人的模型为导向的偏好，验证给定的代理分区（严格地）核心稳定是毫无疑问的，而在朋友，敌人和中立模型下，它是NP-Complete np-Complete以确定一个个人的分区。我们进一步研究了文献中的自然限制案例，例如，当朋友和敌人的关系对称时，当最初的联盟的规模有限时，当友谊图中的顶点学位（分别的友谊和敌方图）是有界的，或者当该图是acyclic或acyclic时或接近acyclic时。我们获得了有关这些情况的完整（参数化）复杂性。
We investigate verification and existence problems for prominent stability concepts in hedonic games with friends, enemies, and optionally with neutrals [8, 16]. We resolve several (long-standing) open questions [4, 16, 20, 23] and show that for friend-oriented preferences, under the friends and enemies model, it is coNP-complete to verify whether a given agent partition is (strictly) core stable, while under the friends, enemies, and neutrals model, it is NP-complete to determine whether an individual stable partition exists. We further look into natural restricted cases from the literature, such as when the friends and enemies relationships are symmetric, when the initial coalitions have bounded size, when the vertex degree in the friendship graph (resp. the union of friendship and enemy graph) is bounded, or when such graph is acyclic or close to being acyclic. We obtain a complete (parameterized) complexity picture regarding these cases.
