Non-monotonicity of Zavist-Tideman (was Re: [EM] re: Markus: RP & BeatpathWinner/CSSD)

[Steve Eppley]

On 11 Mar 2003 at 16:08, Eric Gorr wrote:
> Steve Eppley wrote:
> >It is more reasonable to use the term MAM as a variation of
> >Ranked Pairs than as a synonym for Ranked Pairs.  MAM is
> >monotonic, whereas Zavist-Tideman's Ranked Pairs 1989 is
> >not (nor is the "winning votes" variation of Ranked Pairs
> >1989).
> 
> I was just wondering if you could provide a specific example which 
> shows that the winning votes variation of RP is not monotonic.

There is more than one "winning votes" variation of Ranked Pairs.  
MAM is a "winning votes" variation of Ranked Pairs and is monotonic.  
My claim is that Zavist's 1989 variation of Ranked Pairs is not 
monotonic, neither his "margins" variation nor the "wv" variation.  

(Do we have to call these variations of "Ranked Pairs"?  Tideman 
coined that name in 1987, but Condorcet appears to have described the 
basic algorithm in 1785.)

I need to go check my old notes for the example, since it's been 
a couple of years since I discovered the non-monotonicity of Zavist's 
tiebreaker.  

If my memory is correct, the Zavist non-monotonicity example 
required only 3 candidates and all votes were strict rankings 
(so it didn't matter whether majority size was measured by 
"winning votes" or by "margin."  I'll need to check my notes 
for the details, but I think there was a cycle where two of the 
majorities were equally smallest and there was a voter who, by 
upranking a candidate, decreased its probability of winning when 
using Zavist's tiebreaker, meaning Zavist's method is not monotonic.

Of course, until I post the example, or until you rediscover it 
for yourself, don't accept my word for it.

In the meantime, you can compare my tiebreak method with Zavist's. 
(My tiebreaker was inspired by Zavist's; I don't claim credit for an 
independent development there.  MAM was mostly an independent 
development, though.)  Here's how 
MAM sorts the majorities (after constructing a strict "tiebreaking" 
ordering of the candidates, call it T, using the Random Voter 
Hierarchy procedure):    

   For all pairs of candidates, for instance x and y, 
   let #xy denote the number of votes that rank x over y.

   For all pairs of majorities, for instance x>y and z>w, 
   x>y precedes z>w if and only if at least one of the 
   following conditions holds:

      1.  #xy > #zw.
      2.  #xy = #zw and #wz > #yx.
      3.  #xy = #zw and #wz = #yx and T ranks w over y.
      4.  #xy = #zw and #wz = #yx and w = y and T ranks x over z. 

Condition 1 makes MAM a "winning votes" method.  
Conditions 3 and 4 define the "tiebreaker" when two majorities
are the same size.  Since T is a strict ordering of the candidates, 
the definition above generates a strict ordering of the majorities.  
(There's a subtle difference in how Zavist's tiebreaker works.) 

-- Steve Eppley