## 2 Multi-Winner Voting
### Voter Fairness in Ranking-Based Voting
** STV rules are a large class of voting rules each of which is featured by a rational number \(q\) and some vote-reweighting approach. A common principle of these rules is to guarantee certain groups of voters are proportionally represented. Fixing a \begin{table}
\begin{tabular}{c c c} \hline \hline \multicolumn{2}{c}{**Complexity of Computing**} & **Complexity of Testing** \\ \hline \(q\)-PSC & P & P \\ weak \(q\)-PSC & P & P \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Complexity of computing a committee satisfying a proportional property, or testing whether a given committee satisfies a proportional property. In the table, “P” stands for “polynomial-time solvable”. All results are from the work by the authors of [PERSON] et al. (2017). rational quota \(q\) and a vote-reweighting approach, the STV rule selects winning committees iteratively as shown below. For a candidate \(c\), let \(V^{\mathsf{top}}(c)\) be the set of voters ranking \(c\) in the top. 1. Initially, we associate to each voter \(v\in V\) a weight denoted by \(\mathsf{weight}(v)\). (Usually, all voters have weight \(1\) initially, but this is not necessarily the case.) 2. If there is a candidate, \(c\in C\), that is ranked in the top by at least \(q\) voters, that candidate is added to the winning committee. Then, we apply the vote-reweighting approach so that the total weight of all votes ranking \(c\) in the top are reduced by \(\min\{q,p\}\), where \(p=\sum_{v\in V^{\mathsf{top}}(c)}\mathsf{weight}(v)\) is the sum of the weights of all voters ranking \(c\) in the top before the reweighting. Moreover, the candidate \(c\) is deleted from \(C\) and from all votes. 3. If there is no such a candidate \(c\) as discussed above, then a candidate that is ranked in the top by the least number of voters is eliminated. 4. The procedure terminates until \(k\) candidates are selected. Many of concrete STV rules have been considered in the literature (see the works by the authors of [18; 19] for a history and a summary of many important STV rules). However, for simplicity, in this survey, we discuss only STV rules where initially all voters have weight \(1\), and the _uniform reweighting approach_ is used in Step 2. Particularly, according to this reweighting approach, in Step 2, the weight of a voter \(v\) which ranks \(c\) in the top is reduced to \(\min\{0,\mathsf{weight}(v)\cdot(1-\frac{q}{p})\}\). Two important STV rules are those when \(q\) is equal to the Hare quota or the Droop quota, i.e., \(q=\frac{n}{k}\) and \(q=\left\lfloor\frac{n}{k+1}\right\rfloor+1\). We denote these two special STV rules as D-STV and H-STV, respectively. Much research has been done to investigate whether the above defined multi-winner voting rules provide the PSC fairness property, see Table 2 for a summary of the current known results. According to this table, by using STV rules, we are able to obtain, in polynomial time, winning committees that provide both \(q_{\text{H}}\)-PSC and \(q_{\text{D}}\)-PSC fairness simultaneously. Nevertheless, it is important to point out that STV rules fail many monotonic properties [16]. For a nice remedy, [PERSON] and [PERSON] recently proposed a new rule, which they named \"Expanding Approvals Rule\" (EAR). In particular, they showed that EAR has the following advantages compared with any other concrete rules studied in the literature to date. First, an EAR winning committee can be always computed in polynomial-time. Second, EAR committees provide both \(q_{\text{H}}\)-PSC and \(q_{\text{D}}\)-PSC fairness. Third, EAR committees satisfy many monotonic properties. Finally, EAR works not only for strict preference elections but also for the case where voters hold weak order preferences over candidates. See the work by the authors of [16] for the definition of EAR and the detailed discussions.