Finally I have time to reply to Kristofer's comments about whether or
not VoteFair popularity ranking is the same as the Condorcet-Kemeny method.
If the Smith set does not contain more than six candidates, then yes
VoteFair popularity ranking always identifies the same top-ranked
candidate (the "winner") as the Condorcet-Kemeny method.
This occurs even if there are fifty (or more) candidates because the
VoteFair algorithm quickly moves to the top of the ranking the
candidates who are in the Smith set. (I'll back up this claim when I
finally have time to reply to Jameson's even-earlier message.)
The VoteFair algorithm cross-checks the top six choices using the full
sequence-score calculation method. For this reason, plus the
above-explained reason, there cannot be a discrepancy in identifying the
winner for cases that involve no more than six candidates within the
Smith set.
If the Smith set contains more than six candidates, then the open-source
algorithm for calculating VoteFair popularity ranking results could
possibly identify a different "winner" compared to the Condorcet-Kemeny
method. Yet this discrepancy can only occur if the voters are not clear
in expressing any kind of consistency in their preferences, which means
there is a high level of circular ambiguity. (I hope to have time to
say more about this later.)
In such cases (involving a discrepancy) the "correct" Condorcet-Kemeny
winner would be highly controversial, and that winner could easily fail
to win a runoff election (against the VoteFair-algorithm-ranked most
popular candidate). Plus the results would be controversial regardless
of which Condorcet method were used.
The Wikipedia article titled "Approximation algorithm" (at
http://en.wikipedia.org/wiki/Approximation_algorithm) provides a name
for the relationship between the VoteFair-popularity-ranking algorithm
and the Condorcet-Kemeny method (for cases in which the Smith set
exceeds six candidates), and this is the same relationship that exists
between an algorithm that quickly and reasonably (but not _always_
_exactly_) solves the Traveling Salesman Problem and the exactly
calculated NP-hard Traveling Salesman Problem.
This matches what I've said before, but gives a specific name for the
relationship.
Kristofer implies that the well-studied characteristics of the
Condorcet-Kemeny method cannot apply to the VoteFair popularity ranking
method if there is ever any inconsistency in the results. This
perspective is overly simplistic. Of course it is true that if the
Condorcet-Kemeny method always produces results that meets a specified
criteria, then we cannot be sure that the VoteFair popularity ranking
calculations also meet the specified criteria if the case involves more
than six candidates in the Smith set. Yet it is also true that the
VoteFair popularity ranking calculations may meet the specified
criteria. We don't know which situation applies until we check the results.
As Jameson has pointed out, an election that involves more than four
candidates in the Smith set would be uncommon. An election that
involves more than six candidates in the Smith set would be extremely rare.
On 4/7/2012 3:19 AM, Kristofer Munsterhjelm wrote:
>...
> B>C>D>A has score 44.
> C>D>B>A has score 44.
>
> As far as I understood your post, those are the only with score 44.
> VoteFair picks neither, nor does it give a direct tie between C and B.
If an implementation of the Condorcet-Kemeny method were to choose one
of these two sequences, then it would be ignoring the other sequence,
and that would ignore the whole point of the Condorcet-Kemeny method,
which is to find the sequence or sequences with the highest score. This
method says that both sequences are equally valid as sequences that have
the highest score, so both must be taken into account in order to be
consistent with the Condorcet-Kemeny method.
Of course if these two sequences had choices B and C in the first two
positions (such as B>C>D>A and C>B>D>A) then of course choices B and C
are tied. But that is not the case.
Instead, choice B jumps from first place in the first sequence down to
third place in the second sequence, whereas choice C moves from second
place to first place.
The "official" Condorcet-Kemeny method (including Kemeny's original
description) does not specify how to resolve this situation.
The open-source VoteFair ranking software resolves this situation by
calculating the average ranking of each choice over all the sequences
that have the same highest score. In this case, if we number the
positions starting at 1 for the beginning of the sequence, the average
ranking for choice C is 1.5, the average ranking for choice B is 2.0,
the average for choice D is 2.5, and the average for choice A is 4.0.
This puts choice C (at 1.5) above choice B (at 2.0).
> If, in practical elections, the max Smith set size is low, then any of
> the advanced Condorcet methods may be good enough. Any Condorcet method
> does the right thing with Smith set size 1, and I think Schulze / RP /
> MAM all give the same result with Smith set size <= 3, and that this
> result is the same as the Kemeny result. These other methods are either
> simpler than VoteFair (in the case of Ranked Pairs, say), or are more
> well known (Schulze).
Simplicity for the person who writes the software is a tiny issue
compared to simplicity for the voters (in terms of ballot type and
marking strategies), and compared to simplicity in terms of
understanding the algorithm (which is a big challenge for the
Condorcet-Schulze method), and compared to the issue of voters trusting
the results (which relates to mathematical arguments being difficult for
most people to understand).
As for the Condorcet-Schulze method being better known, that's because
software for it was available years ago, which relates to the concept
that it is easy to program (except for dealing with ties, which
complicates all methods). History is filled with examples of the
first-available choice not surviving over time. As one example, CPM and
MS-DOS came before MS-Windows (and that race isn't over yet).
I regard VoteFair ranking as having advantages that are not yet
appreciated. Remember that the voting characteristics listed in the
Wikipedia "Voting system" comparison chart are just checklist-like
yes-versus-no attributes that fail to reveal how often, and under what
circumstances, each method fails each of the failed criteria. (I am not
disputing the importance of those criteria; I am saying that numeric
information can be more revealing than true/false information.)
> On the other hand, if the max Smith set size is high, then VoteFair may
> not approximate Kemeny well enough. In that case, if what you want is
> Kemeny, then you pretty much have to go to Kemeny.
If someone wants exact Condorcet-Kemeny results for a large Smith set
then I have to wonder why. If it's needed to simulate results for
studying its mathematical characteristics, then of course that's
different from a group of voters wanting to know which candidate
deserves to win an election.
> The fine-tuning argument then is: it appears that for VoteFair to have a
> substantial advantage over other Condorcet methods, the max Smith set
> size for realistic elections have to be high enough that the other
> methods don't approximate Kemeny but simultaneously low enough that
> VoteFair does approximate Kemeny. Is that the case? It doesn't seem
> clear *as such*.
I, and the people who use my software at VoteFair.org, have been getting
superbly fair results, and I have not encountered any case in which one
of the other Condorcet methods would be a better choice.
Only time can determine which voting methods are in use 100 years from now.
Personally my view is that there is excessive focus on single-winner
voting methods (partly because they are easier to study), yet there are
bigger frontiers waiting to be pioneered. That's why I've gone beyond
VoteFair popularity ranking to develop VoteFair representation ranking
(because the "second-most popular" choice is not the same as the
"second-most representative" choice), and VoteFair partial-proportional
ranking (which provides a PR method that is designed for the situation
in the U.S.), and VoteFair party ranking (which deals with the problem
that will arise when vote splitting is not around to limit the number of
candidates on the ballot, and which happens to minimize the cloneproof
failure ascribed to the Condorcet-Kemeny method), and VoteFair
negotiation ranking (which allows a Parliament to elect a fair slate of
Cabinet Ministers without using any quota rules to enforce fairness).
We have a long way to go, and when the dust settles a few centuries from
now, the landscape will probably be unfamiliar to all of us.
Richard Fobes
---------------------------------------------------------
[For context, Kristofer's full message is repeated below:]
On 4/7/2012 3:19 AM, Kristofer Munsterhjelm wrote:
On 04/04/2012 08:06 PM, Richard Fobes wrote:
My comments are interspersed as answers to specific questions/statements.
On 4/3/2012 12:53 AM, Kristofer Munsterhjelm wrote:
But anyway, I'll try to find an example where:
- VoteFair elects A,
- VoteFair has no ties in its social ordering,
- Kemeny finds another candidate X as the winner,
and
- There is no Kemeny-optimal ordering that puts A first.
Would that suffice to show that VoteFair isn't Kemeny?
No. As Jameson Quinn points out (in a message I haven't had time to
reply to yet), real-world elections typically involve no more than four
candidates in the Smith set. VoteFair ranking easily ranks Smith-set
candidates at the top (for reasons I plan to explain later). So, you
might be able to find a set of ballots for 50 candidates in which ALL
(or most) of the candidates are in the Smith set (and there are no
ties), for which VoteFair ranking identifies a "non-Kemeny" winner. But
as I've repeatedly said, if the voter preferences are that ambiguous,
then the difference is not significant.
So let me see if I got you right. You're saying that there may be ballot
sets where the proper Kemeny algorithm provides a certain ordering with
some candidate X at top, that is the unique winner (i.e. no ordering
with some other candidate Y at top can tie the X-at-top ordering's
Kemeny score), and where VoteFair provides an ordering that doesn't have
X at top.
That's enough to prove that VoteFair doesn't give an identical mapping
between ballot sets and social orderings as exhaustive Kemeny.
Mathematically, we're done. It's rather like if you find a method
passing Participation until you involve more than four candidates, after
which it doesn't. Then it doesn't matter that it passes Participation
with less than five candidates -- the method still doesn't pass
Participation.
If you want you say (in terms of analogy) that "okay, if you assign the
number 2 to Kemeny, VoteFair is 1.999998463721034, and that is close
enough", then that's okay. Argue that the difference makes no
difference; but if you say Kemeny *is* VoteFair and vice versa, that
implies VoteFair's number is 2, exactly.
Conclusion 12: VoteFair ranking calculates a fair result within the
limitations of the preference information available, and does so within
the context of the goal of maximizing the Condorcet-Kemeny sequence
score.
It doesn't actually maximize that sequence score, however; it falls one
short. It does provide the same winner as one of the sequences that do,
I see that.
Actually VoteFair ranking does find both the sequences that have the
same highest ("maximized") sequence score, but the "Kemeny" method --
even as you've defined it above -- does not specify how to resolve this
"tie" in the sequence scores.
Then why does VoteFair's output give an ordering with a score of 43
instead of 44? Why doesn't it break the tie only among those orderings
that have maximum score?
Notice that in such cases the "Kemeny" method does not specify choosing
one of the sequences. (They have the same score, so they are equally
valid.)
B>C>D>A has score 44.
C>D>B>A has score 44.
As far as I understood your post, those are the only with score 44.
VoteFair picks neither, nor does it give a direct tie between C and B.
More specifically (as I tried to convey in another message), if a set of
ballots can produce such a difference, the difference will be small
compared to the difference between various possible voting methods, even
if those various possible voting methods are limited to the ones
supported in the Declaration.
Let's say, for the sake of argument, that VoteFair produces the same
winner as Kemeny when the Smith set has <= K members. Then it appears
that your argument is: "K is high enough for VoteFair that for all
practical single-winner elections, VoteFair *is* Kemeny". But this can
cut both ways, in a fine-tuning argument.
If, in practical elections, the max Smith set size is low, then any of
the advanced Condorcet methods may be good enough. Any Condorcet method
does the right thing with Smith set size 1, and I think Schulze / RP /
MAM all give the same result with Smith set size <= 3, and that this
result is the same as the Kemeny result. These other methods are either
simpler than VoteFair (in the case of Ranked Pairs, say), or are more
well known (Schulze).
On the other hand, if the max Smith set size is high, then VoteFair may
not approximate Kemeny well enough. In that case, if what you want is
Kemeny, then you pretty much have to go to Kemeny.
The fine-tuning argument then is: it appears that for VoteFair to have a
substantial advantage over other Condorcet methods, the max Smith set
size for realistic elections have to be high enough that the other
methods don't approximate Kemeny but simultaneously low enough that
VoteFair does approximate Kemeny. Is that the case? It doesn't seem
clear *as such*.
----
Election-Methods mailing list - see http://electorama.com/em for list info
