search

paritytech / substrate

Substrate: The platform for blockchain innovators
Apache License 2.0
8.39k stars 2.65k forks source link

Prime member selection in Phragmen Elections #5290

Closed gavofyork closed 4 years ago

gavofyork commented 4 years ago

Phragmen doesn't allow preference voting among the approvals, so prime member selection will need to be done independently of the Phragmen election. For now it can just select according to https://en.wikipedia.org/wiki/Borda_count, since it's O(m.n) in candidates/voters and computable progressively with a state O(n) in candidates. Ranked pairs or Schulze might be a better choice at some point in the future.

AlfonsoCev commented 4 years ago

I had a look on the ranked pairs and Schulze methods. I great source is Chapter 4 of this book. Both methods take time O(n.m^2) and require space O(m^2), for n voters and m candidates. If we run either method only on the elected council members, so that m <= 24, then the complexities are not too bad. The runtime would likely still be dominated by the seqPhragmen algorithm to elect the council members.

The best method seems to be ranked pairs, as it satisfies a bunch of desirable criteria, see here.