Core Stability in Additively Separable Hedonic Games of Low Treewidth

Additively Separable Hedonic Games (ASHGs) are coalition-formation games where we are given a directed graph whose vertices represent n selfish agents and the weight of each arc uv denotes the preferences from u to v. We revisit the computational complexity of the well-known notion of core stability of symmetric ASHGs, where the goal is to construct a partition of the agents into coalitions such that no group of agents would prefer to diverge from the given partition and form a new coalition. For Core Stability Verification (CSV), we first show the following hardness results: CSV remains coNP-complete on graphs of vertex cover 2; CSV is coW[1]-hard parameterized by vertex integrity when edge weights are polynomially bounded; and CSV is coW[1]-hard parameterized by tree-depth even if all weights are from {−1,1}. We complement these results with essentially matching algorithms and an FPT algorithm parameterized by the treewidth tw plus the maximum degree ∆ (improving a previous algorithm’s dependence from 2^O(tw^∆2) to 2^O(tw^∆)). We then move on to study Core Stability (CS), which one would naturally expect to be even harder than CSV. We confirm this intuition by showing that CS is Σ^p₂-complete even on graphs of bounded vertex cover number. On the positive side, we present a 2^2O(∆tw⁾n^O(1)-time algorithm parameterized by tw + ∆, which is essentially optimal assuming Exponential Time Hypothesis (ETH). Finally, we consider the notion of k-core stability: k denotes the maximum size of the allowed blocking (diverging) coalitions. We show that k-CSV is coW[1]-hard parameterized by k (even on unweighted graphs), while k-CS is NP-complete for all k ≥ 3 (even on graphs of bounded degree with bounded edge weights).