|0.2.0||Aug 4, 2023|
|0.1.4||Jun 12, 2023|
|0.1.3||May 22, 2023|
|0.1.1||Mar 26, 2023|
#1 in #election
23 downloads per month
Single Transferable Vote implementation in Rust
For now, only Meek's counting method is implemented.
You can find more details in the following blog article: STV-rs: Single Transferable Vote implementation in Rust.
$ RUST_LOG=$LOG_LEVEL cargo run \ --release -- \ --arithmetic $ARITHMETIC \ --input ballots.txt \ meek \ --parallel=<true|false>
$ RUST_LOG=$LOG_LEVEL cargo run \ --release -- \ --arithmetic $ARITHMETIC \ --input ballots.txt \ meek \ --parallel=<true|false> \ --equalize
You can control the arithmetic used to count votes via the
command-line flag. The following implementations are available.
fixed9: Each arithmetic operation is rounded to 9 decimal places. Rounding is downwards except for explicitly-marked operations (computing keep factors). This is backed by Rust's
i64and therefore might overflow. Compiling with the
checked_i64feature (enabled by default) will trap integer overflows and make the program panic, rather than continuing with incorrect numbers.
bigfixed9: Same as
fixed9, but this is backed by a big integer type (from the
numcrate) and therefore won't overflow. On the flip side, this will be slower than
float64: Use 64-bit floating-point arithmetic (Rust's
f64). Generally fast but more brittle to reproduce, because the rounding introduced by floating-point arithmetic means that basic properties such as associativity and distributivity don't hold.
exact: Use exact rational numbers without rounding. The computational complexity is generally too high to complete more than a few rounds.
approx: Use exact rational numbers within each STV round, but then round the Meek keep factors after each round, to avoid computational complexity explosion.
In this mode, ballots where candidates are ranked equally are counted as fairly as possible, by simulating a superposition of all possible permutations of equally-ranked candidates.
For example, the ballot
a b=c becomes a superposition of
a b c (with weight
a c b (with weight 1/2). Likewise, the ballot
a b=c=d is counted as
a superposition of 6 ballots, each with weight 1/6:
a b c d,
a b d c,
a c b d,
a c d b,
a d b c,
a d c b.
Besides the election transcript written to the standard output (which aims to be
consistent with Droop.py for
reproducibility), you can get more details via Rust's logging capabilities,
controlled by setting the
$RUST_LOG environment variable.
The log levels will provide the following information.
info: Print high-level results: election setup, elected/defeated candidates.
info+ print debug information about each STV round.
debug+ print how each ballot is counted in each round.
For more advanced logging control, please check the
env_logger crate documentation.
To speed up the computation, you can enable parallelism via the
The vote-counting process involves accumulating votes across all ballots, summing the outcomes of counting each ballot. Without parallelism, this is done by a simple serial loop over the ballots. With parallelism enabled, a parallel loop is used instead, where each ballot is counted independently on any thread, and the sum is computed in any order.
Because the sum is computed in an arbitrary order, it is important to use an
arithmetic where addition is
results won't be reproducible. This excludes
float64, as addition is not
Under the hood, the
rayon crate is used to
automatically schedule and spread the work across available CPU cores
Other STV implementations
Here is a non-exhaustive list of STV implementations.
CONTRIBUTING.md for details.
Apache 2.0; see
LICENSE for details.
This project is not an official Google project. It is not supported by Google and Google specifically disclaims all warranties as to its quality, merchantability, or fitness for a particular purpose.