Phragmen's voting rules

From Wikipedia, the free encyclopedia

Phragmen's voting rules are multiwinner voting methods that guarantee proportional representation. They were published by Lars Edvard Phragmén in French and Swedish between 1893 and 1899,[1] and translated to English by Svante Janson in 2016.[2] There are two kinds of Phragmen rules: rules using approval ballots (that is, multiwinner approval voting), and rules using ranked ballots (that is, multiwinner ranked voting).

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. But Phragmen wanted to keep the vote for individual candidates, so that voters can approve candidates based on their personal merits. In the special case in which each voter approves all and only the candidates of a single party, Phragmen's methods give the same results as D'Hondt's method.[2]: Sec.11  However, Phragmen's method 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).

Phragmen's method for approval ballots[]

Phragmen's method for unordered (approval) ballots can be presented in several equivalent ways.[2]: Sec.3  Here is one description.

Each voter has identical voting-power, denoted by t. Each candidate needs a total voting-power of 1 in order to be elected. For each elected candidate j, the required voting-power of 1 is deducted equally from all voters who approved j. The winners are elected one by one: the next winner is the one who requires the smallest t in order to attain a total voting-power of 1.

Example[]

There are 3 seats and 6 candidates, denoted by A, B, C, P, Q, R. The ballots are: 1034 vote for ABC, 519 vote for PQR, 90 vote for ABQ, 47 vote for APQ. The winners are elected sequentially as follows:

  • First, we compute for each candidate the required value of t so that the candidate can get a total voting-power of 1. This value is 1/1171 for A (since A appears in 1171 ballots); 1/1124 for B; 1/1034 for C; 1/566 for P; 1/656 for Q; 1/519 for R. Thus, A is elected first.
  • Now, we re-compute for each candidate the required value of t so that the candidate can get a total voting-power of 1, keeping in mind to deduct 1/1171 from each voter who approved A. The required value for B is 1/1124+1/1171, since there are 1124 voters who approve B, and all of them already approved A. Similarly, the required value for C is 1/1034+1/1171; for Q it is 1/656+(137/656)/1171, since 137 out of 656 voters for Q already voted for A; for P it is 1/566+(47/566)/1171; and for R it is 1/519. The value is smallest for Q, so it is elected as the second winner.
  • Similarly, B is elected as the third winner.

Properties[]

Homogeneity[]

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

Independence of unelected candidates[]

If any number of candidates is added to a ballot, but none of them is elected, then the outcome does not change.[2]: Sec.6  This reduces the incentive for strategic voting.

Monotonicity[]

Since Phragmen's methods assign seats one-by-one, they satisfy the house monotonicity property: when more seats are added, the set of winners increases (no winner loses a seat).[2]: Sec.5 

They also satisfy the following monotonicity criterion:[2]: Sec.14 

  • For Phragmen's approval-ballot method: if some candidate C is elected, and then candidate C earns some approvals either from new voters who vote for C, or from existing voters who add C to their ballots, and no other changes occur, then C is still elected. However, this monotonicity does not hold for pairs of candidates, even if they always appear together. For example, it is possible that candidates C, D appear together in all ballots and get two seats, but if another ballot is added for C, D, then they get together only one seat (so one of them loses a seat).[2]: Ex.14.4, 14.5 
  • For Phragmen's ranked-ballot method: if some candidate C is elected, and then candidate C is promoted in some of the ballots, or earns some new votes, and no other changes occur, then C is still elected. However, if some other changes occur simultaneously, then C might lose his seat. For example, it is possible that some voters change their mind, and instead of voting for A and B, they vote for C and D, and this change causes C to lose his seat.[2]: Ex.13.16 

Consistency[]

Phragmen's methods do not satsify the consistency criterion. Moreover, they do not ignore full ballots: adding voters who vote for all candidates (and thus are totally indifferent) might affect the outcome.[2]: Ex.15.4, 15.6, 15.8, 15.9 

Special cases[]

When there is a single seat (k=1):

  • Phragmen's approval-ballot method reduces to approval voting - it always selects the candidate with the largest number of approvals.
  • Phragmen's ranked-ballot method reduces to plurality voting - it always selects the candidate ranked first by the largest number of voters.

Further reading[]

More information on Phragmen's methods is available at.[3][4]

Implementations[]

  • Some of Phragmen's voting rules are implemented in the Python package abcvoting.

Both the simple and complicated versions[5][6] are used in the substrate of the cryptocurrency Polkadot.[7]

References[]

  1. ^ 1. "Om proportionella val." (Summary of a public lecture). Stockholms Dagblad, 14 March 1893. 2. "Sur une m ́ethode nouvelle pour r ́ealiser, dansles ́elections, la repr ́esentation proportionelle des partis". ̈Ofversigt avKongl. Vetenskaps-Akademiens F ̈orhandlingar 1894, N:o 3, Stockholm,133–137. 3. "Proportionella val. En valteknisk studie." Svenskasp ̈orsm ̊al 25, Lars H ̈okersbergs f ̈orlag, Stockholm, 1895. 4. "Sur la th ́eorie des ́elections multiples", ̈Ofversigt avKongl. Vetenskaps-Akademiens F ̈orhandlingar 1896, N:o 3, Stockholm,181–191. 5. "Till fr ̊agan om en proportionell valmetod." Statsvetenskaplig Tidskrift2(1899), nr 2, 297–305. http://cts.lub.lu.se/ojs/index.php/st/article/view/1949
  2. ^ a b c d e f g h i j Janson, Svante (2018-10-12). "Phragmen's and Thiele's election methods". arXiv:1611.08826 [math.HO].
  3. ^ Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (2017-02-10). "Phragmén's Voting Methods and Justified Representation". Proceedings of the AAAI Conference on Artificial Intelligence. 31 (1). ISSN 2374-3468.
  4. ^ Peters, Dominik; Skowron, Piotr (2020-07-13). "Proportionality and the Limits of Welfarism". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20. New York, NY, USA: Association for Computing Machinery: 793–794. arXiv:1911.11747. doi:10.1145/3391403.3399465. ISBN 978-1-4503-7975-5. S2CID 208291203.
  5. ^ "consensus/NPoS at master · w3f/consensus". GitHub. 17 October 2021.
  6. ^ https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/download/14757/13791
  7. ^ "Sequential Phragmén Method · Polkadot Wiki". wiki.polkadot.network.
Retrieved from ""