Multiwinner approval voting
Multiwinner approval voting,'' sometimes also called approval-based committee voting, refers to a family of multi-winner electoral systems that use approval ballots. Each voter may select any number of candidates, and multiple candidates are elected.
Multiwinner approval voting is an adaptation of approval voting to multiwinner elections. In a single-winner approval voting system, it is easy to determine the winner: it is the candidate approved by the largest number of voters. In multiwinner approval voting, there are many different ways to decide which candidates will be elected.
Approval block voting
In approval block voting, each voter either approves or disapproves of each candidate, and the k candidates with the most approval votes win. It does not provide proportional representation.Proportional approval voting
Proportional approval voting refers to voting methods which aim to guarantee proportional representation in case all supporters of a party approve all candidates of that party. Such methods include proportional approval voting, sequential proportional approval voting, Phragmen's voting rules and the method of equal shares. In the general case, proportional representation is replaced by a more general requirement called justified representation.In these methods, the voters fill out a standard approval-type ballot, but the ballots are counted in a specific way that produces proportional representation. The exact procedure depends on which method is being used.
Party-approval voting
Party-approval voting is a method in which each voter can approve one or more parties, rather than approving individual candidates. It is a combination of multiwinner approval voting with party-list voting.Other methods
Other ways of extending approval voting to multiple winner elections are satisfaction approval voting, excess method, and minimax approval. These methods use approval ballots but count them in different ways.Strategic voting
Many multiwinner voting rules can be manipulated: voters can increase their satisfaction by reporting false preferences.Example
The most common form of manipulation is subset-manipulation, in which voters report only a strict subset of their approved candidates. This manipulation is called Hylland free riding; manipulators free ride on others approving a candidate and pretend to be worse off than they actually are. Then, the rule is induced to "compensate" the manipulator by electing more of their approved candidates.As an example, suppose we use the PAV rule with k=3, there are 4 candidates, and 5 voters, of whom three support a,b,c and two support a,b,d. Then, PAV selects a,b,c. But if the last voter reports only d, then PAV selects a,b,d, which is strictly better for him.
Strategyproofness properties
A multiwinner voting rule is called strategyproof if no voter can increase his satisfaction by reporting false preferences. There are several variants of this property, depending on the potential outcome of the manipulation:- Inclusion-strategyproofness means that no manipulation can result in electing a strict superset of the manipulator's approved candidates.
- Cardinality-strategyproofness is a stronger property: it means that no manipulation can result in electing a larger number of the manipulator's approved candidates.
- Independence of irrelevant alternatives means that the relative merit of two committees is not influenced by candidates outside these two committees. This prevents a certain form of strategic voting: altering one's vote with respect to irrelevant candidates to manipulate the outcome.
- Monotonicity means that a voter never loses from revealing his true set of approved candidates. This prevents another form of strategic voting: hiding some approved candidates.
Strategyproofness and proportionality
Cardinality-strategyproofness and inclusion-strategyproofness are satisfied by utilitarian approval voting, but not by any other known rule satisfying proportionality.This raises the question of whether there is any rule that is both strategyproof and proportional. The answer is no: Dominik Peters proved that no multiwinner voting rule can simultaneously satisfy a weak form of proportionality, a weak form of strategyproofness, and a weak form of efficiency. Specifically, the following three properties are incompatible whenever k ≥ 3, n is a multiple of k, and the number of candidates is at least k+1:
- Subset-inclusion-strategyproofness: if an agent i with approved-candidates Ai reports a subset of Ai, then no previously unelected candidate from Ai is elected. This property is weaker than inclusion-strategyproofness, as it considers only one type of manipulation: reporting a subset of one's truthful approval set.
- Party-list-proportionality: We define a party-list profile as a profile characteristic of party-list voting, that is: there is a partition of the voters into k groups and a partition of the projects into k subsets, such that each voter from group i votes only and for all projects in group i. Party-list proportionality means that, in a party-list profile, if some singleton ballot appears at least B/''n times, then x'' is elected. This property is weaker than the property of lower quota from apportionment, and weaker than the justified representation property.
- * An alternative property, for which the impossibility holds, is disjoint diversity. It means that, in a party-list profile with at most k different parties, the rule selects at least one member from each party.
- Weak efficiency: if a candidate x is not supported by anyone, and there are at least k candidates that are supported, then x is not elected.
Degree of manipulability
Lackner and Skowron quantified the trade-off between strategyproofness and proportionality by empirically measuring the fraction of random-generated profiles for which some voter can gain by misreporting. Example results, when each voter approves 2 candidates, are: Phragmen's sequential rule is manipulable in 66% of the profiles; Sequential PAV - 68%; PAV - 71%; Satisfaction AV and Maximin AV - 86%; Approval Monroe - 92%; Chamberlin-Courant - 95%. They also checked manipulability of Thiele's rules with p-geometric score function. Note that p=1 yields utilitarian AV, whereas p→∞ yields Chamberlin-Courant. They found out that increasing p results in increasing manipulability: rules which are more similar to utilitarian AV are less manipulable than rules that are more similar to CC, and the proportional rules are in-between.Barrot, Lang and Yokoo present a similar study of another family of rules, based on ordered weighted averaging and the Hamming distance. Their family is also characterized by a parameter p, where p=0.5 yields utilitarian AV, whereas p=1 yields egalitarian AV. They arrive at a similar conclusion: increasing p results in a larger fraction of random profiles that can be manipulated.
Restricted preference domains
One way to overcome impossibility results is to consider restricted preference domains. Botan consider party-list preferences, that is, profiles in which the voters are partitioned into disjoint subsets, each of which votes for a disjoint subset of candidates. She proves that Thiele's rules resist some common forms of manipulations, and it is strategyproof for "optimistic" voters.Irresolute rules
The strategyproofness properties can be extended to irresolute rules. Lackner and Skowron define a strong extension called stochastic-dominance-strategyproofness, and prove that it characterizes the utilitarian approval voting rule.Kluiving, Vries, Vrijbergen, Boixel and Endriss provide a more thorough discussion of strategyproofness of irresolute rules; in particular, they extend the impossibility result of Peters to irresolute rules. Duddy presents an impossibility result using a different set of axioms.
Non-dichotomous preferences
There is an even stronger variant of strategyproofness called non-dichotomous strategyproofness: it assumes that agents have an underlying non-dichotomous preference relation, and they use approvals only as an approximation. It means that no manipulation can result in electing a committee that is ranked higher by the manipulator. Non-dichotomous strategproofness is not satisfied by any non-trivial multiwinner voting rule.Scheuerman, Harman, Mattei and Venable present behavioral studies on how people with non-dichotomous preferences behave when they need to provide an approval ballot, when the outcome is decided using utilitarian approval voting.