Decentralized Multiagent Approach for Hedonic Games

Kshitija Taywade; Judy Goldsmith; Brent Harrison

doi:10.1007/978-3-030-14174-5_15

Decentralized Multiagent Approach for Hedonic Games

Kshitija Taywade, Judy Goldsmith, Brent Harrison

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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 language	English
Title of host publication	Multi-Agent Systems - 16th European Conference, EUMAS 2018, Revised Selected Papers
Editors	Marija Slavkovik
Pages	220-232
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-030-14174-5_15
State	Published - 2019
Event	16th European Conference on Multi-Agent Systems, EUMAS 2018 - Bergen, Norway Duration: Dec 6 2018 → Dec 7 2018

Publication series

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

Conference

Conference	16th European Conference on Multi-Agent Systems, EUMAS 2018
Country/Territory	Norway
City	Bergen
Period	12/6/18 → 12/7/18

Bibliographical note

Publisher Copyright:
© 2019, Springer Nature Switzerland AG.

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science (all)

Access to Document

10.1007/978-3-030-14174-5_15

Cite this

Taywade, K., Goldsmith, J., & Harrison, B. (2019). Decentralized Multiagent Approach for Hedonic Games. In M. Slavkovik (Ed.), Multi-Agent Systems - 16th European Conference, EUMAS 2018, Revised Selected Papers (pp. 220-232). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11450 LNAI). https://doi.org/10.1007/978-3-030-14174-5_15

Taywade, Kshitija ; Goldsmith, Judy ; Harrison, Brent. / Decentralized Multiagent Approach for Hedonic Games. Multi-Agent Systems - 16th European Conference, EUMAS 2018, Revised Selected Papers. editor / Marija Slavkovik. 2019. pp. 220-232 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{47b405fc243549fe94637cb2d5654036,

title = "Decentralized Multiagent Approach for Hedonic Games",

abstract = "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.",

author = "Kshitija Taywade and Judy Goldsmith and Brent Harrison",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; null ; Conference date: 06-12-2018 Through 07-12-2018",

year = "2019",

doi = "10.1007/978-3-030-14174-5_15",

language = "English",

isbn = "9783030141738",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "220--232",

editor = "Marija Slavkovik",

booktitle = "Multi-Agent Systems - 16th European Conference, EUMAS 2018, Revised Selected Papers",

}

Taywade, K, Goldsmith, J & Harrison, B 2019, Decentralized Multiagent Approach for Hedonic Games. in M Slavkovik (ed.), Multi-Agent Systems - 16th European Conference, EUMAS 2018, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11450 LNAI, pp. 220-232, 16th European Conference on Multi-Agent Systems, EUMAS 2018, Bergen, Norway, 12/6/18. https://doi.org/10.1007/978-3-030-14174-5_15

Decentralized Multiagent Approach for Hedonic Games. / Taywade, Kshitija; Goldsmith, Judy ; Harrison, Brent.

Multi-Agent Systems - 16th European Conference, EUMAS 2018, Revised Selected Papers. ed. / Marija Slavkovik. 2019. p. 220-232 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11450 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Decentralized Multiagent Approach for Hedonic Games

AU - Taywade, Kshitija

AU - Goldsmith, Judy

AU - Harrison, Brent

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85063507571&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85063507571&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-14174-5_15

DO - 10.1007/978-3-030-14174-5_15

M3 - Conference contribution

AN - SCOPUS:85063507571

SN - 9783030141738

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 220

EP - 232

BT - Multi-Agent Systems - 16th European Conference, EUMAS 2018, Revised Selected Papers

A2 - Slavkovik, Marija

Y2 - 6 December 2018 through 7 December 2018

ER -

Taywade K, Goldsmith J , Harrison B. Decentralized Multiagent Approach for Hedonic Games. In Slavkovik M, editor, Multi-Agent Systems - 16th European Conference, EUMAS 2018, Revised Selected Papers. 2019. p. 220-232. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-14174-5_15

Decentralized Multiagent Approach for Hedonic Games

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this