## 2 Multi-Winner Voting
### Voter Fairness in Approval-Based Voting
** This rule first calculates a load distribution \(\mathbf{x}\) such that \(\max_{v\in V}x_{v}\) is minimized. Then, \(f(\mathbf{x})\) is the winning committee. **var-Phragmen. ** This rule first calculates a load distribution \(\mathbf{x}\) such that \(\sum_{v\in V}x_{v}^{2}=\sum_{v\in V}(\sum_{c\in C}x_{v,c})^{2}\) is minimized. Then, \(f(\mathbf{x})\) is the winning committee. **seq-Phragmen. ** This rule takes \(k\) rounds to select the winners, one for each round. For a candidate \(c\), let \(V_{c}=\{v\in V:c\in v\}\) be the set of voters approving \(c\). Initially, let \(w=\emptyset\). Let \(x_{v}^{(j)}\) denote the voter loads after round \(j\). At first, all voters have a load of 0, i.e., \(x_{v}^{(0)}=0\) for all \(v\in V\). As a first candidate, we select one \(c\in C\) that receives the most approvals and add \(c\) into \(w\). Then, the voter load of each voter approving this selected candidate is increased to \(\frac{1}{|V_{c}|}\). In the next round, we choose a candidate that induces a (new) maximal voter load that is as small as possible, but now we have to take into account that some voters already have a non-zero load. The new maximal load if some candidate \(c\in C\) is chosen as the \((j+1)\)-st committee member is measured as  
\[s_{c}^{(j+1)}=\frac{1+\sum_{c\in v\in V}x_{v}^{(j)}}{|V_{c}|}.\]  
In other words, if \(c\) is chosen, then we adjust the voter loads of all voters approving \(c\), so that they have the same voter load afterwards. Let \(c\) be the candidate that minimizes \(s_{c}^{(j+1)}\) among those that are not yet in \(w\). Then we add \(c\) to \(w\) and set \(x_{v}^{(j+1)}:=s_{c}^{(j+1)}\) for all \(v\in V_{c}\). After \(k\) rounds, the committee \(w\) consists of exactly \(k\) candidates. Note that we also obtain a load distribution \(\mathbf{x}\) such that \(f(\mathbf{x})=w\). The above rules have been extensively studied in the literature from different aspects [26; 27; 28; 29; 30; 31; 32; 33; 34]. However, the proportionality properties defined above of these rules have only received attention recently. [PERSON] et al. [24] proved that winner determination for all multi-winner voting rules that satisfy PR must be NP-hard. This directly implies that AV, SAV, and seqPAV do not fulfill PR as winner determination for these rules are polynomial-time solvable. [PERSON] and [PERSON] [35] showed that MAV does not satisfy PR. [PERSON] et al. [23] showed that AV, SAV, MAV, and seqPAV do not satisfy JR. As PJR and EJR imply JR, it must be that AV, MAV, SAV, and seqPAV fail also PJR and EJR. So, none of AV, MAV, SAV, and seqPAV satisfy any properties studied in this section. The proportional properties of other rules have also been studied in the literature and we summarize them in Table 4.  
With the help of Table 4, we know that the answer to the following important question is in the negative:  
_Is there a natural rule (or an algorithm) whose outcome always provide JR, EJR, PJR, and PR simultaneously?_  
But do we still have some hope? The answer is unfortunately in the negative again. In fact, [PERSON] et al. [24] proved that there are no voting rules whose outcome always provides both PR and EJR. In particular, they construct an election instance where none of the PR committees provides EJR (Theorem 4 in the work by the authors of [24]). This negative result is in fact their motivation to propose the PJR property. Due to the fact that EJR implies PJR, and PJR implies JR, and the above impossibility result, our question then breaks down to the following two questions. First, is there any natural EJR rule? Second, is there any natural rule whose outcome always provide PR and PJR? The results in Table 4 provide a comprehensive answer: among the rules in the table, PAV is the only one that provides EJR, and thus provides JR and PJR too, and max-Phragmen is the only one that guarantees PJR and PR, and thus provides JR too. However, an obvious disadvantage of PAV and max-Phragmen is that computing a winning committee for them turned out to be a computationally hard problem.