Parameterized Complexity of Hedonic Games with Enemy-Oriented Preferences

Hedonic games model settings in which a set of agents have to be partitioned into groups which we call coalitions. In the enemy aversion model, each agent has friends and enemies, and an agent prefers to be in a coalition with as few enemies as possible and, subject to that, as many friends as possible. A partition should be stable, i. e. , no subset of agents prefer to be together rather than being in their assigned coalitions under the partition. We look at two stability concepts: core stability and strict core stability. This yields several algorithmic problems: determining whether a (strictly) core stable partition exists, finding such a partition, and checking whether a given partition is (strictly) core stable. Several of these problems have been shown to be NP-complete, or even beyond NP. This motivates the study of parameterized complexity. We conduct a thorough computational study using several parameters: treewidth, number of friends, number of enemies, partition size, and coalition size. We conclude this paper with results in the setting in which agents can have neutral relations with each other, including hardness-results for very restricted instances.

Authors

• Martin Durand
• Laurin Erlacher TU Wien
• Johanne Müller Vistisen TU Wien & Technical University of Denmark
• Sofia Simola TU Wien

Keywords

• Hedonic Games
• Parameterized Complexity
• Coalition Formation