ElectionsPhragmen

Overview

  • Phragmén’s method: is to solve the problem of electing a set of given numbers of persons from a larger set of candidates. It is used in the council election mechanism. When you vote for council members, you can select up to 16 different candidates, and then place a reserved bond as the weight of your vote. Phragmén will run once in every election to determine the top candidates to assume council positions and then again amongst the top candidates to equalize the weight of the votes behind them as much as possible.
  • Term duration: The length of a council member's term until the next election round.
  • Voting period: The council's voting period for motions

Diagram

Phragmen Algorithm

Elections for the Glitch Council are weighted by the number of tokens held by the voters. It’s called Weighted Phragmen. Based on this algorithm, candidates are selected sequentially, one per round, until the maximum number of candidates are elected. The currently proposed number of council is 13 (this figure can be decided for configuration later by the developer team)
  • Step 1: Create a list of all voters, their total amount of stake, and which validators they support.
  • Step 2: Generate an initial edge-weighted graph mapping from voters to candidates, where each edge weight is the total potential weight (stake) given by that voter. The sum of all potential weight for a given candidate is called their approval stake.
  • Step 3: Now we start electing candidates. For the list of all candidates who have not been elected, get the initial score:
initial score = 1/approval_stake
  • Step 4: For each voter, update the score of each candidate they support by adding their total budget (stake) multiplied by the load of the voter and then dividing by that candidate's approval stake.
Score = (voter_budget * voter_load / candidate_approval_stake)
  • Step 5: Determine the candidate with the lowest score and elect that candidate to become a council member. Then remove the elected candidate from the pool of potential candidates.
  • Step 6: The edge load connecting to the winning candidate is updated, with the edge load set to the score of the candidate minus the voter's load, and the voter's load is then set to the candidate's score.
edge_load = elected_candidate_score - voter_load
voter_load = elected_candidate_score
  • Step 7: Check whether there is enough selected member. If there are more candidates needed to elect, go to Step 3. Otherwise, continue to step 8.
  • Step 8: Now the stake is distributed amongst each nominator who backed at least one elected candidate. The backing stake for each candidate is calculated by taking the budget of the voter and multiplying by the edge load then dividing by the candidate load
Stake backing = (voter_budget * edge_load / candidate_load)
Note that after term durationis set to 3 days. Term duration is calculated equal to certain number of blocks created in this duration. When creating a new block after this duration, Glitch updates council member list.
Example Note: All numbers in this example are rounded off to three decimal places.
In the following example, there are five voters and five candidates vying for three potential seats. Each voter V1 - V5 has an amount of stake equal to their number (e.g., V1 has a stake of 1, V2 has a stake of 2, etc.). Every voter is also going to have a load, which initially starts at 0.
Initial Round
Filled seats: 0 Open Seats: 3
Candidates
A
B
C
D
E
L0
Voter V1 (1)
X
X
0
Voter V2 (2)
X
X
0
Voter V3 (3)
X
0
Voter V4 (4)
X
X
X
0
Voter V5 (5)
X
X
0
Now we calculate the approval stake of each of the candidates. Recall that this is merely the amount of all support for that candidate by all voters.
Candidate A: 1 + 2 + 3 + 5 = 11 Candidate B: 1 + 2 + 4 = 7 Candidate C: 4 = 4 Candidate D: 4 + 5 = 9 Candidate E: 0
The first step is easy - the candidate E has 0 approval stake and can be ignored from here on out. They will never be elected.
We can now calculate the initial scores of the candidates, which is 1 / approval_stake:
Candidate A: 1 / 11 = 0.091 Candidate B: 1 / 7 = 0.143 Candidate C: 1 / 4 = 0.25 Candidate D: 1 / 9 = 0.111 Candidate E: N/A
or every edge, we are going to calculate the score, which is current score plus the total budget * the load of the voter divided by the approval stake of the candidate. However, since the load of every voter starts at 0, and anything multiplied by 0 is 0, any addition will be 0 / x, or 0. This means that this step can be safely ignored for the initial round.
Thus, the best (lowest) score for Round 0 is Candidate A, with a score of 0.091.
Filled seats: 1 (A)
Open Seats: 2
Candidates
A
B
C
D
E
L0
L1
Voter V1 (1)
X
X
0
0.091
Voter V2 (2)
X
X
0
0.091
Voter V3 (3)
X
0
0.091
Voter V4 (4)
X
X
X
0
Voter V5 (5)
X
X
0
0.091
Round 2
Candidate A is now safe; there is no way that they will lose their seat. Before moving on to the next round, we need to update the scores on the edges of our graph for any candidates who have not yet been elected.
We elided this detail in the previous round since it made no difference to the final scores, but we should go into depth here to see how scores are updated. We first must calculate the new loads of the voters, and then calculate the new scores of the candidates.
Any voter who had one of their choices for candidate fill the seat in this round (i.e., voters V1, V2, V3, and V5, who all voted for A) will have their load increased. This load increase will blunt the impact of their vote in future rounds, and the edge (which will be used in determining stake allocation later) is set to the score of the elected candidate minus the current voter load.
edge_load = elected_candidate_score - voter_load
voter_load = elected_candidate_score
n this instance, the score of the elected candidate 0.091 and the voter loads are all 0. So for each voter who voted A, we will calculate a new edge load Voter -> A of:
Edge load: 0.091 - 0 = 0.091
Voter load: 0.091
As a reminder, here are the current scores. Loads of the voters are all 0.
Candidate B : 0.143
Candidate C : 0.25
Candidate D : 0.111
Now, we go through the weighted graph and update the score of the candidate and the load of the edge, using the algorithm:
candidate_score = candidate_score + ((voter_budget * voter_load) / candidate_approval_stake)
V1 updates B = 0,143 + (1* 0,091)/7
V1 updates B= 0,143 + (1* 0,091)/7= 0.156
V2 updates B= 0,156 + (2* 0,091)/7= 0.182
V4 updates B= 0,182 + (4* 0,091)/7= 0.182
V4 updates C to 0.25
V4 updates D to 0.111
V5 updates D to 0.162
After scores are updated, the final scores for the candidates for this round are:
Candidate B: 0.182
Candidate C: 0.25
Candidate D: 0.162
D, with the lowest score, is elected. You will note that even though the candidate B had more voters supporting them, the candidate D won the election due to their lower score. This is directly due to the fact that they had the lowest score, of course, but the root reason behind them having a lower score was both the greater amount of stake behind them and that voters who did not get one of their choices in an earlier round (in this example, voter V4) correspond to a higher likelihood of a candidate being elected.
We then update the loads for the voters and edges as specified above for any voters who voted for candidate D (viz., V4 and V5) using the same formula as above.
Candidates
A
B
C
D
E
L0
L1
L2
Voter V1 (1)
X
X
0
0.091
0.091
Voter V2 (2)
X
X
0
0.091
0.091
Voter V3 (3)
X
0
0.091
0.091
Voter V4 (4)
X
X
X
0
0.162
Voter V5 (5)
X
X
0
0.091
0.162
Round 3
Following a similar process for Round 2, we start with initial candidate scores of:
Candidate B : 0.143
Candidate C : 0.25
We can then update the scores of the remaining two candidates according to the algorithm described above.
V1 updates B to 0.156
V2 updates B to 0.182
V4 updates B to 0.274
V4 updates C to 0.412
With the lowest score of 0.274, Candidate B claims the last open seat. Candidates A, D, and B have been elected, and candidates C and E are not.
Before moving on, we must perform a final load adjustment for the voters and the graph.
Candidates
A
B
C
D
E
L0
L1
L2
L3
Voter V1 (1)
X
X
0
0.091
0.091
0.274
Voter V2 (2)
X
X
0
0.091
0.091
0.274
Voter V3 (3)
X
0
0.091
0.091
0.091
Voter V4 (4)
X
X
X
0
0.162
0.274
Voter V5 (5)
X
X
0
0.091
0.162
0.162
Now we have to determine how much stake every voter should allocate to each candidate. This is done by taking the load of each edge and dividing it by the voter load, then multiplying it by the total budget of the voter.
Nominator: V1
Edge to A load= 0.091 - 0 = 0,091
Edge to B load= 0,274 - 0,091 = 0.183
Nominator: V2
Edge to A load= 0.091 - 0 = 0,091
Edge to B load= 0,274 - 0,091 = 0.183
Nominator: V3
Edge to A load= 0.091
Nominator: V4
Edge to B load= 0.113
Edge to D load= 0.162
Nominator: V5
Edge to A load= 0.091
Edge to D load= 0.071
For instance, the budget of V1 is 1, the edge load to A is 0.091, and the voter load is 0.274. Using our equation:
backing_stake (A) = voter_budget * edge_load / voter_load
We can fill these variables in with:
backing_stake (A) = 1 * 0.091 / 0.274 = 0.332
For V1 backing stake of B, you can simply replace the edge load value and re-calculate.
backing_stake (B) = 1 * 0.183 / 0.274 = 0.668
Note that the total amount of all backing stake for a given voter will equal the total budget of the voter unless that voter had no candidates elected, in which case it will be 0.
The final results are:
A is elected with stake 6.807.
D is elected with stake 4.545.
B is elected with stake 3.647.
V1 supports: A with stake: 0.332 and B with stake: 0.668.
V2 supports: A with stake: 0.663 and B with stake: 1.337.
V3 supports: A with stake: 3.0.
V4 supports: B with stake: 1.642 and D with stake: 2.358.
V5 supports: A with stake: 2.813 and D with stake: 2.187.
You will notice that the total amount of stake for candidates A, D, and B equals (aside from rounding errors) the total amount of stake of all the voters (1 + 2 + 3 + 4 + 5 = 15). This is because each voter had at least one of their candidates fill a seat. Any voter who had none of their candidates selected will also not have any stake in any of the elected candidates.
Last modified 1yr ago