The complexity of power indexes with graph restricted coalitions

DOI10.1016/J.MATHSOCSCI.2015.04.001MaRDI QIDQ898757zbMATH OpenOpenAlexFDO

Authors Stefano Benati, Romeo Rizzi, Craig A. Tovey

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)

Recommendations

• Power Indices in Spanning Connectivity Games
• The Complexity of Power-Index Comparison
• The complexity of power-index comparison
• NP-completeness for calculating power indices of weighted majority games
• Monotonicity of power in weighted voting games with restricted communication

Cites work

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

Cited in

(10)

• The complexity of power-index comparison
• Monotonicity of power in weighted voting games with restricted communication
• Voting power on a graph connected political space with an application to decision-making in the council of the European Union
• Measuring power in coalitional games with friends, enemies and allies
• Attachment centrality: measure for connectivity in networks
• The Complexity of Power-Index Comparison
• scientific article; zbMATH DE number 1843547 (Why is no real title available?)
• Merging and splitting for power indices in weighted voting games and network flow games on hypergraphs
• Political power on a line graph
• Protectionism and blocking power indices

This page was built for publication: The complexity of power indexes with graph restricted coalitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898757)