<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7226.0">
<TITLE>Re: [Condorcet] Why Schulze is Better than DMC</TITLE>
</HEAD>
<BODY>
<DIV id=idOWAReplyText39980 dir=ltr>
<DIV dir=ltr><FONT face=Arial color=#000000 size=2>There are other
objective measures of complexity besides the ones mentioned by Jobst. (He
mentioned computational complexity from the point of view of the smallest
accurate description of the method or algorithm, as well as the minimal running
time of the algorithm on a fixed universal turing machine.)</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>What I am referring to is the logical
complexity of the concepts involved.</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>For example, "eliminating" a defeat, versus
eliminating a candidate. The set of candidates is one thing, while the set
of defeats is a subset of the set of ordered pairs of candidates, an object of
higher logical type, i.e. an abstraction that is harder to think
about.</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>In other words, the eliminations in Shulze
are intrinsically harder to understand than the eliminations in
DMC.</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>Also cycles are objects of higher logical
type that don't have to be dealt with mentally in order to understand
DMC.</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>The concept of defeat strength, another
higher type object, is not needed for DMC, although it has been introduced
for purposes of comparison with other methods.</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>When I refer to "types" I am speaking of
the following.</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>Sets of candidates, sets of voters, and
other basic sets relevant to elections are of type 1.</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>Those objects that can be modeled as sets
of subsets of type 1 are of type 2.</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>Those objects that can be modeled as sets
of subsets of type n are of type (n+1).</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>DMC beats Shulze decisively from this point
of view.</FONT></DIV>
<DIV dir=ltr><FONT face=Arial size=2></FONT> </DIV>
<DIV dir=ltr><FONT face=Arial size=2>Forest</FONT></DIV></DIV>
<DIV dir=ltr><BR>
<HR tabIndex=-1>
<FONT face=Tahoma size=2><B>From:</B> Condorcet@yahoogroups.com on behalf of
Jobst Heitzig<BR><B>Sent:</B> Tue 9/13/2005 1:38 PM<BR><B>To:</B>
Condorcet@yahoogroups.com<BR><B>Subject:</B> Re: [Condorcet] Why Schulze is
Better than DMC<BR></FONT><BR></DIV>
<DIV>
<P><FONT size=2>Dear Jeff!<BR><BR>You wrote:<BR>> [Jobst, the fact that *you*
think DMC simple and CSSD more complex does not make it so. -- JRF]<BR><BR>I was
talking about the tallying process there.<BR><BR>[That was not clear from the
context, which implied that DMC would be easier to explain, not easier for a
computer's CPU to calculate. Since CPU cycles are cheap, I for one do not care
about the simplicity that you go on to explain. BTW, we covered this ground
before, so let's please drop it here. -- JRF]<BR><BR>It is not a matter
of<BR>opinion whether DMC or CSSD is easier to tally. To the contrary,
there<BR>are well-established mathematical measures of complexity which
show<BR>quite clearly that it is easier to determine the DMC winner than
the<BR>CSSD winner: DMC's order of complexity is n^2, CSSD's is n^3, where n
is<BR>the number of candidates. This means that when doubling the number
of<BR>candidates, the time to apply DMC will approximately be multiplied
by<BR>four, while the time to apply CSSD will approximately be multiplied
by<BR>eight. Another measure of complexity is how many words you need
to<BR>explain the algorithm. It has been pointed out over and over by
various<BR>experts here that also from this point of view DMC is
easier.<BR><BR><BR>Of course, there are also other *kinds* of simplicity, other
than the<BR>tallying simplicity. For example, the question is different when we
ask<BR>how easy it is to *vote* rather than how easy it is to
tally:<BR><BR>Those versions of DMC which use an explicit approval cutoff ask
the<BR>voter for more information and can thus be considered more complex.
But<BR>this amounts to say that giving voters more freedom of expression
is<BR>making voting more complicated. If we don't like this, we should
perhaps<BR>propose Approval Voting and no rankings based method at all, since
the<BR>difference in ballot complexity between an approval-only ballot and
a<BR>rank-only ballot is larger than that between a rank-only ballot and
a<BR>rank-ballot with optional approval cutoff.<BR><BR>Those versions of DMC
which use a standard ranked ballot (with implicit<BR>approval) are no more
complex to vote than CSSD from the point of view<BR>of ballot
complexity.<BR><BR>But voting complexity can also be measured by how complex it
is to find<BR>suitable strategies. Here the situation is even more debatable,
it<BR>seems: Finding a suitable strategy involves understanding the
tallying<BR>process, hence it seems that the simpler tallying process of DMC
should<BR>make it somewhat easier to find good strategies in DMC. This is
most<BR>obvious from the fact that in the most probable situation where there
is<BR>a sincere Condorcet Winner, say X, the obvious strategy to guarantee
the<BR>sincere outcome in DMC is to approve X and everyone I prefer to X.
It<BR>can immediately be seen that in this way no faction which prefers
some<BR>other candidate, say Y, to X can change the fact that X defeats
Y<BR>doubly. In CSSD, it is not so obvious what we can do to guarantee
that<BR>the sincere Condorcet Winner actually wins without voting an
insincere<BR>ranking, is it?<BR><BR>Also, the information I need in order to
anticipate the CSSD winner in<BR>case of a cycle seems to be more precise than
the information I need to<BR>anticipate the DMC winner. For DMC, I would need to
have reliable<BR>polling information about what the likely directions of the
defeats are<BR>and what the likely approval order is. For CSSD, on the other
hand, I<BR>not only need to know the direction of the defeats but also
need<BR>reliable polling information about the *strengths* of these defeats.
It<BR>seems more problematic to me to anticipate which defeat is weakest
than<BR>to anticipate which candidate is least approved.<BR><BR>In all, the only
aspect in which CSSD seems simpler than DMC with<BR>explicit approval seems to
be the ballot. And I did not read a single<BR>reason why DMC with *implicit*
approval could be considered more complex<BR>than CSSD.<BR><BR><BR>Yours,
Jobst<BR><BR></FONT></P></DIV>
</BODY>
</HTML>