[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