Phragmén's voting rules are rules for multiwinner voting. They allow voters to vote for individual candidates rather than parties, while still guaranteeing proportional representation. They produce not only a set of candidates, but also a ranking on the set of candidates; hence, they are particularly useful for primary elections in party-list systems, where a party has to determine an ordered list of its candidates.
Phragmen's voting rules were published by Lars Edvard Phragmén in French and Swedish between 1893 and 1899,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 and translated to English by Svante Janson in 2016.
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. Phragmén 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, Phragmén's methods give the same results as D'Hondt's method. However, Phragmén'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).
Sequential Phragmén's rule for approval ballots Phragmen's original method, nowadays called Seq-Phragmen, can be presented in two equivalent ways.
Load balancing Each elected candidate creates a "load" of 1 unit. The load of a candidate must be born by voters who support him. The goal is to find a committee for which the load can be divided among the voters in the most "balanced" way. This means that it aims to minimize the maximum load, and subject to that the second-maximum load, etc. (using lexicographic max-min optimization). The load-balancing is done sequentially, in each round.
Phragmen illustrated his method by representing each voter as a vessel. The already-elected candidates are represented by water in the vessels. To elect another candidate, 1 liter of water has to be poured into the vessels corresponding to voters who voter for that candidate. The water should be distributed such that the maximum height of the water is as small as possible.
Virtual money Seq-Phragmen can alternatively be described as the following continuous process:
Each voter starts with 0 virtual money, and receives money in a constant rate of 1 per day. At each time t, we define a not-yet-elected candidate x as affordable if the total money held by voters who approve x is at least 1. At the first time in which some candidate is affordable, we choose one affordable candidate y arbitrarily. We add y to the committee, and reset the virtual money of voters who approve y (as they have now "used" their virtual money to fund y). Voters keep earning virtual money and funding candidates until all k committee members are elected.
Examples
Party-list The following simple example resembles party-list voting. There are k=6 seats and 9 candidates, denoted a,b,c,d,e,f,g,h,i. There are 63 voters with the following preferences: 31 voters approve a,b,c; 21 voters approve d,e,f; and 11 voters approve g,h,i.
Round 1 Let candidates be given a score equal to the reciprocal of the number of approvers. We get the following: +CandidateScoreabcdefghi We select the candidate with the lowest score. In this case, it's tied between a, b, and c. Let's suppose that a was selected.
Round 2 Now, candidate scores are increased by the product of 1/31 (a's score) and the proportion of approvers who also approve of a. CandidateDerivationScoreb1/31+1(1/31)c1/31+1(1/31)d1/21+0(1/31)e1/21+0(1/31)f1/21+0(1/31)g1/11+0(1/31)h1/11+0(1/31)i1/11+0(1/31) We select the candidate with the lowest score. In this case, it's tied between d, e, and f. Let's suppose that d was selected.
Round 3 Now, candidate scores are increased by the sum of the product of 1/31 (a's score) and the proportion of approvers whose 'most recent' approval was a, and the product of 1/21 (d's score) and the proportion of approvers whose 'most recent' approval was d. CandidateDerivationScoreb1/31+1(1/31)+0(1/21)c1/31+1(1/31)+0(1/21)e1/21+0(1/31)+1(1/21)f1/21+0(1/31)+1(1/21)g1/11+0(1/31)+0(1/21)h1/11+0(1/31)+0(1/21)i1/11+0(1/31)+0(1/21) We select the candidate with the lowest score. In this case, it's tied between b and c. Let's suppose that b was selected.
Round 4 Now, candidate scores are increased by the sum of the product of 1/31 (a's score) and the proportion of approvers whose 'most recent' approval was a, and the sum of the product of 1/21 (d's score) and the proportion of approvers whose 'most recent' approval was d, and the product of 2/31 (b's score) and the proportion of approvers whose 'most recent' approval was b. CandidateDerivationScorec1/31+0(1/31)+0(1/21)+1(2/31)e1/21+0(1/31)+1(1/21)+0(2/31)f1/21+0(1/31)+1(1/21)+0(2/31)g1/11+0(1/31)+0(1/21)+0(2/31)h1/11+0(1/31)+0(1/21)+0(2/31)i1/11+0(1/31)+0(1/21)+0(2/31) We select the candidate with the lowest score. In this case, it's tied between g, h, and i. Let's suppose that g was selected.
Round 5 CandidateDerivationScorec1/31+0(1/31)+0(1/21)+1(2/31)+0(1/11)e1/21+0(1/31)+1(1/21)+0(2/31)+0(1/11)f1/21+0(1/31)+1(1/21)+0(2/31)+0(1/11)h1/11+0(1/31)+0(1/21)+0(2/31)+1(1/11)i1/11+0(1/31)+0(1/21)+0(2/31)+1(1/11) We select the candidate with the lowest score. In this case, it's tied between e and f. Let's suppose that e was selected.
Round 6 CandidateDerivationScorec1/31+0(1/31)+0(1/21)+1(2/31)+0(1/11)+0(2/21)f1/21+0(1/31)+0(1/21)+0(2/31)+0(1/11)+1(2/21)h1/11+0(1/31)+0(1/21)+0(2/31)+1(1/11)+0(2/21)i1/11+0(1/31)+0(1/21)+0(2/31)+1(1/11)+0(2/21) We select the candidate with the lowest score, which is c.
Voters start earning money at a fixed rate of 1 per day. After 1/31 or ~0.0323 days, the 31 abc voters have 0.0323 each, so together they can fund one of their approved candidates. One of a,b,c is chosen arbitrarily; suppose it is a. After 1/21 or ~0.0476 days, the 31 abc voters have only ~0.015 each, but the 21 def voters have 0.0476 each, so together they can fund one of their approved candidates. One of d,e,f is chosen arbitrarily; suppose it is d. After ~0.0645 days, the abc voters again have 0.0323 each, so they buy another one of their approved candidates, say b. After 1/11 or ~0.0909 days, the ghi voters have 0.0909 each, so together they can fund one of their approved candidates, say g (at this point, the abc voters have only 0.0264 each and the def voters have 0.0434 each, so none of them can by another candidate). After 0.0952 days, the def voters again have 0.0476 each, so they can buy another candidate, say e. After 0.0968 days, the abc voters again have 0.0323 each, so they can buy another candidate, say c. The final committee is a,b,c; d,e; g. Note that each "party" is represented approximately in proportion to its size: 3 candidates for 31 voters, 2 candidates for 21 voters, and 1 candidate for 11 voters.
Small, non-{party-list} As an example without a party structure, consider the following instance with 4 candidates, denoted by a,b,c,d, and 5 voters with approval sets 1: a; 2: b; 3: b and c; 4: a,b, and c; 5: d.
Round 1 Again, let candidates be given a score equal to the reciprocal of the number of approvers. We get the following: CandidateScoreabcd We select the candidate with the lowest score, which is b.
Round 2 Now, candidate scores are increased by the product of 1/3 (b's score) and the proportion of approvers who also approve of b. CandidateDerivationScorea1/2+(1/2)(1/3)c1/2+1(1/3)d1/1+0(1/3) We select the candidate with the lowest score, which is a.
Round 3 Now, candidate scores are increased by the sum of the product of 1/3 (b's score) and the proportion of approvers whose 'most recent' approval was b, and the product of 2/3 (a's score) and the proportion of approvers whose 'most recent' approval was a. CandidateDerivationScorec1/2+(1/2)(1/3)+(1/2)(2/3)1d1/1+0(1/3)+0(2/3)1 We select the candidate with the lowest score. In this case, it's tied between c and d.
Voters again start earning money at a fixed rate of 1 per day. After 1/3 days, the approvers of b have enough to buy b, resetting their money to 0, leading to a money distribution of (1/3, 0, 0, 0, 1/3). After 2/3 days, the money distribution is (2/3, 1/3, 1/3, 1/3, 2/3). Thus, the approvers of a can buy the candidate, with their money afterward being reset to 0 leading to a distribution of (0, 1/3, 1/3, 0, 2/3). Finally, after 1 day, the money distribution is (1/3, 2/3, 2/3, 1/3, 1). Thus, either c or d can be bought according to the tie-breaking used.
Hence, for the committee size k = 3 both {a,b,c} and {a,b,d} are valid seq-Phragmén committees.
Realistic Here is a more 'realistic' example. There are k=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:
Round 1 Again, let candidates be given a score equal to the reciprocal of the number of approvers. We get the following: CandidateScoreABCPQR We select the candidate with the lowest score, which is A.
Round 2 Now, candidate scores are increased by the product of 1/1171 (A's score) and the proportion of approvers who also approve of A. CandidateDerivationScoreB1/1124+1(1/1171)C1/1034+1(1/1171)P1/566+(47/566)(1/1171)Q1/656+(137/656)(1/1171)R1/519+0(1/1171) We select the candidate with the lowest score, which is Q.
Round 3 Now, candidate scores are increased by the sum of the product of 1/1171 (A's score) and the proportion of approvers whose 'most recent' approval was A, and the product of 327/192044 (Q's score) and the proportion of approvers whose 'most recent' approval was Q. CandidateDerivationScoreB1/1124+(517/562)(1/1171)+(45/562)(327/192044)C1/1034+1(1/1171)+0(327/192044)P1/566+0(1/1171)+1(327/192044)R1/519+0(1/1171)+1(327/192044) We select the candidate with the lowest score, which is B.
Variants for Approval Ballots Recall that in the Load Balancing description, each elected candidate creates a "load" of 1 unit. The load of a candidate must be born by voters who support him. The goal is to find a committee for which the load can be divided among the voters in the most "balanced" way. Depending on the exact definition of "balanced" several rules are possible:
Minimax-Phragmen (also called max-Phragmen or leximax-Phragmen): Minimizing the maximum load, and subject to that the second-maximum load, etc. (using lexicographic max-min optimization).