The maximin support method: an extension of the d'Hondt method to approval-based multiwinner elections (Q6201928)

In this paper the authors propose an extension of the d'Hondt method -- for distributing seats in parliament based on the support (number of votes) obtained by the different parties -- to approval-based multi-winner elections. Their method is based on the same principle as the d'Hondt method, in that the voter support for the least supported elected candidate should be as large as possible. They call this new method the maximin support method (MMS). An (approval-based multiwinner) election \(E\) can be represented by a tuple \(E = (N, C, A, k)\), where \(N = \{1, \ldots, n\}\) is a set of voters, \(C\) a set of candidates, \(A = (A_1, \ldots, A_n)\) a list of of approval ballots, one for each voter \(i \in N\) and \(k\) the number of committee members to be elected. An (approval-based multiwinner voting) rule \(R\) is a function that maps an election \(E = (N,C, A, k)\) to a subset \(R(E) \subseteq C\) of candidates of size \(|R(E)| = k\), referred to as the committee. For each voter \(i \in N\), let \(f (i, c)\) be the fraction of voter \(i\)'s vote that is assigned to candidate \(c\). In particular, \(f (i, c) = 0\) whenever \(c \not\in A_i\), i.e., whenever \(i\) does not approve of \(c\). Given an approval profile \(A = (A_1, \ldots , A_n)\) and a nonempty subset \(D \subseteq C\) of candidates, let \(F_{A,D}\) be the set of all functions \(f: N \times D \rightarrow [0, 1]\) such that \(f(i, c) = 0\) for all \(i \in N\) and \(c \in D - A_i\), and \(\sum_{c \in A_i \cap D} f(i, c) = 1\) for all \(i \in N\) with \(A_i \cap D \neq \emptyset\). Given a vote assignment \(f \in F_{A,D}\) and a candidate \(c \in D\), let \(\mathrm{supp}_{f} (c)\) denote the total support received by \(c\) under \(f\), i.e., \(\mathrm{supp}_{f} (c) = \sum_{i \in N} f (i, c)\). Let \(\mathrm{maximin}(A, D)\) denote the maximal support for the least supported candidate in \(D\), where the maximum is taken over all vote assignments in \(F_{A,D}\). Formally, \(\mathrm{maximin}(A, D) = \max_{f \in F_{A,D}} \min_{c \in D} \mathrm{supp}_{f} (c)\). Furthermore, let \(F_{A,D}^{opt}\) be the (non-empty) set of optimal vote assignments for (\(A, D\)), i.e., \[ \mathcal{F}_{A, D}^{opt} := \{f \in F_{A,D} : \mathrm{supp}_{f}(c) \geq \mathrm{maximin}(A, D) \mbox{ for all } c \in D\}. \] Given an approval based multiwinner election \(E = (N, C, A, k)\), the set \(W = MMS(E)\) of winning candidates is determined by starting with \(W = \emptyset\) and iteratively adding candidates until \(|W| = k\). In each iteration, the authors add to \(W\) an unelected candidate receiving the greatest support under the condition that only optimal vote assignments are considered. The following theorems for the maximin support method (MMS) are proved: 1. It can be computed in polynomial time. 2. It is an extension of the d'Hondt method for distributing seats in party-list systems of proportional representation. 3. It satisfies committee monotonicity, i.e., all selected candidates are still selected when the committee size \(k\) is increased. 4. It satisfies weak support monotonicity, i.e., when the support of a subset of the winners is increased, at least one of those candidates must remain in the winning set. 5. It satisfies proportional justified representation. In additon, the authors show by giving counterexamples that there are a number of properties the maximin support method does not satisfy. In section 5.6 they review three axiomatic characterizations of the d'Hondt method given by \textit{M. L. Balinski} and \textit{H. P. Young} [Fair representation: meeting the ideal of one man, one vote. New Haven, CT: Yale University Press (1982)] and discuss the potential of generalizing the respective characterizations to approval-based multi-winner elections. Finally, in the last section they compare the maximin support method with other generalizations to approval based multi-winner elections of the d'Hondt method by Phragmén and Thiele. The paper is well written and illustrated by many examples to clarify the content.