[EM] RE: [Condorcet] Why Schulze is Better than DMC

Simmons, Forest simmonfo at up.edu
Tue Sep 13 17:20:22 PDT 2005

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.)
What I am referring to is the logical complexity of the concepts involved.
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.
In other words, the eliminations in Shulze are intrinsically harder to understand than the eliminations in DMC.
Also cycles are objects of higher logical type that don't have to be dealt with mentally in order to understand DMC.
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.
When I refer to "types" I am speaking of the following.
Sets of candidates, sets of voters, and other basic sets relevant to elections are of type 1.
Those objects that can be modeled as sets of subsets of type 1 are of type 2.
Those objects that can be modeled as sets of subsets of type n are of type (n+1).
DMC beats Shulze decisively from this point of view.


From: Condorcet at yahoogroups.com on behalf of Jobst Heitzig
Sent: Tue 9/13/2005 1:38 PM
To: Condorcet at yahoogroups.com
Subject: Re: [Condorcet] Why Schulze is Better than DMC

Dear Jeff!

You wrote:
> [Jobst, the fact that *you* think DMC simple and CSSD more complex does not make it so. -- JRF]

I was talking about the tallying process there.

[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]

It is not a matter of
opinion whether DMC or CSSD is easier to tally. To the contrary, there
are well-established mathematical measures of complexity which show
quite clearly that it is easier to determine the DMC winner than the
CSSD winner: DMC's order of complexity is n^2, CSSD's is n^3, where n is
the number of candidates. This means that when doubling the number of
candidates, the time to apply DMC will approximately be multiplied by
four, while the time to apply CSSD will approximately be multiplied by
eight. Another measure of complexity is how many words you need to
explain the algorithm. It has been pointed out over and over by various
experts here that also from this point of view DMC is easier.

Of course, there are also other *kinds* of simplicity, other than the
tallying simplicity. For example, the question is different when we ask
how easy it is to *vote* rather than how easy it is to tally:

Those versions of DMC which use an explicit approval cutoff ask the
voter for more information and can thus be considered more complex. But
this amounts to say that giving voters more freedom of expression is
making voting more complicated. If we don't like this, we should perhaps
propose Approval Voting and no rankings based method at all, since the
difference in ballot complexity between an approval-only ballot and a
rank-only ballot is larger than that between a rank-only ballot and a
rank-ballot with optional approval cutoff.

Those versions of DMC which use a standard ranked ballot (with implicit
approval) are no more complex to vote than CSSD from the point of view
of ballot complexity.

But voting complexity can also be measured by how complex it is to find
suitable strategies. Here the situation is even more debatable, it
seems: Finding a suitable strategy involves understanding the tallying
process, hence it seems that the simpler tallying process of DMC should
make it somewhat easier to find good strategies in DMC. This is most
obvious from the fact that in the most probable situation where there is
a sincere Condorcet Winner, say X, the obvious strategy to guarantee the
sincere outcome in DMC is to approve X and everyone I prefer to X. It
can immediately be seen that in this way no faction which prefers some
other candidate, say Y, to X can change the fact that X defeats Y
doubly. In CSSD, it is not so obvious what we can do to guarantee that
the sincere Condorcet Winner actually wins without voting an insincere
ranking, is it?

Also, the information I need in order to anticipate the CSSD winner in
case of a cycle seems to be more precise than the information I need to
anticipate the DMC winner. For DMC, I would need to have reliable
polling information about what the likely directions of the defeats are
and what the likely approval order is. For CSSD, on the other hand, I
not only need to know the direction of the defeats but also need
reliable polling information about the *strengths* of these defeats. It
seems more problematic to me to anticipate which defeat is weakest than
to anticipate which candidate is least approved.

In all, the only aspect in which CSSD seems simpler than DMC with
explicit approval seems to be the ballot. And I did not read a single
reason why DMC with *implicit* approval could be considered more complex
than CSSD.

Yours, Jobst

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20050913/5d0b0181/attachment-0002.htm>

More information about the Election-Methods mailing list