A mathematically formal definition of MAM

Revised:  January 17, 2004

The following formal definition of the "Maximize Affirmed Majorities" voting rule is 
equivalent to the (less formal) definition of the MAM procedure.  The formal definition 
is deterministic and non-procedural, except at its end.  Since it is completely equivalent, 
it is useful in proofs about the properties of the MAM procedure.  

(See the document "Set Operators and Binary Relations" for useful definitions of 
common mathematical symbols and terms.  Note that we use the term "ranking" 
to refer to an ordering of alternatives.) 

Let N denote a finite non-empty set of individuals (i.e., voters) {1,2,...,n}. 

Let X denote a non-empty set of potential alternatives, possibly vast. 
Let A X denote a finite non-empty subset of "nominated" alternatives, 
often called the agenda, that the voters are asked to vote on. (Depending 
on the rules, individual voters could be permitted to include "write-in" 
candidates in their votes that would be treated as nominees.) 

For all i N, let Ri O(A) denote the ordering of A implied by the 
expressions contained in individual i's ballot.  

(We shall use the term "ranking" to  refer to an ordering of alternatives.  Thus each 
voter's vote is assumed to contain a ranking of the alternatives in A, or information 
about the alternatives from which a ranking can be readily inferred.  Thus MAM() 
could be used to tally "approval" votes or "cardinal utility" votes.  But there is at 
least one criterion, minimal defense, that requires that each voter be allowed to 
express nearly any ordering of the alternatives, so MAM explicitly allows each 
voter to express any ordering of the alternatives.)  

Let R denote the collection of all voters' ballots (R1,R2,...,Rn)
(That is, the voters' rankings of A, one ranking per voter.) 

For all a,b A, let R(a,b) denote the collection of ballots that rank a over b
(In other words, the ballots in R that express a "preference" for a over b.)  
For all a,b A, let #R(a,b) denote the number of ballots that rank a over b.) 

Let Pairs(A) denote the set of all possible ordered pairs of alternatives 
{(a,b) such that a A and b A}. (This is sometimes written as A2 or 
as A A.  Note that (a,b) and (b,a) are distinct pairs in Pairs(A) for 
all distinct a,b A.)  Where A is clear in the context, abbreviate Pairs

Let Majorities(A,R) denote the ordered pairs {(a,b) Pairs(A) such that 
#R(a,b) > #R(b,a)}.  Call each ordered pair in Majorities(A,R) a "majority."  
Where A and R are clear, abbreviate Majorities

(Note that Majorities(A,R) is an irreflexive asymmetric binary relation on A
but it is not necessarily complete or transitive or even acyclic.  Below we define 
an acyclic subset of Majorities(A,R), called the "affirmed" majorities, and then a 
superset of the affirmed majorities that is a strict "social" ordering of the alternatives, 
that satisfy many desirable criteria.)

For all a,b A, (a,b) is said to be won by a and lost by b 
        if and only if (a,b) Majorities(A,R). 
For all a,b A, (a,b) is said to be tied 
        if and only if #R(a,b) = #R(b,a) and a b.  
For all a,b,c A, (a,b) is said to involve c if and only if a = c or b = c.

For all non-empty B X and all collections of votes R, let R|B denote 
the restriction of R to the alternatives in B.  That is, R|B is the same 
as R except all preferences regarding alternatives not in B are deleted.

For all pairs of sets S1 and S2, let L(S1,S2) denote the set of all possible 
ordered pairs of strict orderings of S1 coupled with strict orderings of S2
(In other words, all (s1,s2) such that s1 L(S1) and s2 L(S2).  
For brevity's sake we shall often use a symbol such as s to denote 
an ordered pair (s1,s2) L(S1,S2).)

For all pairs of finite non-empty subsets of alternatives B,C X  
and all s L(R|B,C), let sR denote the first component of s and 
let sA denote the second component of s

(Each possible sR corresponds to a possible "strict hierarchy" of the voters, 
and each possible sA corresponds to a possible "strict hierarchy" of the specified 
subset of alternatives.  Note that nearly any random tie-breaking procedure 
can be constructed from a s picked randomly from L(R,A).)

Random Voter Hierarchy:  For all s L(R,A) and all a,b A
let R(ab) denote the collection of ballots in R that rank a over b or b over a
(The votes that are not indifferent regarding a versus b.)  For all s L(R,A
and all a,b A such that R(ab) is not empty, let Rsab denote the ballot in R(ab)  
ranked highest by sR.  For all s L(R,A), let RVH(A,R,s) denote the 
binary relation on A such that both of the following conditions hold: 
        1.  For all a,b A such that R(ab) is not empty, RVH(A,R,s) ranks 
             a over b if and only if Rsab ranks a over b.  
        2.  For all a,b A such that R(ab) is empty, RVH(A,R,s) ranks 
             a over b if and only if sA ranks a over b.  
Where A and R are clear, abbreviate RVH(s).  

(It can be easily proved that RVH(s) is a strict ordering of AMore properties 
of RVH(s) are detailed below
at the end of this document.  Note also that if s is 
picked randomly from L(R,A) and no voter expresses any indifference, then RVH is 
equivalent to the "Random Dictator" procedure.  RVH generalizes Random Dictator, 
always constructing a strict ordering even when some voters express indifference.  
MAM specifies that s is picked randomly for the sake of complete satisfaction 
of anonymity and neutrality, but it would be easy to design a variation of MAM 
that, when breaking ties, privileges some voters such as a chairperson or by seniority, 
or privileges some alternatives such as the status quo.)

For all a,b A and all P Pairs(A), (a,b) is consistent with P if and only if 
there do not exist (x1,x2),(x2,x3,),...,(xk-1,xk) P such that x1 = b and xk = a.  

For all P Pairs(A), P is internally consistent if and only if every ordered 
pair of alternatives in P is consistent with P. (This is usually called acyclicity.) 

For all a,b A and all P Pairs(A), P is a minimal set with which (a,b) is 
if and only if (a,b) is inconsistent with P and (a,b) is consistent 
with every strict subset of P.  

For all a,b A and all P Pairs(A) such that P is a minimal set 
with which (a,b) is inconsistent, (a,b) is said to cycle with P
and P {(a,b)} is said to be a cycle.  

For all a,b,c,d A, (a,b) is said to be the same size as (c,d) given R 
if and only if #R(a,b) = #R(c,d) and #R(b,a) = #R(d,c). (Note that in an 
election with many voters, it is unlikely two majorities will be the same size.) 

For all a,b,c,d A, (a,b) is said to be larger than (c,d) given R if and only if 
#R(a,b) > #R(c,d) or [#R(a,b) = #R(c,d) and #R(b,a) < #R(d,c)]. 

For all a,b,c,d A and all s L(R,A), (a,b) is said to precede (c,d) 
given (R,s) if and only if one of the following conditions holds: 
        1.  (a,b) is larger than (c,d) given R
        2.  (a,b) is the same size as (c,d) given R 
             and RVH(A,R,s) ranks d over b
        3.  (a,b) is the same size as (c,d) given R 
             and d = and RVH(A,R,s) ranks a over c

For all a,b A and all s L(R,A), let Precede(a,b,A,R,s) denote the 
ordered pairs {(c,d) Pairs(A) such that (c,d) precedes (a,b) given (R,s)}.  
Where A and R are clear, abbreviate Precede(a,b,s).

For all s L(R,A), let Affirmed(A,R,s) denote {(a,b) Majorities(A,R
such that (a,b) is consistent with Affirmed(A,R,s Precede(a,b,A,R,s)}.  
Where A and R are clear, abbreviate Affirmed(s).

(Note that Affirmed() is defined recursively but not circularly.  It can be quickly 
computed by considering the majorities one at a time in order of precedence, 
as described in the document MAM Procedure Definition.)  

For all s L(R,A), let Top(A,R,s) denote {a A such that, for all b A
(b,a) Affirmed(A,R,s)}.  Where A and R are clear, abbreviate Top(s). 

(Note that by theorem "At Least One Top", Top(A,R,s) always contains at least 
one alternative.  In elections with many voters, Top(A,R,s) will usually be a single 
alternative and independent of s.  See theorem "MAM is Reasonably Deterministic."

For all s L(R,A), let MAM(A,R,s) denote the (unique) alternative 
in Top(A,R,s) that RVH(A,R,s) ranks over every other alternative 
in Top(A,R,s).  Where A and R are clear, abbreviate MAM(s). 

(Note that by theorem "MAM is Resolute" there must exist such an alternative.)  

To elect an alternative in A given votes R, randomly pick s L(R,A
and elect the (unique) alternative MAM(A,R,s).


MAM2, a voting rule equivalent to MAM

The MAM() function defined in the previous section is completely equivalent to the 
MAM2() function defined in this section.  MAM2 finds the social orderings which 
"maximize affirmed majorities" and elects an alternative which tops such an ordering.  
This is similar to the Kemeny-Young "maximum likelihood estimation" voting rule, 
except MAM2 uses a leximax comparison of the possible social orderings while 
Kemeny-Young scores each of the possible social orderings by adding the sizes of 
the majorities it agrees with. (Two variations of Kemeny-Young have been described 
in the literature: one measures the size of a majority by subtracting the size of the 
opposition from the size of the support, and the other simply uses size of the support.  
MAM2 is more like the variation which uses the size of support.)  Kemeny-Young's 
theoretical claim regarding "maximum likelihood" of choosing the best social ordering 
can be seen to be flawed by consideration of nomination strategies and voter strategies: 
for instance, since Kemeny-Young fails the independence of clone alternatives 
criterion, this means nomination strategies can easily manipulate its maximum likelihood 
calculation.  Also, Kemeny-Young is hard to compute since the number of possible 
social orderings increases factorially with the number of alternatives, whereas MAM2  
can be quickly computed since it is equivalent to MAM

Refer to the definitions above, as needed.

For all r L(A), let Agreed(r,A,R) denote the ordered pairs of alternatives 
{(a,b) Majorities(A,R) such that r ranks a over b}.  (In other words, 
the majorities consistent with r.)  Where A and R are clear from the context, 
abbreviate Agreed(r).

For all r,r' L(A), let DistinctAgreed(r,r',A,R) denote the ordered pairs 
of alternatives in Agreed(r,A,R) or in Agreed(r',A,R) but not in both.  
Where A and R are clear, abbreviate DistinctAgreed(r,r').

For all s L(R,A) and all r,r' L(A) such that DistinctAgreed(r,r',A,R) is 
not empty, let LargestDistinctAgreed(r,r',A,R,s) denote the (unique) ordered 
pair (a,b) DistinctAgreed(r,r',A,R) such that (a,b) precedes all other ordered 
pairs in DistinctAgreed(r,r',A,R) given (R,s). (In other words, of the majorities 
consistent with r or with r' but not with both, the one with the greatest precedence.)  
Where A and R are clear, abbreviate LargestDistinctAgreed(r,r',s).

(Note that theorem "Precedence is a Strict Ordering" establishes that when 
DistinctAgreed(r,r',A,R) is not empty, LargestDistinctAgreed(r,r',A,R,s
is indeed unique.)  

For all s L(R,A) and all r,r' L(A), r dominates r' given (R,s)  
if and only if DistinctAgreed(r,r',A,R) is not empty and 
LargestDistinctAgreed(r,r',A,R) Agreed(r,A,R).  (In other words, 
r dominates r' if and only if, of the majorities consistent with r or with r' but 
not with both, the majority with the greatest precedence is consistent with r.  

(Note that theorem "Dominance is an Ordering" establishes the dominance relation is an 
ordering of the set of strict rankings of A.  Note also that theorem "MAM is Reasonably 
establishes there is a unique undominated ranking if no two alternatives 
tie pairwise, and if in addition no two majorities are the same size then the unique 
undominated ranking is independent of s.)

For all s L(R,A), let UndominatedRankings(A,R,s) denote the orderings 
{r L(A) such that no r' L(A) dominates r given (R,s)}.  Where A and R  
are clear, abbreviate UndominatedRankings(s).

For all s L(R,A), let Top2(A,R,s) denote {a A such that there exists 
r UndominatedRankings(A,R,s) such that [for all b Ar does not 
rank b over a]}. (In other words, every alternative which tops at least one 
undominated ranking.)  Where A and R are clear, abbreviate Top2(s).

For all s L(R,A), let MAM2(A,R,s) denote the alternative in Top2(A,R,s
which RVH(A,R,s) ranks over all other alternatives in Top2(A,R,s).  
Where A and R are clear, abbreviate MAM2(s).

To elect an alternative in A given R, randomly pick s L(R,A
and elect the alternative MAM2(A,R,s).

Theorem "MAM2 = MAM" establishes MAM() and MAM2() are completely equivalent. 

The MAM social ordering

Though MAM has been defined as a reasonably deterministic function which chooses 
one alternative, the principles upon which MAM is based can be used to construct a 
strict "social" ordering of the alternatives.  We present three natural ways to do so, 
which turn out to be completely equivalent.  The second way is the most efficient 
to calculate.

The first way to construct a strict social ordering uses an iterative technique that can 
be applied to any resolute (i.e., single-winner) voting rule:  The kth alternative in the 
social ordering is the alternative which would be elected if the 1st through (k-1)th  
alternatives were deleted from the ballots.  Here is the formal definition of Rsocial():  

For all non-empty B A and all R, let R|B denote the restriction of R to B
(That is, R|B is the same as R except all alternatives not in B are deleted.) 
For all non-empty B A and all s L(R,A), let s|B denote the restriction of s  
to B. (That is, s|B is the same as s except all alternatives not in B are deleted.) 

Define Finish() and Bottom() recursively.  In words, Finish(.,k) is the alternative 
that finishes in kth place, calculated by deleting the top k-1 finishers from the votes 
and recalculating MAM's choice  from the remaining nominees.  Bottom(.,k) is 
the subset of  nominees that remain when the top k-1 finishers are deleted.  
Their formal definitions are as follows: 

For all s L(R,A), let Bottom(A,R,s,1) = A

For all s L(R,A), let Finish(A,R,s,1) = MAM(A,R,s).  

For all s L(R,A) and all k {2,3,...,#A}, let Bottom(A,R,s,k
denote Bottom(A,R,s,k-1)\{Finish(A,R,s,k-1)}.

For all s L(R,A) and all k {2,3,...,#A}, let Finish(A,R,s,k
denote MAM(Bottom(A,R,s,k),R|Bottom(A,R,s,k),s|Bottom(A,R,s,k)).  

For all s L(R,A), let Rsocial(A,R,s) denote the binary relation on A such 
that, for all a,b A, Rsocial(A,R,s) ranks a over b if and only if there exist 
j,k {1,2,...,#A} such that Finish(A,R,s,j) = a and Finish(A,R,s,k) = b 
and  j < k.  Where A and R are clear, abbreviate Rsocial(s).

A second way to construct a strict social ordering, specific to MAM, is to begin 
with Affirmed(A,R,s) (the majorities affirmed by MAM, which are acyclic but 
not necessarily complete) and then iteratively resolve the "highest" remaining social 
indifference by using RVH(A,R,s) (a strict ordering), repeating until no social 
indifferences remain.  Here is the formal definition of Rsocial2(): 

For all P Pairs(A), let Tied(P) denote {a A such that, 
for some b A\{a}, (a,b) P and (b,a) P}. 

For all P Pairs(A), let TopTied(P) denote {a Tied(P) such that, 
for all b Tied(P)\{a}, (b,a) P}. (Note that theorem "At Least One 
Top (3)"
establishes that if Tied(P) is not empty and P is internally 
consistent, then TopTied(P) is not empty.) 

For all s L(R,A) and all P Pairs(A), let Next(P,A,R,s
denote {a TopTied(P) such that RVH(A,R,s) does not rank 
any b TopTied(P) over a}. (Note that by theorem "Random 
Voter Hierarchy is a Strict Ordering"
, if TopTied(P) is not empty 
then Next(P,A,R,s) is a singleton alternative.) 

For all s L(R,A), let P0(A,R,s) denote the subset of Pairs(A
such that, for all a,b A, (a,b) P0(A,R,s) if and only if a b and 
(b,a) is inconsistent with Affirmed(A,R,s). (Note that by theorem 
"Reversed Inconsistent Pair is Consistent"
and theorem "Consistency 
, P0(A,R,s) is internally consistent.)  

For all integers k > 0 and all s L(R,A), let Pk(A,R,s) denote the 
subset of Pairs(A) such that, for all a,b A, (a,b) Pk(A,R,s
if and only if at least one of the following conditions holds: 
    1.  (a,b) Pk-1(A,R,s).  
    2.  (b,a) Pk-1(A,R,s) and a b and Next(Pk-1(A,R,s),A,R,s) = {a}. 
(Note that Pk() is defined recursively.  Furthermore, it can be easily 
seen that, for all integers k > 0, if Tied(Pk-1(A,R,s)) is not empty then 
Tied(Pk(A,R,s)) Tied(Pk-1(A,R,s))\Next(Pk-1(A,R,s),A,R,s).)   

For all s L(R,A), let s denote the smallest non-negative integer such 
that Tied(Ps(A,R,s)) is empty. (Note that, by the preceding argument, 
s must exist, and furthermore 0 s #A.) 

For all s L(R,A), let Rsocial2(A,R,s) denote the binary relation on A 
such that, for all a,b A, Rsocial2(A,R,s) ranks a over b if and only if 
(a,b) Ps(A,R,s). (Actually, Rsocial2(A,R,s) = Ps(A,R,s), which 
can be seen by inspection of the definition of binary relation.  The 
term "rank over" is merely different language that means the same.) 

A third way to construct a strict social ordering, also specific to MAM, is to weaken 
the dominance relation in such a way that it becomes a strict ordering of L(A), 
and then choose the unique ranking in L(A) that tops this weakened relation.  
Here is the formal definition of Rsocial3():  

For all r L(A) and all x A, let Over(r,x) denote {y A such 
that r ranks y over x}. (The alternatives that r ranks over x.) 

For all r L(A) and all x A, let Place(r,x) = 1 + #Over(r,x). 
(Thus the alternative atop r is in 1st place according to r, etc.)

For all r L(A) and all k {1,2,...,#A}, let NthPlaceAlternative(r,k
denote the unique x A such that Place(r,x) = k.  

For all distinct r,r' L(A), let TopmostDifferentPlace(r,r'
denote the smallest k {1,2,...,#A} such that 
NthPlaceAlternative(r,k) NthPlaceAlternative(r',k). 

For all distinct r,r' L(A), let TopmostDifferentAlternative(r,r'
denote NthPlaceAlternative(r,TopmostDifferentPlace(r,r')). 

For all s L(R,A) and all r,r' L(A), say r weakly dominates r' 
given (R,s) if and only if at least one of the following conditions holds: 
        (1)  r dominates r' given (R,s).  
        (2)  r' does not dominate r given (R,s) and r r' and 
              RVH(A,R,s) ranks TopmostDifferentAlternative(r,r'
              over TopmostDifferentAlternative(r',r). 
(Note that theorem "Weak Dominance is a Strict Ordering" shows 
the weak dominance relation is a strict ordering of L(A).)

For all s L(R,A), let Rsocial3(A,R,s) denote the (unique) r L(A
such that, for all r' L(A)\{r}, r weakly dominates r' given (R,s)

Theorem "RSocial = RSocial2" and theorem "RSocial = RSocial3" establish the 
complete equivalence of Rsocial(), Rsocial2(), and Rsocial3().  Theorem "Properties 
of RSocial"
establishes the following properties: 

For all s L(R,A), Rsocial(s) is a strict ordering of the alternatives.  
For all s L(R,A), Rsocial(s) ranks MAM(s) over all other alternatives.  
For all s L(R,A) and all (a,b) Affirmed(s), Rsocial(s) ranks a over b.  
For all s L(R,A) and all (a,b) Majorities\Affirmed(s), Rsocial(s) ranks b over a
For all s L(R,A), Rsocial(s) UndominatedRankings(s).  
For all s L(R,A) and all a,b A, if (a,b) is inconsistent with Affirmed(s
    then Rsocial(s) ranks b over a
For all s L(R,A) and all non-empty B A such that Rsocial(A,R,s) ranks every 
alternative in A\B over every alternative in B, both of the following conditions hold: 
        1.  Affirmed(B,R|B,s|B) = Affirmed(A,R,s) Pairs(B).  
        2.  Affirmed(A\B,R|A\B,s|A\B) = Affirmed(A,R,s) Pairs(A\B).  

Also, it is established elsewhere that the MAM social ordering satisfies the criteria 
local independence of irrelevant alternatives (LIIA) and immunity from majority 
(IMC). (See the documents "Proof MAM satisfies Local Independence 
of Irrelevant Alternatives
" and "Immunity from Majority Complaints".)

A formal definition of the Random Voter Hierarchy procedure

The Random Voter Hierarchy procedure defined informally in the document 
"MAM Procedure Definition"
is equivalent to the following formal definition 
(but it will be shown below that the RVH() function can also be used in a 
deterministic way):

Refer to the definitions above. 
Randomly pick any s L(R,A). 
Select the strict ranking RVH(A,R,s).

Constructing a strict random ordering sR of the ballots and a strict random ordering sA  
of the alternatives is computationally less efficient than the Random Voter Hierarchy 
procedure informally defined in "MAM procedure definition", since the Random Voter 
Hierarchy procedure typically constructs its strict ordering of the alternatives by adopting 
the preferences of only a few (randomly picked) ballots. (Atypical situations would 
involve massive voter indifference.)  However, even though it is less practical to use 
a pair of strict orderings sR and sA, the fact that the definition above is equivalent to 
Random Voter Hierarchy is useful in proofs about the properties of Random Voter 
Hierarchy (monotonicityindependence of irrelevant alternatives, etc.) and in 
proofs about the properties of procedures such as MAM which utilize Random Voter 
Hierarchy for tie-breaking purposes.  Here are some of the properties of Random 
Voter Hierarchy, established elsewhere:

Theorem "Random Voter Hierarchy is independent of irrelevant alternatives"
shows that the probability that the restriction to some B A of the ordering 
constructed by Random Voter Hierarchy is the same as the probability that 
Random Voter Hierarchy would construct that same ordering of B given the 
voters' rankings restricted to B.

Theorem "Random Voter Hierarchy is monotonic" shows that if some voter(s) 
uprank an alternative, the probability that the ordering constructed by Random 
Voter Hierarchy ranks that alternative over any other particular alternative 
will not decrease.

Theorem "Random Voter Hierarchy ranks clones together" establishes that
the ordering constructed by Random Voter Hierarchy never ranks a non-clone
between clones. (For the definition of clone alternatives, see the documents 
"Independence from Similar Alternatives in Social Choice Procedures" and 
"Proof MAM is Independent of Clone Alternatives."  See also the 
paper by TN Tideman, "Independence of Clones as a Criterion for Voting 
Rules," Social Choice and Welfare, 1987.)  

Theorem "Random Voter Hierarchy satisfies strong Pareto" establishes that, 
for all a,b A, if no voter ranks b over a and at least one voter ranks a over b
then the ordering constructed by Random Voter Hierarchy will with certainty 
rank a over b.

There may be situations in which complete determinism is desired, even though this 
must come at the expense of anonymity or neutrality. (In other words, distinguishing 
some voters such as a chairperson or senior members of the group, or distinguishing 
some alternatives such as the status quo.)  This can be accomplished simply by picking 
s L(R,A) non-randomly.  Its first component, the ordering of the votes sR, could 
be in order of seniority, and its second component, the ordering of the alternatives sA
could rank the status quo highest and rank the remaining alternatives in the chronological 
order that they were nominated.  In this case, the tie-break ordering RVH(A,R,s) would 
be deterministic.  These issues are unimportant when there are many voters, as in large 
public elections, but could occasionally affect the outcome in small elections (where ties 
would not be rare).  

In situations involving a series of votes in which voting on alternatives already nominated 
is interspersed with nomination of additional alternatives, it would be sensible to pick the 
same sR for each vote (unless for some reason the set of voters changes).  It would also 
be sensible to append the latest nominees to the bottom of sA.  If these measures are
employed, the outcome will not change merely by retallying the same collection of votes
on the same set of nominees.  Thus, in tied situations, no one would have an incentive to
call for an additional round of voting hoping that next time the tie would be resolved in
their favor.