TY - GEN
T1 - Stability in role based hedonic games
AU - Spradling, Matthew
AU - Goldsmith, Judy
N1 - Publisher Copyright:
Copyright © 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84958162358&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958162358&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84958162358
T3 - Proceedings of the 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015
SP - 85
EP - 90
BT - Proceedings of the 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015
A2 - Eberle, William
A2 - Russell, Ingrid
T2 - 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015
Y2 - 18 May 2015 through 20 May 2015
ER -