On the complexity of problems on simple games

DOI10.1051/ro/2011115zbMath1235.68082MaRDI QIDQ5388151

Xavier Molinero, Martin Olsen, Maria J. Serna, Josep Freixas

Publication date: 18 April 2012

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/222510

zbMATH Keywords

NP-completeness; simple; weighted; majority games

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

91A12: Cooperative games

Related Items

On the complexity of exchanging, Forms of representation for simple games: sizes, conversions and equivalences, Simple games versus weighted voting games: bounding the critical threshold value, On Dedekind's problem for complete simple games, Cooperation through social influence

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-completeness of some problems concerning voting games
• Simple games and weighted games: A theoretical and computational viewpoint
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• Complete simple games
• Simple games and magic squares
• On the geometric separability of Boolean functions
• On the computational complexity of weighted voting games
• Weighted voting, abstention, and multiple levels of approval
• On the dimension of simple monotonic games
• On the Complexity of Cooperative Solution Concepts
• NP-completeness for calculating power indices of weighted majority games
• Decision tree approximations of Boolean functions