Thiele's voting rules

Last updated March 07, 2024

Thiele'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 Thorvald Thiele in Danish in 1895,^[1] and translated to English by Svante Janson in 2016.^[2] They were used in Swedish parliamentary elections to distribute seats within parties, and are still used in city council elections.

Background

In multiwinner approval voting, each voter can vote for one or more candidates, and the goal is to select a fixed number k of winners (where k may be, for example, the number of parliament members). The question is how to determine the set of winners?

The simplest method is multiple non-transferable vote , in which the k candidates with the largest number of approvals are elected. But this method tends to select k candidates of the largest party, leaving the smaller parties with no representation at all.
In the 19th century, there was much discussion regarding election systems that could guarantee proportional representation. One solution, advocated for example by D'Hondt in 1878, was to vote for party-lists rather than individual candidates. This solution is still very common today.

Thiele wanted to keep the vote for individual candidates, so that voters can approve candidates based on their personal merits. However, Thiele's methods can handle more general situations, in which voters may vote for candidates from different parties (in fact, the method ignores the information on which candidate belongs to which party).^[2]^: Sec.1

Thiele's rules for approval ballots

We denote the number of voters by n, the number of candidates by m, and the required number of committee members k. With approval ballots, each voter i has an approval setA_i, containing the subset of candidates that i approves. The goal is: given the sets A_i, select a subset W of winning candidates, such that |W|=k. This subset represents the elected committee.

Thiele's rules are based on the concept of satisfaction function. It is a function f that maps the number of committee-members approved by a voter, to a numeric amount representing the satisfaction of this voter from the committee. So if voter i approves a set of candidates A_i, and the set of elected candidates is W, then the voter's satisfaction is $f(|A_{i}\cap W|)$ . The goal of Thiele's methods is to find a committee W that maximizes the total satisfaction (following the utilitarian rule). The results obviously depend on the function f. Without loss of generality, we can normalize f such that f(0)=0 and f(1)=1. Thiele claims that the selection of f should depend on the purpose of the elections:^[2]^: Sec.4

For electing a government, all members have the same importance, so the identity function f(r)=r for all r makes sense.
For electing an investigation committee, it is important to have diversity, so he suggests f(r)=ind(r≥1), that is: f(r)=1 if r≥1 and 0 otherwise.
For electing a representative body, he suggests f(r)=Harmonic(r) = 1/1 + 1/2 + ... + 1/r.

For each choice of f, Thiele suggested three methods.

Optimization methods: find the committee that maximizes the total satisfaction.

When f(r)=r, Thiele's optimization method is equivalent to the method known as Approval voting (AV), which just picks the k candidates with the largest total number of votes; it is not proportional towards minority groups.
When f(r)=ind(r≥1) Thiele's optimization method is equivalent to the method known as the Chamberlin-Courant voting rule (CC), which aims to maximize the number of citizens who are represented by at least one committee member. It enhances diversity, but it is not proportional towards majority groups.
When f(r)=Harmonic(r), Thiele's optimization method is equivalent to Proportional approval voting (PAV), which was rediscovered by Forest Simmons in 2001.^[3] It is the only choice of f that guarantees justified representation.

In general, solving the global optimization problem is an NP-hard computational problem, except when f(r)=r. Therefore, Thiele suggested two greedy approximation algorithms:

Addition methods: Candidates are elected one by one; at each round, the elected candidate is one that maximizes the increase in the total satisfaction. This is equivalent to weighted voting where each voter i, with r_i approved winners so far, has a weight of f(r_i+1)-f(r_i).

When f(r)=r, the weight of voter i is always 1, regardless of the number of winners he approves so far. So the resulting rule is again approval voting.
When f(r)=Harmonic(r), the weight of voter i is 1/r_i; the resulting method is often called Sequential PAV .
When f(r)=ind(r≥1), the weight of voter i is 1 if he is not represented yet, and 0 if he is already represented. The resulting method is called Greedy Approval Voting^[4] or Greedy Chamberlin-Courant.

Elimination methods work in the opposite direction to addition methods: starting with the set of all m candidates, candidates are removed one by one, until only k remain; at each round, the removed candidate is one that minimizes the decrease in the total satisfaction.

When f(r)=Harmonic(r), the resulting rule is equivalent to a rule called Harmonic Weighting, reinvented as a method for ordering alternatives for display for the electronic voting system LiquidFeedback.^[5]

Thiele's rules for ranked ballots

There is a ranked ballot version for Thiele's addition method. At each round, each voter i, with r_i approved winners so far, has a voting weight of f(r_i+1)-f(r_i). Each voter's weight is counted only for his top remaining candidate. The candidate with the highest total weight is elected.

It was proposed in the Swedish parliament in 1912 and rejected; but was later adopted for elections inside city and county councils, and is still used for that purpose.^[2]^: Sec.10

Properties

Homogeneity

For each possible ballot b, let v_b be the number of voters who voted exactly b (for example: approved exactly the same set of candidates). Let p_b be fraction of voters who voted exactly b (= v_b / the total number of votes). A voting method is called homogeneous if it depends only on the fractions p_b. So if the numbers of votes are all multiplied by the same constant, the method returns the same outcome. Thiele's methods are homogeneous in that sense.^[2]^: Rem.2.1

Monotonicity

Thiele's addition method satisfies a property known as house monotonicity: when the number of committee members increases, all the previously elected members are still elected. This follows immediately from the method description. Thiele's elimination method is house-monotone too. But Thiele's optimization method generally violates house monotonicity, as noted by Thiele himself. In fact, Thiele's optimization method satisfies house-monotonicity only for the (normalized) satisfaction function f(r)=r. Here is an example:^[2]^: Sec.5.1

Assume first that f(2)<2. Suppose there are three candidates x,y,z and four citizens with approval sets xy, xz, y, z. When k=1, all committees {x},{y},{z} have the same total satisfaction: 2f(1)+2f(0) = 2+0 = 2 (by normalization) so the committee is elected by tie-breaking; suppose {x} is elected. Now suppose k increases to 2. The satisfaction of {x,y} and of {x,z} is f(2)+2f(1)+f(0) = f(2)+2; the satisfaction of {y,z} is 4f(1) = 4. If f(2)<2, then {y,z} is elected, which violates house-monotonicity.
Assume next that f(2)>2. Suppose there are three candidates x,y,z and two citizens with approval sets x and yz. When k=1, all committees {x},{y},{z} have the same total satisfaction 1; suppose {x} is elected. Now suppose k increases to 2. The satisfaction of {x,y} and of {x,z} is 2f(1) = 2; the satisfaction of {y,z} is f(2). If f(2)>2, then {y,z} is elected, which violates house-monotonicity.
Therefore, f(2)=2 must hold for house-monotonicity to hold. Using similar arguments, we can prove that f(r)=r for all r.

This also implies that Thiele's optimization method coincides with the addition method iff f(r)=r.^[2]^: Rem.5.2

Proportionality

Lackner and Skowron^[6] show that Thiele's voting rules can be used to interpolate between regressive and degressive proportionality: PAV is proportional; rules in which the slope of the score function is above that of PAV satisfy regressive proportionality; and rules in which the slope of the score function is below that of PAV satisfy degressive proportionality. Moreover,^[7] If the satisfaction-score of the i-th approved candidate is (1/p)ⁱ, for various values of p, we get the entire spectrum between CC and AV.

Related Research Articles

Score voting or range voting is an electoral system for single-seat elections, in which voters give each candidate a score, the scores are added, and the candidate with the highest total is elected. It has been described by various other names including evaluative voting, utilitarian voting, interval measure voting, point-sum voting, ratings summation, 0-99 voting, and average voting. It is a type of cardinal voting electoral system that aims to approximate the utilitarian social choice rule.

Arrow's impossibility theorem, the general possibility theorem or Arrow's paradox is an impossibility theorem in social choice theory that states that when voters have three or more distinct alternatives (options), no ranked voting electoral system can convert the ranked preferences of individuals into a community-wide ranking while also meeting the specified set of criteria: unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives. The theorem is often cited in discussions of voting theory as it is further interpreted by the Gibbard–Satterthwaite theorem. The theorem is named after economist and Nobel laureate Kenneth Arrow, who demonstrated the theorem in his doctoral thesis and popularized it in his 1951 book Social Choice and Individual Values. The original paper was titled "A Difficulty in the Concept of Social Welfare".

The independence of irrelevant alternatives (IIA), also known as binary independence or the independence axiom, is an axiom of decision theory and the social sciences that describes a necessary condition for rational behavior. The axiom says that adding "pointless" (rejected) options should not affect behavior. This is sometimes explained with a short story by philosopher Sidney Morgenbesser:

Morgenbesser, ordering dessert, is told by a waitress that he can choose between blueberry or apple pie. He orders apple. Soon the waitress comes back and explains cherry pie is also an option. Morgenbesser replies "In that case, I'll have blueberry."

The Schulze method is an electoral system developed in 1997 by Markus Schulze that selects a single winner using votes that express preferences. The method can also be used to create a sorted list of winners. The Schulze method is also known as Schwartz Sequential dropping (SSD), cloneproof Schwartz sequential dropping (CSSD), the beatpath method, beatpath winner, path voting, and path winner. The Schulze method is a Condorcet method, which means that if there is a candidate who is preferred by a majority over every other candidate in pairwise comparisons, then this candidate will be the winner when the Schulze method is applied.

Proportionality for solid coalitions (PSC) is a fairness criterion for ranked voting systems. It is an adaptation of the proportional representation criterion to voting systems in which there are no parties, the voters can vote directly for candidates, and can rank the candidates in any way they want. This criterion was proposed by the British philosopher and logician Michael Dummett.

Satisfaction approval voting (SAV), also known as equal and even cumulative voting, is an electoral system that is a form of multiwinner approval voting as well as a form of cumulative voting. In the academic literature, the rule was studied by Steven Brams and Marc Kilgour in 2010. In this system, voters may approve a number of candidates, and each approved candidate receives an equal fraction of the vote. For example, if a voter approves 4 candidates, then each candidate receives a 0.25 fractional vote. The election winners are those candidates that receive the highest fractional vote count.

Proportional approval voting (PAV) is a proportional electoral system for multiwinner elections. It is a multiwinner approval method that extends the highest averages 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.

Sequential proportional approval voting (SPAV) or reweighted approval voting (RAV) is an electoral system that extends the concept of approval voting to a multiple winner election. It is a simplified version of proportional approval voting. It is a special case of Thiele's voting rules, proposed by Danish statistician Thorvald N. Thiele in the early 1900s. It was used in Sweden for a short period from 1909-1921, and was replaced by a cruder "party-list" style system as it was easier to calculate.

STAR voting is an electoral system for single-seat elections. Variations also exist for multi-winner and proportional representation elections. The name stands for "Score then Automatic Runoff", referring to the fact that this system is a combination of score voting, to pick two finalists with the highest total scores, followed by an "automatic runoff" in which the finalist who is preferred on more ballots wins. It is a type of cardinal voting electoral system.

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.

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.

Multiwinner approval voting, also called approval-based committee (ABC) voting, is a multi-winner electoral system that uses approval ballots. Each voter may select ("approve") any number of candidates, and multiple candidates are elected. The number of elected candidates is usually fixed in advance. For example, it can be the number of seats in a country's parliament, or the required number of members in a committee.

Multiwinner voting, also called multiple-winner elections or committee voting or committee elections, is an electoral system in which multiple candidates are elected. The number of elected candidates is usually fixed in advance. For example, it can be the number of seats in a country's parliament, or the required number of members in a committee.

House monotonicity is a property of apportionment methods. These are methods for allocating seats in a parliament among federal states. The property says that, if the number of seats in the "house" increases, and the method is re-activated, then no state should have fewer seats than it previously had. A method that fails to satisfy house-monotonicity is said to have the Alabama paradox.

Fractional approval voting is an electoral system using approval ballots, in which the outcome is fractional: for each alternative j there is a fraction p_j between 0 and 1, such that the sum of p_j 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 p_j can be interpreted in various ways, depending on the setting. Examples are:

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.

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.

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.

Fully proportional representation(FPR) is a property of multiwinner voting systems. It extends the property of proportional representation (PR) by requiring that the representation be based on the entire preferences of the voters, rather than on their first choice. Moreover, the requirement combines PR with the requirement of accountability - each voter knows exactly which elected candidate represents him, and each candidate knows exactly which voters he represents.

References

↑ Thorvald N. Thiele. "Om Flerfoldsvalg." Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger 1895, København, 1895–1896, 415–441.
1 2 3 4 5 6 7 Janson, Svante (2018-10-12). "Phragmén's and Thiele's election methods". arXiv: 1611.08826 [math.HO].
↑ Kilgour, D. Marc (2010). "Approval Balloting for Multi-winner Elections". In Jean-François Laslier; M. Remzi Sanver (eds.). Handbook on Approval Voting. Springer. pp. 105–124. ISBN 978-3-642-02839-7.
↑ Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017). "Justified representation in approval-based committee voting". Social Choice and Welfare. 48 (2): 461–485. arXiv: 1407.8269 . doi:10.1007/s00355-016-1019-3. S2CID 8564247.
↑ "The principles of Liquid Feedback". scholar.google.com. Retrieved 2023-11-22.
↑ Lackner, Martin; Skowron, Piotr (2018-06-11). "Consistent Approval-Based Multi-Winner Rules". Proceedings of the 2018 ACM Conference on Economics and Computation. EC '18. New York, NY, USA: Association for Computing Machinery. pp. 47–48. arXiv: 1704.02453 . doi:10.1145/3219166.3219170. ISBN 978-1-4503-5829-3.
↑ Lackner, Martin; Skowron, Piotr (2020-11-01). "Utilitarian welfare and representation guarantees of approval-based multiwinner rules". Artificial Intelligence. 288: 103366. arXiv: 1801.01527 . doi:10.1016/j.artint.2020.103366. ISSN 0004-3702. S2CID 221377362.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Thorvald N. Thiele. "Om Flerfoldsvalg." Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger 1895, København, 1895–1896, 415–441.

[:0-2] 1 2 3 4 5 6 7 Janson, Svante (2018-10-12). "Phragmén's and Thiele's election methods". arXiv: 1611.08826 [math.HO].

[Kilgour2010-3] Kilgour, D. Marc (2010). "Approval Balloting for Multi-winner Elections". In Jean-François Laslier; M. Remzi Sanver (eds.). Handbook on Approval Voting. Springer. pp. 105–124. ISBN 978-3-642-02839-7.

[:03-4] Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017). "Justified representation in approval-based committee voting". Social Choice and Welfare. 48 (2): 461–485. arXiv: 1407.8269 . doi:10.1007/s00355-016-1019-3. S2CID 8564247.

[5] "The principles of Liquid Feedback". scholar.google.com. Retrieved 2023-11-22.

[6] Lackner, Martin; Skowron, Piotr (2018-06-11). "Consistent Approval-Based Multi-Winner Rules". Proceedings of the 2018 ACM Conference on Economics and Computation. EC '18. New York, NY, USA: Association for Computing Machinery. pp. 47–48. arXiv: 1704.02453 . doi:10.1145/3219166.3219170. ISBN 978-1-4503-5829-3.

[7] Lackner, Martin; Skowron, Piotr (2020-11-01). "Utilitarian welfare and representation guarantees of approval-based multiwinner rules". Artificial Intelligence. 288: 103366. arXiv: 1801.01527 . doi:10.1016/j.artint.2020.103366. ISSN 0004-3702. S2CID 221377362.

[1]

[2]

[3]

[4]

[5]

[6]

[7]