Crate sp_npos_elections

A set of election algorithms to be used with a substrate runtime, typically within the staking sub-system. Notable implementation include

• seq_phragmen: Implements the Phragmén Sequential Method. An un-ranked, relatively fast election method that ensures PJR, but does not provide a constant factor approximation of the maximin problem.
• balance_solution: Implements the star balancing algorithm. This iterative process can increase a solutions score, as described in evaluate_support.

More information can be found at: https://arxiv.org/abs/2004.12990

Macros

generate_solution_type

Generates a struct to store the election result in a small way. This can encode a structure which is the equivalent of a sp_npos_elections::Assignment<_>.

Structs

Assignment	A voter's stake assignment among a set of targets, represented as ratios.
ElectionResult	Final result of the 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 election 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_ratio_to_staked_normalized	Same as assignment_ratio_to_staked and try and do normalization.
assignment_staked_to_ratio	Converts a vector of staked assignments into ones with ratio values.
assignment_staked_to_ratio_normalized	Same as assignment_staked_to_ratio and try and do normalization.
balance_solution	Performs balancing 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.
build_support_map	Build the support map from the given election result. It maps a flat structure like
evaluate_support	Evaluate a support map. The returned tuple contains:
is_score_better	Compares two sets of election scores based on desirability and returns true if this is better than that.
reduce	Reduce the given [Vec<StakedAssignment<IdentifierT>>]. This removes redundant edges from without changing the overall backing of any of the elected candidates.
seq_phragmen	Perform election based on Phragmén algorithm.
to_without_backing	consumes a vector of winners with backing stake to just winners.

Type Definitions

ElectionScore	The score of an assignment. This can be computed from the support map via evaluate_support.
ExtendedBalance	A type in which performing operations on vote weights are safe.
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.