Skip to content

Instantly share code, notes, and snippets.

@DRMacIver
Created May 31, 2013 21:25
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save DRMacIver/5688125 to your computer and use it in GitHub Desktop.
Save DRMacIver/5688125 to your computer and use it in GitHub Desktop.
A very basic voting simulator.
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