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 [email protected]
"Imagination is more important than knowledge."
----
Election-Methods mailing list - see http://electorama.com/em for
list info
----
Election-Methods mailing list - see http://electorama.com/em for list info
