Computational complexity in the design of voting systems

Koji Takamiya and Akira Tanaka

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. -- computational complexity ; NP-completeness ; simple game ; core ; stability ; Nakamura number

MoreLess

Year of publication:	Mar. 2006
Other Persons:	Takamiya, Koji (contributor) ; Tanaka, Akira (contributor)
Publisher:	Osaka : Inst. of Social and Economic Research, Osaka Univ.
Subject:	Abstimmungsregel \| Voting rule \| Theorie \| Theory

Extent:	Online-Ressource, 7 S., Text
Series:	Discussion paper / Institute of Social and Economic Research. - Osaka : [Verlag nicht ermittelbar], ISSN 2435-0982, ZDB-ID 2106942-6. - Vol. 653
Type of publication:	Book / Working Paper
Type of publication (narrower categories):	Arbeitspapier ; Working Paper
Language:	English
Notes:	Systemvoraussetzungen: Acrobat Reader
Other identifiers:	hdl:10419/92844 [Handle]
Classification:	C71 - Cooperative Games ; D71 - Social Choice; Clubs; Committees; Associations
Source:	ECONIS - Online Catalogue of the ZBW

Persistent link: https://ebvufind01.dmz1.zbw.eu/10003321306