Expanding approvals rule

An expanding approvals rule (EAR) is a rule for multi-winner elections, which allows agents to express weak ordinal preferences (i.e., ranking with indifferences), and guarantees a form of proportional representation called proportionality for solid coalitions. The family of EAR was presented by Aziz and Lee.

In general, the EAR algorithm works as follows. Let n denote the number of voters, and k the number of seats to be filled. Initially, each voter is given 1 unit of virtual money. Groups of voters can use their virtual money to "buy" candidates, where the "price" of each candidate is $n/k$ (though the divisor can be slightly different; see highest averages method). The EAR goes rank by rank, starting at rank 1 which corresponds to the top candidates of the voters, and increasing the rank in each iteration. (This is where the term "expanding approvals" comes from: as the rank increases, the number of approved candidates expands.) For each rank r:

1. EAR checks if there is a candidate who can be afforded by all voters who rank this candidate r-th or better. If there is such a candidate, EAR selects one such candidate c (there are different variants regarding how to select this candidate), and adds c to the committee.
2. The "price" of n/k is deducted from the balance of voters who rank c r-th or better (there are different variants regarding how exactly the price is split among them).

Properties

Aziz and Lee prove that EAR satisfies generalized proportionality for solid coalitions (GPSC): a property for ordinal weak preferences that generalizes both proportionality for solid coalitions (for strict preferences) and proportional justified representation (for dichotomous preferences). Further, EAR can be computed in polynomial time and satisfies several weak candidate monotonicity properties.

Extensions

Aziz and Lee extended EAR to the setting of combinatorial participatory budgeting.

Related rules

The method of equal shares (MES) can be seen as a special case of EAR, in which, in step 1, the elected candidate is a candidate that can be purchased in the smallest price (in general, it is the candidate supported by the largest number of voters with remaining funds), and in step 2, the price is deducted as equally as possible (those who have insufficient budget pay all their remaining budget, and the others pay equally).

Single transferable vote (STV) can also be seen as a variant of EAR, in which voters always approve only their top candidate (r=1); however, if no candidate can be "purchased" by voters ranking it first, the candidate whose supporters have the fewest leftover votes is removed (this brings a new candidate to the top position of these voters). Like EAR, STV satisfies proportionality for solid coalitions. However, EAR allows weak rankings, whereas STV works only with strict rankings. Moreover, EAR has better candidate monotonicity properties. This addressed an open question by Woodall, who asked if there are rules with the same political properties as STV, which are more monotonic.