On the computational complexity of weighted voting games

DOI10.1007/s10472-009-9162-5zbMath1185.91081OpenAlexW2064536758MaRDI QIDQ2268913

Paul W. Goldberg, Leslie Ann Goldberg, Michael Wooldridge, Edith Elkind

Publication date: 15 March 2010

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-009-9162-5

zbMATH Keywords

coreweighted voting gamesnucleolusleast core

Mathematics Subject Classification ID

Voting theory (91B12) Other game-theoretic models (91A40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Related Items (33)

Reasoning about coalitional games ⋮ Characteristic function games with restricted agent interactions: core-stability and coalition structures ⋮ The Cost of Stability in Network Flow Games ⋮ A linear approximation method for the Shapley value ⋮ The Least-Core and Nucleolus of Path Cooperative Games ⋮ Proof systems and transformation games ⋮ Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability ⋮ On the use of binary decision diagrams for solving problems on simple games ⋮ Growth of dimension in complete simple games ⋮ On the complexity of nucleolus computation for bipartite \(b\)-matching games ⋮ Unnamed Item ⋮ The complexity of power indexes with graph restricted coalitions ⋮ Forms of representation for simple games: sizes, conversions and equivalences ⋮ Characterization sets for the nucleolus in balanced games ⋮ On the complexity of core, kernel, and bargaining set ⋮ On the complexity of problems on simple games ⋮ Analyzing power in weighted voting games with super-increasing weights ⋮ Finding and verifying the nucleolus of cooperative games ⋮ Simple games versus weighted voting games: bounding the critical threshold value ⋮ Path-disruption games: bribery and a probabilistic model ⋮ On the computational complexity of weighted voting games ⋮ The nucleolus of arborescence games in directed acyclic graphs ⋮ Negotiating team formation using deep reinforcement learning ⋮ Computing the nucleolus of weighted cooperative matching games in polynomial time ⋮ Analyzing Power in Weighted Voting Games with Super-Increasing Weights ⋮ A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications ⋮ Answers set programs for non-transferable utility games: expressiveness, complexity and applications ⋮ The Complexity of the Nucleolus in Compact Games ⋮ Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games ⋮ Cooperative games with overlapping coalitions: charting the tractability frontier ⋮ Computing the nucleolus of weighted voting games in pseudo-polynomial time ⋮ Monte Carlo methods for the Shapley-Shubik power index ⋮ Measuring power in coalitional games with friends, enemies and allies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-completeness of some problems concerning voting games
• Weighted voting, multicameral representation, and power
• The nucleolus and kernel for simple games or special valid inequalities for 0-1 linear integer programs
• Methods for task allocation via agent coalition formation
• Geometric algorithms and combinatorial optimization.
• Coalition structure generation with worst case guarantees
• Voting power in the European Union enlargement
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the computational complexity of weighted voting games
• Complexity of constructing solutions in the core based on synergies among coalitions
• On the Complexity of Cooperative Solution Concepts
• On Weights of Constant-Sum Majority Games
• The Nucleolus of a Characteristic Function Game
• Finding nucleolus of flow game
• NP-completeness for calculating power indices of weighted majority games

This page was built for publication: On the computational complexity of weighted voting games