election_audits.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Auditing Elections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Risks to Elections\n",
    "\n",
    "https://www.nytimes.com/interactive/2018/07/16/us/elections/russian-interference-statements-comments.html\n",
    "\n",
    "https://www.usatoday.com/story/news/2018/08/03/russian-us-election-interference-donald-trump/878910002/\n",
    "\n",
    "https://www.nbcnews.com/politics/elections/u-s-intel-russia-compromised-seven-states-prior-2016-election-n850296\n",
    "\n",
    "https://www.newyorker.com/news/news-desk/america-continues-to-ignore-the-risks-of-election-hacking\n",
    "\n",
    "https://www.nytimes.com/2018/09/26/magazine/election-security-crisis-midterms.html\n",
    "\n",
    "https://freedom-to-tinker.com/2018/10/16/design-flaw-in-dominion-imagecast-evolution-voting-machine/\n",
    "\n",
    "https://freedom-to-tinker.com/2018/10/22/an-unverifiability-principle-for-voting-machines/\n",
    "\n",
    "https://www.apnews.com/f6876669cb6b4e4c9850844f8e015b4c \n",
    "\n",
    "http://www8.nationalacademies.org/onpinews/newsitem.aspx?RecordID=25120\n",
    "\n",
    "http://time.com/5340060/donald-trump-vladimir-putin-summit-russia-meddling/\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Potential goals: FUD (fear, uncertainty, doubt)\n",
    "\n",
    "+ Alter election results through social manipulation, propaganda, etc. \"social hacking\"\n",
    "    - \"fake news\" propagated through social media, etc. \n",
    "    - disinformation regarding how to vote, polling-place location, etc. http://fortune.com/2016/11/03/text-vote-hillary-clinton/\n",
    "\n",
    "+ Alter election results through election equipment, tabulation, reporting. \"computer hacking\"\n",
    "\n",
    "+ Alter election results by removing voters from voter registration lists. \"computer hacking\"\n",
    "\n",
    "+ Cast doubt on election results and on the electoral process: clumsy hacks are effective"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Election technology, including vote tabulation, is vulnerable. What can we do?\n",
    "\n",
    "If there's a trustworthy, voter-verified paper trail, that can be used to check the results.\n",
    "\n",
    "For instance, could hand count the votes on all the ballots.\n",
    "\n",
    "Can we use Statistics to do less work than a full hand count?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Audit goals\n",
    "\n",
    "The basic goal of auditing is to check the electronic results, using the paper trail, which is assumed to be trustworthy (because it passed a _compliance audit_).\n",
    "\n",
    "+ Precisely what do we want to check? What is the right standard for accuracy?\n",
    "\n",
    "+ How can Statistics help?\n",
    "\n",
    "+ State laws https://www.verifiedvoting.org/verifier/\n",
    "    - some states have no voter-verifiable paper trail\n",
    "    - of those that do, rules governing protecting the paper generally are inadequate\n",
    "    - many states with paper many do not audit results\n",
    "    - of those that audit results, \n",
    "        + only Colorado currently audits in a rigorous way--but it only audits a few contests\n",
    "        + Rhode Island will soon conduct good audits\n",
    "        + New Mexico's audits have some good features\n",
    "        + California's audits got worse in 2017; has had good pilot programs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Detection Paradigm\n",
    "\n",
    "+ Before 2006, audits generally looked at some fixed percentage of votes or precincts selected \"at random\" and compared electronic results to manual tabulation\n",
    "    - Some even worse, e.g., select 500 ballots and tabulate them by machine, retabulate by hand\n",
    "    \n",
    "+ Academic work focused on _detection_:\n",
    "    - Suppose the reported outcome is wrong. How many precincts/ballots need to be checked by hand to have a high probability of finding at least one error?\n",
    "    - Not the best question to ask: audits of hand-marked ballots likely to find at least one misinterpreted ballot. So what?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The evidence paradigm\n",
    "\n",
    "+ An audit should give strong evidence that the outcome is right (if it is right), or should correct the outcome if it is wrong.\n",
    "\n",
    "To correct an outcome requires a full manual tally: can't overturn the result using statistical evidence alone."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A _risk-limiting audit_ (RLA) is any post-election procedure that offers the following statistical guarantee: \n",
    "\n",
    "> _If a full manual tally of the complete voter-verifiable paper trail would show a different \n",
    "electoral outcome, there is a known, pre-determined minimum chance that the procedure \n",
    "will lead to a full manual tally._\n",
    "\n",
    "If the procedure does lead to a full manual tally, the result of that tally replaces the \n",
    "reported result, thereby correcting it.\n",
    "    \n",
    "The maximum chance that the procedure will _not_ lead to a full manual tally if that tally\n",
    "would show a different outcome is called the _risk limit_.\n",
    "\n",
    "The risk limit is the largest chance that the audit will fail to correct\n",
    "an outcome that is incorrect, where _incorrect_ means that a full manual tally of the\n",
    "voter-verifiable paper trail would find different winner(s).\n",
    "\n",
    "A RLA with a risk limit of 5% has at least a 95% chance of requiring a full manual\n",
    "tally, if that tally would show a different outcome.\n",
    "\n",
    "For an overview of risk-limiting audits, see https://www.stat.berkeley.edu/~stark/Preprints/lhc18.pdf\n",
    "\n",
    "For a more technical discussion and example methods, see Lindeman and Stark (2012)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aside: Compliance Audits\n",
    "\n",
    "An audit that relies on an untrustworthy paper trail, or any audit that purports to ascertain voter \n",
    "intent from an electronic record or from an artifact that the voter did not have the opportunity\n",
    "to check, is \"security theater.\"\n",
    "\n",
    "There is little reason to believe that a full manual tally of such records would reveal the true winner(s). \n",
    "\n",
    "It's crucial to:\n",
    "\n",
    "+ base audits on voter-verifiable paper records\n",
    "+ ensure that those records include every validly cast vote exactly once, and no others (checking the determination of eligibility, in particular)\n",
    "+ ensure that those records remain complete and intact from the moment they are cast through the audit\n",
    "+ assess the evidence that they are trustworthy.\n",
    "\n",
    "Without evidence that the paper trail is a trustworthy\n",
    "record of voter intent--that it accurately reflects the intent of every voter who legitimately cast\n",
    "a ballot in the contests under audit, and no others--the audit might simply confirm the incorrect\n",
    "outcome.\n",
    "\n",
    "The process of assessing the trustworthiness of the paper trail is called a _compliance audit_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compliance audits should include the following steps, among others:\n",
    "\n",
    "+ Ballot accounting. \n",
    "    - Check that the number of ballots sent to polling places equals the number returned\n",
    "voted plus the number returned spoiled, plus the number returned unvoted. (For systems that print ballots on demand, check that the paper stock--sheets cast, spoiled, and still blank--adds up to the number of sheets sent to the polling place or vote center.)\n",
    "    - Check that the number of ballots returned from each polling place does not exceed the \n",
    "number of voters registered at that polling place or the number of pollbook signatures at the polling place\n",
    "    - Check that the number of ballots of each style corresponds to the number of ballots\n",
    "of each style reported by the voting system. Ballot counts for this purpose should be based on the physical\n",
    "paper, not on the voting system: the audit needs external touchstones to check the voting system.\n",
    "\n",
    "+ Eligibility.\n",
    "    - Check signature verification on vote-by-mail ballots, especially if signature verification was automated.\n",
    "    - Check the disposition of provisional ballots to ensure that all that were validly cast (and no others) were included in the results.\n",
    "    - Check that each voter received the correct ballot style based on her eligibility. For vote-by-mail ballots, there should be a record of the ballot style mailed to the voter; for in-person voting, this might require recording (e.g., in pollbooks) the ballot style given to the voter. For provisionally cast ballots, this might be more complicated.\n",
    "+ Physical chain of custody. \n",
    "    - Record seal numbers whenever a batch of ballots is sealed.\n",
    "    - Check physical seals for signs of tampering whenever a batch is unsealed. (Good procedure is to photograph each seal after it is applied, check each seal against its photograph before breaking the seal, perhaps taking a second photograph to document the state of the seal, and record any discrepancies.)\n",
    "    - Use numbered seals that are hard to forge or bypass; check seal numbers against the numbers recorded when the boxes or bags were sealed; and log the result.\n",
    "    - Review custody logs. Check that at least two staff accompanied the ballots whenever ballots were not locked securely and under surveillance.\n",
    "    - Review surveillance video of secure ballot storage facility to ensure there was no unauthorized access to ballots.\n",
    "+ Due diligence regarding processes, equipment, etc.\n",
    "    - Review voting equipment event logs.\n",
    "    - Review any complaints made by voters or anomalies or problems noted by pollworkers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Obstacles\n",
    "\n",
    "+ Local election officials\n",
    "\n",
    "+ State laws / legislators\n",
    "\n",
    "+ Perceived costs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sampling Strategies\n",
    "\n",
    "+ Comparison audits: compare machine tabulation to hand tabulation.\n",
    "    - 3 stages: \n",
    "        + export subtotals from voting system and \"commit\"\n",
    "        + check that exported subtotals reproduce reported contest results\n",
    "        + check random sample of subtotals against hand counts of the paper\n",
    "    - batch-level (precincts, machines, etc.) Requires data export / munging\n",
    "    - ballot-level. Requires modern equipment\n",
    "\n",
    "+ Polling audits: use paper directly\n",
    "    - one stage: look at ballots, not at electronic results\n",
    "    - batches\n",
    "    - individual ballots\n",
    "    \n",
    "+ Combinations of comparison and polling\n",
    "    \n",
    "+ Sample design: with or without replacement? stratified or unstratified?\n",
    "\n",
    "+ Comparison audits and polling audits generally require a _ballot manifest_ as a sampling frame (c.f. Bernoulli ballot polling). Ballot manifest describes how the ballots are stored."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Auditing as a statistical hypothesis test\n",
    "\n",
    "+ Null hypothesis: reported outcome is incorrect\n",
    "    - _outcome_ means winner(s), not exact counts\n",
    "    - _incorrect_ means an accurate, full handcount would find other winner(s)\n",
    "\n",
    "+ Type I error: certifying an incorrect outcome (seating the wrong winner)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Social choice functions\n",
    "\n",
    "Most common in the US are variants of _plurality_:\n",
    "\n",
    "+ Majority (common for ballot measures)\n",
    "+ Plurality (\"first past the post\")\n",
    "+ $k$-plurality\n",
    "\n",
    "Also in the US: Instant Runoff Voting (IRV), a form of Ranked-Choice Voting (RCV)\n",
    "\n",
    "Elsewhere and non-political: \n",
    "+ proportional representation (e.g., D'Hondt for parliamentary elections)\n",
    "+ single transferrable vote (STV)\n",
    "+ approval, Borda, many others"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Transforming \"incorrect outcome\" into math\n",
    "\n",
    "Depends on social choice function. Concentrate on plurality-type functions.\n",
    "\n",
    "+ $\\mathcal{W}$: the set of reported winners of the contest\n",
    "\n",
    "+ $\\mathcal{L}$: the set of reported losers of the contest\n",
    "\n",
    "+ $N_s$ ballots were cast in stratum $s$. (The contest might not appear on all $N_s$ ballots.)\n",
    "\n",
    "+ $P$ \"batches\" of ballots are in stratum $s$. A batch contains one or more ballots. Every ballot in stratum $s$ is in exactly one batch.\n",
    "\n",
    "+ $n_p$: number of ballots in batch $p$. $N_s = \\sum_{p=1}^P n_p$.\n",
    "\n",
    "+ $v_{pi} \\in \\{0, 1\\}$: reported votes for candidate $i$ in batch $p$\n",
    "\n",
    "+ $a_{pi} \\in \\{0, 1\\}$: actual votes for candidate $i$ in batch $p$. If the contest does not appear on any ballot in batch $p$, then $a_{pi} = 0$.\n",
    "\n",
    "+ $V_{w\\ell,s} \\equiv \\sum_{p=1}^P (v_{pw} - v_{p\\ell})$: \n",
    "Reported margin in stratum $s$ of reported winner $w \\in \\mathcal{W}$ over reported loser \n",
    "$\\ell \\in \\mathcal{L}$, in votes.\n",
    "\n",
    "+ $V_{w\\ell}$: \n",
    "overall reported margin in votes of reported winner $w \\in \\mathcal{W}$ over reported loser \n",
    "$\\ell \\in \\mathcal{L}$ for the entire contest (not just stratum $s$)\n",
    "\n",
    "+ $V \\equiv \\min_{w \\in \\mathcal{W}, \\ell \\in \\mathcal{L}} V_{w \\ell}$: \n",
    "smallest reported overall margin in votes between any reported winner and reported loser\n",
    "\n",
    "+ $A_{w\\ell,s} \\equiv \\sum_{p=1}^P (a_{pw} - a_{p\\ell})$: \n",
    "actual margin in votes in the stratum of reported winner $w \\in \\mathcal{W}$ over reported loser \n",
    "$\\ell \\in \\mathcal{L}$\n",
    "\n",
    "+ $A_{w\\ell}$: \n",
    "actual margin in votes of reported winner $w \\in \\mathcal{W}$ over reported loser \n",
    "$\\ell \\in \\mathcal{L}$ for the entire contest (not just in stratum $s$)\n",
    "\n",
    "\n",
    "Reported winner(s) really won if $A_{w\\ell} > 0$ for all $w \\in \\mathcal{W}$, $\\ell \\in \\mathcal{L}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For unstratified polling-based audits, natural to work with proportions: $w$ really beat $\\ell$ if $\\pi_{w\\ell} > 1/2$, where\n",
    "\n",
    "\\begin{equation*} \n",
    "   \\pi_{w\\ell} \\equiv \\frac{\\# \\mbox{ballots with votes for only $w$}}{\\# \\mbox{ballots with votes for only $w$ or for only $\\ell$}}.\n",
    "\\end{equation*}\n",
    "\n",
    "Can test using [Wald's Sequential Probability Ratio Test](https://github.com/pbstark/S157F17/blob/master/sprt.ipynb) (also see [SPRT without replacement](https://github.com/pbstark/S157F17/blob/master/pSPRTnoReplacement.ipynb)).\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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": 4
}