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.

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

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