The "Maximize Affirmed Majorities" (MAM) voting procedure
Revised: February 11, 2004
Introduction
Whenever there are more than two
alternatives, there will typically be more than one
majority preference, since each preference is a relative preference regarding a
pair of
alternatives. For example,
suppose there are three
alteratives x, y and z, and suppose
40% of the voters
prefer x over y and y over z,
35% prefer y over z and z over x, and
25% prefer z
over x and x over y. It can be
seen that a majority (65%) prefer x over y,
another majority
(75%) prefer y over z,
and another majority (60%) prefer z over x.
The majority preference for x over y can be interpreted as
majority support for the
proposition that "x shall be
socially ranked over y." Similarly, the majority preference
for y over z can be interpreted as
majority
support for the proposition that "y shall be
socially ranked over z" etc.
In 1785 the Marquis de Condorcet demonstrated in his
seminal essay on election theory
that the majority preferences can be inconsistent, or "cyclic," as
they are in the example
above. In that essay, Condorcet appears to advocate more
than one voting procedure.
One is tersely described in his introduction. The following excerpt is translated
from
his introduction:
"... take successively all the propositions that have a majority, beginning
with those possessing the largest. As soon as these first propositions
produce
a result, it
should be taken as the decision, without regard
for the less probable decisions that follow."
-- Marquis de Condorcet, "Essay on the Application of
Mathematics to
the Theory of Decision-Making"
[1785], page lxviii (as translated by
Keith Michael Baker in "Condorcet:
From Natural Philosophy to Social
Mathematics" [1975],
p.240, Chicago University Press)
Thus in the example Condorcet would begin by affirming "y over z"
since it has the
largest majority (75%). Then he would affirm "x over y"
since it has the next largest
majority (65%). Those two propositions taken together produce the result
"x over y
over z." The proposition "z over x"
would not be affirmed despite its majority support
since it conflicts with the affirmed propositions. The social ordering
"x over y over z"
implies x would be elected.
Condorcet's wording is ambiguous when two or more majorities are the same size
and
when pairings are "ties" (i.e., neither alternative in the pairing has a majority
over the other).
When there are many voters, as in large public elections, neither of these
conditions is
likely to occur. The "Maximize Affirmed Majorities" (MAM)
procedure is based on
Condorcet's rule, but is defined unambiguously.
MAM treats each majority preference
as evidence that
the majority's more preferred
alternative should finish over
the majority's less
preferred alternative, the weight of
the evidence
depending on the size of the
majority. Since majority preferences can
sometimes be inconsistent, it may be
impossible to honor all of them. Therefore,
MAM considers
the majority
preferences one at a time, from largest majority to
smallest
majority, affirming
only the majority preferences that are consistent with
those already affirmed. Since the resulting set of affirmed majority
preferences is
self-consistent, there
will always be at least one alternative such that no alternative
is ranked over it by an affirmed majority.
MAM chooses such an alterative.
(Typically there will be exactly one such alternative; MAM
is usually deterministic.)
Section 1 below provides two simple
examples to illustrate MAM's basic operation.
Section 2 discusses MAM's tiebreaking mechanism. Section 3 provides a
detailed
description of the MAM procedure. Section 4 provides two examples to
illustrate
MAM's operation when tiebreaking is necessary. A concluding section provides
additional comments, including a list of desirable criteria satisfied by MAM.
Separate documents provide a
mathematically formal definition completely equivalent
to MAM (useful in formal proofs that MAM satisfies the criteria it
satisfies) and proofs
that MAM satisfies several important criteria. Computer software which
implements
MAM will be available for downloading over the internet.
1. Two examples to illustrate MAM's basic operation
Example 1.1: Suppose there are three
alternatives, represented here by the letters
x, y, and z. The voters are asked to rank the
alternatives from most preferred to
least preferred. (Note that sometimes some voters may have strategic
incentives to
misrepresent their orders of preference. This is not peculiar to MAM;
such incentives
may exist no matter what voting method is used.) Suppose the voters submit the
following votes:
34% | 10% | 10% | 46% |
x | y | y | z |
y | x | z | y |
z | z | x | x |
By inspection of the votes, three
majorities can be identified:
66% of the voters ranked y
over x.
56% of the voters ranked z
over x.
54% of the voters ranked y
over z.
MAM considers the majorities from
largest to smallest:
First MAM affirms the "y
over x" majority, which is largest.
Next, since "z over
x" is consistent with "y over x", MAM affirms
the "z over x" majority.
Next, since "y over
z" is consistent with "y over x and z
over x",
MAM affirms the "y over z" majority.
Alternative x is less
preferred by two affirmed majorities, "y over x" and "z
over x."
Alternative y is not less preferred by any affirmed majority.
Alternative z is less preferred by one affirmed majority, "y over z."
Since y is not less preferred by any affirmed majority, MAM elects y.
Example 1.2: Suppose the voters submit the following votes:
34% | 10% | 10% | 46% |
x | y | y | z |
y | x | z | |
z | z | x |
This example illustrates that
voters are not required to vote complete strict orderings
of the alternatives. They are allowed to express indifference, and as a
shortcut they
may leave some alternatives unranked. When a voter leaves
alternatives
unranked,
the ballot is interpreted as though the voter had ranked them as equal to each
other
and less preferred than the explicitly ranked alternatives. Thus the
ballots of the 46%
who voted just "z" are treated the same as if they had voted z
as their first choice
and x & y equally second.
By inspection of the votes, three
majorities can be identified:
34% of the voters ranked x
over y.
56% of the voters ranked z
over x.
54% of the voters ranked y
over z.
MAM considers the majorities from
largest to smallest:
First MAM affirms the "z
over x" majority.
Next, since "y over z"
is consistent with "z over x",
MAM
affirms the "y over z" majority.
Next, since "x over y"
is inconsistent with "y over z and z over x", MAM
does not affirm the "x over y" majority. (The
reason "x over y" is
inconsistent is that "y over z" and "z over x"
together imply "y over x".)
Alternative x is less
preferred by one affirmed majority, "z over x."
Alternative y is not less preferred by any affirmed majority.
Alternative z is less preferred by one affirmed majority, "y over z."
Since y is not less preferred by any affirmed majority, MAM elects y.
2. MAM's tiebreaking mechanism
Any voting procedure which satisfies the criteria of anonymity and neutrality
must
in some cases depend on chance. (Anonymity requires that no voter be
privileged
and neutrality requires no alternative be privileged.) For instance, if there are two
alternatives
and the voters are evenly split between them, each alternative must have
a ½ chance of being
elected. (Presumably a fair coin toss could be used to pick one
of them randomly.) This is
more likely to occur in small committee voting than in
large public elections, where chance
would rarely play a role.
Though MAM could be modified to privilege someone as a tiebreaking voter
(e.g.,
a committee's chairperson) or to privilege one of the alternatives (e.g., the status
quo),
the version of MAM defined here satisfies anonymity and neutrality. Thus there
are
some possible scenarios in which chance would play a role. When MAM considers
the majorities from
largest to smallest, chance could play a role if two or more majorities
are the same size,
since it may be the case that the order in which they are considered
for affirmation determines which are affirmed, which may ultimately affect which
alternative is not less preferred by any affirmed majority. Clearly, in
elections with
many voters it would be very rare for two majorities to be exactly the same size
and also be relevant to each other's
affirmation.
Chance can also play a role in MAM if two or more alternatives are not less
preferred
by any affirmed majority, but this cannot happen unless the voters are evenly
divided
between two alternatives. This too would be rare in elections having many
voters,
and also in committees comprised of an odd
number of voters.
In order to ensure that MAM completely satisfies the independence of clone alternatives
criterion, we have defined the tiebreaking mechanism in MAM (used when two or
more
majorities are the same size or when two or more alternatives are not less
preferred by
any
affirmed majority) to be more sophisticated than blind chance. The
first step after
encountering such a tie is to construct a strict ordering of the alternatives,
call it Tiebreak,
by picking one of the voters'
ballots at random and adopting its preferences. (If this ballot
is indifferent regarding any pair of alternatives, we would continue randomly
picking from
the remaining ballots, one at a time, incorporating into Tiebreak
their strict preferences
that don't conflict with those already incorporated, until either Tiebreak
is a strict ordering
of the alternatives or every ballot has been picked. If Tiebreak is still
not a strict ordering
after picking every ballot--which could only happen if all voters are indifferent regarding
a
pair
of alternatives--then any remaining indifferences in Tiebreak are resolved randomly.)
In large
public elections the tiebreaking mechanism isn't important since such
ties would be
extremely unlikely, and a simpler (purely random) tiebreaking mechanism could be
used.
But the tiebreaking mechanism could make a difference when voting within legislatures
or committees, and since we anticipate MAM will be used by such small
groups before
it is used for public elections, it makes sense to advocate the version of MAM presented
here which is
completely independent of clones, in spite of the slight increase in complexity.
(We could further argue that all anonymous, neutral voting methods should use this
tiebreaking mechanism instead of blind chance to improve their resistance to clones.)
Here is a
detailed description of the mechanism by which MAM constructs a strict
ordering of the alternatives to be used if necessary for
tiebreaking. We call this the
Random Voter Hierarchy procedure. It is a straight-forward generalization of the
"Random Dictator" procedure (which simply picks one ballot at random
and adopts
its preferences, and resolves any remaining indifferences randomly).
procedure: Random Voter Hierarchy
Initialize Tiebreak to be the utterly indifferent "ordering" of the alternatives.
Repeat the following until Tiebreak is a strict
ordering
of the alternatives:
{
If at least one voter's ballot has not yet been marked "picked"
{
Randomly pick a
voter's ballot not yet marked "picked" and
let r
denote this ballot. Mark r "picked" (so it won't be
picked again).
For all pairs of alternatives x
and y such that Tiebreak is indifferent
between
x and y and
r is not
indifferent between x and y,
amend Tiebreak (preserving its strict portions) so
it ranks x and y
relative to each other
the same as r does.
}
Else amend Tiebreak (preserving its
already strict
portions) into a
strict ordering by randomly resolving all its remaining indifferences.
}
Note that the Random Voter Hierarchy procedure
needs to be performed at most once
(per election), and not at all by MAM if no pairings are ties and no two
majorities are the
same size, which means the tiebreaker will rarely be needed in elections
that have many
voters. For simplicity, however, we define MAM here so it performs the
Random Voter
Hierarchy procedure exactly once (per election), prior to sorting the list of
majorities from
largest to smallest. There are some small timesaving efficiencies that
could be implemented
without affecting outcomes, such as calculating only as much of the strict
Tiebreak ordering
as needed to break ties actually encountered. In the worst case (where every
voter is
totally indifferent between some pair of alternatives) the time to execute Random Voter
Hierarchy increases as the number of ballots and increases as the square of
the number
of alternatives. Thus it is practical to compute on
inexpensive computers even in a worst
case involving hundreds of millions of voters . In scenarios
needing tiebreaking, typically
most voters will express strict preferences regarding most alternatives, so few
ballots
(possibly only one) will need to be picked.
Assuming it were time-consuming to randomly pick even
a few of the ballots (which
could conceivably be the case if there are hundreds of millions of ballots
occupying
several billion bytes of computer mass storage, another way time might be saved
is
to recognize that in many cases the precise relative ordering of precedence of
two
or more majorities that are the same size will not affect the outcome. For
instance,
if two majorities that are the same size are not also the smallest majorities in
some
cycle that includes both, then it will not matter which is considered for
affirmation
before the other. So, before spending time constructing the portion of the
Tiebreak
ordering "needed" to determine the relative precedence of two or more
same size
majorities, we could first check whether their order of precedence
matters. This
can be accomplished fairly quickly by first neglecting the ones that already
conflict
with those already affirmed, and then checking whether the other ones could
all
be affirmed. Often the answer will be yes, in which case it will not
matter which
of them is affirmed before the rest.
In cases where there are hundreds of millions of
voters, planning for the worst case
would mean keeping track of the ballots that have been (randomly) picked, so
that
the time needed to pick an unpicked ballot won't grow as the number of
unpicked
ballots dwindles. Keeping track means maintaining a growing list of the
ballots that
have been picked so far. Since in large public elections this list could
conceivably grow
larger than the amount of RAM memory in a small computer, it might be necessary
to
write the list to mass storage, which is slower than RAM. In many cases,
time can be
saved by not bothering to keep track of the first few ballots picked, trading
the extra
time wasted if the same ballot is accidentally picked more than once for the
time saved
by not having to write any data to mass storage. There is no harm in
accidentally
picking the same ballot again, other than the time wasted. So, if the
total number
of voters is n, it would probably be more efficient not to bother
tracking the first
n/20 ballots picked. And it would make sense to check how much of
the list can
be stored in RAM before writing any of it to mass storage.
If additional small amounts of time are to be saved, a limit on the number of ballots
which
Random Voter Hierarchy may pick could be imposed. If the limit is
reached
before the tiebreaking ranking being constructed is strict, remaining
indifferences
would be resolved randomly. (If the limit is set
to one, this is the
Random Dictator
procedure.) Choosing
a limit smaller than the number of voters would make it possible
to violate the Strong
Pareto criterion, and since any time saved would be relatively
small even in the worst case of massive indifference, Random Voter Hierarchy
is
defined with no such limit. Random Voter Hierarchy, by
having no limit, allows
satisfaction of an independence
of clone alternatives criterion that is slightly stronger
than the
version of independence of clone alternatives defined by TN Tideman
in 1987, but a limit of one is all that is needed to satisfy Tideman's version. In a
large public election, little would be lost by setting the limit to zero (meaning the
tiebreaking strict ranking of the alternatives, if needed, would be completely random)
since in large elections it
is so unlikely there would be any ties needing breaking
that no would-be manipulator would
expect to gain by exploiting properties of
the tiebreaking procedure.
The two examples in section 4 illustrate the operation of MAM when
tiebreaking
is necessary. But first, section 3 provides a detailed description of
MAM.
3. A complete definition of MAM
Here is the detailed definition of the MAM procedure:
procedure: Maximize Affirmed Majorities
Each voter is allowed to rank (that is, order) the alternatives.
(Voters' rankings
need not be strict, meaning that voters may express
indifferences as well as
preferences. To be practical when there are many
alternatives,
as a shortcut
each voter may leave some alternatives unranked,
which shall be interpreted
as though the voter had voted the unranked alternatives at the bottom, indifferent
to each
other and below all the explicitly
ranked alternatives. To be practical
in committees, which typically intermingle voting on alternatives with proposing
of new
alternatives, it is
recommended that the technology automatically append
newly
proposed alternatives at the bottom
of each voter's previously voted
ranking
and allow each voter to easily edit his/her
ranking.)
Construct the vote count table V
by counting the votes:
For each of the possible pairs
of
alternatives, for instance x and y,
let V_{xy} be the number of votes that rank x over y,
and let V_{yx} be the number of votes that rank y over x.
Construct the list of Majorities:
Begin with an empty list.
For each pair
of alternatives, for instance x and y,
if V_{xy} >
V_{yx}
then append "x over y" to the list.
else if V_{yx} > V_{xy}
then append "y over x" to the list.
Construct a strict ordering of the
alternatives, called Tiebreak, from the voters'
rankings by using the
Random Voter Hierarchy procedure (defined
above).
(This ordering will be used to break ties,
if necessary, in the steps which follow.)
Sort the list of Majorities, primarily
from largest majority to smallest majority:
To be more specific, a majority for x over y precedes a majority
for z over w
if and only if at least one of the following conditions holds:
1. V_{xy} > V_{zw}.
2. V_{xy} = V_{zw} and V_{wz} > V_{yx}.
3. V_{xy} = V_{zw} and V_{wz} = V_{yx} and Tiebreak ranks w over y.
4. V_{xy} = V_{zw} and V_{wz} = V_{yx} and w = y and Tiebreak ranks x over z.
(In other words, the majority having more
"support" for its preferred alternative
has
greater precedence, as shown in condition 1. If two majorities have the
same amount of support, then the
one having less support
for its less preferred
alternative (smaller minority "opposition") has greater precedence, as shown
in
condition 2. If two
majorities have the same amount of support and have
the same amount of opposition, then their relative precedence
is determined
by appealing to the Tiebreak ordering as shown in condition 3 or 4.)
Initialize the table FinishOver so
that no alternative finishes over any other.
That is, for all
pairs of alternatives x and y, set FinishOver_{xy}
to false
and set FinishOver_{yx} to false.
Conditionally affirm majorities in the Majorities
list, considering one majority
at a time in order of precedence, as follows:
Letting "x over y"
denote the majority under
consideration,
if FinishOver_{yx} is
still false // (which means
"x over y" doesn't conflict
// with those already affirmed)
and FinishOver_{xy} is
still false //
(which means x finishing over y has not
// already been implied by x finishing
// over some z and z finishing over y)
then affirm("x finishes over y")
// defined
below
Construct the list of Top Alternatives, which is the alternative(s)
x such that
FinishOver_{yx} is not true for any alternative y.
If the list of Top Alternatives contains only one alternative,
elect it. Otherwise,
elect the alternative in the Top Alternatives list that Tiebreak ranks over all other
alternatives in that list.
The affirm procedure (invoked
repeatedly within
the MAM procedure), when given
a social preference (such as "x finishes over y") to affirm, sets to true the corresponding
element of the
FinishOver table. Then it affirms the social preferences
not yet affirmed
but
which are logically implied by "transitivity" given all the social preferences
affirmed thus
far. For example, if it has already been affirmed that x finishes
over y and that y finishes
over z, then together these logically imply that x finishes over z.
Furthermore, it means
a (smaller) majority for z over x, if there is one, conflicts with
the (larger) majorities
already affirmed. The affirm procedure is "recursive" but not circular, and
its maximum
depth of
recursion is always less than the number of alternatives. The
affirm procedure
is defined here:
procedure: affirm("x finishes over y")
Set FinishOver_{xy}
to true.
Repeat the following once for every alternative, letting the label "a"
denote
the alternative under consideration:
If FinishOver_{ax}
is true
// a over x and x over y together imply a
over y.)
and FinishOver_{ay} is not yet
true,
// (Don't waste time unnecessarily.)
then affirm("a
finishes over y").
// (recursion)
If FinishOver_{ya}
is true
// (x over y and y over a together imply x
over a.)
and FinishOver_{xa} is not yet
true,
// (Don't waste time unnecessarily.)
then affirm("x
finishes over a").
// (recursion)
While the FinishOver table is under construction during MAM's affirmation of
majorities,
the table offers a quick test of whether a majority being
considered for affirmation conflicts
with the majority preferences affirmed thus
far. For instance, suppose "x over y" is the
majority being considered for affirmation, and suppose "y over
z" and "z over x" are
majorities that
preceded "x over y" due to greater support, and suppose
"y over z"
and "z over x"
were affirmed
before "x over y"
is considered. The affirmed majority
for y over z is treated as evidence that y
should finish over z and the affirmed majority
for z over x is treated as evidence that z should finish over x, so
together they also
constitute affirmed evidence that logically implies (by transitivity) that y should finish
over x. Thus those two affirmed majorities contradict evidence
that suggests x should
finish over y. In other words, "x over y"
conflicts with the majorities already affirmed.
Suppose in addition, for example, that "y over z"
was affirmed before "z over x."
When "z over x"
was affirmed, the affirm procedure would at some point have tested
whether FinishOver_{yz} is true (letting the label
x in the definition of affirm represent the
z in "z over x," letting the label y
in the definition of affirm
represent the x in "z over x,"
and at some point letting the label a
represent y) and because FinishOver_{yz} was true
the affirm procedure would have set FinishOver_{yx} to true.
Thus FinishOver_{yx} would
be true when MAM considers "x over y," indicating
"x over y" is inconsistent with
the affirmed majorities. Thus in this instance MAM
will not affirm "x over y".
The overall MAM procedure is easily computable since its execution
time increases
only as a small polynomial function of the number of alternatives and the
number of
voters. Since most children seem capable of ranking things
in order of preference,
and since MAM offers a couple of shortcuts to the
voters (non-strict
rankings and
treatment of unranked alternatives as if the voter had ranked them
below the explicitly
ranked alternatives), we consider MAM practical for many democratic institutions,
such as large public elections and legislatures, councils and committees.
There is a more sophisticated MAM algorithm that does
not merely select a winner.
It also constructs a complete strict "social" ordering of the
alternatives, with the winner
on top of course, and this requires little extra time. The MAM social
ordering has
many nice properties. For one, the alternative that is second in the MAM
social
ordering is the one that would have been elected by MAM if the winner were
deleted
from all the votes. In other words, deleting from all votes one or more
alternatives
that top the MAM social ordering will not change the rest of the ordering.
Similarly,
deleting from all votes one or more alternatives at the bottom of the MAM
social
ordering will not change the rest of the ordering. For more information,
see
the
section on the MAM social ordering in "A formal definition of MAM."
4. Two examples involving tiebreaking
Example 4.1: Suppose the voters rank three alternatives x, y and z as follows:
32% | 34% | 34% |
x | y | z |
y | z | x |
z | x | y |
By inspection of the votes, three
majorities can be identified:
66% of the voters ranked x
over y.
68% of the voters ranked z
over x.
66% of the voters ranked y
over z.
MAM considers the majorities from
largest to smallest. The "z over x" majority is
considered first since it is uniquely largest, and MAM affirms it. Next, however,
since the remaining two majorities are the same size (both having the same amount
of
support for the majority's more preferred alternative and both also having the same
amount of
opposition against the preferred alternative), the tiebreaking mechanism is
invoked: the
Random Voter Hierarchy procedure is used to construct a tiebreaking
strict ordering of the
alternatives, which we name Tiebreak. Random Voter Hierarchy
randomly
picks one of the voters' ballots and adopts that ballot's strict preferences.
Thus in this example there
are three cases to consider:
Case 1: There is a 32% chance
that Tiebreak ranks x first, y second, and z
last.
In this case, the "y over z" majority is considered
before the "x over y" majority
since Tiebreak ranks y (the less preferred alternative
of the "x
over y" majority)
over z (the less preferred alternative of the "y over z" majority). Thus MAM
affirms "y
over z." MAM does not affirm "x over y" since it is inconsistent with
"y
over z" and "z over x." Since y
is not less preferred by any affirmed majority,
MAM elects y in case 1.
Case 2: There is a 34% chance
that Tiebreak ranks y first, z second, and x
last.
In this case, as in case 1, the "y over z" majority is
considered before the
"x over y" majority since Tiebreak ranks y (the
less preferred alternative of
the
"x over y" majority) over z (the less
preferred alternative of the "y over z"
majority). Thus MAM affirms
"y over z." MAM does not affirm "x over y"
since it is inconsistent with "y
over z" and "z over x." Since y
is not less preferred
by any affirmed majority, MAM elects y in case 2.
Case 3: There is a 34% chance
that Tiebreak ranks z first, x second, and y
last.
In this case, the "x over y" majority is considered
before the "y over z" majority
since Tiebreak ranks z (the less preferred alternative
of the "y
over z" majority)
over y (the less preferred alternative of the "x over y" majority). Thus MAM
affirms "x
over y." MAM does not affirm "y over z" since it is inconsistent with
"z
over x" and "x over y." Since z
is not less preferred by any affirmed majority,
MAM elects z in case 3.
Thus there is a 66% chance that MAM
elects y, a 34% chance that MAM elects z,
and no chance that MAM elects x.
Example 4.2: Suppose the voters rank three alternatives x, y
and z as follows:
20% | 30% | 40% | 10% |
x | y | z | z |
y | z | y | x |
z | x | x | y |
By inspection of the votes, two
majorities can be identified:
80% of the voters ranked z
over x.
70% of the voters ranked y
over x.
The remaining pairing, y versus z, is a tie with 50% of the
voters ranking y over z
and 50% ranking z over y.
MAM considers the majorities from
largest to smallest:
First MAM affirms the "z
over x" majority.
Next, since the "y over x"
majority is consistent with "z over x",
MAM
affirms the "y over x" majority.
Alternative x is less
preferred by two affirmed majorities, "z over x" and "y over x."
Alternative y is not less preferred by any affirmed majority.
Alternative z is not less preferred by any affirmed majority.
Since both y and z are
not less preferred by any affirmed majority, MAM invokes its
tiebreaking mechanism to choose between them. The Random Voter Hierarchy
procedure is
used to construct a tiebreaking strict ordering of the alternatives,
Tiebreak.
Random Voter Hierarchy randomly picks one of the voters' ballots and adopts its
strict
preferences. Thus in this example there are four cases to consider:
Case 1: There is a 20% chance
that Tiebreak ranks x first, y second, and z
last.
In this case, since Tiebreak ranks y over z,
MAM elects y.
Case 2: There is a 30% chance
that Tiebreak ranks y first, z second, and x
last.
In this case, since Tiebreak ranks y over z,
MAM elects y.
Case 3: There is a 40% chance
that Tiebreak ranks z first, y second, and x
last.
In this case, since Tiebreak ranks z over y,
MAM elects z.
Case 4: There is a 10% chance
that Tiebreak ranks z first, x second, and y
last.
In this case, since Tiebreak ranks z over y,
MAM elects z.
Thus there is a 50% chance that MAM elects y and a 50% chance that MAM elects z.
Here is a list of some criteria satisfied by MAM. (Definitions of the
criteria and proofs
that MAM satisfies them are provided below, or in linked
documents, or are widely
known in the social choice literature.)
Feasibility (practicality, computability)
Anonymity
Neutrality
Pareto (a.k.a. Unanimity), Strong Pareto
Condorcet-consistency, Top Cycle, Condorcet Loser
Monotonicity (non-negative responsiveness)
Resolvability, Reasonable Determinism
Minimal Defense
Non-Drastic Defense
Truncation Resistance
Larger Majority
Independence of Clone Alternatives
Immunity from Majority Complaints
Local Independence from Irrelevant Alternatives
Homogeneity
Independence of Irrelevant Alternatives (the weak version for
social choice procedures, not the strong version for social
ordering procedures--see "Arrow's Impossibility Theorem"
for the definition of the weak version.)
Here are some criteria not satisfied by MAM, with descriptions provided below:
Reinforcement
Participation
Cancellation
Independence of Irrelevant Alternatives (the strong version for
social ordering procedures)
Choice Consistency (similar in spirit to the strong version of
Independence of Irrelevant Alternatives but worded for
social choice procedures--see "Arrow's Impossibility Theorem"
for its definition.)
Independence of Pareto-Dominated Alternatives
Uncompromising
Reinforcement requires that if two distinct groups of voters separately
choose the
same alternative, that alternative must be chosen if their votes are
tallied together
as one large group. Aside from an aesthetic appeal,
failure to satisfy reinforcement
allows manipulation of the outcome only if some
minority has the power to divide
the voters into separate groups. But in
typical voting institutions no minority has
that power, so this criterion should
usually be considered much less important
than other criteria. Reinforcement is a weaker criterion than the
criterion that it
be impossible to gain by gerrymandering, which is too strong for any democratic
voting procedure to
satisfy.
Participation requires that no voter prefers the outcome resulting from
abstention
more than the outcome resulting if s/he votes his/her
"sincere" preferences. This is
a false dichotomy, however, since
voters may choose to vote strategically, for
instance by ranking a compromise equal to a more preferred alternative. When
a voter has information
suggesting abstention is preferable to sincere voting, that
same
information suggests compromising is at least as good as abstention.
So satisfaction of participation should not be considered important.
Cancellation requires that the outcome must not change if two
completely opposite
votes are removed from the set of votes. (Note that the votes which would tend
to
be completely opposite are those of voters at opposite extremes.) This
criterion is
aesthetically appealing, but not satisfying it appears to have no cost to
society so
it seems unimportant.
Reinforcement and participation are satisfied by the Borda procedure but not
by any voting procedure that satisfies Condorcet-consistency. Besides
failing
the Condorcet-consistency, Borda also fails top cycle, minimal
defense, non-
drastic defense, truncation resistance, independence of
clone alternatives,
and immunity from majority complaints, which are more important (in our
opinion)
than reinforcement and participation.
Independence of Irrelevant Alternatives (IIA) has been defined in more than
one
way in the political science literature, beginning with Kenneth Arrow in 1953.
Depending on the formulation, its meaning may be encapsulated by the choice
consistency criterion. It essentially requires that if the
voters' preferences regarding
any non-chosen
alternative are deleted from the voters' rankings, then the alternative
chosen
originally must still be chosen. (The term "irrelevant" is misleading, since
IIA essentially defines as irrelevant every alternative besides the chosen one.)
However,
IIA (or choice consistency) is so demanding that no
reasonable voting
procedure can comply. IIA is controversial since it is derived from a similar criterion
which assumes voters' utility valuations of the
alternatives are elicited instead of voters'
ordinal rankings of the alternatives; it is easy to justify an independence criterion for
voting rules which tally voters' utilities, but it is well-established that voters' utilities
cannot be reliably elicited, which justifies eliciting ordinal rankings
instead but loses
thereby the justification for independence. To the contrary, since voters' ordinal
rankings
lack information about their preference intensities, preferences regarding
so-called
"irrelevant"
alternatives may provide useful hints.
Uncompromising requires that if some voters uprank some alternative
from the
bottom (or from having been left unranked)--for example ranking a
compromise over
a "greater evil"-- this must not cause the defeat of an
alternative
still ranked over it.
One voting procedure that satisfies uncompromising is Instant Runoff
Voting (IRV,
also known as the Alternative Vote and as the single-winner versions of
Hare and
Single
Transferable Vote). IRV eliminates one candidate at a time, counting for
each
non-eliminated
candidate the number of voters who rank it over all other
non-eliminated
candidates
and eliminating the candidate with the smallest count.
Unfortunately, IRV can easily neglect voters' expressed preferences
for compromise
alternatives over less preferred alternatives, which means it conflicts with
criteria that
are more
important, in our opinion.
For instance, IRV
egregiously fails Condorcet-
consistency, top cycle, monotonicity, minimal
defense, non-drastic
defense,
and immunity from majority complaints (also
less
important criteria
such as
reinforcement and participation, and the essentially
impossible strong IIA).
Uncompromising
has been promoted
by advocates of IRV such as the Center
for Voting and
Democracy, who
are more concerned with promoting proportional
representation
systems for electing
legislatures than with improving elections where
one alternative is to be elected. (Since the IRV algorithm is the special single-winner
form
of the
Hare Single Transferable Vote proportional representation algorithm,
teaching the public about IRV (instead of about better procedures) serves the
interests of proportional
representation advocates
by helping to demystify an
important proportional
representation
algorithm. Arguably their interests would
be
better served by a voting procedure such as MAM that would be better than
IRV at
reducing
the "spoiler" problem, thereby allowing voters to express their
preferences
for their most preferred alternatives more often.)
Another voting procedure that satisfies uncompromising is the minimax
variation
of Simpson-Kramer, which elects the candidate whose largest pairwise
opposition
is the smallest. Minimax satisfies
monotonicity and independence from
Pareto-dominated alternatives, but not Condorcet-consistency, top cycle,
independence from clone alternatives or immunity from majority complaints.
(Its failures of some of these criteria are not egregious, however. For
instance,
it is Condorcet-consistent if all votes are strict rankings of the
alternatives,
and it can only fail top cycle in the presumably rare cases where the
majorities
within the top cycle are larger than other majorities.)
Another criterion promoted on behalf of Instant Runoff by the Center for
Voting and
Democracy is not well-defined, but was described in Science News (Nov. 2,
2002).
Essentially, they asserted that voting procedures need to strike the proper
balance of
two conflicting criteria: rewarding the candidate ranked top by the most
voters yet
not ignoring the rest of each voter's preferences. They claimed IRV strikes
this
balance best. Their justification for placing so much weight on
voters' top choices
(as if each voter cares strongly for her top choice and is nearly indifferent
between
the rest) is that being ranked top by a large minority of voters signifies
possession of
essential leadership skills. By implication, a candidate ranked second by
every voter
is less qualified than a candidate ranked top by a large minority, and in
particular
possesses less leadership ability. They cited no evidence to support such a
claim,
and it stands to reason that, all else being equal, voters would rank candidates
possessing superior leadership ability over other candidates, so that in a
competitive
election a candidate ranked second by most voters would indeed possess those
skills.
If their argument is based on the theory that being the sole nominee of a
"large" party
indicates possession of those skills, a counter-argument is that the nominee
typically
has had little to do with building or leading the party organization; rather,
s/he won a
brief "king of the hill" contest over other potential nominees in
which special interest
money may be more important than leadership skills.
Furthermore, it is important to keep in mind the effect of the voting method
on the
nomination process. Just as Plurality Rule induces parties to nominate at
most one
candidate per office to avoid electing less preferred candidates, so would IRV.
If party X nominates more than one candidate for an office under IRV,
they
risk
causing their own defeat since IRV can easily eliminate their
most electable
candidate
before their less electable candidates. To see this, suppose
"moderate"
candidate x
would win, in part by votes of some of the "swing
voters" whose policy
preferences
lie between x and party Y's candidate y. Now
suppose X also nominates x' who is
less moderate than x but more appealing than x
to X's hard-core
base and other
less moderate voters. Thus x no longer appears to IRV as
the top choice of as
many voters as before, and thus x may be eliminated
before x'.
Assuming many
of the swing voters prefer y over (less moderate) x',
y would win. This
risk may
be great enough and ubiquitous enough that parties would rarely
nominate
more
than one candidate per office, and thus would still rely on a flawed
nomination
process (for instance, primary elections dominated by special interest money)
that
would stifle competition and perhaps prevent the best candidates from
competing.
By similar reasoning, "less moderate" third party candidacies could
result in the defeat
of more moderate candidates. (Thus the claim made by many advocates of IRV
that
IRV would eliminate
"spoiling" is false.) Also, "centrist" third parties adopting
policies
between the
two large parties would be eliminated early by IRV, and possibly
perceived as being unpopular.
Indeed, books on Robert's Rules of Order (including the prestigious Scott,
Foreman
editions) clearly recommend against using IRV when better methods are feasible,
noting that IRV can easily defeat the best compromises. (The books on
Robert's
Rules unfortunately call IRV by the generic name
"preferential voting" even though
many other methods, such as MAM,
allow voters to vote orders of preference.)
In
hindsight,
the U.S. is fortunate that IRV was not the procedure used at the
Constitutional
Convention of 1787, since the "Great Compromise" (population-
proportional
House of Representatives and state-equal Senate) would have been
deemed
the least popular alternative by IRV: big states preferred
proportionality
and small states preferred equality, with the compromise being
the favorite of
almost no one but the second choice of nearly every delegate.
Possibly that
would have eliminated the compromise from further consideration
and prevented
ratification of a U.S. constitution.
Implied two paragraphs above is the claim that MAM would induce parties to
nominate more than one candidate per office. Each party would have at
least five
incentives to do so: (1) By nominating candidates favored by diverse
factions,
voter turnout of their supporters would presumably increase, and while
voting
for their favorites many of those voters would also presumably rank the
party's
other candidates over those of other parties. (2) The party may not know
at
nomination time which of their potential nominees have the best chances to
win
later in the general election. (3) Since MAM satisfies about as much of
spirit of
the strong IIA criterion as possible, nominating more than one candidate
would
rarely cause the defeat of all of the party's candidates, and such cases might
be
predictable (and thus avoidable on a case-by-case basis). (4) The minimal
defense voting strategy would be available to deter reversal strategies
that
might be attempted by supporters of other parties. (5) The party could
save
considerable campaign resources by eliminating its primary elections.
In addition to the Marquis de Condorcet, some credit for the
development of the
MAM procedure should also be given to TN Tideman. Tideman described a
procedure he called Ranked Pairs in
his paper "Independence of Clones as a
Criterion for Voting Rules" (Social Choice and Welfare,
1987). Ranked Pairs
is closely related to MAM even though MAM was independently
developed.
Ranked Pairs differs from MAM in three ways. The two differences that
are
most important in the context of large public elections (where it is unlikely
any
two majorities will be the same size) are:
1. Ranked Pairs requires each voter to vote a strict ordering
of the
alternatives
(at least in its 1987 incarnation).
2. When Ranked Pairs determines the order of precedence
of the majorities,
it measures their sizes by subtracting opposition from
support.
Because of these differences, Ranked Pairs fails minimal defense, non-drastic
defense, truncation resistance and immunity from majority complaints.
The other difference, unimportant in large public elections but possibly
significant
in small elections such as committees and legislatures, Ranked Pairs uses a
different tiebreaking scheme when determining the relative precedence of two
or more majorities that have the
same size, and as a result it does not completely
satisfy independence of clones or strong Pareto-efficiency.
In a subsequent 1989 paper, TM Zavist and Tideman
revised Ranked Pairs so it
allows voters to express non-strict orderings and uses a different tiebreaking scheme.
The 1989 tiebreaking scheme provides complete satisfaction of independence of
clones and strong Pareto-efficiency, but sacrifices monotonicity
by permitting
the chance that an alternative is elected to fall when voters rank it higher.
(This was
not mentioned in their paper.) Ranked Pairs 1989 still fails minimal defense,
non-drastic
defense, truncation resistance and immunity from majority
complaints. The tiebreaking
scheme in MAM does not sacrifice monotonicity.
(The MAM tiebreaker was developed as a refinement of Zavist's tiebreaker,
so the development of MAM was not entirely independent of Tideman and
Zavist's work.)