[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