NP-COMPLETENESS OF SOME PROBLEMS CONCERNING VOTING GAMES

被引：43

作者：

PRASAD, K ^{[1
]}

KELLY, JS ^{[1
]}

机构：

[1] SYRACUSE UNIV,DEPT ECON,SYRACUSE,NY 13244

来源：

INTERNATIONAL JOURNAL OF GAME THEORY | 1990年 / 19卷 / 01期

关键词：

D O I：

10.1007/BF01753703

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

The 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. © 1990 Physica-Verlag.

引用

页码：1 / 9

页数：9