NP-completeness of some problems concerning voting games
NP-completeness of some problems concerning voting games
复制标题
一些投票博弈问题的NP-完备性
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
J. Kelly
中科院分区：
文献类型：
--
作者：
Kislaya Prasad;J. Kelly
摘要确定个体选择的联盟数量下限的问题是NP完全的。因此，确定幂指数非零值的问题是NP完全问题。计算绝对Banzhaf指数的问题是#P-完全的。对功率指数的相关问题进行了讨论。
SummaryThe problem of confirming lower bounds on the number of coalitions for which an individual is pivoting is NP-complete. Consequently, the problem of confirming non-zero values of power indices is NP-complete. The problem of computing the Absolute Banzhaf index is #P-complete. Related problems for power indices are discussed.