On Feb 6, 2010, at 3:28 PM, Juho wrote:
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.
This last sentence is unfortunately not true. Circular connection
between any two Smith set members can be guaranteed only for the full
n-cycle.
Juho
(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
----
Election-Methods mailing list - see http://electorama.com/em for list info
