[EM] (5) MAM better than VoteFair: Steve's 5th dialogue with Kristofer

[steve bosworth]

From: stevebosworth at hotmail.com
To: electionmethods at votefair.org
Subject: RE: (5) MAM better than VoteFair:  Steve's 5th dialogue with Kristofer
Date: Tue, 20 Oct 2015 20:35:00 +0000







Re: (5) MAM better than VoteFair:
Steve's 4th dialogue with Kristofer


Date: Sat, 17 Oct 2015 17:17:12 -0700

 From: ElectionMethods at VoteFair.org

 To:
election-methods at lists.electorama.com

 CC: stevebosworth at hotmail.com

 Subject: Re: (4) MAM better than
VoteFair: Steve's 4th dialogue with Richard Fobes






Hi Kristofer, and all others,


Kristofer, thank you for the detailed
explanation (copied below) that you gave me in response to my questions in my
EM dialogue with Richard Fobes.  I asked
about how Kemeny-Young (KY or VoteFair) scored the pairs to find the winning
sequence.  You concluded that KY is vulnerable
to cloning attacks while Maximize Affirmed Majorities (MAM) is not.  At the time, I felt that I did not fully
understand all of your explanations but I hope I do now.  I think I have done this with the help an edited
version of the relevant parts of Steve Eppley’s email to me (see below).  As a result, I have tentatively concluded
that MAM would provide the best way by which the US President could be elected,
i.e. better than by VoteFair.


Do you agree?


Also, I would very much appreciate it
if you (or anyone else) would tell me whether or not the following account
shows that I have fully understood MAM and its superiority over KY for the
election of a President.  To Steve Eppley’s
words, I have sometimes [added my own words in square brackets (SB)] in an
attempt to confirm my understandings.  I
found his less abstract mathematical ways of explaining MAM very helpful.  For example, he explains in his 2nd
Example how, when using VoteFair, the adding of clone D to C changes the winner
from A to B.  MAM retains A as the winner.


From
Steve Eppley to Steve Bosworth:






[….]




MAM isn't the same as Kemeny-Young unless there are fewer than 4 candidates.
(Many pairwise voting methods behave the same with fewer than 4 candidates;
another method that behaves the same with fewer than 4 is Schulze's method.)



A criterion that MAM satisfies but KY doesn't is Independence of Clone
Alternatives. (If you're unfamiliar with Independence of Clone Alternatives,
the pair of examples below will help to explain it.)  A criterion that KY
satisfies but MAM doesn't is Weak Reinforcement: If two collections of votes
tallied separately produce the same order of finish, then that same order of
finish must be produced when the votes are tallied together.  [SB: 
Not important for electing a president.]  



Independence of Clone Alternatives is important because it's easy for a small
minority to nominate clones, whereas Weak Reinforcement is unimportant because
a simple rule can prevent a minority from dividing the voters into separate
groups (districts).  Weak Reinforcement is an example of criteria I call
"aesthetic consistency" criteria; society won't be harmed by voting
methods that fail those criteria.  Too much of the academic literature of
social choice theory is about unimportant aesthetic consistency criteria.



To illustrate how Kemeny-Young and MAM work, here's a pair of examples that
together also serve to illustrate the Independence of Clone Alternatives
criterion:



Example 1.  Suppose there are 100 voters and 3 candidates A, B and
C.  Suppose the voters' top-to-bottom rankings are:



     40    
35     25

      A      B 
    C

      B     
C      A

      C     
A      B



Kemeny-Young defines the "best" order of finish as the order of
finish that minimizes the sum of voters' pairwise preferences that the order
"disagrees" with.



There are three majorities:

     75 rank B over C (with 25 opposed).

     65 rank A over B (with 35 opposed).

     60 rank C over A (with 40 opposed).



KY says the best order of finish is ABC.  ABC disagrees with the 25 who
rank C over B and the 35 who rank B over A and the 60 who rank C over A.  Thus
the sum of pairwise preferences that ABC disagrees with is 120. (All other
possible orders of finish have a larger sum, and are therefore worse, according
to KY.)  Since ABC is the order of finish, the winner is A.


 


Example
2:  Same scenario as example 1, but suppose a clever voter who favors B
decides to also nominate a fourth alternative D that's similar to C (but
slightly inferior to C).  Now the voters' top-to-bottom rankings are:



     40    
35     25

      A     
B      C

      B     
C      D

      C      D  
   A

      D     
A      B



[….]

Now there are six majorities:

     C is ranked over D by a majority of size x [i.e. 100
in this case]. (x doesn't matter but let's suppose it's largest.)

     75 rank B over C [with 25 opposed].

     75 rank B over D [with 25 opposed].

     65 rank A over B [with 35 opposed].

     60 rank C over A [with 40 opposed].

     60 rank D over A [with 40 opposed].



Now KY says the best order of finish is BCDA.  BCDA disagrees with the 25
who rank C over B and the 25 who rank D over B and the 65 who rank A over B and
the 40 who rank A over C and the 40 who rank A over D, which sum to 295-x [i.e.
295 – 100].  ABCD is not the best order of finish because it disagrees
with [the 35 who rank B over A] and [the 25 who rank C over B] and the 25 who
rank D over B and the [60 who rank C over A] and the 60 who rank D over A,
which sum to 305-x.  Th[is] larger sum makes ABCD worse than BCDA,
according to KY.



Now the KY winner is B.  The clever voter who favors B changed the winner
by nominating D.  When small groups vote, typically the rules allow one or
two people to nominate an alternative, which means it's easy for a tiny
minority to manipulate the outcome when a voting method isn't independent of
clones.



In example 1, MAM agrees that ABC is the best order of finish.  In example
2, MAM says the best order of finish is ABCD. (With MAM the clever voter fails
to change the winner.)  Here's how MAM works:



     MAM constructs the order of finish a piece at a time,
by considering 

     the majorities one at a time, from largest majority to
smallest majority:  

     For each majority, MAM places their more-preferred
candidate ahead 

     of their less-preferred candidate in the order of
finish, unless MAM 

     has already placed their less-preferred candidate
ahead of their 

     more-preferred candidate (due to the
"transitivity" property of an 

     order of finish, as the following will explain).



In example 1, the largest majority rank B over C [i.e. a majority of 75], so
MAM places B ahead of C in the [initial] order of finish:

     B>C

The second largest majority is A over B [i.e. 65], so MAM next places A ahead
of B in the [second] order of finish:

     A>B>C  [SB: Now the cumulated maximized affirmed majorities
are: 75+65= 140.]




Because A finishes ahead of B and B finishes ahead of C, it follows that A
finishes ahead of C too. (This is the transitivity property I mentioned.)






The third largest majority is C
over A [i.e. 60], but MAM does not place C ahead of A because A is already
[transitively] ahead of C [with an MAM of 140]. The completed order of finish
is ABC, and MAM elects A.  [SB:  A>B>C’s MAM of 140 shows that ABC is the
most popular possible sequence when compared to the cumulated affirmed
majorities of each of the other possible sequences: BCA:  135, CAB: 
125, ACB:  0, CBA:  0, BAC: 
0]



In example 2, let's assume the largest majority is the voters who rank C over D
(although this doesn't matter).  Thus this is the first majority that MAM
considers, and MAM places C ahead of D in the order of finish:

     CD



Next MAM considers the second largest majority, which is either the 75 who rank
B over C or the 75 who rank B over D.  Later I'll discuss how MAM chooses
between majorities that are the same size; for now let's assume MAM decides the
second largest majority is the 75 who rank B over D and the third largest
majority is the 75 who rank B over C.



Since the second largest majority rank B over D, MAM now places B ahead of D in
the order of finish:

     CD

     BD



Since the third largest majority rank B over C, MAM next places B ahead of C in
the order of finish:

     BCD

The fourth largest majority [I have similarly chosen for simplicity] is the 65
who rank A over B, so MAM places A ahead of B in the order of finish:

     ABCD

Note that because A is ahead of B and B is ahead of C & D, this means A is
ahead of C & D too. (The transitivity property.)



(The order of finish is now a linear ordering, ABCD, so if we wished we could
stop here and elect A.  But let's keep going.)



The fifth largest majority is either the 60 who rank C over A or the 60 who
rank D over A.  Again I'll defer an explanation of this
"tiebreaking" of same-size majorities; for now let's assume MAM
considers the fifth largest majority to be the 60 who rank C over A and the
sixth largest majority to be the 60 who rank D over A.



The fifth largest majority rank C over A, but since A is already ahead of C in
the order of finish, MAM does not place C ahead of A.



The sixth largest majority rank D over A, but since A is already ahead of D in
the order of finish, MAM does not place D ahead of A.



The completed order of finish is ABCD, so MAM elects A.  Nominations of
similar alternatives (D, which is similar to C) don't change the outcome with
MAM.



There are other criteria satisfied by MAM but not by KY, but as far as I know
the only criterion satisfied by KY but not by MAM is the Weak Reinforcement
criterion I mentioned above.  When Peyton Young promoted KY in his papers
and at least one book (Equity in Theory and Practice), he touted a criterion he
called Local Independence of Irrelevant Alternatives... which is satisfied by
MAM.



(There's another criterion called Reinforcement by Donald Saari, which I call
Strong Reinforcement, that neither KY nor MAM satisfy: If two collections of
votes separately elect X, then X must be elected if the votes are
combined.  The Borda method satisfies it, and so does Plurality
Rule.  Like Weak Reinforcement, I believe Strong Reinforcement is
unimportant, because it's simple to have a rule that prevents a minority from
dividing the voters into groups.)



Another problem with KY is that it takes a long time to find its best order of
finish when there are many candidates.  There's a "combinatorial
explosion" of possible orders of finish, and each one needs to be
checked.  The difficulty in checking all possible orders of finish, to calculate
each one's sum, is why I didn't include KY in software I wrote years ago that
compares voting methods head-to-head to see which methods' winners are
preferred by more voters. (My software generates a series of random votes,
tallies the votes using two voting methods and accumulates statistics.  I
presume James Green-Armytage used similar software to conduct his analysis.)



* * *



Regarding tiebreaking in MAM:



There are two places in MAM's algorithm where tiebreaking can be
required.  One is when majorities are the same size, as mentioned
above.  The other can result from a tied pairing; the simplest example is
a two-candidate election in which the voters split 50/50.  In this case,
consideration of all the majorities may not suffice to place one candidate
ahead of the other. (Transitivity may do it [as it might be as illustrated by
the following example:].  For example: suppose the "A versus B"
pairing is tied, and [at the same time there is] a majority rank A over C, and
a majority rank C over B.  [These additional pairings produce:
A>C>B.]  The order of finish after
MAM considers the[se] two majorities is ACB, and no tiebreaking is needed to
resolve A versus B.)



In an election with many voters, it will be very rare that two [pairing]
majorities are the same size, and [thus] it will be very rare that a pairing is
tied.  So the simple definition of MAM provided above would typically
suffice for public elections.



The tiebreak procedure has been carefully chosen so that MAM completely
satisfies criteria such as Independence of Clone Alternatives, Strong Pareto,
etc.  In elections with many voters, tiebreaking would be extremely rare
so the [complete satisfaction of these criteria would not be in doubt’ completeness
of the criteria satisfaction would not matter, but in voting by small
groups it's important to [provide a tiebreaking method that would] completely
satisfy Independence of Clones.  With any voting method that doesn't
completely satisfy Independence of Clones [like KY or VoteFair], elections in
small groups can degenerate into farces, because each faction will always have
an incentive to nominate a huge number of clones because there's a chance it
can help and it can't hurt.  [SB:  It can help by effectively multiplying the
size of the ‘majority’ of the most favored clone over the other clones.  The more supporters of the favored clone who
explicitly favor her over all of her slightly inferior clones, the greater will
be her majority.  This enables each
strategizer’s vote to count (have more weight) than each other voter.]



The [MAM] tiebreak procedure begins the same way for both same-size majorities
and resolving tied pairings.  A tiebreak ordering of the candidates is
constructed by randomly picking [one ballot]at a time, and including into the
tiebreak ordering all of [that] ballot's preferences that don't conflict with
the preferences already included from the ballots [that may have been]
previously picked [in order to break any earlier ties.  This procedure is repeated] until the
tiebreak ordering is complete.  Here's a simple example:  Suppose
there are 3 voters and 4 candidates A,B,C,D, and suppose the voters'
top-to-bottom rankings are as follows:



     
A      B      C

     B=C    
C      D

     
D             A

             
      B



The middle vote [Voter 2 has] omitted A & D.  MAM treats it the same
as if the voter had [explicitly] ranked A & D equally at the bottom:



     
A      B      C

     B=C    
C      D

      D    
A=D     A

             
      B



MAM picks one of the votes at random.  Suppose it's the middle vote. 
MAM includes its preferences into the [1st suggested] tiebreak
ordering, which becomes BC(A=D), identical to the [ordering of this picked
voter].  The tiebreak ordering isn't yet complete because it's not a
linear ordering (it ranks A & D the same) so MAM picks another vote at
random.  Suppose it's the left vote.  The left vote ranks A over D,
so MAM includes the A over D preference into the tiebreak ordering, which [now]
becomes BCAD.  Now the tiebreak ordering is a linear ordering, so there's
no need to pick any more votes [at random].



Let's return to example 2, which has two pairs of same-size majorities: two
majorities are 75 voters, and two majorities are 60 voters.  When MAM
reaches the point at which it wants to consider the second largest majority, it
sees that two majorities have 75 voters.  So it checks the sizes of their
opposing minorities.  If one of the same-size majorities is opposed by a
smaller minority, then that would be the majority that MAM considers next. 
In example 2, though, the opposing minorities are both the same size
(25).  So MAM picks a vote at random to start constructing the tiebreak
ordering.  Suppose the vote that MAM picks is one of the 35 votes that
rank B over C over D over A.  All of this vote's preferences are included
into the tiebreak ordering, which becomes BCDA (identical to the vote that was
picked).  The tiebreak ordering is now a linear ordering, so no more votes
need to be picked.  Next MAM compares the two same-size majorities by
checking the positions of their less-preferred candidates in the tiebreak
ordering:  The less-preferred candidate of the 75 who rank B over C is C,
and the less-preferred candidate of the 75 who rank B over D is D.  Since
D is behind C in the BCDA tiebreak ordering, MAM will consider [and give
priority to] the 75 who rank B over D before considering the 75 who rank B over
C.  In other words, the second largest majority is the 75 who rank B over
D, and the third largest majority is the 75 who rank B over C.



Later, when MAM reaches the point where it wants to consider the fifth largest
majority, it finds 60 who rank C over A and 60 who rank D over A.  In both
of these same-size majorities, the less-preferred candidate is A.  So MAM
checks the positions of their more-preferred candidates in the tiebreak
ordering.  The more-preferred candidate of the 60 who rank C over A is C,
and the more-preferred candidate of the 60 who rank D over A is D.  Since
C is ahead of D in the BCDA tiebreak ordering, MAM will consider [and give
priority to] the 60 who rank C over A before considering the 60 who rank D over
A.  In other words, the fifth largest majority is the 60 who rank C over
A, and the sixth largest majority is the 60 who rank D over A.



In the case where a pairing is tied and not resolved by transitive majorities,
MAM uses the [??? following] and give priority tiebreak ordering to
break the tie(s) in the order of finish.  Suppose there's a 5-candidate
election and that after all the majorities have been considered, the order of
finish is (A=B)C(D=E).  In other words, A & B are tied for first
place, and D & E are tied for last place.  MAM will pick votes at
random to construct a linear tiebreak ordering as described above. 
Suppose the tiebreak ordering is CEBDA.  MAM breaks the ties beginning
with the most significant tie, in this case A versus B.  Since B is ahead
of A in the tiebreak ordering CEBDA, MAM places B ahead of A, and the order of
finish becomes BAC(D=E).  The next tie to break is D versus E.  Since
E is ahead of D in the tiebreak ordering CEBDA, MAM places E ahead of D, and
the order of finish becomes BACED.  MAM always constructs a linear order
of finish, resolving all ties.



Because voters can express indifference between candidates, it's theoretically
possible that every vote will be indifferent between two candidates. (Identical
twins?)  In other words, the procedure of randomly picking votes may fail
to produce a linear tiebreak ordering even after every vote has been
picked.  In this case, the incomplete tiebreak ordering is completed (made
linear) by randomly completing it.  Then any ties can be broken.



There's a shortcut in the tiebreak procedure that can save labor in some cases,
but it's not worth discussing the shortcut here. (Here's a hint: the
tiebreaking ordering only needs to be as linear as necessary.)



Did I answer all your questions?



Would it help if I provide source code for MAM written in the Ruby programming
language?  I tried to write it in a way that will make it as easy as
possible for people unfamiliar with Ruby to understand it.  It's not a
complete program; it doesn't have the routines needed to input votes or parse
the votes, but those routines aren't unique to MAM; they're needed in any
pairwise voting method.



Also, you can freely use the online MAM server at:  http://MAM.hostei.com






[….]


 


Best
wishes,

Steve Eppley


 		 	   		   		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20151020/593c506f/attachment-0001.htm>