Stability in role based hedonic games

Matthew Spradling, Judy Goldsmith

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

9 Scopus citations

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 languageEnglish
Title of host publicationProceedings of the 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015
EditorsWilliam Eberle, Ingrid Russell
Pages85-90
Number of pages6
ISBN (Electronic)9781577357308
StatePublished - 2015
Event28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015 - Hollywood, United States
Duration: May 18 2015May 20 2015

Publication series

NameProceedings of the 28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015

Conference

Conference28th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2015
Country/TerritoryUnited States
CityHollywood
Period5/18/155/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

Fingerprint

Dive into the research topics of 'Stability in role based hedonic games'. Together they form a unique fingerprint.

Cite this