Optimization code to find distribution with optimum distortion with respect to proportional fairness (Paper "Optimized Distortion and Proportional Fairness in Voting" by Soroush Ebadian, Anson Kahng, Dominik Peters, and Nisarg Shah)

prop-fairness.py

import cvxpy as cp
import math

def compute_hi(rankings):
    """Compute h_i(a) for all voters and alternatives."""
    hi = []
    for ranking in rankings:
        h = {}
        for a in ranking:
            h[a] = set(ranking[:ranking.index(a)+1])
        hi.append(h)
    return hi

def optimize(rankings):
    n = len(rankings)
    m = len(rankings[0])
    A = list(rankings[0])

    # Compute p_a values
    top_choices = [ranking[0] for ranking in rankings]
    p_a = [top_choices.count(a)/len(rankings) for a in A]

    # Compute h_i(a)
    hi = compute_hi(rankings)

    x = cp.Variable(m, nonneg=True)
    constraints = [cp.sum(x) == 1]
    
    beta = 2 * (1 + math.log(2*m))
    for i in range(m):
        constraints.append(x[i] >= p_a[i]/beta)
    
    # Objective function
    payoff = []
    for a in A:
        sum_term = sum([cp.inv_pos(cp.sum([x[A.index(alt)] for alt in hi[i][a]])) for i in range(n)])
        payoff.append(sum_term/n)
    
    objective = cp.Minimize(cp.maximum(*payoff))
    prob = cp.Problem(objective, constraints)

    prob.solve()

    return x.value

# Example 2.5 from paper
rankings = [[1,2,3], [2,1,3], [1,3,2]]
optimize(rankings) # approximately [0.5857 0.4142 0]