## 2 Multi-Winner Voting
### Voter Fairness in Ranking-Based Voting  
We consider first ranking-based voting where voters are asked to report linear order preferences over candidates. A voter \(v\)'s preference is denoted by \(\succ_{v}\), so that \(a\succ_{v}b\) represents that this voter prefers the candidate \(a\) to the candidate \(b\). A crucial notion in this setting is _solid coalition_ which was first mentioned in the work by the authors of [15]. Particularly, for a subset \(C^{\prime}\subseteq C\) of candidates, a solid coalition is a subset of voters \(U\subseteq V\) such that all voters in \(U\) rank all candidates in \(C^{\prime}\) above all the other candidates, i.e., for all voters \(v\in U\), it holds that \(a\succ_{v}b\) for all \(a\in C^{\prime}\) and \(b\in C\setminus C^{\prime}\). In this case, we say that \(U\) supports \(C^{\prime}\) and call \(U\) a \(C^{\prime}\)-solid coalition. The following proportional property provides fairness for solid coalitions: it states that for a solid coalition of a certain scale, a guaranteed number of candidates supported by this coalition should be selected as winners. \(q\)**-Proportionality for solid coalition (\(q\)-PSC) [16]. ** For a rational number, \(q\), a \(k\)-committee \(w\subseteq C\) satisfies \(q\)-PSC if for every positive integer \(\ell\) and for every solid coalition \(U\subseteq V\) supporting some \(C^{\prime}\subseteq C\) such that \(|U|\geq\ell q\), it holds that \(|w\cap C^{\prime}|\geq\min\{\ell,|C^{\prime}|\}\). Normally, we are only interested in the case where \(\frac{n}{k+1}<q\leq\frac{n}{k}\), where \(n\) denotes the number of voters. One of the reason is that when \(k=1\), i.e., we select only one winner, a \(q\)-PSC committee is a singleton consisting of a candidate who is most preferred by at least a majority of the voters, whenever such a candidate exists (note that such a candidate must be a Condorcet winner). In addition, \(q\)-PSC is not guaranteed to exist if \(q\leq n/(k+1)\). Moreover, if \(q>n/k\), any \(q\)-PSC committee must provide some counter-intuitive properties (see the work by the authors of [16] for the details). Specifically, if \(q\) is equal to the so-called Hare quota \(n/k\), the property is referred to as Hare-PSC (\(q_{\text{H}}\)-PSC). Besides, if \(q\) is equal to the Droop quota \(\left\lfloor\frac{n}{k+1}\right\rfloor+1\), the property is referred to as Droop-PSC (\(q_{\text{D}}\)-PSC). Proportionality for solid coalition seems to be first considered by [PERSON] [15]. Many of its variants have been studied very recently [16; 17]. For example, the weak \(q\)-PSC puts constraints only on solid coalitions supporting a limited sized committee, and asks a committee \(w\) to contain all candidates who are supported by these solid coalitions. **Weak \(q\)-PSC.**[16]. A committee \(w\subseteq C\) satisfies weak \(q\)-PSC if the following holds, for every positive integer \(\ell\), every \(C^{\prime}\subseteq C\) such that \(|C^{\prime}|\leq\ell\), and every \(C^{\prime}\)-solid coalition \(U\) of size at least \(\ell q\), it holds that \(C^{\prime}\subseteq w\). Similar to \(q\)-PSC, we are particularly interested in the case where \(\frac{n}{k+1}<q\leq\frac{n}{k}\). Weak \(q_{\text{H}}\)-PSC and weak \(q_{\text{D}}\)-PSC are referred to as weak \(q\)-PSC, where \(q\) takes the Hare quota and the Droop quota, respectively. Both PSC and weak PSC are designed to guarantee fairness for voters at group levels, but they differ at the degree of fairness they could provide. In fact, due to the definitions, we know that \(q\)-PSC implies weak \(q\)-PSC, but not necessarily the other way around. Given a concept of fairness, a significant question is whether we can compute a committee providing the fairness efficiently. Let \(\tau\) be a fairness property. \(\tau\)**-Computing**  
Input:  
Prior to the proposal of many fairness properties, a large body of voting rules have been extensively and widely studied in the literature.