Rust implementation of the Phragmén election algorithm. This is used in several pallets to optimally distribute the weight of a set of voters among an elected set of candidates. In the context of staking this is mapped to validators and nominators.
The algorithm has two phases:
- Sequential phragmen: performed in
electfunction which is first pass of the distribution The results are not optimal but the execution time is less.
- Equalize post-processing: tries to further distribute the weight fairly among candidates. Incurs more execution time.
The main objective of the assignments done by phragmen is to maximize the minimum backed candidate in the elected set.
Reference implementation: https://github.com/w3f/consensus Further details: https://research.web3.foundation/en/latest/polkadot/NPoS/4.%20Sequential%20Phragm%C3%A9n%E2%80%99s%20method/
Generates a struct to store the phragmen assignments in a compact way. The struct can only store distributions up to the given input count. The given count must be greater than 2.
A voter's stake assignment among a set of targets, represented as ratios.
Final result of the phragmen election.
A voter's stake assignment among a set of targets, represented as absolute values in the scale
A structure to demonstrate the phragmen result from the perspective of the candidate, i.e. how much support each candidate is receiving.
The errors that might occur in the this crate and compact.
an aggregator trait for a generic type of a voter/target identifier. This usually maps to substrate's account id.
A trait to limit the number of votes per voter. The generated compact type will implement this.
Converts a vector of ratio assignments into ones with absolute budget value.
Converts a vector of staked assignments into ones with ratio values.
Build the support map from the given phragmen result. It maps a flat structure like
Perform election based on Phragmén algorithm.
Performs equalize post-processing to the output of the election algorithm. This happens in rounds. The number of rounds and the maximum diff-per-round tolerance can be tuned through input parameters.
Evaluate a phragmen result, given the support map. The returned tuple contains:
Compares two sets of phragmen scores based on desirability and returns true if
Reduce the given [
consumes a vector of winners with backing stake to just winners.
A type in which performing operations on vote weights are safe.
The score of an assignment. This can be computed from the support map via
A linkage from a candidate and its
A type which is used in the API of this crate as a numeric weight of a vote, most often the
stake of the voter. It is always converted to
A winner, with their respective approval stake.