1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378
//! Meek STV method //! //! [Meek STV](http://www.dia.govt.nz/diawebsite.NSF/Files/meekm/%24file/meekm.pdf) is a popular //! form of Single Transferable Vote election; it allows for electing multiple candidates. //! //! In this method, vote is spread across candidates specified on the ballot, and this spread is //! adjusted in a number of rounds as candidates are progressively eliminated or elected. //! Undecided candidates get the whole part of vote that reaches them, eliminated get none, finally //! elected are only given enough for its total support to reach quota. //! Part of vote that reaches the end of the ballot goes to excess and lowers the quota. //! //! In each round, votes are spread, total supports are gathered, and candidates which reach the //! quota are elected; if all seats are taken, the algorithm stops. //! If no-one can be elected, candidate with a lowest support is eliminated. //! Finally, the algorithm loops back to the next round. //! //! This implementation uses fixed point arithmetic with a customisable amount of decimal digits. //! Similarly, it can use various quota functions; Hagenbach-Bischoff which is used in the AS123 //! paper, Hare or Droop. //! //! # Examples //! ``` //! use wybr::{Tally,Meek,Outcome}; //! //! //Load the example from the AS123 paper //! let tally=Tally::from_blt_file("examples/a123.blt").unwrap(); //! //! //Perform election with default parameters //! let outcome=Meek::new(&tally).run().unwrap(); //! let mut winners:Vec<String>=outcome.elected_names().collect(); //! //Even though outcome is deterministic... //! assert!(outcome.deterministic()); //! //...order may depend on HashSet order, hence we sort to compare //! winners.sort_unstable(); //! assert_eq!(winners,vec!["Adam","Donald"]); //! //! //Perform election ignoring the withdrawal of Basil from the blt file //! let outcome=Meek::new(&tally).withdraw(vec![]).run().unwrap(); //! let mut winners:Vec<String>=outcome.elected_names().collect(); //! winners.sort_unstable(); //! assert_eq!(winners,vec!["Adam","Charlotte"]); //! //! //Also change quota to Hare //! use wybr::Quota; //! let outcome=Meek::new(&tally).withdraw(vec![]).quota(Quota::Hare).run().unwrap(); //! let mut winners:Vec<String>=outcome.elected_names().collect(); //! winners.sort_unstable(); //! assert_eq!(winners,vec!["Adam","Basil"]); //! //! //Perform Warren election with default parameters //! use wybr::Transfer; //! let outcome=Meek::new(&tally).transfer(Transfer::Warren).run().unwrap(); //! let mut winners:Vec<String>=outcome.elected_names().collect(); //! winners.sort_unstable(); //! assert_eq!(winners,vec!["Adam","Donald"]); //! ``` use self::ElectionError::*; use self::Quota::*; use crate::common::{ElectionError, Quota, Transfer}; use crate::outcome::GenericOutcome; use crate::prng::Prng; use crate::tally::{Tally, VoteTree}; use std::collections::{HashMap, HashSet}; ///A builder for the setup of a Meek count. /// ///See [the module level documentation](index.html) for more. /// ///Default configuration can be generated with `Meek::new(tally)`, where `tally` is a ///`VoteTree` object. Count is triggered by the `run()` method, which returns a vector of winners, ///or an error. pub struct Meek<'a> { tally: &'a VoteTree, seats: Option<u32>, withdrawn: Vec<u32>, transfer: Transfer, quota: Quota, digits: u32, seed: u32, } impl<'a> Meek<'a> { ///Acquire reference to a vote tally and initiate default configuration, which can be altered ///with other builder methods. ///The default configuration involves using Hagenbach-Bischoff quota, Meek vote transfer mode, ///seats number and withdraw list pulled from the tally, 6 digits of fixed-point arithmetic, ///finally seed set to 21. pub fn new(tally: &'a VoteTree) -> Self { let mut withdrawn: Vec<u32> = Vec::new(); tally.map_withdrawn(|c| { withdrawn.push(c); }); Self { tally, quota: HagenbachBischoff, transfer: Transfer::Meek, withdrawn, seats: Some(tally.get_seats()), digits: 6, seed: 21, } } ///Alters the random seed potentially used by the election algorithm to break ties. pub fn seed(&mut self, seed: u32) -> &mut Self { self.seed = seed; self } ///Alters the number of seats (candidates to be elected). pub fn seats(&mut self, seats: u32) -> &mut Self { self.seats = Some(seats); self } ///Alters the number of fixed-point digits used. /// ///Seventeen is max (enforced in `run()`); also, 10 ^ digits * total votes in tally must be smaller ///than 2 ^ 64. pub fn digits(&mut self, digits: u32) -> &mut Self { self.digits = digits; self } ///Alter the quota calculation method; see `Quota` type for details. /// ///The default is `HagenbachBischoff` in compatibility with [Algorithm 123](http://www.prsa.org.au/meek_algorithm_1987.pdf), ///but it is good to consider using `Hare` in order to get most of STV. pub fn quota(&mut self, quota: Quota) -> &mut Self { self.quota = quota; self } ///Alter the vote transfer method; see `Transfer` type for details. /// ///In general, Meek algorithm is Meek with the default `Transfer::Meek`; with ///`Transfer::Warren` is becomes Warren STV. ///The naming in wybr reflects the fact that Warren proposed a relatively small change to the ///Meek idea; not insignificant, however. ///Also because this method is much more recognisable as Meek STV. pub fn transfer(&mut self, transfer: Transfer) -> &mut Self { self.transfer = transfer; self } ///Alter a list of withdrawn candidates, which are not considered in count. pub fn withdraw<I>(&mut self, withdraw: I) -> &mut Self where I: IntoIterator<Item = u32>, { self.withdrawn.clear(); for e in withdraw.into_iter() { self.withdrawn.push(e); } self } /// Performs Meek STV election, returns `Vec<u32>` with IDs of winners, or an `ElectionError`. /// /// Aims to be compatible with [Algorithm 123](http://www.prsa.org.au/meek_algorithm_1987.pdf), /// though uses fixed-point arithmetic. /// /// # Errors /// * `NotEnoughCandidates`, in case there is less candidates then seats or no votes, /// * `FixedPointDigitsTooMany`, in case there is too many ballots for a given `digits` value, or /// when `digits` is higher than 17, which is somewhat insane. /// /// # Notes /// In a pathological case, it may take a lot of time, but not infinite (at most ~ number of /// candidates ^ 2 * 10 ^ digits). /// Fixed point stuff works by multiplying almost everything by 10^base and fitting the result in /// u64; when you have like billions of ballots and `digits` of 9, it may become tight. /// /// Votes are also compared to be greater or equal with quota, even when `quota` is `HagenbachBischoff`; when /// it seems that more candidates then seats are going to be elected, random tie breaking is used. /// /// For seats==1, result will be almost certainly identical to this of `irv`, depending on the /// quota method (IRV effectively uses `Hare`). pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> { let seats = self.seats.unwrap_or(1); let candidates = self.tally.get_candidates(); if self.digits > 17 { return Err(FixedPointDigitsTooMany); } let base = 10_u64.pow(self.digits); if self.tally.ballot_count().checked_mul(base).is_none() { return Err(FixedPointDigitsTooMany); } let mut elected: Vec<u32> = Vec::new(); let mut resolved: HashSet<u32> = HashSet::new(); //Initial weights are 1, so base/base let mut weights: HashMap<u32, u64> = (0..candidates).map(|c| (c, base)).collect(); //Remove withdrawn, effectively zeroing their weight for c in &self.withdrawn { weights.remove(c); resolved.insert(*c); } if weights.len() < seats as usize { return Err(NotEnoughCandidates); } let mut rnd = Prng::new(self.seed); loop { //We have to adjust weights for the elected candidates let (_excess, mut score, quota) = loop { let (excess, score) = self.tally.transfer_votes_fp(&weights, base, Transfer::Meek); let useful_votes = score.values().sum(); let quota = match self.quota { Hare => (useful_votes, u64::from(seats)), HareInt => (((useful_votes / u64::from(seats)) / base) * base, 1), Droop => ( ((useful_votes / (u64::from(seats) + 1)) / base + 1) * base, 1, ), HagenbachBischoff => (useful_votes, u64::from(seats) + 1), }; let mut stable = true; for ec in &elected { //Weights cannot go up, so we enforce that over truncation errors if quota.0 > quota.1 * score[ec] { continue; } let new_weight = (weights[ec] * quota.0) / (quota.1 * score[ec]); stable = stable && weights .insert(*ec, new_weight) .map_or(false, |old_weight| old_weight == new_weight) } if stable { break (excess, score, quota); } }; score.retain(|c, _| !resolved.contains(c)); let mut electable: Vec<u32> = score .iter() .filter_map(|(&c, &s)| { if s * quota.1 >= quota.0 { Some(c) } else { None } }) .collect(); if !electable.is_empty() { //We have candidates to elect; but maybe too many due to low quota? while electable.len() + elected.len() > seats as usize { let to_remove = rnd.random_usindex(electable.len()); electable.swap_remove(to_remove); } //We're clear now to elect for &e in &electable { elected.push(e); resolved.insert(e); } //Maybe we're done? if elected.len() == seats as usize { return Ok(GenericOutcome::new( elected.iter().cloned(), self.withdrawn.iter().cloned(), candidates, rnd.sealed(), self.tally.get_meta(), )); } } else { //No one to elect, someone has to be removed let min_score = score.values().min(); let mut worse: Vec<u32> = score .iter() .filter_map(|(c, &s)| { min_score.and_then(|&ms| if s == ms { Some(*c) } else { None }) }) .collect(); if worse.is_empty() { return Err(NotEnoughCandidates); } else { worse.sort_unstable(); //For stable random selection let looser = rnd.only_or_random(&worse).unwrap(); weights.remove(&looser); } } } } } #[cfg(test)] mod tests { use super::*; use crate::Outcome; #[test] fn meek_withdrawn() { let x = [ (3, vec![0, 2, 3]), (4, vec![0, 2, 1]), (2, vec![3, 0, 2]), (1, vec![1]), (2, vec![1, 3, 2, 0]), (1, vec![2, 3, 1]), ] .iter() .collect(); assert_eq!( Meek::new(&x) .seats(2) .withdraw(vec![1]) .quota(Quota::Hare) .run() .unwrap() .elected() .collect::<Vec<u32>>(), vec![0, 3] ); } #[test] fn meek_alts() { let x = [ (3, vec![0, 2, 3]), (4, vec![0, 2, 1]), (2, vec![3, 0, 2]), (1, vec![1]), (2, vec![1, 3, 2, 0]), (1, vec![2, 3, 1]), ] .iter() .collect(); let mut stub = Meek::new(&x); stub.seats(2).digits(6).seed(97); assert_eq!( stub.run().unwrap().elected().collect::<Vec<u32>>(), vec![0, 2] ); assert_eq!( stub.quota(Quota::Hare) .run() .unwrap() .elected() .collect::<Vec<u32>>(), vec![0, 1] ); assert_eq!( stub.transfer(Transfer::Warren) .run() .unwrap() .elected() .collect::<Vec<u32>>(), vec![0, 1] ); } #[test] fn meek_alts_more() { let x = [ (3, vec![0, 2, 3]), (4, vec![0, 2, 1]), (2, vec![3, 0, 2]), (1, vec![1]), (2, vec![1, 3, 2, 0]), (1, vec![2, 3, 1]), ] .iter() .collect(); let mut stub = Meek::new(&x); stub.seats(2).digits(6).seed(97); use Quota::*; for quota in vec![Hare, HareInt, Droop, HagenbachBischoff] { for transfer in vec![Transfer::Warren, Transfer::Meek] { assert!(stub.quota(quota).transfer(transfer).run().is_ok()); } } } #[test] fn meek_empty() { let x = [].iter().collect(); match Meek::new(&x).run().unwrap_err() { ElectionError::NotEnoughCandidates => (), _ => unreachable!(), }; } }