Back to Search
Start Over
Computational complexity in the design of voting rules
- Source :
- Theory and Decision. 80:33-41
- Publication Year :
- 2015
- Publisher :
- Springer Science and Business Media LLC, 2015.
-
Abstract
- This paper considers the computational complexity of the design of voting rules, which is formulated by simple games. We prove that it is an NP-complete problem to decide whether a given simple game is stable, or not.
- Subjects :
- Average-case complexity
Computer Science::Computer Science and Game Theory
Theoretical computer science
Nakamura number
Computational complexity theory
media_common.quotation_subject
Complete
Simple game
General Decision Sciences
Computational resource
Arts and Humanities (miscellaneous)
Simple (abstract algebra)
Voting
0502 economics and business
Developmental and Educational Psychology
Applied Psychology
050205 econometrics
Mathematics
media_common
05 social sciences
FP
ComputingMilieux_PERSONALCOMPUTING
General Social Sciences
Game complexity
NP-completeness
Computer Science Applications
Computational complexity
050206 economic theory
Core
Stability
General Economics, Econometrics and Finance
Algorithm
Subjects
Details
- ISSN :
- 15737187 and 00405833
- Volume :
- 80
- Database :
- OpenAIRE
- Journal :
- Theory and Decision
- Accession number :
- edsair.doi.dedup.....56acb2ce516c8143b244f8395a88219b
- Full Text :
- https://doi.org/10.1007/s11238-014-9422-7