[EM] VoteFair Ranking software version 6.0 in C++ with MIT license

[VoteFair]

On 1/2/2020 3:00 PM, Kristofer Munsterhjelm wrote:
 > ...
 > The VoteFair ranking is F>C>E>A>G>D>B with Kemeny score 118, but
 > C>A>F>E>G>D>B has Kemeny score 119 and is the unique maximum ranking.

Yes, the default value for variable 
"global_check_all_scores_choice_limit" is 6 and it gives a result that 
differs from the (full) Condorcet-Kemeny method.

Increasing this variable to 7 causes the full Kemeny calculation process 
to be done across all 7 choices, and it gets the same result as doing 
the full Condorcet-Kemeny calculation method.

This is consistent with what I said earlier.

Of course the calculation time for the case in which there is a 
Condorcet (rock-paper-scissors) cycle across 50 choices is going to be 
way too time-consuming for this software.

As I've also said before, the odds of such a cycle (involving either 7 
or 50 choices) happening in a real election is lower than the odds of a 
conventional tie.  Either kind of tie can be resolved using a judicial 
decision -- like the Bush versus Gore decision from the US Supreme 
Court, which was not even an exact tie.

The point remains that the VoteFair ranking software matches the 
Condorcet-Kemeny calculations for as many choices as you choose.  The 
choice is determined by the value of the variable 
"global_check_all_scores_choice_limit".

Thank you for checking.  And especially thank you for providing the case 
in the format that I could directly plug into the software.

I have added this case to the GitHub repository.  Again, thanks!

Richard Fobes


On 1/2/2020 3:00 PM, Kristofer Munsterhjelm wrote:
> On 19/12/2019 00.26, VoteFair wrote:
>> On 12/18/2019 2:04 AM, Kristofer Munsterhjelm wrote:
>>> I can't help myself, but must point out again that I think it's more
>>> accurate to say (if this is true), that VoteFair popularity ranking is
>>> an approximation to Kemeny that becomes Kemeny in the limit as a certain
>>> parameter approaches infinity.
>>
>> Yes, when there are a large number of candidates, such as 50 candidates
>> as an example, estimations are done to yield a full ranking, and then
>> the top 6 or 7 or 8 (this is adjustable) most-popular candidates are
>> ranked using the exact Condorcet-Kemeny method to determine the ranking
>> for those top candidates.
>>
>> Yes, you came up with an example of a carefully constructed case that
>> involved something like 50 candidates -- and a small number of carefully
>> balanced groups of voters.  But that example illustrates my point that
>> such a case would not occur among voters who are sincerely marking their
>> ballots independently, without coordination with each other.
>
> I couldn't seem to find the example, so I tried to create a new one. My
> tools are a bit old and hacky, so I may have got it wrong, but I think
> this should work:
>
> 1: A>D>F>E>C>B>G
> 1: C>A>F>B>E>G>D
> 1: C>B>A>F>D>G>E
> 1: C>G>E>A>F>B>D
> 1: D>F>C>E>B>A>G
> 1: E>C>A>D>G>F>B
> 1: F>E>G>C>D>B>A
> 1: F>G>B>E>A>D>C
> 1: G>A>F>C>D>B>E
>
> Pairwise matrix:
>
> - 5 3 7 4 6 5
> 4 - 1 4 4 1 4
> 6 8 - 6 5 4 6
> 2 5 3 - 4 3 4
> 5 5 4 5 - 2 5
> 3 8 5 6 7 - 6
> 4 5 3 5 4 3 -
>
> VoteFair ballot format:
>
> request-no-rep  request-no-party  case 1 q 1 choices 7  x 1 q 1 3 2 1 6
> 4 7 5  x 1 q 1 7 1 6 3 4 2 5  x 1 q 1 5 3 1 4 7 6 2  x 1 q 1 6 5 7 3 4 2
> 1  x 1 q 1 4 6 3 5 2 1 7  x 1 q 1 1 4 6 5 3 2 7  x 1 q 1 3 7 5 1 6 2 4
> x 1 q 1 3 1 6 2 5 7 4  x 1 q 1 6 7 2 5 1 4 3
>
> There are four candidates in the Smith set: A, C, E, and F.
>
> The VoteFair ranking is F>C>E>A>G>D>B with Kemeny score 118, but
> C>A>F>E>G>D>B has Kemeny score 119 and is the unique maximum ranking.
>
> If that's right, there's no need for 50 candidates to make a
> counterexample. The example above does have a carefully balanced
> Condorcet cycle, however (moreso because it is optimized to have as few
> voters as possible).
>
>> In elections, where just a single winner is needed, the only way
>> VoteFair ranking and the full Condorcet-Kemeny calculations can identify
>> different winners is if the case involves numerous almost-equally
>> popular candidates (at the top, not the middle or bottom). (Specifically
>> there needs to be a carefully constructed Condorcet cycle that involves
>> a large number of candidates and a small number of carefully balanced
>> groups of voters.)
>>
>>> Unfortunately, letting that parameter approach infinity destroys
>>> VoteFair's polynomial runtime. So VoteFair does not prove P=NP :-)
>>
>> Yes you are correct that increasing the full calculation parameter
>> further (such as even to 20) would result in a very long computation
>> time, which is of course not a "polynomial runtime."
>>
>> Yet for election purposes, as opposed to mathematical-proof purposes, I
>> cannot imagine needing to increase the full calculation parameter to
>> check more than a few top candidates.  (If that affects the outcome,
>> then just a few spoiled ballots also would be just as likely to change
>> the outcome.)
>
> My point is that a phrase like "mathematically equivalent" is about
> mathematical-proof purposes, not practical election purposes. So I
> wouldn't say "mathematically equivalent" would be accurate for an
> approximation, any more than say
>
> f(x) = sum k = 0...100: x^k/k!		if x is a prime integer > 10^9
>        sum k = 0...infinity x^k/k!	otherwise
>
> is mathematically equivalent to e^x (where you always have to take the
> sum as k goes to infinity, not stop at 100). It may be pretty close for
> a typical number (as integers have measure zero), but it's not the same
> function.
>
> If functions are mathematically equivalent, then proofs about the former
> should also apply to the latter. But properties about e^x won't hold of
> f above, and properties of Kemeny won't hold of VoteFair over the whole
> domain. E.g. Kemeny passes LIIA but VoteFair doesn't (as eliminating the
> loser of the example election above would probably result in VoteFair
> returning the optimal Kemeny result).
>
> Mathematical equivalence might be too strict, but it is what it is. Or
> that's what I'd think the term would mean.
>
> You could save mathematical equivalence by restricting the domain to
> e.g. elections with a Smith set no larger than three candidates, prove
> that the sort-based VoteFair mechanism agrees with Kemeny within this
> domain with the usual parameters, and then say that VoteFair is
> mathematically equivalent on that domain. That would be a qualified
> mathematical equivalence, corresponding to your "real election purposes".
>