Comparisons of the MAM and PathWinner voting rules

Stephen Eppley <seppley@alumni.caltech.edu>

Revised:  July 12, 2002

This document compares the MAM and PathWinner voting procedures on three measures:  
The first, determinism, is defined as the fraction of scenarios in which the outcome is 
determined by the voters' expressed preferences alone, not by other factors such as 
chance or agenda orders.  The second compares the number of scenarios in which more 
voters prefer MAM's winner with the number of scenarios in which more voters prefer 
PathWinner's winner.  The third is similar to the second, accumulating the number of 
voters who prefer MAM's winner minus the number who prefer PathWinner's winner.  
The second and third measures can be considered benchmarks for majority rule, but 
other criteria (Minimal Defense, Truncation Resistance, Independence from Clone 
Alternatives) are also essential. 

(See also the document "Proof MAM is Immune from Majority Complaints",
which discusses two other criteria satisfied by MAM but not by PathWinner.)  

In our view, determinism is of little significance; what matters is that all "non-top" 
alternatives be defeated with certainty. (See the document "Strategic Indifference"
which defines the "Minimal Defense" and "Truncation Resistance" criteria, and 
includes proofs that both MAM and PathWinner satisfy them plus examples which 
show other prominent voting procedures fail them.)  However, since some analysts 
may believe determinism is important, we include it among the comparisons.  
(We also include for reference a section which shows the determinism values 
for two alternatives given any anonymous neutral voting procedure, at the end of 
this document.)  The difference in determinism between MAM and PathWinner 
would be most significant in small committee elections, not in large public elections.  
Thus, since committees are usually chosen so as to have an odd number of members, 
table 2 would seem to be more relevant than tables 1 or 3 for comparing determinism 
of MAM and PathWinner.  MAM's edge in determinism in table 2 gains added 
significance if the assumption is made that MAM and PathWinner will need to gain 
widespread acceptance as the decision-making procedure within small groups 
(replacing the Robert's Rules "successive pairwise elimination" procedure) 
before they gain widespread acceptance for large public elections.

Section 4.3 of the document "Strategic Indifference" claimed computer simulations 
using randomly generated voters' rankings indicate that the alternative chosen by the 
MAM voting rule beats pairwise the alternative chosen by the PathWinner voting rule 
more often than vice versa.  Put simply, once could say MAM is a better implementation 
of majority rule since in the long run more voters would prefer MAM winners over 
PathWinner winners than vice versa.  The following tables summarize the computer 
simulations. 

Of course, (most) real voters do not vote randomly.  Thus these simulations more 
closely approximate reality if we reinterpret the number of alternatives in each trial 
to mean the number of "top" alternatives, which we presume will be fairly similar 
to each other, and neglect the "non-top" alternatives which are defeated with certainty 
and are irrelevant to the outcomes.  This presumption makes even more sense with 
voting procedures like MAM and PathWinner which are independent of clone 
alternatives, since similar alternatives can be nominated without committing 
electoral "fratricide."

For each row of table 1a, the number of trials was varied so the number of trials with 
no Condorcet winner reached 10000.  (In scenarios with a Condorcet winner both MAM 
and PathWinner will choose the Condorcet winner, so to contrast the two voting rules 
we ensured there would be a significant number of trials with no Condorcet winner.)  
To save time, for each row of table 2a the number of trials was varied so the number 
of  trials with no Condorcet winner reached 1000.  Tables 1b and 2b were derived 
from 1a and 2a by normalization.

In each trial of table 1a, 100 simulated voters each voted a non-strict ranking.  In each 
trial of table 2a, 1000 simulated voters each voted a non-strict ranking.  Each voter's 
ranking was constructed from a randomly generated permutation of the alternatives, 
into which either a "preference" symbol or an "indifference" symbol was inserted 
between each pair of adjacent alternatives.  The probability that an inserted symbol 
was "indifference" was arbitrarily set to 0.3, but the conclusion that MAM is better 
than PathWinner is not sensitive to this parameter. (For instance, compare to table 3a, 
generated with 101 voters and indifference probability set to 0.)

Table 1a:  Simulations comparing MAM and PathWinner, 100 voters

Alternatives

Trials No CW Det(MAM) Det(PW)

MAM/PW

PW/MAM

Margin

3 81301 10000 5678 5678 0 0 0
4 51140 10000 7165 7372 209 7 523
5 37651 10000 7931 8201 465 21 1152
6 31857 10000 8230 8617 654 62 1361
7 26151 10000 8551 8906 879 94 2043
8 23912 10000 8629 9084 1017 85 2502
9 21561 10000 8633 9171 1118 106 2878
10 20084 10000 8688 9144 1176 132 2616
15 16000 10000 8928 9371 1561 211 3509
20 14172 10000 8969 9356 1746 247 3866

 

The "Det(MAM)" column shows the number of trials having no Condorcet winner 
in which MAM was deterministically decisive. (Note that due to the nature of 
MAM we do not possess a computationally tractable algorithm for calculating 
exactly when MAM's outcome depends on chance.  Instead we used an algorithm 
which provides a reasonable approximation:  

MAM begins tallying an election by first constructing a "tiebreaking" 
ranking which will be used (if necessary) to distinguish the relative 
precedence of equal size majorities.  MAM constructs this tiebreaking 
ranking using the Random Voter Hierarchy procedure (which is a 
generalization of Random Dictator, in order to satisfy anonymity, 
neutrality and independence of clones).  To test whether some other 
alternative could have been chosen had Random Voter Hierarchy 
behaved according to different randomness, MAM is restarted but 
with the reverse of MAM's "social order" substituted for the original 
tiebreaking ranking.  If MAM again chooses the same winner, this 
usually indicates MAM will choose this alternative with certainty.  

The "Det(PW)" column shows the number of trials having no Condorcet winner 
in which PathWinner was deterministically decisive. 

The "MAM/PW" column shows the number of trials in which both MAM 
and PathWinner were deterministically decisive and the MAM winner 
beat pairwise the PathWinner winner.  

The "PW/MAM" column shows the number of trials in which both MAM 
and PathWinner were deterministically decisive and the PathWinner winner 
beat pairwise the MAM winner.  

The "Margin" column shows the number of voters who ranked the MAM 
winner over the PathWinner winner, minus the number of voters who ranked 
the PathWinner winner over the MAM winner, accumulated over the trials 
in which both MAM and PathWinner were deterministically decisive. 
(A negative margin would indicate an edge for PathWinner, but all the 
observed numbers were zero or positive, indicating an edge for MAM.)

Table 1b showing overall values was derived from table 1a by mathematically 
including the trials having a Condorcet winner (which were excluded from table 1a) 
and normalizing.  Note that MAM's edges over PathWinner grow as the number of 
alternatives increases.  

Table 1b:  Normalized values (includes scenarios with Condorcet winners), 100 voters

Alternatives

Det(MAM) Det(PW)

MAM/PW

PW/MAM

Margin

3 94.68% 94.68% .000% .000% .000%
4 94.46% 94.86% .409% .014% .010%
5 94.50% 95.22% 1.235% .056% .031%
6 94.44% 95.66% 2.053% .195% .043%
7 94.46% 95.82% 3.361% .360% .078%
8 94.27% 96.17% 4.253% .356% .105%
9 93.66% 96.16% 5.185% .492% .134%
10 93.47% 95.74% 5.855% .657% .130%
15 93.30% 96.07% 9.756% 1.319% .219%
20 92.73% 95.46% 12.320% 1.743% .273%

 

The "Det(MAM)" column shows the fraction of trials in which MAM was 
deterministically decisive. (See the note above regarding the approximation 
used to measure MAM's decisiveness.)

The "Det(PW)" column shows the fraction of trials in which PathWinner was 
deterministically decisive. 

The "MAM/PW" column shows the fraction of trials in which both MAM and 
PathWinner were deterministically decisive and the MAM winner beat pairwise 
the PathWinner winner.  

The "PW/MAM" column shows the fraction of trials in which both MAM and 
PathWinner were deterministically decisive and the PathWinner winner beat 
pairwise the MAM winner.  

The "Margin" column shows the fraction of the total number of voters who ranked 
the MAM winner over the PathWinner winner, less the fraction of the total number 
of voters who ranked the PathWinner winner over the MAM winner. (A negative 
margin would indicate an edge for PathWinner, but all the observed margins were 
zero or positive, indicating an edge for MAM.)

Since small committees are usually composed of an odd number of people who carefully 
study the alternatives and thus are less likely to be indifferent between any alternatives, 
we also ran simulations to explore this case.  Tables 2a and 2b were generated like 
1a and 1b except the number of voters was set to 101 and the indifference probability 
was set to 0.  Since the number of voters was odd and every ballot was a strict ranking, 
no two alternatives ever tied each other pairwise.  Thus with both MAM and PathWinner 
the non-deterministic scenarios were caused by two or more majorities which were 
the same size and which were the smallest majorities in some (topmost) cycle.  

Surprisingly, MAM and PathWinner were less deterministic in table 2 than in table 1,
presumably caused by an increase in the number of scenarios having two or more 
majorities being equally smallest in some cycle.  Unlike table 1 in which PathWinner 
dominates MAM in determinism, in table 2 MAM dominates PathWinner in determinism, 
which indicates that scenarios where PathWinner is deterministic but MAM is not are 
mainly due to pairwise ties.  

As in table 1, the results in table 2 are consistent with the conclusion that the MAM 
winner would beat pairwise the PathWinner winner much more often than vice versa, 
and the number of voters preferring MAM winners to PathWinner winners would 
exceed the number preferring PathWinner winners over MAM winners.

Table 2a:  Simulations comparing MAM and PathWinner, 101 voters, strict rankings

Alternatives

Trials

No CW Det(MAM) Det(PW)

MAM/PW

PW/MAM

Margin

3 117509 10000 6879 6879 0 0 0
4 57971 10000 7316 6980 192 2 284
5 40519 10000 7436 7018 343 10 467
6 32289 10000 7626 7084 479 10 711
7 27255 10000 7570 7059 535 21 764
8 24096 10000 7564 7079 617 21 992
9 22051 10000 7538 6948 672 27 1073
10 20636 10000 7548 7067 688 28 1099
15 16617 10000 7581 7061 879 46 1598
20 14793 10000 7495 7088 1033 52 1896

 

Table 2b:  Normalized values (includes scenarios with Condorcet winners), 
101 voters, strict rankings

Alternatives

Det(MAM) Det(PW)

MAM/PW

PW/MAM

Margin

3 97.34% 97.34% 0.000% 0.000% .000%
4 95.37% 94.79% 0.331% 0.003% .005%
5 93.67% 92.64% 0.847% 0.025% .011%
6 92.65% 90.97% 1.483% 0.031% .022%
7 91.08% 89.21% 1.963% 0.077% .028%
8 89.89% 87.88% 2.561% 0.087% .041%
9 88.83% 86.16% 3.047% 0.122% .048%
10 88.12% 85.79% 3.334% 0.136% .053%
15 85.44% 82.31% 5.290% 0.277% .095%
20 83.97% 80.32% 6.983% 0.352% .127%

 

Tables 3a and 3b were generated like tables 1a and 1b except for 1000 voters  instead 
of 100 voters, and (to save time at a slight cost of accuracy) 1000 trials  having no 
Condorcet winner per row instead of 10000 trials.  Thus table 3 is more like large 
public elections, which typically have so many voters that it would be rare for there 
to be any pairwise ties or any majorities which are the same size.

Table 3a:  Simulations comparing MAM and PathWinner, 1000 voters

Alternatives

Trials

No CW Det(MAM) Det(PW)

MAM/PW

PW/MAM

Margin

3 16001 1000 937 937 0 0 0
4 7740 1000 949 954 56 8 627
5 5144 1000 979 984 98 14 1803
6 3860 1000 977 985 105 10 1760
7 3182 1000 985 991 167 17 3441
8 2732 1000 987 991 153 22 2345
9 2614 1000 977 990 169 32 2593
10 2313 1000 990 994 195 21 3305
15 1776 1000 983 999 235 37 4243
20 1571 1000 990 1000 326 52 5216

 

Table 3b:  Normalized values (includes scenarios with Condorcet winners), 1000 voters

Alternatives

Det(MAM) Det(PW)

MAM/PW

PW/MAM

Margin

3 99.61% 99.61% 0.00% 0.00% .000%
4 99.34% 99.41% 0.72% 0.10% .008%
5 99.59% 99.69% 1.91% 0.27% .035%
6 99.40% 99.61% 2.72% 0.26% .046%
7 99.53% 99.72% 5.25% 0.53% .108%
8 99.52% 99.67% 5.60% 0.81% .086%
9 99.12% 99.62% 6.47% 1.22% .099%
10 99.57% 99.74% 8.43% 0.91% .143%
15 99.04% 99.94% 13.23% 2.08% .239%
20 99.36% 100.00% 20.75% 3.31% .332%

 


Determinism given Two Alternatives

For reference, we also performed simulations to establish the baseline determinism 
of any anonymous neutral voting procedure given 2 alternatives (i.e., majority rule).  
Determinism given 2 alternatives and randomly generated votes depends on the 
number of voters and on the probability that a voter is indifferent.  For instance, 
if the number of voters is odd and no voter is indifferent, then majority rule with 
2 alternatives is completely deterministic.  These simulations show determinism is 
essentially independent of the indifference parameter over a broad domain of values, 
except for a sharp change at zero indifference and a gradual decline at high indifference.  
(The results for high indifference are probably not relevant to real elections.)  The 
simulations (10000 trials for each setting of the parameters) are summarized by 
tables 4a (100 voters), 4b (101 voters), 4c (1000 voters) and 4d (1001 voters):  

Table 4a:  Determinism given 2 alternatives, 100 voters.

Alternatives

Voters Indifference Probability Determinism

2

100

0.00

92.24%

2

100

0.01

95.57%

2

100

0.02

95.37%

2

100

0.03

95.99%

2

100

0.04

96.25%

2

100

0.05

96.11%

2

100

0.10

95.72%

2

100

0.20

95.91%

2

100

0.30

95.02%

2

100

0.40

94.94%

2

100

0.50

94.11%

2

100

0.60

93.52%

2

100

0.70

92.80%

2

100

0.80

90.99%

2

100

0.90

87.46%

2

100

0.95

81.91%

2

100

0.96

78.96%

2

100

0.97

75.65%

2

100

0.98

69.26%

2

100

0.99

53.88%

2

100

1.00

0.00%

Table 4b:  Determinism given 2 alternatives, 101 voters.

Alternatives

Voters Indifference Probability Determinism

2

101

0.00

100.00%

2

101

0.01

96.59%

2

101

0.02

96.03%

2

101

0.03

96.19%

2

101

0.04

95.71%

2

101

0.05

95.73%

2

101

0.10

96.02%

2

101

0.20

95.68%

2

101

0.30

95.31%

2

101

0.40

94.96%

2

101

0.50

94.33%

2

101

0.60

93.88%

2

101

0.70

93.07%

2

101

0.80

91.25%

2

101

0.90

87.41%

2

101

0.95

81.77%

2

101

0.96

79.36%

2

101

0.97

76.26%

2

101

0.98

70.25%

2

101

0.99

54.82%

2

101

1.00

0.00%

Table 4c:  Determinism given 2 alternatives, 1000 voters.

Alternatives

Voters Indifference Probability Determinism

2

1000

0.00

99.18%

2

1000

0.01

99.53%

2

1000

0.02

99.43%

2

1000

0.03

99.46%

2

1000

0.04

99.64%

2

1000

0.05

99.52%

2

1000

0.10

99.57%

2

1000

0.20

99.32%

2

1000

0.30

99.47%

2

1000

0.40

99.35%

2

1000

0.50

99.32%

2

1000

0.60

99.26%

2

1000

0.70

99.25%

2

1000

0.80

98.62%

2

1000

0.90

98.51%

2

1000

0.95

97.92%

2

1000

0.96

97.71%

2

1000

0.97

96.98%

2

1000

0.98

94.99%

2

1000

0.99

86.45%

2

1000

1.00

0.00%

Table 4d:  Determinism given 2 alternatives, 1001 voters.

Alternatives

Voters Indifference Probability Determinism

2

1001

0.00

100.00%

2

1001

0.01

99.55%

2

1001

0.02

99.62%

2

1001

0.03

99.46%

2

1001

0.04

99.65%

2

1001

0.05

99.45%

2

1001

0.10

99.53%

2

1001

0.20

99.48%

2

1001

0.30

99.37%

2

1001

0.40

99.33%

2

1001

0.50

99.18%

2

1001

0.60

99.16%

2

1001

0.70

99.08%

2

1001

0.80

99.13%

2

1001

0.90

98.61%

2

1001

0.95

97.69%

2

1001

0.96

97.53%

2

1001

0.97

97.03%

2

1001

0.98

95.57%

2

1001

0.99

86.65%

2

1001

1.00

0.00%