[EM] (5) MAM better than VoteFair: Steve's 5th dialogue with Kristofer
Toby Pereira
tdp201b at yahoo.co.uk
Wed Oct 21 17:17:55 PDT 2015
Apologies if this has been discussed at length before, but is MAM different enough from Ranked Pairs to be considered a different method? A quick search suggests to me that the differences are that 1) Ranked Pairs requires voters to give a full ordering of candidates whereas MAM allows ties, and 2) MAM uses winning votes rather than margins.
I wasn't even aware Ranked Pairs required this full ordering anyway, but relaxing it is not really a new method. Also margins/winning votes isn't even an issue if ties aren't allowed. And it's generally understood that methods where the inventor says they prefer winning votes or margins can also be used the other way while remaining the same basic method. E.g. Schulze with margins is still Schulze.
From: steve bosworth <stevebosworth at hotmail.com>
To: "ElectionMethods at VoteFair.org" <electionmethods at votefair.org>; "election-methods at lists.electorama.com" <election-methods at lists.electorama.com>; "km_elmet at t-online.de" <km_elmet at t-online.de>
Sent: Tuesday, 20 October 2015, 16:38
Subject: Re: [EM] (5) MAM better than VoteFair: Steve's 5th dialogue with Kristofer
<!--#yiv4340004040 .yiv4340004040hmmessage P{margin:0px;padding:0px;}#yiv4340004040 body.yiv4340004040hmmessage{font-size:12pt;font-family:Calibri;}-->
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
<!--#yiv4340004040 .yiv4340004040ExternalClass .yiv4340004040ecxhmmessage P {padding:0px;}#yiv4340004040 .yiv4340004040ExternalClass body.yiv4340004040ecxhmmessage {font-size:12pt;font-family:Calibri;}-->
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 thanVoteFair: Steve's 4th dialogue with Richard Fobes
Hi Kristofer, and all others,
Kristofer, thank you for the detailedexplanation (copied below) that you gave me in response to my questions in myEM dialogue with Richard Fobes. I askedabout how Kemeny-Young (KY or VoteFair) scored the pairs to find the winningsequence. You concluded that KY is vulnerableto cloning attacks while Maximize Affirmed Majorities (MAM) is not. At the time, I felt that I did not fullyunderstand all of your explanations but I hope I do now. I think I have done this with the help an editedversion of the relevant parts of Steve Eppley’s email to me (see below). As a result, I have tentatively concludedthat 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 itif you (or anyone else) would tell me whether or not the following accountshows that I have fully understood MAM and its superiority over KY for theelection of a President. To Steve Eppley’swords, I have sometimes [added my own words in square brackets (SB)] in anattempt to confirm my understandings. Ifound his less abstract mathematical ways of explaining MAM very helpful. For example, he explains in his 2ndExample how, when using VoteFair, the adding of clone D to C changes the winnerfrom A to B. MAM retains A as the winner.
FromSteve 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 CloneAlternatives. (If you're unfamiliar with Independence of Clone Alternatives,the pair of examples below will help to explain it.) A criterion that KYsatisfies but MAM doesn't is Weak Reinforcement: If two collections of votestallied separately produce the same order of finish, then that same order offinish 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 smallminority to nominate clones, whereas Weak Reinforcement is unimportant becausea simple rule can prevent a minority from dividing the voters into separategroups (districts). Weak Reinforcement is an example of criteria I call"aesthetic consistency" criteria; society won't be harmed by votingmethods that fail those criteria. Too much of the academic literature ofsocial choice theory is about unimportant aesthetic consistency criteria.
To illustrate how Kemeny-Young and MAM work, here's a pair of examples thattogether also serve to illustrate the Independence of Clone Alternativescriterion:
Example 1. Suppose there are 100 voters and 3 candidates A, B andC. 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 offinish 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 whorank C over B and the 35 who rank B over A and the 60 who rank C over A. Thusthe sum of pairwise preferences that ABC disagrees with is 120. (All otherpossible orders of finish have a larger sum, and are therefore worse, accordingto KY.) Since ABC is the order of finish, the winner is A.
Example2: Same scenario as example 1, but suppose a clever voter who favors Bdecides to also nominate a fourth alternative D that's similar to C (butslightly 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. 100in 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 25who rank C over B and the 25 who rank D over B and the 65 who rank A over B andthe 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 disagreeswith [the 35 who rank B over A] and [the 25 who rank C over B] and the 25 whorank 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 winnerby nominating D. When small groups vote, typically the rules allow one ortwo people to nominate an alternative, which means it's easy for a tinyminority to manipulate the outcome when a voting method isn't independent ofclones.
In example 1, MAM agrees that ABC is the best order of finish. In example2, MAM says the best order of finish is ABCD. (With MAM the clever voter failsto 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 tosmallest majority:
For each majority, MAM places their more-preferredcandidate ahead
of their less-preferred candidate in the order offinish, unless MAM
has already placed their less-preferred candidateahead 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], soMAM 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 aheadof B in the [second] order of finish:
A>B>C [SB: Now the cumulated maximized affirmed majoritiesare: 75+65= 140.]
Because A finishes ahead of B and B finishes ahead of C, it follows that Afinishes ahead of C too. (This is the transitivity property I mentioned.)
The third largest majority is Cover 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 finishis ABC, and MAM elects A. [SB: A>B>C’s MAM of 140 shows that ABC is themost popular possible sequence when compared to the cumulated affirmedmajorities 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 MAMconsiders, 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 rankB over C or the 75 who rank B over D. Later I'll discuss how MAM choosesbetween majorities that are the same size; for now let's assume MAM decides thesecond largest majority is the 75 who rank B over D and the third largestmajority is the 75 who rank B over C.
Since the second largest majority rank B over D, MAM now places B ahead of D inthe order of finish:
CD
BD
Since the third largest majority rank B over C, MAM next places B ahead of C inthe order of finish:
BCD
The fourth largest majority [I have similarly chosen for simplicity] is the 65who 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 isahead of C & D too. (The transitivity property.)
(The order of finish is now a linear ordering, ABCD, so if we wished we couldstop 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 whorank D over A. Again I'll defer an explanation of this"tiebreaking" of same-size majorities; for now let's assume MAMconsiders the fifth largest majority to be the 60 who rank C over A and thesixth 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 inthe 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 inthe order of finish, MAM does not place D ahead of A.
The completed order of finish is ABCD, so MAM elects A. Nominations ofsimilar alternatives (D, which is similar to C) don't change the outcome withMAM.
There are other criteria satisfied by MAM but not by KY, but as far as I knowthe only criterion satisfied by KY but not by MAM is the Weak Reinforcementcriterion I mentioned above. When Peyton Young promoted KY in his papersand at least one book (Equity in Theory and Practice), he touted a criterion hecalled Local Independence of Irrelevant Alternatives... which is satisfied byMAM.
(There's another criterion called Reinforcement by Donald Saari, which I callStrong Reinforcement, that neither KY nor MAM satisfy: If two collections ofvotes separately elect X, then X must be elected if the votes arecombined. The Borda method satisfies it, and so does PluralityRule. Like Weak Reinforcement, I believe Strong Reinforcement isunimportant, because it's simple to have a rule that prevents a minority fromdividing the voters into groups.)
Another problem with KY is that it takes a long time to find its best order offinish when there are many candidates. There's a "combinatorialexplosion" of possible orders of finish, and each one needs to bechecked. The difficulty in checking all possible orders of finish, to calculateeach one's sum, is why I didn't include KY in software I wrote years ago thatcompares voting methods head-to-head to see which methods' winners arepreferred by more voters. (My software generates a series of random votes,tallies the votes using two voting methods and accumulates statistics. Ipresume 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 berequired. One is when majorities are the same size, as mentionedabove. The other can result from a tied pairing; the simplest example isa two-candidate election in which the voters split 50/50. In this case,consideration of all the majorities may not suffice to place one candidateahead of the other. (Transitivity may do it [as it might be as illustrated bythe 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, anda majority rank C over B. [These additional pairings produce:A>C>B.] The order of finish afterMAM considers the[se] two majorities is ACB, and no tiebreaking is needed toresolve 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 istied. So the simple definition of MAM provided above would typicallysuffice for public elections.
The tiebreak procedure has been carefully chosen so that MAM completelysatisfies criteria such as Independence of Clone Alternatives, Strong Pareto,etc. In elections with many voters, tiebreaking would be extremely rareso the [complete satisfaction of these criteria would not be in doubt’ completenessof the criteria satisfaction would not matter, but in voting by smallgroups it's important to [provide a tiebreaking method that would] completelysatisfy Independence of Clones. With any voting method that doesn'tcompletely satisfy Independence of Clones [like KY or VoteFair], elections insmall groups can degenerate into farces, because each faction will always havean incentive to nominate a huge number of clones because there's a chance itcan help and it can't hurt. [SB: It can help by effectively multiplying thesize of the ‘majority’ of the most favored clone over the other clones. The more supporters of the favored clone whoexplicitly favor her over all of her slightly inferior clones, the greater willbe her majority. This enables eachstrategizer’s vote to count (have more weight) than each other voter.]
The [MAM] tiebreak procedure begins the same way for both same-size majoritiesand resolving tied pairings. A tiebreak ordering of the candidates isconstructed by randomly picking [one ballot]at a time, and including into thetiebreak ordering all of [that] ballot's preferences that don't conflict withthe preferences already included from the ballots [that may have been]previously picked [in order to break any earlier ties. This procedure is repeated] until thetiebreak ordering is complete. Here's a simple example: Supposethere 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 sameas 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] tiebreakordering, which becomes BC(A=D), identical to the [ordering of this pickedvoter]. The tiebreak ordering isn't yet complete because it's not alinear ordering (it ranks A & D the same) so MAM picks another vote atrandom. 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'sno need to pick any more votes [at random].
Let's return to example 2, which has two pairs of same-size majorities: twomajorities are 75 voters, and two majorities are 60 voters. When MAMreaches the point at which it wants to consider the second largest majority, itsees that two majorities have 75 voters. So it checks the sizes of theiropposing minorities. If one of the same-size majorities is opposed by asmaller 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 tiebreakordering. Suppose the vote that MAM picks is one of the 35 votes thatrank B over C over D over A. All of this vote's preferences are includedinto the tiebreak ordering, which becomes BCDA (identical to the vote that waspicked). The tiebreak ordering is now a linear ordering, so no more votesneed to be picked. Next MAM compares the two same-size majorities bychecking the positions of their less-preferred candidates in the tiebreakordering: 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. SinceD is behind C in the BCDA tiebreak ordering, MAM will consider [and givepriority to] the 75 who rank B over D before considering the 75 who rank B overC. In other words, the second largest majority is the 75 who rank B overD, 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 largestmajority, it finds 60 who rank C over A and 60 who rank D over A. In bothof these same-size majorities, the less-preferred candidate is A. So MAMchecks the positions of their more-preferred candidates in the tiebreakordering. 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. SinceC is ahead of D in the BCDA tiebreak ordering, MAM will consider [and givepriority to] the 60 who rank C over A before considering the 60 who rank D overA. In other words, the fifth largest majority is the 60 who rank C overA, 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 tobreak the tie(s) in the order of finish. Suppose there's a 5-candidateelection and that after all the majorities have been considered, the order offinish is (A=B)C(D=E). In other words, A & B are tied for firstplace, and D & E are tied for last place. MAM will pick votes atrandom to construct a linear tiebreak ordering as described above. Suppose the tiebreak ordering is CEBDA. MAM breaks the ties beginningwith the most significant tie, in this case A versus B. Since B is aheadof A in the tiebreak ordering CEBDA, MAM places B ahead of A, and the order offinish becomes BAC(D=E). The next tie to break is D versus E. SinceE is ahead of D in the tiebreak ordering CEBDA, MAM places E ahead of D, andthe order of finish becomes BACED. MAM always constructs a linear orderof finish, resolving all ties.
Because voters can express indifference between candidates, it's theoreticallypossible that every vote will be indifferent between two candidates. (Identicaltwins?) In other words, the procedure of randomly picking votes may failto produce a linear tiebreak ordering even after every vote has beenpicked. In this case, the incomplete tiebreak ordering is completed (madelinear) 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: thetiebreaking 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 programminglanguage? I tried to write it in a way that will make it as easy aspossible for people unfamiliar with Ruby to understand it. It's not acomplete program; it doesn't have the routines needed to input votes or parsethe votes, but those routines aren't unique to MAM; they're needed in anypairwise voting method.
Also, you can freely use the online MAM server at: http://MAM.hostei.com
[….]
Bestwishes,
Steve Eppley
----
Election-Methods mailing list - see http://electorama.com/em for list info
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20151022/3489e76d/attachment-0001.htm>
More information about the Election-Methods
mailing list