[EM] Sorting algorithms applied to candidate ranking

[Kristofer Munsterhjelm]

On 02.04.2023 19:20, Richard, the VoteFair guy wrote:

> Clarification:  As Kristofer points out, there are contrived (highly 
> cyclic) cases where the results do not match Kemeny results.  Yet the 
> top 7 or so candidates can be identified and run through the full Kemeny 
> calculations to identify the winner.  It's possible the Kemeny winner 
> from the full set of candidates does not get identified as one of the 
> top 7 candidates, but in those contrived cases any winner would be 
> controversial (in the same way that an algorithm for finding the highest 
> mountain would produce controversial results if it were used to find the 
> highest sand dune in a desert).

I'd like to also clarify that mixed integer programming solvers can do 
Kemeny of Smith sets of size 20 or more in reasonable time. If I recall 
correctly, state of the art like CPLEX or Gurobi can do up to 40, but 
I'm not completely sure I got those figures correct.

If the sorting approach is Monte Carlo (takes a fixed time though being 
incorrect with small probability), then MIP is Las Vegas (always correct 
but sometimes takes a very long time) - though the analogy is incomplete 
as they're deterministic algorithms.

In practice, it may not matter; but then, in practice, we could use a 
polytime election method, get similar results, and please theoreticians 
too :-)

-km