[EM] hey Markus, can you confirm something?...

[Juho]

On Feb 6, 2010, at 5:34 AM, robert bristow-johnson wrote:

>
> On Feb 5, 2010, at 10:24 PM, Warren Smith wrote:
>
>> robert bristow-johnson:
>>> In a Condorcet election in which a cycle occurs, if there are only  
>>> three
>>> candidates in the Smith set, or even if there are more but the  
>>> defeat
>>> path is a simple single loop, is the outcome of the election any
>>> different if decided by Schulze rules than if decided by Tideman  
>>> ruules
>>> (Ranked Pairs)?
>>>
>>> Of course, this question is open for anyone to answer.
>>
>> Kristofer Munsterhjelm:
>> AFAIK, if there are three candidates in a cycle, RP and Schulze  
>> returns
>> the same: they break the cycle by its weakest defeat. This is obvious
>> for RP, because the weakest defeat (least victory) gets sorted  
>> last. For
>> Schulze, consider the Schwartz set implementation (CSSD) as  
>> described on
>> http://en.wikipedia.org/wiki/Schulze_method#The_Schwartz_set_heuristic 
>>  .
>> Since there's a cycle and all three candidates are involved in it,  
>> steps
>> one and two can't be done, so 3 is done, which also discards the  
>> weakest
>> defeat.
>>
>> Warren D Smith:
>> To complete KM's answer, the case where
>> "there are more [than three in the Smith set]
>> but the defeat  path is a simple single loop"
>> does not exist.
>
> that, i didn't expect.
>
>>  That is because if there is a directed N-cycle
>> for some N>3, you can always "draw a chord" in the "circle"
>
> <smacking forehead>
>
>> and no matter which way the arrow on that chord points, the result  
>> is always
>> at least one shorter directed cycle, i.e. with smaller N.    
>> Consequently, no
>> matter what the value of N>3, there is always a 3-cycle.
>
> so everyone in the smith set is related to everyone else via a 3- 
> cycle?  or is that also not general?

In a 4 member Smith set we can without loss of generality assume that  
there is a 4-cycle A>B>C>D>A and that the remaining "chords" are A>C  
and B>D. This means that B and C are not part of any 3-cycle. All 4  
member Smith sets are thus isomorphic, and a 4 member Smith set always  
has exactly two members that are not connected to each others with a 3- 
cycle.

Here are some more general results. A Smith set (n>=3) may have two  
members that are not both part of any of its 3-cycles. A n member  
Smith set may have all pairs of its members connected to to each  
others via some of its 3-cycles if n>=5. For all m, 3 <= m <= n, all  
members of a n member Smith set are part of a m-cycle. For all m, 4 <=  
m <= n, any two members of a n member Smith set are both part of one  
of the m-cycles.

(All this is based on the assumption that there are no pairwise ties.  
I hope I got the equations otherwise right.)

Juho


>
>> So... do Schulze & Ranked Pairs always return the same winner? No.
>> If the Smith set has 3 or fewer members? Yes.
>
>
> i suspected these two answers but don't mind getting misconceptions  
> enlightened.
>
> thanks, Warren.
>
> --
>
> r b-j                  rbj at audioimagination.com
>
> "Imagination is more important than knowledge."
>
>
>
>
> ----
> Election-Methods mailing list - see http://electorama.com/em for  
> list info