supermajority.py

import numpy as np
import numpy.random as npr
from itertools import permutations


N_SAMPLES = 10 ** 6


def calculate_threshold(n_candidates, ph):
    candidates = range(n_candidates)

    scores = np.zeros((n_candidates, n_candidates))
    for c, v in zip(permutations(candidates), ph):
        for i, a in enumerate(c):
            for b in c[i+1:]:
                scores[a, b] += v
    result = 0.0
    for n in range(3, n_candidates + 1):
        for cycle in permutations(candidates, n):
            score = min(scores[i, j] for i, j in zip(cycle, cycle[1:]))
            score = min(score, scores[cycle[-1], cycle[0]])
            result = max(result, score)
    assert isinstance(result, float)
    return result


def fact(n):
    i = 1
    for k in range(1, n + 1):
        i *= k
    return i


def threshold_distribution(n_candidates):
    print("Calculating thresholds for %d candidates" % (n_candidates,))

    thresholds = []

    for p in npr.dirichlet([1] * fact(n_candidates), size=N_SAMPLES):
        thresholds.append(calculate_threshold(n_candidates, p))

    thresholds = np.array(thresholds)

    cycles = thresholds[thresholds >= 0.5]

    print("%.2f%% of cycles exceed 54%%" % (
        len(cycles[cycles >= 0.54]) * 100.0 / len(cycles),
    ))

    print("Found %d cycles out of %d" % (len(cycles), len(thresholds)))
    print("%2.f%% of elections have cycles" % (
        len(cycles) * 100.0 / len(thresholds),))

    print("Average threshold for cycles is %.2f" % (cycles.mean(),))
    print("Largest threshold for cycles is %.2f" % (cycles.max(),))

    print("99%% mark is %.2f" % (np.percentile(thresholds, 99),))
    print("99.9%% mark is %.2f" % (np.percentile(thresholds, 99.9),))
    print("One in a million is %.2f" % (
        np.percentile(thresholds, (1 - 10 ** -6) * 100),))
        
if __name__ == '__main__':
    for k in (3, 4):
        threshold_distribution(k)
        print()

Note: This code is very slow and is not a particularly efficient way to calculate the result.