Some theorems useful in proofs about MAM
Revised: December 28, 2002
For definitions of terms, refer to the formal definitions of MAM and MAM2.
Theorem:
"Random Voter Hierarchy is a Strict Ordering":
(1) For all s Î L(R,A)
and all alternatives a Î A, RVH(A,R,s)
does not
rank a over a. (That
is, RVH is irreflexive.)
(2) For all s Î L(R,A)
and all distinct alternatives a,b Î A,
if RVH(A,R,s)
does
not rank a over b
then RVH(A,R,s)
ranks b over a. (That
is, RVH is complete.)
(3) For all s Î L(R,A)
and all alternatives a,b Î A,
if RVH(A,R,s)
ranks a over b
then RVH(A,R,s)
does not rank b over a. (That
is, RVH is asymmetric.)
(4) For all s Î L(R,A)
and all alternatives a,b,c Î A,
if RVH(A,R,s)
ranks a
over b and b over c then RVH(A,R,s)
ranks a over c.
(That is, RVH is transitive.)
Proofs of (1,2,3): These follow by inspection of the definition of RVH().
Proof of (4): Pick
any s Î L(R,A).
Abbreviate RVH = RVH(A,R,s).
Pick any alternatives a,b,c Î A
(not necessarily distinct). Assume RVH ranks
a over b and b over c. We must show RVH ranks
a over c. By 1, RVH is
irreflexive, so a ¹ b and b ¹
c. By 3, RVH is asymmetric, so a ¹
c.
Thus a,b,c are three distinct alternatives. There are four cases to
consider:
Case 4.1: Every voter voted indifference between a,b and indifference
between b,c. This implies R(ab) is empty and R(bc) is empty and
R(ac) is empty. Since R(ab) is empty and RVH ranks a over b, it follows
by the definition of RVH() that sA ranks a over b. Since R(bc) is empty
and RVH ranks b over c, it follows by the definition of RVH() that
sA ranks b over c. Thus sA ranks a over c. Since R(ac) is empty
and sA ranks a over c, it follows that RVH ranks a over c in case 4.1.Case 4.2: At least one voter did not vote indifference between a,b
and every voter voted indifference between b,c. This implies R(ab)
is not empty and R(bc) is empty. By the definition of RVH(),
both of the following must hold:
(4.2.1) Rsab (the vote in R(ab) ranked highest by sR) ranks a
over b and is indifferent between b,c.
(4.2.2) Every vote in R ranked over Rsab by sR is indifferent
between a,b and indifferent between b,c.
By 4.2.1, Rsab ranks a over c. Thus, by 4.2.2 and the definition
of RVH(), RVH ranks a over c in case 4.2.Case 4.3: Every voter voted indifference between a,b and at least one
voter did not vote indifference between b,c. By reasoning that parallels
case 4.2, RVH ranks a over c in case 4.3.Case 4.4: At least one voter did not vote indifference between a,b
and at least one voter did not vote indifference between b,c.
This implies R(ab) is not empty and R(bc) is not empty. By the
definition of RVH(), the following four statements must hold:
(4.4.1) Rsab (the vote in R(ab) ranked highest by sR) ranks a over b.
(4.4.2) Every vote in R ranked over Rsab by sR is indifferent
between a,b.
(4.4.3) Rsbc (the vote in R(bc) ranked highest by sR) ranks b over c.
(4.4.4) Every vote in R ranked over Rsbc by sR is indifferent
between b,c.
There are two subcases to consider:
Case 4.4.5: Rsab = Rsbc. Since Rsab ranks a over b and b over c,
Rsab ranks a over c. Since every vote in R ranked over Rsab
by sR is indifferent between a,b,c, it follows that RVH ranks
a over c in case 4.4.5.
Case 4.4.6: Rsab ¹ Rsbc. Since sR is a strict ordering of the ballots,
either sR ranks Rsab over Rsbc or sR ranks Rsbc over Rsab.
Thus there are two subcases to consider:
Case 4.4.6.1: sR ranks Rsab over Rsbc. By 4.4.4, Rsab is
indifferent between b,c. Thus Rsab ranks a over c.
By 4.4.2 and 4.4.4, every vote in R ranked over Rsab
by sR is indifferent between a,b,c. Thus it follows
that RVH ranks a over c in case 4.4.6.1.
Case 4.4.6.2: sR ranks Rsab over Rsbc. By reasoning
that parallels case 4.4.6.1, RVH ranks a over c
in case 4.4.6.2.
Since RVH ranks a over c in both subcases, RVH ranks a
over c in case 4.4.6.
Since RVH ranks a over c in both subcases, RVH ranks a over c
in case 4.4.
Since RVH ranks a over c
in all four cases, this means it is transitive.
Since RVH is irreflexive, complete,
asymmetric and transitive,
RVH is a strict ordering of the
alternatives.
QED
Theorem: "Precedence
is a Strict Ordering":
(1) For all s Î L(R,A)
and all p Î Pairs, p
does not precede p given (R,s).
(In other words, precedence is irreflexive.)
(2) For all s Î L(R,A)
and all distinct ordered pairs p,p' Î Pairs,
if p does not precede p' given (R,s)
then p' precedes p given (R,s).
(In other words, precedence is complete.)
(3) For all s Î L(R,A)
and all ordered pairs p,p' Î Pairs,
if p precedes p' given (R,s)
then p' does not precede p given (R,s).
(In other words, precedence is asymmetric.)
(4) For all s Î L(R,A)
and all ordered pairs p,p',p" Î Pairs,
if p precedes p' given (R,s)
and p' precedes p" given (R,s),
then p precedes p" given (R,s).
(In other words, precedence is transitive.)
Proof of (1): Pick
any s Î L(R,A)
and any p Î Pairs.
Abbreviate by
omitting R and s from the notation,
and abbreviate
RVH = RVH(s).
Let (a,b) denote p. Clearly none of the following four
conditions holds:
#R(a,b) > #R(a,b)
#R(b,a) > #R(b,a)
RVH ranks b
over b.
RVH ranks a over a.
It follows by the definition of
precedence that p does not precede p,
meaning precedence is irreflexive.
Proof of (2): Pick
any s Î L(R,A)
and any distinct p,p' Î Pairs.
Abbreviate by omitting R and s from the notation,
and abbreviate
RVH = RVH(s). Assume p does not precede p'. Let (a,b) denote p
and let (c,d) denote p'. Since (a,b)
does not precede (c,d), by the
definition of precedence none of the following four conditions can
hold:
#R(a,b) > #R(c,d)
#R(a,b) = #R(c,d)
and #R(d,c) > #R(b,a)
#R(a,b) = #R(c,d)
and #R(d,c) = #R(b,a) and RVH ranks d
over b.
#R(a,b) = #R(c,d)
and #R(d,c) = #R(b,a) and d=b
and RVH ranks a over c.
Thus, by theorem
"Random Voter Hierarchy is a Strict Ordering",
at least one of the following four conditions must hold:
#R(c,d) > #R(a,b)
#R(c,d) = #R(a,b)
and #R(b,a) > #R(d,c)
#R(c,d) = #R(a,b)
and #R(b,a) = #R(d,c) and RVH ranks b
over d.
#R(c,d) = #R(a,b)
and #R(b,a) = #R(d,c) and b=d
and RVH ranks c over a.
This implies p' precedes p given (R,s),
establishing (2),
meaning precedence is complete.
Proof of (3): Pick
any s Î L(R,A)
and any p,p' Î Pairs.
Abbreviate
by omitting R and s from the notation. Abbreviate RVH = RVH(s).
Assume p precedes p'. By 1 (irreflexivity), p ¹
p'. Let (a,b) denote p
and let (c,d) denote p'. Since (a,b) precedes (c,d), one
of the following
four conditions must hold:
#R(a,b) > #R(c,d)
#R(a,b) = #R(c,d)
and #R(d,c) > #R(b,a)
#R(a,b) = #R(c,d)
and #R(d,c) = #R(b,a) and RVH ranks d
over b.
#R(a,b) = #R(c,d)
and #R(d,c) = #R(b,a) and d=b
and RVH ranks a over c.
By inspection and by theorem
"Random Voter Hierarchy is a Strict Ordering",
none of the following four conditions can hold:
#R(c,d) > #R(a,b)
#R(c,d) = #R(a,b)
and #R(b,a) > #R(d,c)
#R(c,d) = #R(a,b)
and #R(b,a) = #R(d,c) and RVH ranks b
over d.
#R(c,d) = #R(a,b)
and #R(b,a) = #R(d,c) and b=d
and RVH ranks c over a.
This means p' cannot precede p given (R,s),
establishing (3),
meaning precedence is asymmetric.
Proof of (4): Pick
any s Î L(R,A)
and any p,p',p" Î Pairs.
Abbreviate by omitting R and s from the notation. Abbreviate
RVH = RVH(s). Assume p precedes p' and p' precedes p".
Let (a,b) denote p, let (c,d) denote p', and let (e,f)
denote p".
Since (a,b) precedes (c,d), (c,d) cannot be larger than (a,b),
meaning one of the following two conditions must hold:
#R(a,b) > #R(c,d)
#R(a,b) = #R(c,d)
and #R(d,c) ³ #R(b,a)
Since (c,d) precedes (e,f), (e,f) cannot be larger than (c,d),
meaning one of the following two conditions must hold:
#R(c,d) > #R(e,f)
#R(c,d) = #R(e,f)
and #R(f,e) ³ #R(d,c)
Thus there are four cases to consider:
Case 4.1: #R(a,b)
> #R(c,d) and #R(c,d) > #R(e,f).
Clearly
#R(a,b) > #R(e,f), implying p
is larger than p", implying p precedes p".
Case 4.2: #R(a,b)
> #R(c,d) and #R(c,d) = #R(e,f)
and #R(f,e) ³ #R(d,c). Clearly #R(a,b) > #R(e,f),
implying
p is larger than p", implying p precedes p".
Case 4.3: #R(a,b)
= #R(c,d) and #R(d,c) ³
#R(b,a)
and #R(c,d) > #R(e,f). Clearly #R(a,b) > #R(e,f),
implying
p is larger than p", implying p precedes p".
Case 4.4: #R(a,b)
= #R(c,d) and #R(d,c) ³
#R(b,a)
and #R(c,d) = #R(e,f) and #R(f,e) ³ #R(d,c).
Thus
#R(a,b) = #R(c,d) = #R(e,f). There are three subcases to consider:
Case 4.4.1: #R(d,c)
> #R(b,a). Here #R(a,b)
= #R(e,f)
and #R(f,e) > #R(b,a), meaning p
is larger than p",
implying p precedes p".
Case 4.4.2: #R(f,e)
> #R(d,c). Here #R(a,b) = #R(e,f)
and #R(f,e) > #R(b,a), meaning p
is larger than p",
implying p precedes p".
Case 4.4.3: #R(d,c)
= #R(b,a) and #R(f,e) =
#R(d,c).
Here
p and p' and p" are the same size, so precedence is
determined by RVH. There are two subcases to consider:
Case 4.4.3.1: p, p',
and p" all have the same second alternative.
(In other words, b = d = f.) Since p precedes p', RVH must rank
a over c. Similarly, since p' precedes p" RVH must
rank c over e.
Thus,
by theorem "Random Voter Hierarchy is a Strict Ordering"
RVH ranks a over e, from which it follows that p precedes p".
Case 4.4.3.2: p, p',
and p" do not all have the same second
alternative. (In other words, if b = d then b ¹
f, etc.) Since p
precedes p', RVH does not rank b
over d. Since p' precedes p",
RVH does not rank d over f. Thus, by theorem
"Random Voter
Hierarchy is a Strict Ordering",
RVH must rank f over b.
It follows that p
precedes p".
Since p precedes p" in both subcases, p precedes p" in case 4.4.3.
Since p precedes p" in all three subcases, p precedes p" in case 4.4.
Since p precedes p"
given (R,s) in all four cases,
(4) is established,
meaning precedence is transitive.
Since precedence is irreflexive, complete,
asymmetric and transitive,
precedence is a strict ordering of Pairs(A).
QED
Theorem: "Dominance
is an Ordering":
(1) For all r Î L(A)
and all s Î
L(R,A), r does not dominate
itself
given (R,s). (That
is, dominance is irreflexive.)
(2) For all r,r' Î L(A)
and all s Î
L(R,A), if r dominates r' given (R,s),
then r' does not dominate r given (R,s). (That
is, dominance is asymmetric.)
(3) For all r,r',r" Î L(A)
and all s Î
L(R,A), if r dominates r' given (R,s)
and r' dominates r" given (R,s), then r dominates r" given (R,s).
(That
is, dominance is transitive.)
(4) For all r,r',r" Î L(A)
and all s Î
L(R,A), if r dominates r' given (R,s)
and r" does not dominate r' given (R,s), then r dominates r" given (R,s).
(5) For all r,r',r" Î L(A)
and all s Î
L(R,A), if r' does not dominate r
given (R,s) and r' dominates r" given (R,s), then r dominates r" given (R,s).
(6) For all r,r',r" Î L(A)
and all s Î
L(R,A), if r
does not dominate r'
given (R,s) and r' does not dominate r" given (R,s), then r
does not
dominate r" given (R,s). (That
is, dominance is negatively transitive.)
Proof of (1): Irreflexivity follows by inspection of the definition of dominance.
Proof of (2): Pick any s Î
L(R,A). Abbreviate by omitting "given (R,s)"
from the notation. Make the following abbreviations:
For all r Î
L(A),
Agreed(r) = Agreed(r,R).
For all r,r' Î L(A),
Distinct(r,r') = DistinctAgreed(r,r',A,R).
For all r,r' Î L(A)
such that
Distinct(r,r') is not empty,
LDA(r,r') = LargestDistinctAgreed(r,r',A,R,s).
Assume r
dominates r'. By the definition of
dominance, this
implies LDA(r,r') Î
Agreed(r) and LDA(r,r') Ï
Agreed(r').
This implies r' does not dominate r. Thus dominance
is asymmetric.
Proof of (3): Pick any s Î
L(R,A). Make the
same abbreviations as in (2).
Assume r
dominates r' and r' dominates r". This implies
Distinct(r,r') is not
empty
and Distinct(r',r") is not empty. By theorem
"Precedence is a Strict
Ordering" and the definition of LargestDistinctAgreed(),
we can let (x,y)
denote
the unique ordered pair LDA(r,r')
and can let (z,w) denote the unique
ordered
pair LDA(r',r"). Clearly (x,y) Î
Agreed(r) and (z,w) Î
Agreed(r')
and (x,y) ¹ (z,w).
There are two cases to consider:
Case 3.1: (x,y)
precedes (z,w). Since LDA(r',r") = (z,w) this
implies
(x,y) Ï Distinct(r',r").
Thus, since r' ranks y over x, r" must also rank
y
over x. Since r ranks x over y and r" ranks y over x, (x,y)
Î Distinct(r,r").
To show that r dominates r", suppose the contrary.
Then there must exist
(a,b) Î Agreed(r")\Agreed(r) which precedes (x,y). This implies r" ranks a
over b and r ranks b
over a. Since r ranks b over a and LDA(r,r')
= (x,y),
r' must also rank b over a. Thus (a,b) Î
Agreed(r")\Agreed(r'). Since
(a,b) precedes (x,y) and (x,y) precedes (z,w),
by theorem "Precedence
is a Strict Ordering" (a,b) must
precede (z,w). But this means LDA(r',r")
is not (z,w),
a contradiction which refutes the contrary assumption and
establishes r dominates r"
in case 3.1.
Case 3.2: (z,w)
precedes (x,y). Since LDA(r,r') = (x,y), this
implies
(z,w) Ï Distinct(r,r'). Thus,
since r' ranks z over w, r must also rank z
over w. Since r ranks z over w and r" ranks w over z, (z,w)
Î Distinct(r,r").
To show that r dominates r", suppose the contrary.
Then there must
exist (a,b) Î Agreed(r")\Agreed(r)
which precedes (z,w). This implies
r" ranks a over b and r ranks b
over a. Since (a,b) precedes (z,w)
and (z,w)
precedes (x,y), by theorem
"Precedence is a Strict Ordering"
(a,b) must
precede (x,y). Since r ranks b over a and (a,b) precedes
(x,y),
r' must also rank b over a. Thus (a,b) Î
Agreed(r")\Agreed(r').
But since (a,b) precedes (z,w), this implies LDA(r',r")
is not (z,w),
a contradiction which refutes the contrary assumption and
establishes r dominates r" in case
3.2.
Since r dominates r" in both cases, dominance is transitive.
Proof of (4): Make the
same abbreviations as in (2). Assume r
dominates r'
and r" does not dominate r'. By theorem
"Precedence is a Strict Ordering"
and the definition of LargestDistinctAgreed(),
we can let (x,y) denote
the unique ordered pair LDA(r,r'). Clearly (x,y) Î
Agreed(r).
There are two
cases to consider:
Case 4.1: Distinct(r',r")
is empty. This implies r' ranks a
and b the same
as r" does for all (a,b) Î
Majorities(A,R). This means r' and r" can
only
disagree on alternatives
which tie pairwise.) This implies LDA(r,r")
= (x,y),
so r dominates r" in case 4.1.
Case 4.2: Distinct(r',r")
is not empty. By theorem
"Precedence is a Strict
Ordering" and the definition of LargestDistinctAgreed(), we can let (z,w)
denote the unique ordered pair LDA(r',r"). Since r" does not dominate r',
this implies (z,w)
Ï Agreed(r").
Therefore (z,w)
Î Agreed(r'), which
implies r'
dominates r". By 3 (transitivity), r dominates r" in case
4.2.
Since r dominates r" in both cases, (4) is established.
Proof of (5): Make the
same abbreviations as in (2) above. Assume r'
does not
dominate r and r' dominates r". By theorem
"Precedence is a Strict Ordering"
and the definition of LargestDistinctAgreed(),
we can let (z,w) denote
the
unique ordered pair LDA(r',r"). Clearly (z,w) Î
Agreed(r').
There are two
cases to consider:
Case 5.1: Distinct(r,r')
is empty. This implies r ranks a relative to b
the same as r'
does for all (a,b) Î
Majorities(A,R). (In other words,
r and r' can
only
disagree on alternatives which
tie pairwise.) This
implies LDA(r,r")
= (z,w)
and thus r dominates r" in case 5.1.
Case 5.2: Distinct(r,r')
is not empty. By theorem
"Precedence is
a Strict
Ordering" and the definition of LargestDistinctAgreed(),
we can let (x,y)
denote the unique ordered pair LDA(r,r'). Since r'
does not dominate r, (x,y)
Ï Agreed(r'). Therefore (x,y)
Î Agreed(r),
implying r
dominates r'.
Since r dominates r' and r'
dominates r",
by 3 (transitivity) r dominates r" in case 5.2.
Since r dominates r" in both cases, (5) is established.
Proof of (6): Make the
same abbreviations as in (2) above. Assume r
does
not dominate r'
and r' does not dominate r". There are three
cases to consider:
Case 6.1: r' dominates r.
By 5 (swapping the labels of r and r"),
r" dominates r. By 2 (asymmetry), r does not dominate r".
Case 6.2: r" dominates r'.
By 4 (swapping the labels of r and r"),
r" dominates r. By 2 (asymmetry), r does not dominate r".
Case 6.3: r' does not dominate r
and r" does not dominate r'. Since r
does not dominate r' and r' does not dominate r, Distinct(r,r')
must be
empty. Since r' does not dominate r" and r"
does not dominate r',
Distinct(r',r") must be empty. Since Distinct(r,r') is
empty, r ranks a
relative to b the same as r'
does for all (a,b) Î
Majorities(A,R).
Since Distinct(r',r") is empty, r' ranks a relative to
b the same as r"
does
for all (a,b) Î
Majorities(A,R). Combining
the last two statements,
r ranks a relative to b the same as r"
does for all (a,b) Î
Majorities(A,R).
Thus Distinct(r,r") is empty, which implies r does not dominate r".
Since r does not dominate r"
in all three cases, dominance is negatively
transitive.
Since dominance is irreflexive, asymmetric, transitive and negatively
transitive, it is an ordering of L(A)
(the set of all strict rankings of
the
alternatives).
QED
Theorem: "Weak
Dominance
is a Strict Ordering":
(1) For all r Î L(A)
and all s Î
L(R,A), r does not
weakly dominate
itself given (R,s). (In
other words, weak dominance is irreflexive.)
(2) For all distinct r,r' Î L(A)
and all s Î
L(R,A), if r
does not weakly
dominate r' given (R,s), then r'
weakly dominates r given (R,s).
(In
other words, weak dominance is complete.)
(3) For all r,r' Î L(A)
and all s Î
L(R,A), if r
weakly dominates r'
given (R,s), then r' does not
weakly dominate r given (R,s).
(In
other words, weak dominance is asymmetric.)
(4) For all r,r',r" Î L(A)
and all s Î
L(R,A), if r
weakly dominates r'
given (R,s)
and r' weakly dominates r" given (R,s),
then r weakly dominates r" given (R,s).
(In
other words, weak dominance is transitive.)
(5) For all r,r',r" Î L(A)
and all s Î
L(R,A), if r
does not weakly
dominate r' given (R,s) and r' does not
weakly dominate r" given (R,s),
then r does not weakly dominate r" given (R,s).
(In
other words, dominance is negatively transitive.)
Proof of (1): Pick any s Î
L(R,A) and any r Î L(A).
By theorem
"Dominance
is an Ordering (1)", dominance is irreflexive, so r does
not dominate itself
given (R,s). Thus
condition 1 of the
definition of weak dominance does not
hold. Since r = r, condition 2 of the
definition of weak dominance does not hold.
Since neither condition holds, r does not weakly dominate itself given (R,s).
Since r and s were picked arbitrarily, this
means weak dominance is irreflexive.
Proof of (2): Pick any s Î
L(R,A). Abbreviate by omitting "given (R,s)"
from the notation. Make the following abbreviations:
RVH = RVH(A,R,s).
For all distinct r,r' Î L(A),
TDA(r,r') = TopmostDifferentAlternative(r,r').
Pick any distinct r,r' Î L(A).
Assume r
does not weakly dominate r'.
By the
definition of weak dominance, r
does not dominate r' and
[either r' dominates r or RVH does not rank TDA(r,r') over
TDA(r',r)].
Thus there are two cases to consider:
Case 2.1: r'
dominates r. It follows by condition 1 of the
definition of
weak dominance that r' weakly dominates r in case
2.1.
Case 2.2: r' does not
dominate r. This implies RVH does not rank TDA(r,r')
over TDA(r',r). By theorem
"Random Voter Hierarchy is a Strict Ordering",
RVH must rank TDA(r',r) over TDA(r,r'). Since r
does not dominate r' and
r ¹ r' and RVH ranks TDA(r',r)
over TDA(r,r'), it follows by condition 2
of the
definition of weak dominance that r' weakly dominates r in
case 2.2.
Since in both cases r' weakly dominates r, this means weak dominance is complete.
Proof of (3): Pick any s Î
L(R,A). Make the
same abbreviations as in (2).
Pick any r,r' Î L(A).
Assume r
weakly
dominates r'. There are two cases:
Case 3.1: r
dominates r'. By theorem
"Dominance is an Ordering",
dominance is asymmetric, so r' does not dominate r.
By inspection of
the
definition of weak dominance, r' does not weakly dominate r in
case 3.1.
Case 3.2: r does not
dominate r'. Since r
weakly
dominates r' but does not
dominate r', it follows by condition 2 of the
definition of weak dominance
that r' does not dominate r and RVH ranks TDA(r,r') over
TDA(r',r).
This implies r' does not weakly dominate r in case 3.2.
Since in both cases r' does not weakly dominate r, weak dominance is asymmetric.
Proof of (4): Pick any s Î
L(R,A). Make the
same abbreviations as in (2).
Pick any r,r',r" Î L(A).
Assume r
weakly
dominates r' and r' weakly
dominates r". There are three cases to consider:
Case 4.1: r
dominates r'. Since r' weakly dominates r", by
3 (asymmetry)
r" does not weakly dominate r', so by condition 1 of the definition of weak
dominance r" does not dominate r'. Since r
dominates r' and r" does not
dominate r', by theorem "Dominance is an
Ordering (4)" r
dominates r".
By condition 1 of the definition of weak dominance, r weakly
dominates r".
Case 4.2: r' dominates r".
Since r weakly dominates r', by 3 (asymmetry)
r' does not weakly dominate r, so by condition 1 of the definition of weak
dominance r' does not dominate r. Since r'
dominates r" and r' does not
dominate r, by theorem "Dominance is an
Ordering (5)", r
dominates r".
By condition 1 of the definition of weak dominance, r weakly
dominates r".
Case 4.3: r does not
dominate r' and r' does not dominate r". By 1,
weak
dominance is irreflexive, so r ¹ r'
and r' ¹ r". By 3, weak
dominance is
asymmetric, so r ¹ r".
Thus r, r' and r" are three distinct rankings of
the
alternatives. Thus we can let x denote TDA(r,r') and let x'
denote TDA(r',r)
and let y' denote TDA(r',r") and let y" denote
TDA(r",r') and let z denote
TDA(r,r") and let z" denote TDA(r",r).
Clearly x ¹ x' and y' ¹
y"
and z ¹ z" and the following two
statements hold:
(4.3.1) Over(r,x)
= Over(r',x').
(4.3.2) Over(r',y')
= Over(r",y").
By 3 (asymmetry), r' does not weakly dominate r. Thus
by condition 1
of the definition of weak dominance r' does not dominate r.
Similarly,
r" does not weakly dominate r' nor dominate r'.
Since r
weakly
dominates r' but does not dominate r', by condition 2 of the
definition of
weak dominance RVH ranks x over x'. Similarly, RVH ranks y'
over y".
There are three subcases to consider:
Case 4.3.3: x' = y'.
Since RVH ranks x over x' and x' over y",
by theorem
"Random Voter Hierarchy is a Strict Ordering"
RVH ranks x over y". Thus x ¹
y". By 4.3.1 and 4.3.2,
Over(r,x) = Over(r",y").
Furthermore, it follows by the definitions
of TopmostDifferentPlace() and TopmostDifferentAlternative()
that z = x and z" = y".
Case 4.3.4: r' ranks x'
over y'. By 4.3.2, r" ranks x' over y"
and,
furthermore, it follows by the definitions of TopmostDifferentPlace()
and TopmostDifferentAlternative() that z = x
and z" = x'.
Case 4.3.5: x' ¹
y' and r' does not rank x' over y'. Since r'
is
a strict ranking, r' ranks y' over x'. By 4.3.1, r
ranks y' over x and,
furthermore, it follows by the definitions of TopmostDifferentPlace()
and TopmostDifferentAlternative() that z = y'
and z" = y".
Since in all three subcases r" does not dominate r and r ¹
r" and
RVH ranks z over z", by condition 2 of the definition of weak dominance
r weakly dominates r" in case 4.3.
Since r weakly dominates r" in all three cases, weak dominance is transitive.
Proof of (5): Pick any s Î
L(R,A). Make the
same abbreviations as in (2).
Pick any r,r',r" Î L(A).
Assume r
does not weakly dominate r' and
r' does not weakly dominate r". There are four
cases to consider:
Case 5.1: r = r'.
By inspection of the assumptions,
r does not weakly dominate r".
Case 5.2: r' = r".
By inspection of the assumptions,
r does not weakly dominate r".
Case 5.3: r = r".
By 1 (irreflexivity),
r does not weakly dominate r".
Case 5.4: r, r'
and r" are three distinct rankings. By 2 (completeness),
r' weakly dominates r and r" weakly dominates r'.
By 4 (transitivity),
r" weakly dominates r. By 3 (asymmetry), r
does not weakly dominate r".
Since in all four cases r does not weakly
dominate r", weak dominance is
negatively transitive. (Note that in general, negative transitivity
is always
implied by the combination of irreflexivity, completeness, asymmetry
and transitivity, by reasoning as in this proof.)
Since weak dominance is irreflexive, complete, asymmetric, transitive
and negatively transitive, it is a strict ordering of L(A).
QED
Properties of Internal Consistency and Internal Inconsistency
Theorem: "Consistency
Means Acyclicity":
(1) For all P Í
Pairs, P is internally consistent if and only if
there do not exist (a1,a2),(a2,a3),...,(ak-1,ak)
Î P such that ak = a1.
(2) For all P Í
Pairs, P is internally consistent if and only if
(a,a) is consistent with P for all a Î A.
Proof of (1): First we prove the
"only if": Assume P Í
Pairs and P is internally
consistent. We show there do not exist (a1,a2),(a2,a3),...,(ak-1,ak)
Î P such
that ak = a1. Suppose to the contrary that (a1,a2),(a2,a3),...,(ak-1,a1)
Î P.
Since (a2,a3),...,(ak-1,a1)
Î P, (a1,a2)
is inconsistent with P. Since (a1,a2)
Î P
and (a1,a2)
is inconsistent with P, P is internally inconsistent. This contradicts
the assumption that P is internally consistent,
refuting the contrary assumption
and establishing the "only if" clause.
Next we prove the "if": Assume P Í
Pairs and that there do not exist
(a1,a2),(a2,a3),...,(ak-1,ak)
Î P such that ak = a1.
We want to show P is
internally consistent. Suppose to the contrary P is internally inconsistent.
This means there exist (b1,b2),(b2,b3),...,(bj-1,bj)
Î P such that (bj,b1)
Î P.
Let ai
= bi for all i Î
{1,2,...,j}. Let k = j+1 and let ak
= b1. Since ak = b1 =
a1
and (a1,a2),(a2,a3),...,(ak-2,ak-1),(ak-1,ak)
Î P, this contradicts the assumption
that there do not exist (a1,a2),(a2,a3),...,(ak-1,ak)
Î P such that ak = a1.
Thus the contrary assumption is refuted, establishing P is
internally consistent.
Since both the "if" and
"only if" clauses have been established, (1) is established.
Proof of (2): First we prove the
"only if" clause: Assume P is internally consistent.
We must show (a,a) is
consistent with P for all a Î A.
Suppose to the contrary
that (x,x) is inconsistent with P for some x Î A.
This means there exist
(a1,a2),(a2,a3),...,(ak-1,ak)
Î P such that a1 = ak
= x. Let j = k-1.
Since (a1,a2),(a2,a3),...,(aj-1,aj)
Î P, (aj,a1)
is inconsistent with P.
Since (aj,a1)
= (ak-1,ak)
and (ak-1,ak)
Î P, P is internally inconsistent.
This contradicts the given assumption that P is internally consistent,
refuting
the contrary assumption and establishing (a,a) is
consistent with P for all a Î A.
Next we prove the "if"
clause: Assume (a,a) is
consistent with P for all a Î A.
We must show P is internally consistent. Suppose to the contrary P is
internally
inconsistent. There must exist (a1,a2),(a2,a3),...,(ak-1,ak)
Î P such that
(ak,a1)
Î P. Clearly (a1,a2),(a2,a3),...,(ak-1,ak),(ak,a1)
Î P. Let j = k+1
and let aj denote a1.
Since (a1,a2),(a2,a3),...,(aj-2,aj-1),(aj-1,aj)
Î P
and aj = a1,
(a1,a1)
is inconsistent with P. Since a1 Î A,
this contradicts
the given assumption that (a,a) is
consistent with P for all a Î A.
This refutes
the contrary assumption and establishes P is internally consistent.
Since both
the "if" and
"only if" clauses have been established, (2) is established.
QED
Theorem:
"Reversed Inconsistent Pair is Consistent":
(1) For all internally consistent P Í Pairs and all
a,b Î A such
that (a,b) is inconsistent with P, (b,a) is consistent with P.
Proof: Pick any P Í Pairs
and any a,b Î A. Assume P is
internally
consistent and (a,b) is inconsistent with P. Suppose
to the contrary that
(b,a) is inconsistent with P. Since (a,b)
is inconsistent with P, by the
definition of inconsistent there must exist (x1,x2),(x2,x3),...,(xk-1,xk)
Î P
such that x1 = b and xk = a.
Similarly, since (b,a) is inconsistent with P
there must exist (y1,y2),(y2,y3),...,(yj-1,yj)
Î P
such that y1 = a and yj =
b.
Clearly (x2,x3,),...,(xk-1,a),(a,y2),(y2,y3,),...,(yj-1,x1)
Î P. This implies
(x1,x2) is
inconsistent with P.
Since (x1,x2)
Î P and (x1,x2) is inconsistent
with P,
P is not internally consistent. But this is a
contradiction, so the
contrary assumption cannot hold, establishing the theorem.
QED
Theorem: "Minimal
Inconsistent Set":
(1) For all a,b Î
A and all P Í
Pairs such that (a,b) is inconsistent
with P,
there exists at least one P0 Í
P such that P0 is a minimal set with
which (a,b)
is inconsistent.
(2) For all distinct a,b Î
A and all P Í
Pairs such that P is a minimal set
with which (a,b)
is inconsistent, a is not the first alternative in any ordered
pair in P and b is not the second alternative in any ordered pair in P.
(3) For all a,b,c Î A
and
all P Í Pairs such
that P is a minimal set
with which
(a,b) is inconsistent, if c is not the second alternative
in any ordered pair
in P È {(a,b)} then c is not an alternative in any ordered pair in P È
{(a,b)}.
Proof of (1): Suppose (a,b) is
inconsistent with P. Let Pab denote the set of
all subsets of P with which (a,b) is inconsistent. Since P
Î Pab, Pab is
not empty.
Thus there must exist at least one P0
Î Pab
such that #P0 £ #P'
for all P' Î Pab.
This implies no strict subset
of P0
is in Pab. Therefore P0 is a minimal set with
which (a,b) is
inconsistent. Thus (1) has been established.
Proof of (2): Assume a
¹ b and P is a minimal set with which (a,b) is inconsistent.
This means there exist (a1,a2),(a2,a3,),...,(ak-1,ak)
Î P such that a1 = b
and ak = a.
Since
P is minimal,
P must be {(a1,a2),(a2,a3,),...,(ak-1,ak)}.
First we show
a is
not the first alternative in any pair in P. Suppose the contrary. This means aj
= a
for some j Î
{1,...,k-1}. Since a ¹ b, it follows that a1
¹ a, so 1 < j < k.
By
the
definition of consistent, (a,b) is inconsistent with {(a1,a2),(a2,a3,),...,(aj-1,aj)},
which is
a strict
subset of P. But this contradicts the assumption that P is minimal.
Thus the contrary assumption cannot hold, establishing a is not first in any
pair in P.
Next we prove b is not the
second alternative in any pair in P.
Suppose
the contrary. This means aj = b for some j Î
{2,...,k}. Since a ¹ b,
it follows that ak
¹ b, thus 1 < j < k. Clearly
(a,b) is
inconsistent with
{(aj,aj+1),(aj+1,aj+2,),...,(ak-1,ak)}, which is a strict
subset of P.
But this contradicts the assumption that P is minimal, so
the contrary
assumption cannot hold,
establishing b is not second in any
pair in P.
Thus (2) has been established.
Proof of (3): Suppose P is a minimal set with
which (a,b) is inconsistent
and c is not second
in any pair in P È {(a,b)}.
This implies there exist
(a1,a2),(a2,a3,),...,(ak-1,ak)
Î P such that a1 = b and ak = a. Since
P is
minimal, P must be {(a1,a2),(a2,a3,),...,(ak-1,ak)}. Let P'
denote P È {(a,b)}.
(Possibly P'
= P.) By
inspection of P', every alternative which is first in
at least one pair in P' is also second in at
least
one pair in P'. Thus,
since c is not second in any pair in P', c cannot be first in any pair in P'.
Since c is neither first nor second in any pair in P', c is not
in any
pair in P'.
Thus (3) has been
established. QED
Theorem: "More
Inconsistent":
Definition: For all a Î A and all P Í
Pairs,
let I(a,P) denote {x Î
A\{a} such that (a,x)
is inconsistent with P}.
For all a,b Î A and all P Í
Pairs, if (a,b) is inconsistent with P then #I(a,P) > #I(b,P).
Proof: Assume a,b Î A
and P Í
Pairs and (a,b) is inconsistent with P.
Abbreviate Ia = I(a,P)
and Ib = I(b,P). For all x Î
Ib there must exist
(a1,a2),(a2,a3),...,(ak-1,ak)
Î P such that a1 = x and ak = b (for some k
which may vary with x). Since (a,b) is inconsistent with P, there must
exist
(b1,b2),(b2,b3),...,(bj-1,bj)
Î P such that b1 = b and bj = a.
Thus for all
x Î
Ib
there must exist (x,a2),(a2,a3),...,(ak-1,b),(b,b2),(b2,b3),...,(bj-1,a)
Î P.
Therefore (a,x) is inconsistent with P for all x Î
Ib.
This means x Î
Ia
for all x Î
Ib. Thus Ib Í Ia. Since (a,b) is inconsistent with P,
b Î Ia.
By the
definition of I(), b Ï
Ib. Since b Î Ia and
b Ï
Ib, Ib ¹
Ia.
Since Ib Í Ia
and Ib ¹
Ia, Ib must be a strict subset of Ia.
Since A is
finite, this implies #Ia
> #Ib. QED
Theorem: "Consistency Maintained":
(1) For all internally
consistent P Í Pairs(A)
and all a,b Î A such
that (a,b) is consistent with P, P È
(a,b) is internally consistent.
(2) For all s Î
L(R,A), Affirmed(A,R,s) is
internally consistent.
Proof of (1): Assume P
Í Pairs(A) and P is
internally consistent and
(a,b) is consistent with P. Let
P' denote
P È (a,b).
Suppose to the contrary
that P' is internally inconsistent. This
implies (a,b) Ï
P. Since P' is internally
inconsistent
there must exist (a1,a2),(a2,a3,),...,(ak-1,ak)
Î P' such that
(ak,a1) Î
P'.
There are three cases to
consider:
Case 1.1: There exists no j Î
{1,2,...,k-1} such that (aj,aj+1)
= (a,b).
Thus, (a1,a2),(a2,a3,),...,(ak-1,ak)
Î P. There are two subcases
to
consider:
Case 1.1.1: (ak,a1) = (a,b).
This implies (a,b) is inconsistent
with P. But this is a contradiction, so case 1.1.1 is impossible.
Case 1.1.2: (ak,a1) ¹
(a,b). Since (ak,a1)
Î
P', (ak,a1)
Î
P.
This implies P is internally inconsistent. But this is a
contradiction,
so case 1.1.2 is
impossible.
Since both subcases are impossible, case 1.1 is impossible.
Case 1.2: There exists at least one
j Î
{1,2,...,k-1} such that
(aj,aj+1)
= (a,b). Thus we can let i denote the smallest integer in
{1,2,...,k-1}
such that (ai,ai+1) = (a,b), and
we can let j denote the
largest integer in {1,2,...,k-1}
such that (aj,aj+1) = (a,b). (Possibly i = j.)
Clearly 1 £ i
£ j < k. There are two
subcases to consider:
Case 1.2.1: j = k-1.
Clearly (ak,a1),(a1,a2),(a2,a3),...,(ai-1,ai) Î
P.
Since ak = b and ai
= a, this means (a,b) is inconsistent with P.
But this is a contradiction, so case 1.2.1 is
impossible.
Case 1.2.2: j ¹
k-1. This implies j < k-1. By inspection, we
see that
(aj+1,aj+2),(aj+2,aj+3,),...,(ak-1,ak),(ak,a1),(a1,a2),(a2,a3),...,(ai-1,ai) Î
P.
Since aj+1 = b
and ai = a, this means (a,b) is inconsistent with P.
But this is a contradiction, so case 1.2.2 is
impossible.
Since both subcases are impossible, case 1.2 is impossible.
Since both cases are impossible, the contrary
assumption cannot hold,
establishing (1).
Proof of (2): Suppose to the contrary
there exists s Î
L(R,A) such that
Affirmed(A,R,s) is
internally inconsistent. Make the following abbreviations:
For all (a,b) Î
Pairs(A), Precede(a,b) = Precede(a,b,A,R,s).
Aff = Affirmed(A,R,s).
For all (a,b) Î
Aff, let Affab+ denote Aff Ç
Precede(a,b). Since the empty
set f is
internally
consistent and Aff is assumed internally inconsistent,
by induction and theorem
"Precedence is a Strict Ordering" there must
exist (x,y) Î
Aff such that both of
the following conditions hold:
(2.1) Affxy+
is internally consistent.
(2.2) Affxy+ È {(x,y)}
is internally inconsistent.
Since (x,y) Î
Aff, by the definition of Affirmed() (x,y)
must be consistent
with Affxy+. Since Affxy+
is internally consistent and (x,y) is consistent
with Affxy+, by theorem
"Consistency Maintained (1)"
Affxy+ È (x,y) must
be internally consistent. But this contradicts 2.2, so the contrary assumption
cannot hold. Thus
Affirmed(A,R,s) is
internally consistent for all s Î
L(R,A).
QED
Theorem: "At
Least One Top":
(1) For all non-empty B Í A
and all internally consistent P
Í
Pairs(B),
at least one alternative in B
is not second in any ordered pair in P.
(2) For
all s Î
L(R,A), Top(s)
is not empty.
(3) For all internally consistent P Í
Pairs(A), if Tied(P)
is not empty
then TopTied(P)
is not empty.
Proof of (1): Assume B
is a non-empty subset of A and P is an internally
consistent subset of Pairs(B). For all b
Î B, let Ib denote {b' Î
B
such
that (b,b') is inconsistent with P}. Since A is finite, Ib must be finite for all b Î B,
so there must exist at least one x Î B such that #Ix
£ #Ib for all b Î B. We
aim to show
x is not second in any ordered pair in P. Suppose to
the contrary
there exists y Î B
such that (y,x) Î P. This implies (x,y) is
inconsistent with P.
Since P is
internally consistent, by theorem "More
Inconsistent" #Ix > #Iy.
But this contradicts the definition of x, so the
contrary assumption cannot hold.
Thus x Î B and x is not second in any pair in P.
Proof of (2): Pick any s
Î
L(R,A). By theorem
"Consistency
Maintained
(3)", Affirmed(s)
is internally consistent. By the definition of Affirmed(),
Affirmed(s)
Í Pairs(A).
Thus, by theorem
"At Least One Top (1)"
at least one alternative in A is not
second in
any pair in Affirmed(s).
By the definition of Top(), this implies Top(s)
is not empty.
Proof of (3): Pick any P Í
Pairs(A). Assume P is
internally consistent
and Tied(P) is not empty. By (1), there
exists at least one a Î Tied(P)
such that, for all b Î Tied(P),
(b,a) Ï P. It follows by the definition
of TopTied() that a Î
TopTied(P), and hence that TopTied(P)
is
not empty. QED
Theorem:
" Random Voter Hierarchy satisfies
strong Pareto":
For all s
Î
L(R,A) and all a,b Î
A, if no voters rank b over a and
at least
one voter
ranks a
over b, then RVH(A,R,s) ranks a over b.
Proof: Assume a,b Î
A, no voters rank b over a and at least one
voter ranks a over b. Thus R(b,a) is
empty and R(a,b) is not
empty. Pick any s
Î
L(R,A). Abbreviate RVH = RVH(A,R,s).
We must show RVH
ranks a over b. Since R(ab)
is not empty,
by the definition of RVH() RVH
ranks a relative to b the same
as Rsab
does. Since R(b,a) is
empty, Rsab Î
R(a,b).
Thus RVH ranks a over b. QED
Theorem:
"Majorities are independent of irrelevant alternatives":
For all non-empty B Í A, Majorities(A,R)
Ç
Pairs(B) = Majorities(B,R|B),
where R|B denotes the restriction of R to B. (That is, R|B
is the same as R
except the alternatives not in B are deleted.)
Proof: This follows by inspection of the definition of Majorities(). QED
Theorem:
"Random Voter Hierarchy is independent of irrelevant alternatives."
Some definitions:
For all non-empty B Í
A and all r Î
L(A), let r|B denote the restriction
of r to B. (That
is, r|B is the strict ordering of B which is the same as r
except all alternatives not in B are deleted.)
For all non-empty B Í
A, let R|B denote the restriction of R to B. (That is,
R|B
is the same as the votes in 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
= (sR|B,sA|B) Î
L(R|B,B) where sR|B is the same as
sR
except all alternatives not in B
are deleted, and sA|B
is the strict ordering of B
which is the same as sA
except all alternatives
not in B are deleted.)
For all non-empty B Í A and all s Î L(R,A), RVH(A,R,s)|B = RVH(B,R|B,s|B).
Proof:
Arbitrarily pick non-empty B Í A
and s Î
L(R,A) and distinct a,b Î B.
Thus s|B
= (sR|B,sA|B) Î
L(R|B,B). Abbreviate RVH = RVH(A,R,s)
and
RVH' = RVH(B,R|B,s|B).
There are two cases to consider:
Case 1.1: R(ab)
is not empty. (That is, at least one voter is not indifferent
between a,b.) By the definition of RVH(), RVH ranks a relative to b
the same as Rsab
does. (That is, the same as the ballot in R(ab) ranked
highest by sR.) Clearly R|B(a,b)
= R(a,b)|B and R|B(b,a) =
R(b,a)|B.
Thus R|B(ab) is not empty, implying RVH' ranks a relative to b the same
as R|BsR|Bab
does. Clearly R|BsR|Bab
= Rsab|B,
which means RVH'
ranks a relative to b the same as RVH does.
Case 1.2: R(ab)
is empty. By the definition of RVH(), RVH ranks a
relative to b the same as sA does. Clearly
R|B(ab) is empty, implying
RVH' ranks a relative to b the same as sA|B
does, which is the same
as sA does, which is the same as
RVH does.
Since in both cases RVH'
ranks a relative to b the same as RVH does,
and since B, s, a and b were
picked arbitrarily, the theorem has been
established. QED
Theorem:
"Precedence is independent of irrelevant alternatives":
For all non-empty B Í
A, 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 s Î
L(R,A) and all non-empty B Í
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.) For
all s Î
L(R,A), all non-empty B Í
A and all a,b Î
B,
Precede(a,b,A,R,s)
Ç
Pairs(B) = Precede(a,b,B,R|B,s|B).
Proof: Clearly the following statement must hold:
(1) For all a,b Î B, R(a,b) = R|B(a,b).
By theorem
"Random Voter Hierarchy is independent of
irrelevant alternatives", the following condition must hold:
(2) For all a,b Î
B, RVH(A,R,s)
ranks a over b if and only if
RVH(B,R|B,s|B)
ranks a over b.
The theorem will follow immediately if we establish the following two propositions:
(3) For all a,b,c,d Î
B
and all s
Î
L(R,A), if (c,d) Î Precede(a,b,A,R,s)
then (c,d) Î Precede(a,b,B,R|B,s|B).
(4) For all a,b,c,d Î
B and all s
Î
L(R,A), if (c,d) Î Precede(a,b,B,R|B,s|B)
then (c,d) Î Precede(a,b,A,R,s).
First we establish 3: Assume a,b,c,d Î
B and s
Î
L(R,A) and
(c,d) Î
Precede(a,b,A,R,s).
We must show (c,d) Î Precede(a,b,B,R|B,s|B).
By the definition of precedence, one of the following four conditions must hold:
(3.1) #R(c,d)
> #R(a,b).
(3.2) #R(c,d)
= #R(a,b) and #R(d,c) < #R(b,a).
(3.3) #R(c,d)
= #R(a,b) and #R(d,c) = #R(b,a)
and RVH(A,R,s)
ranks b over d.
(3.4) #R(c,d)
= #R(a,b) and #R(d,c) = #R(b,a)
and b = d
and RVH(A,R,s)
ranks c over a.
Therefore, by 1 and 2 one of the following four conditions must hold:
(3.5) #R|B(c,d)
> #R|B(a,b).
(3.6) #R|B(c,d)
= #R|B(a,b) and #R|B(d,c) < #R|B(b,a).
(3.7) #R|B(c,d)
= #R|B(a,b) and #R|B(d,c) = #R|B(b,a)
and RVH(B,R|B,s|B)
ranks b over d.
(3.8) #R|B(c,d)
= #R|B(a,b) and #R|B(d,c) = #R|B(b,a)
and b = d and RVH(B,R|B,s|B)
ranks c over a.
Thus, by the
definition of precedence (c,d) Î
Precede(a,b,B,R|B,s|B),
establishing 3. Next we establish 4: Assume a,b,c,d Î
B and s
Î
L(R,A)
and (c,d) Î
Precede(a,b,B,R|B,s|B).
We need to show that
(c,d) Î
Precede(c,d,A,R,s). Since (c,d) Î Precede(a,b,B,R|B,s|B),
by the definition of precedence one of the following four conditions must hold:
(4.1) #R|B(c,d)
> #R|B(a,b).
(4.2) #R|B(c,d)
= #R|B(a,b) and #R|B(d,c) < #R|B(b,a).
(4.3) #R|B(c,d)
= #R|B(a,b) and #R|B(d,c) = #R|B(b,a)
and RVH(B,R|B,s|B)
ranks b over d.
(4.4) #R|B(c,d)
= #R|B(a,b) and #R|B(d,c) = #R|B(b,a)
and b = d and RVH(B,R|B,s|B)
ranks c over a.
Therefore, by 1 and 2 one of the following four conditions must hold:
(4.5) #R(c,d)
> #R(a,b).
(4.6) #R(c,d)
= #R(a,b) and #R(d,c) < #R(b,a).
(4.7) #R(c,d)
= #R(a,b) and #R(d,c) = #R(b,a)
and RVH(A,R,s)
ranks b over d.
(4.8) #R(c,d)
= #R(a,b) and #R(d,c) = #R(b,a)
and b = d and RVH(A,R,s)
ranks c over a.
Thus, by the
definition of precedence (c,d) Î
Precede(a,b,A,R,s),
establishing 4.
Having established both 3 and 4, the
theorem is
established. QED
Theorem: "MAM
is resolute":
For all s
Î
L(R,A), MAM(A,R,s)
is a single alternative in A.
Proof: Pick any s Î
L(R,A).
By theorem "At Least One
Top (2)",
Top(A,R,s)
is not empty. Thus, by theorem
"Random Voter Hierarchy
is a Strict Ordering" there must exist a unique alternative x Î
Top(A,R,s)
such that, for all y Î
Top(A,R,s)\{x},
RVH(A,R,s)
ranks x over y.
By inspection of the
definition of MAM(), MAM(A,R,s)
= x,
a single alternative. QED
Theorem: "Properties
of Rsocial": (See the
section "The
MAM social
ordering" in the document "MAM Formal
Definition" for definitions.)
(1) For all s
Î
L(R,A), Rsocial(A,R,s)
is a strict ordering of A. (That is, Rsocial()
is irreflexive, complete, asymmetric,
transitive and negatively transitive.)
(2) For all s
Î
L(R,A), Rsocial(A,R,s)
ranks MAM(A,R,s)
over all other alternatives.
(3) For all s
Î
L(R,A) and all (a,b) Î Affirmed(A,R,s),
Rsocial(A,R,s)
ranks a over b.
(4) For all s
Î
L(R,A) and all (a,b) Î Majorities(A,R)\Affirmed(A,R,s),
Rsocial(A,R,s)
ranks b over a.
(Note that 3 and 4 imply Affirmed(A,R,s)
= Agreed(Rsocial(A,R,s)).)
(5) For all s
Î
L(R,A), Rsocial(A,R,s)
Î UndominatedRankings(A,R,s).
(6) For all s
Î
L(R,A) and all a,b Î
A, if (a,b) is inconsistent
with Affirmed(A,R,s) then Rsocial(A,R,s)
ranks b over a.
(7) 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: