Abstract
We demonstrate that winner selection in two prominent proportional representation voting systems is a computationally intractable problem—implying that these systems are impractical when the assembly is large. On a different note, in settings where the size of the assembly is constant, we show that the problem can be solved in polynomial time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bartholdi J, Orlin J (1991) Single transferable vote resists strategic voting. Soc Choice Welf 8:341–354
Bartholdi J, Tovey CA, Trick MA (1989) The computational difficulty of manipulating an election. Soc Choice Welf 6:227–241
Bartholdi J, Tovey CA, Trick MA (1989) Voting schemes for which it can be difficult to tell who won the election. Soc Choice Welf 6:157–165
Brams SJ, Fishburn PC (2002) Voting procedures. In: Arrow KJ, Sen AK, Suzumura K (eds). Handbook of social choice and welfare. (Chap. 4). North-Holland
Chamberlin JR, Courant PN (1983) Representative deliberations and representative decisions: Proportional representation and the Borda rule. Am Polit Sci Rev 77(3):718–733
Conitzer V, Sandholm T (2002) Complexity of manipulating elections with few candidates. In: Proceedings of the national conference on artificial intelligence. Edmonton, Canada, pp 314–319
Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. (2nd edn) MIT Press
Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of \(\mathcal{NP}\)-completeness. Freeman WH
Kariv O, Hakimi L (1979) An algorithmic approach to nework location problems. part ii: The p-medians. SIAM J Appl Math 37(3):539–560
Monroe BL (1995) Fully proportional representation. Am Polit Sci Rev 89(4):925–940
Papadimitriou CH (1981) On the complexity of integer programming. J Assoc Comput Mach 28(4)
Papadimitriou CH (1994) Computational Complexity. Addison Wesley
Potthoff RF, Brams SJ (1998) Proportional representation: broadening the options. J Theor Polit 10(2)
Procaccia AD, Rosenschein JS (2007) Junta distributions and the average-case complexity of manipulating elections. J Artif Intell Res 28:157–181
Sipser M (1996) Introduction to the theory of computation. Course Technology
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Procaccia, A.D., Rosenschein, J.S. & Zohar, A. On the complexity of achieving proportional representation. Soc Choice Welfare 30, 353–362 (2008). https://doi.org/10.1007/s00355-007-0235-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00355-007-0235-2