[EM] Non-monotonicity example for Zavist-Tideman Ranked Pairs

[Steve Eppley]

Hi, 
In the following message I'll use these abbreviations:

   RPT = Tideman's 1987 Ranked Pairs method
   RPZ = Zavist-Tideman's 1989 Ranked Pairs method
   RPZwv = the "winning votes" variation of RPZ
   MAM = the "Maximize Affirmed Majorities" voting 
            method (which is similar to RPZwv)

In a recent message I pointed out that MAM is monotonic and that 
neither RPZ nor RPZwv are monotonic.  In other words, upranking a 
candidate can decrease its probability of being elected if RPZ or 
RPZwz are used, but not if MAM is used. (My web pages at 
www.alumni.caltech.edu/~seppley include a proof that MAM is 
monotonic.) 

Here is an example that demonstrates non-monotonicity of RPZ and 
RPZwv.  Suppose 9 voters vote on 3 candidates {A,B,C} as follows: 

   3   2   2   1   1
   A   B   C   A   C
   B   C   A   C   B
   C   A   B   B   A

Since every vote is a strict ordering of the candidates, the 
"margins" and "wv" methods are equivalent, so I only need to show 
that RPZwv is not monotonic. (The reasoning for RPZ is the same.)

There are 3 pairwise majorities:
   A>B (6>3)
   B>C (5>4)
   C>A (5>4)

Since A>B is the largest majority, RPZwv affirms it first, with 
certainty.  To decide which one of the two equally smaller majorities 
to affirm, Zavist first constructs a "tiebreaking ranking of the 
candidates", abbreviated TBRC, that is a strict ordering of the 
candidates, by randomly picking one of the ballots, adopting all of 
its strict preferences, and randomly resolving that ballot's 
indifferences (if any).  Then Zavist uses the TBRC to rank the 
majorities as follows:

   For all majorities, for instance x>y, 
   let t(x,y) denote x if TBRC ranks x over y, 
   and y otherwise.

   For all majorities, for instance x>y, 
   let b(x,y) denote y if TBRC ranks x over y, 
   and x otherwise.

   For all pairs of majorities, for instance x>y 
   and z>w, such that x>y and z>w are the "same size", 
   x>y precedes z>w according to Zavist if and only if
   either of the following conditions holds: 
    1. TBRC ranks t(x,y) over t(z,w).
    2. t(x,y) = t(z,w) and TBRC ranks b(x,y) over b(z,w).

In the example, there are 5 cases to consider:

   Case 1: Zavist picks one of the three A>B>C votes 
   for the TBRC. (This has a 3/9 probability.)  
   In this case, t(B,C) = B and t(C,A) = A and 
   TBRC ranks A over B, so RPZwv affirms C>A second,
   and does not affirm B>C (since it would cycle with
   the majorities already affirmed) and elects C.

   Case 2: Zavist picks one of the two B>C>A votes 
   for the TBRC. (This has a 2/9 probability.)  
   In this case, t(B,C) = B and t(C,A) = C and 
   TBRC ranks B over C, so RPZwv affirms B>C second,
   and does not affirm C>A (since it would cycle with
   the majorities already affirmed) and elects A.

   Case 3: Zavist picks one of the two C>A>B votes 
   for the TBRC. (This has a 2/9 probability.)  
   In this case, t(B,C) = C and t(C,A) = C and 
   b(B,C) = B and b(C,A) = A and TBRC ranks A over B, 
   so RPZwv affirms C>A second, and does not 
   affirm B>C (since it would cycle with the 
   majorities already affirmed) and elects C.

   Case 4: Zavist picks the A>C>B vote for the TBRC.
   (This has a 1/9 probability.)  In this case, 
   t(B,C) = C and t(C,A) = A and TBRC ranks A over C, 
   so RPZwv affirms C>A second, and does not 
   affirm B>C (since it would cycle with the 
   majorities already affirmed) and elects C.

   Case 5: Zavist picks the C>B>A vote for the TBRC.
   (This has a 1/9 probability.)  In this case, 
   t(B,C) = C and t(C,A) = C and b(B,C) = B and 
   b(C,A) = A and TBRC ranks B over A, so RPZwv 
   affirms B>C second, and does not affirm C>A 
   (since it would cycle with the majorities 
   already affirmed) and elects A.

Thus RPZwv (and RPZ) give A a 3/9 chance of being elected, and give C 
a 6/9 chance of being elected. 

Now suppose the 9th voter changes her vote from C>B>A to C>A>B.  
Since this is an upranking of A, satisfaction of monotonicity 
requires that A's chance of being elected must not decrease.  

With the changed vote, the A>B majority increases from 6>3 to 7>2 and 
is still affirmed first with certainty.  The other two majorities are 
unaffected, so a TBRC must still be constructed to break that tie.  
But now case 5 is eliminated and case 3's probability increases from 
2/9 to 3/9.  Thus C's chance of being elected increases to 7/9 and 
A's chance decreases to 2/9.  This means RPZwv (and RPZ) are not 
monotonic. (On the other hand, they obviously come much closer to 
satisfying monotonicity than do methods like Instant Runoff, since 
they can only fail monotonicity in scenarios involving ties, which 
are unlikely in large public elections.)

Here is how MAM tallies the example before the vote is changed:  
First the largest majority, A>B, is affirmed.  
Since the remaining two are the same size, MAM constructs a strict 
ordering of the alternatives, call it T, using the Random Voter 
Hierarchy procedure.  Again there are 5 cases to consider:

   Case 1: T = A>B>C (3/9 probability).  
   Since T ranks the "pairloser" of C>A over the 
   "pairloser" of B>C, MAM affirms B>C second, and
   does not affirm C>A (since it would cycle with
   the majorities already affirmed) and elects A.

   Case 2: T = B>C>A (2/9 probability).  
   Since T ranks the "pairloser" of B>C over the 
   "pairloser" of C>A, MAM affirms C>A second, and
   does not affirm B>C (since it would cycle with
   the majorities already affirmed) and elects C.

   Case 3: T = C>A>B (2/9 probability).  
   Since T ranks the "pairloser" of B>C over the 
   "pairloser" of C>A, MAM affirms C>A second, and
   does not affirm B>C (since it would cycle with
   the majorities already affirmed) and elects C.

   Case 4: T = A>C>B (1/9 probability).  
   Since T ranks the "pairloser" of C>A over the 
   "pairloser" of B>C, MAM affirms B>C second, and
   does not affirm C>A (since it would cycle with
   the majorities already affirmed) and elects A.

   Case 5: T = C>B>A (1/9 probability).  
   Since T ranks the "pairloser" of B>C over the 
   "pairloser" of C>A, MAM affirms C>A second, and
   does not affirm B>C (since it would cycle with
   the majorities already affirmed) and elects C.

Thus MAM has a 4/9 chance of electing A and a 5/9 chance of electing 
C. (This seems reasonable since 4/9 of the voters rank A over C and 
5/9 of the voters rank C over A.)  Now suppose the 9th voter upranks 
A as before.  Again case 5 is eliminated and case 3's probability 
increases from 2/9 to 3/9, but with MAM this means A still has a 4/9 
chance and C still has a 5/9 chance.

There's a minor argument in Zavist's favor that I consider 
insignificant: My proof that MAM completely satisfies the strong 
Pareto criterion depends on its tiebreaking ranking of the candidates 
(which I called T above, but not in my web pages) also satisfying 
strong Pareto.  This holds since MAM's tiebreaking ranking is 
constructed using Random Voter Hierarchy, which satisfies strong 
Pareto.  But it might not hold for variations of MAM that construct a 
tiebreaking ranking some other way.  RPZ and RPZwv also satisfy 
strong Pareto (note however that RPT does not), even though RPZ and 
RPZwv do not specify that Random Voter Hierarchy be used to construct 
the TBRC.  My web pages include a proof that MAM satisfies strong 
Pareto and an example that shows RPT does not, but they do not 
include my slightly different proof that RPZwv and RPZ satisfy strong 
Pareto. 

Tideman's 1987 proof that RPT is monotonic used a slightly weaker 
definition of monotonicity.  Recall that RPT is a "choice 
correspondence" (which means it selects one or more of the 
alternatives), whereas RPZ, RPZwv and MAM are technically called 
"lotteries" (which means they give each alternative some probability 
in the range [0,1] of being elected, such that the sum of 
probabilities equals the number of candidates to be elected, usually 
one).  Often the tiebreaker for a choice correspondence is left 
unstated, or the possibility of picking randomly from the selected 
subset is suggested. (I think RPT specified picking one randomly.)  
So monotonicity is often defined for choice correspondences as 
"Upranking a candidate must not cause it to drop out of the selected 
subset."  Choice correspondences are incomplete specifications of 
voting methods, and I think it's best to consider complete 
specifications that include the tiebreaker, when possible.  The 
wording of monotonicity in terms of "probability of election" is nice 
and general, when voting methods are completely specified (even if 
the voting methods are deterministic, since deterministic decisive 
voting methods are equivalent to "degenerate" lotteries).

When testing the monotonicity of a choice correspondence with 
tiebreaker left unstated, I think a second condition should be added 
to the definition of monotonicity, that requires no candidates other 
than the upranked one may enter the selected subset.  In other words, 
the following definition: 

   For all collections V of votes, let C(V) denote 
   the (non-empty) subset of alternatives selected 
   by the choice correspondence given V.

   Call a choice correspondence C monotonic if and 
   only if both of the following conditions hold 
   for all candidates x, all collections V of votes, 
   and all collections V' of votes that are the same 
   as V except one or more votes rank x higher in V' 
   than the corresponding vote(s) in V (note that 
   all preferences between all y,z distinct from x 
   are the same in V' as in V):
      1. If x is in C(V) then x is in C(V').
      2. If y is not in C(V) and y is not x
         then y is not in C(V').

The second condition should be added because, otherwise, the 
tiebreaker could elect some other candidate y that slips into the 
selected subset when x is upranked.  For instance, x's chance of 
being elected by the "Random" tiebreaker would decrease if C(V') 
contains more alternatives than C(V) contains.  For another instance, 
x's chance of being elected by Random Dictator could decrease if the 
random dictator ballot ranks y over x.

By the way, even though I'm pointing out that MAM is monotonic and 
some other RP variations are not, I should say that I consider 
monotonicity relatively unimportant.  I think it would be merely an 
aesthetically pleasing "consistency" criterion, were it not for the 
risk of needlessly providing ammunition to ivory tower academics 
hired to criticize methods proposed by a voting reform movement.  If 
someone knows of a good justification for requiring monotonicity 
(that is better than the aesthetic pleasure derived from its 
satisfaction), please let me know. (Or if I may borrow Markus 
Schulze' recent words, why is satisfaction of monotonicity not "just 
a curiosity"?)

-- Steve Eppley