[EM] MAM non-deterministic when tied losers make cycle?

[Steve Eppley]

On 15 Mar 2003 at 23:32, matt matt wrote:
> Regarding step 2. below, what if there is a three way tie like this:
>    winner loser     strength
>    D      C               20
>    B      D               20
>    C      B               17
>    A      C               17
>    A      D               17
>    B      A               14
> There is a cycle among the three losers BCD: C>B, B>D, and D>C.    
> Under this scenario your procedure appears to be non-deterministic.

I assume Matt meant "not well-defined" rather than "non-
deterministic." (Since the tiebreak ranking in MAM is generated by 
the Random Voter Hierarchy procedure, of course it is not 
deterministic.  No voting procedure that satisfies anonymity and 
neutrality can be deterministic.  For instance, suppose there are two 
alternatives and an even number of voters who split 50-50.  Any 
anonymous neutral voting method must use randomness to pick the 
winner.)  

The cycle Matt noted above is irrelevant in determining how MAM 
orders the majorities.  The alternatives do not cycle in the tiebreak 
ranking T.

MAM's tiebreak ranking of the majorities is a well-defined strict 
ordering.  My web site includes a proof at the following address 
(which is actually one line but is word-wrapped here):  

   www.alumni.caltech.edu/~seppley/Theorems%20used
   %20in%20proofs%20about%20MAM.htm
   #Theorem%20"Precedence%20is%20a%20Strict%20Ordering"

(To understand the notation in the proof, you'll also need to look at 
the "formal definition of MAM" which is linked at the following 
address:  www.alumni.caltech.edu/~seppley)

In Matt's example, he doesn't specify T, the tiebreak ranking of the 
alternatives, which is a strict ordering of the alternatives that MAM 
generates using the Random Voter Hierarchy procedure.  Since T is a 
strict ordering, there cannot be a cycle of alternatives in T.  Thus, 
it follows by condition 3 (below) that MAM orders one of the three 
majorities having size 17 over the other two, etc.  For example, 
suppose T ranks B over C and C over D.  Since T ranks B over D, by 
condition 3 MAM ranks the "A over D" majority over the "C over B" 
majority.  Since T ranks C over D, by condition 3 MAM ranks the "A 
over D" majority over the "A over C" majority.  Since T ranks B over 
C, by condition 3 MAM ranks the "A over C" majority over the "C over 
B" majority.  Combining the last three statements, MAM orders the "A 
over D" majority over the "A over C" majority and the "A over C" 
majority over the "C over B" majority.

> Steve Eppley wrote: 
>> 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