NP-completeness in hedonic games

• 成果类型: Article
• 署名作者: Ballester, C
• 署名单位: Autonomous University of Barcelona
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2003.10.003
• 发表日期: 2004
• 页码: 1-30
• 关键词: hedonic games; coalition formation; computational complexity; NP-hard; NP-complete

摘要

In this paper, we show that there are natural limitations in attaining stability in cooperative environments. These limitations are related to the fact that the time required to obtain a stable partition of the players can grow exponentially, even under very simple assumptions on the preferences over partners. These difficulties arise even when players assess potential coalitions based solely on their size. For this purpose, we demonstrate that the core, the Nash stable set and the individually stable set have corresponding NP-complete decision problems for a variety of situations and, hence, that only exponential-time (slow) algorithms are known for solving them. (C) 2004 Elsevier Inc. All rights reserved.