Crate sp_phragmen

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 elect function 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/

Macros

generate_compact_solution_type

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.

Structs

Assignment

A voter’s stake assignment among a set of targets, represented as ratios.

PhragmenResult

Final result of the phragmen election.

StakedAssignment

A voter’s stake assignment among a set of targets, represented as absolute values in the scale of ExtendedBalance.

Support

A structure to demonstrate the phragmen result from the perspective of the candidate, i.e. how much support each candidate is receiving.

Enums

Error

The errors that might occur in the this crate and compact.

Traits

IdentifierT

an aggregator trait for a generic type of a voter/target identifier. This usually maps to substrate’s account id.

VotingLimit

A trait to limit the number of votes per voter. The generated compact type will implement this.

Functions

assignment_ratio_to_staked

Converts a vector of ratio assignments into ones with absolute budget value.

assignment_staked_to_ratio

Converts a vector of staked assignments into ones with ratio values.

build_support_map

Build the support map from the given phragmen result. It maps a flat structure like

elect

Perform election based on Phragmén algorithm.

equalize

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_support

Evaluate a phragmen result, given the support map. The returned tuple contains:

is_score_better

Compares two sets of phragmen scores based on desirability and returns true if that is better than this.

reduce

Reduce the given Vec<StakedAssignment<IdentifierT>>. This removes redundant edges from without changing the overall backing of any of the elected candidates.

to_without_backing

consumes a vector of winners with backing stake to just winners.

Type Aliases

ExtendedBalance

A type in which performing operations on vote weights are safe.

PhragmenScore

The score of an assignment. This can be computed from the support map via evaluate_support.

SupportMap

A linkage from a candidate and its Support.

VoteWeight

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 ExtendedBalance for computation.

WithApprovalOf

A winner, with their respective approval stake.