## 2 Multi-Winner Voting
### Fairness for Candidates with Sensitive Attributes  
In the previous two sections, we mainly survey fairness properties designed for certain groups of voters. In some real-word applications, candidates have sensitive attributes. In these applications, fairness for groups of candidates has to be imposed into the decision-making procedure to avoid discrimination. In this section, we survey the recent progress of the study on this topic. We still assume that a fixed number \(k\) of winners shall be selected. [PERSON], [PERSON], and [PERSON] [41] studied fairness in the setting where candidates are in a number of groups, each of which corresponds to a sensitive attribute such as gender, ethnicity, etc. Notably, each candidate may have several attributes and hence the groups may be non-disjoint. They studied a quite general framework which requires that a winning committee should be a one that \begin{table}
\begin{tabular}{c c c c c c} \hline  & **EJR** & **PJR** & **JR** & **PR** & **Complexity** \\ \hline AV & N [23] & N [23; 24] & N [23] & N [24; 35] & P (trivial) \\ SAV & N [23] & N [23; 24] & N [23] & N [24; 26; 35] & P [26] \\ seqPAV & N [23] & N [23; 24] & N [23] & N [24; 26; 35] & P [26] \\ MAV & N [23] & N [23; 24] & N [23] & N [23] & NP-complete [36] \\ CCAV & N [23] & N [24] & Y [23] & Y [35] & NP-complete [37] \\ MonAV & N [23] & N [24] & Y [23] & Y [24] & NP-complete [21] \\ var-Phragmen & N [38] & N [38] & Y [38] & Y [38] & NP-complete [38] \\ seq-Phragmen & N [38] & Y [38] & Y [38] & N [38] & P [38] \\ max-Phragmen & N [38] & Y [38] & Y [38] & Y [38] & NP-complete [38] \\ PAV & Y [23] & Y [24] & Y [23] & N [24] & NP-complete [26] \\ \hline \end{tabular}
\end{table} 
Table 4: A summary of proportional properties of important approval-based multi-winner voting rules and the complexity of winner determination for these rules. In the table, “N” means that the rule in the corresponding row does not satisfy the property in the corresponding column, and “Y” means that the rule satisfies the property. maximizes the score with respect to some defined scoring function, and fulfills the restriction that for each group of candidates with a specific attribute, a prescribed fraction of the group members must be selected. Formally, let \(f:2^{C}\rightarrow\mathbb{R}_{\geq 0}\) be a scoring function. Moreover, let \(C_{1},C_{2},\ldots,C_{t}\subseteq C\) be subsets of candidates (it may that \(C_{i}\cap C_{j}\
eq\emptyset\)), and for each \(C_{i}\), \(1\leq i\leq t\), let \(\ell_{i}\) and \(u_{i}\) be two integers such that \(0\leq\ell_{i}\leq u_{i}\leq|C_{i}|\). Then, the goal of an \(f\)-multi-winner voting rule is to select a \(k\)-committee \(w\subseteq C\) with the maximum score under the restriction that for each \(C_{i}\), \(1\leq i\leq t\) it holds that \(\ell_{i}\leq|w\cap C_{i}|\leq u_{i}\). The framework is so general that it only stipulates the maximum and the minimum numbers of candidates that should be selected from each group in general but leaves the settings of these two values to ad hoc applications. Particularly, \(\ell_{i}\)s and \(u_{i}\)s can be constants, or any function of the number of candidates in the groups, the total number of candidates, etc. As argued by the authors, the framework generalizes several important proportional fairness properties studied in the literature including such as fully proportional representation [42], fixed-degressive proportionality [43], flexible proportionality [44], etc. Given that the framework is so general, it is not surprising that computing a winning committee is a computationally hard problem. Given this negative result, the authors explored numerous approximation algorithms for calculating committees satisfying the above fairness constraints. Their results largely depend on the maximum number of groups each candidate is included. For example, they showed that if everyone belongs to exactly one group, i.e., \((C_{1},C_{2},\ldots,C_{t})\) form a partition of \(C\), there is a \((1-1/e)\)-approximation algorithm, and they showed that this is probability optimal.