Top

Social Choice and Welfare

Published in:

09-01-2017 | Original Paper

Justified representation in approval-based committee voting

Authors: Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, Toby Walsh

Published in: Social Choice and Welfare | Issue 2/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article The prediction value

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

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

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

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

Alcalde-Unzu J, Vorsatz M (2009) Size approval voting. J Econ Theory 144(3):1187–1210CrossRef

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–420CrossRef

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–733CrossRef

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–157CrossRef

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

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

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–517CrossRef

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

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–940CrossRef

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

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–103CrossRef

Skowron P, Yu L, Faliszewski P, Elkind E (2015b) The complexity of fully proportional representation for single-crossing electorates. Theor Comput Sci 569:43–57CrossRef

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

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–38CrossRef

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–34CrossRef

Title: Justified representation in approval-based committee voting
Authors: Haris Aziz
Markus Brill
Vincent Conitzer
Edith Elkind
Rupert Freeman
Toby Walsh
Publication date: 09-01-2017
Publisher: Springer Berlin Heidelberg
Published in: Social Choice and Welfare / Issue 2/2017
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-016-1019-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2017

A partial taxonomy of judgment aggregation rules and their properties

On the maximization of menu-dependent interval orders

The one-dimensional Euclidean domain: finitely many obstructions are not enough

John A. Weymark: President-elect of the Society for Social Choice and Welfare 2006–2007, President 2008–2009

The prediction value

A comment on Koh’s “The optimal design of fallible organizations: invariance of optimal decision threshold and uniqueness of hierarchy and polyarchy structures”