r2b2.minerva

Minerva audit module.

Module Contents

class r2b2.minerva.Minerva(alpha: float, max_fraction_to_draw: float, contest: r2b2.contest.Contest)

Bases: r2b2.audit.Audit

Minerva audit implementation.

A Minerva audit is a type of risk-limiting audit that accounts for round-by-round auditor decisions. For a given sample size (in the context of a round schedule), the audit software calculates a minimum number of votes for the reported winner that must be found in the sample to stop the audit and confirm the reported outcome.

Variables

• alpha (float) – Risk limit. Alpha represents the chance that, given an incorrectly called election, the audit will fail to force a full recount.

• max_fraction_to_draw (float) – The maximum number of ballots the auditors are willing to draw as a fraction of the ballots in the contest.

• contest (Contest) – Contest to be audited.

Initialize a Minerva audit.

get_min_sample_size(self, sub_audit: r2b2.audit.PairwiseAudit, min_sprob: float = 10 ** - 6)

Computes the minimum sample size that has a stopping size (kmin). Here we find a practical minimum instead of the theoretical minimum (BRAVO’s minimum) to avoid floating-point imprecisions in the later convolution process.

Parameters

• sub_audit (PairwiseAudit) – Get minimum sample size for this subaudit.

• min_sprob (float) – Round sizes with below min_sprob stopping probability are excluded.

Returns

int – The minimum sample size of the audit, adherent to the min_sprob.

satisfactory_sample_size(self, left, right, sprob, num_dist, denom_dist)

Helper method that returns True if the round size satisfies the stopping probability.

kmin_search_upper_bound(self, n, sub_audit: r2b2.audit.PairwiseAudit)

The Minerva kmin is no greater than the BRAVO kmin, so the latter serves as an upper bound for a kmin binary search.

(Solve for k: (p/.5)^k * ((1-p)/.5)^(n-k) > 1/alpha)

sample_size_kmin(self, left, right, num_dist, denom_dist, sum_num_right, sum_denom_right, orig_right)

Finds a kmin with a binary search given the twin distributions.

find_sprob(self, n, sub_audit: r2b2.audit.PairwiseAudit)

Helper method to find the stopping probability of a given prospective round size.

binary_search_estimate(self, left, right, sprob, sub_audit: r2b2.audit.PairwiseAudit)

Method to use binary search approximation to find a round size estimate.

next_sample_size_gaussian(self, sprob=0.9)

This is a rougher but quicker round size estimate for very narrow margins.

next_sample_size(self, sprob=0.9, verbose=False, *args, **kwargs)

Attempt to find a next sample size estimate no greater than 10000. Failing that, try to find an estimate no greater than 20000, and so on.

Parameters

• sprob (float) – Compute next sample for this stopping probability.

• verbose (bool) – If true, the kmin and stopping probability of the next sample size will be returned in addition to the next sample size itself.

Returns

Return maxmimum next sample size estimate across all pairwise subaudits. If verbose,

return information as specified above.

_next_sample_size_pairwise(self, sub_audit: r2b2.audit.PairwiseAudit, sprob=0.9)

Compute next sample size for a single pairwise subaudit.

Parameters

• sub_audit (PairwiseAudit) – Compute the sample size for this sub_audit.

• sprob (float) – Get the sample size for this stopping probability.

Returns

Estimate in the format [sample size, kmin, stopping probability].

stopping_condition_pairwise(self, pair: str, verbose: bool = False) → bool

Check, without finding the kmin, whether the subaudit is complete.

Parameters

pair (str) – Dictionary key referencing pairwise subaudit to evaluate.

Returns

bool – Whether or not the pairwise stopping condition has been met.

next_min_winner_ballots_pairwise(self, sub_audit: r2b2.audit.PairwiseAudit) → int

Compute stopping size for a given subaudit.

Parameters

sub_audit (PairwiseAudit) – Compute next stopping size for this subaudit.

Returns

int – Stopping size for most recent round.

compute_min_winner_ballots(self, sub_audit: r2b2.audit.PairwiseAudit, rounds: List[int], *args, **kwargs)

Compute the minimum number of winner ballots for a round schedule of a pairwise audit.

Extend the audit’s round schedule with the passed (partial) round schedule, and then extend the audit’s minimum number of winner ballots schedule with the corresponding minimums to meet the stopping condition.

Parameters

• sub_audit (PairwiseAudit) – Compute minimum winner ballots for this Pairwise subaudit.

• rounds (List[int]) – A (partial) round schedule of the audit.

find_kmin(self, sub_audit: r2b2.audit.PairwiseAudit, sample_size: int, append: bool)

Search for a kmin (minimum number of winner ballots) satisfying all stopping criteria.

Parameters

• sub_audit (PairwiseAudit) – Find kmin for this subaudit.

• sample_size (int) – Sample size to find kmin for.

• append (bool) – Optionally append the kmins to the min_winner_ballots list. This may not always be desirable here because, for example, appending happens automatically outside this method during an interactive audit.

compute_all_min_winner_ballots(self, sub_audit: r2b2.audit.PairwiseAudit, max_sample_size: int = None, *args, **kwargs)

Compute the minimum number of winner ballots for the complete (that is, ballot-by-ballot) round schedule.

Note: Due to limited convolutional precision, results may be off somewhat after the

stopping probability very nearly equals 1.

Parameters

• sub_audit (PairwiseAudit) – Compute minimum winner ballots for this pairwise subaudit.

• max_sample_size (int) – Optionally set the maximum sample size to generate stopping sizes (kmins) up to. If not provided the maximum sample size is determined by max_frac_to_draw and the total contest ballots.

Returns

None, kmins are appended to the min_winner_ballots list.

compute_risk(self, votes_for_winner: int, pair: str, *args, **kwargs)

Return the hypothetical pvalue if votes_for_winner were obtained in the most recent round.

get_risk_level(self)

Return the risk level of an interactive Minerva audit.

Non-interactive and bulk Minerva audits are not considered here since the sampled number of reported winner ballots is not available.

__repr__(self)

String representation of Audit class.

Note

Can (and perhaps should) be overwritten in subclass.

__str__(self)

Human readable string (i.e. printable) representation of Audit class.

Note

Can (and perhaps should) be overwritten in subclass.

current_dist_null(self)

Update distribution_null for each sub audit for current round.

_current_dist_null_pairwise(self, sub_audit: PairwiseAudit, bulk_use_round_size=False)

Update distribution_null for a single PairwiseAudit

Parameters

• sub_audit (PairwiseAudit) – Pairwise subaudit for which to update distribution.

• bulk_use_round_size (bool) – Optional argument used by bulk methods. Since the bulk methods do not sample ballots for candidates during the rounds, this flag simply uses the round schedule as the round draw (instead of the pairwise round draw) for updating the distribution. Default is False.

current_dist_reported(self)

Update distribution_reported_tally for each subaudit for current round.

_current_dist_reported_pairwise(self, sub_audit: PairwiseAudit, bulk_use_round_size=False)

Update dist_reported for a single PairwiseAudit.

Parameters

• sub_audit (PairwiseAudit) – Pairwise subaudit for which to update distriution.

• bulk_use_round_size (bool) – Optional argument used by bulk methods. Since the bulk methods do not sample ballots for candidates during the rounds, this flag simply uses the round schedule as the round draw (instead of the pairwise round draw) for updating the distribution. Default is False.

truncate_dist_null(self)

Update risk schedule and truncate null distribution for each subaudit.

_truncate_dist_null_pairwise(self, pair: str)

Update risk schedule and truncate null distribution for a single subaudit.

Parameters

pair (str) – Dictionary key for subaudit (within the audit’s subaudits) to truncate distribution and update risk schedule.

truncate_dist_reported(self)

Update stopping prob schedule and truncate reported distribution for each subaudit.

_truncate_dist_reported_pairwise(self, pair)

Update stopping prob schedule and truncate reported distribution for a single subaudit.

Parameters

pair (str) – Dictionary key for subaudit (within the audit’s subaudits) to truncate distribution and update stopping prob schedule.

__get_interval(self, dist: List[float])

Get relevant interval [l, u] of given distribution.

Find levels l and u such that cdf(l) < tolerance and 1 - cdf(u) < tolerance. The purpose of this is to improve efficiency in the current_dist_* functions for audits without replacement where almost all of the hypergeometric distribution falls in a fraction of its range, i.e. between l and u.

Note

cdf() in this context does not require cdf(infinity) = 1, although the distribution should sum very closely to 1.

asn(self, pair: str)

Compute ASN as described in BRAVO paper for pair of candidates.

Given the fractional margin for the reported winner and the risk limit (alpha) produce the average number of ballots sampled during the audit.

Parameters

pair (str) – Dictionary key referencing pairwise audit in audit’s subaudits.

Returns

int – ASN value.

execute_round(self, sample_size: int, sample: dict, verbose: bool = False) → bool

Execute a single, non-interactive audit round.

Executes 1 round of the audit, given its current state. If the audit is stopped, its state will not be modified.

Warning: This method assumes the audit is in the correct state to be executed. If multiple

executions of a full audit will be run the same audit object, make sure to call reset on the audit object between full executions.

Parameters

• sample_size (int) – Total ballots sampled by the end of this round (cumulative).

• sample (dict) – Sample counts for each candidate by the end of this round (cumulative).

Returns

bool – True if the audit met its stopping condition by this round.

run(self, verbose: bool = False)

Begin interactive audit execution.

Begins the interactive version of the audit. While computations for different audits will vary, the process for executing each one is the same. This provides a process for selecting a sample size, determining if the ballots found for the reported winner in that sample size meet the stopping condition(s), and if not continuing with the audit. As the audit proceeds, data including round sizes, ballots for the winner in each round size, and per round risk and stopping probability are stored.

_reset(self)

Reset attributes modified during run().

stopping_condition(self, verbose: bool = False) → bool

Determine if the audits stopping condition has been met.

The audit stopping condition is met if and only if each pairwise stopping condition is met.

next_min_winner_ballots(self, verbose: bool = False)

Compute next stopping size of given (actual) sample sizes for all subaudits.