Core Stability in Additively Separable Hedonic Games of Low Treewidth

20^th February 2024, 13:00 6th Floor Conference Room 605, EEE
Dr. Noleen Köhler
School of Computing, University of Leeds

Abstract

Additively Separable Hedonic Game (ASHG) are coalition-formation games where we are given a graph whose vertices represent n selfish agents and the weight of each edge uv denotes how much agent u gains (or loses) when she is placed in the same coalition as agent v. We revisit the computational complexity of the well-known notion of core stability of 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 (blocking) coalition. Since both finding a core stable partition and verifying that a given partition is core stable are intractable problems (Sigma_2^p-complete and coNP-complete respectively) we study their complexity from the point of view of structural parameterized complexity, using standard graph-theoretic parameters, such as treewidth.
This is joint work with Tesshu Hanaka and Michael Lampis.