{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4244bc3d-706b-430f-9e2d-b2c0156bd05b",
   "metadata": {},
   "source": [
    "# The SHANGRLA framework for Risk-Limiting Election Audits"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e2e9fd8-3baa-4399-b08f-30343b9ace41",
   "metadata": {},
   "source": [
    "## Half-average nulls\n",
    "\n",
    "Reduce auditing elections to multiple instances of the same statistical question: is the mean of a bounded list of\n",
    "nonnegative numbers less than or equal to 1/2?\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4c6ca07-dfca-49f8-9834-c5c09dae7cda",
   "metadata": {},
   "source": [
    "## Two-candidate plurality\n",
    "\n",
    "$b_i$ is $i$th ballot card, $N$ cards in all.\n",
    "\n",
    "+ mark for Alice but not Bob, $A_{\\mathrm{Alice, Bob}} (b_i) := 1$.\n",
    "\n",
    "+ mark for Bob but not Alice, $A_{\\mathrm{Alice, Bob}} (b_i) := 0$.\n",
    "\n",
    "+ marks for both (overvote) or neither (undervote) or doesn't contain contest,\n",
    "$A_{\\mathrm{Alice, Bob}} (b_i) := 1/2$.\n",
    "\n",
    "\n",
    "$$\n",
    "   \\bar{A}_{\\mathrm{Alice, Bob}}^b :=  \\frac{1}{N} \\sum_{i=1}^N A_{\\mathrm{Alice, Bob}} (b_i).\n",
    "$$\n",
    "\n",
    "Mean of a finite list of $N$ bounded, nonnegative numbers.\n",
    "\n",
    "Alice won iff $\\bar{A}_{\\mathrm{Alice, Bob}}^b > 1/2$.\n",
    "\n",
    "\n",
    "## General Plurality & Approval Voting\n",
    "\n",
    "$K \\ge 1$ winners, $C>K$ candidates in all.\n",
    "\n",
    "Candidates $\\{w_k\\}_{k=1}^K$ are reported winners.\n",
    "\n",
    "Candidates $\\{\\ell_j\\}_{j=1}^{C-K}$ reported losers.\n",
    "\n",
    "\n",
    "Outcome correct iff\n",
    "\n",
    "$$\n",
    "  \\bar{A}_{\\mathrm{w_k, \\ell_j}}^b > 1/2,  \\;\\; \\mbox{ for all } 1 \\le k \\le K, \\;\\; 1 \\le j \\le C-K\n",
    "$$\n",
    "\n",
    "Means of $K(C-K)$ lists of nonnegative, bounded numbers.\n",
    "\n",
    "\n",
    "Same approach works for D'Hondt, Hamilton, & other proportional representation schemes.\n",
    "(Stark & Teague 2015; \n",
    "\n",
    "\n",
    "## Super-majority \n",
    "\n",
    "$f \\in (0, 1]$. \n",
    "\n",
    "Alice won iff\n",
    "\n",
    "$$ \n",
    "\\mbox{(votes for Alice)} > f \\times \\left ( \\mbox{valid votes for anyone} \\right )\n",
    "$$\n",
    "\n",
    "Set\n",
    "$$ \n",
    "  A(b_i) :=  \\left \\{ \\begin{array}{ll} \n",
    "        \\frac{1}{2f}, & \\mbox{$b_i$ has a mark for Alice and no one else} \\\\\n",
    "        0, & \\mbox{$b_i$ has a mark for exactly one candidate, not Alice} \\\\\n",
    "        \\frac{1}{2}, & \\mbox{otherwise}.\n",
    "        \\end{array}\n",
    "        \\right .\n",
    "$$ \n",
    "\n",
    "Alice won iff \n",
    "$$\n",
    " \\bar{A}^b > 1/2.\n",
    "$$ \n",
    "\n",
    "---\n",
    "\n",
    "## Borda count, STAR-Voting, & other additive weighted schemes\n",
    "\n",
    "Winner is the candidate who gets most \"points\" in total.\n",
    "\n",
    "$s_{\\mathrm{Alice}}(b_i)$: Alice's score on ballot $i$.\n",
    "\n",
    "$s_{\\mathrm{cand}}(b_i)$: another candidate's score on ballot $i$.\n",
    "\n",
    "$s^+$: upper bound on the score any candidate can get on a ballot.\n",
    "\n",
    "Alice beat the other candidate iff Alice's total score is bigger than theirs:\n",
    "\n",
    "$$\n",
    "   A_{\\mathrm{Alice, c}}(b_i) :=  \\frac{s_{\\mathrm{Alice}}(b_i) - s_{\\mathrm{c}}(b_i) + s^+}{2s^+}.\n",
    "$$\n",
    "\n",
    "Alice won iff $\\bar{A}_{\\mathrm{Alice, c}}^b > 1/2$ for every other candidate $c$.\n",
    "\n",
    "\n",
    "## Ranked-Choice Voting, Instant-Runoff Voting (RCV/IRV)\n",
    "\n",
    "2 types of assertions (Blom et al. 2018):\n",
    "\n",
    "1. Candidate $i$ has more first-place ranks than candidate $j$ has total mentions.\n",
    "1. After a set of candidates $E$ have been eliminated from consideration, candidate $i$ is ranked\n",
    "higher than candidate $j$ on more ballots than _vice versa_.\n",
    "\n",
    "Both can be written $\\bar{A}^b > 1/2$.\n",
    "\n",
    "Finite set of such assertions implies reported outcome is right.\n",
    "\n",
    "More than one set suffices; can optimize expected workload.\n",
    "\n",
    "---\n",
    "   \n",
    "## Auditing assertions \n",
    "\n",
    "Test _complementary null hypothesis_ $\\bar{A}^b \\le 1/2$ sequentially.\n",
    "\n",
    "+ Audit until either all complementary null hypotheses about a contest are rejected at significance \n",
    "level $\\alpha$ or until all ballots have been tabulated by hand.\n",
    "\n",
    "+ No multiplicity adjustment needed.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "001e4967-cd04-4c0b-81f6-43c62d1705c4",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}