wybr/methods/baldwin.rs
1//! Baldwin's method
2//!
3//! [Baldwin's method](https://en.wikipedia.org/wiki/Nanson's_method) is an extension of Borda count
4//! in which candidates are progressively eliminated rather than ranked once.
5//! Namely, in each round one candidate with smallest Borda score is eliminated, so
6//! that the ballots are shifted giving more points to other candidates.
7//! Such procedure is repeated until one winner is left.
8//!
9//! There can be a tie, in this case random tie breaking is used to select worse candidate among
10//! these with smallest score.
11//!
12//! # Examples
13//!
14//! ```
15//! use wybr::{Tally,Baldwin,Outcome};
16//!
17//! //Load the Tennessee Wikipedia example
18//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
19//! let mut nanson=Baldwin::new(&tally);
20//!
21//! //Perform simple election with default, Borda1 rules
22//! let outcome=Baldwin::new(&tally).run().unwrap();
23//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
24//! ```
25
26use crate::common::BordaKind;
27use crate::outcome::GenericOutcome;
28use crate::prng::Prng;
29use crate::tally::Tally;
30use crate::ElectionError;
31use crate::VoteTree;
32use std::collections::HashSet;
33
34use BordaKind::*;
35
36pub struct Baldwin<'a> {
37 tally: &'a VoteTree,
38 borda_kind: BordaKind,
39 withdraw: HashSet<u32>,
40 max_rank: Option<u32>,
41 seed: u32,
42}
43
44///A builder for the setup of a Baldwin count.
45///
46///See [the module level documentation](index.html) for more.
47///
48///Default configuration can be generated with `Baldwin::new(&tally)`, where `tally` is a `VoteTree`
49///object.
50///Count is triggered by the `run()` method, which returns a solitary winner, or an error.
51impl<'a> Baldwin<'a> {
52 ///Acquire reference to a vote tally and initiate default configuration, which can be altered
53 ///with other builder methods.
54 ///The default configuration involves using `Borda1` kind, withdraw list pulled from the tally,
55 ///maximal rank equal to the actual maximal rank found in the tally, finally for seed equal to 21.
56 pub fn new(tally: &'a VoteTree) -> Self {
57 let mut withdraw: HashSet<u32> = HashSet::new();
58 tally.map_withdrawn(|c| {
59 withdraw.insert(c);
60 });
61 Self {
62 tally,
63 borda_kind: Borda1,
64 withdraw,
65 max_rank: None,
66 seed: 21,
67 }
68 }
69 ///Alters the random seed potentially used by the election algorithm to break ties.
70 pub fn seed(&mut self, seed: u32) -> &mut Self {
71 self.seed = seed;
72 self
73 }
74 ///Alter the Borda election kind; see `BordaKind` type for details.
75 pub fn kind(&mut self, kind: BordaKind) -> &mut Self {
76 self.borda_kind = kind;
77 self
78 }
79 ///Alter the maximal rank used for election; ranks are count from zero, so when this value is
80 ///x, up to (x + 1)-th vote is considered, while the later ones are discarded.
81 ///
82 ///Note that withdraws act before this filter, so vote A B C with `max_rank` 1 and B withdrawn
83 ///is interpreted as first preference is A, second is no-one.
84 pub fn max_rank(&mut self, max_rank: u32) -> &mut Self {
85 self.max_rank = Some(max_rank);
86 self
87 }
88 ///Alter a list of withdrawn candidates, which are not considered in count.
89 ///
90 ///A vote A B C with B withdrawn is interpreted as first preference is A, second is C, third is
91 ///no-one.
92 pub fn withdraw<I>(&mut self, withdraw: I) -> &mut Self
93 where
94 I: IntoIterator<Item = u32>,
95 {
96 self.withdraw.clear();
97 for e in withdraw.into_iter() {
98 self.withdraw.insert(e);
99 }
100 self
101 }
102
103 /// Performs Baldwin election; returns the ID of a winner, or an `ElectionError`.
104 ///
105 /// # Notes
106 /// Baldwin's method is essentially an iterated Borda election; on each iteration all candidates
107 /// with Borda score lower or equal than average are eliminated.
108 /// All parameters of the Baldwin method are identical to these of the Borda method.
109 ///
110 /// # Errors
111 /// * `ArithmeticOverflow`, when score numbers are too large to fit in u64; this is especially
112 /// likely with `Nauru` kind and insane `max_rank`, like 40+.
113 /// * `NotEnoughCandidates`, when there is no candidates or no votes.
114 pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> {
115 let mut rnd = Prng::new(self.seed);
116 use crate::methods::borda::Borda;
117 let mut borda = Borda::new(self.tally);
118 borda.kind(self.borda_kind);
119 if let Some(mr) = self.max_rank {
120 borda.max_rank(mr);
121 };
122
123 let mut eliminated: HashSet<u32> = HashSet::new();
124 for e in self.withdraw.iter() {
125 eliminated.insert(*e);
126 }
127
128 let winner = loop {
129 let scores = borda.withdraw(eliminated.iter().cloned()).scores()?;
130 if scores.is_empty() {
131 return Err(ElectionError::NotEnoughCandidates);
132 }
133 if scores.len() == 1 {
134 //We have only one candidate, hence it wins
135 break *scores.keys().next().unwrap();
136 }
137
138 let min = scores.values().min().unwrap();
139 let mut loosers: Vec<u32> = scores
140 .iter()
141 .filter_map(|(c, s)| if s == min { Some(*c) } else { None })
142 .collect();
143 loosers.sort_unstable();
144 let looser = rnd.only_or_random(&loosers).unwrap();
145
146 if scores.len() == 2 {
147 //We have one left, it must be a winner
148 break *scores.keys().find(|&&c| c != looser).unwrap();
149 }
150 eliminated.insert(looser);
151 };
152
153 Ok(GenericOutcome::new(
154 Some(winner),
155 self.withdraw.iter().cloned(),
156 self.tally.get_candidates(),
157 rnd.sealed(),
158 self.tally.get_meta(),
159 ))
160 }
161}
162
163#[cfg(test)]
164mod tests {
165 use super::*;
166 use crate::outcome::Outcome;
167 #[test]
168 fn demo() {
169 //Load the Tennessee Wikipedia example
170 let tally = Tally::from_blt_file("examples/tennessee.blt").unwrap();
171 //Perform simple election with default, Borda1 rules
172 let outcome = Baldwin::new(&tally).run().unwrap();
173 assert!(outcome.deterministic());
174 assert_eq!(outcome.winner_name().unwrap(), "Nashville");
175 }
176 #[test]
177 fn with_tie() {
178 let x = [
179 (10, vec![0, 1]),
180 (10, vec![1, 0]),
181 (5, vec![2, 3]),
182 (5, vec![3, 2]),
183 ]
184 .iter()
185 .collect();
186 let mut stub = Baldwin::new(&x);
187 stub.max_rank(1);
188 stub.seed(97);
189 let ans = stub.kind(Borda0).run().unwrap();
190 assert!(!ans.deterministic());
191 assert_eq!(ans.winner().unwrap(), 1);
192 stub.seed(99);
193 assert_eq!(stub.kind(Borda0).run().unwrap().winner().unwrap(), 1);
194 }
195}