Abstract
In the hedonic coalition formation game model Roles and Teams Hedonic Games (RTHG) (Spradling et al. 2013), agents view teams as compositions of available roles. An agent's utility for a partition is based upon which role she fulfills within the coalition and which additional roles are being fulfilled within the coalition. Goals for matchmaking in this setting include forming partitions which optimize some function of the utility. Optimization problems related to finding Perfect, MaxSum and MaxMin partitions in RTHG are all known to be NP-hard. In this paper, we introduce a Role Based Hedonic Game model (RBHG) which has no fixed team size and a more relaxed set of compositions. We consider the related problem of stability in RBHG. Given a set of available movements for agents, a partition is stable iff no agent would choose to move from the partition to another partition. We show NP-completeness for several RBHG stability problems and coNP-completeness for two verification problems.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015 |
| Editors | William Eberle, Ingrid Russell |
| Pages | 85-90 |
| Number of pages | 6 |
| ISBN (Electronic) | 9781577357308 |
| State | Published - 2015 |
| Event | 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015 - Hollywood, United States Duration: May 18 2015 → May 20 2015 |
Publication series
| Name | Proceedings of the 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015 |
|---|
Conference
| Conference | 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015 |
|---|---|
| Country/Territory | United States |
| City | Hollywood |
| Period | 5/18/15 → 5/20/15 |
Bibliographical note
Publisher Copyright:Copyright © 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
ASJC Scopus subject areas
- Artificial Intelligence