#!/usr/bin/env python
# coding: utf-8

# # The SHANGRLA framework for Risk-Limiting Election Audits

# ## Half-average nulls
# 
# Reduce auditing elections to multiple instances of the same statistical question: is the mean of a bounded list of
# nonnegative numbers less than or equal to 1/2?
# 
# 

# ## Two-candidate plurality
# 
# $b_i$ is $i$th ballot card, $N$ cards in all.
# 
# + mark for Alice but not Bob, $A_{\mathrm{Alice, Bob}} (b_i) := 1$.
# 
# + mark for Bob but not Alice, $A_{\mathrm{Alice, Bob}} (b_i) := 0$.
# 
# + marks for both (overvote) or neither (undervote) or doesn't contain contest,
# $A_{\mathrm{Alice, Bob}} (b_i) := 1/2$.
# 
# 
# $$
#    \bar{A}_{\mathrm{Alice, Bob}}^b :=  \frac{1}{N} \sum_{i=1}^N A_{\mathrm{Alice, Bob}} (b_i).
# $$
# 
# Mean of a finite list of $N$ bounded, nonnegative numbers.
# 
# Alice won iff $\bar{A}_{\mathrm{Alice, Bob}}^b > 1/2$.
# 
# 
# ## General Plurality & Approval Voting
# 
# $K \ge 1$ winners, $C>K$ candidates in all.
# 
# Candidates $\{w_k\}_{k=1}^K$ are reported winners.
# 
# Candidates $\{\ell_j\}_{j=1}^{C-K}$ reported losers.
# 
# 
# Outcome correct iff
# 
# $$
#   \bar{A}_{\mathrm{w_k, \ell_j}}^b > 1/2,  \;\; \mbox{ for all } 1 \le k \le K, \;\; 1 \le j \le C-K
# $$
# 
# Means of $K(C-K)$ lists of nonnegative, bounded numbers.
# 
# 
# Same approach works for D'Hondt, Hamilton, & other proportional representation schemes.
# (Stark & Teague 2015; 
# 
# 
# ## Super-majority 
# 
# $f \in (0, 1]$. 
# 
# Alice won iff
# 
# $$ 
# \mbox{(votes for Alice)} > f \times \left ( \mbox{valid votes for anyone} \right )
# $$
# 
# Set
# $$ 
#   A(b_i) :=  \left \{ \begin{array}{ll} 
#         \frac{1}{2f}, & \mbox{$b_i$ has a mark for Alice and no one else} \\
#         0, & \mbox{$b_i$ has a mark for exactly one candidate, not Alice} \\
#         \frac{1}{2}, & \mbox{otherwise}.
#         \end{array}
#         \right .
# $$ 
# 
# Alice won iff 
# $$
#  \bar{A}^b > 1/2.
# $$ 
# 
# ---
# 
# ## Borda count, STAR-Voting, & other additive weighted schemes
# 
# Winner is the candidate who gets most "points" in total.
# 
# $s_{\mathrm{Alice}}(b_i)$: Alice's score on ballot $i$.
# 
# $s_{\mathrm{cand}}(b_i)$: another candidate's score on ballot $i$.
# 
# $s^+$: upper bound on the score any candidate can get on a ballot.
# 
# Alice beat the other candidate iff Alice's total score is bigger than theirs:
# 
# $$
#    A_{\mathrm{Alice, c}}(b_i) :=  \frac{s_{\mathrm{Alice}}(b_i) - s_{\mathrm{c}}(b_i) + s^+}{2s^+}.
# $$
# 
# Alice won iff $\bar{A}_{\mathrm{Alice, c}}^b > 1/2$ for every other candidate $c$.
# 
# 
# ## Ranked-Choice Voting, Instant-Runoff Voting (RCV/IRV)
# 
# 2 types of assertions (Blom et al. 2018):
# 
# 1. Candidate $i$ has more first-place ranks than candidate $j$ has total mentions.
# 1. After a set of candidates $E$ have been eliminated from consideration, candidate $i$ is ranked
# higher than candidate $j$ on more ballots than _vice versa_.
# 
# Both can be written $\bar{A}^b > 1/2$.
# 
# Finite set of such assertions implies reported outcome is right.
# 
# More than one set suffices; can optimize expected workload.
# 
# ---
#    
# ## Auditing assertions 
# 
# Test _complementary null hypothesis_ $\bar{A}^b \le 1/2$ sequentially.
# 
# + Audit until either all complementary null hypotheses about a contest are rejected at significance 
# level $\alpha$ or until all ballots have been tabulated by hand.
# 
# + No multiplicity adjustment needed.
# 

# In[ ]: