Hedonic coalition nets
Hedonic coalition nets
复制标题
DOI：
10.1145/1558013.1558070
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
Edith Elkind;M. Wooldridge
中科院分区：
文献类型：
--
作者：
Edith Elkind;M. Wooldridge
在享乐博弈中，参与者有机会形成联盟，并对他们可能加入的联盟有偏好。这种游戏可以用来模拟各种设置，从多代理协调到社交网络中的群体形成。然而，享乐游戏的实际应用受到这样一个事实的阻碍，即这种游戏的朴素表示是指数的玩家数量。在本文中，我们研究享乐联盟网--一个简洁的，基于规则的享乐游戏表示。这种形式主义是基于边际贡献网，这是由杨和Shoham代表联盟游戏与可转移的效用。我们表明，享乐联盟网是普遍表达，但至少是简洁的享乐游戏的其他现有的表示方案。然后，我们研究了许多自然决策问题的复杂性享乐联盟网。特别是，我们提供了一个完整的特征的计算困难的问题，联盟的稳定性与享乐游戏表示享乐网。
In hedonic games, players have the opportunity to form coalitions, and have preferences over the coalitions they might join. Such games can be used to model a variety of settings ranging from multi-agent coordination to group formation in social networks. However, the practical application of hedonic games is hindered by the fact that the naive representation for such games is exponential in the number of players. In this paper, we study hedonic coalition nets---a succinct, rule-based representation for hedonic games. This formalism is based on marginal contribution nets, which were developed by Ieong and Shoham for representing coalitional games with transferable utility. We show that hedonic coalition nets are universally expressive, yet are at least as succinct as other existing representation schemes for hedonic games. We then investigate the complexity of many natural decision problems for hedonic coalition nets. In particular, we provide a complete characterisation of the computational difficulty of problems related to coalitional stability for hedonic games represented with hedonic nets.