Finding and verifying the nucleolus of cooperative games
Finding and verifying the nucleolus of cooperative games
复制标题
DOI：
10.1007/s10107-020-01527-9
复制
发表时间：
2020-06
影响因子：
2.7
通讯作者：
Márton Benedek;J. Fliege;Tri-Dung Nguyen
中科院分区：
文献类型：
--
作者：
Márton Benedek;J. Fliege;Tri-Dung Nguyen
核仁在合作博弈中提供了一个理想的收益分享解决方案，这要归功于它的吸引人的特性--它总是存在于核心中（如果核心非空的话），而且它是唯一的。核仁被认为是最“稳定”的解决方案，因为它在字典上最小化了所有联盟之间的不满。尽管计算核仁非常具有挑战性，但科尔伯格准则提供了一种强大的方法来验证相对较小的游戏（即玩家数量）中的解是否是核仁。然而，这种方法对于较大的游戏变得更具挑战性，因为需要形成和检查可能涉及指数级大联盟集合的标准，每个集合可能具有指数级大的大小。这项工作的目的是双重的。首先，我们开发了一个改进的版本的科尔伯格标准，涉及检查的“平衡性”在mostsets的联盟。其次，我们利用这些结果，并引入了一种新的基于下降的建设性算法，有效地找到核仁。我们证明了新算法的性能，通过比较它们与现有的方法在不同类型的游戏。我们的贡献还包括第一个开放源代码计算核仁的游戏中的大小。
The nucleolus offers a desirable payoff-sharing solution in cooperative games, thanks to its attractive properties—it always exists and lies in the core (if the core is non-empty), and it is unique. The nucleolus is considered as the most ‘stable’ solution in the sense that it lexicographically minimizes the dissatisfactions among all coalitions. Although computing the nucleolus is very challenging, the Kohlberg criterion offers a powerful method for verifying whether a solution is the nucleolus in relatively small games (i.e. with the number of players). This approach, however, becomes more challenging for larger games because of the need to form and check a criterion involving possibly exponentially large collections of coalitions, with each collection potentially of an exponentially large size. The aim of this work is twofold. First, we develop an improved version of the Kohlberg criterion that involves checking the ‘balancedness’ of at mostsets of coalitions. Second, we exploit these results and introduce a novel descent-based constructive algorithm to find the nucleolus efficiently. We demonstrate the performance of the new algorithms by comparing them with existing methods over different types of games. Our contribution also includes the first open-source code for computing the nucleolus for games of moderately large sizes.