Core stability of minimum coloring games

• 成果类型: Article
• 署名作者: Bietenhader, Thomas; Okamoto, Yoshio
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; Toyohashi University of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1060.0187
• 发表日期: 2006
• 页码: 418-431
• 关键词: algorithms; DOMINATION

摘要

In cooperative game theory, a characterization of games with stable cores is known as one of the most notorious open problems. We study this problem for a special case of the minimum coloring games, introduced by Deng et al. [10], which arise from a cost allocation problem when the players are involved in conflict. In this paper, we show that the minimum coloring game on a perfect graph has a stable core if and only if every vertex of the graph belongs to a maximum clique. We also consider the problem on the core largeness, the extendability, and the exactness of minimum coloring games. As a consequence, we show that it is coNP-complete to decide whether a given game has a large core, is extendable, or is exact.