NP-completeness for calculating power indices of weighted majority games

DOI10.1016/S0304-3975(00)00251-6zbMath0991.91006MaRDI QIDQ5941522

Tomomi Matsui, Yasuko Matsui

Publication date: 20 August 2001

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

zbMATH Keywords

NP-completenessBanzhaf power indexShapley-Shubik power indexpower indexvoting game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12) Voting theory (91B12)

Related Items (25)

Equilibrium computation of the Hart and Mas-Colell bargaining model ⋮ Implicit power indices for measuring indirect control in corporate structures ⋮ Ranking of decision rules with random power distribution ⋮ Proof systems and transformation games ⋮ A cooperative game-theoretic approach to the social ridesharing problem ⋮ Dynamic programming for computing power indices for weighted voting games with precoalitions ⋮ The complexity of power indexes with graph restricted coalitions ⋮ Manipulating the quota in weighted voting games ⋮ The consequences of eliminating NP solutions ⋮ Selfish bin covering ⋮ Confidence intervals for the Shapley-Shubik power index in Markovian games ⋮ On the complexity of problems on simple games ⋮ Analyzing power in weighted voting games with super-increasing weights ⋮ Computing cooperative solution concepts in coalitional skill games ⋮ Power indices of simple games and vector-weighted majority games by means of binary decision diagrams ⋮ Unnamed Item ⋮ On the computational complexity of weighted voting games ⋮ The complexity of power-index comparison ⋮ Analyzing Power in Weighted Voting Games with Super-Increasing Weights ⋮ Variable Influences in Conjunctive Normal Forms ⋮ Effort Games and the Price of Myopia ⋮ Voting power on a graph connected political space with an application to decision-making in the council of the European Union ⋮ Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games ⋮ SOME OPEN PROBLEMS IN SIMPLE GAMES ⋮ Monte Carlo methods for the Shapley-Shubik power index

Cites Work

• On variations of the subset sum problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: NP-completeness for calculating power indices of weighted majority games