NPoS Election Algorithms
NPoS Election Algorithms
Since validators are paid almost equally in in each era, it is important that the stake behind each validator is uniformly spread out. An election algorithm for Nominated Proof of Staking (NPoS) will try to optimize three metrics when computing a solution graph of nominators and validators:
 Maximize the total amount at stake.
 Maximize the stake behind the minimally staked validator.
 Minimize the variance of the stake in the set.
Sequential Phragmén, Phragmms and Star balancing are a few notable algorithms used for computing the NPoS solutions in Polkadot and Kusama.
What is the sequential Phragmén method?
The sequential Phragmén method is a multiwinner election method introduced by Edvard Phragmén in the 1890s. The quote below taken from the reference Phragmén paper sums up the purpose of the sequential Phragmén method:
The problem that Phragmén’s methods try to solve is that of electing a set of a given numbers of persons from a larger set of candidates. Phragmén discussed this in the context of a parliamentary election in a multimember constituency; the same problem can, of course, also occur in local elections, but also in many other situations such as electing a board or a committee in an organization.
Validator Elections
The sequential Phragmén is one of the methods used in the Nominated ProofofStake scheme to elect validators based on their own selfstake and the stake that is voted to them from nominators. It also tries to equalize the weights between the validators after each election round.
OffChain Phragmén
Given the large set of nominators and validators, Phragmén's method is a difficult optimization problem. Polkadot uses offchain workers to compute the result offchain and submit a transaction to propose the set of winners. The reason for performing this computation offchain is to keep a constant block time of six seconds and prevent long block times at the end of each era, when the validator election takes place.
The process of computing the optimal solution for NPoS election can be delegated to Staking Miners.
Council Elections
Phragmen was used for Council elections in Governance v1.
The Phragmén method was also used in the council election mechanism. When you voted for council members, you could select up to 16 different candidates and then place a reserved bond as the weight of your vote. Phragmén would run once on every election to determine the top candidates to assume council positions and then again amongst the top candidates to equalize the weight of the votes behind them as much as possible.
What does it mean for node operators?
Phragmén is something that will run in the background and requires no extra effort from you. However, it is good to understand how it works since it means that not all the stake you've been nominated will end up on your validator after an election. Nominators are likely to nominate a few different validators that they trust to do a good job operating their nodes.
You can use this offlinephragmén tool for predicting the outcome of a validator election ahead of a new election.
Understanding Phragmén
This section explains the sequential Phragmén method indepth and walks through examples.
Basic Phragmén
Rationale
In order to understand the Weighted Phragmén method, we must first understand the basic Phragmén method. There must be some group of candidates, a group of seats they are vying for (which is less than the size of the group of candidates), and some group of voters. The voters can cast an approval vote  that is, they can signal approval for any subset of the candidates.
The subset should be a minimum size of one (i.e., one cannot vote for no candidates) and a maximum size of one less than the number of candidates (i.e., one cannot vote for all candidates). Users are allowed to vote for all or no candidates, but this will not affect the final result, making votes of this nature meaningless.
Note that in this example, all voters are assumed to have equal say (that is, their vote does not
count more or less than any other votes). The weighted case will be considered later. However,
weighting can be "simulated" by having multiple voters vote for the same slate of candidates. For
instance, five people voting for a particular candidate is mathematically the same as a single
person with weight 5
voting for that candidate.
The particular algorithm we call here the "Basic Phragmén" was first described by Brill et al. in their paper "Phragmén’s Voting Methods and Justified Representation".
Algorithm
The Phragmén method will iterate, selecting one seat at a time, according to the following rules:
 Voters submit their ballots, marking which candidates they approve. Ballots will not be modified after submission.
 An initial load of 0 is set for each ballot.
 The candidate who wins the next available seat is the one where the ballots of their supporters would have the least average (mean) cost if that candidate wins.
 The n ballots that approved that winning candidate get 1/n added to their load.
 The load of all ballots that supported the winner of this round are averaged out so that they are equal.
 If there are any more seats, go back to step 3. Otherwise, the selection ends.
Example
Let's walk through an example with four candidates vying for three seats, and five voters.
Open Seats: 3
Candidates: A B C D L0

Voter V1: X 0
Voter V2: X X 0
Voter V3: X X 0
Voter V4: X X 0
Voter V5: X X X 0
In this example, we can see that voter V1
approves only of candidate B
, voter V2
approves of
candidates C
and D
, etc. Voters can approve any number of candidates between 1 and
number_of_candidates  1
. An initial "load" of 0
is set for each ballot (L0
= load after round
0
, i.e., the "round" before the first round). We shall see shortly how this load is updated and
used to select candidates.
We will now run through an iterative algorithm, with each iteration corresponding to one "seat". Since there are three seats, we will walk through three rounds.
For the first round, the winner is simply going to be the candidate with the most votes. Since all
loads are equal, the lowest average load will be the candidate with the highest n, since 1/n
will
get smaller as n
increases. For this first example round, for instance, candidate A
had only one
ballot vote for them. Thus, the average load for candidate A is 1/1
, or 1. Candidate C has two
ballots approving of them, so the average load is 1/2
. Candidate B has the lowest average load, at
1/4
and they get the first seat. Ballots loads are now averaged out, although for the first
iteration, this will not have any effect.
Filled seats: 1 (B)
Open Seats: 2
Candidates: A B C D L0 L1

Voter V1: X 0 1/4
Voter V2: X X 0 0
Voter V3: X X 0 1/4
Voter V4: X X 0 1/4
Voter V5: X X X 0 1/4
We are now down to candidates A
, C
, and D
for two open seats. There is only one voter (V4
)
for A
, with load 1/4
. C
has two voters, V2
and V5
, with loads of 0
and 1/4
. D
has
three voters approving of them, V2
, V3
, and V5
, with loads of 0
, 1/4
, and 1/4
,
respectively.
If Candidate A
wins, the average load would be (1/4 + 1/1) / 1
, or 5/4
. If candidate C
wins,
the average load would be ((0 + 1/2) + (1/4 + 1/2)) / 2
, or 5/8
. If candidate D
wins, the
average load would be ((0 + 1/3) + (1/4 + 1/3) + (1/4 + 1/3)) / 3
, or 1/2
. Since 1/2
is the
lowest average load, candidate D wins the second round.
Now everybody who voted for Candidate D
has their load set to the average, 1/2
of all the loads.
Filled seats: 2 (B, D)
Open Seats: 1
Candidates: A B C D L0 L1 L2

Voter V1: X 0 1/4 1/4
Voter V2: X X 0 0 1/2
Voter V3: X X 0 1/4 1/2
Voter V4: X X 0 1/4 1/4
Voter V5: X X X 0 1/4 1/2
There is now one seat open and two candidates, A
and C
. Voter V4
is the only one voting for
A
, so if A
wins then the average load would be (1/4 + 1/1) / 1
, or 5/4
. Voters V2
and V5
(both with load 1/2
) support C
, so if C
wins the average load would be
((1/2 + 1/2) + (1/2 + 1/2)) / 2
, or 1
. Since the average load would be lower with C
, C
wins
the final seat.
Filled seats: 3 (B, D, C)
Open Seats: 0
Candidates: A B C D L0 L1 L2 L3

Voter V1: X 0 1/4 1/4 1/4
Voter V2: X X 0 0 1/2 1
Voter V3: X X 0 1/4 1/2 1/2
Voter V4: X X 0 1/4 1/4 1/4
Voter V5: X X X 0 1/4 1/2 1
An interesting characteristic of this calculation is that the total load of all voters will always
equal the number of seats filled in that round. In the zeroth round, load starts at 0
and there
are no seats filled. After the first round, the total of all loads is 1
, after the second round it
is 2
, etc.
Weighted Phragmén
Rationale
While this method works well if all voters have equal weight, this is not the case in Polkadot. Elections for both validators and candidates for the Council are weighted by the number of tokens held by the voters. This makes elections more similar to a corporate shareholder election than a traditional political election, where some members have more pull than others. Someone with a single token will have much less voting power than someone with 100. Although this may seem antidemocratic, in a pseudonymous system, it is trivial for someone with 100 tokens to create 100 different accounts and spread their wealth to all of their pseudonyms.
Therefore, not only do we want to allow voters to have their preferences expressed in the result, but do so while keeping as equal a distribution of their stake as possible and express the wishes of minorities as much as is possible. The Weighted Phragmén method allows us to reach these goals.
Algorithm
Weighted Phragmén is similar to Basic Phragmén in that it selects candidates sequentially, one per round, until the maximum number of candidates are elected. However, it has additional features to also allocate weight (stake) behind the candidates.
NOTE: in terms of validator selection, for the following algorithm, you can think of "voters" as "nominators" and "candidates" as "validators".
 Candidates are elected, one per round, and added to the set of successful candidates (they have won a "seat"). This aspect of the algorithm is very similar to the "basic Phragmén" algorithm described above.
 However, as candidates are elected, a weighted mapping is built, defining the weights of each selection of a validator by each nominator.
In more depth, the algorithm operates like so:
 Create a list of all voters, their total amount of stake, and which validators they support.
 Generate an initial edgeweighted graph mapping from voters to candidates, where each edge weight is the total potential weight (stake) given by that voter. The sum of all potential weight for a given candidate is called their approval stake.
 Now we start electing candidates. For the list of all candidates who have not been elected, get
their score, which is equal to
1 / approval_stake
.  For each voter, update the score of each candidate they support by adding their total budget
(stake) multiplied by the load of the voter and then dividing by that candidate's approval stake
(voter_budget * voter_load / candidate_approval_stake)
.  Determine the candidate with the lowest score and elect that candidate. Remove the elected candidate from the pool of potential candidates.
 The load for each edge connecting to the winning candidate is updated, with the edge load set to the score of the candidate minus the voter's load, and the voter's load then set to the candidate's score.
 If there are more candidates to elect, go to Step 3. Otherwise, continue to step 8.
 Now the stake is distributed amongst each nominator who backed at least one elected candidate.
The backing stake for each candidate is calculated by taking the budget of the voter and
multiplying by the edge load then dividing by the candidate load
(
voter_budget * edge_load / candidate_load
).
Example
Note: All numbers in this example are rounded off to three decimal places.
In the following example, there are five voters and five candidates vying for three potential seats.
Each voter V1  V5
has an amount of stake equal to their number (e.g., V1
has stake of 1, V2
has stake of 2, etc.). Every voter is also going to have a load, which initially starts at 0
.
Filled seats: 0
Open Seats: 3
Candidates: A B C D E L0

Voter V1 (1): X X 0
Voter V2 (2): X X 0
Voter V3 (3): X 0
Voter V4 (4): X X X 0
Voter V5 (5): X X 0
Let us now calculate the approval stake of each of the candidates. Recall that this is merely the amount of all support for that candidate by all voters.
Candidate A: 1 + 2 + 3 + 5 = 11
Candidate B: 1 + 2 + 4 = 7
Candidate C: 4 = 4
Candidate D: 4 + 5 = 9
Candidate E: 0
The first step is easy  candidate E
has 0 approval stake and can be ignored from here on out.
They will never be elected.
We can now calculate the initial scores of the candidates, which is 1 / approval_stake
:
Candidate A: 1 / 11 = 0.091
Candidate B: 1 / 7 = 0.143
Candidate C: 1 / 4 = 0.25
Candidate D: 1 / 9 = 0.111
Candidate E: N/A
For every edge, we are going to calculate the score, which is current score plus the total budget *
the load of the voter divided by the approval stake of the candidate. However, since the load of
every voter starts at 0, and anything multiplied by 0 is 0, any addition will be 0 / x
, or 0. This
means that this step can be safely ignored for the initial round.
Thus, the best (lowest) score for Round 0 is Candidate A, with a score of 0.091
.
Candidates: A B C D E L0 L1

Voter V1 (1): X X 0 0.091
Voter V2 (2): X X 0 0.091
Voter V3 (3): X 0 0.091
Voter V4 (4): X X X 0 0
Voter V5 (5): X X 0 0.091
Filled seats: 1 (A)
Open Seats: 2
Candidates: A B C D E L0

Voter V1 (1): X X 0
Voter V2 (2): X X 0
Voter V3 (3): X 0
Voter V4 (4): X X X 0
Voter V5 (5): X X 0
Candidate A
is now safe; there is no way that they will lose their seat. Before moving on to the
next round, we need to update the scores on the edges of our graph for any candidates who have not
yet been elected.
We elided this detail in the previous round, since it made no difference to the final scores, but we should go into depth here to see how scores are updated. We first must calculate the new loads of the voters, and then calculate the new scores of the candidates.
Any voter who had one of their choices for candidate fill the seat in this round (i.e., voters V1
,
V2
, V3
, and V5
, who all voted for A
) will have their load increased. This load increase will
blunt the impact of their vote in future rounds, and the edge (which will be used in determining
stake allocation later) is set to the score of the elected candidate minus the current voter load.
edge_load = elected_candidate_score  voter_load
voter_load = elected_candidate_score
In this instance, the score of the elected candidate is 0.091
and the voter loads are all 0
. So
for each voter who voted for A
, we will calculate a new edge load Voter
> A
of:
Edge load: 0.091  0 = 0.091
and a new voter load of:
Voter load: 0.091
As a reminder, here are the current scores. Loads of the voters are all 0
.
Candidate B : 0.143
Candidate C : 0.25
Candidate D : 0.111
Now, we go through the weighted graph and update the score of the candidate and the load of the edge, using the algorithm:
candidate_score = candidate_score + ((voter_budget * voter_load) / candidate_approval_stake)
Without walking through each step, this gives us the following modifications to the scores of the different candidates.
V1 updates B to 0.156
V2 updates B to 0.182
V4 updates B to 0.182
V4 updates C to 0.25
V4 updates D to 0.111
V5 updates D to 0.162
After scores are updated, the final scores for the candidates for this round are:
Candidate B: 0.182
Candidate C: 0.25
Candidate D: 0.162
D
, with the lowest score, is elected. You will note that even though candidate B
had more voters
supporting them, candidate D
won the election due to their lower score. This is directly due to
the fact that they had the lowest score, of course, but the root reason behind them having a lower
score was both the greater amount of stake behind them and that voters who did not get one of their
choices in an earlier round (in this example, voter V4) correspond to a higher likelihood of a
candidate being elected.
We then update the loads for the voters and edges as specified above for any voters who voted for
candidate D
(viz., V4
and V5
) using the same formula as above.
Filled seats: 2 (A, D)
Open Seats: 1
Candidates: A B C D E L0 L1 L2

Voter V1 (1): X X 0 0.091 0.091
Voter V2 (2): X X 0 0.091 0.091
Voter V3 (3): X 0 0.091 0.091
Voter V4 (4): X X X 0 0 0.162
Voter V5 (5): X X 0 0.091 0.162
Following a similar process for Round 2, we start with initial candidate scores of:
Candidate B : 0.143
Candidate C : 0.25
We can then update the scores of the remaining two candidates according to the algorithm described above.
V1 updates B to 0.156
V2 updates B to 0.182
V4 updates B to 0.274
V4 updates C to 0.412
With the lowest score of 0.274
, Candidate B
claims the last open seat. Candidates A
, D
, and
B
have been elected, and candidates C
and E
are not.
Before moving on, we must perform a final load adjustment for the voters and the graph.
Filled seats: 3 (A, D, B)
Open Seats: 0
Candidates: A B C D E L0 L1 L2 L3

Voter V1 (1): X X 0 0.091 0.091 0.274
Voter V2 (2): X X 0 0.091 0.091 0.274
Voter V3 (3): X 0 0.091 0.091 0.091
Voter V4 (4): X X X 0 0 0.162 0.274
Voter V5 (5): X X 0 0.091 0.162 0.162
Now we have to determine how much stake every voter should allocate to each candidate. This is done by taking the load of the each edge and dividing it by the voter load, then multiplying by the total budget of the voter.
In this example, the weighted graph ended up looking like this:
Nominator: V1
Edge to A load= 0.091
Edge to B load= 0.183
Nominator: V2
Edge to A load= 0.091
Edge to B load= 0.183
Nominator: V3
Edge to A load= 0.091
Nominator: V4
Edge to B load= 0.113
Edge to D load= 0.162
Nominator: V5
Edge to A load= 0.091
Edge to D load= 0.071
For instance, the budget of V1
is 1
, the edge load to A
is 0.091
, and the voter load is
0.274
. Using our equation:
backing_stake (A) = voter_budget * edge_load / voter_load
We can fill these variables in with:
backing_stake (A) = 1 * 0.091 / 0.274 = 0.332
For V1
backing stake of B
, you can simply replace the edge load value and recalculate.
backing_stake (B) = 1 * 0.183 / 0.274 = 0.668
Note that the total amount of all backing stake for a given voter will equal the total budget of the voter, unless that voter had no candidates elected, in which case it will be 0.
The final results are:
A is elected with stake 6.807.
D is elected with stake 4.545.
B is elected with stake 3.647.
V1 supports: A with stake: 0.332 and B with stake: 0.668.
V2 supports: A with stake: 0.663 and B with stake: 1.337.
V3 supports: A with stake: 3.0.
V4 supports: B with stake: 1.642 and D with stake: 2.358.
V5 supports: A with stake: 2.813 and D with stake: 2.187.
You will notice that the total amount of stake for candidates A
, D
, and B
equals (aside from
rounding errors) the total amount of stake of all the voters (1 + 2 + 3 + 4 + 5 = 15
). This is
because each voter had at least one of their candidates fill a seat. Any voter who had none of their
candidates selected will also not have any stake in any of the elected candidates.
Optimizations
The results for nominating validators are further optimized for several purposes:
 To reduce the number of edges, i.e. to minimize the number of validators any nominator selects
 To ensure, as much as possible, an even distribution of stake among the validators
 Reduce the amount of block computation time
HighLevel Description
After running the weighted Phragmén algorithm, a process is run that redistributes the vote amongst the elected set. This process will never add or remove an elected candidate from the set. Instead, it reduces the variance in the list of backing stake from the voters to the elected candidates. Perfect equalization is not always possible, but the algorithm attempts to equalize as much as possible. It then runs an edgereducing algorithm to minimize the number of validators per nominator, ideally giving every nominator a single validator to nominate per era.
To minimize block computation time, the staking process is run as an offchain worker. In order to give time for this offchain worker to run, staking commands (bond, nominate, etc.) are not allowed in the last quarter of each era.
These optimizations will not be covered indepth on this page. For more details, you can view the
Rust implementation of elections in Substrate,
the
Rust implementation of staking in Substrate,
or the seqPhragménwithpostprocessing
method in the
Python reference implementation. If you would
like to dive even more deeply, you can review the
W3F Research Page on Sequential Phragmén Method.
Rationale for Minimizing the Number of Validators Per Nominator
Paying out rewards for staking from every validator to all of their nominators can cost a
nontrivial amount of chain resources (in terms of space on chain and resources to compute). Assume
a system with 200 validators and 1000 nominators, where each of the nominators has nominated 10
different validators. Payout would thus require 1_000 * 10
, or 10_000 transactions. In an ideal
scenario, if every nominator selects a single validator, only 1_000 transactions would need to take
place  an order of magnitude fewer. Empirically, network slowdown at the beginning of an era has
occurred due to the large number of individual payouts by validators to nominators. In extreme
cases, this could be an attack vector on the system, where nominators nominate many different
validators with small amounts of stake in order to slow the system at the next era change.
While this would reduce network and onchain load, being able to select only a single validator incurs some diversification costs. If the single validator that a nominator has nominated acts maliciously, then the nominator incurs a risk of a significant amount of slashing. Nominators are thus allowed to nominate up to 16 different validators. However, after the weighted edgereducing algorithm is run, the number of validators per nominator is minimized. Nominators are likely to see themselves nominating a single active validator for an era.
At each era change, as the algorithm runs again, nominators are likely to have a different validator than they had before (assuming a significant number of selected validators). Therefore, nominators can diversify against incompetent or corrupt validators causing slashing on their accounts, even if they only nominate a single validator per era.
Rationale for Maintaining an Even Distribution of Stake
Another issue is that we want to ensure that as equal a distribution of votes as possible amongst
the elected validators or council members. This helps us increase the security of the system by
ensuring that the minimum amount of tokens in order to join the active validator set or council is
as high as possible. For example, assume a result of five validators being elected, where validators
have the following stake: {1_000, 20, 10, 10, 10}
, for a total stake of 1_050. In this case, a
potential attacker could join the active validator set with only 11 tokens, and could obtain a
majority of validators with only 33 tokens (since the attacker only has to have enough stake to
"kick out" the three lowest validators).
In contrast, imagine a different result with the same amount of total stake, but with that stake
perfectly equally distributed: {210, 210, 210, 210, 210}
. With the same amount of stake, an
attacker would need to stake 633 tokens in order to get a majority of validators, a much more
expensive proposition. Although obtaining an equal distribution is unlikely, the more equal the
distribution, the higher the threshold  and thus the higher the expense  for attackers to gain
entry to the set.
Rationale for Reducing Block Computing Time
Running the Phragmén algorithm is timeconsuming, and often cannot be completed within the time limits of production of a single block. Waiting for calculation to complete would jeopardize the constant block production time of the network. Therefore, as much computation as possible is moved to an offchain worker, which validators can work on the problem without impacting block production time.
To limit the complexity of the election and payout, any given nominator can only select a limited number of validators to nominate.
Phragmms (aka Balphragmms)
Phragmms
, formerly known as Balphragmms
, is a new election rule inspired by Phragmén and
developed inhouse for Polkadot. In general, election rules on blockchains is an active topic of
research. This is due to the conflicting requirements for election rules and blockchains: elections
are computationally expensive, but blockchains are computationally limited. Thus, this work
constitutes state of the art in terms of optimization.
Proportional representation is a very important property for a decentralized network to have in
order to maintain a sufficient level of decentralization. While this is already provided by the
currently implemented seqPhragmen
, this new election rule provides the advantage of the added
security guarantee described below. As far as we can tell, at the time of writing, Polkadot and
Kusama are the only blockchain networks that implement an election rule that guarantees proportional
representation.
The security of a distributed and decentralized system such as Polkadot is directly related to the goal of avoiding overrepresentation of any minority. This is a stark contrast to traditional approaches to proportional representation axioms, which typically only seek to avoid underrepresentation.
Maximin Support Objective and PJR
This new election rule aims to achieve a constantfactor approximation guarantee for the maximin support objective and the closely related proportional justified representation (PJR) property.
The maximin support objective is based on maximizing the support of the leastsupported elected
candidate, or in the case of Polkadot and Kusama, maximizing the least amount of stake backing
amongst elected validators. This securitybased objective translates to a security guarantee for
NPoS and makes it difficult for an adversarial whale’s validator nodes to be elected. The Phragmms
rule, and the guarantees it provides in terms of security and proportionality, have been formalized
in a peerreviewed paper).
The PJR property considers the proportionality of the voter’s decision power. The property states that a group of voters with cohesive candidate preferences and a large enough aggregate voting strength deserve to have a number of representatives proportional to the group’s vote strength.
Comparing Sequential Phragmén, MMS, and Phragmms
Sequential Phragmén (seqPhragmen
) and MMS
are two efficient election rules that both achieve
PJR.
Currently, Polkadot employs the seqPhragmen
method for validator and council elections. Although
seqPhramen
has a very fast runtime, it does not provide constantfactor approximation for the
maximin support problem. This is due to seqPhramen
only performing an approximate rebalancing of
the distribution of stake.
In contrast, MMS
is another standard greedy algorithm that simultaneously achieves the PJR
property and provides a constant factor approximation for maximin support, although with a
considerably slower runtime. This is because for a given partial solution, MMS
computes a balanced
edge weight vector for each possible augmented committee when a new candidate is added, which is
computationally expensive.
We introduce a new heuristic inspired by seqPhragmen
, PhragMMS
, which maintains a comparable
runtime to seqPhragmen
, offers a constantfactor approximation guarantee for the maximin support
objective, and satisfies PJR. This is the fastest known algorithm to achieve a constantfactor
guarantee for maximin support.
The New Election Rule: Phragmms
Phragmms
is an iterative greedy algorithm that starts with an empty committee and alternates
between the Phragmms
heuristic for inserting a new candidate and rebalancing by replacing the
weight vector with a balanced one. The main differentiator between Phragmms
and seqPhragmen
is
that the latter only perform an approximate rebalancing. Details can be found in
Balanced Stake Distribution.
The computation is executed by offchain workers privately and separately from block production, and the validators only need to submit and verify the solutions onchain. Relative to a committee A, the score of an unelected candidate c is an easytocompute rough estimate of what would be the size of the least stake backing if we added c to committee A. Observing onchain, only one solution needs to be tracked at any given time, and a block producer can submit a new solution in the block only if the block passes the verification test, consisting of checking:
 Feasibility,
 Balance and
 Local Optimality  The least stake backing of A is higher than the highest score among unelected candidates
If the tentative solution passes the tests, then it replaces the current solution as the tentative winner. The official winning solution is declared at the end of the election window.
A powerful feature of this algorithm is the fact that both its approximation guarantee for maximin
support and the above checks passing can be efficiently verified in linear time. This allows for a
more scalable solution for secure and proportional committee elections. While seqPhragmen
also has
a notion of score for unelected candidates, Phragmms
can be seen as a natural complication of the
seqPhragmen
algorithm, where Phragmms
always grants higher score values to candidates and thus
inserts them with higher support values.
To summarize, the main differences between the two rules are:
 In
seqPhragmen
, lower scores are better, whereas inPhragmms
, higher scores are better.  Inspired by
seqPhragmen
, the scoring system ofPhragmms
can be considered to be more intuitive and does a better job at estimating the value of adding a candidate to the current solution, and hence leads to a better candidateselection heuristic.  Unlike
seqPhragmen
, inPhragmms
, the edge weight vector w is completely rebalanced after each iteration of the algorithm.
The Phragmms
election rule is currently being implemented on Polkadot. Once completed, it will
become one of the most sophisticated election rules implemented on a blockchain. For the first time,
this election rule will provide both fair representation (PJR) and security (constantfactor
approximation for the maximin support objection) to a blockchain network.
Algorithm
The Phragmms
algorithm iterates through the available seats, starting with an empty committee of
size k:

Initialize an empty committee A and zero edge weight vector w = 0.

Repeat k times:
 Find the unelected candidate with highest score and add it to committee A.
 Rebalance the weight vector w for the new committee A.

Return A and w.
External Resources
 Phragmms  W3F research paper that expands on the sequential Phragmén method.
 W3F Research Page on NPoS  An overview of Nominated Proof of Stake as its applied to Polkadot.
 Python Reference Implementations  Python implementations of Simple and Complicated Phragmén methods.
 Substrate Implementation  Rust implementation used in Substrate.
 Phragmén's and Thiele's Election Methods  95page paper explaining Phragmén's election methods in detail.
 Phragmén’s Voting Methods and Justified Representation  This paper by Brill et al. is the source for the simple Phragmén method, along with proofs about its properties.
 Offline Phragmén  Script to generate the Phragmén validator election outcome before the start of an era.