## 2 Multi-Winner Voting
### Voter Fairness in Approval-Based Voting
** The SAV score of a candidate \(c\) is defined as  
\[\sum_{c\in p\in V}\frac{1}{|v|}-\sum_{ \begin{subarray}{c}v\in V,\\ c\
otin p\end{subarray} }\frac{1}{m-|v|}\]  
where \(m\) denotes that number of candidates. A winning \(k\)-committee consists of \(k\) candidates with the highest SAV scores. **Minimax approval voting (MAV). ** This rule aims to find a committee that is most close to every voter's opinion. More precisely, the Hamming distance between a committee \(w\) and a vote \(v\) is \(d_{\mathrm{H}}(v,w)=|w\setminus v|+|v\setminus w|\), and this rule selects a \(k\)-committee \(w\) minimizing \(\max_{v\in V}d_{\mathrm{H}}(v,w)\). **Proportional approval voting (PAV). ** The PAV score of a committee \(w\) is defined as  
\[\sum_{ \begin{subarray}{c}v\in V,\\ v\cap w\
eq\emptyset\end{subarray} }\left(1+\frac{1}{2}+\cdots+\frac{1}{|v\cap w |}\right).\]  
A winning \(k\)-committee is an one with the maximum score. **Sequential proportional approval voting (seq-PAV). ** This rule provides an approximation solution to PAV rule. It selects \(k\) winners in \(k\) rounds, one in each round. Precisely, initially we let \(w=\emptyset\). Assume that we have an \(i\)-committee \(w\) after round \(i<k\). Then, in the next round, we find a candidate \(c\) which offers the maximum PAV score of \(w\cup\{c\}\), and we extend \(w\) by resetting \(w:=w\cup\{c\}\). After \(k\) rounds, \(w\) contains exactly \(k\) candidates. **Chamberlin-Courant approval voting (CCAV). ** This rule is a variant of CC rule for approval-based voting. In particular, a voter satisfies with a committee if and only if this committee contains at least one of her approved candidates. This rule selects a \(k\)-committee that satisfies the maximum number of voters. **[PERSON]'s approval voting (MonAV). ** This is a variant of [PERSON]'s rule for approval-based voting and is similar to CCAV. In CCAV, a candidate can satisfy all voters who approve this candidate. However, in MonAV, we require that each candidate is assigned to at most \(\left\lceil\frac{u}{k}\right\rceil\) voters approving this candidate and, moreover, each voter can be assigned to at most one candidate. The MonAV score of a committee is the maximum number of voters who are satisfied by this committee and fulfill the above conditions. In addition to the above rules, a class of important rules, coined by [PERSON], have been studied. These rules determine the winners in a reverse-thinking approach. Particularly, assume that we know the \(k\) winners. The rules assume that each of this winners has a unit point which is distributed over all voters approving this candidate in a way to achieve some objective ([PERSON]'s rules differ only at the objectives). Then, the selected winners should be those that yield the optimal objective over all subsets of \(k\) candidates. We give the formal definitions below. A _load distribution_ is a two-dimensional array \(\mathbf{x}=(x_{v,c})_{v\in V,c\in\mathrm{C}}\) satisfying the following conditions. 1. For each \(v\in V\) and \(c\in C\) it holds that \[0\leq x_{v,c}\leq 1.\]
2. For every \(c\in C\) and \(v\in V\), if \(c\
otin v\), then \[x_{v,c}=0.\] This corresponds to winner that is only distributed over voters approving that winner. 3. It holds that \[\sum_{v\in V,c\in C}x_{v,c}=k.\] That is, there are in total \(k\) points to be distributed. For every \(c\in C\), it holds that \[\sum_{v\in V}x_{v,c}\in\{0,1\}.\] This together with the previous restriction ensure that exactly \(k\) candidates have points to distribute. For a load distribution \(\mathbf{x}\) and a vote \(v\), let \(x_{v}=\sum_{c\in C}x_{v,c}\). Particularly, \(x_{v}\) is referred to as the voter load of \(v\). Due to the last two conditions in the definition of load distribution, we know that each load distribution \(\mathbf{x}\) gives us a unique \(k\)-committee  
\[f(\mathbf{x})=\left\{c\in C:\sum_{v\in V}x_{v,c}=1\right\}.\]  
Note that for a \(k\)-committee \(w\), there can be multiple load distributions \(\mathbf{x}\) such that \(f(\mathbf{x})=w\). **max-Phragmen.