[EM] Verification of a voting outcome for VoteFair.

[Richard Fobes]

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*.