"Maximize Affirmed Majorities" (MAM) satisfies
Minimal Defense,
Non-Drastic Defense, Truncation Resistance and Larger Majority.
Revised: December 31, 2002
For more information about these criteria, see the document "Strategic
Indifference"
and the paragraphs below.
Let A denote the set of (nominated) alternatives, assumed finite and non-empty.
Minimal Defense:
Every (non-strict) ranking of A must be an admissible vote,
and for all x Î A,
x must not be elected if both of the following
conditions hold:
(1) More than half of the voters vote x no better than tied for
bottom.
(2) There exists y Î A
voted over x by more than half of the voters.
Non-Drastic Defense:
Each voter must be allowed to vote as many alternatives
tied for top as she wishes, and for all x Î A,
x must not be elected if there
exists y Î A such that that more than half of the voters vote
y over x and
no worse than tied for top.
Truncation Resistance:
Let SincereTop denote the smallest non-empty B Í
A
such that, for all x
Î A\B and all y Î
B, the number of voters who sincerely prefer y
over x exceeds the number who sincerely prefer x over y.
For all x Î
A\SincereTop,
x must not be elected if both of the following conditions
hold:
(1) For all a,b Î
A, every voter who votes a over b sincerely prefers a
over b.
(2) There exists y Î
SincereTop voted over x by more than half of the
voters.
Larger Majority:
For all x,y Î A, let #R(x,y)
denote the number of voters
who vote x over y. For all x,y Î A, say that
x
beats y pairwise if and only if
#R(x,y) > #R(y,x). For all
x Î A,
x must not be elected if there exists y
Î A
such that both of the following conditions hold:
1. y beats x pairwise.
2. For all a_{1},a_{2},...,a_{k}
Î A, if a_{1} = x
and a_{k} = y and a_{j}
beats a_{j}_{+1}
pairwise for all j Î
{1,2,...,k-1}, then there exists j Î
{1,2,...,k-1}
such that #R(y,x) > #R(a_{j},a_{j}_{+1}).
Satisfaction of minimal defense is
considered more important than satisfaction of
non-drastic defense due to our
expectation it will be easier for voters to coordinate
the "minimal defense strategy" (that is, downranking of "greater
evil" alternatives)
than the "non-drastic defense strategy" (that is, upranking a
compromise alternative
to at least tied for top). "Defensive" strategies are important
in scenarios where
supporters of "greater evil" alternatives would otherwise have an
incentive to
strategically misrepresent their preferences (in particular, voting the reverse
of
some preferences, such as downranking the "sincere winner" below less
preferred
alternatives). We do not consider defensive strategies
"manipulative" since they
serve to defend the election of the alternative that would be elected if every
voter
voted her sincere order of preference, by creating an equilibrium in which no
other
subset of voters has an incentive to misrepresent preferences.
Satisfaction of
non-drastic defense is better than nothing, however, since the only
other defensive
strategy capable of thwarting the "offensive" reversal strategy is the "drastic"
defensive strategy of ranking some compromise alternative over more preferred
alternatives, and we believe this defensive strategy is the most difficult to coordinate.
An example of a voting
procedure that satisfies non-drastic defense but fails minimal
defense is Approval, in which each voter may select as many alternatives as she wishes
and the alternative selected by the most voters is elected.
The non-drastic defensive
strategy under Approval is for a majority to select some compromise
alternative they
all prefer over the "greater evil" alternatives, and for each voter in
that majority to also
select every alternative she prefers over the compromise.
Two common voting procedures which fail these criteria are "plurality
rule" (which
allows each voter to select only one alternative, and elects the alternative
selected
by the most voters) and "majority runoff" (which allows each voter to
select only one
alternative, and elects the alternative selected by more than half the voters
if there
is one, and otherwise conducts a second round of voting to choose between the
two alternatives selected by the most voters). Some other prominent procedures
that fail all four criteria are Instant Runoff (also known as Hare, Single
Transferable
Vote, and the Alternative Vote), Copeland, Simpson and scoring rules such as
Borda.
Thus, most voting procedures
often force many voters to choose between expressing
their preference for their favorite alternative or pretending to prefer
some "compromise"
alternative over their favorite, a strategy that many voters seems to loathe.
Technically, the larger majority criterion is not failed by plurality rule,
majority
runoff, nor Approval since those procedures do not permit voters to rank
the
alternatives. Larger majority serves as a tool for comparing voting
procedures
that allow each voter to non-strictly rank the alternatives, since it turns out
that
its
satisfaction by such procedures implies they also satisfy the other three criteria.
Also, satisfaction of larger majority by a procedure that allows non-strict
rankings
implies that a majority seeking to defeat some "greater evil" alternative x do not
necessarily need to rank x no better than tied for bottom (the strategy suggested
by minimal defense), since they can also defeat x by ranking x no better than
the alternatives that may cycle with their "compromise" alternative y. Thus the
misrepresentation of preferences implied by downranking of x can
be even
less than with the blunt strategy suggested by minimal defense.
Example 1: The minimal defense voting strategy.
Suppose there are 3
alternatives x, y and z. Suppose the
voters'
sincere preferences regarding the alternatives are as follows:
46% | 10% | 10% | 34% |
x | y | y | z |
y | x | z | y |
z | z | x | x |
That is, 46% of the voters prefer x over y
and y over z, 10% prefer y over x
and x
over z, etc. Suppose the
voters vote the following rankings:
46% | 10% | 10% | 34% |
x | y | y | z |
z | z | y | |
y | x | x |
The votes of the 46% who voted x over z
over y misrepresent their preferences
since they prefer y over z. (This is the classic "reversal" strategy, burying y
in their rankings hoping to
defeat y and elect their favored alternative x.)
The votes of the 10% who ranked only y are
interpreted as having ranked x
and z tied for bottom, below y. Thus 54% rank x no better than tied for
bottom
and rank y over x, so satisfaction of minimal
defense requires
that x not be elected given these votes. Note that the 34% who prefer
z
over y do not need to rank y equal to or over z
to ensure x is
not elected,
assuming satisfaction of minimal defense.
Now suppose instead that the voters vote the following rankings:
46% | 20% | 34% |
x | y | z |
y | y | |
z | x |
The votes of the 20% who ranked only y are
interpreted as having ranked x and z
tied for bottom, below y. Thus 66% rank z no better than tied for bottom and
rank y over z. Also, 54% rank x no better than tied for bottom and rank y over x.
Therefore, satisfaction of minimal defense requires that
neither x nor z be elected
given these votes, which means y must be elected.
Note that this set of votes
constitutes
a "strategic equilibrium" since no voter nor coalition of voters has
an incentive to vote differently. (That is, no strategy of the 46% can elect x,
the
alternative they prefer over y, and no strategy of the 34% can elect z,
the alternative they prefer over y.) Thus no voter outside the
20% has an
incentive to
misrepresent preferences, and no voter has an incentive to
misrepresent preferences regarding alternatives preferred over y.
Example 2: The non-drastic defense voting strategy.
Suppose there are 3
alternatives x, y and z. Suppose the
voters'
preferences regarding the alternatives are as follows:
46% | 10% | 10% | 34% |
x | y | y | z |
y | x | z | y |
z | z | x | x |
That is, 46% of the voters sincerely prefer x over y
and y over z, 10% prefer y
over x and x
over z, etc. Suppose the
voters vote the following rankings:
46% | 10% | 10% | 34% |
x | y | y | z,y |
z | x | z | x |
y | z | x |
The votes of the 46% who voted x over z
over y misrepresent their preferences
since they prefer y over z. (As above, this is the classic "reversal"
strategy.)
The 34% who ranked both z and y tied for
best are part of a 54% coalition
who voted y over x and no worse than tied for best. Satisfaction of
non-drastic
defense requires that x must not be elected given
these votes. Note that the
34% who prefer z over y do not need to "drastically" rank y over
z
to ensure
that x is not elected, assuming satisfaction of non-drastic
defense.
Example 3: Resistance to truncation.
Suppose there are 3
alternatives x, y and z. Suppose the
voters'
preferences regarding the alternatives are as follows:
46% | 10% | 10% | 34% |
x | y | y | z |
y | x | z | y |
z | z | x | x |
That is, 46% of the voters sincerely prefer x over y
and y over z, 10% prefer y
over x and x
over z, etc. The sincere top cycle is {y} since more voters
prefer y
over x than vice versa and more voters prefer y over z than vice
versa. Suppose the
voters vote the following rankings:
46% | 10% | 10% | 34% |
x | y | y | z |
x | z | y | |
z | x | x |
The 46% who ranked only x have
not expressed their preference for y over z.
Such an expression of indifference that fails to express a voter's sincere
preference
is called a "truncation of preference." Those votes are
interpreted as having ranked
y and z tied for bottom, below x. However, note that all of the strict preferences
expressed by all of the voters accurately represent sincere
preferences. Since 54%
rank y over x, satisfaction of truncation resistance requires
x must not be elected.
Thus, satisfaction of truncation resistance implies truncation is
ineffective as an
"offensive" voting strategy, so no "defensive" misrepresentation of preferences by
the 54% is needed to
ensure x will not be elected. This property is important
when few voters are sophisticated enough to attempt a "reversal" strategy,
and
when voters are representatives accountable to unsophisticated constituents
who will not appreciate
reversal strategies.
Theorem "MAM satisfies Minimal Defense."
Proof: Refer to the definitions in the document
that provides the formal definition
of MAM. By inspection of the
definition of MAM, all strict and non-strict rankings
of A are admissible votes under MAM. Thus the first clause of minimal
defense is
satisfied by MAM. Assume more than half of the voters rank y over x and more
than half of the voters rank x no better than tied for bottom. We must show
that
MAM does not elect x. Suppose to the
contrary
there is a non-zero chance that
MAM elects x. This means there exists s
Î L(R,A) such
that x = MAM(A,R,s).
Make the following abbreviations:
Maj = Majorities(A,R).
Aff = Affirmed(A,R,s).
Precede(y,x) = Precede(y,x,A,R,s).
Top = Top(A,R,s).
MAM = MAM(A,R,s).
Since more than half of the voters rank y over
x and x no better than tied for bottom,
clearly both of the following statements hold:
(1.1) #R(y,x)
> #R/2.
(1.2) For all a Î A, #R(x,a)
< #R/2.
Thus the following statement holds:
(1.3) For all a Î A, (y,x) is larger than (x,a).
By 1.3 and the definition of precedence, the following statement must hold:
(1.4) For all a Î A, (x,a) Ï Precede(y,x).
Since MAM = x, x Î
Top. This means (a,x) Ï Aff
for all a Î A. Thus (y,x)
Ï Aff.
By 1.1, (y,x) Î Maj. Since (y,x) Î Maj and (y,x) Ï
Aff, it follows by the
definition of Affirmed() that
(y,x) is inconsistent with Aff Ç Precede(y,x).
This means there exist (a_{1},a_{2}),(a_{2},a_{3}),...,(a_{k}_{-1},a_{k})
Î Aff Ç Precede(y,x)
such that a_{1} = x and a_{k} = y. This implies (x,a_{2}) Î
Precede(y,x). But this
contradicts 1.4, which means the contrary assumption cannot hold, establishing
MAM cannot elect x. This implies MAM satisfies minimal defense.
QED
Theorem "MAM satisfies Non-Drastic Defense."
Proof: Refer to the definitions in the document
that provides the formal definition
of MAM. By inspection of the
definition of MAM, all strict and non-strict rankings
of A are admissible votes under MAM. Thus each voter
may rank as many alternatives
as she wishes at the top of her vote, which means the first clause of non-drastic
defense
is satisfied by MAM. Assume more than half of the voters rank y
over x and no worse
than tied for best. We must show that MAM does not elect x. Suppose to the
contrary
there is a non-zero chance that MAM elects x. This implies there exists s
Î L(R,A)
such
that x = MAM(A,R,s).
Make the same abbreviations as in the proof above
that MAM satisfies minimal defense. Since more than half of the
voters rank y
over x and no worse than tied for top, clearly both of the following statements hold:
(2.1) #R(y,x)
> #R/2.
(2.2) For all a Î A, #R(a,y)
< #R/2.
Thus the following statement holds:
(2.3) For all a Î A, (y,x) is larger than (a,y).
By 2.3 and the definition of precedence, the following statement must hold:
(2.4) For all a Î A, (a,y) Ï Precede(y,x).
Since MAM = x, x Î
Top. This means (a,x) Ï Aff
for all a Î A. Thus (y,x)
Ï Aff.
By 2.1, (y,x) Î Maj. Since (y,x) Î Maj and (y,x) Ï
Aff, it follows by the
definition of Affirmed() that
(y,x) is inconsistent with Aff Ç Precede(y,x).
This means there exist (a_{1},a_{2}),(a_{2},a_{3}),...,(a_{k}_{-1},a_{k})
Î Aff Ç Precede(y,x)
such that a_{1} = x and a_{k} = y. This implies (a_{k}_{-1},y) Î
Precede(y,x).
But this
contradicts 2.4, which means the contrary assumption cannot hold, establishing
MAM cannot elect x. This implies MAM satisfies non-drastic
defense. QED
Theorem "MAM satisfies Truncation Resistance."
Proof: Refer to the definitions in the document
that provides the formal definition
of
MAM. Abbreviate T = SincereTop. By the definition of SincereTop,
for
all a Î
T and all b Î A\T the number of voters who prefer b over a must be
less than #R/2.
Assume that for all a,b Î A, every voter
who votes a over b
sincerely prefers a over b. This means the following statement
holds:
(3.1) For all a Î T and all b Î A\T, #R(b,a) < #R/2.
Assume also that x Î A\T
and there exists y Î T such that #R(y,x)
> #R/2. We
must show MAM does not elect x. Suppose to the
contrary there is a non-zero
chance that MAM elects x. This implies there exists s
Î L(R,A) such
that
x = MAM(A,R,s).
Make the same abbreviations as in the proof above that
MAM satisfies minimal defense. Since #R(y,x)
> #R/2, by 3.1 the following
statement holds:
(3.2) For all a Î T and all b Î A\T, #R(y,x) > #R(b,a).
By 3.2 and the definition of precedence, the following statement must hold:
(3.3) For all a Î T, all b Î A\T, (b,a) Ï Precede(y,x).
Since MAM = x, x Î
Top. This means (a,x) Ï Aff
for all a Î A, so (y,x)
Ï Aff.
Since #R(y,x)
> #R/2, #R(x,y) < #R(y,x). Thus (y,x) Î Maj.
Since (y,x) Î Maj
and
(y,x) Ï Aff, by the
definition of Affirmed() (y,x) is inconsistent with Aff Ç Precede(y,x).
This means there
exist (a_{1},a_{2}),(a_{2},a_{3}),...,(a_{k}_{-1},a_{k})
Î Aff Ç Precede(y,x)
such
that a_{1} = x and a_{k} = y. Since
a_{1} Ï T and a_{k} Î
T, by induction there must exist
j Î
{1,2,...,k-1} such that a_{j} Ï
T and a_{j}_{+1} Î T.
But since (a_{j},a_{j}_{+1}) Î
Precede(y,x),
this contradicts 3.3, which means the contrary assumption cannot hold, establishing
MAM cannot elect x. This implies MAM satisfies truncation
resistance. QED
Theorem "MAM satisfies Larger Majority"
Proof: Refer to the definitions in the document
that provides the formal
definition of MAM. Pick any x,y Î
A. Make the following assumptions:
(4.1) (y,x) Î
Majorities(A,R). (That is, #R(y,x) > #R(x,y).)
(4.2) For all a_{1},a_{2},...,a_{k}
Î A, if a_{1} = x
and a_{k} = y
and (a_{j},a_{j+1}) Î
Majorities(A,R) for all j Î
{1,2,...,k-1},
then there exists j Î
{1,2,...,k-1} such that #R(y,x) > #R(a_{j},a_{j}_{+1}).
We must show that MAM does not elect x. Suppose to the
contrary
there is
a non-zero chance that MAM elects x. This implies there exists s
Î L(R,A)
such
that x = MAM(A,R,s).
Make the same abbreviations as in the proof
above that MAM satisfies minimal defense.
By 4.2 and the definitions of inconsistency and precedence, the following holds:
(4.3) For all P
Í Maj, if (y,x) is inconsistent with P then
there
exists (a,b) Î P such that (a,b)
Ï Precede(y,x).
Since MAM = x, x Î
Top. This means (a,x) Ï Aff
for all a Î A, so (y,x)
Ï Aff.
By 4.1, (y,x) Î Maj. Since (y,x) Î
Maj\Aff, by the
definition of Affirmed()
(y,x) must be inconsistent with Aff Ç Precede(y,x). But this
contradicts 4.3,
so the contrary assumption cannot hold, establishing MAM does not elect x.
This implies MAM satisfies larger majority.
QED