论文标题
享乐游戏和树宽重新审视
Hedonic Games and Treewidth Revisited
论文作者
论文摘要
我们重新审视了可添加性可分开的享乐游戏（ASHGS）的精心研究的复杂性。这样的游戏模型是一种基本的聚类或联盟形成场景，其中自私的代理人由边缘加权的digraph $ g =（v，e）$表示，弧线$ uv $的重量表示效用$ u $ $ u $的收益，通过在同一联盟中与$ v $相同。我们专注于（可以说）有关此类游戏的最基本稳定问题：给定图形，是否存在NASH稳定解决方案，我们可以有效地发现它吗？ 我们研究ASHG稳定性的（参数化）复杂性时，基础图具有树宽$ t $和最大程度$δ$。当前的最佳FPT算法是Peters [AAAI 2016]所要求的，时间复杂性约为$ 2^{o（δ^5t）} $。我们提出了一种具有参数依赖性$（ΔT）^{o（ΔT）} $的算法，尽管对$ t $的依赖性稍差，但对彼得斯给出的$δ$的参数依赖性有了显着改善。我们的主要结果是，对于$ t $，实际上是完全合理的：我们观察到先前声称的算法是不正确的，实际上，除非ETH失败，否则没有算法可以实现依赖性$ t^{o（t）} $。这是我们对$δ$的依赖性提供的相应边界，关节参数确定我们的算法在ETH下对两个参数基本上都是最佳的。 然后，我们仅通过树宽来重新审视参数化，并解决了彼得斯也提出的一个问题，即在添加偏好下，NASH稳定性在恒星上仍然存在很强的NP。尽管如此，我们也发现了一个轻度的易处理性岛：我们表明，连接的NASH稳定性在伪单式时间内可以解决常数$ t $，尽管XP依赖于$ t $，因此无法避免，这是我们确定的。
We revisit the complexity of the well-studied notion of Additively Separable Hedonic Games (ASHGs). Such games model a basic clustering or coalition formation scenario in which selfish agents are represented by the vertices of an edge-weighted digraph $G=(V,E)$, and the weight of an arc $uv$ denotes the utility $u$ gains by being in the same coalition as $v$. We focus on (arguably) the most basic stability question about such a game: given a graph, does a Nash stable solution exist and can we find it efficiently? We study the (parameterized) complexity of ASHG stability when the underlying graph has treewidth $t$ and maximum degree $Δ$. The current best FPT algorithm for this case was claimed by Peters [AAAI 2016], with time complexity roughly $2^{O(Δ^5t)}$. We present an algorithm with parameter dependence $(Δt)^{O(Δt)}$, significantly improving upon the parameter dependence on $Δ$ given by Peters, albeit with a slightly worse dependence on $t$. Our main result is that this slight performance deterioration with respect to $t$ is actually completely justified: we observe that the previously claimed algorithm is incorrect, and that in fact no algorithm can achieve dependence $t^{o(t)}$ for bounded-degree graphs, unless the ETH fails. This, together with corresponding bounds we provide on the dependence on $Δ$ and the joint parameter establishes that our algorithm is essentially optimal for both parameters, under the ETH. We then revisit the parameterization by treewidth alone and resolve a question also posed by Peters by showing that Nash Stability remains strongly NP-hard on stars under additive preferences. Nevertheless, we also discover an island of mild tractability: we show that Connected Nash Stability is solvable in pseudo-polynomial time for constant $t$, though with an XP dependence on $t$ which, as we establish, cannot be avoided.
