[EM] Elections methods performance criterion

Ken Johnson kjinnovation at earthlink.net
Wed Apr 14 17:03:04 PDT 2004


This is a follow-up to my previous post, Election-methods digest, Vol 1 
#538, Message 2, in which I gave simulation results comparing 
performance of various voting methods, using Sincere CR as a comparison 
standard. I modified the simulation model to take into account 
correlations between CR's based on candidates' issue positions. The 
model assumptions are:

(1) Each candidate j has a position CP[j,k] with respect to each issue k 
(CP = "candidate position"), with -1 <= CP[j,k] <= 1. The probability 
that candidate j will adequately represent the interests of issue-k 
proponents is (1+CP[j,k])/2; the probability that the candidate will 
adequately represent opponents' interests is (1-CP[j,k])/2.

(2) Each voter i assigns a signed weight W[i,k] to each issue k. The 
sign of W[i,k] is positive if the voter is a proponent of issue k, and 
negative if the voter is an opponent.

(3) Each voter i assigns to each candidate j a sincere cardinal rating 
CR[i,j], which is a weighted average of the candidate's issue weights:
    CR[i,j] = (sum|k  W[i,k]*CP[j,k]) / (sum|k  abs(W[i,k]))

The simulation generates CP's and W's randomly, computes sincere CR's as 
above, and creates simulated ballots based on the CR's. Various election 
methods are applied to the ballots, and the winners are compared in 
terms of their voter-averaged sincere CR's. The winner's average CR 
cannot exceed that of an "optimal consensus candidate" whose issue 
positions are adapted to the majority view on every issue, and the 
winners' average CR's are tabulated as fractions of the maximum possible 
average CR.

I haven't modeled strategic voting except for the most trivial strategy: 
Exaggerate. Also, a couple caveats from Forest Simmons:

"(1) treating ten issues as independent or uncorrelated; I think that 
the two or three dimensional issue space would better represent typical 
politics.  This should be taken into account when interpreting the results.

"(2) using only uncorrelated candidate positions doesn't test a method's 
independence from clones, so in a sense, methods like Borda and Copeland 
would be given an unfair advantage.  Again this fact can be mitigated if 
taken into account when interpreting the results."

The modeled election methods are as follows:

(1) SincereCR: Sincere cardinal rating. (CR's are signed and 
unquantized, -1 <= CR <= 1)

(2) ExaggerateCR: Voters exaggerate their CR's so that each voter's min 
and max CR's are -1 and +1.

(3) NormalizeCR: Similar to SincereCR, except voters' CR's are linearly 
transformed to remove the incentive to give exaggerated or polarized 
(approval-type) ratings. Each voter's CR's are transformed as follows: 
First apply an additive shift so that the average is zero. Then apply a 
multiplicative scale shift so that the sum of the absolute values is 1. 
The resulting CR's satisfy the normalization conditions,
    (sum|j  CR[i,j]) = 0
    (sum|j  abs(CR[i,j])) = 1

(4) SincereAV: Sincere Approval Voting (CR >= 0: approve; CR < 0: 
disapprove)

(5) ExaggerateAV: Similar to SincereAV, except based on exaggerated 
CR's. (SincereCR, ExaggerateCR, and SincereAV are strategically 
equivalent to ExaggerateAV.)

(6) Majority: Condorcet with MinMax cycle resolution.

(7) Borda

(8) IRV: Instant Runoff Voting

(9) Top2Runoff

(10) Plurality

(11) RandV: Let a randomly-selected voter decide the election.

(12) RandC: Pick the winning candidate by random selection.

One thing that I find surprising in the results is the relatively poor 
performance of Approval when there are many candidates and few issues 
(e.g., see results for num_candidate=10, num_issue=1). Perhaps a rating 
method such as NormalizeCR could alleviate this deficiency. The 
advantage of such a method over Majority is that voters could express 
degrees of preference, but there may be significant drawbacks in terms 
of strategy.

Simulation conditions:
number of voters: 10 or 100
number of candidates: 2, 3, or 10
number of issues: 1, 2, 3, or 10

Results:

num_voter=10
num_candidate=2
num_issue=1
num_election=100000
runtime (sec): 445.11
 
Voter-averaged CR of optimal consensus candidate:
                  0.245708

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.33558
ExaggerateCR  0.33558
NormalizeCR   0.33558
SincereAV     0.2516
ExaggerateAV  0.33558
Majority      0.33558
Borda         0.33558
IRV           0.33558
Top2Runoff    0.33558
Plurality     0.33558
RandV         0.13872
RandC         0.0040805
 
 
num_voter=10
num_candidate=2
num_issue=2
num_election=100000
runtime (sec): 395.749
 
Voter-averaged CR of optimal consensus candidate:
         0.280415825934413

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.26196
ExaggerateCR  0.22738
NormalizeCR   0.22743
SincereAV     0.21115
ExaggerateAV  0.22738
Majority      0.22738
Borda         0.22738
IRV           0.22738
Top2Runoff    0.22738
Plurality     0.22738
RandV         0.093214
RandC         0.00055697
 
 
num_voter=10
num_candidate=2
num_issue=3
num_election=100000
runtime (sec): 380.657
 
Voter-averaged CR of optimal consensus candidate:
         0.288060615687464

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.22152
ExaggerateCR  0.18528
NormalizeCR   0.18525
SincereAV     0.17918
ExaggerateAV  0.18528
Majority      0.18528
Borda         0.18528
IRV           0.18528
Top2Runoff    0.18528
Plurality     0.18528
RandV         0.075896
RandC         -0.00046545
 
 
num_voter=10
num_candidate=2
num_issue=10
num_election=100000
runtime (sec): 398.653
 
Voter-averaged CR of optimal consensus candidate:
         0.292289649191725

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.12667
ExaggerateCR  0.10077
NormalizeCR   0.10058
SincereAV     0.10044
ExaggerateAV  0.10077
Majority      0.10077
Borda         0.10077
IRV           0.10077
Top2Runoff    0.10077
Plurality     0.10077
RandV         0.041258
RandC         0.00068772
 
 
num_voter=10
num_candidate=3
num_issue=1
num_election=100000
runtime (sec): 411.072
 
Voter-averaged CR of optimal consensus candidate:
                   0.24496

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.49674
ExaggerateCR  0.49674
NormalizeCR   0.49674
SincereAV     0.37219
ExaggerateAV  0.43482
Majority      0.49674
Borda         0.49674
IRV           0.49674
Top2Runoff    0.46506
Plurality     0.49674
RandV         0.20365
RandC         -0.0020013
 
 
num_voter=10
num_candidate=3
num_issue=2
num_election=100000
runtime (sec): 391.232
 
Voter-averaged CR of optimal consensus candidate:
          0.28119221778613

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.39218
ExaggerateCR  0.37023
NormalizeCR   0.36944
SincereAV     0.31576
ExaggerateAV  0.34442
Majority      0.35459
Borda         0.35485
IRV           0.32944
Top2Runoff    0.31469
Plurality     0.33115
RandV         0.13999
RandC         0.00089587
 
 
num_voter=10
num_candidate=3
num_issue=3
num_election=100000
runtime (sec): 392.615
 
Voter-averaged CR of optimal consensus candidate:
         0.288457153147491

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.33248
ExaggerateCR  0.30804
NormalizeCR   0.30792
SincereAV     0.26825
ExaggerateAV  0.28964
Majority      0.29264
Borda         0.29471
IRV           0.26802
Top2Runoff    0.25626
Plurality     0.26859
RandV         0.11432
RandC         0.0007901
 
 
num_voter=10
num_candidate=3
num_issue=10
num_election=100000
runtime (sec): 395.969
 
Voter-averaged CR of optimal consensus candidate:
         0.292561012951434

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.18907
ExaggerateCR  0.17043
NormalizeCR   0.17028
SincereAV     0.14972
ExaggerateAV  0.16076
Majority      0.15895
Borda         0.16194
IRV           0.14603
Top2Runoff    0.13899
Plurality     0.14477
RandV         0.060336
RandC         -0.00062398
 
 
num_voter=10
num_candidate=10
num_issue=1
num_election=100000
runtime (sec): 538.465
 
Voter-averaged CR of optimal consensus candidate:
                   0.24598

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.81886
ExaggerateCR  0.81886
NormalizeCR   0.81886
SincereAV     0.49891
ExaggerateAV  0.50045
Majority      0.81886
Borda         0.81886
IRV           0.81886
Top2Runoff    0.81807
Plurality     0.81886
RandV         0.33304
RandC         -0.00055643
 
 
num_voter=10
num_candidate=10
num_issue=2
num_election=100000
runtime (sec): 574.095
 
Voter-averaged CR of optimal consensus candidate:
         0.281618804665733

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.66589
ExaggerateCR  0.65865
NormalizeCR   0.65399
SincereAV     0.47957
ExaggerateAV  0.48077
Majority      0.62611
Borda         0.62719
IRV           0.52048
Top2Runoff    0.53351
Plurality     0.51374
RandV         0.23658
RandC         0.001797
 
 
num_voter=10
num_candidate=10
num_issue=3
num_election=100000
runtime (sec): 611.67
 
Voter-averaged CR of optimal consensus candidate:
         0.288010050660844

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.57492
ExaggerateCR  0.56471
NormalizeCR   0.56178
SincereAV     0.42965
ExaggerateAV  0.43484
Majority      0.53326
Borda         0.53644
IRV           0.43632
Top2Runoff    0.43217
Plurality     0.41278
RandV         0.19659
RandC         0.0017932
 
 
num_voter=10
num_candidate=10
num_issue=10
num_election=100000
runtime (sec): 616.576
 
Voter-averaged CR of optimal consensus candidate:
         0.292472777941538

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.33975
ExaggerateCR  0.33068
NormalizeCR   0.33089
SincereAV     0.26231
ExaggerateAV  0.26942
Majority      0.30958
Borda         0.31591
IRV           0.25064
Top2Runoff    0.24462
Plurality     0.21834
RandV         0.11044
RandC         0.00058673
 
 
num_voter=100
num_candidate=2
num_issue=1
num_election=100000
runtime (sec): 542.379
 
Voter-averaged CR of optimal consensus candidate:
                  0.079407

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.33425
ExaggerateCR  0.33425
NormalizeCR   0.33425
SincereAV     0.25069
ExaggerateAV  0.33425
Majority      0.33425
Borda         0.33425
IRV           0.33425
Top2Runoff    0.33425
Plurality     0.33425
RandV         0.042568
RandC         0.0018552
 
 
num_voter=100
num_candidate=2
num_issue=2
num_election=100000
runtime (sec): 501.21
 
Voter-averaged CR of optimal consensus candidate:
        0.0886916303750231

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.26218
ExaggerateCR  0.23448
NormalizeCR   0.23464
SincereAV     0.21602
ExaggerateAV  0.23448
Majority      0.23448
Borda         0.23448
IRV           0.23448
Top2Runoff    0.23448
Plurality     0.23448
RandV         0.027867
RandC         0.0020244
 
 
num_voter=100
num_candidate=2
num_issue=3
num_election=100000
runtime (sec): 514.13
 
Voter-averaged CR of optimal consensus candidate:
        0.0905220457812579

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.21986
ExaggerateCR  0.18847
NormalizeCR   0.1884
SincereAV     0.17999
ExaggerateAV  0.18847
Majority      0.18847
Borda         0.18847
IRV           0.18847
Top2Runoff    0.18847
Plurality     0.18847
RandV         0.022584
RandC         -0.00065332
 
 
num_voter=100
num_candidate=2
num_issue=10
num_election=100000
runtime (sec): 531.424
 
Voter-averaged CR of optimal consensus candidate:
        0.0921764480931304

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.12685
ExaggerateCR  0.10336
NormalizeCR   0.10325
SincereAV     0.10187
ExaggerateAV  0.10336
Majority      0.10336
Borda         0.10336
IRV           0.10336
Top2Runoff    0.10336
Plurality     0.10336
RandV         0.012556
RandC         0.00077983
 
 
num_voter=100
num_candidate=3
num_issue=1
num_election=100000
runtime (sec): 542.28
 
Voter-averaged CR of optimal consensus candidate:
                 0.0798578

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.49998
ExaggerateCR  0.49998
NormalizeCR   0.49998
SincereAV     0.37553
ExaggerateAV  0.4374
Majority      0.49998
Borda         0.49998
IRV           0.49998
Top2Runoff    0.46925
Plurality     0.49998
RandV         0.05842
RandC         -0.0044023
 
 
num_voter=100
num_candidate=3
num_issue=2
num_election=100000
runtime (sec): 565.713
 
Voter-averaged CR of optimal consensus candidate:
        0.0884947266777429

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.39236
ExaggerateCR  0.36996
NormalizeCR   0.37006
SincereAV     0.32138
ExaggerateAV  0.34915
Majority      0.35802
Borda         0.35767
IRV           0.33137
Top2Runoff    0.29928
Plurality     0.24892
RandV         0.046009
RandC         0.0023027
 
 
num_voter=100
num_candidate=3
num_issue=3
num_election=100000
runtime (sec): 575.238
 
Voter-averaged CR of optimal consensus candidate:
        0.0906803128096646

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.33092
ExaggerateCR  0.30616
NormalizeCR   0.30605
SincereAV     0.27058
ExaggerateAV  0.29157
Majority      0.29112
Borda         0.29371
IRV           0.26441
Top2Runoff    0.24352
Plurality     0.20019
RandV         0.035209
RandC         0.0007397
 
 
num_voter=100
num_candidate=3
num_issue=10
num_election=100000
runtime (sec): 599.632
 
Voter-averaged CR of optimal consensus candidate:
        0.0922030460767445

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.18918
ExaggerateCR  0.16964
NormalizeCR   0.16975
SincereAV     0.15152
ExaggerateAV  0.16215
Majority      0.15834
Borda         0.16237
IRV           0.14498
Top2Runoff    0.13942
Plurality     0.12194
RandV         0.01976
RandC         -0.00084813
 
 
num_voter=100
num_candidate=10
num_issue=1
num_election=100000
runtime (sec): 1027.537
 
Voter-averaged CR of optimal consensus candidate:
                 0.0796558

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.81924
ExaggerateCR  0.81924
NormalizeCR   0.81924
SincereAV     0.50012
ExaggerateAV  0.50013
Majority      0.81924
Borda         0.81924
IRV           0.81924
Top2Runoff    0.81859
Plurality     0.81924
RandV         0.10052
RandC         -0.0016341
 
 
num_voter=100
num_candidate=10
num_issue=2
num_election=100000
runtime (sec): 1247.093
 
Voter-averaged CR of optimal consensus candidate:
        0.0888420877069938

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.66643
ExaggerateCR  0.65901
NormalizeCR   0.65392
SincereAV     0.48799
ExaggerateAV  0.49059
Majority      0.62469
Borda         0.62673
IRV           0.49779
Top2Runoff    0.50661
Plurality     0.37561
RandV         0.076805
RandC         -0.00029596
 
 
num_voter=100
num_candidate=10
num_issue=3
num_election=100000
runtime (sec): 1370.911
 
Voter-averaged CR of optimal consensus candidate:
        0.0906677186917281

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.57514
ExaggerateCR  0.56468
NormalizeCR   0.5615
SincereAV     0.4373
ExaggerateAV  0.44232
Majority      0.53052
Borda         0.53576
IRV           0.40001
Top2Runoff    0.40182
Plurality     0.29703
RandV         0.061886
RandC         -0.00033832
 
 
num_voter=100
num_candidate=10
num_issue=10
num_election=100000
runtime (sec): 1454.422
 
Voter-averaged CR of optimal consensus candidate:
        0.0921563662815433

Voter-averaged CR of winning candidate relative to optimal candidate:
SincereCR     0.34035
ExaggerateCR  0.33062
NormalizeCR   0.33092
SincereAV     0.26808
ExaggerateAV  0.27474
Majority      0.30596
Borda         0.31627
IRV           0.23237
Top2Runoff    0.22159
Plurality     0.17128
RandV         0.035123
RandC         0.00078996









More information about the Election-Methods mailing list