[EM] Theorems to optimize Kemeny Young?

[Kristofer Munsterhjelm]

On 01.02.2022 00:49, 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?

The standard way to do this is to formulate K-Y as an integer linear
program and then let the knowledge of the experts who made your solver
find the shortcuts for you. IIRC this approach has been used with number
of candidates approaching 40 with no problems in the average case.

According to Conitzer's paper and my source code, the MIP is:

maximize sum of, over all A,B: x_ind_A>B * A>B

subject to:
 - for all A,B: x_ind_A>B binary
 - for all A,B: x_ind_A>B + x_ind_B>A = 1    (1)
 - for all A,B,C: x_ind_A>B + x_ind_B>C + x_ind_C>A >= 1  (2)

(1) makes sure there are no ties in the resulting ordering, while (2)
makes sure there are no cycles so that the resulting ordering is
transitive. Then x_ind_A>B if A beats B pairwise in the social order. At
the moment I don't remember how (2) enforces non-cycles since on the
face of it, it seems to explicitly specify that cycles are allowed, but
that's how it's stated.

The mathematical term for this problem is called feedback arc set or
feedback edge set. See also

https://users.cs.duke.edu/~conitzer/kemenyAAAI06.pdf
https://en.wikipedia.org/wiki/Feedback_arc_set#Exact
https://github.com/sschnug/kemeny_ranking

If you replace the maximize sum objective with leximax, then if I'm not
mistaken, you get Ranked Pairs. MIP solvers rarely support this kind of
objective, though, and for RP you could just use its standard algorithm.

(Perhaps I should put this in the Electowiki article -- if I could just
understand how constraint (2) works.)

Finally note that Richard Fobes' implementation can fail for very large
Smith sets. This is how it manages to achieve polynomial runtime without
proving P=NP.

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

Unfortunately not; I've mostly taught myself.

-km