Finding and recognizing popular coalition structures

Felix Brandt, Martin Bullinger

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

An important aspect of multi-agent systems concerns the formation of coalitions that are stable or optimal in some well-defined way. The notion of popularity has recently received a lot of attention in this context. A partition is popular if there is no other partition in which more agents are better off than worse off. In 2019, a long-standing open problem concerning popularity was solved by proving that computing popular partitions in roommate games is NP-hard, even when preferences are strict. We show that this result breaks down when allowing for randomization: mixed popular partitions can be found efficiently via linear programming and a separation oracle. Mixed popular partitions are particularly attractive because they are guaranteed to exist in any coalition formation game. Our result implies that one can efficiently verify whether a given partition in a roommate game is popular and that strongly popular partitions can be found in polynomial time (resolving an open problem). By contrast, we prove that both problems become computationally intractable when moving from coalitions of size 2 to coalitions of size 3, even when preferences are strict and globally ranked. Moreover, we give elaborate proofs showing the NP-hardness of finding popular, strongly popular, and mixed popular partitions in additively separable hedonic games and finding popular partitions in fractional hedonic games.

Original languageEnglish
Title of host publicationProceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020
EditorsBo An, Amal El Fallah Seghrouchni, Gita Sukthankar
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages195-203
Number of pages9
ISBN (Electronic)9781450375184
StatePublished - 2020
Event19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020 - Virtual, Auckland, New Zealand
Duration: 19 May 2020 → …

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume2020-May
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020
Country/TerritoryNew Zealand
CityVirtual, Auckland
Period19/05/20 → …

Keywords

  • Coalition Formation
  • Social Choice Theory

Fingerprint

Dive into the research topics of 'Finding and recognizing popular coalition structures'. Together they form a unique fingerprint.

Cite this