Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/92844
Authors: 
Takamiya, Koji
Tanaka, Akira
Year of Publication: 
2006
Series/Report no.: 
ISER Discussion Paper, Institute of Social and Economic Research, Osaka University 653
Abstract: 
This paper discusses an aspect of computational complexity in social choice theory. We consider the problem of designing voting rules, which is formulated in terms of simple games. We prove that it is an NP-complete problem to decide whether a given simple game is stable, or not.
Subjects: 
computational complexity
NP-completeness
simple game
core
stability
Nakamura number
JEL: 
C71
D71
Document Type: 
Working Paper

Files in This Item:
File
Size
151.32 kB





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.