## 2 Multi-Winner Voting
### Voter Fairness in Approval-Based Voting  
This section is devoted to fairness properties of approved-based multi-winner voting rules, where each vote \(v\in V\) consists of a subset of candidates, the candidates approved by the corresponding voter. Several important proportional properties have been put forward in the literature. In general, these properties aim at providing fairness for certain group of voters who approve some candidates in common. In particular, they ensure that for such a group of enough large size, at least a certain number of candidates approved by all (or some) members of this group should be selected. **Justified representation (JR). ** A \(k\)-committee, \(w\subseteq C\), provides JR, if, for every subset \(U\subseteq V\) of at least \(\frac{n}{k}\) votes such that \(\bigcap_{u\in U}u\
eq\emptyset\), at least one of the candidates approved by some vote in \(U\) is included in \(w\), i.e.,  
\[w\cap\left(\bigcup_{u\in U}u\right)\
eq\emptyset.\]  
This property was proposed by [PERSON] et al. [22; 23]. **Proportional justified representation (PJR). ** A \(k\)-committee,\(w\subseteq C\), provides PJR if for every positive integer \(\ell\leq k\), and for every subset \(U\subseteq V\) of at least \(\ell\cdot\frac{n}{k}\) votes such that \(|\bigcap_{u\in U}u|\geq\ell\), the committee \(w\) contains at least \(\ell\) candidates from \(\bigcup_{u\in U}u\), i.e., \(|w\cap\left(\bigcup_{u\in U}u\right)|\geq\ell\). This property was proposed in the work by the authors of [24]. **Extended justified representation (EJR). ** A \(k\)-committee \(w\subseteq C\) provides EJR if for every positive integer \(\ell\leq k\) and for every subset \(U\subseteq V\) of at least \(t\geq\ell\cdot\frac{n}{k}\) votes such that \(|\bigcap_{u\in U}u|\geq\ell\), the committee \(w\) contains at least \(\ell\) candidates from every vote \(u\in U\), i.e., \(|w\cap u|\geq\ell\) for all \(u\in U\). This property was proposed by [PERSON] et al. [23]. **Perfect representation (PR). ** PR is defined for special elections. Particularly, let \((C,V)\) be an election such that \(|V|=t\cdot k\) for some integer \(t\). A \(k\)-committee \(w=\{c_{1},c_{2},\ldots,c_{k}\}\) provides PR if there is a partition \((V_{1},V_{2},\ldots,V_{k})\) of \(V\) such that \(|V_{i}|=t\) for all \(1\leq i\leq k\) and \(c_{i}\) is approved by all votes in \(V_{i}\). This property was studied in the work by the authors of [24]. From the definitions, it is easy to see that EJR implies PJR, and PJR implies JR [22; 24]. As discussed in the previous section, two important questions are (1) whether we can always calculate a committee providing a certain property efficiently and (2) whether we can determine whether a given committee provides a certain fairness property efficiently. For JR, we have positive answers to both questions. However, for the two more refined concepts EJR and PJR, we have only the positive answer to the first question. See Table 3 for a summary of the concrete results. The next important question is, therefore, whether there are committees providing several fairness properties simultaneously, and whether we calculate such a committee in polynomial time if it exists. We check the answer by surveying several well-studied and natural multi-winner voting rules. **Approval voting (AV). ** The AV score of a candidate is the number of votes approving this candidate, and a winning \(k\)-committee consists of \(k\) candidates with the highest AV scores. \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Complexity of Computing** & **Complexity of Testing** \\ \hline justified representation & P [23] & P [23] \\ extended Justified representation & P [25] & co-NP-complete [23] \\ proportional Justified representation & P [24] & co-NP-complete [25] \\ perfect representation & NP-complete [24] & P [24] \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Complexity of computing a committee satisfying a proportional property or testing whether a given committee satisfies a proportional property. **Satisfaction approval voting (SAV).