Multiwinner approval voting

The goal is to construct a committee with k members. There is a set C of m candidates; usually m>k (otherwise the problem is trivial). There are some n voters. Each voter i, let A_i ⊆ C be the set of candidates approved by voter i. A multiwinner voting rule takes k and the A_i as an input, and returns a subset W ⊆ C of winners, such that |W|=k. The utility of voter i for a committee W is the number of approved winners it contains, u_i(W) = |A_i ∩ W|.

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, different ways may be used to decide which candidates are elected.

The simplest multiwinner voting rule is block approval voting, in which the k candidates with the largest number of approvals are elected. This rule corresponds to the utilitarian rule, as it maximizes the total satisfaction. However, it is unfair as it does not provide proportional representation.

Various other multiwinner voting rules have been developed in order to guarantee various forms of proportional representation. 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.

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.

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 (a,b,c,d), 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 (as in the PAV example above).
• Cardinality-strategyproofness is a stronger property: it means that no manipulation can result in electing a larger number of the manipulator's approved candidates.

Strategyproofness properties can also be classified by the type of potential manipulations:

• 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.

Lackner and Skowron focus on the class of ABC-counting rules (an extension of positional scoring rules to multiwinner voting). Among these rules, Thiele's rules are the only ones satisfying IIA, and dissatisfaction-counting-rules are the only ones satisfying monotonicity. Utilitarian approval voting is the only non-trivial ABC counting rule satisfying both axioms. It is also the only non-trivial ABC counting rule satisfying SD-strategyproofness—an extension of cardinality-strategyproofness to irresolute rules. If utilitarian approval voting is made resolute by a bad tie-breaking rule, it might become non-strategyproof.

Strategyproofness and proportionality

Cardinality-strategyproofness and inclusion-strategyproofness are satisfied by utilitarian approval voting (majoritarian approval voting rule with unlimited ballots), 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 A_i reports a subset of A_i (and all other reports are the same), then no previously unelected candidate from A_i 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 {x} 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.

The proof is by induction; the base case (k=3) was found by a SAT solver. For k=2, the impossibility holds with a slightly stronger strategyproofness axiom.

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 (where the scores are powers of 1/p, for some fixed p). 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 (such as PAV) resist some common forms of manipulations, and it is strategyproof for "optimistic" voters.

Irresolute rules

The strategyproofness properties can be extended to irresolute rules (rules that return several tied committees). 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.

The core is a strong stability and proportionality requirement borrowed from cooperative game theory and from the theory of public goods. It was brought into approval-based committee voting by Aziz, Brill, Conitzer, Elkind, Freeman and Walsh. The idea is that each voter is regarded as holding an entitlement of k/n seats, and a group of voters may pool its entitlements to "buy" a committee of its own.

Definition

Given a winning committee W of size k, a subset S of voters is called a blocking coalition if there is a set of candidates T ⊆ C with |T| ≤ (|S| / n) · k such that u_i(T) > u_i(W) for every voter i ∈ S. A blocking coalition is large enough that it could elect T with the combined entitlement of all its members, and yet every one of its members strictly prefers T to the committee that was actually elected.

A committee W of size k lies in the core if it has no blocking coalitions.

The definition of core can be adapted to the more general setting of combinatorial participatory budgeting, where candidate j has a size or cost s_j and the committee must satisfy a budget constraint b rather than a cardinality constraint: a group S can afford any set T with total cost at most (|S|/n)·b, and voters may have arbitrary monotone utility functions over sets of candidates. Multiwinner approval voting is the special case in which every candidate has the same cost and every voter has a 0–1 additive utility function.

Relation to other axioms

Core stability is stronger than the representation axioms most often studied for approval-based committee rules: every committee in the core satisfies extended justified representation, and therefore also proportional justified representation and justified representation, and it is Pareto optimal.

The converse is not true: Proportional approval voting (PAV) satisfies extended justified representation but not the core. Peters and Skowron showed that no welfarist rule — one whose choice depends only on the vector of voter utilities induced by a committee — can always return a core-stable committee.

Existence

Whether a committee in the core always exists is one of the best-known open problems in the field. Currently, only partial results are known. The known positive results are the following.

• Peters proved, with the aid of computer search over linear programs, that the core is non-empty whenever k ≤ 8 (for any m and n), by showing that PAV itself always returns a core-stable committee when k ≤ 7 and returns at least one core-stable committee when k = 8; a rule built by recursively applying PAV shows non-emptiness whenever m ≤ 15.
• Becker, Greger and Peters proved non-emptiness for every election with at most 5 voters, and more generally with at most 5 distinct approval sets, using affine monoid methods; in these cases a core-stable committee can be found in polynomial time.
• Cheng, Jiang, Munagala and Wang established the case k = 3, and showed that stable lotteries — probability distributions over committees that no group can block in expectation — always exist in the approval setting. That is, the fractional core is never empty. However, they did not provide an efficient algorithm for computing the fractional core.
• Pierczyński and Skowron showed that the core is non-empty, and computable in polynomial time, on several restricted preference domains, including voter-interval, candidate-interval, single-peaked and single-crossing profiles. They also exhibited an empty core for strict top-monotonic preferences.

In more general models the answer is known to be negative:

• Fain, Munagala and Shah showed that the core can be empty once voters have arbitrary additive utilities rather than approval utilities.
• Maly showed that in approval-based participatory budgeting the core can be empty for essentially every satisfaction function based on project cost, leaving the cardinality-based utilities of multiwinner approval voting as the remaining open case.

If the integrality requirement is dropped and candidates may be funded fractionally, the picture changes completely: a fractional committee in the core always exists, because a Lindahl equilibrium — a market equilibrium with personalized prices — is a core outcome, as shown by Fain, Goel and Munagala for combinatorial participatory budgeting.

Approximating the core

Because exact core stability is so hard to guarantee, the literature studies two different relaxations. Most existence proofs for approximate cores proceed by constructing such a fractional solution and then rounding it.

Approximating the utility

In the multiplicative relaxation, a deviating group must gain by a factor of α rather than merely gaining. Munagala, Shen, Wang and Wang define a committee W to be in the α-core if there is no group S and set T affordable by S with u_i(T) > α · u_i(W ∪ {q}) for every i ∈ S and every candidate q; the extra candidate q, called an additament, is needed because no purely multiplicative approximation is possible without it. Known results include:

• PAV lies in the 2-core (though it cannot be computed in polynomial time). No rule satisfying the Pigou–Dalton principle of transfers can approximate the core better than a factor of 2. The method of equal shares gives a logarithmic approximation to the core in polynomial time, as shown by Peters and Skowron.
• For participatory budgeting with additive utilities, Peters, Pierczyński and Skowron gave a rule computing a committee in the O(log(u_max/u_min))-core in polynomial time.
• Munagala, Shen, Wang and Wang improved this to a constant. Applying a continuous local-search procedure to the Nash welfare objective under the multilinear extension yields a fractional solution that is almost a 2-approximate fractional core, and iteratively rounding it gives a committee in the 67.37-core for arbitrary monotone submodular utilities, computable in polynomial time. For additive utilities, using an exact fractional core obtained from a Lindahl equilibrium together with dependent rounding improves the factor to 9.27, though without a polynomial-time guarantee.
• Mavrov, Munagala and Shen showed that globally optimizing a smoothed variant of the Nash welfare rule yields a committee in the e-approximate core for XOS utilities, a class containing submodular utilities. Their guarantee holds even when adding arbitrary constraints on the committee.

Constant-factor results of this kind cannot be pushed all the way to α = 1, nor extended to arbitrary preferences:

• For monotone submodular utilities the 1.015-core can already be empty.
• For general monotone utilities the φ(n, m)-core can be empty for every function φ of the numbers of voters and candidates, so no approximation factor depending only on the size of the instance is achievable.

Approximating the entitlement

A second relaxation leaves utilities alone and instead shrinks the budget available to a deviating group. Jiang, Munagala and Wang call a committee of size k c-approximately stable if for every other committee T the fraction of voters strictly preferring T is less than c·|T|/k. The case c = 1 corresponds to ordinary core stability. They proved that a 32-approximately stable committee exists for arbitrary monotone preferences, by rounding a 2-approximately stable lottery. No constant below 2 is achievable, even for ranking preferences. For approval preferences specifically, Gao, Sun and Vondrák brought the constant down to 3.65, by computing a Lindahl equilibrium and sampling from an associated strongly Rayleigh distribution.

Computing the core

Even verifying that a given committee is core-stable is hard. Munagala, Shen and Wang studied this auditing problem for participatory budgeting with additive utilities and showed that it cannot be approximated to within a factor better than 1 + 1/e. On the positive side, a matching logarithmic approximation is obtainable by linear-programming rounding.

Computing a core-stable committee is possible in the cases where one is known to exist: a local-search variant of PAV finds one in polynomial time whenever k ≤ 7. For the fractional relaxation, the main obstacle for a long time was that no polynomial-time algorithm was known for the Lindahl equilibrium, even for unit-size candidates and additive utilities. Kroer and Peters have since given a convex program whose optimal solutions are Lindahl equilibria, including in the setting with funding caps, which makes approximately core-stable fractional outcomes efficiently computable for separable piecewise-linear concave utilities.

Variable number of winners

Freeman, Kahng and Pennock study multiwinner approval voting in which the number of winners is not fixed in advance, but determined by the votes. For example, when selecting candidates for interview, if there are many strong candidates, then the number of candidates selected for interview may be larger. They extend the notion of average satisfaction to this setting.

Divisible committees

Cake sharing is a variant of multiwinner approval voting in which there is a continuum of candidates, represented by a real interval [0, c]. The goal is to select a subset of this interval, with total length at most k, where here k and c can be any real numbers with 0<k<c. Approval voting with mixed goods is an even more general model, in which candidates can be both divisible and indivisible; it generalizes both multiwinner approval voting and cake-sharing.

Party-approval voting

Party-approval voting (also called approval-based apportionment) 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.

Multiwinner approval voting, while less common than standard approval voting, is used in several places.

Block approval voting

• Korean villages used block approval voting for competitive elections following the surrender of Japan, according to observations made by journalist Anna Louise Strong in 1946: "In one village there were twelve candidates, of whom five were to be chosen for the Village Committee. Each voter was given twelve cards, bearing the names of the candidates. He then cast his chosen ones into the white box and the rejected ones into the black."
• Several Swiss cantons elect their government using such methods and so do French cities with population below 1000.
• In 1963, the proportional representation system in East Germany was replaced by a procedure in which the candidates had to receive more than 50% of the votes. Had more candidates than seats in this constituency won the majority, the order of the list would determine who would join the Volkskammer.

Fair approval voting

• The Polkadot blockchain platform uses a variant of Phragmen's voting rules to elect new block validators every day.