nach oben

Social Choice and Welfare

Erschienen in:

09.08.2019 | Original Paper

The expanding approvals rule: improving proportional representation and monotonicity

verfasst von: Haris Aziz, Barton E. Lee

Erschienen in: Social Choice and Welfare | Ausgabe 1/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Proportional representation (PR) is often discussed in voting settings as a major desideratum. For the past century or so, it is common both in practice and in the academic literature to look towards the single transferable vote (STV) rule as the solution for achieving PR. Some of the most prominent electoral reform movements around the globe are pushing for the adoption of STV. It has been termed a major open problem to design a voting rule that satisfies the same PR properties as STV and better monotonicity properties. In this paper, we first present a taxonomy of proportional representation axioms for general weak order preferences, some of which generalise and strengthen previously introduced concepts. We then present a rule called the expanding approvals rule (EAR) that satisfies properties stronger than the central PR axiom satisfied by STV, can handle indifferences in a convenient and computationally efficient manner, and also satisfies better candidate monotonicity properties. In view of this, our proposed rule seems to be a compelling solution for achieving proportional representation in voting settings.

Nächster Artikel Identifying changing taste from demand data via golden eggs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

Here single-district means that the winning candidate set is expected to represent all voters, rather than having the voters ex-ante partitioned into districts with each district having their own winning candidate(s). Note that in practice this ‘single-district’ is often an amalgamation of multiple lower-government level districts.

The setting is referred to as a preferential voting system. It is more general and flexible than settings in which voters vote for their respective parties and then the number of seats apportioned to the parties is proportional to the number of votes received by the party (Pukelsheim 2014).

Proportional representation may be the fairest way for representation but it also allows for an extreme group to have some representation at least when the group is large enough. PR also need not be the most effective approach to a stable government. Black (1958) wrote that “It [PR] makes it difficult to form a cabinet which can command a parliamentary majority and so makes for weak government.”

Notable uses of STV include Oscar nominations, internal elections of the British Liberal Democrats, and selection of Oxford Union, Cambridge Union, and Harvard/Radcliffe Undergraduate Councils.

There are two PSC axioms that differ in only whether the Hare quota is used or whether the Droop quota is used. The one with respect to the Droop quota has also been referred to as DPC (Droop’s proportionality criterion) (Woodall 1994). Woodall (1994) went as far as saying that “I assume that no member of the Electoral Reform Society will be satisfied with anything that does not satisfy DPC.”

Although it is easy to compute one outcome of STV, checking whether a certain set is a possible outcome of STV is NP-complete (Conitzer et al. 2009).

One notable exception was philosopher Michael Dummett who was a stringent critic of STV. He proposed a rival PR method called the Quota Borda System (QBS) and pushed its case (Dummett 1984, 1997). However, even he agreed that in terms of achieving PR, “[STV] guarantees representation for minorities to the greatest degree to which any possible electoral system is capable of doing” (Dummett 1997) [page 137].

Hill (2001) and Meek (1994) propose one way to handle indifferences but it leads to an algorithm that may take time O(m!).

Later we provide a generalised version which accounts for weak preferences in a more appropriate manner. This is necessary since in some cases Dummett’s axiom applied out-of-context to a setting where voters have weak preferences can lead to the PSC axiom being trivially satisfied due to the non-existence of a (non-trivial) solid coalition.

A reason for restricting the parameter q to the interval \((n/(k+1), n/k]\) is as follows. If \(q\le n/(k+1)\), then a q-PSC committee need not exist. If \(q>n/k\), then a committee may satisfy q-PSC but also maintain counterintuitive properties. For example, it may be the case that a committee W satisfies q-PSC while containing candidate(s) who are unanimously less preferred than some candidate not in W.

Droop PSC is also referred to as Droop’s proportionality criterion (DPC). Technically speaking the Droop quota is \(\left\lfloor {n/(k+1)} \right\rfloor +1\). The exact value \(n/(k+1)\) is referred to as the Hagenbach–Bischoff quota.

For fixed n and k, any pair of Droop quotas \(q_1, q_2\) are equivalent in terms of the q-PSC requirement. To see this, note that if \(|N'|\ge \ell q_2\) then \(|N'|> \ell \cdot n/(k+1)\) but then by (1) it must be that \(|N'|\ge \ell q_1\).

A related property for general k is the fixed majority principle (Debord 1993) which requires that if a majority of voters strictly prefers each candidate in a k-sized set Y to each candidate in \(C\backslash Y\), then Y should be the outcome. For \(k=1\), this property is slightly more general than the majority principle of Woodall (1997) since it allows indifference within the candidate sets Y and \(C\backslash Y\), while Woodall’s focus is on settings where voters have strict preferences. For \(k=1\), fixed majority principle is a strictly weaker concept than generalised Droop-PSC (to be presented in Definition 6). However, for \(k>1\), the fixed majority principle is incomparable with any of our PSC concepts and is not aligned with proportional representation. For discussion on other properties in multiwinner voting that are related to majority comparisons, we refer to the papers by Gehrlein (1985) and Aziz et al. (2017b).

The lemma is stated for \(q\in (n/(k+1), n/k]\), however, more generally it holds for any positive q.

Recall that it is assumed that no voter is completely indifferent between all candidates.

Some of these papers consider irresolute voting rules whereby the rule selects a set of potential winners (of arbitrary size) rather than a single winner.

Sánchez-Fernández and Fisteus (2019) also consider two other monotonicity axioms that involve increasing the number of voters, and allowing (simultaneous) reinforcements by groups of voters.

Elkind et al. (2017) also consider a committee monotonicity axioms that involves comparing outcomes of voting rules as the size of the winning committee, k, increases. For resolute voting rules, Barberà and Coelho (2008) introduced a similar axiom referred to as enlargement consistency.

This terminology of “supporting” and “supported” is also used in the context of strict preferences in Definition 1. It will be clear from context whether the intended meaning is with respect to the generalised solid coalition definition or the original solid coalition definition.

We note that despite this procedure choosing an arbitrary candidate when indifferences are present, the definitions involving \(c^{(i,j)}\) are independent of this candidate choice. This follows since the definitions utilise only the relative rank of candidate \(c^{(i,j)}\) with respect to \(\succsim _i\). Thus, our results and definitions are not simply attained by deriving a profile of strict preferences from a profile of weak preferences.

Although our model assumes no voter is completely indifferent between all candidates (and hence rules out this case), we include it to highlight that our result holds without this assumption.

Here \(\max _{\succsim _i}(C)\) denote the equivalence class of (strictly) most preferred candidates in C with respect to \(\succsim _i\).

Details of this reweighting process will be provided later.

If two candidates have equivalent rank vectors we can break ties using any pre-determined ordering of candidate labels to attain L, e.g., alphabetical. This ensures that the priority ordering L is complete.

When introducing the family of STV rules in Sect. 6 we will discuss other possible reweighting schemes.

Recall that we only consider non-degenerate preference profiles, i.e., we assume no voter is completely indifferent between all candidate.

Fractional reweighting in STV has been referred to as Gregory or ‘senatorial’ (see e.g., Janson 2016; Tideman 1995).

Note that the discrete reweighting rule will reduce individual voter weights by fractions.

Our results for STV will explicitly state the reweighting method where relevant. If no reference to the reweighting procedure is made, then the result holds for all reweighting methods.

Technically speaking, our definition of CM only considers reinforcements by a single voter. However, it is easy to see (by considering a sequence of single-voter reinforcements) that if a violation occurs when multiple voters reinforce the same winning candidate then there must be a violation of CM w.r.t. to a single voter’s reinforcement.

The description of the rule is somewhat informal and long in the original books of Dummett which may have lead to The Telegraph terming the rule as “a highly complex arrangement” (Telegraph 2011).

Geller (2002) wrongly claims that QBS satisfies the stronger axiom of CM.

QBS checks for PSC requirements and adds suitable number of candidates to represent the corresponding solid coalition of voters. In order to work for generalised PSC, QBS will have to identify whether solid coalitions of voters and meet their requirement which means that it will need to solve the problem of testing generalised PSC which is coNP-complete.

Hare-EAR is simply EAR where, instead of using the default quota \(\bar{q}\), the Hare quota \(q_H=n/k\) is applied.

However, Janson (2016) does note that one may possibly view the Bottoms-up method as an ordered version of Thiele’s Elimination Method.

A closely related method is called Greedy Approval Voting (GreedyAV or GAV) (Aziz et al. 2017a).

In fact, the example shows that the method fails the even weaker concept of Justified Representation (Aziz et al. 2017a).

Since these rules are Condorcet-consistent, they are vulnerable to the no-show paradox (Moulin 1988).

Recall that \(A_i^{(j)}\) is the subset of candidates which voter i weakly prefers to her jth most preferred candidate.

Technically speaking, if the number of elected and unelected, but also uneliminated, candidates is equal to k, i.e., \(|C^*|=k\), then the set of all such candidates, \(C^*\), are elected simultaneously in the same iteration. Within this proof and for simplicity of notation, we assume that if such situation has occurred the election of the candidates in \(C^*\) occurs in a sequential manner and supporting voter weights are reduced as per line 9–11 of Algorithm 2. Clearly, this assumption is without loss of generality.

Aiyar KVK (1930) Proportional representation by the single transferable vote: the system and its methods. The Madras Law Journal Press, Chennai

Arrow KJ (1959) A difficulty in the concept of social welfare. J Political Econ 58:328–346CrossRef

Aleskerov F, Karpov A (2013) A new single transferable vote method and its axiomatic justification. Soc Choice Welf 40(13):771–786CrossRef

Aziz H, Huang S (2016) Computational complexity of testing proportional justified representation. Technical report. arXiv:1612.06476

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 joint conference on autonomous agents and multi-agent systems (AAMAS). pp 107–115

Aziz H, Brill M, Conitzer V, Elkind E, Freeman R, Walsh T (2017a) Justified representation in approval-based committee voting. Soc Choice Welf 48:461–485CrossRef

Aziz H, Elkind E, Faliszewski P, Lackner M, Skowron P (2017b) The Condorcet principle for multiwinner elections: from shortlisting to proportionality. In: Proceedings of the 26th international joint conference on artificial intelligence (IJCAI). pp 84–90

Aziz H, Elkind E, Huang S, Lackner M, Sánchez-Fernández L, Skowron P (2018a) On the complexity of Extended and Proportional Justified Representation. In: Proceedings of the 32nd AAAI conference on artificial intelligence (AAAI). AAAI Press, pp 902–909

Aziz H, Lee BE, Talmon N (2018b) Proportionally representative participatory budgeting: axioms and algorithms. In: Proceedings of the 17th international joint conference on autonomous agents and multi-agent systems (AAMAS). pp 23–31

Black D (1958) The theory of committees and elections. Cambridge University Press, Cambridge

Bowler S, Grofman B (2000) Introduction: STV as an embedded Institution. In: Elections in Australia, Ireland, and Malta under the single transferable vote: reflections on an embedded institution. pp 1–14

Barberà S, Coelho D (2008) How to choose a non-controversial list with k names. Soc Choice Welf 31(1):79–96CrossRef

Brams S, Sanver R (2009) Voting systems that combine approval and preference. In: The mathematics of preference, choice and order. Springer, pp 215–237

Brill M, Freeman R, Janson S, Lackner M (2017) Phragmén’s voting methods and justified representation. In: Proceedings of the 31st AAAI conference on artificial intelligence (AAAI). AAAI Press, pp 406–413

Cabannes Y (2004) Participatory budgeting: a significant contribution to participatory democracy. Environ Urban 16(1):27–46CrossRef

Chamberlin JR, Courant PN (1983) Representative deliberations and representative decisions: proportional representation and the Borda rule. Am Political Sci Rev 77(3):718–733CrossRef

Conitzer V, Rognlie M, Xia L (2009) Preference functions that score rankings and maximum likelihood estimation. In: Proceedings of the 21st international joint conference on artificial intelligence (IJCAI). AAAI Press, pp 109–115

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

Debord B (1993) Prudent k-choice functions: properties and algorithms. Math Soc Sci 26:63–77CrossRef

Dummett M (1997) Principles of electoral reform. Oxford University Press, Oxford

Doron G, Kronick R (1977) Single transferrable vote: an example of a perverse social choice function. Am J Political Sci 21(2):303–311CrossRef

Elkind E, Faliszewski P, Skowron P, Slinko A (2017) Properties of multiwinner voting rules. Soc Choice Welf 48(3):599–632CrossRef

Fishburn PC (1982) Monotonicity paradoxes in the theory of elections. Discrete Appl Math 4:119–134CrossRef

Faliszewski P, Talmon N (2019) A framework for approval-based budgeting methods. In: Proceedings of the 33rd AAAI conference on artificial intelligence (AAAI)

Faliszewski P, Skowron P, Slinko A, Talmon N (2017) Multiwinner voting: a new challenge for social choice theory. In: Endriss U (ed) Trends in computational social choice, chapter 2

Fluschnik T, Skowron P, Triphaus M, Wilker K (2019) Fair knapsack. In: Proceedings of the 33rd AAAI conference on artificial intelligence (AAAI)

Gehrlein WV (1985) The Condorcet criterion and committee selection. Math Soc Sci 10(3):199–209CrossRef

Geller C (2002) Single transferable vote with Borda elimination: a new vote-counting system. Technical report 2201, Deakin University, Faculty of Business and Law

Goel A, Anilesh KK, Sakshuwong S, Aitamurto T (2019) Knapsack voting for participatory budgeting. ACM Trans Econ Comput (TEAC) 7(2):8:1–8:27CrossRef

Hill ID (2001) Difficulties with equality of preference. Voting Matters 13

Janson S (2016) Phragmén’s and Thiele’s election methods. Technical report. arXiv:1611.08826 [math.HO]

Kilgour DM (2010) Approval balloting for multi-winner elections. In: Handbook on approval voting, chapter 6. Springer

Lackner M, Skowron P (2018) Approval-based multi-winner rules and strategic voting. In: Proceedings of the 27th international joint conference on artificial intelligence (IJCAI)

Laslier J-F, Sanver MR (eds) (2010) Handbook on approval voting. Studies in choice and welfare. Springer, Berlin

Moulin H (1988) Condorcet’s principle implies the No Show Paradox. J Econ Theory 45:53–64CrossRef

Meek BL (1994) A new approach to the single transferable vote, paper ii. Voting Matters 1

Monroe BL (1995) Fully proportional representation. Am Political Sci Rev 89(4):925–940CrossRef

Pukelsheim F (2014) Proportional representation: apportionment methods and their applications. Springer, BerlinCrossRef

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

Rios J, Insua DR, Fernandez E, Rivero JA (2005) Participatory budget formation through the web. In: Proceedings of E-Government: towards electronic democracy, international conference, TCGOV 2005, Bolzano, Italy, March 2-4, 2005. pp 268–276CrossRef

Smith JH (1973) Aggregation of preferences with variable electorate. Econometrica 41(6):1027–1041CrossRef

Schulze M (2002) On Dummett’s ‘Quota Borda System’. Voting Matters 15(3)

Schulze M (2011) Free riding and vote management under proportional representation by single transferable vote

Sanver MR, Zwicker WS (2009) One-way monotonicity as a form of strategy-proofness. Int J Game Theory 38:553–574CrossRef

Sanver MR, Zwicker WS (2012) Monotonicity properties and their adaptation to irresolute social choice rules. Soc Choice Welf 39:371–398CrossRef

Sánchez-Fernández L, Fisteus JA (2019) Monotonicity axioms in approval-based multi-winner voting rules. In: Proceedings of the 18th international joint conference on autonomous agents and multi-agent systems (AAMAS)

Sánchez-Fernández L, Fernández N, Fisteus LA (2016) Fully open extensions to the D’Hondt method. Technical report. arXiv:1609.05370 [cs.GT]

Sánchez-Fernández L, Elkind E, Lackner M (2017a) Committees providing EJR can be computed efficiently. Technical report. arXiv:1704.00356

Sánchez-Fernández L, Elkind E, Lackner M, Fernández N, Fisteus JA, Basanta Val P, Skowron P (2017b) Proportional justified representation. In: Proceedings of the 31st AAAI conference on artificial intelligence (AAAI). AAAI Press

Tideman N (1995) The single transferable vote. J Econ Perspect 9(1):27–38CrossRef

Tideman TN (2006) Collective decisions and voting: the potential for public choice. Ashgate, Farnham

The Telegraph (2011) Professor Sir Michael Dummett. http://www.telegraph.co.uk/news/obituaries/culture-obituaries/8981654/Professor-Sir-Michael-Dummett.html

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

Woodall DR (1994) Properties of preferential election rules. Voting Matters 3

Woodall DR (1997) Monotonicity of single-seat preferential election rules. Discrete Appl Math 77(1):81–98CrossRef

Zwicker WS (2016) Introduction to the theory of voting. In: Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (eds) Handbook of computational social choice, chapter 2. Cambridge University Press, Cambridge

Titel: The expanding approvals rule: improving proportional representation and monotonicity
verfasst von: Haris Aziz
Barton E. Lee
Publikationsdatum: 09.08.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Social Choice and Welfare / Ausgabe 1/2020
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-019-01208-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2020

Vote and voice: an experiment on the effects of inclusive governance rules

Single-crossing choice correspondences

Governance efficiency with and without government

Lobbying as a multidimensional tug of war

Robust bounds on choosing from large tournaments

A characterization of the single-peaked single-crossing domain