wybr/methods/nanson.rs
1//! Nanson's method
2//!
3//! [Nanson'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 all candidates with Borda scores smaller or equal than average are 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 among candidates which reached the
10//! final round.
11//!
12//! # Examples
13//!
14//! ```
15//! use wybr::{Tally,Nanson,Outcome};
16//!
17//! //Load the Tennessee Wikipedia example
18//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
19//! let mut nanson=Nanson::new(&tally);
20//!
21//! //Perform simple election with default, Borda1 rules
22//! let outcome=Nanson::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 Nanson<'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 Nanson count.
45///
46///See [the module level documentation](index.html) for more.
47///
48///Default configuration can be generated with `Nanson::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> Nanson<'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 Nanson election; returns the ID of a winner, or an `ElectionError`.
104 ///
105 /// # Notes
106 /// Nanson'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 Nanson 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 let average = (scores.values().map(|x| u128::from(*x)).sum::<u128>()
134 / (scores.len() as u128)) as u64;
135 let mut elim_c: usize = 0;
136 let mut winner: Option<u32> = None;
137 for (c, s) in &scores {
138 if *s <= average {
139 eliminated.insert(*c);
140 elim_c += 1;
141 } else if winner.is_none() {
142 winner = Some(*c);
143 } else {
144 winner = None;
145 }
146 }
147 //Maybe we only have one candidate left?
148 if let Some(x) = winner {
149 break x;
150 }
151
152 //Maybe we have eliminated everyone?
153 if elim_c == scores.len() {
154 //This means there is a tie and we need to back-track elimination
155 //and select random one from the start of this round
156 let mut winners: Vec<u32> = scores.keys().cloned().collect();
157 winners.sort_unstable();
158 //We have checked earlier, so someone is in winners
159 break rnd.only_or_random(&winners).unwrap();
160 };
161 };
162
163 Ok(GenericOutcome::new(
164 Some(winner),
165 self.withdraw.iter().cloned(),
166 self.tally.get_candidates(),
167 rnd.sealed(),
168 self.tally.get_meta(),
169 ))
170 }
171}
172
173#[cfg(test)]
174mod tests {
175 use super::*;
176 use crate::outcome::Outcome;
177 #[test]
178 fn demo() {
179 //Load the Tennessee Wikipedia example
180 let tally = Tally::from_blt_file("examples/tennessee.blt").unwrap();
181 //Perform simple election with default, Borda1 rules
182 let outcome = Nanson::new(&tally).run().unwrap();
183 assert!(outcome.deterministic());
184 assert_eq!(outcome.winner_name().unwrap(), "Nashville");
185 }
186 #[test]
187 fn with_tie() {
188 let x = [
189 (10, vec![0, 1]),
190 (10, vec![1, 0]),
191 (5, vec![2, 3]),
192 (5, vec![3, 2]),
193 ]
194 .iter()
195 .collect();
196 let mut stub = Nanson::new(&x);
197 stub.seed(97);
198 let ans = stub.kind(Borda0).run().unwrap();
199 assert!(!ans.deterministic());
200 assert_eq!(ans.winner().unwrap(), 1);
201 stub.seed(99);
202 assert_eq!(stub.kind(Borda0).run().unwrap().winner().unwrap(), 0);
203 assert_eq!(stub.kind(Nauru).run().unwrap().winner().unwrap(), 0);
204 assert_eq!(stub.kind(Borda1).run().unwrap().winner().unwrap(), 0);
205 }
206 #[test]
207 fn single_cand() {
208 let x = [(10, vec![0])].iter().collect();
209 let ans = Nanson::new(&x).run().unwrap();
210 assert!(ans.deterministic());
211 assert_eq!(ans.winner().unwrap(), 0);
212 }
213 #[test]
214 fn empty() {
215 let x = [].iter().collect();
216 match Nanson::new(&x).run().unwrap_err() {
217 ElectionError::NotEnoughCandidates => (),
218 _ => unreachable!(),
219 }
220 }
221}