Approval elections with a variable number of winners

Abstract

Multi-winner elections, for example, the election of members to a committee, are now quite common, and include the interesting subclass of elections with a variable number of winners, or VNW elections. In VNW elections, voters determine how many winners there are, as well as which candidates win. Common VNW elections include elections to bestow honorary status, such as enshrinement in a hall of fame, and elections to determine a shortlist of, say, job candidates for interviews. Such elections are VNW elections whenever the number of winners is not specified in advance. Multi-winner elections are often conducted by adapting standard procedures for single-winner elections. Approval balloting is particularly appropriate for multi-winner elections, as every ballot, and the set of winners, are subsets of the set of all candidates. Many methods of counting approval ballots appropriate to VNW elections are reviewed and illustrated, and their properties—desirable and undesirable—discussed.

1 Introduction

Multi-winner elections seem to be increasingly common, perhaps reflecting greater computational capabilities and the ubiquity of the internet as much as the growth of democracy. Multi-winner elections are used to populate committees, select papers for conferences, and determine times to meet and topics to be added to an agenda. Many procedures are available for multi-winner elections, including generalizations of plurality voting ranging from single non-transferable vote through cumulative voting to single transferable vote, and well as various forms of list-based proportional representation (Tideman 2016).¹ As well, many single-winner election procedures based on scores, such as Borda Count and Range Voting, are easy to adapt to the multi-winner context.

Among the latter group are procedures using approval balloting, that is, a voter’s ballot indicates the candidates approved by the voter. Approval ballots are natural for multi-winner elections because every ballot, and the winners, are all subsets of the set of all candidates. For a general review of multi-winner election procedures using approval balloting, see Kilgour (2010).

This paper concerns elections carried out with approval ballots, which may be unrestricted or restricted in the sense that not all subsets of candidates can be specified on an approval ballot—a ballot for a “forbidden” subset is considered spoiled, and discarded. Ballot restrictions are common in committee, or fixed number of winners (FNW), elections. A committee election or k-election is an election to select a set of k candidates, where k is fixed in advance. In committee elections carried out with approval balloting, it is not uncommon to require that each voter approves at most k candidates.

Plurality voting can be viewed as approval balloting with the severe restriction that each voter may approve only one candidate. While plurality voting is not common in k-elections with $k > 1$, the procedures discussed here nonetheless apply to it. More generally, ballot restrictions do not alter procedures for counting ballots, although they may affect voters’ strategies, and therefore the results of the election. Moreover, Ratliff and Saari (2014) suggest that ballot restrictions alone are unlikely to be sufficient to guarantee that the elected committee will satisfy “diversity” constraints.

Ballot restrictions are limitations on the possible ballots that may be cast; equally, there may be limitations on the possible sets of winners of the election. Such restrictions are expressed by specifying the admissible sets, or sets of candidates that could win the election. Admissibility is often used to impose distributional requirements on the winning set, for example, the admissible sets may contain only sets with at least one man and at least one woman, or must contain a representative of each subdivision of an organization. Admissibility is certainly relevant to FNW or k-elections, where every admissible set must contain exactly k candidates. For a discussion of procedures based on approval balloting for FNW elections, see Kilgour and Marshall (2012).

The main concern here is the development of procedures for approval elections with a Variable Number of Winners, or VNW elections, where the admissible sets are not all of the same size. In a VNW election, the voters determine not just which candidates win, but also how many winners there are. Common examples include elections to bestow honorary status, such as enshrinement in a hall of fame, or to screen a larger set of candidates to determine a smaller set which it is practical to examine more closely. An example of the latter process is the determination of a shortlist of job candidates who will be invited to an interview. Note that distributional requirements, represented by admissibility conditions, may also also apply to a VNW election.

We address how to design procedures for an approval VNW election. To simplify the presentation, we will assume that any subset is admissible, as it is easy to modify our conclusions to fit other cases. First we review the simple approval procedure, and discuss its application to VNW elections. Then we collect some other procedures that are appropriate to VNW elections and discuss some of their properties.

2 Approval voting and multi-winner elections

First, we set the terminology and notation for approval voting in a single-winner election (Brams and Fishburn 1978, 1983). Suppose that there are $m > 1$ candidates and $n > 1$ voters. Denote the set of all voters by $\mathcal {V}$ and denote the set of all candidates by $\mathcal {C} = \{C_1, C_2, \ldots , C_m \}$. (Sometimes we will refer to candidate $C_j$ as candidate j.)

In approval voting, each voter is asked to name all candidates he or she approves. For $i \in \mathcal {V}$, voter i’s ballot, $V_i \subseteq \mathcal {C}$, is voter i’s response to this request. Both $V_i = \emptyset$ and $V_i = \mathcal {C}$ are possible, but both mean that voter i is in fact not participating in the election, so we will assume that $V_i$ is a non-empty, proper subset of $\mathcal {C}$. Then $(V_i)_{i \in \mathcal {V}}$ is called the ballot profile; the set of all possible ballot profiles is the set of all possible assignments of a subset of $\mathcal {C}$ to each member of $\mathcal {V}$, denoted $\mathcal {P} = \left( 2^{\mathcal {C}}\right) ^\mathcal {V}$.

Table 1 shows Example 1, an election conducting using approval balloting, with four voters and three candidates. One voter votes for $C_1$ only, two vote for $C_1$ and $C_2$ (but not $C_3$), and one votes for $C_1$ and $C_3$ (but not $C_2$).

Example 1

Ballot Profile $(\{1\}, \{1, 2\}, \{1, 2\}, \{1, 3\})$.

Table 1 Example 1: $n = 4, m = 3$

Beginning with a ballot profile, the winner under approval voting is determined from the candidates’ approval scores. The approval score of candidate $C_j \in \mathcal {C}$ is

$$\begin{aligned} x_j = |\{i \in \mathcal {V} : C_j \in V_i \}|. \end{aligned}$$

(1)

Thus, candidate $C_h$’s approval score equals the number of voters who approve $C_h$. Candidate $C_j \in \mathcal {C}$ is a approval winner, or winner under approval voting, iff

$$\begin{aligned} x_j \ge x_h \quad \text { for all } C_h \in \mathcal {C}. \end{aligned}$$

(2)

In other words, the approval winners are the candidates with maximum approval score. Of course, a tie occurs when two or more candidates obtain this maximum score.

In Example 1, the approval scores (vote counts) are $x_1 = 4, x_2 = 2, x_3 = 1$. Table 2 shows the approval scoring of Example 1. In Example 1, it is clear that the unique approval winner (score shown in boldface) is $C_1$.

Table 2 Approval Scoring of Example 1

Most approaches to approval balloting are based on the use of (1) to convert the ballot profile to a vote count vector $x = (x_1, x_2, \ldots , x_m) \in \mathbb {Z}^m$. The total number of votes cast in the election is $X(x) = X = \sum _{j=1}^m x_j$. For Example 1, $x = (4, 2, 1)$ and $X = 7$. We assume throughout that $x_j > 0$ for all $C_j \in \mathcal {C}$; in other words, we drop any candidate who received no votes, so that the vote count vector is $x \in \mathbb {Z}^m_+$.

We are interested in multi-winner rather than single-winner elections. Specifically, the election will be won not by a candidate but by a subset of candidates, $W \subseteq \mathcal {C}$. Often, it is desired to elect a set of candidates that satisfies some “diversity” conditions. As demonstrated by Ratliff and Saari (2014), ballot restrictions cannot be guaranteed to produce a winning subset that satisfies the same restrictions. A solution, suggested by Fishburn and Pekeč (2004), is to specify all possible winning subsets of candidates, called admissible sets. The list of admissible sets is denoted $\mathcal {A} \subseteq 2^{\mathcal {C}}$, and we can assume that $|\mathcal {A}| > 1$. Note that $\mathcal {A}$ can be considered to be a parameter of the election, like the number of voters, n, and the number of candidates, m.

If the election is conducted to select a committee with k members, where k is a positive integer, and there are no other restrictions, then the admissible sets are

$$\begin{aligned} \mathcal {A}_k = \{ S \subseteq \mathcal {C} {:} |S| = k \}. \end{aligned}$$

Any election with $\mathcal {A} \subseteq \mathcal {A}_k$ is a k-election.

A scoring rule for an election is a function $f{:} \mathcal {A} \longrightarrow \mathbb {R}$. (The scoring rule also depends on the ballot profile or the vote count vector, but that dependence is suppressed in this notation.) The scoring rule f assigns to the admissible set $A \in \mathcal {A}$ the value f(A), which is taken to measure the appropriateness of A as the set of winners of the election (given the underlying ballot profile). We define $S \in \mathcal {A}$ to be a winning subset under scoring rule $f(\cdot )$ iff

$$\begin{aligned} f(S) \ge f(T) \quad \text { for all } T \in \mathcal {A}. \end{aligned}$$

(3)

In other words, a winning subset under a scoring rule is any admissible set with maximum score.

For example, (1) can be generalized to an Approval Scoring rule. The approval score of an admissible set $S \in \mathcal {A}$ is

$$\begin{aligned} f_\mathrm{AV}(S) = \sum _{i \in \mathcal {V}} |S \cap V_i| . \end{aligned}$$

(4)

In words, the approval score of a subset is the total number of times that a voter approved a member of that subset. Note that substituting $S = \{C_j\}$ into (4) produces $f_\mathrm{AV}(C_j) = x_j$, so that (4) generalizes (1). It follows that (3) is equivalent to (2) when$f(\cdot ) = f_\mathrm{AV}(\cdot )$ and $\mathcal {A} = \mathcal {A}_1$ .

Note that (4) implies that ballot restrictions, such as a ceiling on the number of candidates a voter may approve, are irrelevant to the calculation of approval scores. Therefore, (3) can be used to determine the winner(s) without regard to possible ballot restrictions, which we will ignore in any calculations based on approval scores. Nonetheless, we recall that ballot restrictions may well affect voters’ strategies and, therefore, election results.

Treating Example 1 as a 2-election with admissible set $\mathcal {A}_2$ (any 2-subset may win) produces the approval scores shown in Table 3. The unique winning subset is $\{C_1, C_2\}$.

Table 3 Example 1 as a 2-election: $n = 4, m = 3, k = 2$

Our objective is to study multi-winner elections that are not k-elections. In such elections, $\mathcal {A}$ contains sets of different cardinalities. Below, we will assume that every subset of candidates is admissible, i.e., $\mathcal {A} = 2^\mathcal {C}$, to avoid the need to verify that a subset is admissible before declaring it a winner.

Table 4 shows how Example 1 changes when $\mathcal {A} = 2^{\mathcal {C}}$, i.e., any subset of candidates may win. Observe that the unique winner is $\{C_1, C_2, C_3\}$.

Table 4 Example 1 as a VNW election: $n = 4, m = 3, \mathcal {A} = 2^\mathcal {C}$

Example 1 considered as a VNW election demonstrates why approval scoring cannot be recommended in VNW elections—larger subsets automatically attain higher scores. This bias toward larger subsets implies that $\mathcal {C}$, the set of all candidates, is always a winner of a VNW election with approval scoring—in fact, our assumption that every candidate receives at least one vote implies that $\mathcal {C}$ is the unique winner.

What we have just observed is really a simple form of linearity: the score for a set equals the sum of the scores of its non-overlapping subsets. Formally, a scoring rule $f(\cdot )$ is additive if whenever $S_1, S_2 \in \mathcal {A}$ and $S_1 \cap S_2 = \emptyset$, then $f(S_1 \cup S_2) = f(S_1) + f(S_2)$ (Kilgour 2010). If $f(\cdot )$ is additive, then $f(S) = \sum _{j \in S} f(j)$ (where $f(j) = f(\{j\})$), which explains why such a scoring rule is sometimes called candidate-wise (Kilgour and Marshall 2012).

3 Net scoring procedures for VNW elections

Many procedures that are appropriate for VNW elections conducted with approval balloting will be described later in this report but Approval Scoring is not among them, because of its bias toward larger subsets. However, this bias is easy to correct, as noted by Kilgour (2010), who proposed the Net Approval Score:

$$\begin{aligned} f_\mathrm{NAV}(S) = \sum _{i \in \mathcal {V}} |S \cap V_i| - |S \cap V_i^c | \end{aligned}$$

(5)

where $V_i^c$ is the complement of $V_i$. The Net Approval Score of a set can be interpreted as the total number of approvals of members of that set reduced by the total number of disapprovals, where disapproving a candidate means not voting for him or her.

Comparison of Table 5 (Net Approval Scoring) and Table 4 (Approval Scoring) makes it clear how Net Approval Scoring corrects the bias of Approval Scoring toward larger subsets. Under Net Approval Scoring, the two sets $\{C_1\}$ and $\{C_1, C_2\}$ both receive score 4 ($\{C_1\}$ has four approvals and no disapprovals, while $\{C_1, C_2\}$ has six approvals and two disapprovals). Thus, both are winners, i.e., they are tied.

Table 5 Example 1: $n = 4, m = 3, \mathcal {A} = 2^\mathcal {C}$, Net Approval Scoring

In fact, any scoring rule that is biased toward larger subsets can be converted to a corresponding net scoring rule that corrects this bias. If the scoring rule $f(\cdot )$ is written in the form $f(S, V_1, V_2, \ldots , V_n)$, then the corresponding net scoring rule is defined by

$$\begin{aligned} f_\mathrm{Net}(S) = f(S, V_1, V_2, \ldots , V_n) - f(S, V_1^c, V_2^c, \ldots , V_n^c). \end{aligned}$$

The idea is to regard not voting for a candidate as disapproving the candidate, and reducing total approvals by total disapprovals.

Some scoring rules, such as approval, are additive, an important property because it speeds up calculation. It is easy to verify that if a scoring rule is additive, then so is its associated net scoring rule. For example, Net Approval is additive; the scores in Table 5 can be obtained from the candidate scores $f_\mathrm{Net}(1) = 4, f_\mathrm{Net}(2) = 0, f_\mathrm{Net}(3) = -2$.

Many other scoring rules have a natural bias toward larger subsets, which can be corrected using a net version. For example, Satisfaction Approval Voting (Brams and Kilgour 2014) is based on the Satisfaction Approval Score

$$\begin{aligned} f_\mathrm{SAV}(S) = \sum _{i \in \mathcal {V}} \frac{|S \cap V_i|}{|V_i|}, \end{aligned}$$

with the convention that a fraction equals zero if its denominator is zero. In Satisfaction Approval, approval votes are downweighted according the number of candidates approved of by the voter. As an example, see Table 6 for Example 1 considered as a VNW election. It is clear that Satisfaction Approval is biased toward larger subsets.

Table 6 Example 1 as SAV and NSAV VNW elections

The Net Satisfaction Approval Score is defined as

$$\begin{aligned} f_\mathrm{NSAV}(S) = \sum _{i \in \mathcal {V}} \frac{|S \cap V_i|}{|V_i|} - \frac{|S \cap V_i^c|}{|V_i^c|} \end{aligned}$$

The use of this score is also shown in Table 6. It is noteworthy that both SAV and NSAV are additive.

Other scoring rules for which a net version might be appropriate are the satisfaction-related scoring rules Capped Satisfaction Approval (CSA) and Modified Satisfaction Approval (MSA) defined by

$$\begin{aligned} f_\mathrm{CSA}(S) = \sum _{i \in \mathcal {V}} \frac{|S \cap V_i|}{|S|} \; ; \;\;\; f_\mathrm{MSA}(S) = \sum _{i \in \mathcal {V}} \frac{|S \cap V_i|}{\min \{|S|, |V_i|\}}, \end{aligned}$$

with the usual convention that a fraction equals zero if its denominator is zero (see Kilgour and Marshall 2012 for details). It might be argued that CSA scoring is not biased in favour of larger subsets, because the size of the subset appears in the denominator. Nonetheless, the Net versions of these scoring rules, called NCSA and NMSA, respectively, are of interest, and are applied to Example 1 in Table 7.

Table 7 Example 1 scored with various procedures

Another set of scoring procedures identified by Kilgour and Marshall (2012) are the Generalized Approval Procedures. A rep sequence is a non-decreasing sequence of real numbers $r(0) = 0, r(1), r(2), \ldots$ where r(j) represents the contribution to the score of a subset from a voter’s ballot that has j elements in common with the subset. Specifically, for the rep sequence $r = r(0), r(1), r(2), \ldots$, the rep score is

$$\begin{aligned} f_r(S) = \sum _{i \in \mathcal {V}} r(|S \cap V_i|). \end{aligned}$$

Thus, the score of a subset S equals r(1) times the number of voters who voted for one member of S plus r(2) times the number of voters who voted for two members of S plus $\ldots$.

It is easy to see that the Approval Score $f_\mathrm{AV}(\cdot )$ is the rep score based on the sequence $(0, 1, 2, 3, \ldots )$, that is, $r(j) = j$. The Proportional Approval Score (Simmons 2001) is the rep score based on the rep sequence $(0, 1, 1 + \frac{1}{2}, 1 + \frac{1}{2} + \frac{1}{3}, \ldots )$, that is, $r(j) = \sum _{k=1}^j \frac{1}{k}$, for $j \ge 1$. Another family of rep sequences are the p-representative sequences, defined for parameter $p > 0$ by

$$\begin{aligned} r(j) = {\left\{ \begin{array}{ll} 0 &{}\text {if }j < p \\ 1 &{}\text {if }j \ge p \end{array}\right. } \end{aligned}$$

Thus, the rep score based on the p-representative sequence counts a subset as representing a voter whose ballot has at least p candidates in common with the subset. A subset counts 1 if it represents a voter in this sense, and 0 otherwise. In the tables, the Proportional Approval voting rule is called PAV, and any p-Representative procedure is called REP-p.

Fishburn and Pekeč (2004) provided a generalization of the REP-p (or p-representative) procedures in another direction. An REP-p winner can be defined as any subset S that maximizes

$$\begin{aligned} \left| \{i \in \mathcal {V} : |S \cap V_i| \ge p \}\right| , \end{aligned}$$

that is, the score of S equals the number of voters who approve of at least p members of S. The generalization suggested by Fishburn and Pekeč (2004) was to define a function, called the threshold function, $t{:} 2^\mathcal {C} \longrightarrow \mathbb {Z}_+$ and to define the score of S as the number of voters who approve of at least t(S) members of S. The threshold t(S) should satisfy $1 \le t(S) \le |S|$ and $t(S_1) = t(S_2)$ if $|S_1| = |S_2|$. Thus, the threshold score of a subset S would equal

$$\begin{aligned} \left| \{i \in \mathcal {V} : |S \cap V_i| \ge t(S) \}\right| . \end{aligned}$$

Two specific threshold procedures have appeared in the literature, and seem appropriate for approval VNW elections

$$\begin{aligned} \text {MT}{:}\,t(S) = \frac{|S|}{2} \quad \text { and } \quad \text {SMT}{:}\,t(S) = \frac{|S|+1}{2}, \end{aligned}$$

called the Majority Threshold and the Strict Majority Threshold, respectively. The idea is that a majority, or a strict majority, of the elected subset should be supported by the maximum number of voters.

The Generalized Approval procedures (including approval), the satisfaction-related procedures, and the threshold procedures, are applied to Example 1 in Table 7. Where a net version seems appropriate, it is indicated by a preceding “N”.

4 Centralization procedures for VNW elections

The centralization procedures suggested by Kilgour et al. (2006) and Brams et al. (2005) constitute another set of scoring procedures that apply to VNW approval elections. Because a possible winning subset and a ballot are subsets of the set of all candidates, one can measure the distance between them using Hamming distance (the number of elements—in this case, candidates—in exactly one of the two subsets). Thus, for each possible winning subset, the distances to each ballot can be determined. The idea of a centralization procedure is to identify a subset that minimizes these distances. While these procedures can be viewed as scoring procedures, it is noteworthy that in general a winning subset has minimum, rather than maximum, distance.

Table 8 illustrates the set of distances associated with each possible winning subset using the ballots from Example 1. According to the count-based minisum procedure $\text {MSUM}_\mathrm {c}$, a winning subset is one that minimizes the sum of the distances from the subset to all ballots. According to the count-based minimax procedure $\text {MMAX}_\mathrm {c}$, a winning subset is one that minimizes the maximum distance from the subset to any ballots. Table 8 applies both of these procedures to Example 1. Selected subsets are indicated in boldface; as Kilgour (2010) noted, the Minisum Count ($\text {MSUM}_\mathrm {c}$) and Net Approval (NAV) procedures are very different, but they always produce exactly the same winning sets.

Table 8 Example 1: Ballot distances

Proximity weighting adds a further refinement to centralization procedures. Each distinct ballot is weighted according to the number of times it is cast and according to its distance from other ballots, so as to downweight extreme ballots. If the possible ballots are denoted $B_1, B_2, \ldots B_{2^m}$, if ballot h is cast $c_h$ times, and if $D(\cdot , \cdot )$ denotes Hamming distance, then the proximity weight of ballot k is

$$\begin{aligned} \rho _k = \frac{c_k}{\sum _h c_h D(B_k, B_h)} \end{aligned}$$

For Example 1, the three ballots cast are 1, 12, and 13, with counts 1, 2, and 1, respectively. The proximity weights are $\frac{1}{3}, \frac{2}{3}, \text { and } \frac{1}{5}$, respectively. Table 9 shows the application of the proximity-based minisum procedure $\text {MSUM}_\mathrm {p}$ and the proximity-based minimax procedure $\text {MMAX}_\mathrm {p}$ to Example 1.

Table 9 Example 1: Proximity procedures

5 Next r procedures

The Next Two Rule is probably the simplest procedure proposed for VNW approval elections that is not based on scoring (Brams and Kilgour 2012). We introduce Next Two as a member of the more general Next r family of procedures for VNW approval elections, which are defined for $r = 2, 3, \ldots , m - 1$. The input to a Next r rule is the vote count vector $x = (x_1, x_2, \ldots , x_m) \in \mathbb {Z}^m_+$. To simplify the expressions, we assume that the candidates have been renamed, if necessary, in order that

$$\begin{aligned} x_1 \ge x_2 \ge \cdots \ge x_m \end{aligned}$$

For example, $x_1$ is the number of votes received by the leading candidate. As usual, we assume $\mathcal {A} = 2^\mathcal {C}$. In a Next r rule, the set of winning candidates will be of the form $\{ C_1, C_2, \ldots , C_j\}$. Thus, the winning set, denoted $N_r(x) = \{1, 2, \ldots , j\}$, will contain the j highest scoring candidates, for some j satisfying $1 \le j \le m$.

Fix r such that $2 \le r < m$. Then the Next r Rule is defined formally as follows:

Next r Rule::

The set of winning candidates is $N_r(x) = \{1, 2, \ldots , j\}$ where j is the minimum value of k satisfying both $1 \le k < m$ and

$$\begin{aligned} x_k > \sum _{h=k+1}^{\hbox {min}\{k+r, m\}} x_h \end{aligned}$$

(6)

if such a value of k exists; otherwise, $j = m$.

Thus, the winners as determined by the Next r rule consist of candidate j and all preceding candidates, where, if (6) can be satisfied, j is the first candidate to receive more votes than the total of the next r candidates, if j is relatively small (i.e., j satisfies $j \le m - r$), or than all remaining candidates, if j is large (i.e., $j > m - r$). If (6) cannot be satisfied, then $j = m$, which means that the set of all candidates, $\mathcal {C}$, is the winning set. A necessary condition for (6) to fail for all values of $k < m$, and hence for $N_r(x) = \mathcal {C}$ is $x_{m - 1} = x_m$, since otherwise $x_{m - 1} > x_m$, which implies that (6) is satisfied by $k = m - 1$, and possibly by some smaller value of k.

For Example 1, with $x = (4, 2, 1)$, the unique Next 2 winner is $\{1\}$, since $C_1$’s total approval vote exceeds the total for $C_2$ and $C_3$. But consider

Example 2

$m = 3, x = (4, 3, 2)$, in which 3 candidates receive 4, 3, and 2 votes, respectively.

In Example 2, the unique Next 2 winner is $\{1, 2\}$. More examples illustrating the Next r rule appear below.

It is easy to verify that a Next r procedure never produces a tie. Any winning candidate must have a strictly greater vote count than every losing candidate. In addition, if $2 \le r < s \le m - 1$, then $N_r(x) \subseteq N_s(x)$. For example, the Next 2 winners are always a subset of the Next 3 winners. The Next $m - 1$ Rule is also called the All Remaining Rule, and can be written $N_{AR}(x) = N_{m - 1}(x)$.

6 First majority procedures

Another non-scoring rule, apparently first discovered as a consequence of a system of axioms is the First Majority Rule (Kilgour 2016). Like the Next r Rules, its only input is the vote count vector, $x = (x_1, x_2, \ldots , x_m)$. For any $m > 1$ and any $x \in \mathbb {Z}^m_+$, recall that $X(x) = \sum _{j = 1}^m x_j$, so that X(x) is the total number of approvals when the vote count vector is x. Again like the Next r rules, the set of winning candidates under First Majority will be of the form $\{ C_1, C_2, \ldots , C_j\}$. In other words, the winning set, denoted $N_{FM}(x) = \{1, 2, \ldots , j\}$, will contain the j highest scoring candidates, for some j satisfying $1 \le j \le m$.

First Majority Rule::

$N_{FM}(x) = (1, 2, \ldots , j)$ where

$$\begin{aligned} j = \min \left\{ k : \sum _{h=1}^k x_h > \frac{X(x)}{2} \text { and }x_k > x_{k + 1} \right\} . \end{aligned}$$

Thus, $\hbox {FM}(x)$ consists of the smallest possible set of top-scoring candidates that receives, in total, more than half of all votes and such that every candidate not in the set receives fewer votes than any candidate in the set. For Example 1, with $x = (4, 2, 1)$, we have $N_\mathrm{FM}(x) = \{1\}$. For Example 2, with $x = (4, 3, 2)$, we have $N_\mathrm{FM}(x) = \{1, 2\}$.

Again, it is easy to verify that the First Majority rule never produces a tie. Any winning candidate must have a strictly greater vote count than any losing candidate. In addition, $N_\mathrm{FM}(x) \le N_\mathrm{AR}(x)$, that is the set of First Majority winners is never larger than the set of All Remaining winners. The examples below provide additional illustrations of the First Majority Rule and the Next r Rules. Note that all examples have $m = 5$ candidates. For brevity, we write $N_\mathrm{FM}(x) = \{1, 2, \ldots , \hbox {FM}(x)\}$, $N_r(x) = \{1, 2, \ldots , n_r(x)\}$, and $N_\mathrm{AR}(x) = \{1, 2, \ldots , \hbox {AR}(x)\}$

Example 3

$x=(40, 20, 19, 12, 9)\quad \hbox {FM}(x) = 2, n_2(x) = 1, n_3(x) = \hbox {AR}(x) = 4$

Example 4

$x=(25, 20, 20, 20, 15)\quad \hbox {FM}(x) = 4, n_2(x) = 1, n_3(x) = \hbox {AR}(x) = 4$

Example 5

$x=(24, 20, 20, 18, 18)\quad \hbox {FM}(x) = 3, n_2(x) = n_3(x) = \hbox {AR}(x) = 5$

7 Conclusions

Approval ballots are natural for multi-winner elections, and there are many ways to base a multi-winner election on approval ballots. Variable Number of Winners (VNW) elections are of course multi-winner elections, but not all of the procedures used for multi-winner approval elections are appropriate. Many of them, such as elections to the Baseball Hall of Fame, are based on restricted ballots (a maximum on the number of candidates who may be supported) and scoring thresholds (a minimum score for election) (National Baseball Hall of Fame BBHOF 2015). Since such restrictions and thresholds are essentially arbitrary, one might ask for an “intrinsic” procedure to identify the winner of a VNW election. This paper has reviewed several such procedures, and shown how other multi-winner approval procedures such as Approval (AV) and Satisfaction Approval (SAV) can be converted into procedures that are natural to VNW elections, and in particular do not rely on arbitrary restrictions or thresholds.

Some properties, both representational and computational, have been suggested here, but the analysis of properties, and development of procedures that meet them, is left for others. For instance, the recently proposed property “justified representation” in FNW elections has been shown to be achieved uniquely by Proportional Approval Voting (PAV) (Aziz et al. 2015); it is unknown whether the property carries over in any sense to the Net version, NPAV, in VNW elections. One attempt to axiomatize VNW election is Kilgour (2016). Similarly, computational properties of procedures have barely been mentioned here; indeed many of the procedures described here are known to be computationally hard. There is much work to be done to find good procedures for VNW elections, and to characterize them

More broadly, VNW elections are a metaphor for the integration of preference information or decision recommendations which are important in many contexts, including democracies and group decision processes, as well as in engineering, computer science, and biology. A better understanding of VNW elections may provide new tools that can be used in many different fields.