The Expanding Approvals Rule: Improving Proportional Representation and Monotonicity
Haris Aziz Barton Lee








	
	

	
	  H. Aziz B. E. Lee Data61, CSIRO and UNSW,
	 	  Sydney 2052 , Australia 

	 	  Tel.: +61-2-8306 0490 

	 	  Fax: +61-2-8306 0405 

	 haris.aziz@unsw.edu.au, barton.e.lee@gmail.com

	

	
	
	
    		 
    		 







	
	
	



The Expanding Approvals Rule: 

Improving Proportional Representation and Monotonicity
    Haris Aziz Barton E. Lee
    
======================================================================================




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 jump to single transferable vote (STV) 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 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. 


	
	

JEL Classification: C70 · D61 · D71





§ INTRODUCTION













Of all modes in which a national representation can possibly be constituted, this one [STV] affords the best security for the intellectual qualifications desirable in the representatives—John Stuart Mill (Considerations on Representative Government, 1861).
	


	A major unsolved problem is whether there exist rules that retain the important political features of STV and are also more monotonic—<cit.>.
	
	
	We consider a well-studied voting setting in which n voters express ordinal preferences over m candidates and based on the preferences k≤ m candidates are selected. The candidates may or may not be from particular parties but voters express preferences directly over individual candidates.[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 <cit.>. ] 
This kind of voting problem is not only encountered in parliamentary elections but to form any kind of representative body. When making such a selection by a voting rule, a desirable requirement is that of proportional representation. Proportional representation stipulates that voters should get representation in a committee or parliament according to the strengths of their numbers. It is widely accepted that proportional representation is the fairest way to reflect the diversity of opinions among the voters.[Proportional representation may be the fairest way for representation but it also allows for 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. <cit.> wrote that “It [PR] makes it difficult to form a cabinet which can command a parliamentary majority and so makes for weak government.”]  

	
	
 For the last 120 years or so, the most widely used and accepted way to achieve it is via single transferable vote (STV) <cit.> and its several variants. In fact STV is used for elections in several countries including Australia, Ireland, India, and Pakistan. 
 It is also used to select representative committees in hundreds of settings including professional organisations, scientific organizations, political parties, school groups, and university student councils all over the globe.[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.] 
 

The reason for the widespread adoption of STV is partly due to the fact that it has been promoted to satisfy  proportional representation axioms. In particular, STV satisfies a key PR axiom called Proportionality for Solid Coalitions (PSC) <cit.>. <cit.> argues that “It is the fact that STV satisfies PSC that justifies describing STV as a system of proportional representation.” <cit.> also calls the property the “essential feature of STV, which makes it a system of proportional representation.”
 <cit.> motivated PSC as a minority not requiring to coordinate its report and that it should deserve some high preferred candidates to be selected as long as enough voters are `solidly committed to such candidates.' PSC captures the idea that as long as voters have the same top candidates (possibly in different ordering), they do not need to coordinate their preferences to get a justified number of such candidates selected.
In this sense PSC is also similar in spirit to the idea that if a clone of a candidate is introduced, it should not affect the selection of the candidate. 
 Voters from the same party not having to coordinate their reports as to maximize the number of winners from their own party can be viewed as a weak form of group-strategyproofness. PSC can also be seen as a voter's vote not being wasted due to lack of coordination with like-minded voters. 
PSC has been referred to as “a sine qua non for a fair election rule” by <cit.>.[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) <cit.>. 

<cit.> 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 STV is not necessarily the only rule satisfying PR properties, it is at times synonymous with proportional representation in academia and policy circles. The outcome of STV can also be computed efficiently which makes it suitable for large scale elections.[Although it is easy to compute one outcome of STV, checking whether a certain set is a possible outcome of STV is NP-complete <cit.>.] Another reason for the adoption of STV is historical. Key figures proposed ideas related to STV or pushed for the adoption of STV. The ideas behind STV can be attributed to several thinkers including C. Andrae, T. Hare
, H. R. Droop, and T. W. Hill. For a detailed history of the development of STV family of rules, please see the article by <cit.>. In a booklet, <cit.> explains the rationale behind different components of the STV rule. 
STV was supported by influential intellectuals such as 
John Stuart Mill 
who placed STV “among the greatest improvements yet made in the theory and practice of government.” <cit.> note the British influence on the spread of STV among countries with historical association with Great Britain. 

With historical, normative, and computational motivation behind it, STV has become the  `go to' rule for PR and has strong support.[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 <cit.>. 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” <cit.>[page 137].] It is also vigorously promoted by prominent electoral reform movements across the globe including the Proportional Representation Society of Australia (<http://www.prsa.org.au>) and the Electoral Reform Society (<https://www.electoral-reform.org.uk>). 


Despite the central position of STV, it is not without some flaws. It is well-understood that it violates basic monotonicity properties even when selecting a single candidate <cit.>. Increasing the ranking of the winning candidate may result in the candidate not getting selected. STV is also typically defined for strict preferences which limits its ability to tackle more general weak orders. 
There are several settings where voters may be indifferent between two candidates because  the candidates have the same characteristics that the voter cares about. It could also be that the voter does not have the cognitive power or time to distinguish between two candidates and does not wish to break ties arbitrarily. 
It is not clearly resolved in the literature how STV can be extended to handle weak orders without compromising on its computational efficiency or some of the desirable axiomatic properties it satisfies.[<cit.> and <cit.> propose one way to handle indifferences however, this leads to an algorithm that may take time O(m!).]
The backdrop of this paper is that improving upon STV in terms of both PR as well as monotonicity has been posed as a major challenge <cit.>. 
















  
Contributions










We propose a new voting rule called Expanding Approvals Rule () that has several advantages.
(1) It satisfies an axiom called Generalised PSC that is stronger than PSC. (2) It satisfies some natural monotonicity criteria that are not satisfied by STV.
(3) It is defined on general weak preferences rather than just for strict preferences and hence constitutes a flexible and general rule that finds a suitable outcome in polynomial time for both strict and dichotomous preferences. Efficient computation of a rule is an important concern when we deal with election of large committees. 



Our work also helps understand the specifications under which different variants of STV satisfy different PR axioms. 
Apart from understanding how far STV and satisfy PR axioms, one of the conceptual contributions of this paper is to define a taxonomy of PR axioms based on PSC and identify their relations with each other. In particular, we propose a new axiom for weak preferences called Generalised PSC that simultaneously generalises PSC (for strict preferences) and proportional justified representation (for dichotomous preferences).













§ MODEL AND AXIOMS


In this section, we lay the groundwork of the paper by first defining the model and then formalizing the central axioms by which proportional representation rules are judged. 



 §.§ Model


We consider the standard social choice setting with a set of voters N={1,…, n}, a set of candidates C={c_1,…, c_m} and a preference profile =(_1,…,_n) such that each _i is a complete and transitive relation over C. 
Based on the preference profile, the goal is to select a committee W⊂ C of predetermined size k.
Since our new rule is defined over weak orders rather than strict orders, we allow the voters to express weak orders. 


			 		
						
			 			We write a _i b to denote that voter i values candidate a at least as much as candidate b and use _i for the strict part of _i, i.e., a _i b iff a _i b but not b _i a. Finally, _i denotes i's indifference relation, i.e., a _i b if and only if both a _i b and b _i a.
			 			
			 			The relation _i results in (non-empty) equivalence classes E_i^1,E_i^2, …, E_i^m_i for some m_i such that a_i a' if and only if a∈ E_i^l and a'∈ E_i^l' for some l<l'. Often, we will use these equivalence classes to represent the preference relation of a voter as a preference list
			 			i E_i^1,E_i^2, …, E_i^m_i. If candidate c is in E_i^j, we say it has rank j in voter i's preference. 
			 		For example, we will denote the preferences a_i b_i c by the list i: {a,b}, {c}. 
			 		
					If each equivalence is of size 1, the preferences will be called strict preferences or linear orders. Strict preferences will be represented by a comma separated list of candidates. If for each voter, the number of equivalence classes is at most two, the preferences are referred to as dichotomous preferences. When the preferences of the voters are dichotomous, the voters can be seen as approving a subset of voters. In this case for each voter i∈ N, the first equivalence class E_i^1 is also referred to as the approval set A_i. The vector A=(A_1,…, A_n) is referred to as the approval ballot profile. Since our model concerns ordinal preferences, when a voter i is completely indifferent between all the candidates, it means that E_i^1=C and we do not ascribe any intensity with which these candidates are liked or disliked by voter i. None of our results connecting dichotomous preferences with approval-based committee voting are dependent on how complete indifference is interpreted in terms of all approvals versus all disapprovals.
					
The model allows for voters to express preference lists that do not include some candidates. In that case, the candidates not included in the list will be assumed to form the last equivalence class. 















 §.§ PR under Strict Preferences


In order to understand the suitability of voting rules for proportional representation, we recap the central PR axiom from the literature. It was first mentioned and popularised by <cit.>. It is defined for strict preferences. 



A set of voters N' is a solid coalition for a set of candidates C' if every voter in N' strictly prefers every candidate in C' ahead of every candidate in C\ C'. That is, for all i∈ N' and for any c'∈ C'

    ∀ c∈ C\ C'    c'_i c.

The candidates in C' are said to be supported by voter set N'.


Importantly, the definition of a solid coalition does not require voters to maintain the same order of strict preferences among candidates in C' nor C\ C'. Rather the definition requires only that all candidates in C' are strictly preferred to those in C\ C'. Also notice that a set of voters N' may be a solid coalition for multiple sets of candidates and that the entire set of voters N is trivially a solid coalition for the set of all candidates C. 





















Let q∈ (n/(k+1), n/k]. We say a committee W satisfies q-PSC if for every positive integer ℓ, and for every solid coalition N' supporting a candidate subset C' with size |N'|≥ℓ q, the following holds


    |W∩ C'|≥min{ℓ, |C'|}.






 If q=n/k, then we refer to the property as Hare-PSC. If q=n/(k+1)+ϵ for small ϵ>0 , then we refer to the property as Droop-PSC.[Droop PSC is also referred to as Droop's proportionality criterion (DPC). Technically speaking the Droop quota is n/(k+1)+1. The exact value n/(k+1) is referred to as the  Hagenbach-Bischoff quota.] 
 
There are some reasons to prefer the `Droop' quota n/(k+1)+ϵ for small ϵ>0. Firstly, for k=1 the use of the Droop quota leads to rules that return a candidate that is most preferred by more than half of the voters. Secondly, STV defined with respect to the Droop quota ensures slight majorities get slight majority representation. 
 
Hare-PSC was stated as an essential property that a rule designed for PR should satisfy <cit.>. 
 

When preferences are strict and k=1, <cit.> refers to the restriction of Droop-PSC under these conditions as the majority principle.  The majority principle requires that if a majority of voters are solidly committed to a set of candidates C', then one of the candidates from C' must be selected.

























									Consider the profile with 9 voters and where k=3. Then the voters in set N'={1,2,3} form a solid coalition with respect to Hare quota who support candidates in {c_1,c_2,c_3,c_4}. The voters in set N”={4,5,6,7,8,9} form a solid coalition with respect to Hare quota who support three candidate subsets {e_1}, {e_1, e_2} and {e_1, e_2, e_3}. 
								
    1:      c_1, c_2, c_3, c_4,... 
    
    														2:      c_4, c_1, c_2, c_3,...
    
    														3:      c_2, c_3, c_4, c_1,... 
    
    														4:      e_1, e_2, e_3, ...
    
    														5:      e_1, e_2, e_3,  ...
    
    														6:       e_1, e_2, e_3, ...
    
    														7:      e_1, e_2, e_3, ...
    
    														8:       e_1, e_2, e_3, ...
    
    														9:       e_2, e_1, e_3, ...

	



One can also define a weak version of PSC. In some works <cit.>, the weaker version has been attributed to the original definition of PSC as defined by Dummett. For example, <cit.> in their Definition 2.9 term weak PSC as the property put forth by Dummett although he advocated the stronger property of PSC. 








Let q∈ (n/(k+1), n/k]. A committee W satisfies weak q-PSC if for every positive integer ℓ, and for every solid coalition N' supporting a candidate subset C'  :  |C'|≤ℓ with size |N'|≥ℓ q, the following holds. 

    |W∩ C'|≥min{ℓ, |C'|}.




For weak q-PSC, we restrict our attention to solid coalitions who support sets of candidates of size at most ℓ whereas in q-PSC we impose no such restriction. 
Note that q-PSC implies weak q-PSC but the reverse need not hold. Furthermore, the condition that |C'|≤ℓ and |W∩ C'|≥min{ℓ, |C'|} is equivalent to C'⊆ W. We also note that under strict preferences and k=1, if a majority of the voters have the same most preferred candidate, then weak Droop-PSC implies that the candidate is selected. In particular, this implies that the majority principle is satisfied when weak-Droop PSC is satisfied.  

We now present a lemma connecting (weak) q-PSC for different values of q. The proof is omitted since it is implied by a stronger lemma (Lemma <ref>) proven in section <ref>. 


Let q, q' be real numbers such that q<q'.  If a committee W satisfies (weak) q-PSC then W satisfies (weak) q'-PSC.













 In this paper we focus on PR axioms related to q-PSC where q is a real number contained in the interval (n/k+1, n/k]. The reason for focusing on these values is that a committee satisfying q-PSC committee is guaranteed to exists for any preference profile when q>n/k+1. Whilst whenever q≤n/k a unanimity-like principle is satisfied. That is,  if all voters form a solid coalition for a size-k candidate subset C' then there is a unique committee satisfying q-PSC, i.e, W=C'. However in principle, the PR axioms and many results in this paper can be considered with values of q outside of the interval (n/k+1, n/k].













 
 







 
 



















In section <ref>, we generalise the PSC property to weak preferences which has not been done in the literature.







 
 

 §.§ Candidate Monotoncity Axioms


PR captures the requirement that cohesive groups of voters should get sufficient representation. Another desirable property is candidate monotonicity that requires that increased support for an otherwise-elected candidate should never cause this candidate to become unelected. Candidate monotonicity involves the notion of a candidate being reinforced. 
We say a candidate is reinforced if its relative position is improved while not changing the relative positions of all other candidates. 
More formally, we say that candidate c is reinforced in preference _i to obtain preference _i', if (1)
c _i d  c _i' d for all d∈ C∖{c}; (2)
d _i' c  d _i c for all d∈ C∖{c}; (3)
there exists a d∈ C such that d _i c and c ≻_i' d (in this case c is said to cross over d); and
(4) d _i e  d _i' e for all d,e ≠ c.

We are now in a position to formalise some natural candidate monotonicity properties of voting rules. The definitions apply not just to strict preferences but also to weak preferences. One of the definitions (RRCM) is based on the ranks of candidates as specified in the preliminaries. 






	
 	
  * Candidate Monotonicity (CM): if a winning candidate is reinforced  by a single voter, it remains a winning candidate.
 	
  * Rank Respecting Candidate Monotonicity (RRCM): if a winning candidate c is reinforced  by a single voter without changing the respective ranks of other winning candidates in each voter's preferences, then c remains a winning candidate. 
 
  * Non-Crossing Candidate Monotonicity (NCCM): if a winning candidate c is reinforced  by a single voter without ever crossing over another winning candidate, then c remains a winning candidate. 
 
  * Weak Candidate Monotonicity (WCM): if a winning candidate is reinforced  by a single voter, then some winning candidate still remains winning. 
 
 




NCCM and WCM are extremely weak properties but STV violates them even for k=1.  
We observe the following relations between the properties. 
 
 	The following relations hold. 
	
	
 	
 		



  * RRCM and NCCM are equivalent for linear orders. 

  * CMRRCMNCCM.

  * CMWCM.
		
  * Under k=1, WCM, RRCM, NCCM, and CM are equivalent. 
		
  * Under dichotomous preferences, RRCM and CM are equivalent.
 	
 	
	
	Note that if a rule fails CM for k=1, then it also fails RRCM, NCCM, and WCM.
 
 
















 
 
 
 
 
 
 
 
 

 









 
 
 
 
 
 
  




























§ PR UNDER GENERALISED PREFERENCE RELATIONS


The notion of a solid coalition and PSC can be generalised to the case of weak preferences. In this section, we propose a new axiom called generalised PSC which not only generalises PSC (that is only defined for strict preferences) but also Proportional Justified Representation (PJR) a PR axiom that is only defined for dichotomous preferences. 



A set of voters N' is a generalised solid coalition for a set of candidates C' if every voter in N' weakly prefers every candidate in C' at least as high as every candidate in C\ C'. That is, for all i∈ N' and for any c'∈ C'

    ∀ c∈ C\ C'    c'_i c.



We note that under strict preferences, a generalised solid coalition is equivalent to solid coalition. 
Let c^(i,j) denotes voter i's j-th most preferred candidate. In case the voter's preference has indifferences, we use lexicographic tie-breaking to identify the candidate in the j-th position.











Let q∈ (n/(k+1), n/k]. A committee W satisfies generalised q-PSC if for all generalised solid coalitions N' supporting candidate subset C' with size |N'|≥ℓ q, there exists a set C”⊆ W with size at least min{ℓ, |C'|} such that for all c”∈ C”

    ∃ i∈ N'  :    c”_i c^(i, |C'|).





The idea behind generalised q-PSC is identical to that of q-PSC and in fact generalised q-PSC is equivalent to q-PSC under linear preferences. 
Note that in the definition above, a voter i in the solid coalition of voters N' does not demand membership of candidates from the solidly supported subset C' but of any candidate that is at least as preferred as a least preferred candidate in C'. Generalised weak q-PSC is a natural weakening of generalised q-PSC in which we require that C' is of size at most ℓ.




Let q∈ (n/(k+1), n/k]. A committee W satisfies weak generalised q-PSC if for every positive integer ℓ, and every generalised solid coalition N' supporting a candidate subset C':   |C'|≤ℓ with size |N'|≥ℓ q, there exists a set C”⊆  W with size at least min{ℓ, |C'|} such that for all c”∈ C”

    ∃ i∈ N'  :    c”_i c^(i, |C'|).










The following example shows that generalised q-PSC is a weak property when solid coalitions equal, or just barely exceed, the quota q. 


Let N={1, 2, 3, 4}, C={a, b, …, j}, k=2, and suppose voter 1 and 2's preferences are given as follows:

    1:       {a,b,…, j}
    
    2:        a, b,  … , j







We consider generalised PSC with respect to the Hare quota; that is, q_H=n/k=2. There is a generalised solid coalition N'={1, 2} with |N'|≥ q_H supporting candidate subset C'={a}. The generalised q_H-PSC axiom requires the election of ℓ=1 candidates into W who are at least as preferred as either voter 1 or 2's most preferred candidate. Since voter 1 is indifferent between all candidates, electing any candidate such as j∈ C, will satisfy the axiom – this is despite candidate j being voter 2's strictly least preferred candidate.

















We now show that if a committee W satisfies generalised (weak) q-PSC then the committee also satisfies generalised (weak) q'-PSC for all q'>q.




Let q, q' be real numbers such that q<q'.  If a committee W satisfies generalised (weak) q-PSC then W satisfies generalised (weak) q'-PSC.



Let q<q' and suppose that the committee W satisfies generalised (weak) q-PSC. We wish to show that (weak) generalised q'-PSC is also satisfied by W.  To see this, notice that any generalised solid coalition N' requiring representation under generalised (weak) q'-PSC also requires at least as much representation under generalised (weak) q-PSC since |N'|≥ℓ q' implies that |N'|≥ℓ q.



Under linear orders, generalised PSC and generalised weak PSC coincide respectively with PSC and weak PSC. 
Generalising PSC to the case of weak preferences is important because it provides a useful link with PR properties defined on dichotomous preferences. Proportional Justified Representation (PJR) <cit.> is a proportional representation property for dichotomous preferences <cit.>.


Recall the following definition of PJR:


A committee W with |W|=k satisfies PJR for an approval ballot profile A=(A_1, …, A_n) over a candidate set C if for every positive integer ℓ≤ k there does not exists a set of voters N^*⊆ N with |N^*|≥ℓn/k such that 

    |⋂_i∈ N^* A_i|≥ℓ    but    |(⋃_i∈ N^* A_i)∩ W|<ℓ.



						


























Under dichotomous preferences, generalised weak Hare-PSC implies PJR. 



For the purpose of a contradiction, let W be a committee of size k and suppose that generalised weak Hare-PSC holds but PJR does not. If PJR does not hold, then there must exist a set N^* of voters and a positive integer ℓ such that |N^*|≥ℓn/k=ℓ q_H (where q_H is the Hare quota) and both
	
    |⋂_i∈ N^* A_i|≥ℓ    and    |(⋃_i∈ N^* A_i)∩ W|<ℓ.

	Note that if i∈ N^* it must be that i is not indifferent between all candidates (i.e. A_i≠∅, C), otherwise (<ref>) cannot hold. This means that the result is independent of whether a voter with preference _i leading to single equivalence class is defined to have preference presented via the approval ballot A_i=∅ or A_i=C (both of which induce the same single equivalence class over candidates).  
	

	
Now it follows that N^* is a generalised solid coalition for each candidate subset C'⊆⋂_i∈ N^* A_i since every candidate in C' is weakly preferred to every candidate in C for all i∈ N^*. Since |⋂_i∈ N^* A_i|≥ℓ, we can select a subset C' with exactly ℓ candidates so that |C'|=ℓ. 
	



	Thus, if generalised weak Hare-PSC holds then there exists a set C”⊆ W with size at least min{ℓ, |C'|}=ℓ such that for all c”∈ C” there exists i∈ N^*  :  c” c^(i, ℓ). But note that for any voter j∈ N^* we have c^(j, ℓ)∈ A_j and hence for this particular candidate c” and voter i∈ N^* we have c”∈ A_i. It follows that C”⊆ (⋃_i∈ N^* A_i)∩ W, and
	
    |(⋃_i∈ N^* A_i)∩ W|≥ |C”| ≥ℓ,

		which contradicts (<ref>).





















Under dichotomous preferences,  PJR implies generalised Hare-PSC. 

	
		
		Suppose that for dichotomous preferences,
			a committee W of size k satisfies PJR. 
			Then there exists no set of voters N^*⊆ N with |N^*|≥ℓn/k such that 
			
    |⋂_i∈ N^* A_i|≥ℓ    but    |(⋃_i∈ N^* A_i)∩ W|<ℓ.

	Equivalently, for every set of voters N^*⊆ N with |N^*|≥ℓn/k, the following holds:
			
    |⋂_i∈ N^* A_i|≥ℓ|(⋃_i∈ N^* A_i)∩ W|≥ℓ.

	We now prove that for all generalised solid coalitions N^* of size |N^*|≥ℓ n/k=ℓ q_H (where q_H is the Hare quota) supporting candidate subset C' then there exists a set C”⊆ W with size at least min{ℓ, |C'|} such that for all c”∈ C”
		
    ∃ i∈ N^*  :    c”_i c^(i, |C'|).


Consider a solid coalitions N^* of size |N^*|≥ℓ n/k supporting candidate subset C'.
	
		
  * Suppose there exists some voter i∈ N^* who has one of her least preferred candidates c in C'. In that case, each candidate in C' is at least as preferred for i as c. Hence the condition of genaralized Hare-PSC is trivially satisfied by any committee. 
	
  * The other case is that for each i∈ N^* and each c∈ C', c∈max__i(C).[Here max__i(C) denote the equivalence class of (strictly) most preferred candidates in C with respect to _i.] Equivalently, for each i∈ N^* and each c∈ C', c∈ A_i. Hence C'⊆⋂_i∈ N^*A_i.	Since W satisfies PJR, it follows that |(⋃_i∈ N^* A_i)∩ W|≥ℓ. In that case, we know that there exists a set C”=(⋃_i∈ N^* A_i)⊆ W of size at least min{ℓ, |C'|} such that for all c”∈ W, 
    ∃ i∈ N^*  :    c”_i c^(i, ℓ).
 Hence the condition of genaralised Hare-PSC is again satisfied. 
	
	This completes the proof. 
		
		

























Under dichotomous preferences, PJR, weak generalised Hare-PSC, and generalised Hare-PSC are equivalent.




Since it is known that testing PJR is coNP-complete <cit.>, it follows that testing generalised PSC and generalised weak PSC is coNP-complete. 


Testing generalised PSC and generalised weak PSC is coNP-complete even under dichotomous preferences.  


On the other hand, PSC and weak PSC can be tested efficiently (please see the appendix).

Figure <ref> depicts the relations between the different PR axioms.


							


 












































			
			
			
			
							
 



§ THE CASE OF STV


						
In this section, we define the family of STV rules for instances where voters submit strict preferences. The family is formalised as Algorithm <ref>. 
STV is a multi-round rule; in each round either a candidate is selected as a winner or one candidate is eliminated from the set of potential winners. Depending on the quota q and the reweighting rule applied, one can obtain particular STV rules <cit.>.  To distinguish between variants of STV, based on different quota values q, we denote the STV rule with quota q by q-STV. When the quota q is equal to the Hare or Droop quota we simply refer to the q-STV variant as Hare-STV or Droop-STV, respectively. One of the most common rules is Hare-STV with discrete reweighting. This implies that a subset of voters of size  n/k 

 is removed from the profile once their most preferred candidate in the current profile has been selected. STV modifies the preference profile ≻ by deleting candidates. We will denote by C(≻) the current set of candidates in the profile ≻. When k=1, STV is referred to as Instant-Runoff voting (IRV) or as the Alternative Vote (AV).



							
							
							
														
								
								






							 
							

								
								[Illustration of Droop-STV]
								For this example we consider the Droop-STV rule with uniform fractional reweighting. This reweighting method means that line <ref> of Algorithm <ref> is executed as follows: First calculate the total weight of voters in N', i.e.,  T=∑_i∈ N' w_i, then the weight of each voter i∈ N' is updated from w_i to w_i×T-q_D/T where q_D is the Droop quota. 
								
								To illustrate this STV rule consider the following profile with 9 voters and suppose we wish to elect a committee of size k=3 
								
					
												
    1:      c_1, c_2, c_3, e_1, e_2, e_3, e_4, d_1
    
    													2:      c_2, c_3, c_1, e_1, e_2, e_3, e_4, d_1
    
    													3:      c_3, c_1, d_1, c_2, e_1, e_2, e_3, e_4
    
    													4:      e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    													5:      e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    													6:       e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    													7:      e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    													8:       e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    													9:       e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1

					
													In the first round e_1 is selected and the total weight of the voters in set {4, 5, 6, 7, 8, 9} goes down by the Droop quota q_D, i.e., slightly more than 2.25. Candidate e_1 is then removed from the preference profile. In the second round,  e_2 is selected and the total weight of the voters in the set {4, 5, 6, 7, 8, 9} is now 6-2q_D, i.e., slightly less than 1.5. Candidate e_2 is then removed from the preference profile. After that since no candidate has plurality support, with respect to current weights, of at least the quota one candidate is deleted. Candidates e_3 and e_4 are removed in succession as they have plurality support no more than 1.5 with respect to the current voting weights. Then candidate c_1 is elected since she has plurality support of 1+6-2q_D, i.e., slightly less than 2.5, which exceeds the quota q_D.

STV has been claimed to satisfy Proportionality for Solid Coalitions/Droop Proportionality Criterion <cit.>. 

On the other hand, STV violates just about every natural monotonicity axiom that has been proposed in the literature.  

In STV, voters are viewed as having an initial weight of one. When a candidate supported by a voter is selected, the voter's weight may decrease. 
STV can use fractional reweighting or discrete reweighting.[Fractional reweighting in STV has been referred to as Gregory  or `senatorial' <cit.>]  We will show that fractional reweighting is crucial for some semblance of PR. Incidentally, fractional reweighting is not necessarily introduced to achieve better PR but primarily to minimize the “stochastic aspect” of tie-breaking in STV <cit.>. The following result shows that if STV resorts to discrete reweighting then it does not even satisfy weak PSC. Discrete reweighting refers to the modification of voter weights in Line 9 of Algorithm <ref> such that the total weight of voters in N' decreases by some integer greater or equal to q. 

			













Under strict preferences and for any q, q'∈ (n/k+1, n/k], q-STV with discrete reweighting does not satisfy weak q'-PSC. 

	
	
	
		Let N={1,2, …, 10}, C={c_1, …, c_8}, k=7 and consider the following profile:
		
    1:      c_1, c_5, c_6, c_7, c_8, c_2, c_3, c_4
    
    			2:      c_2, c_5, c_6, c_7, c_8, c_1, c_3, c_4
    
    			3:      c_3, c_5, c_6, c_7, c_8, c_1, c_2, c_4
    
    			4:      c_4, c_5, c_6, c_7, c_8, c_1, c_2, c_3
    
    			5:      c_5, c_6, c_7, c_8, c_1, c_2, c_3, c_4
    
    			6:      c_5, c_6, c_7, c_8, c_1, c_2, c_3, c_4
    
    			7:      c_5, c_6, c_7, c_8, c_1, c_2, c_3, c_4
    
    			8:      c_5, c_6, c_7, c_8, c_1, c_2, c_3, c_4
    
    			9:      c_5, c_6, c_7, c_8, c_1, c_2, c_3, c_4
    
    			10:      c_5, c_6, c_7, c_8, c_1, c_2, c_3, c_4

			
For fixed q∈  (n/k+1, n/k] we use q-STV with discrete reweighting to select the candidates. Under discrete reweighting, the total weights of voters are modified by some integer p≥ 2 (refer to Line 9 of Algorithm <ref>). In this proof we focus on the case where p=2, a similar argument can be applied to prove the proposition for larger integer values.  Note that 2=q for any q∈  (n/k+1, n/k].
			
			 Applying the q-STV rule, first c_5, c_6 and c_7 are selected. Each time we select these candidates, the total weight of voters in the set N'={5, 6, 7, 8, 9, 10} goes down by 2. Thus the remaining four candidates are to be selected from c_1, c_2, c_3, c_4 and c_8. At this stage candidate c_8 has the lowest plurality support (equal to zero) and is removed from all preference profiles and the list of potentially elected candidates, and hence c_8∉ W.
			
			Now for any fixed q'∈(n/k+1, n/k], weak q'-PSC requires that at least four candidates from {c_5,c_6, c_7,c_8} be selected, since |N'|≥ 4× q', but using discrete reweighting only three candidates are selected by q-STV. 
				
				
				The proof above has a similar argument as Example 1 in <cit.> that concerns an approval voting setting.
			
			
			
				
		
		
		
		

























				
			
		
			

























				
									
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					
					

					
					






















				

			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			

			

				


				
				













 




		Next we show that STV satisfies PSC with fractional reweighting. The proof details are in the appendix. 
		
		

























		
	
	
	For any q∈ (n/k+1, n/k], under strict preferences q-STV satisfies q-PSC.	
	
				















































	
	
	
	

	




	
	
	

		
		
		Below we provide an example of STV violating CM for k=1.  The example assumes the Droop quota, i.e., Droop-STV, however, the same example violates CM for any q-STV rule with q∈ (n/k+1, n/k].
		
		[Example showing that STV violates CM for k=1.]
									Consider the following instance of 100 voters with strict preferences.
					
    Total number of voters      Corresponding preferences
    
    					 28 :      c,b,a
    
    					5:      c,a,b
    
    					30 :       a,b,c
    
    					5:       a, c,b
    
    					16:       b,c,a
    
    					16:      b,a,c.

					 We consider the single-winner election setting with the Droop quota; that is, k=1 and q_D=50+ε for sufficiently small ε>0.
 
					 Under the Droop-STV rule the outcome is W_STV={a}. To see this notice that the plurality support of the candidates a,b,c are 35,32,33, respectively. Since no candidate receives plurality support ≥ q_D we remove the candidate with lowest plurality support, i.e, candidate b, and the 32 voters previously supporting candidate b now give their plurality support to their second preference. Thus, the updated plurality support of the two remaining candidates a and c are 35+16=51 and 33+16=49, and hence candidate a is elected.
					 
					
 
					 Now to show a violation of CM we consider an instance where two voters originally with preferences c,a,b change their preferences to a,c,b  i.e. a reinforcement of the previously winning candidate a. The new profile is shown below
					 
    Total number of voters      Corresponding preferences
    
    					28 :      c,b,a
    
    					3:      c,a,b
    
    					30:       a,b,c
    
    					7:       a, c,b
    
    					16:       b,c,a
    
    					16:      b,a,c.

					In this modified setting, the Droop-STV outcome is W_STV'={b} which is a violation of candidate monotonicity (CM). To see this notice that plurality support of the candidates a,b,c are 37, 32, 31, respectively. Since no candidate receives plurality support ≥ q_D we remove the candidate with lowest plurality support, i.e, candidate c, and the 31 voters previously supporting candidate c now give their plurality support to their second preference. Thus, the updated plurality support of the two remaining candidates a and b are 37+3=40 and 32+28=60, and hence candidate b is elected.
					
					
									
									

				



§ EXPANDING APPROVALS RULE ()


We now present the Expanding Approvals Rule (). The rule utilises the idea of j-approval voting whereby every voter is asked to approve their j most preferred candidates, for some positive integer j. At a high level, works as follows. 


An index j is initialised to 1. The voting weight of each voter is initially 1. We use a quota q that is between n/(k+1) and n/k.
While k candidates have not been selected, we do the following. 
We perform j-approval voting with respect to the voters' current voting weights. If there exists a candidate c with approval support at least a quota q, we select such a candidate. 
If there exists no such candidate, we increment j by one and repeat until k candidates have been selected.  



							

The rule is formally specified as Algorithm <ref>. 
It is well-defined for weak preferences. 


EAR is based on a combination of several natural ideas that have been used in the design of voting rules. 



	
  * Candidates are selected in a sequential manner. 
	
  * A candidate needs to have at least the Droop quota of `support' to be selected.  
	
  * The voting weight of a voter is reduced if some of her voting weight has already been used to select some candidate. The way voting weight is reduced is fractional.
	
	
	


  * 

We use j-approval voting for varying j. When considering weak orders, we adapt j-approval voting so that in j-approval voting, a voter not only approves her j most preferred candidates but also any candidate that is at least as preferred as the j-th most preferred candidate.  One way to view j-approval for weak orders is as follows. 
(1) break all ties temporarily to get an artificial linear order. (2) Identify the j-th candidate d in the artificial linear order. (3) Approve all candidates that are at least as weakly preferred as d. 
	
	
	















For EAR, the default value of q that we propose is 

    q̅=n/k+1 + 1/m+1(n/k+1+1-n/k+1).

The reason for choosing this quota is that
		q̅ can be viewed as q̅=n/k+1+ε where ε is small enough so that
		that for any ℓ≤ k, ℓ·q̅ <ℓn/k+1+1.  In particular, this implies that if there exists a solid coalition N' of size |N'|≥ℓ q_D (where q_D is the Droop quota) then |N'|≥ℓq̅. On the other hand, ε is large enough so that the algorithm is polynomial in the input size.
	
	We also propose a default priority ordering that is with respect to rank maximality under . This way of tie breaking is one but not the only way to ensure that  satisfies RRCM. For any candidate a, its corresponding rank vector is r(a)=(r_1(a), …, r_m(a)) where r_j(a) is the number of voters who have a in her j-th most preferred equivalence class.

We compare rank vectors lexicographically. One rank vector r=(r_1,…, r_m) is better than r'=(r_1',…, r_m') if for the smallest i such that r_i≠ r_i', it must hold that r_i>r_i'. 


Finally we propose the following natural way of implementing the reweighting in Step <ref>.
If the total support for c in the j-approval election is T, then for each i∈ N who supported c, we reweigh it as follows
 
    w_i⟵ w_i×T-q/T.

This ensures that exactly q weight is reduced. 	
		

	
	

In the following example, we demonstrate how works. 





[Illustration of ]
Consider the profile with 9 voters and where k=3. Note that the default quota is q̅≈ 2.33.
				
    1:      c_1, c_2, c_3, e_1, e_2, e_3, e_4, d_1
    
    					2:      c_2, c_3, c_1, e_1, e_2, e_3, e_4, d_1
    
    					3:      c_3, c_1, d_1, c_2, e_1, e_2, e_3, e_4
    
    					4:      e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    					5:      e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    					6:       e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    					7:      e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    					8:       e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    					9:       e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1

					
					In the first round e_1 is selected and the total weight of the voters in set {4, 5, 6, 7, 8, 9} goes down by q̅, i.e., 6-q̅≈ 3.67. In the second round, since no other candidate has sufficient weight when we run the 1-approval election, we consider 2-approval election. Under 2-approval, candidate e_2 receives support 6-q̅≈ 3.67 which exceeds q̅ and hence is elected.  When e_2 is selected, the total weight of the voters in set {4, 5, 6, 7, 8, 9}  goes down again by q̅. At this point the total weight of voters in set {4, 5, 6, 7, 8, 9} is 6-2q̅≈ 1.34 and no unselected candidate has approval support more than q̅, under 2-approval. So considers 3-approval whereby, candidates c_1 and c_3 both get support 3. Hence selects c_1, due to the default priority ordering L (rank maximality ordering), and the winning committee is {e_1,e_2, c_1}.
					
					

		The example above produced an outcome which coincided with the Droop-STV outcome (recall Example <ref>). Next, we present an example showing that STV and EAR are different even for k=1. 
		
		
		
					
									[Example showing that STV and EAR are different even for k=1.]
					Recall Example <ref> which showed that the following instance of 100 voters with strict preferences
					
    Total number of voters      Corresponding preferences
    
    28 :      c,b,a
    
    					3:      c,a,b
    
    					30:       a,b,c
    
    					7:       a, c,b
    
    					16:       b,c,a
    
    					16:      b,a,c,

					 leads to the single-winner Droop-STV outcome W={b}.  More generally for any quota q∈ (n/k+1, n/k] the q-STV outcome is also {b}. We now show that in this case the outcome is W'={a} and hence the STV outcome and outcomes do not coincide even for k=1.
					 
					 To see that the outcome is W'={a} we proceed as follows: First, we consider the 1-approval election which gives candidates a,b,c approval support 37,32,31, respectively. Since no candidate attains approval support beyond the default quota q̅=501/3 we move to the 2-approval election. In the 2-approval election candidates a,b,c attain approval support 56,90,54, respectively. Since all candidates attain approval support beyond q̅ we apply our default priority ordering L (rank-maximality) which leads to candidate a being elected. 
					 
					 
					

 

 











									
					
					
					
					
						In case voters do not specify certain candidates in their list and do not wish that their vote weight to be used to approve such candidates, EAR can be suitably tweaked so as to allow this requirement. In this case, candidates are selected as long as a selected candidate can get approval weight q. The required number of remaining candidates can be selected according to some criterion. 
Another way EAR can be varied is that instead of using L as the priority ordering, the candidate with the highest weighted support that is at least q is selected.
						
					
					




























							












We point out the rule's outcome can be computed efficiently. 


		
		
			runs in polynomial time O(n+m)^2.
			
			

			
			
			
			The rank maximal vectors can be computed in O(n+m) and the ordering based on rank maximality can be computed in time O(n+m)^2. In each round, the smallest j is found for which there are some candidates in C∖ W that have an approval score of at least q. The candidate c which is rank-maximal is identified. All voters who approved of c have their weight modified accordingly which takes linear time. Hence the whole algorithm takes time at most O(n+m)^2.
				
				
				
	A possible criticism of is that the choice of quota as well as reweighting makes it complicated enough to not be usable by hand or to be easily understood by the general public. However we have shown that without resorting to fractional reweighting, STV already fails weak PSC. 
				
				
				Since is designed for proportional representation which is only meaningful for large enough k, may not be the ideal rule for k=1. Having said that, we mention the following connection with a single-winner rule from the literature. 
				

				
				
					For k=1 and under linear orders with every candidate in the list, is equivalent to the Bucklin voting rule <cit.>. For k=1 and under linear orders for all but a subset of equally least preferred candidates applying the tweak in Remark <ref> leads to the being equivalent to the Fallback voting rule <cit.>. 
					
					


						
	










Under dichotomous preferences and using Hare quota, bears similarity to Phragmén's first method (also called Enström's method) described by <cit.> (page 59).

However the latter method when extended to strict preferences does not satisfy Hare-PSC. Although has connections with previous rules, extending them to the case of multiple-winners and to handle dichotomous, strict and weak preferences simultaneously and satisfy desirable PR properties requires careful thought. 




				












We observe some simple properties of the rule. It is anonymous (the names of the voters do not matter). It is also neutral as long as lexicographic tie-breaking is not required to be used. 
Under linear orders and when using with the default quota, if more than half the voters most prefer a candidate, then that candidate is selected. This is known as the majority principle.


 is defined with default quota q. However it is possible to consider variants of with other quota values such as the Hare quota. We refer to the variant of with the Hare quota as Hare-. The proposition below shows that the choice of this quota can lead to different outcomes. In particular, we show that (defined with the default quota) can lead to a different outcome than that attained under Hare-.



		
		Under dichotomous preferences, Hare-EAR and EAR are not equivalent. 
						 

		
		Let |N|=100 and k=5. Denote the Hare quota by q_H=20 and note that the default quota is q̅≈ 16.71. Let the preferences of the voters be (i.e. expressing the top equivalence class of most preferred candidates):
		
    Total number of voters      Corresponding preferences
    
    		17:        {a}
    
    		  17:        {b,f}
    
    		 17:        {c}
    
    		 17:        {d}
    
    		 17:        {e}
    
    		  1:       {f}
    
    		  14:        {g}.

		

		First note that the rank-maximal ordering, L (with the lexicographic ordering applied for equal rank maximal ordering) is 
		
    f▹ a▹ b▹ c▹ d▹ e▹ g.

		This ordering is independent of voter weights, is calculated at the start of the algorithm, and is never updated throughout the algorithm. 

		Now under Hare-EAR, in the 1-approval election no candidate has support exceeding q_H. Thus, we move to a 2-approval election whereby all voters support all candidates and all candidates have support 100. Thus, we select the candidate with highest rank-maximal priority which is candidate f and reweight its supporters (i.e. reduce all voter weights to 8/10 since all voters support all candidates). Repeating this process leads to the election of the first five candidates according to the priority ranking L i.e.
		
    W={f,a,b,c,d}.
 

		Now under EAR, in the 1-approval election there are 6 candidates {a,b,c,d,e, f} with support q̅. Thus, we select the candidate with highest L priority, i.e., candidate f, and then reweight each of its 18 supporters' weights to 18-q̅/18≈ 0.07. Now there still remains 4 candidates {a,c,d,e} with support of 17>q̅, since all voters supporting such a candidate are disjoint we have that the winning committee is 
		
    W'={f,a,c,d,e}.


		Note that W≠ W'.
		














		
		
		
		
		
						
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
		

		



§ PROPORTIONAL REPRESENTATION AND CANDIDATE MONOTONICITY UNDER 





 §.§ Proportional Representation  under 


We show that satisfies the central PR axioms for general weak order preference profiles. 

 
































			
			
				













				
							
								Under weak orders, satisfies generalised Droop-PSC.
								
								
							
								
		
		Let W be an outcome of the and suppose for the purpose of a contradiction that generalised Droop-PSC is not satisfied. That is, there exists a positive integer ℓ and a generalised solid coalition N' such that |N'|≥ℓ q_D (where q_D is the Droop quota) supporting a candidate subset C' and for every set C”⊆ W with |C”|≥min{ℓ, |C'|} there exists c”∈ C” such that 
		
    ∀ i∈ N'       c^(i, |C'|)_i c”.

		Without loss of generality we may assume that the solid coalition N' is chosen such that ℓ≤ |C'| and so min{ℓ, |C'|}=ℓ.

		Let j^* be the smallest integer such that in the j^*-approval election each voter in N' supports all candidates in C'. We claim that the j^*-approval election must be reached. Suppose not, then it must be that |W|=k at some earlier j-approval election where j<j^*. But if |W|=k this implies that after reweighting
			
    ∑_i∈ N w_i   = n-kq̅=n/k+1-kε̅,

			where ε̅=1/m+1(n/k+1+1-n/k_1). However, in every j'-approval election for j'≤ j each voter i∈ N' only supports candidates weakly preferred to c^(i, |C'|). Let Ĉ_i  be the set of candidates which voter i finds weakly preferable to c^(i, |C'|) and define Ĉ=∪_i∈ N'Ĉ_i. The total weight of voters in N' at the termination of the algorithm (i.e. at the end of the j-approval election) is reduced by at most |C”| q̅ where C”=W∩Ĉ. But by assumption since C”⊆ W and every candidate c”∈ C” is weakly preferred to c^(i, |C'|) for some voter i∈ N' it must be that |C”|<min{ℓ, |C'|}=ℓ. It follows that
			
    ∑_i∈ N' w_i≥ℓ q_D-(ℓ-1)q̅= n/k+1-(ℓ-1)ε̅,

			which contradicts (<ref>) since N'⊆ N. Thus, we conclude that the j^*-approval election is indeed reached.	
		

		Now at the j^*-approval election each voter i∈ N' supports only the candidates in the set Ĉ_i, excluding those already elected in an earlier approval election. Recall that Ĉ=∪_i∈ N'Ĉ_i and let m^* be the number of candidates elected from Ĉ in earlier approval elections. Since |N'|≥ℓ q_D implies that |N'|≥ℓq̅, it follows that the total weight of voters in N' when the j^*-approval election is reached is at least (ℓ-m^*)q̅. Since C'⊆Ĉ_i for all i∈ N', every unelected candidate in C' attains support at least (ℓ-m^*)q̅, note that there are at least |C'|-m^*≥ℓ-m^* of these. In addition, each voter i∈ N' also supports the unelected candidates in Ĉ_i\ C'. Thus, the algorithm can only terminate if weight of voters in N' is reduced below q̅ which can only occur if at least (ℓ-m^*) candidates from Ĉ are elected. It then follows that 
		
    |W∩Ĉ|=m^*+(ℓ-m^*)=ℓ.

	By again defining C”=W∩Ĉ we attain a contradiction since C”⊆ W and |C”|≥ℓ but (<ref>) does not hold since C”⊆Ĉ.






			

		
							
		
		
			Note that satisfying PSC or generalised PSC does not depend on  what priority tie-breaking is used (Step <ref>) or how the fractional reweighting is applied (Step <ref>). 
			
											










	
		
										Recalling Lemma <ref> we have the following corollary.
	
									
										Under weak orders, satisfies generalised Hare-PSC.
										
									
														
							
							
							
					
								
								Under linear orders, satisfies the majority principle. 
								
								
								
					
					
								
			
			
								
									Under linear orders, Droop-PSC implies the majority principle. 
									
					
					
										
										
					
			
			We get the following corollary from Corollary <ref>.
			
			
			Under dichotomous preferences, satisfies proportional justified representation.  
				
				
					We had observed that under dichotomous preferences, generalised Hare-PSC implies PJR. 
					
			
				Incidentally, the fact that there exists a polynomial-time algorithm to satisfy PJR for dichotomous preferences was the central result of two recent papers <cit.>. We have shown that EAR can in fact satisfy a property stronger than PJR that is defined with respect to the Droop quota.
					Since satisfies generalised PSC, it implies that there exists a polynomial-time algorithm to compute a committee satisfying generalised PSC. Interestingly, we already observed that checking whether a given committee satisfies generalised PSC is coNP-complete. 	
				
		 
		 
			
				
				
				
						
						
						
						
						








 §.§ Candidate Monotonicity under 














We show that  satisfies rank respecting candidate monotonicity (RRCM). In what follows we shall refer to the profile of all voter preferences (weak or strict) as simply the profile.

							
								satisfies rank respecting candidate monotonicity (RRCM).
			
			


			
			
				Consider a profile  with election outcome W and let c_i∈ W. Now consider another modified profile ' in which c_i's rank is improved while not harming the rank of other winning candidates, relative to , and denote the election outcome under ' by W'. Since we use rank-maximality to define the order L, note that the relative position of c_i is at least as good under ' as it is under .
				
				Let the order of candidates selected under  be c_1,…, c_i, …, c_|W|. In the modified profile ', let us trace the order of candidates selected. For the first candidate c_1, either it is selected first for exactly the same reason as it is selected first under  or, alternatively, now c_i is selected. If c_i is selected, our claim has been proved. Otherwise, the same argument is used for candidates after c_1 until c_i is selected.


	
	This leads immediately to the following corollaries of the above proposition. 			
				
				 
 				
 					satisfies  non-crossing candidate monotonicity (NCCM).
 					
				 
				
				
					For k=1, satisfies candidate monotonicity (CM). 
					
					
					
										For dichotomous preferences, satisfies candidate monotonicity.
									
									
		Consider dichotomous profile P and another profile dichotomous P' in which winning candidate c_i's rank is improved while not harming the rank of other winning candidates. This implies that the rank of c_i is improved while not affecting the ranks of any other alternatives including the winning candidates. Since satisfies rank respecting candidate monotonicity (RRCM), it follows that for dichotomous preferences, satisfies candidate monotonicity. 					
										
									













				
				

			
	On the other hand, does not satisfy CM or WCM for k>1.	
						
	
	does not satisfy WCM. 



































	
	Let N={1, 2, 3, 4}, C={a,b, c,d,e, f}, k=2, and let strict preferences be given by the following preference profile:

    1:      a, c, f, d,…
    
    2:      d, b, f, a, c, …
    
    3:      a, d, c, b, f, …
    
    4:      f, e, c, d, …,

	With this preference profile will output the winning committee 
	W={a, f}. First, a is selected into W and each weight of each voter i∈{1,3} is reduced to w_i=2-q̅/2 where q̅ is the default quota. Since q̅>4/3 we infer that w_i<1/3.  Moving to the 2-approval election no candidate receives support of at least q̅. Finally in the 3-approval election candidate f receives support at least 2 which exceeds the quota, and candidate c attains support 1+2w_i. If 1+2w_i<q̅ then candidate f is the only candidate exceeding the quota and so is elected. On the other hand, if 1+2w_i≥q̅ then both candidates c and f exceed the quota; however, due to the default (rank maximal) priority ordering f is still elected into W.	
	
	
	Now consider a reinforcement of f by voter 1 (shift f from third to first place), this is described by the following preference profile:

    1:      f, a, c, d, …
    
    2:      d, b, f, a, c,…
    
    3:       a, d, c, b, f,…
    
    4:      c, e, f, d,…,

	With these preferences the winning committee is W'={d, c}. In the 2-approval election both candidates a and d attain support of at least q̅, however due to the priority ordering L (rank maximality) candidate d is selected into W and each voter i∈{2,3} has their weight reduced to w_i=2-q̅/2<1/3. In the 3-approval election both candidates c and f attain support of at least 2≥q̅. Furthermore, c and f are equally ranked with respect to rank maximality but applying lexicographic tie-breaking leads to c being elected into W'.





	The above proposition was proven for the default quota q̅ however the same counter-example can be used to prove the statement for any other quota q∈ (n/k+1, n/k].
	



	
	

	
	
	
	
	
	
	
	
	
	
	
	
	

	
	

	








	

















 


	























	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
				
				
				
				
			
			
				





					
			
			
			
			

§ OTHER RULES
	
			
			
			
			In the literature, several rules have been defined for PR purposes. We explain how is better in its role at achieving a strong degree of PR or has other relative merits.
			
			

 §.§ Quota Borda System (QBS)

			
			
			<cit.> proposed a counterpart to STV called QPS (Quota Preference Score)  or a more specific version QBS (Quota Borda System). The rule works for complete linear orders and is designed to obtain a committee that satisfies Droop-PSC. It does so by examining the prefixes (of increasing sizes) of the preference lists of voters and checking whether there exists a corresponding solid coalition for a set of voters. If there is such a solid set of voters, then the appropriate number of candidates with the highest Borda count are selected.[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 “a highly complex arrangement” <cit.>. ]
We can partition the PSC demands among demands pertaining to rank from j=1 to m. For any given j, we only consider candidates in C^(j)
the set of candidate involved in preferences of voters up till their first j positions. In Algorithm <ref>, we present a formal description of QBS. 


							

			
Although Dummett did not show that the rule satisfies some axiom which STV does not, he argued that QPS satisfies the Droop proportionality criterion and is somewhat less “chaotic” than STV. <cit.> argues that QBS is chaotic as well and his Example 3 implicitly shows that QBS in fact violates WCM.[<cit.> wrongly claims that QBS satisfies the stronger axiom of CM.] 
Tideman also feels that QBS is overly designed to satisfy Droop-PSC but is not robust enough to go beyond this criterion especially if voters in a solid coalition perturb their preferences. 
			
			
			
has some important advantages over QBS: (1) it can easily handle indifferences whereas QBS is not well-defined for indifferences. In particular, in order for QBS to be suitably generalised for indifferences and to still satisfy generalised PSC, it may become an exponential-time rule[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.], (2)  can easily handle voters expressing partial lists by implicitly having a last indifference class whereas QBS cannot achieve this, (3) rule satisfies an established PR property called PJR for the case for dichotomous preferences. As said earlier, QBS is not well-defined for indifferences and even for dichotomous preferences, (4) addresses a criticism of <cit.>: “Suppose there are voters who would be members of a solid coalition except that they included an “extraneous” candidate, which is quickly eliminated  among their top choices. These voters' nearly solid support for the coalition counts for nothing which seems to me inappropriate.” We demonstrate the last flaw of QBS pointed out by Tideman in the explicit example below. does not have this flaw.



	

Consider the profile with 9 voters and where k=3.
				
    1:      c_1, c_2, c_3, e_1, e_2, e_3, e_4, d_1
    
    					2:      c_2, c_3, c_1, e_1, e_2, e_3, e_4, d_1
    
    					3:      c_3, c_1, d_1, c_2, e_1, e_2, e_3, e_4
    
    					4:      e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    					5:      e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    					6:       e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    					7:      e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    					8:       e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1
    
    					9:       e_1, e_2, e_3, e_4, c_1, c_2, c_3, d_1

					In the  example, {e_1, e_2, e_3} is the outcome of QBS. Although PSC is not violated for voters in {1,2,3} but the outcome appears to be unfair to them because they almost have a solid coalition. Since they form one-third of the electorate they may feel that they deserve that at least one candidate such as c_1, c_2 or c_3 should be selected.  In contrast, it was shown in Example <ref> that does not have this flaw and instead produces the outcome {e_1, e_2, c_1}.
					





































 §.§ Chamberlin-Courant and Monroe




			There are other rules that have been proposed within the class of “fully proportional representation” rules such as Monroe <cit.> and Chamberlin-Courant (CC) <cit.>. 
<cit.> used the term “fully proportional representation” to refer to PR-oriented rules that take into account the full preference list. 
			Recently, variants of the rules called Greedy Monroe, and Greedy CC <cit.> have been discussed. However none of the rules satisfy even weak PSC <cit.>. 
			
			A reason for this is that voters are assumed to not care about how many of their highly preferred candidates are in the committee as long the most preferred is present. Monroe and CC are also NP-hard to compute <cit.>. 
			
			
			
	

 §.§ Phragmén's First Method


	Phragmén's first method was first considered by Phragmén but not published or pursued by him <cit.>. In the method, voters approve of most preferred candidates that have not yet been selected. The candidate with highest weight of approval is selected. The total weight of the voters whose approved candidate was selected is reduced by the Hare quota if the total weight is more than the Hare quota. Otherwise all such voters' weights are set to zero. 
	
	Although Phragmén's first method seems to have been defined primarily for dichotomous preferences, the same definition of the rule works for linear orders. However the rule when applied to linear orders does not satisfy Hare-PSC. See the example below. 
									
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
								
									
	

									Consider the profile with 9 voters and where k=3.
													
    1:      c_1, c_2, c_3, …
    
    														2:      c_2, c_3, c_1, …
    
    														3:      c_3, c_1, c_3,…
    
    														4:      e_1, c_1, c_2, c_3, …
    
    														5:      e_2, c_1, c_2, c_3,…
    
    														6:      e_3, c_1, c_2, c_3,…
    
    														7:      e_4, c_1, c_2, c_3,…
    
    														8:       e_5, c_1, c_2, c_3,…
    
    														9:       e_6, c_1, c_2, c_3,…

					
														In the  example, {e_1, e_2, e_3} is a possible outcome of rule. When e_1 is selected, voter 4's weight goes to zero. Then when e_2 is selected, voter 5's weight goes to zero. Finally e_3 is selected. Hare-PSC requires that c_1 or c_2, or c_3 is selected. 
														
								
								
	
	
	The next example shows that Hare-EAR and Phragmén's first rule are not equivalent. 
								
								Consider the profile with 4 voters, where k=2 and with dichotomous preferences given as follows:
									
    1:     {b}
    
    														2:     {a, c}
    
    														3,4:     {a}.

		Note that in this example the Hare quota is q_H=2. Now under Hare-the winning committee is W={a,c }. First a is elected since her approval support is 3≥ q_H and all other candidates have support less than the quota. Once candidate a is elected all of her supporting voters have their weights reduced to w_i=1/3. Now there is no candidate with support beyond the quota, q_H, and so we move to a 2-approval election. In this case the support of candidate b is 2-1/3<q_H and the support of candidate c is 2≥ q_H, and so c is elected into W.  
		
		 Under Phragmén's first rule we attain W'={a,b}. First candidate a is elected since she has maximal support, then all supporting voters have their weight reduced to 1/3. Then the weighted supported of candidate b is 1 and the weight support of candidate c is 1/3 – hence Phragmén's first rule elects b into the committee.  
		 
		 
		 Thus, Hare-and Phragmén's rule are not equivalent under dichotomous preferences. 

								

				 


































		
		
		
		
		
					







 §.§ Phragmén's  Methods


			A compelling rule is  Phragmén's Ordered Method that can even be generalised for weak orders. Under strict preferences, it satisfies weak Droop-PSC  <cit.>. On the other hand, even under strict preferences, it does not satisfy Droop-PSC <cit.>. If we are willing to forego PSC, then Phragmén's Ordered Method seems to be an exceptionally  useful rule for strict preferences because unlike STV it satisfies both candidate monotonicity and committee monotonicity <cit.>. Committee monotonicity requires that for any outcome W of size k, there is a possible outcome W' of size k+1 such that W'⊃ W.
	
	

	
			
			


 §.§ Thiele's Ordered Methods


			Thiele's methods are based on identifying candidates that are most preferred by the largest weight of voters. For any voter who has had j candidates selected has current weight 1/(j+1). 
<cit.> presented an example (Example 13.15) that can be used to show that Thiele's ordered methods do not satisfy weak Droop-PSC under strict preferences. 			
			
			

			
			
			

 §.§ CPO-STV rules

			
			A class of STV related rules is CPO-STV that was proposed by <cit.>. The rules try to achieve a PR-type objective while ensuring that for k=1, a Condorcet winner is returned if there exists a Condorcet winner.[Since these rules are Condorcet-consistent, they are vulnerable to the no-show paradox <cit.>.]
One particular rule within this class is Schulze-STV <cit.>. All of these rules are only defined for linear orders and hence do not satisfy generalised PSC. Furthermore, they all require enumeration of all possible committees and then finding pairwise comparisons between them. Hence they are exponential-time rules and impractical for large elections. <cit.> writes that CPO-STV is “computationally tedious, and for an election with several winners and many candidates it may not be feasible.”
<cit.> also considered whether CPO-STV rules satisfy Droop-PSC but was unable to prove that they satisfy PSC (page 282). In any case, having an exponential-time rule satisfying PSC may not be compelling because there exists a trivial exponential-time algorithm that satisfies PSC: enumerate committees, check whether they satisfy PSC, and then return one of them. 			
			
			

 
			





















						

				
				

§ CONCLUSIONS


				
				
				
				
				


				
				
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
				
				
				





























				
				
				In this paper, we undertook a formal study of proportional representation under weak preferences. The generalised PSC axiom we proposed generalises several well-studied PR axioms in the literature. We then devised a rule that satisfies the axiom. 

Since EAR has relative merits over STV and Dummett's QBS (two known rules that satisfy PSC), it appears to be a compelling solution for achieving PR via voting. At the very least, it appears to be another useful option in the toolbox of representative voting rules and deserves further consideration and study. The relative merits of STV, QBS, and are summarised in Table <ref>. 




	EAR can be modified to also work for `participatory budgeting' settings in which candidates may have a non-unit `cost' and the goal is to select a maximal set of candidates such that the total cost of candidates does not exceed a certain budget B. In our original setting of committee voting, EAR with q=n/k can be seen as follows. 
We initialise the weight of each voter as 1. Each candidate is viewed as having a unit cost and the budget is k. A candidate c is selected if including c does not exceed the budget (k) and if c has approval support of 1n/k. When c is selected, the total weight of the voters supporting c is decreased by n/k times the unit cost. If no such candidate exists, we increment j-approval to j+1-approval. The process continues until no candidate can be included without exceeding the budget limit.
We now explain how to modify EAR to work for non-unit costs and budgets.
We again initialise the budget weight of each voter as 1. 
A candidate c is selected if including c does not exceed the budget B and 
if c has approval support of n/B times the cost of c. When c is selected, the total weight of the voters supporting c is decreased by n/B times the cost of c. If no such candidate exists, we increment j-approval to j+1-approval. The process continues until no candidate can be included without exceeding the budget limit. Proportional representation axioms related to those studied in this paper have only recently been extended and explored in the participatory budgeting setting by <cit.>.



Our work also sheds light on the complexity of computing committees that satisfy PR axioms as well the the complexity of testing whether a given a committee satisfies a given PR axiom. We found that whereas a polynomial-time algorithm such as finds a committee that satisfies generalised PSC, testing whether a given committee satisfies properties such as generalised PSC or generalised weak PSC is computationally hard. These findings are summarised in Table <ref>.
				
				
				
				
				
				

				
				 
				

				
				
				
				
				
				
				
			
			
			




				
				
				
				
				







				







  
				
			
			
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
						
						
						
























































































































































				

§ ACKNOWLEDGMENTS

				Haris Aziz is supported by a Julius Career Award.
				Barton Lee is supported by a Scientia PhD fellowship. The authors thank Markus Brill, Edith Elkind, Dominik Peters and Bill Zwicker for comments. 

plainnat
 


  
  
  38
  
  
  urlstyle

  [Aiyar(1930)]Aiya30a
  K. V. K. Aiyar.
  Proportional Representation by The Single Transferable Vote:
    The System and its Methods.
  The Madras Law Journal Press, 1930.

  [Aleskerov and Karpov(2013)]AlKa13a
  F. Aleskerov and A. Karpov.
  A new single transferable vote method and its axiomatic
    justification.
  Social Choice and Welfare, 400 (13):0
    771–786, 2013.

  [Aziz and Huang(2016)]AzHu16a
  H. Aziz and S. Huang.
  Computational complexity of testing proportional justified
    representation.
  Technical Report arXiv:1612.06476, arXiv.org, 2016.

  [Aziz et al.(2017)Aziz, Brill, Conitzer, Elkind, Freeman, and
    Walsh]ABC+16a
  H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh.
  Justified representation in approval-based committee voting.
  Social Choice and Welfare, pages 461–485, 2017.

  [Aziz et al.(2018a)Aziz, Elkind, Huang, Lackner,
    Sánchez-Fernández, and Skowron]AEH+18
  H. Aziz, E. Elkind, S. Huang, M. Lackner, L. Sánchez-Fernández, and
    P. Skowron.
  On the complexity of Extended and Proportional Justified
    Representation.
  In Proceedings of the 32nd AAAI Conference on Artificial
    Intelligence (AAAI). AAAI Press, 2018a.

  [Aziz et al.(2018b)Aziz, Lee, and Talmon]ALT18
  H. Aziz, B. E. Lee, and N. Talmon.
  Proportionally representative participatory budgeting: Axioms and
    algorithms.
  In Proceedings of the 17th International Joint Conference on
    Autonomous Agents and Multi-Agent Systems (AAMAS), 2018b.

  [Black(1958)]Blac58a
  D. Black.
  The Theory of Committees and Elections.
  Cambridge University Press, 1958.

  [Bowler and Grofman(2000)]BoGr00a
  S. Bowler and B. Grofman.
  Introduction: STV as an Embedded Institution.
  In Elections in Australia, Ireland, and Malta under the Single
    Transferable Vote: Reflections on an Embedded Institution, pages 1–14,
    2000.

  [Brams and Sanver(2009)]BrSa09a
  S. Brams and R. Sanver.
  Voting systems that combine approval and preference.
  In The Mathematics of Preference, Choice and Order, pages
    215–237. Springer, 2009.

  [Brill et al.(2017)Brill, Freeman, Janson, and Lackner]BFJL16a
  M. Brill, R. Freeman, S. Janson, and M. Lackner.
  Phragmén's voting methods and justified representation.
  In Proceedings of the 31st AAAI Conference on Artificial
    Intelligence (AAAI), pages 406–413. AAAI Press, 2017.

  [Chamberlin and Courant(1983)]ChCo83a
  J. R. Chamberlin and P. N. Courant.
  Representative deliberations and representative decisions:
    Proportional representation and the Borda rule.
  The American Political Science Review, 770
    (3):0 718–733, 1983.

  [Conitzer et al.(2009)Conitzer, Rognlie, and Xia]CRX09a
  V. Conitzer, M. Rognlie, and L. Xia.
  Preference functions that score rankings and maximum likelihood
    estimation.
  In Proceedings of the 21st International Joint Conference on
    Artificial Intelligence (IJCAI), pages 109–115. AAAI Press, 2009.

  [Doron and Kronick(1977)]DoKr77a
  G. Doron and R. Kronick.
  Single transferrable vote: An example of a perverse social choice
    function.
  American Journal of Political Science, 210
    (2):0 303–311, 1977.

  [Dummett(1984)]Dumm84a
  M. Dummett.
  Voting Procedures.
  Oxford University Press, 1984.

  [Dummett(1997)]Dumm97a
  M. Dummett.
  Principles of Electoral Reform.
  Oxford University Press, 1997.

  [Elkind et al.(2014)Elkind, P., Faliszewski, Skowron, and
    Slinko]EFSS14a
  E. Elkind, P., Faliszewski, P. Skowron, and A. Slinko.
  Properties of multiwinner voting rules.
  In Proceedings of the 13th International Joint Conference on
    Autonomous Agents and Multi-Agent Systems (AAMAS), pages 53–60, 2014.

  [Elkind et al.(2017)Elkind, Faliszewski, Skowron, and Slinko]EFSS17a
  E. Elkind, P. Faliszewski, P. Skowron, and A. Slinko.
  Properties of multiwinner voting rules.
  Social Choice and Welfare, 2017.

  [Faliszewski et al.(2017)Faliszewski, Skowron, Slinko, and
    Talmon]FSST17a
  P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon.
  Multiwinner voting: A new challenge for social choice theory.
  In U. Endriss, editor, Trends in Computational Social Choice,
    chapter 2. 2017.

  [Geller(2002)]Gell02a
  C. Geller.
  Single transferable vote with borda elimination: a new vote-counting
    system.
  Technical Report 2201, Deakin University, Faculty of Business and
    Law, 2002.

  [Hill(2001)]Hill01a
  I. D. Hill.
  Difficulties with equality of preference.
  Voting Matters, 0 (13), 2001.

  [Janson(2016)]Jans16a
  S. Janson.
  Phragmén's and Thiele's election methods.
  Technical Report arXiv:1611.08826 [math.HO], arXiv.org, 2016.

  [Meek(1994)]Meek94a
  B. L. Meek.
  A new approach to the single transferable vote, paper ii.
  Voting Matters, 0 (1), 1994.

  [Monroe(1995)]Monr95a
  B. L. Monroe.
  Fully proportional representation.
  The American Political Science Review, 890
    (4):0 925–940, 1995.

  [Moulin(1988)]Moul88
  H. Moulin.
  Condorcet's principle implies the No Show Paradox.
  Journal of Economic Theory, 45:0 53–64, 1988.

  [Procaccia et al.(2008)Procaccia, Rosenschein, and Zohar]PSZ08a
  A. D. Procaccia, J. S. Rosenschein, and A. Zohar.
  On the complexity of achieving proportional representation.
  Social Choice and Welfare, 30:0 353–362, 2008.

  [Pukelsheim(2014)]Puke14a
  F. Pukelsheim.
  Proportional Representation: Apportionment Methods and Their
    Applications.
  Springer, 2014.

  [Sánchez-Fernández et al.(2016)Sánchez-Fernández,
    Fernández, and Fisteus]SFF16a
  L. Sánchez-Fernández, N. Fernández, and L. A. Fisteus.
  Fully open extensions to the D'Hondt method.
  Technical Report arXiv:1609.05370 [cs.GT], arXiv.org, 2016.

  [Sánchez-Fernández
    et al.(2017a)Sánchez-Fernández, Elkind, and
    Lackner]SEL17a
  L. Sánchez-Fernández, E. Elkind, and M. Lackner.
  Committees providing ejr can be computed efficiently.
  Technical Report arXiv:1704.00356, arXiv.org, 2017a.

  [Sánchez-Fernández
    et al.(2017b)Sánchez-Fernández, Elkind, Lackner,
    Fernández, Fisteus, Basanta Val, and Skowron]SFF+17a
  L. Sánchez-Fernández, E. Elkind, M. Lackner, N. Fernández, J. A.
    Fisteus, P. Basanta Val, and P. Skowron.
  Proportional justified representation.
  In Proceedings of the 31st AAAI Conference on Artificial
    Intelligence (AAAI). AAAI Press, 2017b.

  [Schulze(2002)]Schu02a
  M. Schulze.
  On Dummett's 'Quota Borda System'.
  Voting matters, 150 (3), 2002.

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

  [Telegraph(2011)]Tele11a
  The Telegraph.
  Professor Sir Michael Dummett, December 2011.

  [Tideman(1995)]Tide95a
  N. Tideman.
  The single transferable vote.
  Journal of Economic Perspectives, 90 (1):0
    27–38, 1995.

  [Tideman and Richardson(2000)]TiRi00a
  N. Tideman and D. Richardson.
  Better voting methods through technology: The
    refinement-manageability trade-off in the single transferable vote.
  Public Choice, 1030 (1-2):0 13–34, 2000.

  [Tideman(2006)]Tide06a
  T. N. Tideman.
  Collective Decisions And Voting: The Potential for Public
    Choice.
  Ashgate, 2006.

  [Woodall(1994)]Wood94a
  D. R. Woodall.
  Properties of preferential election rules.
  Voting Matters, 3, 1994.

  [Woodall(1997)]Wood97a
  D. R. Woodall.
  Monotonicity of single-seat preferential election rules.
  Discrete Applied Mathematics, 770 (1):0
    81–98, 1997.

  [Zwicker(2016)]Zwic15a
  W. S. Zwicker.
  Introduction to the theory of voting.
  In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia,
    editors, Handbook of Computational Social Choice, chapter 2. Cambridge
    University Press, 2016.

  
  



 




















































































§ STV


		
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	







		
	
	
	
	
	

  
Proof of Proposition <ref>
	

































						
						
						Let q∈ (n/k+1, n/k] and assume that all voters have strict preferences. Suppose for the purpose of a contradiction that W is the STV outcome for some instance and q-PSC is not satisfied. That is, there exists a positive integer ℓ and a solid coalition N'⊆ N with |N'|≥ℓ q supporting a set of candidates C' and W∩ C'|<min{ℓ^*, |C'|}. Without loss of generality we assume that |C'|≥ℓ. If this were not the case, i.e., |C'|<ℓ, one could simply consider a smaller subset of voters in N' and these voters will necessarily still solidly support all candidates in C'.
						
						Thus, given that N' solidly supports the candidate set C' with |C'|≥ℓ and |N'|≥ℓ q we wish to derive a contradiction from the fact that 
						
    j=|W∩ C'|<min{ℓ, |C'|} =ℓ.

						The STV algorithm iteratively elects or eliminates a single candidate.[Technically speaking, if the sum of elected candidates, W, and unelected but also uneliminated candidates, C^*, is equal to k the set of all unelected and also uneliminated 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 8-10 of Algorithm <ref>. Clearly this assumption is without loss of generality.] Let T be the number of the iteration which the STV algorithm runs through to output W, and let (c_1, …, c_T) be a sequence of candidates such that in iteration t∈{1, …, T} candidate c_t is either elected or eliminated. Note that T≥ k and it need not be the case that ∪_t{c_t}=C. Furthermore, since |W∩ C'|=j it must be the case that |∪_t{c_t}∩ C'|≥ j. 
						
						
						First, we claim that C'⊆∪_t {c_t}. If this were not the case, then in every iteration voters in N' support only candidates in C' and since precisely j candidates in C' were elected the remaining weight of voters in N' is >(ℓ -j)q. But this is a contradiction; the STV algorithm cannot terminate when voters in N have remaining weight >q (recall the footnote of the previous paragraph) since this would imply <k candidates have been elected. Thus, we conclude that C'⊆∪_t {c_t}. This implies that there exist a unique ordering of the candidates in C'
						
    (c_1', …, c_|C'|')

						 which maintains the ordering (c_1, …, c_T), i.e., simply define the one-to-one mapping σ: {1, …, |C'|}→{1, …, T} such that (c_1', …, c_|C'|')=(c_σ(1), …, c_σ(|C'|)). 
						 
						 Second, we claim that the j candidates (c_|C'|-(j-1)', c_|C'|-(j-2)', …, c_|C'|') are all elected. Starting with iteration t=σ(|C'|) suppose that candidate c_|C'|' is not elected. This would then imply that at the start of iteration t voters in N' have weight >(ℓ-j)q>q – having only supporting candidates in C' in earlier iterations at precisely j of these being elected. Furthermore, since  c_|C'|' is the only unelected and un-eliminated candidate in C' all voters in N' support candidate c_|C'|'. Thus, the weighted-plurality support is >q which contradicts the assumption that c_|C'|' is not elected. We conclude that in fact candidate c_|C'|' is elected and so in all earlier iterations s<t the weight of voters in >(ℓ-j+1)q and precisely (j-1) candidates from C' are elected in earlier iterations. Now consider iteration t'=σ(|C'|=1) and suppose that candidate c_|C'|-1' is not elected. But at the start of this iteration each voter in N' supports with their plurality vote either candidate c_|C'| or candidate c_|C'|-1 and in total have weight >(ℓ-j+1)q>2q. Thus, at least one of the candidate must have weighted-plurality support >q and so no candidate is eliminated in this iteration, and we conclude that it must be that candidate c_|C'|-1' is elected. This argument can be repeated for all iterations t”=σ(|C'|-2), …, σ(|C'|-(j-1)), and so we conclude that the j candidates (c_|C'|-(j-1)', c_|C'|-(j-2)', …, c_|C'|') are all elected.
						 
						 Finally, we argue that candidate c_|C'|-j is also elected which contradicts the original assumption that |W∩ C'|=j<ℓ. To see this, note that at the start of iteration t^*=σ(|C'|-j) the total weight of voters in N' is >ℓ q (applying the claim from the previous paragraph) and each voter in N' has a plurality vote for one of the (j+1) candidates in ∪_i=0^j{c_|C'|-i'}. Noting that ℓ≥ j+1, there exists at least one candidate in ∪_i=0^j{c_|C'|-i'} who receives weighted-plurality support > q and so no candidate is eliminated in this iteration. In particular, this implies that candidate c_|C'|-j is elected. Combining this with the previous claims we see that j+1 candidate are elected which contradicts the original assumption and completes the proof.
						


 

§ COMPLEXITY OF TESTING PSC

 
 
	 Under linear orders, it can be tested in polynomial time whether a committee satisfies PSC.
	 
	 
		 For each i from 1 to m one can look at prefixes of preference lists of sizes i. For these prefixes, we can see check whether there exists a corresponding solid coalition. For such solid coalitions we can check whether the appropriate number of candidates are selected or not.
		 
	 
	 
	 The same idea can be used for weak PSC. 

	 
		 Under linear orders, it can be tested in polynomial time whether a committee satisfies weak PSC.
		 
		 
		 
		 
			 Under dichotomous preference, the problem of testing generalised PSC is coNP-complete.	 
			 
			 
			 

			 
			 
				 Under dichotomous preferences, generalised PSC is equivalent to PJR. Since <cit.> and <cit.> showed that testing PJR is coNP-complete, it follows that that testing Generalised PSC is coNP-complete as well. 
				 			










				 
				 
				 










				 
	

