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

[Kristofer Munsterhjelm]

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