Created
May 31, 2013 21:25
-
-
Save DRMacIver/5688125 to your computer and use it in GitHub Desktop.
A very basic voting simulator.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from scipy.stats.distributions import norm as normal | |
from numpy.linalg import norm | |
from numpy import dot | |
import random | |
import numpy | |
import operator | |
def generate_sphere(n): | |
result = normal().rvs(n) | |
result /= norm(result) | |
return result | |
def generate_votes(candidates): | |
facets = len(candidates[0]) | |
candidates = list(enumerate(candidates)) | |
while True: | |
voter = generate_sphere(facets) | |
random.shuffle(candidates) | |
candidates.sort(key=lambda (i, c): dot(c, voter), reverse=True) | |
yield [i for i, c in candidates] | |
def dominance_matrix(votes): | |
n = len(votes[0]) | |
matrix = numpy.zeros((n, n)) | |
for v in votes: | |
for i in xrange(n): | |
c1 = v[i] | |
for j in xrange(i+1, n): | |
c2 = v[j] | |
matrix[c1, c2] += 1 | |
return matrix | |
def find_condorcet_winners(votes): | |
matrix = dominance_matrix(votes) | |
n = len(matrix) | |
dominance_sets = {} | |
for i in xrange(n): | |
dominance_sets[i] = set( | |
j | |
for j in xrange(n) | |
if matrix[j, i] >= matrix[i, j] | |
) | |
changed = True | |
while changed: | |
changed = False | |
for i, s in dominance_sets.items(): | |
t = reduce(operator.or_, (dominance_sets[j] for j in s)) | |
if t != s: | |
assert len(t) > len(s) | |
dominance_sets[i] = t | |
changed = True | |
return list(reduce(operator.and_, dominance_sets.values())) | |
def first_past_the_post(votes): | |
counts = {} | |
for v in votes: | |
counts[v[0]] = counts.get(v[0], 0) + 1 | |
return max(counts.items(), key=lambda (_, c): c)[0] | |
def alternative_vote(votes): | |
not_rejected = set(votes[0]) | |
while True: | |
counts = {} | |
for v in votes: | |
for c in v: | |
if c in not_rejected: | |
counts[c] = counts.get(c, 0) + 1 | |
break | |
for i, c in counts.items(): | |
if c > len(votes) / 2: | |
return i | |
loser = min(counts.items(), key=lambda (_, c): c)[0] | |
not_rejected.remove(loser) | |
def random_condorcet_winner(votes): | |
return random.choice(find_condorcet_winners(votes)) | |
def random_ballot(votes): | |
return random.choice(votes)[0] | |
def random_ranked_pair(votes): | |
matrix = dominance_matrix(votes) | |
n = len(matrix) | |
i = random.randint(0, n-1) | |
j = random.randint(0, n-1) | |
if matrix[i, j] < matrix[j, i]: | |
i, j = j, i | |
return i | |
if __name__ == '__main__': | |
from itertools import islice | |
strategies = [ | |
("AV", alternative_vote), | |
("FPTP", first_past_the_post), | |
("RandomCondorcet", random_condorcet_winner), | |
("RandomBallot", random_ballot), | |
("RandomRankedPair", random_ranked_pair) | |
] | |
while True: | |
candidates = [generate_sphere(6) for _ in xrange(6)] | |
votes = list(islice(generate_votes(candidates), 0, 500)) | |
print '\t'.join("%s:%s" % (name, str(strategy(votes))) for name, strategy in strategies) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment