root / stv.py @ 79948f90
History | View | Annotate | Download (11.5 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 |
logging.basicConfig(format=LOGGER_FORMAT) |
55 |
logging.getLogger(SVT_LOGGER).setLevel(logging.INFO) |
56 |
|
57 |
class Ballot: |
58 |
"""A ballot class for Single Transferable Voting.
|
59 |
|
60 |
The ballot class contains an ordered list of candidates (in
|
61 |
decreasing order of preference) and an ordered list of weights
|
62 |
(new weights are added to the front of the list). The index of the
|
63 |
current preference (for the first count and subsequent rounds)
|
64 |
is also kept.
|
65 |
|
66 |
"""
|
67 |
|
68 |
candidates = [] |
69 |
weights = [1.0]
|
70 |
current_preference = 0
|
71 |
_value = 1.0
|
72 |
|
73 |
def __init__(self, candidates=[]): |
74 |
self.candidates = candidates
|
75 |
|
76 |
def add_weight(self, weight): |
77 |
self.weights.insert(0, weight) |
78 |
self._value *= weight
|
79 |
|
80 |
def get_value(self): |
81 |
return self._value |
82 |
|
83 |
def random_generator(num): |
84 |
if not random_sequence: |
85 |
print "Need random from " + num |
86 |
sys.exit() |
87 |
else:
|
88 |
return random_sequence.pop(0) |
89 |
|
90 |
def randomly_select_first(sequence, key, action, random_generator=None): |
91 |
"""Selects the first item of equals in a sorted sequence of items.
|
92 |
|
93 |
For the given sorted sequence, returns the first item if it
|
94 |
is different than the second; if there are ties so that there
|
95 |
are items with equal values, it randomly selects among those items.
|
96 |
The value of each item in the sequence is provided by applying the
|
97 |
function key to the item. The action parameter indicates the context
|
98 |
in which the random selection takes place (election or elimination).
|
99 |
random_generator, if given, is the function that produces the random
|
100 |
selection.
|
101 |
|
102 |
"""
|
103 |
|
104 |
first_value = key(sequence[0])
|
105 |
collected = [] |
106 |
for item in sequence: |
107 |
if key(item) == first_value:
|
108 |
collected.append(item) |
109 |
else:
|
110 |
break
|
111 |
index = 0
|
112 |
num_eligibles = len(collected)
|
113 |
if (num_eligibles > 1): |
114 |
if random_generator is None: |
115 |
index = int(random() * num_eligibles)
|
116 |
else:
|
117 |
index = random_generator(num_eligibles) |
118 |
selected = collected[index] |
119 |
logger = logging.getLogger(SVT_LOGGER) |
120 |
description = "{0} from {1} to {2}".format(selected, collected, action)
|
121 |
logger.info(LOG_MESSAGE.format(action=Action.RANDOM, desc=description)) |
122 |
return collected[index]
|
123 |
|
124 |
|
125 |
def redistribute_ballots(selected, hopefuls, allocated, weight, vote_count): |
126 |
"""Redistributes the ballots from selected to the hopefuls.
|
127 |
|
128 |
Redistributes the ballots currently allocated to the selected
|
129 |
candidate. The ballots are redistributed with the given weight.
|
130 |
The total ballot allocation is given by the allocated dict. The current
|
131 |
vote count is given by vote_count and is adjusted according to the
|
132 |
redistribution.
|
133 |
|
134 |
"""
|
135 |
|
136 |
logger = logging.getLogger(SVT_LOGGER) |
137 |
transferred = [] |
138 |
# Keep a hash of ballot moves for logging purposes.
|
139 |
# The hash comprises
|
140 |
moves = {} |
141 |
|
142 |
for ballot in allocated[selected]: |
143 |
reallocated = False
|
144 |
i = ballot.current_preference + 1
|
145 |
while not reallocated and i < len(ballot.candidates): |
146 |
recipient = ballot.candidates[i] |
147 |
if recipient in hopefuls: |
148 |
ballot.current_preference = i |
149 |
ballot.add_weight(weight) |
150 |
current_value = ballot.get_value() |
151 |
if recipient in allocated: |
152 |
allocated[recipient].append(ballot) |
153 |
else:
|
154 |
allocated[recipient] = [ballot] |
155 |
if recipient in vote_count: |
156 |
vote_count[recipient] += current_value |
157 |
else:
|
158 |
vote_count[recipient] = current_value |
159 |
vote_count[selected] -= current_value |
160 |
reallocated = True
|
161 |
if (selected, recipient, current_value) in moves: |
162 |
moves[(selected, recipient, current_value)] += 1
|
163 |
else:
|
164 |
moves[(selected, recipient, current_value)] = 1
|
165 |
transferred.append(ballot) |
166 |
else:
|
167 |
i += 1
|
168 |
for move, times in moves.iteritems(): |
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.info(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 |
candidates)) |
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) |
239 |
logger.info(LOG_MESSAGE.format(action=Action.ELECT, |
240 |
desc=best_candidate)) |
241 |
if surplus > 0: |
242 |
# Calculate the weight for this round
|
243 |
weight = float(surplus) / vote_count[best_candidate]
|
244 |
# Find the next eligible preference for each one of the ballots
|
245 |
# cast for the candidate, and transfer the vote to that
|
246 |
# candidate with its value adjusted by the correct weight.
|
247 |
redistribute_ballots(best_candidate, hopefuls, allocated, |
248 |
weight, vote_count) |
249 |
# If there is no surplus, take the least hopeful candidate
|
250 |
# (i.e., the hopeful candidate with the less votes) and
|
251 |
# redistribute that candidate's votes.
|
252 |
else:
|
253 |
hopefuls_sorted.reverse() |
254 |
worst_candidate = randomly_select_first(hopefuls_sorted, |
255 |
key=vote_count.get, |
256 |
action=Action.ELIMINATE, |
257 |
random_generator=rnd_gen) |
258 |
hopefuls.remove(worst_candidate) |
259 |
logger.info(LOG_MESSAGE.format(action=Action.ELIMINATE, |
260 |
desc=worst_candidate)) |
261 |
redistribute_ballots(worst_candidate, hopefuls, allocated, 1.0,
|
262 |
vote_count) |
263 |
|
264 |
current_round += 1
|
265 |
num_hopefuls = len(hopefuls)
|
266 |
num_elected = len(elected)
|
267 |
|
268 |
return elected, vote_count
|
269 |
|
270 |
if __name__ == "__main__": |
271 |
parser = argparse.ArgumentParser(description='Perform STV')
|
272 |
parser.add_argument('--ballots', nargs='?', default='sys.stdin', |
273 |
dest='ballots_file', help='input ballots file') |
274 |
parser.add_argument('--seats', nargs='?', default=0, |
275 |
dest='seats', help='number of seats') |
276 |
args = parser.parse_args() |
277 |
ballots = [] |
278 |
ballots_file = sys.stdin |
279 |
if args.ballots_file != 'sys.stdin': |
280 |
ballots_file = open(args.ballots_file)
|
281 |
ballots_reader = csv.reader(ballots_file, delimiter=',',
|
282 |
quotechar='"',
|
283 |
skipinitialspace = True)
|
284 |
for ballot in ballots_reader: |
285 |
ballots.append(Ballot(ballot)) |
286 |
|
287 |
if args.seats == 0: |
288 |
args.seats = len(ballots) / 2 |
289 |
(elected, vote_count) = count_stv(ballots, int(args.seats))
|
290 |
|
291 |
print "Results:" |
292 |
for candidate in elected: |
293 |
print candidate, vote_count[candidate]
|