Phragmen's voting rules

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,^[1] and translated to English by Svante Janson in 2016.^[2]

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.^[2]^: Sec.11 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).

Phragmén's rules for approval ballots

Phragmén's method for unordered (approval) ballots can be presented in several equivalent ways.^[2]^: Sec.3

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.

Depending on the exact definition of "balanced" several rules are possible:^[3]

Leximax-Phragmen: Minimizing the maximum load, and subject to that the second-maximum load, etc. (using lexicographic max-min optimization).
Leximin-Phragmen: Maximizing the minimum load, and subject to that the second-minimum load, etc..
var-Phragmen or Ebert's method: Minimizing the variance of the load.

Each of these variants has two sub-variants:

A global optimization variant, which is usually NP-hard to compute;
A sequential variant, in which candidates are selected sequentially, and in each turn, the next elected candidate is the one who attains the optimal measure among all candidates (i.e., a greedy algorithm).

Phragmen's original method is the sequential method that minimizes the maximum load, which is currently known as Seq-Phragmen.^[3]

In practice, the rules that have the best axiomatic guarantees in the global-optimization category are leximax-Phragmen and var-Phragmen. Among the sequential variants, the best guarantees are given by Seq-Phragmen.

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

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.

Voters start earning money at a fixed rate of 1 per day. After 1/31 day (~0.0323 day), 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 day (~0.0476 day), 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.0646 day, the abc voters again have 0.0323 each, so they buy another one of their approved candidates, say b.
After 1/11 day (~0.091 day) the ghi voters have 0.091 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 day, the def voters again have 0.0476 each, so they can buy another candidate, say e.
After 0.0969 day, 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.

Here is a more complex 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:

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.

Computation

Var-Phragmen and Leximax-Phragmen are NP-hard to compute, even when each agent approves 2 candidates and each candidate is approved by 3 voters. The proof is by reduction from Maximum independent set on cubic graphs.^[3]

Leximax-Phragmen can be computed by a sequence of at most 2n mixed-integer linear programs with O(n m + n²) variables each (where n is the number of voters and m the number of candidates); see Lexicographic max-min optimization.

Var-Phragmen can be computed by solving one mixed-integer quadratic program with O(n m) variables.

Seq-Phragmen can be computed in polynomial time. A naive computation shows that the run-time is O(k m n): there are k steps (one for each elected candidate); in each step, we have to check all candidates to see which of them can be funded; and for each candidate, we have to check all voters to see which of them can fund it. However, to be accurate, we need to work with rational numbers, and their magnitude grow up to k log n. Since computations in b bits may require O(b²) time, the total run-time is O(k³ m n log² n).

Phragmén's rules for Ranked ballots

Phragmén rules are commonly used with approval ballots (that is, multiwinner approval voting), but they have variants using ranked ballots (that is, multiwinner ranked voting). An adaptation for Seq-Phragmen was proposed in 1913 by a Royal Commission on the Proportional Election Method. The method has been used in Swedish elections for the distribution of seats within parties since 1921.^[2]^: Sec.9

In the adapted version, in each round, each voter effectively votes only for the highest-ranked remaining candidate. Again, when a candidate is elected, his "load" of 1 unit should be distributed among the candidates who vote for him (i.e., rank him first); the load division should minimize the maximum load of a voter.

Variants

Party voting

It is possible to use Phragmen's method for parties. Each voter can approve one or more parties. The procedure is the same as before, except that now, each party can be selected several times - between 0 and the total number of candidates in the party.^[4]

Participatory budgeting

The Seq-Phragmen rule was adapted to the more general setting of combinatorial participatory budgeting.^[5]

Degressive and regressive proportionality

Jaworski and Skowron^[6] constructed a class of rules that generalise seq-Phragmen for degressive and regressive proportionality. Intuitively:

Degressive proportionality is obtained by assuming that the voters who already have more representatives earn money at a slower rate than those that have fewer;
Regressive proportionality is implemented by assuming that the candidates who are approved by more voters cost less than those that garnered fewer approvals.

Using Phragmen's method to rank alternatives

The sequential Phragmen method can be used not only to select a subset, but also to create a ranking of alternatives, according to the order by which they are chosen. Brill and Israel^[7] extend this method to dynamic rankings. Motivated by online Q&A applications,^[8] they assume that some candidates were already chosen, and use this information in computing the ranking. They suggest two adaptations of Phragmen's rule:

Dynamic Phragmen: at each step, loop over the sequence of already-elected candidates, and divide their "cost" among their supporters. This creates, for each user, a potential "debt" - negative balance. Computing the debts can be done in time O(m n²), where m is the number of candidates and n the number of users. Then, users start accruing money as usual, where a user can start buying new candidates only after having paid its "debt". Users buy candidates sequentially, until the new ranking is computed. The new ranking is proportional. Computing the new sequence can be done in time O(m² n²).
Myopic Phragmen: the "debt" of each user is computed as in Dynamic Phragmen. Then, instead of creating a complete ranking by running Sequential Phragmen, the candidates are ranked by the amount of "debt" they will create to the users. That is: the candidates are ranked by their suitability to be elected next. The resulting ranking is not necessarily proportional (in particular, when the sequence is empty, Myopic Phragmen coincides with utilitarian approval voting). Computing the new sequence can be done in time O(m n²).

They analyze the monotonicity and fairness properties of these adaptations, both theoretically and empirically.

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. Phragmén'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 (even if some of them are voted for), then the outcome does not change.^[2]^: Sec.6 This reduces one incentive for strategic manipulation: adding "dummy" candidates to attract votes.

Monotonicity

Seq-Phragmén assign seats one-by-one, so it satisfies the committee monotonicity property: when more seats are added, the set of winners increases (no winner loses a seat).^[2]^: Sec.5

They also satisfy several other monotonicity criteria.^[2]^: Sec.14

For Phragmén'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} Similarly, monotonicity does not hold in the variant with parties: a party can get more approvals but still get fewer seats. For example:^[4]

Suppose there are k=3 seats and 3 candidates: a,b,c. The ballots are: 4 for a, 7 for b, 1 for a+b, 16 for a+c, 4 for b+c. Then the elected committee is {a,b,a}. But, if one of the b voters approves a too (so that the ballots are: 4 for a, 6 for b, 2 for a+b, 16 for a+c, 4 for b+c), then the elected committee is {a,c,b}. So party a won an approval but lost a seat.

For Phragmén'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

Justified representation

The Sequential Phragmen rule satisfies an axiom known as Proportional Justified Representation (PJR).^[3] This makes it one of the only methods satisfying both PJR and monotonicity.

However, it fails a stronger axiom known as Extended Justified Representation (EJR). One example is given here:^[3]

There are 14 candidates: a, b, c1, ..., c12. There are 12 seats to fill.
There are 24 voters: two voters approve {a,b,c1}; two voters approve {a,b,c2}; 6 voters approve {c1,c2,...,c12}; 5 voters approve {c2,c3,...,c12); 9 voters approve {c3,c4,...,c12}.
Seq-Phragmen selects c1,...,c12. It violates EJR for the four voters who approve {a,b,c1} and {a,b,c2}: this group has 2 quotas and it is 2-cohesive, but no member has 2 approved winners.

Another example is given here (for the setting of parties):^[9]

There are 3 candidate-parties and 10 seats to fill.
There are 10 voters, with approval sets ab,ab,ab; ac,ac,ac,ac; bc,bc; b.
Seq-Phragmen chooses a (at time 1/7); then b; then a,b,a,b,a,b,a,b.
Voters 1,2,3 approve all 10 candidates, but voters 4,...,10 approve only 5 candidates. However, the group of voters 4,5,6,7,8,9 all agree on party c, so EJR requires that at least one of them should approve 6 candidates, so EJR is violated (note that PJR is not violated for that group, since all 10 candidates are approved by at least one member of the group).

Seq-Phragmen also fails a different, incompatible axiom called Perfect Representation (PER).

Var-Phragmen satisies PER, but fails PJR and EJR (except for the case L=1).

Leximan-Phragmen satisfies both PJR and PER, but still fails EJR.

Consistency

Phragmén'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):

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

Implementations and demonstrations

Some of Phragmén's voting rules are implemented in the Python package abcvoting.
Some of Phragmén's voting rules can be tried online on the pref.tools website.
Both the simple and complicated versions^[13]^[14] are used in the substrate of the cryptocurrency Polkadot.^[15]

Generalizations

Motamed, Soeteman, Rey and Endriss^[16] present a sequential load balancing mechanism, that generalizes Phragmen's rule to participatory budgeting with multiple resources.

References

^ 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
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k Janson, Svante (2018-10-12). "Phragmén's and Thiele's election methods". arXiv:1611.08826 [math.HO].
^ ^a ^b ^c ^d ^e Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (2023-03-06). "Phragmén's voting methods and justified representation". Mathematical Programming. 203 (1–2): 47–76. arXiv:2102.12305. doi:10.1007/s10107-023-01926-8. ISSN 1436-4646. PMC 10858002. PMID 38344413.
^ ^a ^b Mora, Xavier; Oliver, Maria (2015-07-28). "Eleccions mitjançant el vot d'aprovació. El mètode de Phragmén i algunes variants". Butlletí de la Societat Catalana de Matemàtiques (in Catalan). 30 (1): 57–101. ISSN 2013-9829.
^ Los, Maaike; Christoff, Zoé; Grossi, Davide (2022). "Proportional Budget Allocations: Towards a Systematization". arXiv:2203.12324 [cs.GT].
^ Jaworski, Michal; Skowron, Piotr (2022). "Phragmén Rules for Degressive and Regressive Proportionality". arXiv:2201.04248 [cs.GT].
^ Israel, Jonas; Brill, Markus (2021). "Dynamic Proportional Rankings". arXiv:2105.08043 [cs.GT].
^ Q&A applications such as slido, mentimeter, pigeonhole live or speakup.
^ Chandak, Nikhil; Goel, Shashwat; Peters, Dominik (2023). "Proportional Aggregation of Preferences for Sequential Decision Making". arXiv:2306.14858 [cs.GT].
^ 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. pp. 793–794. arXiv:1911.11747. doi:10.1145/3391403.3399465. ISBN 978-1-4503-7975-5. S2CID 208291203.
^ Janson, Svante; Öberg, Anders (2017). "A piecewise contractive dynamical system and election methods". arXiv:1709.06398 [math.DS].
^ Camps, Rosa; Mora, Xavier; Saumell, Laia (2019). "The method of Eneström and Phragmén for parliamentary elections by means of approval voting". arXiv:1907.10590 [econ.TH].
^ "consensus/NPoS at master · w3f/consensus". GitHub. 17 October 2021.
^ https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/download/14757/13791 ^{[bare URL PDF]}
^ "Sequential Phragmén Method · Polkadot Wiki". wiki.polkadot.network. 30 June 2023.
^ Motamed, Nima; Soeteman, Arie; Rey, Simon; Endriss, Ulle (2022). "Participatory Budgeting with Multiple Resources". In Baumeister, Dorothea; Rothe, Jörg (eds.). Multi-Agent Systems. Lecture Notes in Computer Science. Cham: Springer International Publishing. pp. 330–347. doi:10.1007/978-3-031-20614-6_19. ISBN 978-3-031-20614-6. S2CID 252357719.

[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

[:0-2] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k Janson, Svante (2018-10-12). "Phragmén's and Thiele's election methods". arXiv:1611.08826 [math.HO].

[:2-3] Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (2023-03-06). "Phragmén's voting methods and justified representation". Mathematical Programming. 203 (1–2): 47–76. arXiv:2102.12305. doi:10.1007/s10107-023-01926-8. ISSN 1436-4646. PMC 10858002. PMID 38344413.

[:1-4] Mora, Xavier; Oliver, Maria (2015-07-28). "Eleccions mitjançant el vot d'aprovació. El mètode de Phragmén i algunes variants". Butlletí de la Societat Catalana de Matemàtiques (in Catalan). 30 (1): 57–101. ISSN 2013-9829.

[:8-5] Los, Maaike; Christoff, Zoé; Grossi, Davide (2022). "Proportional Budget Allocations: Towards a Systematization". arXiv:2203.12324 [cs.GT].

[6] Jaworski, Michal; Skowron, Piotr (2022). "Phragmén Rules for Degressive and Regressive Proportionality". arXiv:2201.04248 [cs.GT].

[7] Israel, Jonas; Brill, Markus (2021). "Dynamic Proportional Rankings". arXiv:2105.08043 [cs.GT].

[8] Q&A applications such as slido, mentimeter, pigeonhole live or speakup.

[:7-9] Chandak, Nikhil; Goel, Shashwat; Peters, Dominik (2023). "Proportional Aggregation of Preferences for Sequential Decision Making". arXiv:2306.14858 [cs.GT].

[10] 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. pp. 793–794. arXiv:1911.11747. doi:10.1145/3391403.3399465. ISBN 978-1-4503-7975-5. S2CID 208291203.

[11] Janson, Svante; Öberg, Anders (2017). "A piecewise contractive dynamical system and election methods". arXiv:1709.06398 [math.DS].

[12] Camps, Rosa; Mora, Xavier; Saumell, Laia (2019). "The method of Eneström and Phragmén for parliamentary elections by means of approval voting". arXiv:1907.10590 [econ.TH].

[13] "consensus/NPoS at master · w3f/consensus". GitHub. 17 October 2021.

[14] ttps://aaai.org/ocs/index.php/AAAI/AAAI17/paper/download/14757/13791 ^{[bare URL PDF]}

[15] "Sequential Phragmén Method · Polkadot Wiki". wiki.polkadot.network. 30 June 2023.

[16] Motamed, Nima; Soeteman, Arie; Rey, Simon; Endriss, Ulle (2022). "Participatory Budgeting with Multiple Resources". In Baumeister, Dorothea; Rothe, Jörg (eds.). Multi-Agent Systems. Lecture Notes in Computer Science. Cham: Springer International Publishing. pp. 330–347. doi:10.1007/978-3-031-20614-6_19. ISBN 978-3-031-20614-6. S2CID 252357719.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]