4 papers
Complexity of Strong Popularity in Additively Separable Hedonic Games
Matan Gilboa
In a hedonic game, agents need to be partitioned into coalitions, and have a preference order over partitions. A partition is called strongly popular if it beats any other partitio…
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…
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 al…
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…