Skip to content

Instantly share code, notes, and snippets.

@arpruss
Last active January 15, 2020 21:56
Show Gist options
  • Save arpruss/c57ed6d4ed27a180a3b0bb399965c645 to your computer and use it in GitHub Desktop.
Save arpruss/c57ed6d4ed27a180a3b0bb399965c645 to your computer and use it in GitHub Desktop.
Black's or Nanson's voting algorithm
import sys
#
# MIT Licensed code by Alexander R Pruss
#
# Implements Black's Procedure: Condorcet backed up with Borda to generate a ranked list from ranked votes
# and Nanson's Method: drop all candidates with Borda scores below average
#
# require n [default: None]
# require a valid ballot to have n candidates
# invariantBordaScoreInBlacks 1/0 [default: 0]
# in Black's procedure, is the Borda score based on the original ballots (or on the ballots with previous winners deleted)?
# ballot c1 c2 c3 ...
# register a ballot
# key k name
# register k as the abbreviation for name
# BEGIN sectionname
# ...
# END sectionname
# same as prefacing each line of ... with sectionname
candidates = set()
ballots = []
validBallots = []
options = {}
selected = set()
keys = {}
section = None
INVARIANT_BLACKS = "invariantbordascoreinblacks"
def parse(s):
try:
return int(s)
except:
return s
def beatsInBallot(c1,c2,ballot):
try:
i1 = ballot.index(c1)
except:
i1 = len(ballot)
try:
i2 = ballot.index(c2)
except:
i2 = len(ballot)
return i1 < i2
def isCondorcet(c):
for d in candidates:
if d != c and d not in selected:
beats = 0
beaten = 0
for b in validBallots:
if beatsInBallot(c,d,b):
beats += 1
elif beatsInBallot(d,c,b):
beaten += 1
if beats <= beaten:
return False
return True
def getGroup(size, soFar=[]):
if size > len(candidates):
raise "There aren't enough candidates"
if len(soFar) == size:
yield soFar
else:
for c in candidates:
if c not in soFar:
for g in getGroup(size, soFar+[c]):
yield g
def winnerGroupOfSize(size):
global selected
for group in getGroup(size):
selected = group
beaten = False
for c in group:
if not isCondorcet(c):
beaten = True
break
if not beaten:
return group
return None
def describe(c):
if c in keys:
return "%s [%s]" % (keys[c],c)
elif not keys:
return c
else:
return "["+c+"]"
def getCondorcet():
for c in candidates:
if c not in selected:
if isCondorcet(c):
return c
return None
def getReversedBordaScore(c,allowed):
score = 0
for b in validBallots:
b = [d for d in b if d in allowed]
try:
score += b.index(c)
except:
score += len(b)
return score
def getBordas():
scores = {}
allowedCandidates = candidates if options.get(INVARIANT_BLACKS,0) else candidates-selected
for c in candidates:
if c not in selected:
scores[c] = getReversedBordaScore(c, allowedCandidates)
best = min(scores[c] for c in scores)
return [c for c in scores if scores[c] == best]
def BlacksProcedure():
place = 0
while len(selected) < len(candidates):
if len(candidates) - len(selected) == 1:
c = list(candidates-selected)[0]
print("position %s: %s" % ( (place+1), describe(c)))
selected.add(c)
else:
c = getCondorcet()
if c:
print("position %s (Condorcet): %s" %( (place+1), describe(c)))
selected.add(c)
place += 1
else:
b = getBordas()
n = len(b)
b.sort()
for c in b:
print("position %s (Borda%s score): %s" % ((place+1), ("" if n==1 else " tie"), describe(c)))
selected.add(c)
place += n
def getNansons(candidates):
scores = { c:getReversedBordaScore(c, candidates) for c in candidates }
values = [ scores[c] for c in candidates ]
if min(values) == max(values):
return list(candidates)
total = sum(scores[c] for c in candidates)
n = len(candidates)
return getNansons([c for c in candidates if scores[c] * n <= total])
def NansonsMethod():
place = 0
unselected = set(candidates)
while len(unselected)>1:
cond = getCondorcet()
b = getNansons(unselected)
n = len(b)
b.sort()
for c in b:
print("position %d%s%s: %s" % ((place+1), (" (Condorcet)" if c == cond else ""), ("" if n==1 else " (tie)"), describe(c)))
selected.add(c)
unselected.remove(c)
place += n
if len(unselected):
print("position %s: %s" % ((place+1), describe(list(unselected)[0])))
with open(sys.argv[-1]) as f:
for line in f:
line = line.strip()
if '#' in line:
line = line[:line.index('#')].strip()
if line:
cmd,data1 = line.split(None, 2)[:2]
if cmd == "BEGIN":
if section:
print("Nested sections not allowed")
sys.exit(1)
else:
if data1 == "ballots" or data1 == "keys":
section = data1[:-1]
else:
section = data1
elif cmd == "END":
if section != data1 and section + "s" != data1:
print("END doesn't match BEGIN")
sys.exit(1)
section = None
else:
if section:
line = section + " " + line
cmd,data = line.split(None, 1)
cmd = cmd.lower()
if cmd == "ballot":
ballots.append(data.split())
elif cmd == "key":
dd = data.split()
keys[dd[0]] = dd[1]
else:
options[cmd] = parse(data.strip())
i = 1
while i + 1 < len(sys.argv):
if sys.argv[i].startswith("-o"):
opt,d = sys.argv[i][2:].split("=", 1)
options[opt.lower()] = parse(d)
i+=1
print("Options:",options)
def validate(b):
r = options.get('require',0)
if r and len(b) != r:
return False
if len(set(b)) != len(b):
# repetition of a candidate
return False
return True
validBallots = []
for b in ballots:
if validate(b):
validBallots.append(b)
else:
print("Invalid ballot:",b)
print("Ballots:", len(ballots))
print("Valid ballots:", len(validBallots))
for b in validBallots:
candidates |= set(b)
if not candidates:
print("No candidates!")
exit(0)
lc = list(candidates)
lc.sort()
print("Candidates:", lc)
m = options.get("method", "Black's")
if m.lower().startswith("black"):
print("Method: Black's%s" % (" with invariant Borda scores" if options.get(INVARIANT_BLACKS, 0) else ""))
BlacksProcedure()
elif m.lower().startswith("nanson"):
print("Method: Nanson's")
NansonsMethod()
else:
print("Unknown method %s" % m)
for i in range(1,len(candidates)):
s = winnerGroupOfSize(i)
if not s:
print("No group of %d that Condercet beats everyone else" % i)
else:
print(("Group of %d that Condorcet beats everyone else: " % i) + ', '.join(list(sorted(describe(a) for a in s))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment