root / stv.py @ d736e543
History | View | Annotate | Download (12.1 kB)
1 |
# Copyright 2011 GRNET S.A. All rights reserved.
|
---|---|
2 |
#
|
3 |
# Redistribution and use in source and binary forms, with or without
|
4 |
# modification, are permitted provided that the following conditions
|
5 |
# are met:
|
6 |
#
|
7 |
# 1. Redistributions of source code must retain the above copyright
|
8 |
# notice, this list of conditions and the following disclaimer.
|
9 |
#
|
10 |
# 2. Redistributions in binary form must reproduce the above
|
11 |
# copyright notice, this list of conditions and the following
|
12 |
# disclaimer in the documentation and/or other materials provided
|
13 |
# with the distribution.
|
14 |
#
|
15 |
# THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
|
16 |
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
|
17 |
# TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
|
18 |
# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
|
19 |
# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
|
20 |
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
|
21 |
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
|
22 |
# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
|
23 |
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
|
24 |
# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
|
25 |
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
26 |
# SUCH DAMAGE.
|
27 |
#
|
28 |
# The views and conclusions contained in the software and
|
29 |
# documentation are those of the authors and should not be interpreted
|
30 |
# as representing official policies, either expressed or implied, of
|
31 |
# GRNET S.A.
|
32 |
|
33 |
from operator import mul, itemgetter |
34 |
from random import random, seed |
35 |
import logging |
36 |
import sys |
37 |
import math |
38 |
import csv |
39 |
import argparse |
40 |
|
41 |
SVT_LOGGER = 'SVT'
|
42 |
LOGGER_FORMAT = '%(levelname)s %(message)s'
|
43 |
LOG_MESSAGE = "{action} {desc}"
|
44 |
|
45 |
class Action: |
46 |
COUNT_ROUND = "@ROUND"
|
47 |
TRANSFER = ">TRANSFER"
|
48 |
ELIMINATE = "-ELIMINATE"
|
49 |
ELECT = "+ELECT"
|
50 |
COUNT = ".COUNT"
|
51 |
RANDOM = "*RANDOM"
|
52 |
THRESHOLD = "^THRESHOLD"
|
53 |
|
54 |
class Ballot: |
55 |
"""A ballot class for Single Transferable Voting.
|
56 |
|
57 |
The ballot class contains an ordered list of candidates (in
|
58 |
decreasing order of preference) and an ordered list of weights
|
59 |
(new weights are added to the front of the list). The index of the
|
60 |
current preference (for the first count and subsequent rounds)
|
61 |
is also kept.
|
62 |
|
63 |
"""
|
64 |
|
65 |
candidates = [] |
66 |
weights = [1.0]
|
67 |
current_preference = 0
|
68 |
_value = 1.0
|
69 |
|
70 |
def __init__(self, candidates=[]): |
71 |
self.candidates = [ x.strip() for x in candidates] |
72 |
|
73 |
def add_weight(self, weight): |
74 |
self.weights.insert(0, weight) |
75 |
self._value *= weight
|
76 |
|
77 |
def get_value(self): |
78 |
return self._value |
79 |
|
80 |
def random_generator(num): |
81 |
if not random_sequence: |
82 |
print "Need random from " + num |
83 |
sys.exit() |
84 |
else:
|
85 |
return random_sequence.pop(0) |
86 |
|
87 |
def randomly_select_first(sequence, key, action, random_generator=None): |
88 |
"""Selects the first item of equals in a sorted sequence of items.
|
89 |
|
90 |
For the given sorted sequence, returns the first item if it
|
91 |
is different than the second; if there are ties so that there
|
92 |
are items with equal values, it randomly selects among those items.
|
93 |
The value of each item in the sequence is provided by applying the
|
94 |
function key to the item. The action parameter indicates the context
|
95 |
in which the random selection takes place (election or elimination).
|
96 |
random_generator, if given, is the function that produces the random
|
97 |
selection.
|
98 |
|
99 |
"""
|
100 |
|
101 |
first_value = key(sequence[0])
|
102 |
collected = [] |
103 |
for item in sequence: |
104 |
if key(item) == first_value:
|
105 |
collected.append(item) |
106 |
else:
|
107 |
break
|
108 |
index = 0
|
109 |
num_eligibles = len(collected)
|
110 |
if (num_eligibles > 1): |
111 |
if random_generator is None: |
112 |
index = int(random() * num_eligibles)
|
113 |
else:
|
114 |
index = random_generator(num_eligibles) |
115 |
selected = collected[index] |
116 |
logger = logging.getLogger(SVT_LOGGER) |
117 |
description = "{0} from {1} to {2}".format(selected, collected, action)
|
118 |
logger.info(LOG_MESSAGE.format(action=Action.RANDOM, desc=description)) |
119 |
return collected[index]
|
120 |
|
121 |
|
122 |
def redistribute_ballots(selected, hopefuls, allocated, weight, vote_count): |
123 |
"""Redistributes the ballots from selected to the hopefuls.
|
124 |
|
125 |
Redistributes the ballots currently allocated to the selected
|
126 |
candidate. The ballots are redistributed with the given weight.
|
127 |
The total ballot allocation is given by the allocated dict. The current
|
128 |
vote count is given by vote_count and is adjusted according to the
|
129 |
redistribution.
|
130 |
|
131 |
"""
|
132 |
|
133 |
logger = logging.getLogger(SVT_LOGGER) |
134 |
transferred = [] |
135 |
# Keep a hash of ballot moves for logging purposes.
|
136 |
# Keys are a tuple of the form (from_recipient, to_recipient, value)
|
137 |
# where value is the current value of the ballot. Each tuple points
|
138 |
# to the ballot being moved.
|
139 |
moves = {} |
140 |
|
141 |
for ballot in allocated[selected]: |
142 |
reallocated = False
|
143 |
i = ballot.current_preference + 1
|
144 |
while not reallocated and i < len(ballot.candidates): |
145 |
recipient = ballot.candidates[i] |
146 |
if recipient in hopefuls: |
147 |
ballot.current_preference = i |
148 |
ballot.add_weight(weight) |
149 |
current_value = ballot.get_value() |
150 |
if recipient in allocated: |
151 |
allocated[recipient].append(ballot) |
152 |
else:
|
153 |
allocated[recipient] = [ballot] |
154 |
if recipient in vote_count: |
155 |
vote_count[recipient] += current_value |
156 |
else:
|
157 |
vote_count[recipient] = current_value |
158 |
vote_count[selected] -= current_value |
159 |
reallocated = True
|
160 |
if (selected, recipient, current_value) in moves: |
161 |
moves[(selected, recipient, current_value)].append(ballot) |
162 |
else:
|
163 |
moves[(selected, recipient, current_value)] = [ballot] |
164 |
transferred.append(ballot) |
165 |
else:
|
166 |
i += 1
|
167 |
for move, ballots in moves.iteritems(): |
168 |
times = len(ballots)
|
169 |
description = "from {0} to {1} {2}*{3}={4}".format(move[0], |
170 |
move[1],
|
171 |
times, |
172 |
move[2],
|
173 |
times * move[2])
|
174 |
logger.debug(LOG_MESSAGE.format(action=Action.TRANSFER, |
175 |
desc=description)) |
176 |
allocated[selected][:] = [x for x in allocated[selected] |
177 |
if x not in transferred ] |
178 |
|
179 |
def count_stv(ballots, seats, rnd_gen=None): |
180 |
"""Performs a SVT vote for the given ballots and number of seats.
|
181 |
|
182 |
"""
|
183 |
|
184 |
allocated = {} # The allocation of ballots to candidates
|
185 |
vote_count = {} # A hash of ballot counts, indexed by candidates
|
186 |
candidates = [] # All candidates
|
187 |
elected = [] # The candidates that have been elected
|
188 |
hopefuls = [] # The candidates that may be elected
|
189 |
|
190 |
seed() |
191 |
|
192 |
threshold = (1 + len(ballots) / (seats + 1)) |
193 |
|
194 |
logger = logging.getLogger(SVT_LOGGER) |
195 |
logger.info(LOG_MESSAGE.format(action=Action.THRESHOLD, |
196 |
desc=threshold)) |
197 |
|
198 |
# Do initial count
|
199 |
for ballot in ballots: |
200 |
selected = ballot.candidates[0]
|
201 |
for candidate in ballot.candidates: |
202 |
if candidate not in candidates: |
203 |
candidates.append(candidate) |
204 |
vote_count[candidate] = 0
|
205 |
if selected in allocated: |
206 |
allocated[selected].append(ballot) |
207 |
else:
|
208 |
allocated[selected] = [ballot] |
209 |
vote_count[selected] += 1
|
210 |
|
211 |
# In the beginning, all candidates are hopefuls
|
212 |
hopefuls = [x for x in candidates] |
213 |
|
214 |
# Start rounds
|
215 |
current_round = 1
|
216 |
num_elected = len(elected)
|
217 |
num_hopefuls = len(hopefuls)
|
218 |
while num_elected < seats and num_hopefuls > 0: |
219 |
logger.info(LOG_MESSAGE.format(action=Action.COUNT_ROUND, |
220 |
desc=current_round)) |
221 |
# Log count
|
222 |
description = ';'.join(map(lambda x: "{0} = {1}".format(x, |
223 |
vote_count[x]), |
224 |
hopefuls)) |
225 |
logger.info(LOG_MESSAGE.format(action=Action.COUNT, |
226 |
desc=description)) |
227 |
hopefuls_sorted = sorted(hopefuls, key=vote_count.get, reverse=True ) |
228 |
# If there is a surplus try to redistribute the best candidate's votes
|
229 |
# according to their next preferences
|
230 |
surplus = vote_count[hopefuls_sorted[0]] - threshold
|
231 |
remaining_seats = seats - num_elected |
232 |
if surplus >= 0 or num_hopefuls <= remaining_seats: |
233 |
best_candidate = randomly_select_first(hopefuls_sorted, |
234 |
key=vote_count.get, |
235 |
action=Action.ELECT, |
236 |
random_generator=rnd_gen) |
237 |
hopefuls.remove(best_candidate) |
238 |
elected.append((best_candidate, current_round, |
239 |
vote_count[best_candidate])) |
240 |
logger.info(LOG_MESSAGE.format(action=Action.ELECT, |
241 |
desc=best_candidate |
242 |
+ " = " + str(vote_count[best_candidate]))) |
243 |
if surplus > 0: |
244 |
# Calculate the weight for this round
|
245 |
weight = float(surplus) / vote_count[best_candidate]
|
246 |
# Find the next eligible preference for each one of the ballots
|
247 |
# cast for the candidate, and transfer the vote to that
|
248 |
# candidate with its value adjusted by the correct weight.
|
249 |
redistribute_ballots(best_candidate, hopefuls, allocated, |
250 |
weight, vote_count) |
251 |
# If there is no surplus, take the least hopeful candidate
|
252 |
# (i.e., the hopeful candidate with the less votes) and
|
253 |
# redistribute that candidate's votes.
|
254 |
else:
|
255 |
hopefuls_sorted.reverse() |
256 |
worst_candidate = randomly_select_first(hopefuls_sorted, |
257 |
key=vote_count.get, |
258 |
action=Action.ELIMINATE, |
259 |
random_generator=rnd_gen) |
260 |
hopefuls.remove(worst_candidate) |
261 |
logger.info(LOG_MESSAGE.format(action=Action.ELIMINATE, |
262 |
desc=worst_candidate |
263 |
+ " = " + str(vote_count[worst_candidate]))) |
264 |
redistribute_ballots(worst_candidate, hopefuls, allocated, 1.0,
|
265 |
vote_count) |
266 |
|
267 |
current_round += 1
|
268 |
num_hopefuls = len(hopefuls)
|
269 |
num_elected = len(elected)
|
270 |
|
271 |
return elected, vote_count
|
272 |
|
273 |
if __name__ == "__main__": |
274 |
parser = argparse.ArgumentParser(description='Perform STV')
|
275 |
parser.add_argument('--ballots', nargs='?', default='sys.stdin', |
276 |
dest='ballots_file', help='input ballots file') |
277 |
parser.add_argument('--seats', nargs='?', default=0, |
278 |
dest='seats', help='number of seats') |
279 |
parser.add_argument('--loglevel', nargs='?', default=logging.INFO, |
280 |
dest='loglevel', help='logging level') |
281 |
args = parser.parse_args() |
282 |
logging.basicConfig(format=LOGGER_FORMAT) |
283 |
logging.getLogger(SVT_LOGGER).setLevel(args.loglevel) |
284 |
ballots = [] |
285 |
ballots_file = sys.stdin |
286 |
if args.ballots_file != 'sys.stdin': |
287 |
ballots_file = open(args.ballots_file)
|
288 |
ballots_reader = csv.reader(ballots_file, delimiter=',',
|
289 |
quotechar='"',
|
290 |
skipinitialspace = True)
|
291 |
for ballot in ballots_reader: |
292 |
ballots.append(Ballot(ballot)) |
293 |
|
294 |
if args.seats == 0: |
295 |
args.seats = len(ballots) / 2 |
296 |
(elected, vote_count) = count_stv(ballots, int(args.seats))
|
297 |
|
298 |
print "Results:" |
299 |
for result in elected: |
300 |
print result
|