[EM] Verification of a voting outcome for VoteFair.

[Kristofer Munsterhjelm]

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