Skip to content

Instantly share code, notes, and snippets.

@DRMacIver DRMacIver/supermajority.py Secret
Last active Dec 21, 2018

Embed
What would you like to do?
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()
@DRMacIver

This comment has been minimized.

Copy link
Owner Author

commented Jan 28, 2017

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.