Computational complexity in the design of voting rules

DOI10.1007/S11238-014-9422-7MaRDI QIDQ256771zbMATH OpenOpenAlexFDO

Authors Koji Takamiya, Akira Tanaka

Publication date 10 March 2016

Published in Theory and Decision (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2115/63933

zbMATH Keywords

computational complexitystabilitycoreNakamura numberNP-completenesssimple game

Mathematics Subject Classification ID

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

Recommendations

• The computational difficulty of manipulating an election
• Social choice and computational complexity
• Computability of simple games: a complete investigation of the sixty-four possibilities
• On the complexity of problems on simple games
• NP-completeness of some problems concerning voting games

Cites work

• scientific article; zbMATH DE number 5787962 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Complexity of constructing solutions in the core based on synergies among coalitions
• Computability of simple games: A characterization and application to the core
• Computational Complexity
• Computational complexity to verify the unstability of effectivity function
• Recognizing majority-rule equilibrium in spatial voting games
• Stable effectivity functions and perfect graphs
• The Nakamura numbers for computable simple games
• The core of a simple game with ordinal preferences
• The vetoers in a simple game with ordinal preferences

Cited in

(4)

• Computability of simple games: a complete investigation of the sixty-four possibilities
• Computability of simple games: A characterization and application to the core
• Bounds for the Nakamura number
• Social choice and computational complexity

This page was built for publication: Computational complexity in the design of voting rules

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