| 5 |
jtkorb |
1 |
#!/p/python/python
|
|
|
2 |
##
|
|
|
3 |
## Compute Hare Ballot
|
|
|
4 |
##
|
|
|
5 |
## Tim Korb (jtk@cs.purdue.edu), May 2007
|
|
|
6 |
##
|
|
|
7 |
## A few definitions and notes...
|
|
|
8 |
##
|
|
|
9 |
## tally: dictionary in which the keys are candidate names and the
|
|
|
10 |
## values are lists of ballots currently assigned to that candidate
|
|
|
11 |
##
|
|
|
12 |
## ballot: list of candidates in the order determined by the voter
|
|
|
13 |
##
|
|
|
14 |
## winners: list of candidates that have reached the quota of ballots
|
|
|
15 |
## or have remained in the running long enough to be declared a winner
|
|
|
16 |
##
|
|
|
17 |
## losers: list of candidates that have been eliminated from the running
|
|
|
18 |
##
|
|
|
19 |
## Note that plurals are generally used to indicate lists of other
|
|
|
20 |
## objects, e.g., ballots is a list of ballots.
|
|
|
21 |
##
|
|
|
22 |
import cgi
|
|
|
23 |
import string
|
|
|
24 |
import sys
|
|
|
25 |
import math
|
|
|
26 |
import random
|
|
|
27 |
|
| 11 |
jtkorb |
28 |
from revision import revision
|
| 7 |
jtkorb |
29 |
|
| 5 |
jtkorb |
30 |
formaction = string.split(sys.argv[0],"/")[-1]
|
|
|
31 |
|
|
|
32 |
fTrace = 1
|
|
|
33 |
fHTML = 1
|
|
|
34 |
|
|
|
35 |
def emitPreHTML(formaction):
|
|
|
36 |
emitHTML("""Content-type: text/html\n
|
|
|
37 |
<html>
|
|
|
38 |
<body>
|
|
|
39 |
<title>Hare Ballot Calculation</title>
|
|
|
40 |
<h1>Hare Ballot Calculation</h1>
|
|
|
41 |
<form enctype="multipart/form-data" method=POST action=%s>
|
|
|
42 |
<table>
|
|
|
43 |
<tr><td>CSV file of ballots:
|
|
|
44 |
<td><input type=file size=70 name=name>
|
|
|
45 |
</table>
|
|
|
46 |
<p>
|
|
|
47 |
<input type=submit name="run1" value="Run 1 Time">
|
|
|
48 |
<input type=submit name="run1000" value="Run 1000 Times">
|
|
|
49 |
<input type=submit name="convert" value="Convert to BLT Format">
|
|
|
50 |
</form>
|
|
|
51 |
<p>
|
|
|
52 |
Input file format is given
|
|
|
53 |
<a href="http://www.bikmort.com/wiki/index.php?title=Hare_Voting_Procedure">here</a>.
|
|
|
54 |
Almost no error checking is done, so be sure to review the trace output.
|
|
|
55 |
The source code is available <a href="%s?fetch=yes">here</a>.
|
|
|
56 |
<p>
|
|
|
57 |
<small>%s</small>
|
|
|
58 |
<hr>
|
|
|
59 |
<pre>
|
| 11 |
jtkorb |
60 |
""" % (formaction, formaction, revision))
|
| 5 |
jtkorb |
61 |
return
|
|
|
62 |
|
|
|
63 |
def emitPostHTML():
|
|
|
64 |
emitHTML("""</pre>
|
|
|
65 |
</body>
|
|
|
66 |
</html>
|
|
|
67 |
""")
|
|
|
68 |
return
|
|
|
69 |
|
|
|
70 |
def emitHTML(s):
|
|
|
71 |
global fHTML
|
|
|
72 |
if fHTML: print s
|
|
|
73 |
return
|
|
|
74 |
|
|
|
75 |
def trace(s):
|
|
|
76 |
global fTrace
|
|
|
77 |
if fTrace: print s
|
|
|
78 |
return
|
|
|
79 |
|
|
|
80 |
def findWinner(winners, losers, tally, quota, nWinners):
|
|
|
81 |
for candidate in tally.keys():
|
|
|
82 |
if candidate not in winners and len(tally[candidate]) >= quota:
|
|
|
83 |
return candidate
|
|
|
84 |
|
|
|
85 |
# Check to see if only enough candidates remain
|
|
|
86 |
n = 0
|
|
|
87 |
last = ""
|
|
|
88 |
for candidate in tally.keys():
|
|
|
89 |
if candidate not in winners and candidate not in losers:
|
|
|
90 |
last = candidate
|
|
|
91 |
n = n + 1
|
|
|
92 |
if nWinners - len(winners) >= n:
|
|
|
93 |
return last
|
|
|
94 |
return
|
|
|
95 |
|
|
|
96 |
def redistributeWinner(winner, winners, losers, tally, quota):
|
|
|
97 |
excess = len(tally[winner]) - quota
|
|
|
98 |
if excess <= 0:
|
|
|
99 |
trace("\tno excess ballots to redistribute")
|
|
|
100 |
else:
|
|
|
101 |
trace("\tredistributing %d excess ballot(s) at random from %s" %
|
|
|
102 |
(excess, winner))
|
|
|
103 |
while len(tally[winner]) > quota:
|
|
|
104 |
i = int(random.uniform(0, len(tally[winner])))
|
|
|
105 |
trace("\trandom choice = ballot %d" % (i+1))
|
|
|
106 |
ballot = tally[winner][i]
|
|
|
107 |
tally[winner] = tally[winner][0:i] + tally[winner][i+1:]
|
|
|
108 |
redistributeBallot(ballot, winner, winners, losers, tally)
|
|
|
109 |
traceTally(quota, tally)
|
|
|
110 |
|
|
|
111 |
def redistributeBallot(ballot, candidateFrom, winners, losers, tally):
|
|
|
112 |
for candidateTo in ballot:
|
|
|
113 |
if candidateTo not in winners and candidateTo not in losers:
|
|
|
114 |
trace("\tto %s: %s" % (candidateTo, ballot))
|
|
|
115 |
if not tally.has_key(candidateTo): tally[candidateTo] = []
|
|
|
116 |
tally[candidateTo].append(ballot)
|
|
|
117 |
ballot = ""
|
|
|
118 |
break
|
|
|
119 |
if ballot:
|
|
|
120 |
trace("\tineffective ballot dropped: %s" % ballot)
|
|
|
121 |
|
|
|
122 |
def findLoser(losers, winners, tally):
|
|
|
123 |
cMin = sys.maxint # least number of votes for candidate loser
|
|
|
124 |
lMin = [] # list of candidates with least votes
|
|
|
125 |
for c in tally.keys():
|
|
|
126 |
if c not in losers and c not in winners and len(tally[c]) <= cMin:
|
|
|
127 |
if len(tally[c]) == cMin:
|
|
|
128 |
lMin.append(c)
|
|
|
129 |
else:
|
|
|
130 |
lMin = [c]
|
|
|
131 |
cMin = len(tally[c])
|
|
|
132 |
trace("\nELIMINATING LOW CANDIDATE RANDOMLY FROM %s" % lMin)
|
|
|
133 |
if len(lMin) == 0:
|
|
|
134 |
return None
|
|
|
135 |
else:
|
|
|
136 |
return random.choice(lMin)
|
|
|
137 |
|
|
|
138 |
def redistributeLoser(loser, losers, winners, tally, quota):
|
|
|
139 |
excess = len(tally[loser])
|
|
|
140 |
if excess <= 0:
|
|
|
141 |
trace("\tno ballots to redistribute")
|
|
|
142 |
else:
|
|
|
143 |
trace("\tredistributing %d ballot(s) from %s" % (excess, loser))
|
|
|
144 |
while len(tally[loser]) > 0:
|
|
|
145 |
ballot = tally[loser][0]
|
|
|
146 |
tally[loser] = tally[loser][1:]
|
|
|
147 |
redistributeBallot(ballot, loser, winners, losers, tally)
|
|
|
148 |
traceTally(quota, tally)
|
|
|
149 |
return
|
|
|
150 |
|
|
|
151 |
def traceTally(quota, tally):
|
|
|
152 |
global fTrace
|
|
|
153 |
if not fTrace: return
|
|
|
154 |
trace("\nCURRENT ASSIGNMENT OF BALLOTS (%d needed to win)" % quota)
|
|
|
155 |
for candidate in tally.keys():
|
|
|
156 |
trace("\t%s:" % candidate)
|
|
|
157 |
for ballot in tally[candidate]:
|
|
|
158 |
trace("\t\t%s" % ballot)
|
|
|
159 |
return
|
|
|
160 |
|
|
|
161 |
# The basic Single Transferable Vote algorithm with Hare quota
|
|
|
162 |
#
|
|
|
163 |
# while winners < nWinners:
|
|
|
164 |
# if a candidate has more than quota votes:
|
|
|
165 |
# redistribute excess votes to next priority candidate
|
|
|
166 |
# else:
|
|
|
167 |
# eliminate lowest ranking candidate
|
|
|
168 |
# redistribute wasted votes to next priority candidate
|
|
|
169 |
#
|
|
|
170 |
def dotally(nWinners, ballots):
|
|
|
171 |
nBallots = len(ballots)
|
|
|
172 |
quota = int(math.ceil((nBallots + 1.0)/(nWinners + 1)))
|
|
|
173 |
|
|
|
174 |
trace("INPUT SUMMARY")
|
|
|
175 |
trace("\t%d ballots" % nBallots)
|
|
|
176 |
trace("\tChoosing %s winners" % nWinners)
|
|
|
177 |
trace("\tNeed ceil((%d + 1)/(%d + 1)) = %d ballots to win" %
|
|
|
178 |
(nBallots, nWinners, quota))
|
|
|
179 |
|
|
|
180 |
# Create initial tally
|
|
|
181 |
#
|
|
|
182 |
tally = {}
|
|
|
183 |
for ballot in ballots:
|
|
|
184 |
candidate = ballot[0]
|
|
|
185 |
if not tally.has_key(candidate):
|
|
|
186 |
tally[candidate] = []
|
|
|
187 |
tally[candidate].append(ballot)
|
|
|
188 |
traceTally(quota, tally)
|
|
|
189 |
|
|
|
190 |
winners = []
|
|
|
191 |
losers = []
|
|
|
192 |
|
|
|
193 |
while len(winners) < nWinners:
|
|
|
194 |
winner = findWinner(winners, losers, tally, quota, nWinners)
|
|
|
195 |
if winner:
|
|
|
196 |
winners.append(winner)
|
|
|
197 |
trace("\nSELECTION #%d: %s" % (len(winners), winner))
|
|
|
198 |
redistributeWinner(winner, winners, losers, tally, quota)
|
|
|
199 |
else:
|
|
|
200 |
loser = findLoser(losers, winners, tally)
|
|
|
201 |
if loser:
|
|
|
202 |
losers.append(loser)
|
|
|
203 |
trace("\nELIMINATED: %s" % loser)
|
|
|
204 |
redistributeLoser(loser, losers, winners, tally, quota)
|
|
|
205 |
else:
|
|
|
206 |
trace("Not enough chosen candidates to fill all positions")
|
|
|
207 |
break
|
|
|
208 |
|
|
|
209 |
return winners
|
|
|
210 |
|
|
|
211 |
# Parse input file
|
|
|
212 |
#
|
|
|
213 |
# input: lines of comma-separated values
|
|
|
214 |
# nWinners, ...ignored fields...
|
|
|
215 |
# candidate1, ballot1rank, ballot2rank, ...
|
|
|
216 |
# candidate2, ballot1rank, ballot2rank, ...
|
|
|
217 |
#
|
|
|
218 |
# output: list of lists of ballots
|
|
|
219 |
# [[1stcandbal1, 2ndcandbal1, ...], [1stcandbal2, 2ndcandbal2, ...], ...]
|
|
|
220 |
|
|
|
221 |
def parsecontents(contents):
|
|
|
222 |
lines = string.split(contents, "\r\n")
|
|
|
223 |
fields = string.split(lines[0], ",")
|
|
|
224 |
nWinners = int(fields[0])
|
|
|
225 |
|
|
|
226 |
votes = []
|
|
|
227 |
for line in lines[1:]:
|
|
|
228 |
fields = string.split(line, ",")
|
|
|
229 |
candidate = fields[0]
|
|
|
230 |
positions = fields[1:]
|
|
|
231 |
ballotnumber = 0
|
|
|
232 |
for position in positions:
|
|
|
233 |
if position:
|
|
|
234 |
votes.append([ballotnumber, int(position), candidate])
|
|
|
235 |
ballotnumber = ballotnumber + 1
|
|
|
236 |
|
|
|
237 |
votes.sort()
|
|
|
238 |
|
|
|
239 |
ballots = []
|
|
|
240 |
ballotnumber = ""
|
|
|
241 |
ballot = ""
|
|
|
242 |
for triple in votes:
|
|
|
243 |
if ballotnumber == triple[0]:
|
|
|
244 |
ballot.append(triple[2])
|
|
|
245 |
else:
|
|
|
246 |
if ballot:
|
|
|
247 |
ballots.append(ballot)
|
|
|
248 |
ballot = [triple[2]]
|
|
|
249 |
ballotnumber = triple[0]
|
|
|
250 |
|
|
|
251 |
ballots.append(ballot)
|
|
|
252 |
return nWinners, ballots
|
|
|
253 |
|
|
|
254 |
def main():
|
|
|
255 |
global fTrace
|
|
|
256 |
emitPreHTML(formaction)
|
|
|
257 |
|
|
|
258 |
form = cgi.FieldStorage()
|
|
|
259 |
|
|
|
260 |
if not form:
|
|
|
261 |
emitHTML("Enter file name and press a button to see results.")
|
|
|
262 |
elif form.has_key("fetch"):
|
|
|
263 |
source = open(formaction).read()
|
|
|
264 |
print cgi.escape(source)
|
|
|
265 |
elif not form.has_key("name"):
|
|
|
266 |
emitHTML("Error: no file received")
|
|
|
267 |
elif not form["name"].filename:
|
|
|
268 |
emitHTML("Error: file name missing")
|
|
|
269 |
else:
|
|
|
270 |
name = form["name"].filename
|
|
|
271 |
contents = form["name"].value
|
|
|
272 |
|
|
|
273 |
trace("INPUT FILE")
|
|
|
274 |
trace(contents)
|
|
|
275 |
|
|
|
276 |
nWinners, ballots = parsecontents(contents)
|
|
|
277 |
if form.has_key("run1"):
|
|
|
278 |
results = dotally(nWinners, ballots)
|
|
|
279 |
print "\nFINAL RESULTS"
|
|
|
280 |
for winner in results:
|
|
|
281 |
print "\t%s" % winner
|
|
|
282 |
elif form.has_key("run1000"):
|
|
|
283 |
print "RUNNING 1000 TIMES"
|
|
|
284 |
fTrace = 0
|
|
|
285 |
summary = {}
|
|
|
286 |
for i in range(1000):
|
|
|
287 |
results = str(dotally(nWinners, ballots))
|
|
|
288 |
# print "Run %2d: %s" % (i+1, results)
|
|
|
289 |
if not summary.has_key(results):
|
|
|
290 |
summary[results] = 0
|
|
|
291 |
summary[results] = summary[results] + 1
|
|
|
292 |
print "\nSUMMARY"
|
|
|
293 |
l = summary.items()
|
|
|
294 |
l.sort(lambda x,y: cmp(y[1], x[1]))
|
|
|
295 |
for pair in l:
|
|
|
296 |
print "%2d %s" % (pair[1], pair[0])
|
|
|
297 |
elif form.has_key("convert"):
|
|
|
298 |
print "Convert feature not supported yet"
|
|
|
299 |
else:
|
|
|
300 |
print "UNEXPECTED SUBMIT BUTTON: %s" % form
|
|
|
301 |
|
|
|
302 |
emitPostHTML()
|
|
|
303 |
return
|
|
|
304 |
|
|
|
305 |
main()
|