Computational complexity in the design of voting rules

&
Theory and Decision 80 (1):33-41 (2016)
  Copy   BIBTEX

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.

Categories

Add categories

Keywords

Reprint years

DOI

10.1007/s11238-014-9422-7

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,846

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

A characterization of majority voting rules with quorums.Nicolas Houy - 2009 - Theory and Decision 67 (3):295-301.
On the stability of a triplet of scoring rules.Mostapha Diss & Vincent Merlin - 2010 - Theory and Decision 69 (2):289-316.
Complexity of admissible rules.Emil Jeřábek - 2007 - Archive for Mathematical Logic 46 (2):73-92.
Structural database for reducing cost in materials design and complexity of multiscale computations.Nikolai Zarkevich - 2006 - Complexity 11 (4):36-42.
Computational representations of architectural design for tall buildings.Ajla Aksamija - 2009 - Complexity 15 (2):45-53.
Complexity and postmodernism: understanding complex systems.Paul Cilliers - 1998 - New York: Routledge.
Computation models for parameterized complexity.Marco Cesati & Miriam Dilanni - 1997 - Mathematical Logic Quarterly 43 (2):179-202.
A complexity perspective on institutional design.Scott E. Page - 2012 - Politics, Philosophy and Economics 11 (1):5-25.
Sincere‐Strategy Preference‐Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control.Gábor Erdélyi, Markus Nowak & Jörg Rothe - 2009 - Mathematical Logic Quarterly 55 (4):425-443.
On the nature of rules and conversation.Andrew Fordham & Nigel Gilbert - 1995 - AI and Society 9 (4):356-372.
Decision-theoretic paradoxes as voting paradoxes.Rachael Briggs - 2010 - Philosophical Review 119 (1):1-30.
Communication compatible voting rules.Mark Thordal-Le Quement - 2013 - Theory and Decision 74 (4):479-507.
The Computational Complexity of Quantified Reciprocals.Jakub Szymanik - 2009 - In Peter Bosch, David Gabelaia & Jérôme Lang (eds.), Lecture Notes on Artificial Intelligence 5422, Logic, Language, and Computation 7th International Tbilisi Symposium on Logic, Language, and Computation. Springer.
The “who designed the designer?” objection to design arguments.Lloyd Strickland - 2014 - International Journal for Philosophy of Religion 75 (2):87-100.
Changing the rules of play.Marc Pauly - 2005 - Topoi 24 (2):209-220.

Analytics

Added to PP
2015-09-03

Downloads
23 (#681,424)

6 months
7 (#428,584)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Add more references