Expanding approvals rule

Last updated

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. [1] [2]

Contents

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 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 [1] 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 [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, 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, [4] who asked if there are rules with the same political properties as STV, which are more monotonic.

Related Research Articles

<span class="mw-page-title-main">Negative responsiveness paradox</span> Property of electoral systems

In social choice, the negative responsiveness, perversity, or additional support paradox is a pathological behavior of some voting rules, where a candidate loses as a result of having "too much support" from some voters, or wins because they had "too much opposition". In other words, increasing (decreasing) a candidate's ranking or rating causes that candidate to lose (win). Electoral systems that do not exhibit perversity are said to satisfy the positive response or monotonicitycriterion.

<span class="mw-page-title-main">Random ballot</span> Electoral system with lottery among ballots

A random ballot or random dictatorship is a randomized electoral system where the election is decided on the basis of a single randomly-selected ballot. A closely-related variant is called random serialdictatorship, which repeats the procedure and draws another ballot if multiple candidates are tied on the first ballot.

<span class="mw-page-title-main">No-show paradox</span> When voting for a candidate makes them lose

In social choice, a no-show paradox is a pathology in some voting rules, where a candidate loses an election as a result of having too many supporters. More formally, a no-show paradox occurs when adding voters who prefer Alice to Bob causes Alice to lose the election to Bob. Voting systems without the no-show paradox are said to satisfy the participation criterion.

Later-no-harm is a property of some ranked-choice voting systems, first described by Douglas Woodall. In later-no-harm systems, increasing the rating or rank of a candidate ranked below the winner of an election cannot cause a higher-ranked candidate to lose. It is a common property in the plurality-rule family of voting systems.

<span class="mw-page-title-main">Proportionality for solid coalitions</span> Criterion for proportional representation

Proportionality for solid coalitions (PSC) is a criterion of proportionality for ranked voting systems. It is an adaptation of the quota rule to voting systems in which there are no official party lists, and voters can directly support candidates. The criterion was first proposed by the British philosopher and logician Michael Dummett.

<span class="mw-page-title-main">Schulze STV</span> Proportional-representation ranked voting system

Schulze STV is a draft single transferable vote (STV) ranked voting system designed to achieve proportional representation. It was invented by Markus Schulze, who developed the Schulze method for resolving ties using a Condorcet method. Schulze STV is similar to CPO-STV in that it compares possible winning candidate pairs and selects the Condorcet winner. It is not used in parliamentary elections.

<span class="mw-page-title-main">Instant-runoff voting</span> Single-winner ranked-choice electoral system

Instant-runoff voting (IRV), is a single-winner, multi-round elimination rule that uses ranked voting to simulate a series of runoff elections. In each round, the last-place finisher according to a plurality vote is eliminated, and the votes supporting the eliminated choice are transferred to their next available preference until one of the options reaches a majority of the remaining votes. Instant runoff falls under the plurality-with-elimination family of voting methods, and is thus closely related to rules like the exhaustive ballot and two-round runoff system

There are a number of different criteria which can be used for voting systems in an election, including the following

<span class="mw-page-title-main">Fair cake-cutting</span> Fair division problem

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

<span class="mw-page-title-main">Proportional approval voting</span> Multiple-winner electoral system

Proportional approval voting (PAV) is a proportional electoral system for multiwinner elections. It is a multiwinner approval method that extends the D'Hondt method of apportionment commonly used to calculate apportionments for party-list proportional representation. However, PAV allows voters to support only the candidates they approve of, rather than being forced to approve or reject all candidates on a given party list.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Combinatorial participatory budgeting, also called indivisible participatory budgeting or budgeted social choice, is a problem in social choice. There are several candidate projects, each of which has a fixed costs. There is a fixed budget, that cannot cover all these projects. Each voter has different preferences regarding these projects. The goal is to find a budget-allocation - a subset of the projects, with total cost at most the budget, that will be funded. Combinatorial participatory budgeting is the most common form of participatory budgeting.

<span class="mw-page-title-main">Justified representation</span> Criterion for evaluating fairness of electoral systems

Justified representation (JR) is a criterion of fairness in multiwinner approval voting. It can be seen as an adaptation of the proportional representation criterion to approval voting.

<span class="mw-page-title-main">Multiwinner approval voting</span> Family of proportional election methods

Multiwinner approval voting, sometimes also called approval-based committee (ABC) voting, refers to a family of multi-winner electoral systems that use approval ballots. Each voter may select ("approve") any number of candidates, and multiple candidates are elected.

<span class="mw-page-title-main">Multiwinner voting</span> Process of electing more than one winner in the same election / district

Multiwinner, at-large, or committeevoting refers to electoral systems that elect several candidates at once. Such methods can be used to elect parliaments or committees.

<span class="mw-page-title-main">Fractional social choice</span>

Fractional, stochastic, or weighted social choice is a branch of social choice theory in which the collective decision is not a single alternative, but rather a weighted sum of two or more alternatives. For example, if society has to choose between three candidates, then in standard social choice exactly one of these candidates is chosen. By contrast, in fractional social choice it is possible to choose any linear combination of these, e.g. "2/3 of A and 1/3 of B".

<span class="mw-page-title-main">Fractional approval voting</span>

In fractional social choice, fractional approval voting refers to a class of electoral systems using approval ballots, in which the outcome is fractional: for each alternative j there is a fraction pj between 0 and 1, such that the sum of pj is 1. It can be seen as a generalization of approval voting: in the latter, one candidate wins and the other candidates lose. The fractions pj can be interpreted in various ways, depending on the setting. Examples are:

<span class="mw-page-title-main">Phragmen's voting rules</span> Method of counting votes and determining results

Phragmén's voting rules are rules for multiwinner voting. They allow voters to vote for individual candidates rather than parties, but still guarantee proportional representation. They were published by Lars Edvard Phragmén in French and Swedish between 1893 and 1899, and translated to English by Svante Janson in 2016.

<span class="mw-page-title-main">Method of equal shares</span> Method of counting ballots following elections

The method of equal shares is a proportional method of counting ballots that applies to participatory budgeting, to committee elections, and to simultaneous public decisions. It can be used when the voters vote via approval ballots, ranked ballots or cardinal ballots. It works by dividing the available budget into equal parts that are assigned to each voter. The method is only allowed to use the budget share of a voter to implement projects that the voter voted for. It then repeatedly finds projects that can be afforded using the budget shares of the supporting voters. In contexts other than participatory budgeting, the method works by equally dividing an abstract budget of "voting power".

Multi-issue voting is a setting in which several issues have to be decided by voting. Multi-issue voting raises several considerations, that are not relevant in single-issue voting.

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.