This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

Computational Complexity in the Design of Voting Rules

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
Koji Takamiya
Akira Tanaka
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.

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

File URL: http://www.iser.osaka-u.ac.jp/library/dp/2006/DP0653.pdf
File Format:
File Function:
Download Restriction: no

Publisher Info
Paper provided by Institute of Social and Economic Research, Osaka University in its series ISER Discussion Paper with number 0653.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length:
Date of creation: Mar 2006
Date of revision: Jul 2006
Handle: RePEc:dpr:wpaper:0653

Contact details of provider:
Postal: 6-1 Mihogaoka, Ibaraki, Osaka 567-0047
Fax: 81-6-6878-2766
Email:
Web page: http://www.iser.osaka-u.ac.jp/index-e.html
More information through EDIRC

For technical questions regarding this item, or to correct its listing, contact: (Fumiko Matsumoto).

Related research
Keywords:

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:

  1. Boros, Endre & Gurvich, Vladimir, 2000. "Stable effectivity functions and perfect graphs," Mathematical Social Sciences, Elsevier, vol. 39(2), pages 175-194, March. [Downloadable!] (restricted)
  2. Moulin, H. & Peleg, B., 1982. "Cores of effectivity functions and implementation theory," Journal of Mathematical Economics, Elsevier, vol. 10(1), pages 115-145, June. [Downloadable!] (restricted)
  3. Atila Abdulkadiroglu & Tayfun Smez, 2003. "School Choice: A Mechanism Design Approach," Discussion Papers 0203-18, Columbia University, Department of Economics. [Downloadable!]
  4. Shinotsuka, Tomoichi & Takamiya, Koji, 2003. "The weak core of simple games with ordinal preferences: implementation in Nash equilibrium," Games and Economic Behavior, Elsevier, vol. 44(2), pages 379-389, August. [Downloadable!] (restricted)
  5. Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004. "Kidney Exchange," The Quarterly Journal of Economics, MIT Press, vol. 119(2), pages 457-488, May. [Downloadable!] (restricted)
    Other versions:
  6. Mizutani, Masayoshi & Hiraide, Yasuhiko & Nishino, Hisakazu, 1993. "Computational Complexity to Verify the Unstability of Effectivity Function," International Journal of Game Theory, Springer, vol. 22(3), pages 225-39.
Full references

Statistics
Access and download statistics

Did you know? IDEAS indexes over 800000 items of research in Economics alone.

This page was last updated on 2009-12-24.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.