The complexity of power indexes with graph restricted coalitions

DOI10.1016/j.mathsocsci.2015.04.001zbMath1331.91017OpenAlexW2004353559MaRDI QIDQ898757

Craig A. Tovey, Stefano Benati, Romeo Rizzi

Publication date: 18 December 2015

Published in: Mathematical Social Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.mathsocsci.2015.04.001

Mathematics Subject Classification ID

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

Related Items

Voting power on a graph connected political space with an application to decision-making in the council of the European Union ⋮ Attachment centrality: measure for connectivity in networks ⋮ Measuring power in coalitional games with friends, enemies and allies

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Preferences, the agenda setter, and the distribution of power in the EU
• NP-completeness of some problems concerning voting games
• Polynomial calculation of the Shapley value based on sampling
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Computing power indices in weighted multiple majority games.
• Easy weighted majority games
• Generating functions for computing the Myerson value
• Faster algorithms for computing power indices in weighted voting games
• Voting power in the European Union enlargement
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the computational complexity of weighted voting games
• Probabilistic spatial power indexes
• Computing Power Indices for Large Voting Games
• Approximating the Permanent
• Crossing Number is NP-Complete
• PP is as Hard as the Polynomial-Time Hierarchy
• Easy problems for tree-decomposable graphs
• Mathematics and Politics
• Values of Graph-Restricted Games
• On the Position Value for Communication Situations
• Complexity Results for Bandwidth Minimization
• Graphs and Cooperation in Games
• On the Complexity of Cooperative Solution Concepts
• Efficient Computation of Power Indices for Weighted Majority Games
• Computational Complexity
• The Banzhaf value and communication situations
• The core of games on ordered structures and graphs
• Generating functions for computing power indices efficiently
• NP-completeness for calculating power indices of weighted majority games