Efficient algorithms for subdominant cycle-complete cost functions and cycle-complete solutions
Efficient algorithms for subdominant cycle-complete cost functions and cycle-complete solutions
复制标题
用于次主导周期完整成本函数和周期完整解决方案的高效算法
DOI：
10.1016/j.dam.2017.03.007
复制
发表时间：
2017
影响因子：
1.1
通讯作者：
Shoji Kazuya
中科院分区：
文献类型：
--
作者：
Ando Kazutoshi;Inagaki Ryosuke;Shoji Kazuya
Trudeau（2012）提出的循环完备解是最小成本生成树博弈的解概念，并被证明具有理想的性质，如核心选择和对成本函数变化的敏感性。循环完全解被定义为与给定成本函数的次支配循环完全成本函数相关联的最小成本生成树博弈的Shapley值。在这项研究中，我们的特征次支配周期完全成本函数，并提供了一个O（n2 log n）时间算法计算这样的功能，其中n是玩家的数量。该算法导致一个新的算法计算的最小成本生成树游戏的周期完整的解决方案的O（n2 log n）的时间限制。
The cycle-complete solution introduced by Trudeau (2012) is a solution concept for minimum cost spanning tree games and was proved to have desirable properties such as core-selection and sensitivity to change of the cost function. The cycle-complete solution is defined as the Shapley value of the minimum cost spanning tree game associated with the subdominant cycle-complete cost function of a given cost function. In this study, we characterize subdominant cycle-complete cost functions and provide an O (n 2 log n) time algorithm for computing such functions, where n is the number of players. This algorithm leads to a new algorithm for computing the cycle-complete solution of a minimum cost spanning tree game with an O (n 2 log n) time bound.