Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Justified representation in approval-based committee voting

  • Original Paper
  • Published:
Social Choice and Welfare Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

Notes

  1. \(\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).

  2. We are grateful to Svante Janson and Xavier Mora for pointing this out to us.

  3. 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.

  4. \({\mathbf {w}}\)-\(\mathrm {PAV}\) rules with \(w_1=0\) have been considered by Fishburn and Pekec (2004) and Skowron et al. (2016). We note that such rules do not satisfy justified representation (as defined in Sect. 3).

  5. 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • Brams SJ, Kilgour DM, Sanver RM (2007) A minimax procedure for electing committees. Public Choice 132(3–4):401–420

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Droop HR (1881) On methods of electing representatives. J Stat Soc Lond 44(2):141–196

    Article  Google Scholar 

  • Duddy C (2014) Electing a representative committee by approval ballot: an impossibility result. Econ Lett 124:14–16

    Article  Google Scholar 

  • Dummett M (1984) Voting procedures. Oxford University Press, Oxford

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Endriss U (2013) Sincerity and manipulation under approval voting. Theor Decis 74(4):335–355

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Procaccia A, Rosenschein J, Zohar A (2008) On the complexity of achieving proportional representation. Soc Choice Welf 30(3):353–362

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Skowron P, Faliszewski P, Lang J (2016) Finding a collective set of items: from proportional multirepresentation to group recommendation. Artif Intell 241:191–216

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Tideman N (2006) Collective decisions and voting. Ashgate, Surrey

    Google Scholar 

  • 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

    Article  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Haris Aziz.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00355-016-1019-3

Navigation