[EM] Condorcet methods - should the cycle order always determine the result order? (Toby Pereira)

[Forest Simmons]

Toby,

You mentioned Kemeny. The very purpose of Kemeny is to determine a "social
order," namely the one that minimizes the average "distance" from that
order to the ballot orders..

The trouble with Kemeny is that the choice of metric for the "distance:" is
clone dependent: changing the size of a clone set changes the number of
transpositions of order to move a candidate past that set.

However, if cardinal ratings (e.g. score ballots) are used, then clone
independent metrics can be substituted for the Kemeny distance. I once
posted a message to this list describing a clone free technique for
converting a set of ordinal ballots into a set of ratings Then based on
those ratings it was possible to define "Kemeny Done Right," Dodgson Done
Right," and "Borda Done Right." Of these three "done right" methods, only
the latter fails the Condorcet Criterion.

Forest

[Kristofer Munsterhjelm]

Post by Forest Simmons
Toby,
You mentioned Kemeny. The very purpose of Kemeny is to determine a
"social order," namely the one that minimizes the average "distance"
from that order to the ballot orders..
The trouble with Kemeny is that the choice of metric for the "distance:"
is clone dependent: changing the size of a clone set changes the number
of transpositions of order to move a candidate past that set.

If you change "sum" (or average) to leximax, then that problem goes away
and you get Ranked Pairs, right?

Can River also be formulated as an optimization problem?

Post by Forest Simmons
However, if cardinal ratings (e.g. score ballots) are used, then clone
independent metrics can be substituted for the Kemeny distance. I once
posted a message to this list describing a clone free technique for
converting a set of ordinal ballots into a set of ratings Then based on
those ratings it was possible to define "Kemeny Done Right," Dodgson
Done Right," and "Borda Done Right." Of these three "done right"
methods, only the latter fails the Condorcet Criterion.

Does altering Kemeny in this way fix its vulnerability to cloning? I'd
imagine that any way of turning rankings into ratings would make the
ratings depend on the candidates in some way; otherwise, you could bolt
that onto, say, Range, and get a deterministic ranked method that passes
IIA (which we know is impossible).
----
Election-Methods mailing list - see http://electorama.com/em for list info

[Toby Pereira]

Kemeny certainly wouldn't be my preferred choice, partly because of its lack of clone independence, but I mentioned it because it seems to come up frequently enough.

I think I remember seeing before your "done right" post. I'll have to read it again, because I remember considering the possibility of a cloneproof Borda before and deciding that any attempt to cloneproof it would leave it unrecognisable from Borda. For example, if you have the following ballots:

10: A>B>C>D>E
10: B>C>D>E>A

Using Borda philosophy, B is the best here, but from the perspective of A, BCDE form a clone group, so any cloneproof system would have to consider A equal to each other candidate.

I think cloneproof Condorcet systems wouldn't have a set order here. While they would rank B>C>D>E, there would be no specific place for A to go. And I think this is why (as people have said), Condorcet methods don't necessarily have a complete fixed order. For example, even though B beats C and A is equal to C, it is not the case that B beats A.

But back to Borda - if the cloneproof version of Borda uses scores (as normal Borda does), then I can't see a set of scores that would make sense here. We can have scores so that B>C>D>E. But any score for A doesn't work. Because A has to be equal to all of them!

But this also makes me wonder generally - are there any sensible cloneproof ranked-ballot systems that aren't Condorcet methods? IRV is cloneproof, but is it sensible? Is there anything else?

________________________________
Sent: Tuesday, 4 November 2014, 22:46
Subject: [EM] Condorcet methods - should the cycle order always determine the result order? (Toby Pereira)
Toby,
You mentioned Kemeny. The very purpose of Kemeny is to determine a "social order," namely the one that minimizes the average "distance" from that order to the ballot orders..
The trouble with Kemeny is that the choice of metric for the "distance:" is clone dependent: changing the size of a clone set changes the number of transpositions of order to move a candidate past that set.
However, if cardinal ratings (e.g. score ballots) are used, then clone independent metrics can be substituted for the Kemeny distance. I once posted a message to this list describing a clone free technique for converting a set of ordinal ballots into a set of ratings Then based on those ratings it was possible to define "Kemeny Done Right," Dodgson Done Right," and "Borda Done Right." Of these three "done right" methods, only the latter fails the Condorcet Criterion.
Forest
----
Election-Methods mailing list - see http://electorama.com/emfor list info

[Kristofer Munsterhjelm]

Post by Toby Pereira
But this also makes me wonder generally - are there any sensible
cloneproof ranked-ballot systems that aren't Condorcet methods? IRV is
cloneproof, but is it sensible? Is there anything else?

Perhaps one of the descending coalitions family? DAC, DSC or HDSC.
They're cloneproof, but to determine whether they're sensible, you'd
probably need a more exact definition of what "sensible" means. They're
a lot closer to Plurality than Condorcet is.
----
Election-Methods mailing list - see http://electorama.com/em for list info

[Kevin Venzke]

Hi,
________________________________

Envoyé le : Mercredi 5 novembre 2014 15h29
Objet : Re: [EM] Condorcet methods - should the cycle order always determine the result order? (Toby Pereira)

Post by Toby Pereira
But this also makes me wonder generally - are there any sensible
cloneproof ranked-ballot systems that aren't Condorcet methods? IRV is
cloneproof, but is it sensible? Is there anything else?

Perhaps one of the descending coalitions family? DAC, DSC or HDSC.
They're cloneproof, but to determine whether they're sensible, you'd
probably need a more exact definition of what "sensible" means. They're
a lot closer to Plurality than Condorcet is.

Yes, I think those are probably the most fitting suggestions even if they're not that
great. I plotted methods based on similarity some time ago:
http://permalink.gmane.org/gmane.politics.election-methods/18829

........................Bucklin.............................
............................................................
............................................................
..............................DAC...........................
...................WV.......................................
............................................................
............................BklnVar.........................
..............C//KH.........................................
............................................................
.............KH.............................................
.................C//IRV.....................................
.......................QR...................................
...................................DSC......................
..................IRV.......................................
.......................................FPP..................

Methods on the east side (DAC/DSC) don't seem to get invented very often. You probably
won't get much more unusual than these without failing the Plurality criterion.

My own basic principle for sensibility is that the winner of the election should be
one of those candidates who might be the winner if the electorate had been an assembly,
capable of surveying how many voters were available to vote in any given way, and
adjusting votes based on which outcomes might actually be achieved. I think of other
candidates (i.e. those who could not plausibly have won in an assembly setting) as
"unrealistic" winners.

I think that this principle almost implies Condorcet (some worthwhile edge cases might
exist I think), and I think it implies clone-winner and clone-loser to the extent that
the failures of these criteria are tolerable.

Total clone independence is too expensive for me to insist on, and in itself doesn't
even reassure me that there won't be "clone-like" issues. The definition of "clone"
is very strict.

Kevin

----
Election-Methods mailing list - see http://electorama.com/em for list info

[C.Benham]

Kevin,

"I think that this principle almost implies Condorcet (some worthwhile edge cases might
exist I think), and I think it implies clone-winner and clone-loser to the extent that
the failures of these criteria are tolerable.
Total clone independence is too expensive for me to insist on,..."

Can you can clarify your phrase "to the extent that the failures of
these criteria are tolerable"?

What is it that we have to give up for "total clone independence" that
in your view makes it "too expensive"?

Chris Benham

Hi,
________________________________

Envoyé le : Mercredi 5 novembre 2014 15h29
Objet : Re: [EM] Condorcet methods - should the cycle order always determine the result order? (Toby Pereira)

Post by Toby Pereira
But this also makes me wonder generally - are there any sensible
cloneproof ranked-ballot systems that aren't Condorcet methods? IRV is
cloneproof, but is it sensible? Is there anything else?

Perhaps one of the descending coalitions family? DAC, DSC or HDSC.
They're cloneproof, but to determine whether they're sensible, you'd
probably need a more exact definition of what "sensible" means. They're
a lot closer to Plurality than Condorcet is.

Yes, I think those are probably the most fitting suggestions even if they're not that
http://permalink.gmane.org/gmane.politics.election-methods/18829
........................Bucklin.............................
............................................................
............................................................
..............................DAC...........................
...................WV.......................................
............................................................
............................BklnVar.........................
..............C//KH.........................................
............................................................
.............KH.............................................
.................C//IRV.....................................
.......................QR...................................
...................................DSC......................
..................IRV.......................................
.......................................FPP..................
Methods on the east side (DAC/DSC) don't seem to get invented very often. You probably
won't get much more unusual than these without failing the Plurality criterion.
My own basic principle for sensibility is that the winner of the election should be
one of those candidates who might be the winner if the electorate had been an assembly,
capable of surveying how many voters were available to vote in any given way, and
adjusting votes based on which outcomes might actually be achieved. I think of other
candidates (i.e. those who could not plausibly have won in an assembly setting) as
"unrealistic" winners.
I think that this principle almost implies Condorcet (some worthwhile edge cases might
exist I think), and I think it implies clone-winner and clone-loser to the extent that
the failures of these criteria are tolerable.
Total clone independence is too expensive for me to insist on, and in itself doesn't
even reassure me that there won't be "clone-like" issues. The definition of "clone"
is very strict.
Kevin
----
Election-Methods mailing list - see http://electorama.com/em for list info

----
Election-Methods mailing list - see http://electorama.com/em for list info

[Kevin Venzke]

Hi Chris,

"to the extent that the failures of these criteria are tolerable" means that certain extreme
candidate cloning issues shouldn't ultimately be problems in an assembly environment.
If a majority party has three candidates (and the members of this party support those candidates
to the extent that they would be willing to rank them together on a ballot) it should never
happen that the majority loses a vote (???) to a minority proposal. This does not mean that the
outcome was actually independent of the clones, just that a bizarre outcome should not result
from them.

And on the other side, a minority party can't possibly prevail in an assembly environment just
by making a large number of similar proposals.

The low value (that I perceive) of "total" clone independence is not just in the cost but in
what it actually gets you. That is, you only need one vote that denies that two candidates are
clones, and suddenly clone independence guarantees no longer apply to this scenario. (Most
serious clone-proof methods will still behave well, but it's trivial to define a method where
the usefulness of clone independence breaks down quickly given some noise. Like DSC, even.)

To me the cost is mostly simplicity, but also sometimes other criteria. I like C//A, which is
very simple but fails clone-winner. That doesn't really bother me. There's also ICA, which is
not so simple, but satisfies FBC. Clone-proof methods that satisfy FBC can't do much with
pairwise comparisons.

Kevin



----- Mail original -----
De : C.Benham <***@adam.com.au>
À : election-***@lists.electorama.com
Cc :
Envoyé le : Jeudi 6 novembre 2014 8h10
Objet : Re: [EM] Condorcet methods - should the cycle order always determine the result order? (Toby Pereira)

Kevin,

"I think that this principle almost implies Condorcet (some worthwhile edge cases might
exist I think), and I think it implies clone-winner and clone-loser to the extent that
the failures of these criteria are tolerable.
Total clone independence is too expensive for me to insist on,..."

Can you can clarify your phrase "to the extent that the failures of
these criteria are tolerable"?

What is it that we have to give up for "total clone independence" that
in your view makes it "too expensive"?

Chris Benham

Hi,
________________________________

Envoyé le : Mercredi 5 novembre 2014 15h29
Objet : Re: [EM] Condorcet methods - should the cycle order always determine the result order? (Toby Pereira)

Post by Toby Pereira
But this also makes me wonder generally - are there any sensible
cloneproof ranked-ballot systems that aren't Condorcet methods? IRV is
cloneproof, but is it sensible? Is there anything else?

Perhaps one of the descending coalitions family? DAC, DSC or HDSC.
They're cloneproof, but to determine whether they're sensible, you'd
probably need a more exact definition of what "sensible" means. They're
a lot closer to Plurality than Condorcet is.

Yes, I think those are probably the most fitting suggestions even if they're not that
http://permalink.gmane.org/gmane.politics.election-methods/18829
........................Bucklin.............................
............................................................
............................................................
..............................DAC...........................
...................WV.......................................
............................................................
............................BklnVar.........................
..............C//KH.........................................
............................................................
.............KH.............................................
.................C//IRV.....................................
.......................QR...................................
...................................DSC......................
..................IRV.......................................
.......................................FPP..................
Methods on the east side (DAC/DSC) don't seem to get invented very often. You probably
won't get much more unusual than these without failing the Plurality criterion.
My own basic principle for sensibility is that the winner of the election should be
one of those candidates who might be the winner if the electorate had been an assembly,
capable of surveying how many voters were available to vote in any given way, and
adjusting votes based on which outcomes might actually be achieved. I think of other
candidates (i.e. those who could not plausibly have won in an assembly setting) as
"unrealistic" winners.
I think that this principle almost implies Condorcet (some worthwhile edge cases might
exist I think), and I think it implies clone-winner and clone-loser to the extent that
the failures of these criteria are tolerable.
Total clone independence is too expensive for me to insist on, and in itself doesn't
even reassure me that there won't be "clone-like" issues. The definition of "clone"
is very strict.
Kevin
----
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

[Juho Laatu]

One more observation on clones. I think there is a major difference between methods that systematically favour or disfavour groupings with multiple candidates (e.g. Borda where nomination of two candidates instead of one typically changes the results dramatically) and methods that can break the clone criterion in some exceptional situations. For example minmax can handle clones perfectly well if we study only those cases that do not have any loops. If we assume that loops are rare, or that they are weak if they happen to exist, also then there are no significant risks (nor benefits) if some groupings do nominate multiple candidates. I guess it is quite correct to say that in typical elections (where large number of voters make independet decisions) Borda has practical problems with clones, while minmax doesn't (although both formally violate the EM clone criterion). That difference is important when one looks for practical election methods (i.e. not just study theoretical properties of different methos / compliance with various formal criteria).

Juho

Post by Toby Pereira
Kemeny certainly wouldn't be my preferred choice, partly because of its lack of clone independence, but I mentioned it because it seems to come up frequently enough.
10: A>B>C>D>E
10: B>C>D>E>A
Using Borda philosophy, B is the best here, but from the perspective of A, BCDE form a clone group, so any cloneproof system would have to consider A equal to each other candidate.
I think cloneproof Condorcet systems wouldn't have a set order here. While they would rank B>C>D>E, there would be no specific place for A to go. And I think this is why (as people have said), Condorcet methods don't necessarily have a complete fixed order. For example, even though B beats C and A is equal to C, it is not the case that B beats A.
But back to Borda - if the cloneproof version of Borda uses scores (as normal Borda does), then I can't see a set of scores that would make sense here. We can have scores so that B>C>D>E. But any score for A doesn't work. Because A has to be equal to all of them!
But this also makes me wonder generally - are there any sensible cloneproof ranked-ballot systems that aren't Condorcet methods? IRV is cloneproof, but is it sensible? Is there anything else?
Sent: Tuesday, 4 November 2014, 22:46
Subject: [EM] Condorcet methods - should the cycle order always determine the result order? (Toby Pereira)
Toby,
You mentioned Kemeny. The very purpose of Kemeny is to determine a "social order," namely the one that minimizes the average "distance" from that order to the ballot orders..
The trouble with Kemeny is that the choice of metric for the "distance:" is clone dependent: changing the size of a clone set changes the number of transpositions of order to move a candidate past that set.
However, if cardinal ratings (e.g. score ballots) are used, then clone independent metrics can be substituted for the Kemeny distance. I once posted a message to this list describing a clone free technique for converting a set of ordinal ballots into a set of ratings Then based on those ratings it was possible to define "Kemeny Done Right," Dodgson Done Right," and "Borda Done Right." Of these three "done right" methods, only the latter fails the Condorcet Criterion.
Forest
----
Election-Methods mailing list - see http://electorama.com/emfor list info
----
Election-Methods mailing list - see http://electorama.com/em for list info

[Toby Pereira]

Yes, you're right that some methods that fail independence of clones do so far more spectacularly than others. And also what you say about my example where A, B and C might be candidates of the same party but might just happen to be ranked adjacently. But I suppose that's the problem of ranked ballots - that there is no single non-arbitrary method of deciding a winner. And that is one advantage of approval/score. You would get very little disagreement about how to find the winner. That and you get a clear order with an easy-to-digest way of seeing how close it was - total approvals or score (or average score). I do think these things are worth considering in a method. For a Condorcet system, the minimax system has an advantage over most others in that you can put the finishing positions of all the candidates, as well as a meaningful number by them (the number of extra ballots required to make them a winner). Dodgson is the same, so that makes me wonder -
which other Condorcet methods are like this? I almost think it's worth being a named criterion in its own right. Candidate result scorable or something.

________________________________
Sent: Wednesday, 5 November 2014, 22:49
Subject: Re: [EM] Condorcet methods - should the cycle order always determine the result order? (Toby Pereira)
One more observation on clones. I think there is a major difference between methods that systematically favour or disfavour groupings with multiple candidates (e.g. Borda where nomination of two candidates instead of one typically changes the results dramatically) and methods that can break the clone criterion in some exceptional situations. For example minmax can handle clones perfectly well if we study only those cases that do not have any loops. If we assume that loops are rare, or that they are weak if they happen to exist, also then there are no significant risks (nor benefits) if some groupings do nominate multiple candidates. I guess it is quite correct to say that in typical elections (where large number of voters make independet decisions) Borda has practical problems with clones, while minmax doesn't (although both formally violate the EM clone criterion). That difference is important when one looks for practical election methods (i.e. not

just study theoretical properties of different methos / compliance with various formal criteria).

Juho
Kemeny certainly wouldn't be my preferred choice, partly because of its lack of clone independence, but I mentioned it because it seems to come up frequently enough.

Post by Toby Pereira
10: A>B>C>D>E
10: B>C>D>E>A
Using Borda philosophy, B is the best here, but from the perspective of A, BCDE form a clone group, so any cloneproof system would have to consider A equal to each other candidate.
I think cloneproof Condorcet systems wouldn't have a set order here. While they would rank B>C>D>E, there would be no specific place for A to go. And I think this is why (as people have said), Condorcet methods don't necessarily have a complete fixed order. For example, even though B beats C and A is equal to C, it is not the case that B beats A.
But back to Borda - if the cloneproof version of Borda uses scores (as normal Borda does), then I can't see a set of scores that would make sense here. We can have scores so that B>C>D>E. But any score for A doesn't work. Because A has to be equal to all of them!
But this also makes me wonder generally - are there any sensible cloneproof ranked-ballot systems that aren't Condorcet methods? IRV is cloneproof, but is it sensible? Is there anything else?

[Juho Laatu]

Post by Toby Pereira
Yes, you're right that some methods that fail independence of clones do so far more spectacularly than others. And also what you say about my example where A, B and C might be candidates of the same party but might just happen to be ranked adjacently. But I suppose that's the problem of ranked ballots - that there is no single non-arbitrary method of deciding a winner. And that is one advantage of approval/score. You would get very little disagreement about how to find the winner.

I think also other ballot formats, like rated ballots, have some similar problems, i.e. there is no one clear answer to the question what is the ideal way to decide who the winner should be. We could discuss about average score vs. sum of scores, or average score vs. not many low scorings. I agree that it is typically easy to find the agreement in approval/score since the basic summing of the approvals/scores is so obvious first choice.

The problem is also on the real life side in the sense that there are different kind of electons with different needs. Therefore different methods may be ideal (or closest to ideal) for different needs.

Also the strategy questions play a role in the sense that often, even if we wanted to use ratings, we are forced to use rankings because of the risk of excessive strategic voting in competitive environments. A nicer way to explain this is to say that ranked methods give exactly one vote to every voter (in the pairwise comparisons). From this nice equality point of view it is quite possible to find ideal explanations for ranked methods on who should win.

One problem with ranked methods (and especially the Condorcet family) is that the methods try to be very strategy free (and they indeed are), and this sets some limitations to the design. For example it is a natural thought that the number of losses (to different candidates) would be a rather nice measure of popularity, but we can't usually use that criterion since it typically makes the methods vulnerable to clones. I gave one ideal winner explanation to minmax(margins). It focused on worst losses and told that this may be a useful measure of amount of opposition after the election. We could also say that a useful measure of opposition is the number of voters who would like to change the winner to any other candidate, not to some specific candidate. But that explanation is thus ruled out because the strategy and clone related concerns. We must satisfy with comparing the worst losses and contemplate if that is a natural way to measure who should win in our elections.

Post by Toby Pereira
That and you get a clear order with an easy-to-digest way of seeing how close it was - total approvals or score (or average score). I do think these things are worth considering in a method. For a Condorcet system, the minimax system has an advantage over most others in that you can put the finishing positions of all the candidates, as well as a meaningful number by them (the number of extra ballots required to make them a winner). Dodgson is the same, so that makes me wonder - which other Condorcet methods are like this? I almost think it's worth being a named criterion in its own right. Candidate result scorable or something.

Yes, being able to display the results and/or distance to winning the race in an easy to understand way is a good target that could be formulated as a criterion. It may be a true problem of many Condorcet methods that displaying the pairwise comparison values in a matrix or in a cyclic graph is too complex. It may also be difficult to give clear numbers even to experts on how close each candidate is to winning the race. Meadia wants to tell people about the race, also online while waiting for the final results, with clear numbers if possible. (I welcome input here. What can we say about the distance to winning the race in different Condorcet methods?)

As you can already guess, I also don't like very much the idea of forcing the potentially cyclic results into a linear order in some way that "breaks the loops" since that approach easily gives a distorted impression of the relative position of the candidates (the score / minmax ordered results are however ok). This expression, "breaking the loops" (that do exist, are natural, and should not be hidden) actually points out quite well what is wrong in the artificial linearization of the group opinions (also with respect to finding the best winner, not just with respect to giving nice histograms to media).

Juho

[Forest Simmons]

Kristopher, Toby, and all,

Ordinal based methods"Done Right" require two things:

(1) a clone proof, monotonic way of converting rankings into ratings, and
(2) a cardinal ratings analog to the ordinal based method.

(1) One way to accomplish the first requirement is by way of any clone
free, monotonic lottery L, like the random favorite lottery. Convert the
rankings from an ordinal ballot B to ratings in two steps as follows:

(i) For each candidate X, let p(X) be the probability that lottery L would
not elect a candidate ranked ahead of X on ballot B. (ii) On each ballot
normalize these probabilities to ratings with an affine transformation so
that the extreme scores are the same for every ballot, say zero and 100.

Now for (2):

Since Borda elects the candidate with the best rank sum, the Borda analog
is the method that elects the candidate with the best ratings sum, i.e.
"Score." So Borda Done Right is just Score applied to the converted
rankings i.e. to the ratings that are obtained from the rankings by the
above conversion process.

Since Bucklin elects the candidate with best median rank, "Bucklin Done
Right" elects the candidate with the highest median rating. Ties can be
broken a la Majority Judgment, but note that ties are not as likely in this
new context, because ratings that result from the conversion process
described above will result in much greater resolution (i.e. number of
distinct rating levels).

Notice, also, that the conversion step (1) above opens up the possibility
of applying ratings based PR methods while using the more traditional (in
the context of PR) ordinal ballots as inputs. Voters vote ratings or
rankings, according to their preferences. Then the rankings are converted
to ratings so that a (possibly) superior ratings based PR method can be
applied.

For more examples search the archives for the original "done right"
messages.

Forest

On Tue, Nov 4, 2014 at 11:56 PM, Kristofer Munsterhjelm <

Post by Kristofer Munsterhjelm

Post by Forest Simmons
Toby,
You mentioned Kemeny. The very purpose of Kemeny is to determine a
"social order," namely the one that minimizes the average "distance"
from that order to the ballot orders..
The trouble with Kemeny is that the choice of metric for the "distance:"
is clone dependent: changing the size of a clone set changes the number
of transpositions of order to move a candidate past that set.

If you change "sum" (or average) to leximax, then that problem goes away
and you get Ranked Pairs, right?
Can River also be formulated as an optimization problem?
However, if cardinal ratings (e.g. score ballots) are used, then clone

Post by Forest Simmons
independent metrics can be substituted for the Kemeny distance. I once
posted a message to this list describing a clone free technique for
converting a set of ordinal ballots into a set of ratings Then based on
those ratings it was possible to define "Kemeny Done Right," Dodgson
Done Right," and "Borda Done Right." Of these three "done right"
methods, only the latter fails the Condorcet Criterion.

Does altering Kemeny in this way fix its vulnerability to cloning? I'd
imagine that any way of turning rankings into ratings would make the
ratings depend on the candidates in some way; otherwise, you could bolt
that onto, say, Range, and get a deterministic ranked method that passes
IIA (which we know is impossible).