wybr/methods/
ranked_pairs.rs

1//! Ranked pairs (Tideman) method
2//!
3//! [The ranked pairs](https://en.wikipedia.org/wiki/Ranked_pairs) or Tideman method considers each
4//! pair of candidates (i,j) and combines it with a score, which depends on how much candidate i
5//! beats candidate j in pairwise comparison.
6//! Then, pairs are ordered by decreasing score and sequentially either *locked*, that is added as
7//! an edge to a directed acyclic graph over candidates, or dropped, in case adding them would have
8//! cause a cycle in the graph and violate is DAG property.
9//!
10//! The winner is the only candidate in the resulting graph that is not beaten; if there are more
11//! unbeaten candidates, the election is considered unresolved.  There are three possible modes of
12//! scoring pairs, common to most Condorcet methods: `PairScore::Winning`, `PairScore::Margin` and
13//! `PairScore::Opposition`.
14//!
15//! By default, `Margin` option is used, as in the original Tideman formulation.  `Winning` is
16//! often seen in this method formulation; still, such approach is often called MAM or MMV.  In
17//! case of ties in sort, first the possibly low opposition vote is used, that is the number of
18//! votes which prefer j to i, and then pseudo-random order depending on the seed.
19//!
20//! # Examples
21//!
22//! ```
23//! use wybr::{Tally,RankedPairs,Outcome};
24//!
25//! //Load the Tennessee Wikipedia example
26//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
27//!
28//! //Perform simple election with default parameters
29//! let outcome=RankedPairs::new(&tally).run().unwrap();
30//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
31//!
32//! //Change pair score to `Winning`; this won't change the outcome, though
33//! use wybr::PairScore;
34//! let outcome=RankedPairs::new(&tally).pair_score(PairScore::Winning).run().unwrap();
35//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
36//! ```
37mod cand_pair;
38mod forced_dag;
39use self::PairScore::*;
40use crate::common::{ElectionError, PairScore};
41use crate::outcome::GenericOutcome;
42use crate::prng::Prng;
43use crate::tally::{Tally, VoteMatrix};
44use cand_pair::CandPair;
45use forced_dag::ForcedDag;
46
47///A builder for the setup of a Ranked Pairs count
48///
49///See [the module level documentation](index.html) for more.
50///
51///Default configuration can be generated with `RankedPairs::new(&tally)`, where `tally` is a
52///`VoteMatrix` object.
53///Count is triggered by the `run()` method, which returns a solitary winner, or an error.
54pub struct RankedPairs<'a> {
55    tally: &'a VoteMatrix,
56    pair_score: PairScore,
57    seed: u32,
58}
59impl<'a> RankedPairs<'a> {
60    ///Acquire reference to a vote matrix tally and initiate default configuration, which can be
61    ///altered with other builder methods.  The default configuration involves using Winning pair
62    ///scoring and random seed of 21.
63    pub fn new(tally: &'a VoteMatrix) -> Self {
64        Self {
65            tally,
66            pair_score: Winning,
67            seed: 21,
68        }
69    }
70
71    ///Alters the pair scoring method.
72    pub fn pair_score(&mut self, pair_score: PairScore) -> &mut Self {
73        self.pair_score = pair_score;
74        self
75    }
76
77    ///Alters the random seed potentially used by the election algorithm to break ties.
78    pub fn seed(&mut self, seed: u32) -> &mut Self {
79        self.seed = seed;
80        self
81    }
82
83    /// Performs ranked pairs (Tideman) election, returns winner ID or an `ElectionError`.
84    ///
85    /// The method considers each pair of candidates (i,j) and combines it with a score, which
86    /// depends on the mode.  Then, pairs are ordered by decreasing score and sequentially locked,
87    /// that is added as an edge to a directed acyclic graph over candidates, or dropped, in case
88    /// adding them would have cause a cycle in the graph and violate is DAG property.  The winner
89    /// is the only candidate in the resulting graph that is not beaten; if there are more unbeaten
90    /// candidates, the election is considered unresolved and `DegeneratedElectionGraph` error is
91    /// emitted.
92    ///
93    /// The score depends on the mode; also, for mode equal to Winning or Margin only winning pairs
94    /// are considered.  In case of ties in sort, first the possibly low opposition vote is used,
95    /// that is the number of votes which prefer j to i, and then pseudo-random order depending on
96    /// the seed.
97    ///
98    /// # Errors
99    /// * `NotEnoughCandidates`, in case there is no candidates.
100    /// * `DegeneratedElectionGraph`, in case when there is no winner in the final graph; this may
101    ///   happen for instance when the graph looks like this: `A->B<-C` or has isolated sub-graph,
102    ///   like this `A->D->C C->E` -- in both cases, A & B are equally good winners in light of
103    ///   ranked pairs method, but may be not equivalent in terms of actual preference, hence we
104    ///   don't want to use random tie breaking.  Anyhow, such situation happens extremely rarely in
105    ///   practice, especially when indifferent votes are disallowed (this is what wybr does).
106    ///
107    /// # Notes
108    /// Default mode for ranked pairs is `Margin`; `Winning` is often seen in the
109    /// definition of this method.  `Opposition` mode is similar to `Winning`, but affects
110    /// symmetric links (i & j so that d(i,j)=d(j,i)) -- instead of being thrown away as in other
111    /// modes, they are converted into unidirectional ones with a random direction.
112    pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> {
113        if self.tally.get_candidates() < 1 {
114            return Err(ElectionError::NotEnoughCandidates);
115        }
116        let mut rnd = Prng::new(self.seed);
117        let mut pairs: Vec<CandPair> = self
118            .tally
119            .pairs()
120            .filter_map(|((runner, opponent), (win, opposition))| {
121                let score: u64 = match (win > opposition, self.pair_score) {
122                    (true, PairScore::Margin) => win - opposition,
123                    (true, PairScore::Winning) => win,
124                    (_, PairScore::Opposition) => win,
125                    _ => 0,
126                };
127                if win > opposition {
128                    Some(CandPair::new(runner, opponent, score, opposition))
129                } else {
130                    None
131                }
132            })
133            .collect();
134
135        pairs.sort_unstable();
136        let mut dag = ForcedDag::new(self.tally.get_candidates());
137        while !pairs.is_empty() {
138            //Pull a group of CandPairs that are equivalent; this is usually just one
139            let mut group: Vec<CandPair> = Vec::new();
140            while group.is_empty() || pairs.ends_with(&group[0..1]) {
141                group.push(pairs.pop().unwrap());
142            }
143            if group.len() == 1 {
144                //Short-circuit when there are no determinism quirks
145                for x in &group {
146                    dag.add_edge(x.runner, x.opponent);
147                }
148            } else {
149                //Remove pairs that cannot be alone added to the graph
150                group.retain(|x| dag.try_edge(x.runner, x.opponent));
151
152                //Shuffle the order in group; but save rnd state to reset it if the operation was
153                //deterministic after all
154                rnd.push();
155                rnd.shuffle(&mut group);
156
157                //Add the edges that are left. First edge, if any, must be accepted.
158                //If any other edge is rejected, it could be put first and become accepted, hence we
159                //have a dependence on the order and the outcome is not deterministic
160                //NOTE: This is not equivalent to all, since we need to add all edges and
161                //we cannot short-circuit
162                #[allow(clippy::unnecessary_fold)]
163                if group
164                    .iter()
165                    .fold(true, |flag, x| flag && dag.add_edge(x.runner, x.opponent))
166                {
167                    rnd.pop().unwrap();
168                }
169            }
170        }
171        if let Ok(winner) = dag.get_winner() {
172            Ok(GenericOutcome::new(
173                Some(winner),
174                None,
175                self.tally.get_candidates(),
176                rnd.sealed(),
177                self.tally.get_meta(),
178            ))
179        } else {
180            Err(ElectionError::DegeneratedElectionGraph)
181        }
182    }
183}
184
185#[cfg(test)]
186mod tests {
187    use super::*;
188    use crate::Outcome;
189    #[test]
190    fn ranked_pairs_basic() {
191        //Tennessee
192        let x = VoteMatrix::with_vector_bycol(
193            //Tennessee
194            &vec![58, 58, 58, 42, 32, 32, 42, 68, 17, 42, 68, 83],
195        );
196        assert_eq!(
197            RankedPairs::new(&x)
198                .pair_score(PairScore::Margin)
199                .run()
200                .unwrap()
201                .winner()
202                .unwrap(),
203            1
204        );
205    }
206    #[test]
207    fn ranked_pairs_schulze_wiki() {
208        let x = VoteMatrix::with_vector_bycol(&vec![
209            25, 0, 0, 23, 0, 29, 0, 27, 26, 0, 28, 0, 30, 33, 0, 31, 0, 0, 24, 0,
210        ]);
211
212        assert_eq!(
213            RankedPairs::new(&x)
214                .pair_score(PairScore::Winning)
215                .run()
216                .unwrap()
217                .winner()
218                .unwrap(),
219            0
220        );
221    }
222    #[test]
223    fn ranked_pairs_no_wins() {
224        let x = VoteMatrix::with_vector_bycol(&vec![3, 3, 3, 3, 3, 3]);
225        let ans = RankedPairs::new(&x).pair_score(PairScore::Margin).run();
226        match ans.unwrap_err() {
227            ElectionError::DegeneratedElectionGraph => (),
228            _ => unreachable!(),
229        };
230    }
231    #[test]
232    fn ranked_pairs_co2() {
233        let x = VoteMatrix::with_vector_bycol(&vec![0, 0, 1, 1, 0, 0]);
234        let ans = RankedPairs::new(&x).pair_score(PairScore::Margin).run();
235        match ans.unwrap_err() {
236            ElectionError::DegeneratedElectionGraph => (),
237            _ => unreachable!(),
238        };
239    }
240    #[test]
241    fn ranked_pairs_determinism() {
242        //A->B->C->D is deterministic
243        let x = VoteMatrix::with_vector_bycol(&vec![0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1]);
244        assert!(RankedPairs::new(&x).run().unwrap().deterministic());
245
246        //A->B->C->D->A is not deterministic
247        let x = VoteMatrix::with_vector_bycol(&vec![0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1]);
248        assert!(!RankedPairs::new(&x).run().unwrap().deterministic());
249
250        //D=>C A->B->C->D->A is deterministic, though meh
251        let x = VoteMatrix::with_vector_bycol(&vec![0, 0, 1, 1, 0, 0, 0, 1, 2, 0, 0, 1]);
252        assert!(RankedPairs::new(&x).run().unwrap().deterministic());
253
254        //A=>B D=>C C->A B->D is not deterministic
255        let x = VoteMatrix::with_vector_bycol(&vec![0, 1, 0, 2, 0, 0, 0, 0, 2, 0, 1, 0]);
256        assert!(!RankedPairs::new(&x).run().unwrap().deterministic());
257
258        //A=>B=>C=>D=>E C->A D->B E->C A->D B->E is deterministic
259        let x = VoteMatrix::with_vector_bycol(&vec![
260            0, 1, 0, 0, 2, 0, 1, 0, 0, 2, 0, 1, 1, 0, 2, 0, 0, 1, 0, 2,
261        ]);
262        assert!(RankedPairs::new(&x).run().unwrap().deterministic());
263    }
264    #[test]
265    fn no_cands() {
266        use crate::ElectionError;
267        let x: VoteMatrix = VoteMatrix::with_vector_bycol(&vec![]);
268        match RankedPairs::new(&x).run().unwrap_err() {
269            ElectionError::NotEnoughCandidates => (),
270            _ => unreachable!(),
271        }
272    }
273}
wybr/methods/ranked_pairs.rs

wybr/methods/
ranked_pairs.rs
