The complexity of power-index comparison

DOI10.1016/j.tcs.2008.09.034zbMath1155.91013OpenAlexW2041916646MaRDI QIDQ1001906

Piotr Faliszewski, Hemaspaandra, Lane A.

Publication date: 19 February 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.034

zbMATH Keywords

computational complexitycompletenesspower indexclosure property\#P

Mathematics Subject Classification ID

Cooperative games (91A12) Voting theory (91B12)

Related Items (8)

Controlling weighted voting games by deleting or adding players with or without changing the quota ⋮ The complexity of the \(K\)th largest subset problem and related problems ⋮ Manipulating the quota in weighted voting games ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Analyzing power in weighted voting games with super-increasing weights ⋮ Worst-case Bounds on Power vs. Proportion in Weighted Voting Games with an Application to False-name Manipulation ⋮ Maximum box problem on stochastic points ⋮ Structural control in weighted voting games

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• NP-completeness of some problems concerning voting games
• The complexity of optimization problems
• The polynomial-time hierarchy and sparse oracles
• PP is as Hard as the Polynomial-Time Hierarchy
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• Computational Complexity of Probabilistic Turing Machines
• Mathematical Properties of the Banzhaf Power Index
• The Complexity of Planar Counting Problems
• On the Complexity of Cooperative Solution Concepts
• NP-completeness for calculating power indices of weighted majority games

This page was built for publication: The complexity of power-index comparison