Since validators are paid almost equally in Polkadot 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) on Polkadot will try to optimize three metrics when computing a solution graph of nominators and validators:
NOTE
Sequential Phragmén, Phragmms and Star balancing are a few notable algorithms used for computing the NPoS solutions in Polkadot and Kusama.
The sequential Phragmén method is a multi-winner 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:
NOTE
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 multi-member 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.
The sequential Phragmén is one of the methods used in the Nominated Proof-of-Stake scheme to elect validators based on their own self-stake and the stake that is voted to them from nominators. It also tries to equalize the weights between the validators after each election round.
Given the large set of nominators and validators, Phragmén's method is a difficult optimization problem. Polkadot uses off-chain workers to compute the result off-chain and submit a transaction to propose the set of winners. The reason for performing this computation off-chain 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.
STAKING MINERS
The process of computing the optimal solution for NPoS election can be delegated to Staking Miners.
DEPRECATED IN POLKADOT OPENGOV
Phragmen was used for Council elections in Governance v1.