rank_aggregation.py

from itertools import permutations
import numpy as np
from collections import defaultdict
from scipy.stats import kendalltau

# Define the input rankings: each ranking is a list from most to least preferred
rankings = [
    ['A', 'B', 'C'],
    ['B', 'C', 'A'],
    ['C', 'A', 'B']
]

items = ['A', 'B', 'C']
item_to_index = {item: i for i, item in enumerate(items)}
num_items = len(items)
num_voters = len(rankings)

# Convert to rank matrix (rows: voters, columns: items, values: ranks)
rank_matrix = np.zeros((num_voters, num_items), dtype=int)
for i, ranking in enumerate(rankings):
    for pos, item in enumerate(ranking):
        rank_matrix[i, item_to_index[item]] = pos

# -------------------
# 1. Borda Count
# -------------------
avg_ranks = rank_matrix.mean(axis=0)
borda_ranking = sorted(items, key=lambda x: avg_ranks[item_to_index[x]])

# -------------------
# 2. Reciprocal Rank Fusion (RRF)
# -------------------
k = 60  # smoothing constant
rrf_scores = defaultdict(float)
for i in range(num_voters):
    for item in items:
        rank = rank_matrix[i, item_to_index[item]]
        rrf_scores[item] += 1.0 / (k + rank)
rrf_ranking = sorted(items, key=lambda x: -rrf_scores[x])

# -------------------
# 3. Kemeny (brute-force over all permutations)
# -------------------
min_disagreement = float('inf')
best_kemeny = None
for perm in permutations(items):
    perm_ranks = [perm.index(x) for x in items]
    total_distance = 0
    for i in range(num_voters):
        voter_ranks = [rank_matrix[i, item_to_index[x]] for x in items]
        dist, _ = kendalltau(voter_ranks, perm_ranks)
        total_distance += 1 - dist  # 1 - correlation ≈ disagreement
    if total_distance < min_disagreement:
        min_disagreement = total_distance
        best_kemeny = list(perm)

# -------------------
# 4. Dodgson (approximate: count minimum adjacent swaps to become Condorcet winner)
# -------------------
def pairwise_majority(rankings, a, b):
    """Returns how many voters prefer a over b"""
    count = 0
    for ranking in rankings:
        if ranking.index(a) < ranking.index(b):
            count += 1
    return count

# Compute Condorcet matrix
condorcet_wins = {x: [] for x in items}
for a in items:
    for b in items:
        if a == b:
            continue
        if pairwise_majority(rankings, a, b) > num_voters // 2:
            condorcet_wins[a].append(b)

# Count swaps needed to turn each candidate into a Condorcet winner
def dodgson_score(candidate):
    swaps_needed = 0
    for opponent in items:
        if opponent == candidate:
            continue
        if pairwise_majority(rankings, candidate, opponent) <= num_voters // 2:
            # Count how many voters need to swap candidate above opponent
            votes_needed = (num_voters // 2 + 1) - pairwise_majority(rankings, candidate, opponent)
            swaps_needed += votes_needed
    return swaps_needed

dodgson_scores = {item: dodgson_score(item) for item in items}
dodgson_winner = min(dodgson_scores, key=lambda x: dodgson_scores[x])

# Output all rankings and scores
borda_ranking, rrf_ranking, best_kemeny, dodgson_winner, dodgson_scores