[EM] Schulze and Margins was: Reversal Software output6/9/1999

[Blake Cretney]

Dear Markus,
> Dear Blake,
> 
> you wrote (13 Jun 1999):
> > Markus Schulze wrote:
> > > Blake wrote (10 Jun 1999):
> > > > > "Marg" is the Condorcet(Margins) variation.
> > > >
> > > > Calling this method Condorcet seems to be an error started on this
> > > > list.  I'm going to refer to Minmax to refer to the same method since
> > > > this term is used in academic journals.  I use Minmax(Margins) to
> > > > refer to the Marginal variant.
> > > 
> > > I agree with you. There are lots of different interpretations of
> > > Condorcet's wordings. And that interpretation that is used in this
> > > list doesn't seem to be a justifiable one.
> >
> > You once emailed me a quote on Condorcet's musings on extending his
> > method to more than three candidates.  You might post that to EM, as I
> > consider it decisive on this matter.
> 
> Condorcet writes (on page LXVIII of the preface of his "Essai sur
> l'application de l'analyse a la probabilite des decisions rendues a la
> pluralite des voix"): "From the considerations, we have just made, we
> get the general rule, that in all those situations, in which we have to
> choose, we have to take successively all those propositions that have
> a plurality, beginning with those that have the largest, & to pronounce
> the result, that is created by those first propositions, as soon as they
> create one, without considering the following less probable propositions."
> 
> On page 126 of the Essai, he writes: "Create an opinion of those n*(n-1)/2
> propositions, which win most of the votes. If this opinion is one of the
> n*(n-1)*...*2 possible, then consider as elected that subject, with which
> this opinion agrees with its preference. If this opinion is one of the
> (2^(n*(n-1)/2))-n*(n-1)*...*2 impossible opinions, then eliminate of this
> impossible opinion successively those propositions, that have a smaller
> plurality, & accept the resulting opinion of the remaining propositions."

It looks like he describes two procedures

1.  Introduce the greatest pair-wise victories one by one until
ambiguity is removed, and a winner is declared.
OR
2.  Drop the lowest pair-wise victories until there is no more
conflict.  Then declare a winner.

Condorcet only experimented with 3-candidate examples.  In these, you
can always resolve a contradiction by drawing a line between the top
two majorities, which unambiguously declare a winner, and the bottom
one which introduces a conflict.  He seems to have assumed that you
could do this with an example of any size, drawing a line between the
top victories, which would unambiguously declare a winner, and the
bottom ones, which would introduce conflict.  Under this assumption,
his two procedures would both work, and come to the same result.  In
reality, his assumption is incorrect and these procedures do not work.
 They do not describe any existing method.

Since Condorcet didn't provide any examples of this extrapolation, or
any particular justification for it, and since the procedures he
describe cannot be used as methods, I have to conclude that he didn't
seriously consider this issue.  He just mused on how his principles
for the situation he did seriously consider, three candidates, might
be extended for more than three.

I would prefer to reserve the name "Condorcet's Method", for the
method that selects the Condorcet winner, and gives no conclusion when
there is none.  This is the way the term has traditionally been used.

> You wrote (13 Jun 1999):
> > Markus Schulze wrote:
> > > Blake wrote (10 Jun 1999):
> > > > 1.  Why is it useful to have truncation resistance, if anyone who
> > > > would leave candidates unranked can avoid the punishment by simply
> > > > randomly ranking those candidates?  This seems like something
intended
> > > > to trap the gullible.
> > > 
--snip--
> > > It has already been discussed that randomly ranking the otherwise
> > > unranked candidates is a useful strategy only if the winner of the
> > > elections is always that candidate whose highest number of votes
> > > against in any pairwise comparison (= win or defeat) is the smallest.
> >
> > what I call Minmax.
> >
> > > But for every other election method that uses votes-against instead of
> > > margins this is not a useful strategy.
> >
> > It has been discussed, but we obviously came away from that
> > discussion with different conclusions.  This is unfortunate, since
> > this should be a provable point.  Perhaps a computer model would be
> > useful.
> >
> > In fact, I think a strong argument can be made without the computer. 
> > Tell me if any of the following statements are incorrect.
> >
> > 1.  In Minmax, this is a useful strategy for elections involving 3
> > candidates. (or more in fact)
> > 2.  Schulze is equivalent to Minmax for 3 or fewer candidates.
> > 3.  My statement holds true for Schulze elections involving 3
> > candidates.  Obviously incomplete rankings have no effect for two or
> > one candidates.
> >
> > Now, as more candidates are added, more situations arise where
> > random-filling can backfire.  I believe that what you are alluding to
> > is the possibility that with a long chain
> >
> > A>B>C>D>E
> >
> > in this case, a group of voters whose true preference is
> > E A
> > and who choose to randomly rank B C D, may hurt E by unintentionally
> > strengthening a path that works against it.  Unless I have
> > misunderstood you, it is your argument that this possibility makes it
> > impossible to say that random-filling is a useful strategy (unless of
> > course information is known to avoid this scenario).
> >
> > However, the problem is that there is no more reason to believe that
> > the effect on extended paths will help than hurt.  That is, for the
> > middle of extended paths the effect is on average neutral.
> >
> > However, we know from the three candidate examples that the effect on
> > short paths is not neutral, it is in favour of random-filling. 
> > Putting these two together, I conclude that even in Schulze,
> > random-filling is the best strategy in the absence of other
> > information.
> 
> Your argumentation is strange. It seems to me that you assume that
> if a given voter has absolutely no informations about the opinions and
> the voting behaviour of the other voters this voter will (to calculate
> his optimal strategy) assume that the opinions of the other voters
> are distributed randomly and that the other voters don't use any
> strategy.

If I assume they are distributed randomly, it doesn't matter whether
this is the result of strategy or not, so the second assumption is not
an issue.  You're right though, that I have been basing optimal
strategy in the absence of information on the assumption of random
distribution.  If you don't agree that this is correct, then what
would you describe as the optimal strategy with no information about
how others are voting.  It seems absurd to say that there is no
optimal strategy, or that any vote is equally likely to benefit the
voter.

There are some assumptions a voter could make based on how elections
tend to play out, for example
1.  A greater tendency towards near-clones than would be the result
of chance.  This occurs because most elections have some partisan
influence, even if they don't have actual "parties".
2.  Pair-wise votes will tend to be more lop-sided than would be
expected due to chance.
3.  Condorcet winners will be more likely than purely by chance.

For realistic elections, a voter might find better strategy by
assuming these three tendencies than by assuming pure randomness, even
if the voter has no information specific to the particular election. 
But I don't see how any of these three tendencies would affect the
usefulness of random-filling.

So, the obvious question is, is there some tendency that is true of
elections in general, and that makes random-filling a poor or neutral
strategy?  I can't think of any such tendency.  Have you something
like this in mind?

--snip--
> > > Voters don't tend to use order-reversal. But they tend to truncate
> > > if they have to fear that an additional ranking could hurt their
> > > already ranked candidates.
> >
> > Are you saying that voters will truncate if an additional ranking
> > merely "could" hurt, or will they truncate only if it on average does
> > hurt?
> 
> I don't understand what you mean. As Schulze meets the Condorcet
> Criterion, you know the answer to your above question.

IRV advocates often state, correctly, that in a given Condorcet
method (both Margins and VA), additional rankings CAN hurt one's
favourite.  There is a tendency to over-interpret statements of this
form, so a reader of this statement might think that it implies that
additional rankings will in general hurt your favourite, and that it
is therefore good strategy to only rank one candidate.  This is,
however, not what it means, and truncation is not in general a good
strategy.  

I hope that the statement "[voters] tend to truncate if they have to
fear an additional ranking could hurt their already ranked
candidates," does not accurately reflect your views.  After all,
additional ranking "could" hurt your favourite, even in Schulze.  The
point is that this is not a general tendency.

> You wrote (13 Jun 1999):
> > > The aim of the use of votes-against instead of margins is to
> > > minimize the probability that a voter could be punished for making
> > > an additional ranking.
> >
> > It certainly does reduce that possibility, but goes to the extreme
> > that leaving candidates unranked on average hurts your favourite. 
> > Your statement above suggests that you do not believe this to be the
> > case with Schulze.  If you were convinced otherwise, might this alter
> > your stand on this issue?
> 
> Isn't this strategical problem of MinMax(VA)
> caused by its violation of Reversal Symmetry?

I don't understand the connection.  IRV doesn't have Reversal
Symmetry, but truncation is clearly neutral.  You'll have to explain
why you think these two properties are related.

> You wrote (13 Jun 1999):
> > > You wrote (10 Jun 1999):
> > > > VA seems like a very strange method to me, an attempt by Mike
> > > > Ossipoff to combine Approval and Concorcet.  In other methods, a
> > > > sincere vote is the best (or at least equal to the best) vote when no
> > > > strategic information is known, and then as knowledge is picked up,
> > > > strategic possibilities result.  The winning-votes-only methods are
> > > > unique in that a sincere vote isn't always the best vote even when NO
> > > > information is known.
> > > 
> > > It is not true that Ossipoff's VA is the unique election method
> > > for which a sincere vote isn't always the best vote even when no
> > > information is known. The problem is that other people don't
> > > discuss the problem of equal rankings.
> > > 
> > > Example 1: If IRO is used then it is a useful strategy to give
> > > different rankings to your most favorite candidates even if you
> > > like them equally.
> > > 
> > > Example 2: If "first past the post" is used then it is a useful
> > > strategy to vote for only one candidate even if you don't have
> > > a unique favorite candidate.
> >
> > I see a few important differences between these examples and VA.  One
> > is that these methods are open and explicit about the rules.  It is
> > obvious to everyone participating in a plurality election that you are
> > expected to choose a single candidate, and that your vote will be
> > thrown out otherwise.  VA allows people to make votes which I contend
> > are obviously unjustifiable, but does not give the warning that an
> > outright ban does.
> >
> > More importantly, perhaps, is how the analysis of these methods
> > progresses.  When analyzing the Australian method, one would assume
> > that voters will complete their ballots regardless of whether they
> > sincerely have a complete ranking.  I think it is perfectly reasonable
> > to call any of these rankings "sincere" in the sense that it is as
> > sincere as the method allows.  In VA, however, it is often assumed
> > that people will vote partial rankings, and these partial rankings are
> > labeled as being sincere.
> >
> > I guess I might have to amend my statement to say that the
> > winning-votes-only methods are unique in that a vote which is sincere,
> > and not actually a spoiled ballot, is not the best strategic vote,
> > even with no information.  This "uniqueness" is a pretty esoteric
> > point though, and not really central to my argument.
> 
> I don't agree with you. You are actually saying that it is allowed
> to declare all those ballots that don't rank all candidates invalid
> but it is not allowed to try to encourage rather than to deter the
> voters from ranking the candidates.

It's more up-front.  This spoiled ballot rule is in effect a warning
that voters should provide full rankings whether or not they have
them.  Of course, we could provide the same warning to voters in a VA
election, but this would tend to defeat the purpose of VA, which, it
seems to me, is at least to some extent to try to trick truncaters
into reducing the power of their votes.

> On the one side, you write: "I think it is perfectly reasonable to call
> any of these rankings 'sincere' in the sense that it is as sincere as the
> method (=IRO, FPTP,...) allows." On the other side, you don't say:
> "I think it is perfectly reasonable to call a voter who uses
> random-filling 'sincere' in the sense that he is as sincere as the
> method (=VA) encourages."

That's a good point.  The problem is, that there is no agreed upon
principle by which the "sincere" vote can be decided for any election.
 One possibility is to define a sincere vote for each kind of ballot. 
>From this point of view, a ballot that allows unranked candidates
would have a different definition of sincerity than one that didn't. 
Based on this definition, my conclusion stands.

Another view would be to define the sincere vote as the vote that is
most likely to get the desired outcome when no information is known
(the vote the method encourages).  From this point of view, all
methods will by definition have (optimal strategy)=(sincere vote),
when no information is known.  So, in VA, random filling would be
sincere, and leaving candidates unranked would not be.  Of course,
this is means VA gets a very different definition of a sincere vote
than one would expect.  I don't think VA looks better from this
perspective.

---
Blake Cretney
See the EM Resource:  http://www.fortunecity.com/meltingpot/harrow/124
My Path voting Site:  http://www.fortunecity.com/meltingpot/harrow/124/path