Stability in Role Based Hedonic Games
Stability in Role Based Hedonic Games
复制标题
基于角色的快乐游戏的稳定性
DOI：
10.1016/j.geb.2003.10.003
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Goldsmith
中科院分区：
文献类型：
--
作者：
Matthew Spradling;J. Goldsmith
在享乐联盟形成游戏模型角色和团队享乐游戏（RTHG），代理人认为可用的角色组合的团队。一个代理对一个分区的效用取决于她在联盟中扮演的角色以及在联盟中扮演的其他角色。在此设置中，匹配的目标包括形成优化效用的某些功能的分区。在RTHG中寻找Perfect、MaxSum和MaxMin分区的优化问题都是NP难的。在本文中，我们介绍了一个基于角色的快乐博弈模型（RBHG），它没有固定的团队规模和一个更宽松的组合。我们考虑RBHG的稳定性的相关问题。给定代理的一组可用移动，分区是稳定的，如果没有代理会选择从分区移动到另一个分区。我们证明了几个RBHG稳定性问题和两个验证问题的NP-完全性。
In the hedonic coalition formation game model Roles and Teams Hedonic Games (RTHG), 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.