<jupyter_start><jupyter_text>Kemeny-YoungI'm following in the footsteps of [this](http://vene.ro/blog/kemeny-young-optimal-rank-aggregation-in-python.html) article. Here Kemeny-Young, one of the notable Condorcet methods, is formulated as integer programming problem.<jupyter_code>#from __future__ import print_function
import scipy.optimize as optimize #.linprog 
import scipy.stats as stats
import numpy as np

from itertools import combinations, permutations

def kendalltau_dist(rank_a, rank_b):
    tau = 0
    n_candidates = len(rank_a)
    for i, j in combinations(range(n_candidates), 2):
        tau += (np.sign(rank_a[i] - rank_a[j]) ==
                -np.sign(rank_b[i] - rank_b[j]))
    return tau
# columns in order of appearance:
cols = "<NAME>".split()
ranks = np.array([[0, 1, 2, 3, 4],
                  [0, 1, 3, 2, 4],
                  [4, 1, 2, 0, 3],
                  [4, 1, 0, 2, 3],
                  [4, 1, 3, 2, 0]])
                  #[4, 1, 2, 3, 0],
                  #[2, 1, 3, 5, 4]])

kendalltau_dist(ranks[0], ranks[1])
def rankaggr_brute(ranks):
    min_dist = np.inf
    best_rank = None
    n_voters, n_candidates = ranks.shape
    for candidate_rank in permutations(range(n_candidates)):
        dist = np.sum(kendalltau_dist(candidate_rank, rank) for rank in ranks)
        if dist < min_dist:
            min_dist = dist
            best_rank = candidate_rank
    return min_dist, best_rank
dist, aggr = rankaggr_brute(ranks)
print("A Kemeny-Young aggregation with score {} is: {}".format(
    dist,
    ", ".join(cols[i] for i in np.argsort(aggr))))<jupyter_output>A Kemeny-Young aggregation with score 15 is: <NAME>, Gwendolyn, Debbie, Alicia<jupyter_text>The formulation is based on the alternative interpretation of the Kemeny optimal aggregation as the ranking that minimizes the weights of edges it disagrees with:for all e in E   minimize w(e)x(e)  subject to i != j, x(i,j) + x(j,i) = 1 and x(i,j) + x(j,k) + x(k,i) >= 1See also the original article [here](http://www.aaai.org/Papers/AAAI/2006/AAAI06-099.pdf)<jupyter_code>def _build_graph(ranks):
    n_voters, n_candidates = ranks.shape
    edge_weights = np.zeros((n_candidates, n_candidates))
    for i, j in combinations(range(n_candidates), 2):
        preference = ranks[:, i] - ranks[:, j]
        h_ij = np.sum(preference < 0)  # prefers i to j
        h_ji = np.sum(preference > 0)  # prefers j to i
        if h_ij > h_ji:
            edge_weights[i, j] = h_ij - h_ji
        elif h_ij < h_ji:
            edge_weights[j, i] = h_ji - h_ij
    return edge_weights

print(_build_graph(ranks))
from cylp.cy import CyClpSimplex
from cylp.py.modeling.CyLPModel import CyLPArray

def rankaggr_lp(ranks):
    """Kemeny-Young optimal rank aggregation"""

    n_voters, n_candidates = ranks.shape
    
    s = CyClpSimplex()
    
    # to state pairwise and triangle constraints like x(ij) + x(ji) = 1
    x = s.addVariable('x', n_candidates ** 2)
    
    
    # minimize c.T * x
    edge_weights = _build_graph(ranks)
    c = 1 * edge_weights.ravel()  
    
    idx = lambda i, j: n_candidates * i + j
    
    print (n_voters, n_candidates)
    
    # constraints to ensure elements >= 0
    uni_constraints = np.zeros((n_candidates ** 2, n_candidates ** 2))
    for i in range(0, n_candidates ** 2):
        uni_constraints[i,i] = 1
        
    UniConstraints = np.asmatrix(uni_constraints)
    s += UniConstraints * x >= 0
    
    # constraints for every pair - shape (10, 25)
    pairwise_constraints = np.zeros((int((n_candidates * (n_candidates - 1)) / 2),
                                      n_candidates ** 2))
        
    for row, (i, j) in zip(pairwise_constraints,
                           combinations(range(n_candidates), 2)):
        row[[idx(i, j), idx(j, i)]] = 1
    
    
    PairwiseConstraints = np.asmatrix(pairwise_constraints)

    s += PairwiseConstraints * x == 1

    # and for every cycle of length 3 - shape (60, 25)
    triangle_constraints = np.zeros(((n_candidates * (n_candidates - 1) *
                                     (n_candidates - 2)), n_candidates ** 2))
    
    for row, (i, j, k) in zip(triangle_constraints,
                              permutations(range(n_candidates), 3)):
        row[[idx(i, j), idx(j, k), idx(k, i)]] = 1

    TriangleConstraints = np.asmatrix(triangle_constraints)
  
    s += TriangleConstraints * x == 1
    
    # print (s.constraints)
    
    ObjectiveMatrix = np.asmatrix(c)
    print (ObjectiveMatrix.shape)
    
    # print (ObjectiveMatrix)
    s.objective = ObjectiveMatrix * x
    
    # Solve using primal Simplex
    s.primal()
    X = s.primalVariableSolution['x']
        
    # cs = CyClpSimplex()
    # obj, x, duals = CyClpSimplex(c, constraints, constraint_rhs, constraint_signs,
    #                        xint=range(1, 1 + n_candidates ** 2))

    X = np.array(X).reshape((n_candidates, n_candidates))
    print (X)
    aggr_rank = X.sum(axis=1)

    return aggr_rank<jupyter_output><empty_output><jupyter_text>BugThe results in the next cell simply wrong; they should be the same as with the brute force method.**needs more debugging**<jupyter_code>aggr = rankaggr_lp(ranks)
score = np.sum(kendalltau_dist(aggr, rank) for rank in ranks)
print("A Kemeny-Young aggregation with score {} is: {}".format(
    score,
    ", ".join(cols[i] for i in np.argsort(aggr))))<jupyter_output>5 5
(1, 25)
[[0.         0.66666667 0.66666667 0.66666667 0.33333333]
 [0.         0.         0.33333333 0.33333333 0.        ]
 [0.         0.33333333 0.         0.33333333 0.        ]
 [0.         0.33333333 0.33333333 0.         0.        ]
 [0.33333333 0.66666667 0.66666667 0.66666667 0.        ]]
A Kemeny-Young aggregation with score 17 is: Gwendolyn, Robin, Ginny, Alicia, Debbie
{'fraction_non_alphanumeric': 0.11977812445831167, 'fraction_numerical': 0.0405616224648986, 'mean_word_length': 2.5771853688778674, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 14, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '107452', 'license': 'MIT', 'n_tokens_mistral': 2260, 'n_tokens_neox': 2005, 'n_words': 529, 'path': 'Kemeny-Young.ipynb', 'repo_name': 'ankit-jha/mmfunctions', 'size': '5804'}