**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

Let * X* denote a non-empty set of potential alternatives,
possibly vast.

Let

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

expressions contained in individual

(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,

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

(That is, the voters' rankings of

For all *a,b* Î
*
A*, let

(In other words, the ballots in

For all

Let Pairs(** A**)
denote the set of all possible ordered pairs of alternatives

{

as

all distinct

Let Majorities(*A**,*** R**) denote
the ordered pairs {

#

Where

(Note that Majorities(*A**,*** R**)
is an

but it is not necessarily

an

superset of the affirmed majorities that is a strict "social" ordering of the alternatives,

that satisfy many desirable criteria.)

For all *a,b* Î
** A**,

if and only if

For all

if and only if #

For all

For all non-empty *B* Í
* X* and all collections of votes

the restriction of

as

For all pairs of sets *S*_{1}
and *S*_{2}, let L(*S*_{1}*,S*_{2})
denote the set of all possible

ordered pairs of strict orderings
of *S*_{1} coupled with strict orderings of *S*_{2}.

(In other words, all *(*s_{1}*,*s_{2}*)*
such that s_{1} Î
L(*S*_{1}) and s_{2}
Î L(*S*_{2}).

For
brevity's sake we
shall often use a symbol such as s to denote

an ordered pair *(*s_{1}*,*s_{2}*)*
Î L(*S*_{1}*,S*_{2}).)

For all pairs of finite non-empty
subsets of alternatives *B,C*
Í **X**

and all s
Î L(** R**|

let s

(Each possible s* _{R}* corresponds to a
possible "strict hierarchy" of the voters,

and each possible s

subset of alternatives. Note that nearly any random tie-breaking procedure

can be constructed from a s picked randomly from L(

*Random
Voter Hierarchy*: For all s Î
L(**R**,** A**) and all

let

(The votes that are not indifferent regarding

and all

ranked highest by s

binary relation on

1. For all

2. For all

Where

(It can be easily proved
that RVH(s) is a strict
ordering of * A*. More
properties

of RVH(s) are detailed below at the end of this document. Note also that if s is

picked randomly from L(

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

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

there do not exist

For all *P* Í
Pairs(** A**),

pair of alternatives in

For all *a,b* Î
** A** and all

inconsistent if and only if

with every strict subset of

For all *a,b* Î
** A** and all

with which

and

For all *a,b,c,d* Î
** A**,

if and only if #

election with many voters, it is unlikely two majorities will be the same size.)

For all *a,b,c,d* Î
** A**,

#

For all
*a,b,c,d* Î
** A** and all s Î
L(

given

1.

2.

and RVH(

3.

and

For all *a,b* Î
** A** and all s Î
L(

ordered pairs {

Where

For all s Î
L(**R**,** A**), let Affirmed(

such that

Where

(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(

(Note that by theorem
"At Least One Top", Top(*A**, R,*s)
always contains at least

one alternative. In elections with many voters, Top(

alternative and independent of s. See theorem "MAM is Reasonably Deterministic.")

For all s Î
L(**R**,** A**), let MAM(

in Top(

in Top(

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

To elect an alternative in ** A**
given votes

and elect the (unique) alternative MAM(

**MAM _{2}, a voting rule equivalent to MAM**

The MAM() function
defined in the previous section is completely
equivalent to the

MAM_{2}() function defined in this
section. MAM_{2} 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 MAM_{2} 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.

MAM_{2}
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 MAM_{2}

can be quickly computed since it is equivalent to MAM.

Refer to the definitions above, as needed.

For all * r* Î
L(** A**), let Agreed(

{

the majorities consistent with

abbreviate Agreed(

For all *r,r'* Î
L(** A**), let DistinctAgreed(

of alternatives in Agreed(

Where

For all s Î
L(**R**,** A**) and all

not empty, let LargestDistinctAgreed(

pair

pairs in DistinctAgreed(

consistent with

Where

(Note that theorem
"Precedence is a Strict Ordering" establishes that when

DistinctAgreed(*r,r', A,R*)
is not empty, LargestDistinctAgreed(

is indeed unique.)

For all s Î
L(**R**,** A**) and all

if and only if DistinctAgreed(

LargestDistinctAgreed(

not with both, the majority with the greatest precedence is consistent with

(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 s.)

For all s Î
L(**R**,** A**), let UndominatedRankings(

{

are clear, abbreviate UndominatedRankings(s).

For all s Î
L(**R**,** A**), let Top

rank

undominated ranking.) Where

For all s Î
L(**R**,** A**), let MAM

which RVH(

Where

To elect an alternative in ** A** given

and elect the alternative MAM

Theorem
"MAM_{2} = MAM" establishes MAM()
and MAM_{2}() are
completely equivalent.

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 *k*^{th} alternative in the

social ordering is the alternative which would be elected if the 1^{st} through (*k*-1)^{th}

alternatives
were deleted from the ballots. Here is the formal definition of *R*_{social}():

For all non-empty *B* Í
** A** and all

(That is,

For all non-empty

to

Define Finish()
and Bottom() recursively. In words, Finish(.*,k*) is the alternative

that
finishes in *k*^{th} 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(

For all s Î
L(**R**,** A**), let Finish(

For all s Î
L(**R**,** A**) and all

denote Bottom(

For all s Î
L(**R**,** A**) and all

denote MAM(Bottom(

For all s Î
L(**R**,** A**), let

that, for all

and

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 *R*_{social2}():

For all *P* Í
Pairs(** A**), let Tied(

for some

For all *P* Í
Pairs(** A**), let TopTied(

for all

Top (3)" establishes that if Tied(

consistent, then TopTied(

For all s Î
L(**R**,** A**) and all

denote {

any

Voter Hierarchy is a Strict Ordering", if TopTied(

then Next(

For all s Î
L(**R**,** A**), let

such that, for all

"Reversed Inconsistent Pair is Consistent" and theorem "Consistency

Maintained",

For all integers *k*
> 0 and all s Î
L(**R**,** A**), let

subset of Pairs(

if and only if at least one of the following conditions holds:

1.

2.

(Note that

seen that, for all integers

Tied(

For all s Î
L(**R**,** A**), let

that Tied(

For all s Î
L(**R**,** A**), let

such that, for all

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(

Here is the formal definition of

For all *r* Î
L(** A**) and all

that

For all *r* Î
L(** A**) and all

(Thus the alternative atop

For all *r* Î
L(** A**) and all

denote the unique

For all distinct *r,r'* Î
L(** A**), let TopmostDifferentPlace(

denote the smallest

NthPlaceAlternative(

For all distinct *r,r'* Î
L(** A**), let TopmostDifferentAlternative(

denote NthPlaceAlternative(

For all s Î
L(**R**,** A**) and all

given

(1)

(2)

RVH(

over TopmostDifferentAlternative(

(Note that theorem "Weak Dominance is a Strict Ordering" shows

the weak dominance relation is a strict ordering of L(

For all s Î
L(**R**,** A**), let

such that, for all

Theorem
"RSocial = RSocial2" and theorem
"RSocial = RSocial3" establish the

complete equivalence of *R*_{social}(), *R*_{social2}(),
and *R*_{social3}(). Theorem
"Properties

of RSocial" establishes the following
properties:

For all s Î
L(**R**,** A**),

For all s Î L(

For all s Î L(

For all s Î L(

For all s Î L(

For all s Î L(

then

For all s Î L(

alternative in

1. Affirmed(

2. Affirmed(

Also, it is established elsewhere that the MAM social
ordering satisfies the criteria

*local independence of irrelevant alternatives* (*LIIA*) and *immunity from majority
complaints* (

of Irrelevant Alternatives

**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(

Constructing a strict random ordering s* _{R}* of the ballots and a
strict random ordering s

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 s

Random Voter Hierarchy is useful in proofs about the properties of Random Voter

Hierarchy (

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

voters' rankings restricted to

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

then the ordering constructed by Random Voter Hierarchy will with certainty

rank

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 s

be in order of seniority, and its second component, the ordering of the alternatives s

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(

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 s* _{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 s

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.