# Voting systems benchmark Goals: - Accurate measurement of voting quality. - Automated reproducible comparison online. - Automated strategic voting detection. - Ability to add your own voting system into the mix and test it. We assess quality by computing statistical properties through simulated votes. ## 1. Vote setup Register C = 16 **candidates**, from which one will be elected. Generate E = 2048 **voters**. Assign a random probability s of survival to each voter assuming a given candidate is elected. That is E×C = 32768 probabilities. ## 2. Election We perform 8 simultaneous elections, in order to learn the optimal voting strategy. For each, the basic flow goes this way: 1. First, compute an honest election. The learnt outcome is used to learn a better individual strategy given our knowledge of the honest result. 2. Next, iterate through candidates and elections to build the strategic model. The model is a neural network; the learning relies on backpropagation. 3. Finally, compute a strategic election. 4. From that, we can compute the outcome, the electorate satisfaction, and the strategic honesty. ### 2.1. Honest election To compute the honest election, the voting system takes each voter’s survival probability and converts it to a ballot of its form. ```javascript // Return a score from 0 to 1 for each candidate, // where the largest score is that of the elected one. function election(electorate) { return tally(electorate.map(ballot)); } ``` For instance, in a plurality election, the ballot will name the candidate that would give the voter the largest survival probability. ```javascript // Implemented by the voting system. // In this example, it returns the index of the selected candidate. function ballot(voter) { return voter.candidates.reduce((choice, next, i) => next > candidate[choice]? i: choice, 0); } ``` For Condorcet-type methods, the candidates are ranked by their probabilities. Tiebreakers must be broken deterministically by picking a random candidate. For approval-type methods, only candidates with which the voter is more likely to survive than not, are kept in the ballot. The tally is then computed as a list of scores between 0 and 1, where the highest score is given to the elected candidate. ```javascript // Implemented by the voting system. function tally(ballots) { return ballots.reduce((counts, ballot) => counts[ballot]++, Array(16).fill(0)) .map(count => count / ballots.length); } ``` In total, the election requires at least E×C+E = 34816 operations. ### 2.2. Strategy learning The model is a feedforward neural network built in two chunks: 1. A set of layers focused on yielding the strategic vote. 2. A set of layers that, given this strategic vote (and other parameters produced by the previous chunk), try to estimate which candidate wins. #### 2.2.1. Input layer The input layer contains I = 2×C = 32 numbers between -1 and 1. (Having the numbers between -1 and 1, instead of between 0 and 1, ensures we benefit from ReLU activation functions.) Each neuron corresponds to a candidate. 1. The first set of 16 neurons list the honest individual satisfaction that the voter experiences for each candidate. In other words, it is the survival probability given that candidate is elected. 2. The second set of 16 neurons list the honest overall satisfaction that the electorate experiences for each candidate. In other words, it is the result of the honest election. #### 2.2.2. Strategic chunk The strategic chunk is a feedforward network of L = 16 layers. We can greatly reduce the memory cost of the model by exploiting the problem’s symmetries. Each layer of the strategic chunk is a series of A = 8 analyses. Each analysis yields one neuron for each candidate. That is a total of A×C = 128 neurons per layer, and A×C×L = 2048 neurons in the chunk. We persist four weights for each analysis (4×A = 32 on the first layer, 4×A×L = 512 total): - One weight w_IC multiplies the analyzed candidate’s individual honest vote, - One weight w_IO multiplies other candidates’ individual honest vote, - One weight w_EC multiplies the analyzed candidate’s election (global) result, - One weight w_EO multiplies other candidates’ election (global) result. The result then goes through a ReLU activation. Thus the computation of neuron i in the first layer, is b_i = max(0, w_{⌊i÷A⌋, IC}×x_i%C + w_{⌊i÷A⌋, EC}×x_i%C+C × Σ_k≠i (w_{⌊i÷A⌋, IO}×x_k%C + w_{⌊i÷A⌋, EO}×x_k%C+C)). The following 15 layers are similar. Unlike the first, they persist 2×A = 16 weights per analysis (thus 2×A² = 128 per layer). The computation of neurons is the same, using the previous layer’s analyses instead of individual / election results: c_i = max(0, Σ_{0 ≤ a < 8} w_{⌊i÷A⌋, a, C}×b_i%C + w_{⌊i÷A⌋, a, C}×b_i%C+C × Σ_k≠i (w_{⌊i÷A⌋, a, O}×b_k%C + w_{⌊i÷A⌋, a, O}×b_k%C+C)). In total, there are 4×A+2×A²×(L-1) = 1952 weights. In the last layer, the first analysis uses a softsign activation instead of the ReLU activation. Indeed, those neurons yield the strategic votes: y_i = z_i ÷ (|z_i| + 1). #### 2.2.3. Win chunk The first layer of the win chunk uses the last layer of the strategic chunk as input. The 16 layers of that chunk work identically to the intermediate layers of the strategic chunk. However, the output layer uses a softsign activation, which is intended to converge to the strategic election results. Therefore, the total number of weights in that chunk is 2×A²×L+2×A = 2064, for a grand total of 4016 across the whole neural network. #### 2.2.4. Learning the win To learn the win, we apply a Mean Squared Error loss function on the output layer, and backpropagate through the win chunk alone, updating its weights. #### 2.2.5. Learning the strategy To learn the strategy, we apply the sum of the hinge losses of each output, compared to the survival probability for this candidate (ie. the voter’s honest vote). We do not update the weights of the win chunk, but we backpropagate through to the strategy chunk, and we update the weights of the strategy chunk. #### 2.2.6. Optimizer gradient descent, mini-batch, learning rate, cross-validation ## 3. Quality metrics **Voter satisfaction** is computed as the expected proportion of the electorate that survives the term: S = Σ sᵢ ÷ E. The **strategic honesty** is the mean squared error over the 8 elections, between the honest votes and the strategic ones, for each voter. ## Voting systems to integrate - Random - Plurality (First-past-the-post) - Two-round (runoff) - Condorcet - Instant runoff (alternative vote) - Coombs' method - Approval voting - Score voting - Borda count - STAR voting - Majority judgement