NP-completeness of some problems concerning voting games

K. Prasad, J. S. Kelly

Research output: Contribution to journalArticle

51 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1-9
Number of pages9
JournalInternational Journal of Game Theory
Volume19
Issue number1
DOIs
StatePublished - Mar 1 1990

ASJC Scopus subject areas

  • Statistics and Probability
  • Mathematics (miscellaneous)
  • Social Sciences (miscellaneous)
  • Economics and Econometrics
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'NP-completeness of some problems concerning voting games'. Together they form a unique fingerprint.

  • Cite this