An expanding approvals rule (EAR) is a rule for multi-winner elections, which allogs 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.[1][2]

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 (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 candidates who rank c r-th or better (there are different variants regarding how exactly the price is split among them).

Properties

Aziz and Lee[1] prove that EAR satisfies several important properties:

Extensions

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

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).[3]

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, a candidate whose supporters have the least amount of budget 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,[4] who asked if there are rules with the same political properties as STV, which are more monotonic.

References

  1. 1 2 Aziz, Haris; Lee, Barton E. (2020-01-01). "The expanding approvals rule: improving proportional representation and monotonicity". Social Choice and Welfare. 54 (1): 1–45. arXiv:1708.07580. doi:10.1007/s00355-019-01208-3. ISSN 1432-217X.
  2. 1 2 Aziz, Haris; Lee, Barton E. (2021-05-18). "Proportionally Representative Participatory Budgeting with Ordinal Preferences". Proceedings of the AAAI Conference on Artificial Intelligence. 35 (6): 5110–5118. arXiv:1911.00864. doi:10.1609/aaai.v35i6.16646. ISSN 2374-3468.
  3. Brill, Markus; Peters, Jannik (2023). "Robust and Verifiable Proportionality Axioms for Multiwinner Voting". arXiv:2302.01989 [cs.GT].
  4. Woodall, Douglas R. (1997-06-27). "Monotonicity of single-seat preferential election rules". Discrete Applied Mathematics. 77 (1): 81–98. CiteSeerX 10.1.1.545.510. doi:10.1016/S0166-218X(96)00100-X. ISSN 0166-218X.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.