Computer Simulations Comparing MAM and Instant Runoff

Stephen Eppley <seppley@alumni.caltech.edu>

Revised:  April 25, 2001

This document compares the MAM and Instant Runoff 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
Instant Runoff's winner.  The third is similar to the second, accumulating the number of
voters who prefer MAM's winner minus the number who prefer Instant Runoff'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.

satisfied by MAM but not by Instant Runoff.)

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 MAM satisfies them plus examples which show other prominent
voting procedures, including Instant Runoff, 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 Instant Runoff 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
Instant Runoff.  MAM's edge in determinism in table 2 gains added significance if
the assumption is made that MAM and Instant Runoff 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. (Of course, it seems unlikely
Instant Runoff would ever be accepted for use within small groups, since it is
widely known that Instant Runoff can easily defeat compromise alternatives.
See for example the discussion about "preferential voting" in books on Robert's
Rules of Order.  To be fair, we do not know of anyone who has proposed using
Instant Runoff within committees except as a last resort for voting by mail.)

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 more similar
to each other than to the rest, and neglect the "non-top" alternatives which are
defeated with certainty and irrelevant to the outcomes.  When comparing voting
procedures which are as different as MAM and Instant Runoff, this presumption
is problematic since the strategic properties of the voting method can affect whether
or not certain alternatives are nominated onto the ballot.  Since Instant Runoff
fails several important criteria (Condorcet, Top Cycle, Minimal Defense) the
nomination procedure must be carefully coordinated to avoid the election of a
"greater evil" rather than a compromise alternative; thus these computer simulations
comparing MAM and Instant Runoff should not be taken as predictions since the
randomness of the simulated voters neglects the strategic behavior which would
dominate under Instant Runoff.

For each row of table 1a, 1000 elections were simulated.  In each trial, 100 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 an inserted symbol was "indifference" was  arbitrarily
set to 0.3, but the conclusion that MAM is better than Instant Runoff is not sensitive to
this parameter. (For instance, compare to table 2, generated with 101 voters and
the indifference probability set to 0.)

Table 1a:  Simulations comparing MAM and Instant Runoff, 100 voters

 Alternatives Trials Det(MAM) Det(IR) MAM/IR IR/MAM Vote Margin 3 10000 9413 9398 398 85 1140 4 10000 9434 9445 734 223 2182 5 10000 9451 9458 1071 359 3346 6 10000 9417 9464 1385 426 4672 7 10000 9447 9431 1643 552 6014 8 10000 9388 9427 1868 613 7145 9 10000 9393 9425 2047 643 7909 10 10000 9379 9425 2164 739 8738 15 10000 9309 9414 2871 943 13273 20 10000 9274 9401 3393 993 16623

The "Det(MAM)" column shows the number of trials 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(IR)" column shows the number of trials in which Instant Runoff was
deterministically decisive.

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

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

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

Table 1b shows overall values derived from table 1a by normalization.  Note that
MAM's edges over Instant Runoff grow as the number of alternatives increases.

Table 1b:  Normalized values, 100 voters

 Alternatives Det(MAM) Det(IR) MAM/IR IR/MAM Vote Margin 3 94.13% 93.98% 3.98% 0.85% 0.114% 4 94.34% 94.45% 7.34% 2.23% 0.218% 5 94.51% 94.58% 10.71% 3.59% 0.335% 6 94.17% 94.64% 13.85% 4.26% 0.467% 7 94.47% 94.31% 16.43% 5.52% 0.601% 8 93.88% 94.27% 18.68% 6.13% 0.715% 9 93.93% 94.25% 20.47% 6.43% 0.791% 10 93.79% 94.25% 21.64% 7.39% 0.874% 15 93.09% 94.14% 28.71% 9.43% 1.327% 20 92.74% 94.01% 33.93% 9.93% 1.662%

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(IR)" column shows the fraction of trials in which Instant Runoff was
deterministically decisive.

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

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

The "Vote Margin" column shows the fraction of voters who ranked the MAM
winner over the Instant Runoff winner, less the fraction of voters who ranked
the Instant Runoff winner over the MAM winner, accumulated over all trials.
(A negative margin would indicate an edge for Instant Runoff, but all 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 under both MAM and Instant
Runoff 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 Instant Runoff 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 Instant Runoff
dominates MAM in determinism, in table 2 MAM dominates Instant Runoff in determinism,
which indicates that scenarios where Instant Runoff 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 Instant Runoff winner much more often than vice versa,
and the number of voters preferring MAM winners to Instant Runoff winners would
exceed the number preferring Instant Runoff winners over MAM winners.

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

 Alternatives Trials Det(MAM) Det(IR) MAM/IR IR/MAM Vote Margin 3 10000 9753 10000 509 194 1732 4 10000 9550 10000 1007 358 3781 5 10000 - - - - - 6 10000 - - - - - 7 10000 - - - - - 8 10000 - - - - - 9 10000 - - - - - 10 10000 - - - - - 15 10000 - - - - - 20 10000 - - - - -

3 alts, 2.44 margin
4 alts, 2.77 margin
5 alts,  margin

Table 2b:  Normalized values, 101 voters, strict rankings

 Alternatives Det(MAM) Det(IR) MAM/IR IR/MAM Vote Margin 3 % % % % % 4 % % % % % 5 % % % % % 6 % % % % % 7 % % % % % 8 % % % % % 9 % % % % % 10 % % % % % 15 % % % % % 20 % % % % %

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 Instant Runoff, 1000 voters

 Alternatives Trials Det(MAM) Det(IR) MAM/IR IR/MAM Vote Margin 3 1000 - - - - - 4 1000 - - - - - 5 1000 - - - - - 6 1000 - - - - - 7 1000 - - - - - 8 1000 - - - - - 9 1000 - - - - - 10 1000 - - - - - 15 1000 - - - - - 20 1000 - - - - -

Table 3b:  Normalized values, 1000 voters

 Alternatives Det(MAM) Det(IR) MAM/IR IR/MAM Vote Margin 3 % % % % % 4 % % % % % 5 % % % % % 6 % % % % % 7 % % % % % 8 % % % % % 9 % % % % % 10 % % % % % 15 % % % % % 20 % % % % %