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

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

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

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

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

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

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.

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

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

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