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
Proportional representation (PR) refers to any electoral system under which subgroups of an electorate are reflected proportionately in the elected body. The concept applies mainly to political divisions (Political party, political parties) amon ...
. They were published by
Thorvald Thiele in Danish in 1895, and translated to English by
Svante Janson in 2016.
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
Plurality block voting is a type of block voting method for multi-winner elections. Each voter may cast as many votes as the number of seats to be filled. The candidates with the most votes are elected. The usual result when the candidates div ...
'', 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
Proportional representation (PR) refers to any electoral system under which subgroups of an electorate are reflected proportionately in the elected body. The concept applies mainly to political divisions (Political party, political parties) amon ...
. 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).
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 ballot An approval ballot, also called an unordered ballot, is a ballot in which a voter may vote for any number of candidates simultaneously, rather than for just one candidate. Candidates that are selected in a voter's ballot are said to be ''approved'' ...
s, 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
. The goal of Thiele's methods is to find a committee ''W'' that maximizes the total satisfaction (following the
utilitarian rule
In social choice theory, social choice and operations research, the utilitarian rule (also called the max-sum rule) is a Social welfare function, rule saying that, among all possible alternatives, society should pick the alternative which maximize ...
). 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
Ind or IND may refer to:
General
* Independent (politician), a politician not affiliated to any political party
* Independent station, used within television program listings and the television industry for a station that is not affiliated with ...
(r≥1), that is: f''(r)=''1 if r≥1 and 0 otherwise.
* For electing a representative body, he suggests f(''r'')=
Harmonic
In physics, acoustics, and telecommunications, a harmonic is a sinusoidal wave with a frequency that is a positive integer multiple of the ''fundamental frequency'' of a periodic signal. The fundamental frequency is also called the ''1st har ...
(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
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
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
Weighted voting are voting rules that grant some voters a greater influence than others (which contrasts with rules that assign every voter an equal vote). Examples include publicly-traded companies (which typically grant stockholders one vo ...
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
Approval voting is a single-winner rated voting system where voters can approve of all the candidates as they like instead of Plurality voting, choosing one. The method is designed to eliminate vote-splitting while keeping election administration ...
.
* 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
A ranking is a relationship between a set of items, often recorded in a list, such that, for any two items, the first is either "ranked higher than", "ranked lower than", or "ranked equal to" the second. In mathematics, this is known as a weak ...
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 ,, have the same total satisfaction: 2f(1)+2f(0) = 2+0 = 2 (by normalization) so the committee is elected by tie-breaking; suppose is elected. Now suppose ''k'' increases to 2. The satisfaction of and of is f(2)+2f(1)+f(0) = f(2)+2; the satisfaction of is 4f(1) = 4. If f(2)<2, then 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 ,, have the same total satisfaction 1; suppose is elected. Now suppose ''k'' increases to 2. The satisfaction of and of is 2f(1) = 2; the satisfaction of is f(2). If f(2)>2, then 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'')
''i'', for various values of ''p'', we get the entire spectrum between CC and AV.
[{{Cite journal , last1=Lackner , first1=Martin , last2=Skowron , first2=Piotr , date=2020-11-01 , title=Utilitarian welfare and representation guarantees of approval-based multiwinner rules , url=https://www.sciencedirect.com/science/article/pii/S0004370220301168 , journal=Artificial Intelligence , volume=288 , pages=103366 , doi=10.1016/j.artint.2020.103366 , issn=0004-3702, arxiv=1801.01527 , s2cid=221377362 ]
See also
*
Phragmen's voting rules
References
Multi-winner electoral systems
Preferential electoral systems
Approval voting