[EM] summary of order reversal software output (6/6/1999)
Steve Eppley
SEppley at alumni.caltech.edu
Mon Jun 7 13:55:41 PDT 1999
I've corrected the bug implied by Markus's comment to my previously
posted summary. I've also tested some additional methods since then,
including Paul Dumais' method and Nanson's method.
--Steve
--------------
Markus wrote:
> Steve wrote:
> -snip-
> > Method "Schz" is Schulze's Method. Though it appears to
> > perform worse than VA on most stats, it might perform
> > better with more than 3 alternatives.
> -snip-
>
> This is surprising because (if there are less than four
> candidates) Schulze's Method is identical to VA.
Thanks for the feedback. There was indeed a bug in the
software, which is now fixed. Further down in this message
is the corrected output. (There could still be other bugs
in the basic algorithm or in other voting methods' subroutines,
since I haven't put much effort into validating the software.)
The following two paragraphs explain the bug:
I intended for the software to not include any ties in the
database, since I didn't want the results to depend on my
choice of tiebreaker algorithms. Since ties will be rare
with large numbers of voters, not including tied scenarios
shouldn't invalidate any comparitive conclusions. (I made
an exception for Copeland, where ties are expected to be
frequent. Since its advocate, Bruce Anderson, recommends
the Plurality tiebreaker, I programmed Copeland//Plurality
instead of plain Copeland.)
Some tie scenarios were accidentally included as reversal
scenarios in the Schz database. For instance, I'd erroneously
assumed that A and C couldn't tie for first in a scenario
where B is the sincere condorcet winner. I tracked down
my Schz bugs, I think, and debugged and reran the software.
At the bottom of this message I'm appending the new version of
the Schz subroutine in case Markus or someone else wishes to
inspect it for errors.
* *
Below is the latest output from the software. As Markus noted,
the numbers for Schz match the numbers for VA.
Here are method definitions which weren't stated in my previously
posted summary:
Nans is Nanson's "iterative Borda" method. Each iteration
eliminates the contender with the worst Borda score.
Duma is Paul Dumais' "iterative Borda" variation. Each iteration
eliminates the contenders with a below average Borda score.
IVA is iterative VA. Each iteration eliminates the contender
which has the largest pairloss to an uneliminated alternative.
IIVA is iterative InductiveVA. InductiveVA uses VA to tally
a collective order "inductively": the nth place finisher is
tallied by ignoring preferences regarding the 1st thru n-1th
finishers. IIVA iteratively eliminates the contender which
finishes last in InductiveVA. (With only three alternatives,
IIVA behaves the same as VA.)
(The above four methods satisfy the top cycle criterion, even
though they do not explicitly reference cycles. In general,
any iterative elimination method which eliminates only pairlosers
and eliminates only one at a time satisfies the top cycle criterion.)
TC1 eliminates those outside the top cycle.
If more than one remains, the winner is found as follows:
Let P be the Plurality winner (ignoring preferences
regarding those which have been eliminated).
Define "supporters of alternative Y" as the voters who
ranked Y ahead of any other member of the top cycle.
For all alternatives X and Y,
if X beat P pairwise and Y beat X pairwise,
if most supporters of Y ranked X ahead of P
then Y is eliminated.
Finally the Plurality winner is recalculated, ignoring
preferences regarding those which have been eliminated,
and this Plurality winner is elected.
TC2 eliminates those outside the top cycle.
If more than one remains, the winner is found as follows:
Define ratio(i,j,k):
if i, j, and k are uneliminated alternatives
and j beat i pairwise and k beat j pairwise
ratio(i,j,k) = the number of "k>i>j" voters divided
by the number of "k>j>i" voters
else
ratio(i,j,k) = 0
endif
For each alternative Y a score is tallied:
score(Y) = max(ratio(i,j,Y)) over all i,j.
The winner is the pairwinner of the two highest-scoring
uneliminated alternatives.
Given TC1 or TC2 (or Instant Runoff), some voters might attempt a
"drastic" reversal strategy -- ranking a less preferred alternative
ahead of a favorite. The software as written does not test for
when this strategy can succeed, by itself or combined with ordinary
reversal. Since this strategy can backfire if too many attempt
it, it would presumably be harder to organize this strategy than
ordinary reversal -- except in methods where ordinary reversal can
also backfire, which would presumably also be hard to organize.
SK is Simpson-Kramer. The winner is the alternative whose
largest pairwise opposition (in both pairwins and pairlosses)
is the smallest.
WL is the "MaxWin-MaxLoss" method. It elects the alternative
with the largest (max(pairwin) - max(pairloss)).
VOTERS METHOD CWS REVERSALS JITWFOILED BACKFIRES AVGREV MINREV MINREVS JITWMINREV BORDAWORSE MINRBORDA FAILSDSC BORDAWORST BORDAAVG THWARTMAX THWARTAVG
17 Cope 1254 239 239 0 17.9 1 51 51 160 18 164 0.70 0.94 58.8 54.2
17 Nans 1254 361 283 0 23.7 2 64 40 277 28 75 0.71 0.91 64.7 54.5
17 Duma 1254 409 317 0 23.4 2 84 56 278 28 44 0.71 0.94 64.7 54.0
17 IIVA 1254 292 230 0 24.0 2 56 39 161 0 0 0.75 0.97 58.8 53.7
17 IVA 1254 256 212 0 24.7 2 28 17 226 28 50 0.67 0.87 70.6 55.7
17 SK 1254 292 230 0 24.0 2 56 39 161 0 0 0.75 0.97 58.8 53.7
17 Schz 1254 292 230 0 24.0 2 56 39 161 0 0 0.75 0.97 58.8 53.7
17 TC1 1254 75 57 0 7.8 1 51 39 72 48 0 0.46 0.78 88.2 63.3
17 TC2 1254 79 38 13 12.9 1 26 12 65 18 15 0.64 0.88 70.6 57.6
17 VA 1254 292 230 0 24.0 2 56 39 161 0 0 0.75 0.97 58.8 53.7/
17 WL 1254 585 386 36 19.7 1 105 63 339 0 0 0.72 0.96 64.7 54.8
VOTERS METHOD CWS REVERSALS JITWFOILED BACKFIRES AVGREV MINREV MINREVS JITWMINREV BORDAWORSE MINRBORDA FAILSDSC BORDAWORST BORDAAVG THWARTMAX THWARTAVG
18 Cope 1584 140 140 0 20.7 2 34 34 116 21 92 0.71 0.90 61.1 56.5
18 Nans 1584 204 173 0 26.0 3 46 34 185 36 20 0.72 0.88 61.1 56.6
18 Duma 1584 226 191 0 25.8 3 56 43 191 36 0 0.72 0.90 61.1 56.3
18 Schz 1584 154 132 0 26.4 3 35 28 119 15 0 0.76 0.93 61.1 56.1
18 TC1 1584 48 41 0 12.7 2 34 29 48 34 0 0.52 0.78 83.3 63.8
18 TC2 1584 36 23 6 16.7 2 13 8 34 11 4 0.70 0.86 66.7 58.8
18 VA 1584 154 132 0 26.4 3 35 28 119 15 0 0.76 0.93 61.1 56.1
VOTERS METHOD CWS REVERSALS JITWFOILED BACKFIRES AVGREV MINREV MINREVS JITWMINREV BORDAWORSE MINRBORDA FAILSDSC BORDAWORST BORDAAVG THWARTMAX THWARTAVG
33 Cope 27132 5788 5739 0 15.8 1 680 673 4008 250 3892 0.66 0.94 63.6 54.0
33 Nans 27132 8049 5989 0 21.0 2 316 160 6379 120 1798 0.69 0.92 63.6 54.2
33 Duma 27132 9749 6703 0 20.1 2 680 368 6523 120 1016 0.69 0.95 63.6 53.5
33 IVA 27132 6218 4926 0 21.6 2 120 60 5502 120 1364 0.63 0.88 72.7 55.3
33 Schz 27132 8219 5662 0 20.4 2 560 308 4993 0 0 0.71 0.97 63.6 53.3
33 TC1 27132 1896 1442 0 6.6 1 680 504 1800 621 0 0.40 0.80 93.9 62.1
33 TC2 27132 3876 2106 1943 11.2 1 732 386 3018 492 1070 0.48 0.89 84.8 58.3
33 VA 27132 8219 5662 0 20.4 2 560 308 4993 0 0 0.71 0.97 63.6 53.3
Key to columns
--------------
CWs = number of scenarios where B is the sincere condorcet winner
but not the favorite of a majority.
Reversals = number of scenarios where "ABC -> ACB" reversal can elect A.
(Smaller is better.)
JITWFoiled = number of scenarios where reversal would probably be
foiled by C voluntarily withdrawing. (CBA/C > 60%)
(Larger is better, but this is relative to Reversals.)
Backfires = number of scenarios where reversal can succeed but
too much reversing backfires by electing C.
AvgRev = average amount of reversing needed to succeed, expressed
as a percentage of the total voters.
(Larger is better.)
MinRev = minimum number of reversers needed to reverse at least
one scenario. (Larger is better.)
(I don't know if this stat matters. It's probably
3 or less regardless of how many voters there are.)
MinRevs = number of scenarios where the number of reversers needed
to successfully reverse equals MinRev.
(Smaller is better.)
(I don't know if this stat is useful, especially
since it depends on the method's MinRev.)
JITWMinRev = number of MinRevs scenarios where reversal would probably
be foiled by C voluntarily withdrawing.
(Larger is better, but this is relative to MinRevs.)
BordaWorse = number of reversal scenarios where A's sincere Borda score
is worse than B's. (Smaller is better.)
MinRBorda = number of MinRevs scenarios where A's sincere Borda score
is worse than B's. (Smaller is better.)
FailSDSC = number of scenarios where reversal isn't thwarted by
by BAC -> B>A=C truncation. (When voters are devious
enough to reverse, others will be clever enough to defend.)
If always zero for a method, the method satisfies
Mike Ossipoff's "Strong Defensive Strategy" criterion.
(Smaller is better.)
BordaWorst = smallest ratio of A's sincere Borda score to B's.
(Larger is better.)
BordaAvg = average ratio of A's sincere Borda score to B's.
(Larger is better.)
ThwartMax = largest percentage of voters who ranked B ahead of A.
(Smaller is better.)
ThwartAvg = average percentage of voters who ranked B ahead of A.
(Smaller is better.)
A caveat about the Borda and Thwarted Majority stats: A method with
more reversal scenarios may appear better on these stats. But in
scenarios where reversal fails, there is no drop in the winner's
sincere Borda score and no thwarted majority, so a method with fewer
reversal scenarios should perhaps receive extra credit in these
stats for its extra scenarios where reversal fails.
* *
Here's the debugged Schz subroutine. It's written in dBase.
procedure Schulze
parameters nAB,nBA,nAC,nCA,nBC,nCB
* The Schulze method calculates all the beat-paths
* between each pair of alternatives.
* The strength of a beat-path is the strength of its
* weakest pairwin. The strength of a pairwin is the number
* of voters who ranked the pairwinner ahead of the pairloser.
* If maxbeatpath(x>y) > maxbeatpath(y>x) then x shulze-beat y.
* The winner is the alternative which is shulze-unbeaten.
*
* It can be proved that there is (at least) one which is
* shulze-unbeaten, and that when there are no pairties there
* is exactly one which is schulze-unbeaten. Right, Markus?
*
private ABStrength,BCStrength,CAStrength, ABwinner,ACwinner,BCwinner
if nBC>nCB
* Too little reversal to make a difference.
RETURN 'B'
endif
* There is a cycle: B>A, C>=B, A>=C
if nBC>=nCB
* B has no pairlosses so given Schulze B wins.
RETURN 'B'
endif
if nAC<=nCA
* Only C has no pairlosses so given Schulze C wins.
RETURN 'C'
endif
* Here if each alternative has a pairwin and a pairloss.
* Calculate and compare the beat-paths.
* We are already given three of them (nBA, nCB, and nAC).
* Find strength of A>C>B "AB" beatpath:
ABStrength = min(nAC,nCB)
* Find strength of C>B>A "CA" beatpath:
CAStrength = min(nCB,nBA)
* Find strength of B>A>C "BC" beatpath:
BCStrength = min(nBA,nAC)
* Find the schulze-winner of each pairing:
ABwinner = iif(nBA < ABStrength, 'A', iif(nBA > ABStrength, 'B', 'AB'))
ACwinner = iif(nAC < CAStrength, 'C', iif(nAC > CAStrength, 'A', 'AC'))
BCwinner = iif(nCB < BCStrength, 'B', iif(nCB > BCStrength, 'C', 'BC'))
if at('A',ABwinner) = 0
* B schulze-beat A
if at('B',BCwinner) = 0
* C schulze-beat B
RETURN 'C'
else
* C did not schulze-beat B
* B has not schulze-losses so either B wins or B ties C.
RETURN 'B'
endif
else
* B did not schulze-beat A
if at('B',ABwinner) = 0
* A schulze-beat B
if at('A',ACwinner) = 0
* C schulze-beat A
RETURN 'C'
else
* C did not schulze-beat A
* A has no schulze-losses. Either A wins or A ties:
if at('C',ACwinner) = 0
* A schulze-beat C
RETURN 'A'
else
* A schulze-tied C
if at('C',BCwinner) = 0
* B schulze-beat C
* Only A has no schulze-losses.
RETURN 'A'
else
* Neither A nor C has any schulze-losses.
* Ignore this tie scenario.
RETURN 'B'
endif
endif
endif
else
* A schulze-tied B
if at('B',BCwinner) = 0
* C schulze-beat B
if at('C',ACwinner) = 0
* A schulze-beat C
* Only A has no schulze-losses.
RETURN 'A'
else
* A did not schulze-beat C
if at('A',ACwinner) = 0
* C schulze-beat A
RETURN 'C'
else
* A schulze-tied C
* Neither A nor C has any schulze-losses.
* Ignore this tie scenario.
RETURN 'B'
endif
endif
else
* C did not schulze-beat B
* B has no schulze-losses, so either B win or B ties.
RETURN 'B'
endif
endif
endif
* Should never get to here, but put a return at the end anyway:
RETURN 'B'
* * * *
More information about the Election-Methods
mailing list