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.
|Title of host publication||Multi-Agent Systems - 16th European Conference, EUMAS 2018, Revised Selected Papers|
|Number of pages||13|
|State||Published - 2019|
|Event||16th European Conference on Multi-Agent Systems, EUMAS 2018 - Bergen, Norway|
Duration: Dec 6 2018 → Dec 7 2018
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||16th European Conference on Multi-Agent Systems, EUMAS 2018|
|Period||12/6/18 → 12/7/18|
Bibliographical notePublisher Copyright:
© 2019, Springer Nature Switzerland AG.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science (all)