Phragmén's voting rules

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:

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.

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.

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.

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

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

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:

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.

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.

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:

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.

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.

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).
• Maximin-Phragmen (also called min-Phragmen or 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).

The special case of apportionment

In the special case of apportionment, leximax-Phragmen reduces to the Jefferson method and var-Phragmen reduces to the Webster method.

Proportionality degree

Skowron studied the proportionality degree of multiwinner voting rules - a lower bound on the average satisfaction of all groups of a certain size. In particular, he proved that, among the min-max Phragmen rules, the sequential variant has a much higher proportionality degree than the global optimization variant: the sequential variant gives every L-cohesive group an average satisfaction of at least (L-1)/2, whereas the global optimization variant guarantees only 1.

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 the maximum independent set on cubic graphs.

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 evaluation 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 compute the load of each voter accurately, we have to use rational numbers. The denominators of these numbers can grow exponentially: in each round, the denominator is multiplied by the number of supporters of the elected candidate, which is at most n. Hence, the denominator of each load in round t is at most n^t <= n^k. The numerator is at most k n^k. Hence, the sapce required to store the scores is in O(k log n) bits. Since computations in b bits may require O(b²) time, the total run-time is O(k³ m n log² n).

Robustness

Faliszewski, Gawron and Kusek study the robusness of sequential-Phragmen to errors in the votes. They prove that it is not robust, in the following sense: even if, for one voter, there is one mistake (one added approval, one removed approval, or one swapped approval), the entire committee can change.

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.

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.

Participatory budgeting

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

Degressive and regressive proportionality

Jaworski and Skowron 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 extend this method to dynamic rankings. Motivated by online Q&A applications, 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.

Independence of unelected candidates

If any number of candidates is added to a ballot, but none of them are elected (even if some of them are voted for), then the outcome does not change. 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).

They also satisfy several other monotonicity criteria.

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). Similarly, monotonicity does not hold in the variant with parties: a party can get more approvals but still get fewer seats. For example:

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

Justified representation

The Sequential Phragmen rule satisfies an axiom known as Proportional Justified Representation (PJR). 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:

• 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):

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

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.

Current practical use

Polkadot blockchain platform

Variants of Phragmen's voting rules are used in Polkadot (blockchain platform). Polkadot uses nominated proof of stake to validate blocks. In this system, all coin-holders participate in electing a subset of the coin-holders to serve as "validators" (for a fee). The outcome is computed using a weighted variant of Phragmen's rule, in which the weight of each voter ("nominator") is determined by the amount of money he is willing to "freeze" for the course of the elections.

The election is repeated at the start of every "era", a period of 24 hours on Polkadot and 6 hours on its companion network Kusama, and the committee size is the number of validator slots available in that era. As of 2026-08-13, the active set contains 600 validators, and the number of active nominators is 29144. Each nominator may approve at most 16 candidates, so the ballots are approval ballots of bounded size.

Besides selecting the winning committee, the rule is used for a second purpose that has no analogue in parliamentary elections: the load distribution computed by the algorithm is also used to divide each nominator's frozen stake among those of his approved candidates that were elected. The resulting stake assignment determines both the nominator's share of the block rewards and his exposure to slashing, the confiscation of part of the stake backing a validator that misbehaves. Consequently the quantity of interest is not only the identity of the elected committee, but the support (total assigned stake) of each of its members, and in particular the support of the least-supported member, since an adversary can obtain a validator slot by staking slightly more than that amount. Maximizing this quantity is the maximin support objective, which is closely related to the proportional justified representation (PJR) property. Cevallos and Stewart argue that, in this application, the relevant goal is preventing the overrepresentation of a minority, in contrast to the usual reading of proportional representation as preventing underrepresentation.

Because seq-Phragmen performs only an approximate rebalancing of the load distribution, it satisfies PJR but does not guarantee a constant-factor approximation for the maximin support objective. The alternative rule MMS achieves both, but is considerably slower, since it recomputes a balanced weight vector for every candidate augmentation. Cevallos and Stewart therefore proposed a hybrid rule, Phragmms (originally Balphragmms), which alternates between a seq-Phragmen-like insertion heuristic and a full rebalancing of the weight vector; it satisfies PJR, provides a constant-factor approximation for maximin support, and retains a running time comparable to that of seq-Phragmen. In Phragmms, unlike in seq-Phragmen, higher candidate scores are better, the score of an unelected candidate being an estimate of the least support that would result from adding it to the committee.

Two features of the blockchain setting shape the implementation. First, the election instance is too large to be computed within the time budget of a single block, so the computation is performed off-chain and submitted as a candidate solution, which the network then only needs to verify; verification of feasibility, balancedness and local optimality can be performed in linear time and admits parallelization, which Cevallos and Stewart identify as essential to deploying the rule on a computationally limited architecture. Second, the number of edges in the resulting bipartite graph determines the number of on-chain reward payouts, so a post-processing step reduces the number of validators backed by each nominator, ideally to one per era, while leaving the elected committee unchanged. Diversification against slashing is thereby obtained across eras rather than within a single era.

A weighted variant of Phragmen's rule was also used in Polkadot's earlier governance system to elect the "Council", a body responsible for administrative and treasury matters; voters could approve up to 16 candidates with a bonded amount as weight. This use was discontinued when the Council was replaced by the direct-referendum system Polkadot OpenGov.

Primary elections case study

Rosenfeld, Shapiro and Talmon compare six algorithms for primary elections, one of which is Phragmen's rule, on real-world data from primary election conducted by the Israeli Democratit party. They evaluate the level of proportionality using cluster analysis. Their results show that Phragmen's rule produces a more proportionate ranking than the more commonly used method of approval voting.

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 https://pref.tools/abcvoting/ pref.tools website.

Generalizations

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