Thiele's voting rules

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 set A_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 ${\displaystyle 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:

• 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. 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 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.

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.

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.

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:

• 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.

Proportionality

Lackner and Skowron 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, 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.