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 AX 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 iN, let RiO(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 aA and bA}. (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,bA.)  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,bA, (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,bA, (a,b) is said to be tied
if and only if #R(a,b) = #R(b,a) and ab.
For all a,b,cA, (a,b) is said to involve c if and only if a = c or b = c.

For all non-empty BX 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 (σ1,σ2) such that σ1L(S1) and σ2L(S2).
For brevity's sake we shall often use a symbol such as σ to denote
an ordered pair (σ1,σ2)L(S1,S2).)

For all pairs of finite non-empty subsets of alternatives B,CX
and all σ ∈ L(R|B,C), let σR denote the first component of σ and
let σA denote the second component of σ.

(Each possible σR corresponds to a possible "strict hierarchy" of the voters,
and each possible σA 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 σ picked randomly from L(R,A).)

Random Voter Hierarchy:  For all σ ∈ L(R,A) and all a,bA
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 σ ∈ L(R,A
and all a,bA such that R(ab) is not empty, let Rσab denote the ballot in R(ab)
ranked highest by σR.  For all σ ∈ L(R,A), let RVH(A,R,σ) denote the
binary relation on A such that both of the following conditions hold:
1.  For all a,bA such that R(ab) is not empty, RVH(A,R,σ) ranks
a over b if and only if Rσab ranks a over b.
2.  For all a,bA such that R(ab) is empty, RVH(A,R,σ) ranks
a over b if and only if σA ranks a over b.
Where A and R are clear, abbreviate RVH(σ).

(It can be easily proved that RVH(σ) is a strict ordering of AMore properties
of RVH(σ) are detailed below
at the end of this document.  Note also that if σ 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 σ 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,bA and all PPairs(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 PPairs(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,bA and all PPairs(A), P is a minimal set with which (a,b) is
inconsistent
if and only if (a,b) is inconsistent with P and (a,b) is consistent
with every strict subset of P.

For all a,bA and all PPairs(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,dA, (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,dA, (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,dA and all σ ∈ L(R,A), (a,b) is said to precede (c,d)
given (R,σ) 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,σ) ranks d over b
3.  (a,b) is the same size as (c,d) given R
and d = and RVH(A,R,σ) ranks a over c

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

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

(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 σ ∈ L(R,A), let Top(A,R,σ) denote {aA such that, for all bA
(b,a)Affirmed(A,R,σ)}.  Where A and R are clear, abbreviate Top(σ).

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

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

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

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

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 rL(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 σ ∈ 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,σ) 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,σ). (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',σ).

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

For all σ ∈ L(R,A) and all r,r'L(A), r dominates r' given (R,σ)
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
Deterministic"
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 σ.)

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

For all σ ∈ L(R,A), let Top2(A,R,σ) denote {aA such that there exists
rUndominatedRankings(A,R,σ) such that [for all bAr 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(σ).

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

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

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 BA 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 BA and all σ ∈ L(R,A), let σ|B denote the restriction of σ
to B. (That is, σ|B is the same as σ 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 σ ∈ L(R,A), let Bottom(A,R,σ,1) = A

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

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

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

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

A second way to construct a strict social ordering, specific to MAM, is to begin
with Affirmed(A,R,σ) (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,σ) (a strict ordering), repeating until no social
indifferences remain.  Here is the formal definition of Rsocial2():

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

For all PPairs(A), let TopTied(P) denote {aTied(P) such that,
for all bTied(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 σ ∈ L(R,A) and all PPairs(A), let Next(P,A,R,σ)
denote {aTopTied(P) such that RVH(A,R,σ) does not rank
any bTopTied(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,σ) is a singleton alternative.)

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

For all integers k > 0 and all σ ∈ L(R,A), let Pk(A,R,σ) denote the
subset of Pairs(A) such that, for all a,bA, (a,b)Pk(A,R,σ)
if and only if at least one of the following conditions holds:
1.  (a,b)Pk-1(A,R,σ).
2.  (b,a)Pk-1(A,R,σ) and ab and Next(Pk-1(A,R,σ),A,R,σ) = {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,σ)) is not empty then
Tied(Pk(A,R,σ)) ⊆ Tied(Pk-1(A,R,σ))\Next(Pk-1(A,R,σ),A,R,σ).)

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

For all σ ∈ L(R,A), let Rsocial2(A,R,σ) denote the binary relation on A
such that, for all a,bA, Rsocial2(A,R,σ) ranks a over b if and only if
(a,b)Ps(A,R,σ). (Actually, Rsocial2(A,R,σ) = Ps(A,R,σ), 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 rL(A) and all xA, let Over(r,x) denote {yA such
that r ranks y over x}. (The alternatives that r ranks over x.)

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

For all rL(A) and all k ∈ {1,2,...,#A}, let NthPlaceAlternative(r,k
denote the unique xA 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 σ ∈ L(R,A) and all r,r'L(A), say r weakly dominates r'
given (R,σ) if and only if at least one of the following conditions holds:
(1)  r dominates r' given (R,σ).
(2)  r' does not dominate r given (R,σ) and rr' and
RVH(A,R,σ) 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 σ ∈ L(R,A), let Rsocial3(A,R,σ) denote the (unique) rL(A
such that, for all r'L(A)\{r}, r weakly dominates r' given (R,σ)

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 σ ∈ L(R,A), Rsocial(σ) is a strict ordering of the alternatives.
For all σ ∈ L(R,A), Rsocial(σ) ranks MAM(σ) over all other alternatives.
For all σ ∈ L(R,A) and all (a,b)Affirmed(σ), Rsocial(σ) ranks a over b.
For all σ ∈ L(R,A) and all (a,b)Majorities\Affirmed(σ), Rsocial(σ) ranks b over a
For all σ ∈ L(R,A), Rsocial(σ) ∈ UndominatedRankings(σ).
For all σ ∈ L(R,A) and all a,bA, if (a,b) is inconsistent with Affirmed(σ)
then Rsocial(σ) ranks b over a
For all σ ∈ L(R,A) and all non-empty BA such that Rsocial(A,R,σ) ranks every
alternative in A\B over every alternative in B, both of the following conditions hold:
1.  Affirmed(B,R|B,σ|B) = Affirmed(A,R,σ) ∩ Pairs(B).
2.  Affirmed(A\B,R|A\B,σ|A\B) = Affirmed(A,R,σ) ∩ 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
complaints
(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 σ ∈ L(R,A).
Select the strict ranking RVH(A,R,σ).

Constructing a strict random ordering σR of the ballots and a strict random ordering σA
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 σR and σA, 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 BA 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
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,bA, 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
σ ∈ L(R,A) non-randomly.  Its first component, the ordering of the votes σR, could
be in order of seniority, and its second component, the ordering of the alternatives σA
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,σ) 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 σR 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 σA.  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.