Decentralized Multiagent Approach for Hedonic Games

Kshitija Taywade, Judy Goldsmith, Brent Harrison

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

1 Scopus citations


We propose a novel, multi-agent, decentralized approach for hedonic coalition formation games useful for settings with a large number of agents. We also propose three heuristics which, can be coupled with our approach to find sub-coalitions that prefer to “bud off” from an existing coalition. We found that our approach when compared to random partition formation gives better results which further improve when it is coupled with the proposed heuristics. As matching problems are a common type of hedonic games, we have adapted our approach for two matching problems: roommate matching and bipartite matching. Our method does well for additively separable hedonic games, where finding the optimal partition is NP-hard, and gives near optimal results for matching problems.

Original languageEnglish
Title of host publicationMulti-Agent Systems - 16th European Conference, EUMAS 2018, Revised Selected Papers
EditorsMarija Slavkovik
Number of pages13
StatePublished - 2019
Event16th European Conference on Multi-Agent Systems, EUMAS 2018 - Bergen, Norway
Duration: Dec 6 2018Dec 7 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11450 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th European Conference on Multi-Agent Systems, EUMAS 2018

Bibliographical note

Publisher Copyright:
© 2019, Springer Nature Switzerland AG.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Decentralized Multiagent Approach for Hedonic Games'. Together they form a unique fingerprint.

Cite this