Expanding approvals rule


An expanding approvals rule is a rule for multi-winner elections, which allows agents to express weak ordinal preferences, 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 . 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. 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, 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.

    Properties

Aziz and Lee prove that EAR satisfies generalized proportionality for solid coalitions : a property for ordinal weak preferences that generalizes both proportionality for solid coalitions and proportional justified representation. 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 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, and in step 2, the price is deducted as equally as possible.
Single transferable vote can also be seen as a variant of EAR, in which voters always approve only their top candidate ; however, if no candidate can be "purchased" by voters ranking it first, the candidate whose supporters have the fewest leftover votes is removed. 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.