Implement features required for 2006 Meek STV

viz. --round-{tvs,votes,weights}, --defer-surpluses, --meek-immediate-elect and --meek-surplus-tolerance
This commit is contained in:
RunasSudo 2021-06-18 18:48:12 +10:00
parent 2ea8b4b757
commit 13f1885eb5
Signed by: RunasSudo
GPG Key ID: 7234E476BF21C61A
17 changed files with 319 additions and 46 deletions

View File

@ -6,10 +6,12 @@ The preset dropdown allows you to choose from a hardcoded list of preloaded STV
* *Recommended WIGM*: A recommended set of simple STV rules designed for computer counting, using the weighted inclusive Gregory method and rational arithmetic.
* *Scottish STV*: Rules from the [*Scottish Local Government Elections Order 2011*](https://www.legislation.gov.uk/ssi/2011/399/schedule/1/made), using the weighted inclusive Gregory method. Validated against the [2007 Scottish local government election result for Linn ward](https://web.archive.org/web/20121004213938/http://www.glasgow.gov.uk/en/YourCouncil/Elections_Voting/Election_Results/ElectionScotland2007/LGWardResults.htm?ward=1&wardname=1%20-%20Linn).
* [*Meek STV*](http://www.dia.govt.nz/diawebsite.NSF/Files/meekm/%24file/meekm.pdf): Advanced STV rules designed for computer counting, recognised by the Proportional Representation Society of Australia (Victoria–Tasmania) as the superior STV system. Validated against the [Hill–Wichmann–Woodall implementation](https://www.dia.govt.nz/diawebsite.NSF/Files/meekm/%24file/meekm.pdf) for the ERS97 model election (see below).
* [*Meek STV*](http://www.dia.govt.nz/diawebsite.NSF/Files/meekm/%24file/meekm.pdf): Advanced STV rules designed for computer counting, recognised by the Proportional Representation Society of Australia (Victoria–Tasmania) as the superior STV system.
* *Meek STV (1986)* operates according to the original [Hill–Wichmann–Woodall specification](https://www.dia.govt.nz/diawebsite.NSF/Files/meekm/%24file/meekm.pdf) of Meek STV, with the modifications, relevant only in exceptional cases, that (a) fixed-point arithmetic with 5 decimal places is used, and (b) candidates are elected on strictly exceeding the quota. Validated against the Hill–Wichmann–Woodall implementation for the [ERS97 model election](https://www.electoral-reform.org.uk/latest-news-and-research/publications/how-to-conduct-an-election-by-the-single-transferable-vote-3rd-edition/#sub-section-24).
* *Meek STV (2006)* operates according to [Hill's 2006 revisions](http://www.votingmatters.org.uk/ISSUE22/I22P2.pdf). This is the algorithm referred to in OpenSTV/OpaVote as ‘Meek STV’, and forms the basis of New Zealand's Meek STV rules. Validated against OpenSTV for the ERS97 model election.
* *Australian Senate STV*: Rules from the [*Commonwealth Electoral Act 1918*](https://www.legislation.gov.au/Details/C2020C00400/Html/Text#_Toc59107700), using the unweighted inclusive Gregory method. Validated against the [2019 Australian Senate election result for Tasmania](https://results.aec.gov.au/24310/Website/SenateDownloadsMenu-24310-Csv.htm).
* [*PRSA 1977*](https://www.prsa.org.au/rule1977.htm): Simple rules designed for hand counting, using the exclusive Gregory method, with counting automatically performed in thousandths of a vote. Validated against [example 1](https://www.prsa.org.au/example1.pdf) of the PRSA's [*Proportional Representation Manual*](https://www.prsa.org.au/publicat.htm#p2).
* [*ERS97*](https://www.electoral-reform.org.uk/latest-news-and-research/publications/how-to-conduct-an-election-by-the-single-transferable-vote-3rd-edition/): More complex rules designed for hand counting, using the exclusive Gregory method. Validated against the ERS97 [model election](https://www.electoral-reform.org.uk/latest-news-and-research/publications/how-to-conduct-an-election-by-the-single-transferable-vote-3rd-edition/#sub-section-24).
* [*ERS97*](https://www.electoral-reform.org.uk/latest-news-and-research/publications/how-to-conduct-an-election-by-the-single-transferable-vote-3rd-edition/): More complex rules designed for hand counting, using the exclusive Gregory method. Validated against the ERS97 model election.
This functionality is not available on the command line.
@ -86,7 +88,7 @@ When *Surplus method* is set to *Meek method*, this setting is ignored, and the
This dropdown allows you to select how ties (in surplus transfer or exclusion) are broken. The options are:
* *Backwards*: Ties are broken according to which tied candidate had the most/fewest votes at the end of the *most recent* stage where one tied candidate had more/fewer votes than the others, if such a stage exists.
* *Fowards*: Ties are broken according to which tied candidate had the most/fewest votes at the end of the *earliest* stage where one tied candidate had more/fewer votes than the others, if such a stage exists.
* *Fowards*: Ties are broken according to which tied candidate had the most/fewest votes at the end of the *earliest* stage where one tied candidate had more/fewer votes than the others, if such a stage exists. This is also known as the ‘ahead at first difference’ method.
* *Random*: Ties are broken at random (see *Random seed*).
* *Prompt*: The user is prompted to break the tie.
@ -137,6 +139,13 @@ When deferred surpluses is disabled (default), all surpluses must be transferred
When deferred surpluses is enabled, the transfer of all surpluses is deferred if doing so could not change the order of exclusion (including of a bulk exclusion, if that is enabled).
### (Meek) Immediate election (--meek-immediate-elect)
This option controls when candidates are elected when *Surplus method* is set to *Meek method*:
* When immediate election is disabled (default), all current surpluses are distributed and keep values finalised, before any candidates exceeding the quota are then declared elected. This is the method specified in the 1986 Meek rules.
* When immediate election is enabled, a candidate meeting the quota interrupts a surplus distribution. The candidate is immediately declared elected, before the distribution of all surpluses of all now-elected candidates continues. This is the method specified in the 2006 Meek rules.
## Rounding
### Round quota/votes/surplus fractions/ballot weights to [n] d.p. (--round-quota, --round-votes, --round-tvs, --round-weights)
@ -145,14 +154,20 @@ When rounding is enabled, the specified values are rounded to the specified numb
When enabled, the quota is incremented or rounded up (according to the *Quota* option), whereas votes, surplus fractions and weights are always rounded down.
In relation to *Round surplus fractions to [n] d.p.* – note that surplus fractions are used in STV in calculations of the form *A* × (*B*/*C*), where (*B*/*C*) is the surplus fraction. The order of operations depends on this setting:
In relation to *Round surplus fractions to [n] d.p.* (--round-tvs) – note that surplus fractions are used in STV in calculations of the form *A* × (*B*/*C*), where (*B*/*C*) is the surplus fraction. The order of operations depends on this setting:
* When this option is disabled (default), (*A* × *B*) is calculated first, then divided by *C*. This minimises rounding errors.
* When this option is enabled, (*B*/*C*) is calculated separately first and rounded to the specified precision, before being multiplied by *A*. Many STV rules designed for hand counting prescribe this method of manipulating surplus fractions.
In Australia, surplus fractions are often known as ‘transfer values’; however, the term ‘value’ is reserved in OpenTally for referring to the values of votes.
### Sum surplus transfers
When *Surplus method* is set to *Meek method*:
* --round-weights instead controls the rounding of candidate keep values
* --round-tvs instead controls the rounding of each intermediate product when computing candidates' votes
* --round-votes controls the rounding of the final number of votes credited to each candidate
### Sum surplus transfers (--sum-surplus-transfers)
This option allows you to specify how the numbers of votes credited to candidates in a surplus transfer is calculated. In each case, votes are grouped according to the next available preference for a continuing candidate. Subsequently:
@ -161,3 +176,10 @@ This option allows you to specify how the numbers of votes credited to candidate
* *Per ballot*: For each individual vote expressing a next available preference for that candidate, the value of the vote is multiplied by the surplus fraction. The product is credited to that candidate.
This option affects the result only insofar as rounding (due to use of fixed-precision arithmetic, or due to an explicit rounding option) is concerned.
### (Meek) Surplus tolerance (--meek-surplus-tolerance)
When *Surplus method* is set to *Meek method*, this option allows you to specify when the distribution of surpluses will be considered complete. The tolerance may be specified either as a percentage (ends with a `%`) or absolute number of votes (no `%`):
* Percentage: Surplus distributions will be considered complete when every elected candidate's surplus exceeds the quota by no more than the specified percentage. This is the method specified in the 1986 Meek rules.
* Absolute number of votes: Surplus distributions will be considered complete when the total surpluses of all elected candidates is no greater than the specified number of votes. This is the simpler method specified in the 2006 Meek rules.

View File

@ -37,7 +37,8 @@
<select id="selPreset" onchange="changePreset()">
<option value="wigm" selected>Recommended WIGM</option>
<option value="scottish">Scottish STV</option>
<option value="meek">Meek STV</option>
<option value="meek87">Meek STV (1987)</option>
<option value="meek06">Meek STV (2006)</option>
<option value="senate">Australian Senate STV</option>
<!--<option value="wright">Wright STV</option>-->
<option value="prsa77">PRSA 1977</option>
@ -178,10 +179,14 @@
<input type="checkbox" id="chkBulkExclusion">
Bulk exclusion
</label>
<label class="col-12">
<label class="col-6">
<input type="checkbox" id="chkDeferSurpluses">
Defer surpluses
</label>
<label class="col-6">
<input type="checkbox" id="chkMeekImmediateElect">
(Meek) Immediate election
</label>
<div class="col-12 subheading">
Rounding:
</div>
@ -233,6 +238,10 @@
<option value="per_ballot">Per ballot</option>
</select>
</label>
<label class="col-12">
(Meek) Surplus tolerance:
<input type="text" id="txtMeekSurplusTolerance" value="0.001%" style="width: 5em;">
</label>
</div>
</div>

View File

@ -103,6 +103,7 @@ async function clickCount() {
document.getElementById('chkRoundVotes').checked ? parseInt(document.getElementById('txtRoundVotes').value) : null,
document.getElementById('chkRoundQuota').checked ? parseInt(document.getElementById('txtRoundQuota').value) : null,
document.getElementById('selSumTransfers').value,
document.getElementById('txtMeekSurplusTolerance').value,
document.getElementById('chkNormaliseBallots').checked,
document.getElementById('selQuota').value,
document.getElementById('selQuotaCriterion').value,
@ -115,9 +116,11 @@ async function clickCount() {
document.getElementById('selExclusion').value,
document.getElementById('chkBulkExclusion').checked,
document.getElementById('chkDeferSurpluses').checked,
document.getElementById('chkMeekImmediateElect').checked,
parseInt(document.getElementById('txtPPDP').value),
];
// Dispatch to worker
worker.postMessage({
'type': 'countElection',
@ -353,13 +356,14 @@ function changePreset() {
document.getElementById('selPapers').value = 'both';
document.getElementById('selExclusion').value = 'single_stage';
document.getElementById('selTies').value = 'backwards,random';
} else if (document.getElementById('selPreset').value === 'meek') {
} else if (document.getElementById('selPreset').value === 'meek87') {
document.getElementById('selQuotaCriterion').value = 'gt';
document.getElementById('selQuota').value = 'droop_exact';
document.getElementById('selQuotaMode').value = 'static';
document.getElementById('chkBulkElection').checked = true;
document.getElementById('chkBulkExclusion').checked = false;
document.getElementById('chkDeferSurpluses').checked = false;
document.getElementById('chkMeekImmediateElect').checked = false;
document.getElementById('selNumbers').value = 'fixed';
document.getElementById('txtDP').value = '5';
document.getElementById('txtPPDP').value = '2';
@ -368,11 +372,39 @@ function changePreset() {
document.getElementById('chkRoundVotes').checked = false;
document.getElementById('chkRoundTVs').checked = false;
document.getElementById('chkRoundWeights').checked = false;
document.getElementById('selSumTransfers').value = 'single_step';
document.getElementById('selSurplus').value = 'by_size';
//document.getElementById('selSumTransfers').value = 'single_step';
document.getElementById('txtMeekSurplusTolerance').value = '0.001%';
//document.getElementById('selSurplus').value = 'by_size';
document.getElementById('selTransfers').value = 'meek';
document.getElementById('selPapers').value = 'both';
document.getElementById('selExclusion').value = 'single_stage';
//document.getElementById('selPapers').value = 'both';
//document.getElementById('selExclusion').value = 'single_stage';
document.getElementById('selTies').value = 'backwards,random';
} else if (document.getElementById('selPreset').value === 'meek06') {
document.getElementById('selQuotaCriterion').value = 'geq';
document.getElementById('selQuota').value = 'droop';
document.getElementById('selQuotaMode').value = 'static';
document.getElementById('chkBulkElection').checked = true;
document.getElementById('chkBulkExclusion').checked = false;
document.getElementById('chkDeferSurpluses').checked = true;
document.getElementById('chkMeekImmediateElect').checked = true;
document.getElementById('selNumbers').value = 'fixed';
document.getElementById('txtDP').value = '12';
document.getElementById('txtPPDP').value = '2';
document.getElementById('chkNormaliseBallots').checked = false;
document.getElementById('chkRoundQuota').checked = true;
document.getElementById('txtRoundQuota').value = '9';
document.getElementById('chkRoundVotes').checked = true;
document.getElementById('txtRoundVotes').value = '9';
document.getElementById('chkRoundTVs').checked = true;
document.getElementById('txtRoundTVs').value = '9';
document.getElementById('chkRoundWeights').checked = true;
document.getElementById('txtRoundWeights').value = '9';
//document.getElementById('selSumTransfers').value = 'single_step';
document.getElementById('txtMeekSurplusTolerance').value = '0.0001';
//document.getElementById('selSurplus').value = 'by_size';
document.getElementById('selTransfers').value = 'meek';
//document.getElementById('selPapers').value = 'both';
//document.getElementById('selExclusion').value = 'single_stage';
document.getElementById('selTies').value = 'backwards,random';
} else if (document.getElementById('selPreset').value === 'senate') {
document.getElementById('selQuotaCriterion').value = 'geq';

View File

@ -87,6 +87,10 @@ struct STV {
#[clap(help_heading=Some("ROUNDING"), long, possible_values=&["single_step", "by_value", "per_ballot"], default_value="single_step", value_name="mode")]
sum_surplus_transfers: String,
/// (Meek STV) Limit for stopping iteration of surplus distribution
#[clap(help_heading=Some("ROUNDING"), long, default_value="0.001%", value_name="tolerance")]
meek_surplus_tolerance: String,
// -----------
// -- Quota --
@ -140,6 +144,10 @@ struct STV {
#[clap(help_heading=Some("COUNT OPTIMISATIONS"), long)]
defer_surpluses: bool,
/// (Meek STV) Immediately elect candidates even if keep values have not converged
#[clap(help_heading=Some("COUNT OPTIMISATIONS"), long)]
meek_immediate_elect: bool,
// ----------------------
// -- Display settings --
@ -197,6 +205,7 @@ where
cmd_opts.round_votes,
cmd_opts.round_quota,
&cmd_opts.sum_surplus_transfers,
&cmd_opts.meek_surplus_tolerance,
cmd_opts.normalise_ballots,
&cmd_opts.quota,
&cmd_opts.quota_criterion,
@ -209,6 +218,7 @@ where
&cmd_opts.exclusion,
cmd_opts.bulk_exclude,
cmd_opts.defer_surpluses,
cmd_opts.meek_immediate_elect,
cmd_opts.pp_decimals,
);

View File

@ -79,6 +79,29 @@ impl Number for Fixed {
self.0 *= factor;
}
}
fn parse(s: &str) -> Self {
// Parse decimal
if s.contains('.') {
let (whole, decimal) = s.split_once('.').unwrap();
let whole = match IBig::from_str_radix(whole, 10) {
Ok(value) => value,
Err(_) => panic!("Syntax Error"),
} * get_factor();
let decimal = match IBig::from_str_radix(decimal, 10) {
Ok(value) => value,
Err(_) => panic!("Syntax Error"),
} * get_factor() / IBig::from(10).pow(decimal.len());
return Self(whole + decimal);
}
// Parse integer
if let Ok(value) = Self::from_str_radix(s, 10) {
return value;
} else {
panic!("Syntax Error");
}
}
}
impl Num for Fixed {

View File

@ -86,6 +86,29 @@ impl Number for GuardedFixed {
self.0 *= factor;
}
}
fn parse(s: &str) -> Self {
// Parse decimal
if s.contains('.') {
let (whole, decimal) = s.split_once('.').unwrap();
let whole = match IBig::from_str_radix(whole, 10) {
Ok(value) => value,
Err(_) => panic!("Syntax Error"),
} * get_factor();
let decimal = match IBig::from_str_radix(decimal, 10) {
Ok(value) => value,
Err(_) => panic!("Syntax Error"),
} * get_factor() / IBig::from(10).pow(decimal.len());
return Self(whole + decimal);
}
// Parse integer
if let Ok(value) = Self::from_str_radix(s, 10) {
return value;
} else {
panic!("Syntax Error");
}
}
}
impl Num for GuardedFixed {

View File

@ -18,10 +18,9 @@
use super::{Assign, Number};
use derive_more::Display;
use num_traits::{Num, One, Zero};
use num_traits::{Num, One, ParseFloatError, Zero};
use std::cmp::{Ord, Ordering, PartialEq, PartialOrd};
use std::num::ParseIntError;
use std::ops;
type ImplType = f64;
@ -51,9 +50,9 @@ impl Number for NativeFloat64 {
}
impl Num for NativeFloat64 {
type FromStrRadixErr = ParseIntError;
type FromStrRadixErr = ParseFloatError;
fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
match i64::from_str_radix(str, radix) {
match f64::from_str_radix(str, radix) {
Ok(value) => Ok(Self(value as ImplType)),
Err(err) => Err(err)
}

View File

@ -26,6 +26,7 @@ use std::ops;
type RatioBase = num_bigint::BigInt;
type RatioType = num_rational::BigRational;
/// Rational number
#[derive(Clone, Debug, PartialEq, PartialOrd)]
pub struct Rational(RatioType);
@ -60,6 +61,29 @@ impl Number for Rational {
self.0 /= factor;
}
}
fn parse(s: &str) -> Self {
// Parse decimal
if s.contains('.') {
let (whole, decimal) = s.split_once('.').unwrap();
let whole = match RatioBase::from_str_radix(whole, 10) {
Ok(value) => RatioType::from_integer(value),
Err(_) => panic!("Syntax Error"),
};
let decimal = match RatioBase::from_str_radix(decimal, 10) {
Ok(value) => RatioType::from_integer(value),
Err(_) => panic!("Syntax Error"),
} / RatioBase::from(10).pow(decimal.len() as u32);
return Self(whole + decimal);
}
// Parse integer
if let Ok(value) = Self::from_str_radix(s, 10) {
return value;
} else {
panic!("Syntax Error");
}
}
}
impl Num for Rational {

View File

@ -60,6 +60,29 @@ impl Number for Rational {
self.0 /= factor;
}
}
fn parse(s: &str) -> Self {
// Parse decimal
if s.contains('.') {
let (whole, decimal) = s.split_once('.').unwrap();
let whole = match rug::Rational::parse_radix(whole, 10) {
Ok(value) => rug::Rational::from(value),
Err(_) => panic!("Syntax Error"),
};
let decimal = match rug::Rational::parse_radix(decimal, 10) {
Ok(value) => rug::Rational::from(value),
Err(_) => panic!("Syntax Error"),
} / rug::Rational::from(10).pow(decimal.len() as u32);
return Self(whole + decimal);
}
// Parse integer
if let Ok(value) = Self::from_str_radix(s, 10) {
return value;
} else {
panic!("Syntax Error");
}
}
}
impl Num for Rational {

View File

@ -91,7 +91,7 @@ impl<'t, N: Number> BallotTree<'t, N> {
}
/// Initialise keep values, ballot tree and distribute preferences
pub fn distribute_first_preferences<N: Number>(state: &mut CountState<N>)
pub fn distribute_first_preferences<N: Number>(state: &mut CountState<N>, opts: &STVOptions)
where
for<'r> &'r N: ops::Sub<&'r N, Output=N>,
for<'r> &'r N: ops::Mul<&'r N, Output=N>,
@ -113,7 +113,7 @@ where
state.ballot_tree = Some(ballot_tree);
// Distribute preferences
distribute_preferences(state);
distribute_preferences(state, opts);
// Recalculate transfers
for (_, count_card) in state.candidates.iter_mut() {
@ -127,7 +127,7 @@ where
}
/// (Re)distribute preferences according to candidate keep values
pub fn distribute_preferences<N: Number>(state: &mut CountState<N>)
pub fn distribute_preferences<N: Number>(state: &mut CountState<N>, opts: &STVOptions)
where
for<'r> &'r N: ops::Sub<&'r N, Output=N>,
for<'r> &'r N: ops::Mul<&'r N, Output=N>,
@ -140,13 +140,13 @@ where
}
state.exhausted.votes = N::new();
distribute_recursively(&mut state.candidates, &mut state.exhausted, state.ballot_tree.as_mut().unwrap(), N::one(), &state.election);
distribute_recursively(&mut state.candidates, &mut state.exhausted, state.ballot_tree.as_mut().unwrap(), N::one(), &state.election, opts);
}
/// Distribute preferences recursively
///
/// Called by [distribute_preferences]
fn distribute_recursively<'t, N: Number>(candidates: &mut HashMap<&'t Candidate, CountCard<N>>, exhausted: &mut CountCard<N>, tree: &mut BallotTree<'t, N>, remaining_multiplier: N, election: &'t Election<N>)
fn distribute_recursively<'t, N: Number>(candidates: &mut HashMap<&'t Candidate, CountCard<N>>, exhausted: &mut CountCard<N>, tree: &mut BallotTree<'t, N>, remaining_multiplier: N, election: &'t Election<N>, opts: &STVOptions)
where
for<'r> &'r N: ops::Mul<&'r N, Output=N>,
{
@ -157,27 +157,39 @@ where
// FIXME: Possibility of infinite loop if malformed inputs?
// TODO: Round transfers?
// Credit votes at this level
for (candidate, cand_tree) in tree.next_preferences.as_mut().unwrap().as_mut().iter_mut() {
let count_card = candidates.get_mut(candidate).unwrap();
match count_card.state {
CandidateState::Hopeful | CandidateState::Guarded | CandidateState::Doomed => {
// Hopeful candidate has keep value 1, so transfer entire remaining value
count_card.votes += &remaining_multiplier * &cand_tree.num_ballots;
let mut to_transfer = &remaining_multiplier * &cand_tree.num_ballots;
if let Some(dps) = opts.round_votes {
// NZ Meek STV rounds *up*!
to_transfer.ceil_mut(dps);
}
count_card.votes += to_transfer;
}
CandidateState::Elected => {
// Transfer according to elected candidate's keep value
count_card.votes += &remaining_multiplier * &cand_tree.num_ballots * count_card.keep_value.as_ref().unwrap();
let new_remaining_multiplier = &remaining_multiplier * &(N::one() - count_card.keep_value.as_ref().unwrap());
let mut to_transfer = &remaining_multiplier * &cand_tree.num_ballots * count_card.keep_value.as_ref().unwrap();
if let Some(dps) = opts.round_votes {
to_transfer.ceil_mut(dps);
}
count_card.votes += to_transfer;
let mut new_remaining_multiplier = &remaining_multiplier * &(N::one() - count_card.keep_value.as_ref().unwrap());
if let Some(dps) = opts.round_tvs {
new_remaining_multiplier.ceil_mut(dps);
}
// Recurse
distribute_recursively(candidates, exhausted, cand_tree, new_remaining_multiplier, election);
distribute_recursively(candidates, exhausted, cand_tree, new_remaining_multiplier, election, opts);
}
CandidateState::Excluded | CandidateState::Withdrawn => {
// Excluded candidate has keep value 0, so skip over this candidate
// Recurse
distribute_recursively(candidates, exhausted, cand_tree, remaining_multiplier.clone(), election);
distribute_recursively(candidates, exhausted, cand_tree, remaining_multiplier.clone(), election, opts);
}
}
}
@ -186,6 +198,40 @@ where
exhausted.votes += &remaining_multiplier * &tree.next_exhausted.as_ref().unwrap().as_ref().num_ballots;
}
fn recompute_keep_values<'s, N: Number>(state: &mut CountState<'s, N>, opts: &STVOptions, has_surplus: &Vec<&'s Candidate>) {
for candidate in has_surplus.into_iter() {
let count_card = state.candidates.get_mut(candidate).unwrap();
count_card.keep_value = Some(count_card.keep_value.take().unwrap() * state.quota.as_ref().unwrap() / &count_card.votes);
if let Some(dps) = opts.round_weights {
// NZ Meek STV rounds *up*!
count_card.keep_value.as_mut().unwrap().ceil_mut(dps);
}
}
}
/// Determine if the specified surpluses should be distributed, according to [STVOptions::meek_quota_tolerance]
fn should_distribute_surpluses<N: Number>(state: &CountState<N>, has_surplus: &Vec<&Candidate>, opts: &STVOptions) -> bool
where
for<'r> &'r N: ops::Sub<&'r N, Output=N>,
for<'r> &'r N: ops::Div<&'r N, Output=N>,
{
if opts.meek_surplus_tolerance.ends_with('%') {
// Distribute if any candidate has a surplus exceeding the tolerance
let quota_tolerance = N::parse(&opts.meek_surplus_tolerance[0..opts.meek_surplus_tolerance.len()-1]) / N::from(100) + N::one();
return has_surplus.iter().any(|c| {
let count_card = state.candidates.get(c).unwrap();
return &count_card.votes / state.quota.as_ref().unwrap() > quota_tolerance;
});
} else {
// Distribute if the total surplus exceeds the tolerance
let quota_tolerance = N::parse(&opts.meek_surplus_tolerance);
let total_surpluses = has_surplus.iter()
.fold(N::new(), |acc, c| acc + &state.candidates.get(c).unwrap().votes - state.quota.as_ref().unwrap());
return total_surpluses > quota_tolerance;
}
}
/// Recalculate all candidate keep factors to distribute all surpluses according to the Meek method
pub fn distribute_surpluses<N: Number>(state: &mut CountState<N>, opts: &STVOptions) -> Result<bool, STVError>
where
@ -193,49 +239,73 @@ where
for<'r> &'r N: ops::Mul<&'r N, Output=N>,
for<'r> &'r N: ops::Div<&'r N, Output=N>,
{
// TODO: Make configurable
let quota_tolerance = N::one() / N::from(100000) + N::one();
let quota = state.quota.as_ref().unwrap();
let mut has_surplus: Vec<&Candidate> = state.election.candidates.iter() // Present in order in case of tie
.filter(|c| {
let count_card = state.candidates.get(c).unwrap();
return count_card.state == CandidateState::Elected && (&count_card.votes / quota > quota_tolerance);
return count_card.state == CandidateState::Elected && &count_card.votes > quota;
})
.collect();
if !has_surplus.is_empty() {
// TODO: Defer surpluses?
let mut should_distribute = should_distribute_surpluses(state, &has_surplus, opts);
if should_distribute {
// Determine if surplues can be deferred
if opts.defer_surpluses {
let total_surpluses = has_surplus.iter()
.fold(N::new(), |acc, c| acc + &state.candidates.get(c).unwrap().votes - quota);
if super::can_defer_surpluses(state, opts, &total_surpluses) {
state.logger.log_literal(format!("Distribution of surpluses totalling {:.dps$} votes will be deferred.", total_surpluses, dps=opts.pp_decimals));
return Ok(false);
}
}
let mut surpluses_deferred = None; // Option<total_surpluses>
let mut candidates_elected = None; // Option<LogEntry>
let orig_candidates = state.candidates.clone();
let orig_exhausted = state.exhausted.clone();
let mut num_iterations: u32 = 0;
while !has_surplus.is_empty() {
while should_distribute {
num_iterations += 1;
// Recompute keep values
for candidate in has_surplus.into_iter() {
let count_card = state.candidates.get_mut(candidate).unwrap();
count_card.keep_value = Some(count_card.keep_value.take().unwrap() * state.quota.as_ref().unwrap() / &count_card.votes);
}
recompute_keep_values(state, opts, &has_surplus);
// Redistribute votes
distribute_preferences(state);
distribute_preferences(state, opts);
// Recompute quota if more ballots have become exhausted
super::calculate_quota(state, opts);
//println!("Debug {}", num_iterations);
if opts.meek_immediate_elect {
// Try to elect candidates
if super::elect_meeting_quota(state, opts) {
candidates_elected = Some(state.logger.entries.pop().unwrap());
break;
}
}
let quota = state.quota.as_ref().unwrap();
has_surplus = state.election.candidates.iter()
.filter(|c| {
let count_card = state.candidates.get(c).unwrap();
return count_card.state == CandidateState::Elected && (&count_card.votes / quota > quota_tolerance);
return count_card.state == CandidateState::Elected && &count_card.votes > quota;
})
.collect();
should_distribute = should_distribute_surpluses(state, &has_surplus, opts);
// Determine if surplues can be deferred
if should_distribute && opts.defer_surpluses {
let total_surpluses = has_surplus.iter()
.fold(N::new(), |acc, c| acc + &state.candidates.get(c).unwrap().votes - quota);
if super::can_defer_surpluses(state, opts, &total_surpluses) {
surpluses_deferred = Some(total_surpluses);
break;
}
}
}
// Recalculate transfers
@ -259,6 +329,15 @@ where
state.logger.log_literal(format!("Surpluses distributed, requiring {} iterations.", num_iterations));
}
if let Some(total_surpluses) = surpluses_deferred {
state.logger.log_literal(format!("Distribution of surpluses totalling {:.dps$} votes will be deferred.", total_surpluses, dps=opts.pp_decimals));
}
// If candidates were elected, retain that log entry
if let Some(log_entry) = candidates_elected {
state.logger.log(log_entry);
}
let kv_str = state.election.candidates.iter()
.map(|c| (c, state.candidates.get(c).unwrap()))
.filter(|(_, cc)| cc.state == CandidateState::Elected)
@ -274,7 +353,7 @@ where
}
/// Exclude the given candidates according to the Meek method
pub fn exclude_candidates<'a, N: Number>(state: &mut CountState<'a, N>, _opts: &STVOptions, excluded_candidates: Vec<&'a Candidate>)
pub fn exclude_candidates<'a, N: Number>(state: &mut CountState<'a, N>, opts: &STVOptions, excluded_candidates: Vec<&'a Candidate>)
where
for<'r> &'r N: ops::Sub<&'r N, Output=N>,
for<'r> &'r N: ops::Mul<&'r N, Output=N>,
@ -295,7 +374,7 @@ where
let orig_candidates = state.candidates.clone();
let orig_exhausted = state.exhausted.clone();
distribute_preferences(state);
distribute_preferences(state, opts);
// Recalculate transfers
let mut checksum = N::new();

View File

@ -49,6 +49,8 @@ pub struct STVOptions {
pub round_quota: Option<usize>,
/// How to calculate votes to credit to candidates in surplus transfers
pub sum_surplus_transfers: SumSurplusTransfersMode,
/// (Meek STV) Limit for stopping iteration of surplus distribution
pub meek_surplus_tolerance: String,
/// Convert ballots with value >1 to multiple ballots of value 1
pub normalise_ballots: bool,
/// Quota type
@ -71,6 +73,8 @@ pub struct STVOptions {
pub bulk_exclude: bool,
/// Defer surplus distributions if possible
pub defer_surpluses: bool,
/// (Meek STV) Immediately elect candidates even if keep values have not converged
pub meek_immediate_elect: bool,
/// Print votes to specified decimal places in results report
pub pp_decimals: usize,
}
@ -83,6 +87,7 @@ impl STVOptions {
round_votes: Option<usize>,
round_quota: Option<usize>,
sum_surplus_transfers: &str,
meek_surplus_tolerance: &str,
normalise_ballots: bool,
quota: &str,
quota_criterion: &str,
@ -95,6 +100,7 @@ impl STVOptions {
exclusion: &str,
bulk_exclude: bool,
defer_surpluses: bool,
meek_immediate_elect: bool,
pp_decimals: usize,
) -> Self {
return STVOptions {
@ -108,6 +114,7 @@ impl STVOptions {
"per_ballot" => SumSurplusTransfersMode::PerBallot,
_ => panic!("Invalid --sum-transfers"),
},
meek_surplus_tolerance: meek_surplus_tolerance.to_string(),
normalise_ballots,
quota: match quota {
"droop" => QuotaType::Droop,
@ -154,6 +161,7 @@ impl STVOptions {
},
bulk_exclude,
defer_surpluses,
meek_immediate_elect,
pp_decimals,
};
}
@ -167,6 +175,7 @@ impl STVOptions {
if let Some(dps) = self.round_votes { flags.push(format!("--round-votes {}", dps)); }
if let Some(dps) = self.round_quota { flags.push(format!("--round-quota {}", dps)); }
if self.sum_surplus_transfers != SumSurplusTransfersMode::SingleStep { flags.push(self.sum_surplus_transfers.describe()); }
if self.surplus == SurplusMethod::Meek && self.meek_surplus_tolerance != "0.001%" { flags.push(format!("--meek-surplus-tolerance {}", self.meek_surplus_tolerance)); }
if self.normalise_ballots { flags.push("--normalise-ballots".to_string()); }
let ties_str = self.ties.iter().map(|t| t.describe()).join(" ");
if ties_str != "prompt" { flags.push(format!("--ties {}", ties_str)); }
@ -180,6 +189,7 @@ impl STVOptions {
if self.exclusion != ExclusionMethod::SingleStage { flags.push(self.exclusion.describe()); }
if self.bulk_exclude { flags.push("--bulk-exclude".to_string()); }
if self.defer_surpluses { flags.push("--defer-surpluses".to_string()); }
if self.surplus == SurplusMethod::Meek && self.meek_immediate_elect { flags.push("--meek-immediate-elect".to_string()); }
if self.pp_decimals != 2 { flags.push(format!("--pp-decimals {}", self.pp_decimals)); }
return flags.join(" ");
}
@ -509,7 +519,7 @@ where
gregory::distribute_first_preferences(state);
}
SurplusMethod::Meek => {
meek::distribute_first_preferences(state);
meek::distribute_first_preferences(state, opts);
}
}
}
@ -641,7 +651,7 @@ fn meets_quota<N: Number>(quota: &N, count_card: &CountCard<N>, opts: &STVOption
}
/// Declare elected all candidates meeting the quota
fn elect_meeting_quota<N: Number>(state: &mut CountState<N>, opts: &STVOptions) {
fn elect_meeting_quota<N: Number>(state: &mut CountState<N>, opts: &STVOptions) -> bool {
let vote_req = state.vote_required_election.as_ref().unwrap(); // Have to do this or else the borrow checker gets confused
let mut cands_meeting_quota: Vec<&Candidate> = state.election.candidates.iter()
@ -675,7 +685,10 @@ fn elect_meeting_quota<N: Number>(state: &mut CountState<N>, opts: &STVOptions)
//calculate_quota(state, opts);
elect_meeting_quota(state, opts);
}
return true;
}
return false;
}
/// Determine whether the transfer of all surpluses can be deferred

View File

@ -188,6 +188,7 @@ impl STVOptions {
round_votes: Option<usize>,
round_quota: Option<usize>,
sum_surplus_transfers: &str,
meek_surplus_limit: &str,
normalise_ballots: bool,
quota: &str,
quota_criterion: &str,
@ -200,6 +201,7 @@ impl STVOptions {
exclusion: &str,
bulk_exclude: bool,
defer_surpluses: bool,
meek_immediate_elect: bool,
pp_decimals: usize,
) -> Self {
Self(stv::STVOptions::new(
@ -208,6 +210,7 @@ impl STVOptions {
round_votes,
round_quota,
sum_surplus_transfers,
meek_surplus_limit,
normalise_ballots,
quota,
quota_criterion,
@ -220,6 +223,7 @@ impl STVOptions {
exclusion,
bulk_exclude,
defer_surpluses,
meek_immediate_elect,
pp_decimals,
))
}

View File

@ -60,6 +60,7 @@ fn aec_tas19_rational() {
round_votes: Some(0),
round_quota: Some(0),
sum_surplus_transfers: stv::SumSurplusTransfersMode::SingleStep,
meek_surplus_tolerance: String::new(),
normalise_ballots: false,
quota: stv::QuotaType::Droop,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
@ -71,6 +72,7 @@ fn aec_tas19_rational() {
exclusion: stv::ExclusionMethod::ByValue,
bulk_exclude: true,
defer_surpluses: false,
meek_immediate_elect: false,
pp_decimals: 2,
};
utils::validate_election(stages, records, election, stv_opts, None, &["exhausted", "lbf"]);

View File

@ -28,6 +28,7 @@ fn ers97_rational() {
round_votes: Some(2),
round_quota: Some(2),
sum_surplus_transfers: stv::SumSurplusTransfersMode::SingleStep,
meek_surplus_tolerance: String::new(),
normalise_ballots: false,
quota: stv::QuotaType::DroopExact,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
@ -39,6 +40,7 @@ fn ers97_rational() {
exclusion: stv::ExclusionMethod::ByValue,
bulk_exclude: true,
defer_surpluses: true,
meek_immediate_elect: false,
pp_decimals: 2,
};
utils::read_validate_election::<Rational>("tests/data/ers97.csv", "tests/data/ers97.blt", stv_opts, None, &["nt", "vre"]);

View File

@ -28,6 +28,7 @@ fn meek_ers97_float64() {
round_votes: None,
round_quota: None,
sum_surplus_transfers: stv::SumSurplusTransfersMode::SingleStep,
meek_surplus_tolerance: String::from("1.001%"),
normalise_ballots: false,
quota: stv::QuotaType::DroopExact,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
@ -39,6 +40,7 @@ fn meek_ers97_float64() {
exclusion: stv::ExclusionMethod::SingleStage,
bulk_exclude: false,
defer_surpluses: false,
meek_immediate_elect: false,
pp_decimals: 2,
};
utils::read_validate_election::<NativeFloat64>("tests/data/ers97_meek.csv", "tests/data/ers97.blt", stv_opts, Some(2), &["exhausted", "quota"]);

View File

@ -28,6 +28,7 @@ fn prsa1_rational() {
round_votes: Some(3),
round_quota: Some(3),
sum_surplus_transfers: stv::SumSurplusTransfersMode::SingleStep,
meek_surplus_tolerance: String::new(),
normalise_ballots: false,
quota: stv::QuotaType::Droop,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
@ -39,6 +40,7 @@ fn prsa1_rational() {
exclusion: stv::ExclusionMethod::ParcelsByOrder,
bulk_exclude: false,
defer_surpluses: false,
meek_immediate_elect: false,
pp_decimals: 2,
};
utils::read_validate_election::<Rational>("tests/data/prsa1.csv", "tests/data/prsa1.blt", stv_opts, None, &["exhausted", "lbf"]);

View File

@ -35,6 +35,7 @@ fn scotland_linn07_fixed5() {
round_votes: Some(5),
round_quota: Some(0),
sum_surplus_transfers: stv::SumSurplusTransfersMode::PerBallot,
meek_surplus_tolerance: String::new(),
normalise_ballots: true,
quota: stv::QuotaType::Droop,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
@ -46,6 +47,7 @@ fn scotland_linn07_fixed5() {
exclusion: stv::ExclusionMethod::SingleStage,
bulk_exclude: false,
defer_surpluses: false,
meek_immediate_elect: false,
pp_decimals: 5,
};
Fixed::set_dps(5);
@ -60,6 +62,7 @@ fn scotland_linn07_gfixed5() {
round_votes: Some(5),
round_quota: Some(0),
sum_surplus_transfers: stv::SumSurplusTransfersMode::PerBallot,
meek_surplus_tolerance: String::new(),
normalise_ballots: true,
quota: stv::QuotaType::Droop,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
@ -71,6 +74,7 @@ fn scotland_linn07_gfixed5() {
exclusion: stv::ExclusionMethod::SingleStage,
bulk_exclude: false,
defer_surpluses: false,
meek_immediate_elect: false,
pp_decimals: 5,
};
GuardedFixed::set_dps(5);