From the 1 of 4 linked papers with an AI index.
4 papers
Complexity of Strong Popularity in Additively Separable Hedonic Games
Matan Gilboa
The paper investigates the computational difficulty of deciding whether a strongly popular partition exists in additively separable hedonic games, proving the problem is PCW‑comple…
Complexity of Unambiguous Problems in
Matan Gilboa, Paul W. Goldberg, Elias Koutsoupias +1
Various practical problems within the class possess an unambiguity property, meaning that yes-instances correspond with a unique witness. The semantic class containing a…
Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
Martin Bullinger, Adam Dunajski, Edith Elkind +1
We study stability in additively separable hedonic games when coalition sizes have to respect fixed size bounds. We consider four classic notions of stability based on single-agent…
Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games
Martin Bullinger, Matan Gilboa
We study coalition formation in the framework of hedonic games. There, a set of agents needs to be partitioned into disjoint coalitions, where agents have a preference order over c…