Abstract
We consider approval-based committee voting, i.e. the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (\(\mathrm {JR}\)). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides \(\mathrm {JR}\). However, it turns out that several prominent approval-based voting rules may fail to output such a committee. In particular, while Proportional Approval Voting (\(\mathrm {PAV}\)) always outputs a committee that provides \(\mathrm {JR}\), Sequential Proportional Approval Voting (\(\mathrm {SeqPAV}\)), which is a tractable approximation to \(\mathrm {PAV}\), does not have this property. We then introduce a stronger version of the \(\mathrm {JR}\) axiom, which we call extended justified representation (\(\mathrm {EJR}\)), and show that \(\mathrm {PAV}\) satisfies \(\mathrm {EJR}\), while other rules we consider do not; indeed, \(\mathrm {EJR}\) can be used to characterize \(\mathrm {PAV}\) within the class of weighted \(\mathrm {PAV}\) rules. We also consider several other questions related to \(\mathrm {JR}\) and \(\mathrm {EJR}\), including the relationship between \(\mathrm {JR}\)/\(\mathrm {EJR}\) and core stability, and the complexity of the associated computational problems.
Similar content being viewed by others
Notes
\(\mathrm {SAV}\) is equivalent to equal and even cumulative voting (e.g., see Alcalde-Unzu and Vorsatz 2009), where for each voter, a score of 1 is divided evenly among all candidates in the voter’s approval set, and the k candidates with the highest total score are selected (see also Brams and Kilgour 2014, p. 328).
We are grateful to Svante Janson and Xavier Mora for pointing this out to us.
It is convenient to think of \({\mathbf {w}}\) as an infinite vector; note that for an election with m candidates only the first m entries of \({\mathbf {w}}\) matter. To analyze the complexity of \({\mathbf {w}}\)-\(\mathrm {PAV}\) rules, one would have to place additional requirements on \({\mathbf {w}}\); however, we do not consider computational properties of such rules in this paper.
For readability, we use the Hare quota \(\left\lceil \frac{n}{k}\right\rceil \); this choice of quota motivates our name for this rule. However, all our proofs go through if we use the Droop quota \(\left\lfloor \frac{n}{k+1}\right\rfloor +1\) instead. For a discussion of differences between these two quotas, see the article of Tideman (1995).
References
Alcalde-Unzu J, Vorsatz M (2009) Size approval voting. J Econ Theory 144(3):1187–1210
Aziz H, Gaspers S, Gudmundsson J, Mackenzie S, Mattei N, Walsh T (2015) Computational aspects of multi-winner approval voting. In: Proceedings of the 14th international conference on autonomous agents and multiagent systems (AAMAS), pp 107–115
Aziz H, Lang J, Monnot J (2016) Computing Pareto optimal committees. In: Proceedings of the 25th international joint conference on artificial intelligence (IJCAI), pp 60–66
Betzler N, Slinko A, Uhlmann J (2013) On the computation of fully proportional representation. J Artif Intell Res 47:475–519
Brams SJ (2010) Preface. In: Laslier JF, Sanver MR (eds), Handbook on approval voting, studies in choice and welfare, Springer, New York, pp vii–ix
Brams SJ, Fishburn PC (2007) Approval voting, 2nd edn. Springer, New York
Brams SJ, Kilgour DM (2014) Satisfaction approval voting. In: Fara R, Leech D, Salles M (eds) Voting power and procedures, studies in choice and welfare. Springer, New York, pp 323–346
Brams SJ, Kilgour DM, Sanver MR (2006) How to elect a representative committee using approval balloting. In: Simeone B, Pukelsheim F (eds) Mathematics and democracy: recent advances in voting systems and collective choice. Springer, New York, pp 83–96
Brams SJ, Kilgour DM, Sanver RM (2007) A minimax procedure for electing committees. Public Choice 132(3–4):401–420
Byrka J, Sornat K (2014) PTAS for minimax approval voting. In: Proceedings of the 10th international conference on web and internet economics (WINE), pp 203–217
Caragiannis I, Kalaitzis D, Markakis E (2010) Approximation algorithms and mechanism design for minimax approval voting. In: Proceedings of the 24th AAAI conference on artificial intelligence (AAAI), pp 737–742
Caragiannis I, Kaklamanis C, Karanikolas N, Procaccia AD (2014) Socially desirable approximations for Dodgson’s voting rule. ACM Trans Algorithm 10(2). doi:10.1145/2556950
Chamberlin B, Courant P (1983) Representative deliberations and representative decisions: proportional representation and the Borda rule. Am Polit Sci Rev 77(3):718–733
Cornaz D, Galand L, Spanjaard O (2012) Bounded single-peaked width and proportional representation. In: Proceedings of the 20th European conference on artificial intelligence (ECAI), pp 270–275
Davis M, Orrison ME, Su FE (2014) Voting for committees in agreeable societies. Contemp Math 624:147–157
Droop HR (1881) On methods of electing representatives. J Stat Soc Lond 44(2):141–196
Duddy C (2014) Electing a representative committee by approval ballot: an impossibility result. Econ Lett 124:14–16
Dummett M (1984) Voting procedures. Oxford University Press, Oxford
Elkind E, Lackner M (2015) Structure in dichotomous preferences. In: Proceedings of the 24th international joint conference on artificial intelligence (IJCAI), pp 2019–2025
Elkind E, Faliszewski P, Skowron P, Slinko A (2017) Properties of multiwinner voting rules. Soc Choice Welf (forthcoming)
Elkind E, Lang J, Saffidine A (2015) Condorcet winning sets. Soc Choice Welf 44(3):493–517
Endriss U (2013) Sincerity and manipulation under approval voting. Theor Decis 74(4):335–355
Fishburn PC, Pekec AS (2004) Approval voting for committees: threshold approaches. Techn Rept
Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H Freeman and Company, New York
Kilgour DM (2010) Approval balloting for multi-winner elections. In: Laslier JF, Sanver MR (eds) Handbook on approval voting, chapter 6, Springer, New York, pp 105–124
Kilgour DM, Marshall E (2012) Approval balloting for fixed-size committees. In: Felsenthal DS, Machover M (eds), Electoral systems, studies in choice and welfare, Springer, New York, pp 305–326
Laslier J-F, Sanver MR (eds) (2010) Handbook on approval voting. Studies in choice and welfare. Springer, New York
LeGrand R, Markakis E, Mehta A (2007) Some results on approximating the minimax solution in approval voting. In: Proceedings of the 6th international conference on autonomous agents and multi-agent systems (AAMAS), pp 1185–1187
Lu T, Boutilier C (2011) Budgeted social choice: from consensus to personalized decision making. In: Proceedings of the 22nd international joint conference on artificial intelligence (IJCAI), AAAI Press, Cambridge, pp 280–286
Meir R, Procaccia AD, Rosenschein JS, Zohar A (2008) Complexity of strategic behavior in multi-winner elections. J Artif Intell Res 33:149–178
Misra N, Nabeel A, Singh H (2015) On the parameterized complexity of minimax approval voting. In: Proceedings of the 14th international conference on autonomous agents and multiagent systems (AAMAS), pp 97–105
Monroe B (1995) Fully proportional representation. Am Polit Sci Rev 89(4):925–940
Procaccia A, Rosenschein J, Zohar A (2008) On the complexity of achieving proportional representation. Soc Choice Welf 30(3):353–362
Sánchez-Fernández L, Fernández N, Fisteus JA, Basanta-Val P (2016) Some notes on justified representation. In: Proceedings of the 10th multidisciplinary workshop on advances in preference handling (MPREF)
Sánchez-Fernández L, Elkind E, Lackner M, Fernández N, Fisteus JA, Basanta-Val P, Skowron P (2017) Proportional justified representation. In: Proceedings of the 31st AAAI conference on artificial intelligence (AAAI)
Skowron P, Faliszewski P, Slinko A (2015a) Achieving fully proportional representation: approximability results. Artif Intell 222:67–103
Skowron P, Yu L, Faliszewski P, Elkind E (2015b) The complexity of fully proportional representation for single-crossing electorates. Theor Comput Sci 569:43–57
Skowron P, Faliszewski P, Lang J (2016) Finding a collective set of items: from proportional multirepresentation to group recommendation. Artif Intell 241:191–216
Thiele TN (1895) Om flerfoldsvalg. In: Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, pp 415–441
Tideman N (1995) The single transferable vote. J Econ Perspect 9(1):27–38
Tideman N (2006) Collective decisions and voting. Ashgate, Surrey
Tideman N, Richardson D (2000) Better voting methods through technology: the refinement-manageability trade-off in the single transferable vote. Public Choice 103(1–2):13–34
Acknowledgements
The authors thank the anonymous reviewers of the Multidisciplinary Workshop on Advances in Preference Handling (MPREF 2014), and the Twenty-ninth AAAI Conference (AAAI 2015) for their helpful feedback on earlier versions of the paper. We further thank Svante Janson, Martin Lackner, Xavier Mora, and Piotr Skowron for valuable discussions. Brill, Conitzer, and Freeman were supported by NSF and ARO under Grants CCF-1101659, IIS-0953756, IIS-1527434, CCF-1337215, W911NF-12-1-0550, and W911NF-11-1-0332, by a Feodor Lynen research fellowship of the Alexander von Humboldt Foundation, and by COST Action IC1205 on Computational Social Choice. Aziz is supported by a Julius Career Award. Brill and Elkind were partially supported by ERC-StG 639945. Conitzer is supported by a Guggenheim Fellowship. Walsh also receives support from the Asian Office of Aerospace Research and Development (AOARD 124056) and the German Federal Ministry for Education and Research through the Alexander von Humboldt Foundation.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Aziz, H., Brill, M., Conitzer, V. et al. Justified representation in approval-based committee voting. Soc Choice Welf 48, 461–485 (2017). https://doi.org/10.1007/s00355-016-1019-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00355-016-1019-3