## 2 Multi-Winner Voting
### Voter Fairness in Ranking-Based Voting
Analyzing whether the outcomes of these voting rules provide some specific fairness property is of also particular importance. This motivation brings the following decision problem into the line of research. \(\tau\)**-Testing**  
Input:  
Concerning the first decision problem, [PERSON] and [PERSON] [16] proved that both computing and testing \(q\)-PSC and weak \(q\)-PSC are polynomial-time solvable for all possible values of \(q\). See Table 1.  
For the second decision problem, we survey the results for many voting rules studied in the literature. Let \((C,V)\) be an election. For a vote \(\succ\in V\), the position of a candidate \(c\) in \(\succ\), denoted by \(\mathsf{pos}_{\succ}(c)\), is the number of candidates ranked before \(c\) plus one, i.e.,  
\[\mathsf{pos}_{\succ}(c)=|\{c^{\prime}\in C\setminus\{c\}:c^{\prime}\succ c\}|+1.\]  
**Committee scoring rules. ** Under a committee scoring rule, each voter provides a score to each committee based on the positions of the committee-members in the preference of this voter, and winning committees are those with the maximum total score. Committee scoring rules were first studied by [PERSON] et al. [PERSON] et al. (2017) as a general framework to encapsulate many concrete multi-winner voting rules, including, e.g., Bloc, \(k\)-Borda, Chamberlin-Courant, etc. * \(k\)**-Borda. ** Each voter gives \(m-i\) points to each candidate ranked in the \(i\)-th position, where \(m\) denotes the number of candidates. The score of a committee from a voter is the sum of the scores of all its members from the voter. * **Bloc. ** Every voter gives \(1\) point to all of their top \(k\) ranked candidates. The score of a committee from a voter is the sum of the scores of all its members from the voter. * **Single nontransferable vote (SNTV). ** Every voter gives \(1\) point to her top ranked candidate. The score of a committee from a voter is the sum of the scores of all its members from the voter. * **Chamberlin-Courant (CC). ** Different from the above three rules where all members of the winning committee are counted to accumulate the satisfaction of a voter, in CC, for each voter, only the best candidate in the winning committee contributes to the satisfaction of this voter. In other words, each voter is assumed to be only represented by her best candidate in the winning committee. Precisely, each voter has a nonincreasing mapping \(\alpha:\mathbb{N}\to\mathbb{N}\), such that \(\alpha(i)\) is a voter's satisfaction of a candidate ranked in the \(i\)-th position. For a voter \(v\) with preference \(\succ_{v}\) and a nonempty committee \(w\subseteq C\), let \(\mathsf{top}^{w}(\succ_{v})\) be the top-ranked candidate of \(v\) among \(w\), i.e., \(\mathsf{top}^{w}(\succ_{v})\) is the candidate \(c\in w\), such that \(c\succ_{v}c^{\prime}\) for all \(c^{\prime}\in w\setminus\{c\}\). The CC score of a committee \(w\subseteq C\) from a voter with mapping \(\alpha\) is then \(\alpha(\mathsf{pos}_{\succ_{v}}(\mathsf{top}^{w}(\succ_{v})))\). In this section, we consider only the [PERSON] satisfaction function \(\alpha:\mathbb{N}\to\mathbb{N}\), which, for \(m\) candidates, holds that \(\alpha(i)=m-i\). **[PERSON]'s rule. ** This rule is similar to the CC rule but with a further restriction that every candidate can represent at most \(\lceil\frac{n}{k}\rceil\) voters. Let \(g:V\to C\) be an assignment function and \(g^{-}(c)\), \(c\in C\) be the set of voters, \(\succ\in V\), such that \(g(\succ)=c\). Moreover, let \(\mathcal{G}\) be the set of all assignment functions from \(V\) to \(C\). The [PERSON] score of a \(k\)-committee \(w\subseteq C\) is then defined as  
\[\max_{ \begin{subarray}{c}g\in\mathcal{G}\ s.t.\\ |g^{-}(c)|\leq n/k\text{ for all }c\in C\end{subarray} }\left\{\sum_{\succ \in V}\alpha_{\succ}(g(v))\right\},\]  
where \(\alpha_{\succ}:\mathbb{N}\to\mathbb{N}\) is a mapping as in CC. [PERSON]'s rule selects \(k\)-committees with the maximum score as winning committees. **Single-transferable voting (STV).