[EM] Theorems to optimize Kemeny Young?

[Richard, the VoteFair guy]

Here's my code that implements the Condorcet-Kemeny method:

https://github.com/cpsolver/VoteFair-ranking-cpp/blob/master/votefair_ranking.cpp

The comments within the code explain the algorithms used.

The big picture is that if there are, say, 50 candidates, then a special 
kind of insertion sort algorithm is done in a way that approximates the 
Kemeny calculations, and then the top-ranked candidates -- the number of 
which is specified as a constant, and which is (I believe) currently 7 
-- are ranked using the full Kemeny calculations.

Richard Fobes
The VoteFair guy


On 1/31/2022 3:49 PM, culitif at tuta.io wrote:
> Hey all,
>
> I took a crack at Kemeny Young and started off by doing it in the most
> brute force way possible: It generates all possible permutations of the
> list of candidates (all possible paths) and then assigns a score to each
> of them, keeping the one with the highest score. Obviously this is
> highly impractical and ends up being O(n!) where n is the number of
> candidates. I was wondering what theorems exist that could help me
> optimize this. I'm guessing that since its a Condorcet method, if
> there's a strong Condorcet winner, I should just return that winner
> right? Also if there's a subset of weak Condorcet winners then some
> permutation of those winners should lead the highest-scoring path right?
> Are there any other safe assumptions to make?
>
> Side note, do y'all have any recommendations for social choice theory
> books? Preferably something that discusses things like Kemeny Young and
> questions like the ones I have above.
>
> Best,
> Culi.
>
>
> ----
> Election-Methods mailing list - see https://electorama.com/em for list info
>