{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Voting and Auditing with Ternary Plurality Trees\n", "\n", "## by Ronald L. Rivest\n", "\n", "### August 23, 2019" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Abstract\n", "\n", "We suggest using \"_ternary plurality trees_\" to define a voting method (called TPT). \n", "TPT voting is quite close to, but different than, plurality voting; we examine how close TPT and plurality are.\n", "\n", "Perhaps the most interesting aspects of TPT voting have to do with auditing. Auditing a TPT contest is __combinatorial__ in character rather than __statistical__ (as with a risk-limiting audit). With TPT voting an election contest with $3^d$ cast ballots can be audited in a _zero-risk_ manner by manually examining only $2^d$ cast paper ballots, in the case of two candidates, with no missing or invalid ballots. For example, a two-candidate contest with one million cast paper ballots may be audited by examining only 6104 ballots, assuming no interpretation errors are found in the audit.\n", "\n", "The $n$ cast ballots are arranged as the leaves in a ternary tree of height $\\log_3(n)$.\n", "Each internal node of the tree has a value equal to the plurality vote of its three children (with ties broken pseudorandomly).\n", "The value at the root is the winner of the contest, by definition.\n", "Auditing the contest outcome requires examining only two of every three children of audited nodes (assuming two candidates and no discrepancies discovered).\n", "\n", "The TPT voting method is quite close to, but different than, plurality voting; we \n", "examine how close TPT and plurality are.\n", "\n", "The outcome of a TPT election may depend on the way in which ballots are assigned to\n", "leaves of the tree. TPT assigns ballots to leaves in a randomized manner to ensure \n", "that all voters may expect an equal voice in the outcome.\n", "\n", "We present the result of a simple experiment illustrating how auditing a TPT election expands gracefully when interpretation errors are found.\n", "\n", "Finally, we show how the TPT method extends to handle multiple candidates\n", "and ballots with missing or invalid choices.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "** Motivating example **\n", "\n", "We begin with a quick example that illustrates many of the key ideas.\n", "\n", "Imagine that we have an election with nine voters, each voting for one of two candidates, A or B. The first voter votes for B, the second for A, and so on.\n", "\n", "We arrange the nine votes as the leaves of a ternary tree of depth two, shown as labelled square boxes in the figure below. The voter's number is shown below each leaf.\n", "\n", "There are four internal nodes, drawn as circles: the root at the top at level 0, and three internal nodes at level 1 which are its children. Each level-1 node has three leaves as its children.\n", "\n", "The winner of the contest is computed on this tree in a bottom-up manner. Each leaf has a value that is the that voter's choice. Each internal node has a value that is the plurality of the values of its children. (With only two candidates and a ternary tree, plurality is the same as majority.)\n", "\n", "The value at the root is the winner of the contest. In this case, candidate B is the winner." ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeoAAAEkCAYAAADgj3L+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3deXSTZb4H8G+aNpRSoGUvCAUFZVEoUKQdihQYZBGBeiiLOAqDKD0w545X9KqXpaOMg4DCXLQuXIZBWwHZGbZKoaxtoS0tYIWhzAx4WCr7VqBtkuf+wX0zxG5Z3uTdvp9zOKdN3jz5PbzLr9/kzRuTEEKAiIiIVClA6QKIiIioemzUREREKsZGTUREpGJs1ERERCrGRk1ERKRibNREREQqxkZNRESkYmzUREREKsZGTUREpGJs1ERERCrGRk1ERKRibNREREQqxkZNRESkYmzUREREKsZGTUREpGJs1ERERCrGRk1ERKRibNREREQqxkZNRESkYmzUREREKsZGTUREpGJs1ERERCrGRk1ERKRibNREREQqxkZNRESkYmzUREREKsZGTUREpGJs1ERERCrGRk1ERKRibNREREQqxkZNRESkYmzUREREKhaodAFEpG4XLlzAvn37kJeXhxMnTqC0tBSBgYGIiIhAjx490KtXL8TGxsJsNitdKpEumYQQQukiiEh9du3ahU8//RSbN2+G3W6vcdl27dph6tSpmDJlCsLDw/1UIZExsFETkZNLly5h2rRpWLt2rduPbd68Ob744guMGjXKB5URGRMbNRE5HDhwAAkJCbhy5YrjtpYtW+KVV15BXFwcunfvjvDwcFRUVKC4uBh5eXlYv3490tPTncZ59dVX8fnnnyMwkO+uEXmLjZqIAAD79u3DkCFDcO/ePQBA48aN8cknn2D8+PEICgqq8bGnT5/Gm2++ic2bNztuS0xMxMqVK/neNZGX2KiJCP/85z8RFRWF27dvAwB+/etfIzU1Fc2bN3d5DCEEvv76a7z22msoLy8HALz55ptYuHChT2omMgo2aiKDs9vtGDBgAPbu3QsAGDZsGNavX486dep4NN727dsxcuRIVFRUwGQyYe/evejbt6+cJRMZCj9HTWRwf/nLXxxNOjIyEqtWrarUpJOTk2EymRz/6tSpg8cffxzJyckoKytzWnbo0KH48MMPATxI2ZMnT4bVavXPZIh0iI2ayMCEEPjkk08cvy9btgz169evclmLxYLs7GxkZ2cjPT0dEydOxB//+Ee88847lZZ94403EBMTAwAoLi7G1q1bfTMBIgNgoyYysH379uHEiRMAgL59+2LgwIHVLmsymRATE4OYmBjEx8fjvffew0svvYR169ZVWtZsNmPWrFmO31NSUuQvnsgg2KiJDGzTpk2On5OSktx+fP369VFRUVHlfYMHD0bbtm0BABkZGSgtLfWoRiKjY6MmMrD8/HzHz4MGDap1eavVCqvVitLSUmRkZCA1NRWJiYlVLms2mx0J3W634+jRo/IUTWQwbNREBlZQUAAAaNOmDZo0aVLjsmVlZQgKCkJQUBBCQ0MxaNAgxMbGYv78+dU+pmfPno6fCwsL5SmayGB42SAig7Lb7Y7PTbdq1arW5S0WCw4ePAgAqKioQFFREWbPno3Ro0fjb3/7G0wmU6XHPDzu9evXZaqcyFjYqInIJSaTCdHR0Y7fY2NjERYWhsTEROzYsQNDhw5VsDoi/eJL30QGFRAQ4Pgo1vnz5z0ao0uXLgCAY8eOVXn/w+PyW7WIPMNGTWRg3bt3BwD89NNPTl/E4arjx48DAJo2bVrl/Q+frBYVFeVBhUTEl76JDKxnz57Yt28fAGDnzp0YP358tcsKIZCTkwPg3+9RJycno0WLFkhISKi0vM1mw65duwA8SO9s1ESeYaImMrCRI0c6fv78889rXLa8vByxsbGIjY1F//79MW/ePAwZMgQ5OTlVvqydnp6OM2fOAHjwJR8hISGy1k5kFPxSDiIDKy4uRlRUFO7evQvgwYVJaro6matsNhvi4uIcCXzjxo1OfxQQkeuYqIkMyG63489//jO6devmaNIAMHnyZMdHtryxaNEiR5N+9NFH8dxzz3k9JpFRsVETGczp06fRr18//P73v8e9e/ec7jt79izGjRtX6Rux3LF9+3a89957jt+vXbuGjRs3ejwekdGxURMZhJSiu3btigMHDlS73LZt2zB8+HD8/PPPbo0vhMCKFSswatQox/W/p06div79+yMxMRFjx47F5cuXvZoDkRGxURMZQE0pWtK9e3cEBwcDePBedZcuXfD1119X+6Ubvxx/5MiRmDhxIsrLywEAY8aMwaeffop169Zh5cqV2LVrF7p06YK1a9fKNzEiIxBEpFs2m00sXrxY1K1bVwCo8l+9evVESkqKsNlsYv/+/aJJkyZO90dERIh33nlHbNmyRZw/f17cu3dP3Lp1S+Tl5Ykvv/xSPPvss5XGfPXVV0VFRYVTLSUlJSIhIUEAEGPGjBGXLl1S6H+FSFt41jeRTp0+fRqTJk2q8WXu/v37Y9myZWjXrp3jtsuXL2PatGlYs2aN28/ZvHlzfPHFFxg1alSV9wshsHr1akyfPh0BAQFISUnB6NGj3X4eIiPhS99EOuPKe9H16tVDSkoKMjIynJo08OAqY9999x127dqFhIQEBATUfpho164d5s+fjxMnTlTbpIEH1wsfN24cioqKEBcXx/euiVzARE2kI56m6JpcuHAB+/fvR15eHhYvXgyr1eq4r27duti5cydiY2NdaugPY7omcg0bNZEO2O12LFmyBO+++261J4vVq1cPCxYswOuvv+52U5U0atTI6esqw8PDce3aNY/Gkvz8889ISkrChg0bHCegVXftcCIj4kvfRBrnyhnd/fv3x/Hjx5GUlORxk/aV5s2b88xwohqoa48lIpd5+160mvC9a6LqsVETaZDWU3R1mK6JKtPG3ktEAPSVoqvDdE3kjI2aSCP0mqKrw3RN9IC292QiAzBCiq4O0zURGzWRqhktRVeH6ZqMTJ97NZHGGTlFV4fpmoyKjZpIZZiia8Z0TUZjrD2cSMWYol3HdE1GwkZNpAJM0Z5huiYj4N5OpCCmaO8xXZPesVETKYQpWl5M16RX3POJ/Iwp2neYrkmP2KiJ/Igp2j+YrklPeBQg8gOmaP9juia9YKMm8jGmaGUxXZPW8YhA5CNM0erBdE1axkZN5ANM0erEdE1axKMDkYyYotWP6Zq0ho2aSCZM0drCdE1awSMFkZeYorWL6Zq0gI2ayAtM0frAdE1qxqMGkQeYovWH6ZrUio2ayE1M0frGdE1qwyMIkYuYoo2D6ZrUhI2ayAVM0cbEdE1qwKMJUQ2YoonpmpTGRk1UDaZoehjTNSmFRxaiX2CKpuowXZMS2KiJHsIUTa5guiZ/4lGGCEzR5D6ma/IXNmoyPKZo8gbTNfkajzhkWEzRJBema/IlNmoyJKZo8gWma/IFHn3IUJiiydeYrklubNRkGEzR5E9M1yQXHolI95iiSSlM1yQHNmrSNVdS9IABA/DDDz8wRZPPMF2TN3hUIl1yJ0Xv3LkTbdu29W+BZDhM1+QpNmrSHaZoUjOma3IXj1CkG0zRpBVM1+QONmrSBaZo0iKma3IFj1akaUzRpHVM11QbNmrSLKZo0hOma6oOj1ykOUzRpFdM11QVNmrSFKZoMgKma3oYj2KkCUzRZDRM1yRhoybVY4omI2O6Jh7RSLWYookeYLo2NjZqUiWmaKLKmK6NiUc3UhWmaKKaMV0bDxs1qQZTNJHrmK6Ng0c6UhxTNJFnmK6NgY2aFMUUTeQ9pmt941GPFMEUTSQvpmv9YqMmv2OKJvIdpmv94RGQ/IYpmsg/mK71hY2a/IIpmsj/mK71gUdD8immaCJlMV1rHxs1+QxTNJF6MF1rF4+MJDumaCJ1YrrWJjZqkhVTNJH6MV1rC4+SJAumaCJtYbrWDjZq8hpTNJF2MV2rH4+Y5DGmaCJ9YLpWNzZq8ghTNJH+MF2rE4+e5BamaCJ9Y7pWHzZqchlTNJFxMF2rB4+kVCumaCJjYrpWB5MQQihdBMmnoqICmZmZOHz4MPLz83H+/HlYrVbUrVsXnTp1Qs+ePREfH49OnTq5NN7p06cxadKkahs08CBFL1u2jA1ap06dOoU9e/YgLy8Py5cvh9VqddwXHByMdevW4de//jUsFouCVZKvCSGwevVqTJ8+HQEBAUhJScHo0aOVLssQ2Kh14sqVK/jss8/w1Vdf4cKFC7Uu37dvX0yfPh2jR4+u8iVqu92OJUuW4N133632Ze569ephwYIFeP311/kyt84IIbBp0yYsWbIEu3fvrnX5Zs2aYcqUKZg+fTpatGjhhwpJKT///DOSkpKwYcMGjBkzBp9++imaNm3q1hglJSU4dOgQzp49C7PZDCEEhBBo0KABoqOj0blzZ5hMJh/NQIMEad53330nmjRpIgBU+S8wMLDa++Lj48U//vEPp/GKi4tFXFxctY8BIAYMGCD+9a9/KTNh8qmffvpJDB48uMbtyWQyVXlfWFiYWLFihbDb7UpPg3zIbreLlStXisaNG4umTZuKNWvWuPSY9PR0sWDBApGWlibOnDlTaTu5fv26+P7778WCBQvEsmXLRGlpqa+moCls1BpWXl4uJk2a5HSgDAgIEKNGjRKpqani5MmTwmazCSGEuHPnjjh48KBYsGCB6NSpk9NjQkJCxMaNG4XNZhOLFy8WdevWrfYgXa9ePZGSkuIYl/QlPT1dNGjQwGmdt2/fXvzpT38S+/btE7du3RJCCGGz2cSpU6fEypUrRWJiYqU/BseMGSPu37+v8GzI10pKSkRCQoJjnV+6dKnK5S5evCg++OADkZ+f7/LYly9fFh999JHYv3+/XOVqFhu1RlmtVpGYmOh0cExISBBnz56t9bF2u11s27ZNREZGOh5rNptFx44dmaINbPv27SIoKMixvlu2bCnWr1/v0h9l58+fFxMmTHDaXoYNGybKysr8UDkpqbZ0nZOTIxYvXizKy8s9Gj89PV189dVXcpSqWWzUGvX22287DogWi0V88803br/ceOvWLTFu3LgamzNTtDGcOHHC6ZWUkSNHimvXrrk9zrp165zGSUpK8kG1pEZVpevDhw+L5cuXez12YWGh+PLLL70vUqPYqDUoKytLBAQECAAiKChIbN++3eOxbDabmDhxIlO0gVmtVhETE+NY56NHjxYVFRUej7dnzx4RHBzsGG/nzp0yVktq9nC6bty4sZg1a5ZsY+/evVtkZGTINp6WsFFrjM1mE507d3YcBOfNm1flcnPmzHFquBaLRXTo0EHMmTOn0nuHZWVlomvXrkzRBvXZZ5851nuHDh2qPIHHne1JCCE+/fRTx7KRkZEev+xJ2lRSUiKGDx9e7clg7m5Pkvnz54ubN2/6qmzVCqzqTHBSr507d+LHH38EAERHR+PNN9+sdlmLxYK9e/cCAO7fv4+srCzMmTMHN2/exKJFi5yW++tf/4ro6GjY7XZYLBYUFBSgQ4cOvp0MKc5ut2Px4sWO35cvX46QkJAql3V1ewKApKQkrFmzBnv37sXZs2exadMmfubWQK5evYopU6ZUuy0B7m1PkqlTpyI1NRVJSUk+qVu1lP5LgdwzYsQIx1+hGzZsqHa5OXPmiDp16lS6feLEiaJ169ZVPmbkyJGOsdeuXStbzaRe33//vWOdDxw4sNrlPNmedu7c6fQxQDKOjz/+WFit1mrv92R7cnVsPeJVKjSkoqIC6enpAICWLVti+PDhbo9Rv359VFRUVHnf1KlTHT9v3brVsyJJU7Zs2eL4+eH176qatqcBAwagffv2AIC9e/fi9u3bnhVJmiKEQGBgIMxms9uPrWl7ksTHx9d4pUQ9YqPWkKKiIpSVlQEA+vXrh8DA2t+5sFqtsFqtKC0tRUZGBlJTU5GYmFjlss8884zjCmP5+fnyFU6q9fB67t+/f63Lu7M9BQQEOMYUQqCwsFCeoknV/vGPf7j8tpk725Oka9euKCoqkqNUzWCj1pBjx445fu7Zs2ety5eVlSEoKAhBQUEIDQ3FoEGDEBsbi/nz51e5fEhICDp37gzgwR8Ftf1lS9p39OhRAEDbtm3RuHHjGpd1d3sCnLdT6blI344cOYLu3bvXupwn2xMABAYGwmazyVWuJrBRa8iNGzccP0dERNS6vMViQW5uLnJzc5GVlYWlS5eioKAAo0ePhqjmEu/SuDabDXfv3pWncFIlu92OO3fuAPD99gQAN2/elKdwUrVr1665dO1vT7YnidGuA86zvjXE3Y3TZDIhOjra8XtsbCzCwsKQmJiIHTt2YOjQobI+H+kbtydyhclkqrXRSst5uj0ZbVtiotaQRo0aOX7+6aefPBqjS5cuAJxfRn+YNK7FYqnxoxWkfQEBAWjYsCEA329PgPP2S/rVrFkzXLx40aPH1rY9Sex2u0fjaxUbtYY8/L6Ppyd7HT9+HACqfGnq9u3bOHXqFIAHJ2y4crIaaZu0TZ0/fx4///yz24+vaXsCnLdTV963JO3r0aMHjhw54tFja9ueAKC8vBxBQUEeja9VPBJryBNPPIF69eqhtLQUmZmZKCsrQ506dapdXgiBnJwcAA8+2lVUVITk5GS0aNECCQkJlZbfuXOn4yUrV05WI+2Ljo7Gnj17AADp6el4+eWXq13W3e3JarUiIyMDAGA2m9G1a1f5J0Cq06ZNG2zYsKHW5dzdniT5+fmIioqSrV4tYKLWELPZjBEjRgB4cOWftWvX1rh8eXk5YmNjERsbi/79+2PevHkYMmQIcnJyEB4eXmn5zz//3PFzTTsK6cfD6/nh9V8Vd7enrVu34ty5cwCAoUOHom7duvIWT6pkMpkQEBCA8vLyGpdzd3uSZGVloXfv3nKXrWom4cq7/qQaBw4cQN++fQEAHTt2REFBAYKDg70ed8+ePY7PvD722GM4deqU4zPVpF9CCHTv3t3x0aktW7bgueee83rciooK9O7dGwUFBQCAbdu21XqyGenHmTNncOjQIYwdO1bWca9cuYJNmzZh8uTJso6rdjwSa0yfPn0QExMDADh58iTmzJnj9ZilpaX47W9/6/j9P//zP9mkDcJkMmHGjBmO31977TVcv37d63HnzZvnaNJdunTB4MGDvR6TtKNt27a4ePGiLNvSw7766iu89NJLso6pCYpcuJS88sMPPwiLxeK4jvKKFSs8Huv+/fti2LBhjrHi4uL4jVkGY7fbxZAhQ5yuy13dtx65Ys2aNY6vYTWbzeLw4cMyVktacffuXTF37lxht9tlGW/Dhg2G3ZYYmzSoS5cumDt3ruP3iRMnYt68eW5frefChQsYNmwYtm3bBuDBdXaXL1/ONG0wJpMJS5cudXx8as+ePRg0aBDOnj3r1jh2ux1LlizBuHHjHB+fee+999CrVy/Zayb1q1u3LhITE/HnP//Zpc9V12Tv3r0oLy837rak9F8K5Bm73S5+97vfOX2na2xsrDh06FCtj71375746quvRFhYmOOxISEhYs+ePX6onNTq0KFDon79+o5ton79+mLJkiUupeuCggIRHx/vtD1OmjSJr86QOHnypJg7d664deuW24+12+0iLS1NrFmzxgeVaQdPJtMwIQRmz57tlK6BBx+5SUxMRM+ePfHEE0/AYrHgxo0bKCwsRFZWFtLS0nDlyhXH8mFhYdiyZQv69Onj7ymQyuTn52PIkCGVto8JEyagT58+6N69Oxo1aoSKigqcOnUK+fn5WL9+PbKzs53GeeONN7Bw4UK+OkMAgDt37uCzzz5Dq1at8OKLL7q0XRw7dgzffPMNJk+ejI4dO/qhSvVio9a4wsJCry8k8eSTT+LYsWOGuywfVSaEQJ8+fSo1Xlc1a9YM3377LQYOHChzZaR1S5cuxbRp0/DOO++gefPmiIqKQlRUFOrVqwfgwfcL/P3vf0deXh5KSkqwYsUKREZGOt6aMzI2ao174YUXXLq4QG02btyIkSNHylARadnu3bs9arJPPvkk7t69i/DwcOTm5vKPPnJSXl6Oxx9/HDExMVi1ahXKysrwww8/oKCgAOfOncPatWvxwgsv4JlnnkGPHj3QqFEjrFq1CuPHj8ehQ4fw9NNPKz0FRbFRa1h1aXrZsmUICAhAfn4+ioqKkJmZiUGDBuFXv/oVevbsibS0NKxevdrpMVFRUThy5AgPsAYmhEC/fv2wf/9+p9uHDx+OpKQk5OXlYe7cuU5ffxoSEoLs7Gw89dRT2LVrFwYNGsTPTFMlS5cuxeuvv47jx487ructOXLkCHr27In8/Hz06NHDcbvNZsNTTz2Fdu3aYevWrf4uWV0Uem+cZJCQkOB08g4A0bdvX6ePQ+Tn5wsAIj8/33FbcXGxMJvNlR67ceNGJaZBKrFr165K2wQAUVhY6FgmPDzc6b7w8HDHfXa7XfTp00c8/fTTsn0kh7SvrKxMREZGirFjx1Z5f1XHKMnKlSsFAJdOktUznumhUYWFhVW+5J2cnFxrKm7fvn2VFw1ITk72+mMUpE1CCCQnJ1e6/YUXXkC3bt1cGsNkMiE5ORmHDx/Gjh07ZK6QtGrFihX46aefMGvWLLcfm5iYiE6dOuEPf/iDDyrTDjZqjXr//fcr3da3b1/HZUBrM3PmTJjNZqfbCgsLsXnzZlnqI23JzMys9JI3AMyePdutcQYOHIg+ffrwjz4C8OC96T/+8Y8YM2ZMpZe8XWE2mzF79mxs27YNhw8f9kGF2sBGrUHepGkJUzVJ5EjTEqZqepg3aVrCVM1GrUnepmkJUzUB8qVpCVM1Ad6naQlTNRu15siRpiVM1SRnmpYwVRMgT5qWGD1Vs1FrjFxpWsJUbWxyp2kJU7WxyZWmJUZP1WzUGiJnmpYwVRuXL9K0hKna2ORM0xIjp2o2ag2RO01LmKqNyVdpWsJUbUxyp2mJkVM1G7VG+CJNS5iqjceXaVrCVG1MvkjTEqOmajZqjfBVmpYwVRuLr9O0hKnaWHyVpiVGTdVs1BrgyzQtYao2Dn+kaQlTtbH4Mk1LjJiq2ag1wNdpWsJUbQz+StMSpmpj8HWalhgxVbNRq5w/0rSEqVr//JmmJUzVxuCPNC0xWqpmo1Y5f6VpCVO1vvk7TUuYqvXNX2laYrRUzUatYv5M0xKmav1SIk1LmKr1zZ9pWmKkVM1GrWL+TtMSpmp9UipNS5iq9cnfaVpipFTNRq1SSqRpCVO1/iiZpiVM1fqkRJqWGCVVs1GrlFJpWsJUrS9Kp2kJU7W+KJWmJUZJ1WzUKqRkmpYwVeuHGtK0hKlaX5RM0xIjpGo2ahVSOk1LmKr1QS1pWsJUrQ9Kp2mJEVI1G7XKqCFNS5iqtU9NaVrCVK0PakjTEr2najZqlVFLmpYwVWub2tK0hKla29SSpiV6T9Vs1CqipjQtYarWLjWmaQlTtbapKU1L9Jyq2ahVRG1pWsJUrU1qTdMSpmptUlualug5VbNRq4Qa07SEqVp71JymJUzV2qTGNC3Ra6pmo1YJtaZpCVO1tqg9TUuYqrVFrWlaotdUzUatAmpO0xKmau3QQpqWMFVri5rTtESPqZqNWgXUnqYlTNXaoJU0LWGq1ga1p2mJHlM1G7XCtJCmJUzV6qelNC1hqtYGLaRpid5SNRu1wrSSpiVM1eqmtTQtYapWN62kaYneUjUbtYK0lKYlTNXqpcU0LWGqVjctpWmJnlI1G7WCtJamJUzV6qTVNC1hqlYnraVpiZ5SNRu1QrSYpiVM1eqj5TQtYapWJy2maYleUjUbtUK0mqYlTNXqovU0LWGqVhetpmmJXlI1G7UCtJymJUzV6qGHNC1hqlYXLadpiR5SNRu1ArSepiVM1eqglzQtYapWB62naYkeUjUbtZ/pIU1LmKqVp6c0LWGqVgc9pGmJ1lM1G7Wf6SVNS5iqlaW3NC1hqlaWXtK0ROupmo3aj/SUpiVM1crRY5qWMFUrS09pWqLlVM1G7Ud6S9MSpmpl6DVNS5iqlaG3NC3Rcqpmo/YTPaZpCVO1/+k5TUuYqpWhxzQt0WqqZqP2E72maQlTtX/pPU1LmKr9S69pWqLVVM1G7Qd6TtMSpmr/MUKaljBV+5ee07REi6majdoP9J6mJUzV/mGUNC1hqvYPvadpiRZTNRu1jxkhTUuYqn3PSGlawlTtH0ZI0xKtpWo2ah8zSpqWMFX7ltHStISp2reMkqYlWkvVbNQ+ZKQ0LWGq9h0jpmkJU7VvGSlNS7SUqtmofchoaVrCVO0bRk3TEqZq3zBampZoKVWzUfuIEdO0hKlafkZO0xKmat8wYpqWaCVVs1H7iFHTtISpWl5GT9MSpmp5GTVNS7SSqtmofcDIaVrCVC0fpul/Y6qWl5HTtEQLqZqN2geMnqYlTNXyYJp2xlQtD6OnaYkWUjUbtcyYpv+Nqdp7TNOVMVXLg2n639SeqtmoZcY07Yyp2jtM01VjqvYO07QztadqNmoZMU1XxlTtOabp6jFVe4dpujI1p2o2ahkxTVeNqdozTNM1Y6r2DNN01dScqtmoZcI0XT2mavcxTdeOqdozTNPVU2uqZqOWCdN0zZiq3cM07RqmavcwTddMramajVoGTNO1Y6p2HdO065iq3cM0XTs1pmo2ahkwTbuGqdo1TNPuYap2DdO0a9SYqtmovcQ07Tqm6toxTbuPqdo1TNOuU1uqZqP2EtO0e5iqa8Y07Rmm6poxTbtHbamajdoLTNPuY6quHtO055iqa8Y07T41pWo2ai8wTXuGqbpqTNPeYaquGtO0Z9SUqtmoPcQ07Tmm6sqYpr3HVF01pmnPqSVVs1F7iGnaO0zVzpim5cFU7Yxp2jtqSdVs1B5gmvYeU/W/MU3Lh6naGdO099SQqtmoPcA0LQ+m6geYpuXFVP0A07Q81JCq2ajdxDQtH6ZqpmlfYKp+gGlaPkqnajZqNzFNy8voqZpp2jeMnqqZpuWldKpmo3YD07T8jJyqmaZ9x+ipmmlafkqm6kC/P6NCoqOjUVJS4tUYV69erXSbxWLByy+/7HRbixYtkJeX59VzVae8vBxHjx51efmTJ08CAIqKigr6pe8AAA64SURBVGCz2Vx+XLdu3WCxWNyuzxW/XBdWq7XSMoWFhWjatCmCg4O9ei5frgtvt6mysjJcuXKl0u0HDhzAI4884nSbr+bh7hxu3LhR6fdf1lodf+8XDRo0QNeuXTFjxgw0btxYlj+mfblfuLtvV6eiogKzZ8/GwIEDcffuXeTm5jrd78s5APo4RlU3hwkTJmDmzJn461//KssrFb169XJpOZPQe2z5f4888gjOnz/vl+dq1aoVzp0755Oxc3NzUVRU5NOXs6TxXd2I3KWXdaGHeehhDoA+9gs9zAHQxzz8NYeJEye6tKxhErUkICAAERERPhn74sWLsNvtPhn7Yb7e0fxFD+sC0Mc89DAHPewXepgDoI95qGkOhmvUERERukhYeqCXdaGHeehhDkR6xZPJiIiIVIyNmoiISMXYqH9B+qiV9K9OnTp4/PHHkZycjLKyMqXLc9szzzwDk8lU5cfK1E4P60IPcwD0Mw8J9wtl6WEOv+TLbcpw71G7wmKxYO/evQCA+/fvIysrC3PmzMHNmzexaNEihatz3dmzZ3HgwAEAQFpaGhISEhSuyH16WBd6mAOgn3lwv1AHPcxB4uttio26CiaTCTExMY7f4+PjUVxcjHXr1mlqA0pLS4MQAoMHD8aWLVtw8+ZNNGzYUOmy3KKHdaGHOQD6mQf3C3XQwxwkvt6m+NK3i+rXr4+Kigqly3BLWloaevfujdmzZ6OsrAxr165VuiRZaHFd/JIe5gBocx7cL9RLq3Pw9TbFRl0Nq9UKq9WK0tJSZGRkIDU1FYmJiUqX5bKCggL8+OOPmDBhAn71q1+hXbt2SEtLU7osj2h9XQD6mAOg/Xlwv1AXPczBH9sUX/quQllZGYKCgpxuGzZsGObPn69QRe5LTU1FYGAgxo4dCwAYP3485s2bh/Pnz6NVq1YKV+c6PawLPcwB0Mc8uF+ohx7mAPhnm2KiroLFYkFubi5yc3ORlZWFpUuXoqCgAKNHj9bEF0XY7XasWrUKgwYNQrNmzQA8uEat3W7Ht99+q3B17tH6ugD0MQdA+/PgfqEuepiDv7YpJuoqmEwmREdHO36PjY1FWFgYEhMTsWPHDgwdOlTB6mq3e/duXLhwAbNmzXJ8iULLli3RuXNnpKWl4a233lK4QtdpfV0A+pgDoP15cL9QFz3MwV/bFBO1i6SLsx87dkzhSmqXmpoKAEhKSkJ4eLjj348//oijR4+iqKhI4Qq9o6V1UR09zAHQ1jy4X6if1ubgr22KidpFx48fBwA0bdpU4Upqdu/ePaxfvx7PPfccZsyY4XTf3bt3MWLECKSmpuJPf/qTQhV6TyvroiZ6mAOgnXlwv9AGLc3Bn9sUG3UVhBDIyckB8OC7XYuKipCcnIwWLVqo/uIImzdvxu3bt/G73/0O8fHxle5/9tln8e233+LDDz+U5ft5fU3L60KihzkA2p4H9wv10foc/LlNsVFXoby8HLGxsQAAs9mMRx55BEOGDMEf/vAHhIeHK1xdzdLS0tCyZUsMGjSoyvtfeeUVjBs3Dvv378czzzzj5+rcp+V1IdHDHABtz4P7hfpofQ7+3KZMQiun13lJ+qo9X355vT+eIzc3FwB8/sXvvnwOvawLPTyHHuYA6GO/0MMc9PIc/pqDq+PzZDIiIiIVY6MmIiJSMTZqIiIiFWOjJiIiUjE2aiIiIhUz3MezLl68iEceecRnY/uDr6+gVFRU5LhCkC/pYV1Iz6X1eehhDnrYL/QwB+l5fD2+HtaFq2d9G65R2+12nD9/XukyPNatWzefP0eXLl388jxaXxcSPcxD63PQw36hhzkA+piHv+bgKsM06hYtWujiuSwWi08/2+cPelkXepiHHuYA6GO/0MMcAH3MQ21zMMwFT4iIiLSIJ5MRERGpGBs1ERGRirFRExERqRgbNRERkYqxURMREakYG3UVTp8+jalTpyIqKgqBgYHo2LGj0iW5be3atUhISECbNm0QEhKCzp0746OPPkJ5ebnSpbls/fr1iIuLQ5MmTRAcHIzHHnsMM2bMwI0bN5QuzWM2mw09evSAyWTCqlWrlC7HZXv27IHJZKr0b/jw4UqX5rbVq1fj6aefRkhICBo1aoSBAwf69QI53oqPj69yXZhMJsybN0/p8ly2efNmxMTEoEGDBmjWrBmef/55HDt2TOmy3LZjxw706tULwcHBiIiIwJtvvon79+/L+hyG+Ry1O4qKirB161b07t0bdrtdU81NsnDhQkRGRuKjjz5CREQEcnJy8P777+PIkSNYvXq10uW55Nq1a4iPj8dbb72Fhg0b4tixY0hOTkZWVhaysrKULs8jn3/+OS5cuKB0GR773//9X6cLNYSHhytYjfs+/vhjvPvuu5gxYwY++ugjlJaWYv/+/bIfWH0pJSUFt27dcrrtm2++QUpKCoYNG6ZQVe7ZvXs3EhIS8OKLL+L9999HaWkpPvzwQwwYMADHjx9HRESE0iW6JDMzE8899xzGjh2LuXPn4sSJE/jv//5vlJSUIC0tTb4nElSJzWZz/PzKK6+IJ554QsFqPHPp0qVKty1atEgAEGfOnFGgInl8+eWXAoA4efKk0qW4raSkRISFhYnly5cLAGLlypVKl+SyzMxMAUBkZ2crXYrHiouLRVBQkEhJSVG6FNn16tVLPPXUU0qX4bJXX31VtGvXTtjtdsdt//znPwUAsXz5cuUKc1P//v1Ft27dnG6TjrNHjx6V7Xn40ncVAgK0/9/StGnTSrf17NkTADSd6Bo3bgwACAzU3otBb731FgYPHoz4+HilSzGkv/zlL7BYLJg8ebLSpciquLgYubm5eOmll5QuxWUVFRUIDQ2FyWRy3NagQQMAgNDQNbgOHz6MZ5991um2IUOGAAA2bdok2/NovyORy/bu3Quz2YwOHTooXYpbbDYb7t+/j/z8fHzwwQd4/vnn8dhjjyldllv27duH9evXY8GCBUqX4pURI0bAbDajZcuWeOONN3D37l2lS3JZVlYWOnbsiK+//hqRkZEIDAxEt27dsH37dqVL80pqaioCAgLw4osvKl2Ky1599VWcPHkS//M//4Pr16/j3Llz+I//+A9ERkbihRdeULo8l5nNZlgsFqfb6tSpAwD48ccfZXseNmqDKC4uxvz58zFp0iQ0adJE6XLc0rhxY9StWxfR0dGIiIjAypUrlS7JLVarFdOmTcO7776L1q1bK12ORxo2bIi3334by5cvx86dOzFlyhR88cUXGDFihNKluaykpAR///vfMXPmTHzwwQfYtm0b2rRpgxEjRvj8m5J86dtvv0W/fv189u1nvhAXF4dNmzZh5syZaNSoEVq3bo3s7GxkZGSgYcOGSpfnsg4dOuDw4cNOtx06dAjAg3NsZCPbi+g6pdX3qB929epV0alTJ9GxY0dx8+ZNpctxW0FBgTh48KD48ssvRevWrUX//v2F1WpVuiyXLVy4UDz22GPi/v37Qggh/vWvf2nuPeqqSO+17969W+lSXNK+fXsBQGzatMlxW1lZmWjdurX4zW9+o2BlnsvOzhYAxLJly5QuxS3Z2dkiPDxcTJ8+XWRkZIhNmzaJuLg48eijj4qSkhKly3PZsmXLBADxySefiKtXr4qDBw+KNm3aCLPZLIYMGSLb87BR10LrjfrOnTsiJiZGtGrVSpw9e1bpcryWl5cnAIg1a9YoXYpLLl++LEJDQ8XXX38trl+/Lq5fvy6OHj3qOLjeuHFD6RI9VlpaKkwmk5g/f77Spbjk6aefFgDE7du3nW6fMGGC6NGjh0JVeWfatGkiODhYc3+AR0dHi+eff97ptlu3bomwsDDxX//1XwpV5T6bzSZ+//vfi8DAQAFABAUFiQ8++EA0bdpUTJo0Sbbn4UvfOlZeXo5Ro0bh1KlT+P7779GmTRulS/JaVFQUAgICcPr0aaVLccm5c+dw584dvPzyywgPD0d4eLjju24nT56MyMhIhSv0nPj/k34ePiFIzar7/l+73a6pj2dJrFYrvvvuOzz//POOE7G0oqioCFFRUU631a9fH+3bt0dxcbFCVbkvICAAixYtwpUrV3D06FFcunQJr7/+Oi5fvozY2Fj5nke2kUhVbDYbxo8fj+zsbGzbtg2dO3dWuiRZHDx4EHa7HY8++qjSpbikffv2yMzMdPonvcc+a9YsbNmyReEKPffdd99BCKGq7+2tifR+ekZGhuO2srIy7N+/H9HR0UqV5bH09HRcvnxZU2d7S9q2bYv8/Hyn227evIni4mK0a9dOoao817BhQ3Tt2hVhYWFYsmQJwsLCkJiYKNv42vuMix/cvXsX27ZtAwCcPXsWt2/fxtq1awEAvXr10kQKmjZtGtavX4/k5GQIIZCTk+O4r3Pnzpr4C3zw4MEYOHAgunTpgjp16qCgoAALFixA165dMWrUKKXLc0loaGilj2OdOXMGwIP1EBcX5/+iPPCb3/wGjz/+OKKiohAcHIx9+/Zh4cKFGDx4MPr166d0eS4ZMWIEYmNj8dprr+HatWuIiIjAkiVLcPXqVbz99ttKl+e21NRUNG7cGEOHDlW6FLdNnz4d06ZNQ1JSEhISEnDnzh18/PHHKCsrw5QpU5Quz2WHDx9GZmYmunfvjvv372Pz5s1Yvnw50tLSEBYWJt8TyfYiuo5IJ/tU9U8rH8aPjIysdg6ZmZlKl+eSmTNniqeeekqEhoaK0NBQ8eSTT4o5c+Zo7v24X9LiyWQffvihePLJJ0VoaKgICgoSHTp0ELNmzRL37t1TujS3XL16VUycOFGEh4eL4OBg0bdvX01exOX27dsiJCREJCUlKV2KR+x2u1i2bJno3r27CA0NFU2bNhWDBw8WOTk5SpfmloKCAtG7d28RGhoqQkJCRFxcnEhPT5f9eUxCaOjT5URERAbD96iJiIhUjI2aiIhIxdioiYiIVIyNmoiISMXYqImIiFSMjZqIiEjF2KiJiIhUjI2aiIhIxdioiYiIVIyNmoiISMXYqImIiFSMjZqIiEjF2KiJiIhUjI2aiIhIxf4PIf3oqexRTd4AAAAASUVORK5CYII=", "text/plain": [ "Figure(PyObject
)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# need to run notebook twice to get draw_tree and contest defined here\n", "try\n", " draw_tree(contest)\n", "catch\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To audit this election, we consider the subtree that determined the winning value (at the root). By construction, the value at any node can be confirmed by confirming the values at exactly two of its children. Recursively this yields a binary tree that is a subtree of the ternary tabulation tree; this binary tree is shown in bold in the above figure. We see that auditing exactly **four** of the leaves suffices to confirm that the election outcome is correct. Note that (unlike RLAs) a TPT audit only examines ballots that are reported to be votes for the reported winner.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Introduction and Notation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voting is a central feature of democratic countries and many organizations;\n", "running elections is an essential operation.\n", "\n", "There are a dazzling array of voting methods that have been studied and used in practice;\n", "see \n", "__[Wikipedia page on electoral systems](https://en.wikipedia.org/wiki/Electoral_system)__.\n", "\n", "The security of election systems has become an increasing concern.\n", "See for example the recent NASEM report\n", "__[Securing The Vote](https://www.nap.edu/catalog/25120/securing-the-vote-protecting-american-democracy)__, which recommends the use of paper ballots and post-election audits. An election outcome can be audited by manually examining a random sample of the cast paper ballots to provide confidence that the election outcome was correctly tabulated (computed correctly from the cast paper ballots).\n", "\n", "Today, most post-election audits are statistical in character. They are __risk-limiting audits__ that control the chance (risk) that an incorrect outcome would be accepted by the audit. Such audits sample an increasing number of cast paper ballots at random until the risk of accepting an incorrect outcome is determined to be less than a pre-specified risk limit.\n", "See \n", "__[A Gentle Introduction to Risk-Limiting Audits](https://www.stat.berkeley.edu/~stark/Preprints/gentle12.pdf)__ for more detail.\n", "\n", "Risk-limiting audits (RLAs) are a wonderful invention and can be highly recommended. They have the following potential drawbacks, however:\n", "- the number of ballots examined is a random variable that depends on the \"luck of the draw\" when selecting ballots to be examined by hand\n", "- a RLA may need to examine all of the cast paper ballots in the worst case (when there is a near-tie), even if the tabulation is correct,\n", "- risk-limiting audits are known only for some voting methods; for other methods devising an appropriate RLA remains an open research question. (But RLAs are known for the most common voting methods.)\n", "\n", "The current note attempts to answer the question: \n", "> \"Are there any voting methods that are similar to plurality (the most common voting method), but which are more **audit-friendly** (in terms of having a predictable and bounded audit workload)?\"\n", "\n", "We suggest such a voting method, called TPT (the Ternary Plurality Tree method) that behaves very much like plurality voting, but which has much better auditing properties---that is, much more predictable audit workload (at least for two-candidate contests) and\n", "a much smaller worst-case workload.\n", "\n", "This note thus begins a search for new voting methods that are well-behaved from a political science point of view and which support highly efficient audits, even in the worst case. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Notation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We assume an election with a single contest.\n", "We discuss later elections with multiple contests, but TPT does not provide much economy of scale for audits of multiple contests.\n", "\n", "We let $m$ denote the number of candidates (possible outcomes) in the contest. We begin by examining the case of two candidates $(m=2)$. We let $C$ denote the set of $m$ candidates.\n", "\n", "We assume that the contest outcome is always one of the eligible candidates.\n", "\n", "We let $n$ denote the number of cast paper ballots.\n", " \n", "Each cast paper ballot specifies a vote for exactly one of the $m$ candidates.\n", "We do not consider voting by ranking or scoring the candidates.\n", "\n", "We let $x = (x_1, x_2, \\ldots, x_n)$ denote the list of votes cast; each $x_i$ is an element of $C$.\n", "\n", "Later on, we shall also allow a ballot to say \"missing\" to denote a ballot left blank or a ballot with an invalid vote. \n", "Although we may allow $C$ to contain the value \"missing\", the value \"missing\" is special in that it is ineligible to win the contest; it can not win the contest unless **all** cast votes are \"missing\".\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Winner determination rules" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A _winner determination rule_ $f$ (also commonly known as a _social choice function_) takes as input\n", "\n", "- a list $x = (x_1, x_2, \\ldots, x_n)$ of votes; each $x_i$ a vote for exactly one member of the set $C$ of $m$ candidates, \n", "- a randomization seed $r$\n", "\n", "and produces as output a _winner_ (or _contest outcome_) $f(x, r)$ (also denoted $f_r(x)$),\n", "which is also a member of $C$.\n", "\n", "While the inclusion of the randomization seed $r$ may seem unusual, it is in fact typical for winner determination rules to use randomization to break ties and the like. We assume that $f$ is otherwise deterministic; any randomization it uses is based on the seed $r$\n", "(which might, say, be a 20-digit or a 256-bit randomly chosen value).\n", "\n", "The winner determination function should have certain properties:\n", "\n", "- **Unanimity**: For any $a\\in C$ and any $r$ if $x=(a,a,...,a)$ the value $f(x,r)=a$.\n", "\n", "- **Monotonicity**: For any $r$, the function $f$ is __monotone__: \n", " for any $x$ if $f(x,r)=a$ and $x_i\\ne a$, then changing $x_i$ to $a$ will not\n", " change the output of $f$ to any outcome other than $a$.\n", "\n", "- **Neutrality**: All outcomes are treated equally.\n", "\n", "- **Anonymity**: All votes are treated equally.\n", "\n", "- **Sensitivity**: For any fixed $r$ and any $i$, the function $f_r(x)$ should \n", " depend on $x_i$.\n", "\n", "One can interpret the anonymity criterion as saying that \n", "for any $r$, the function $f_r(x)$\n", "is invariant under permutations of the elements of $x$, such permutations\n", "belonging to a transitive permutation group.\n", "(In practice for TPT, this is obtained not by such\n", "an invariance, but by randomizing the order of the elements of $x$ before applying\n", "the TPT outcome rule.)\n", "\n", "Similarly, neutrality may be interpreted as saying that renaming all votes in a consistent way causes the winner to be renamed in the same way." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# TPT winner determination\n", "\n", "This section describes the TPT method of computing a contest winner.\n", "\n", "A key component of the TPT method is computing the plurality winner of\n", "a small group (typically of size 3, but sometimes 2 or 4) of votes. \n", "\n", "This may be easy to do, such as when finding the winner among three votes, each\n", "of which is for one of two candidates.\n", "\n", "In other cases, when there are more than two candidates or when the size of the group is not three, a tie may ensue. We resolve any such ties pseudorandomly, using\n", "a master random seed and a number unique to that particular group. (To ensure\n", "neutrality, the random selection is based on picking one of the relevant votes\n", "randomly, rather than by trying to directly pick one of the relevant outcomes randomly.\n", "Perhaps a small point, but worth noting.)\n", "\n", "In any case, the small group of votes is then represented by (replaced by) its\n", "plurality winner. \n", "\n", "This process of computing a plurality winner for a small group can be iterated\n", "to determine the TPT winner of the entire collection of votes. \n", "\n", "We describe two such methods; they are equivalent when $n$ is a power of three.\n", "\n", "**Method 1 (Grouping by threes)**\n", "\n", "We describe the GBT method for computing a\n", "winner given $n$ votes, where $n>1$. This is not our recommended\n", "method, but has some utility for its intuitive content, and the fact\n", "the GBT is the same as TPT when $n$ is a power of three.\n", "\n", "1. Arrange the $n$ votes into a list. \n", "\n", "2. Permute this list pseudorandomly based on a random seed.\n", "\n", "3. Group the votes by threes: ballots 1,2,3 form the first group of three, ballots 4,5,6 form form the second group of three, and so on. If the number of votes is not a multiple of three, finish the grouping with one differently-sized last group (of size 2 or 4) as necessary so that each vote is in exactly one group.\n", "\n", "4. Replace each group of (usually three) ballots by the plurality winner for the ballots in that group. \n", "This operation reduces the length of the list by a factor of\n", "approximately three.\n", "\n", "5. If the list now has length one, the vote remaining is for the winner, by\n", "definition. Otherwise return to step 3 and continue.\n", "\n", "**Method 2 (Ternary plurality tree)**\n", "\n", "Our second (and recommended) method of computing a TPT winner\n", "is based on a heap-like representation of a ternary tree with an array.\n", "\n", "A ternary tree has a number of nodes, some of which are _internal nodes_ and\n", "some of which are _leaves_. A leaf has no children, while an internal node\n", "has two or three children. A single root node is at the top of the tree. Each\n", "internal node is the root of a ternary subtree. The above figure illustrates a\n", "ternary tree having $n=9$ leaves.\n", "\n", "The number of internal nodes is $\\underline{ni} = (n-1)/(k-1)$, rounded up as necessary, where $k=3$ is the arity of the tree. Adding in the $n$ leaves, the total number of nodes in the tree\n", "is $$\\underline{nt} = \\underline{ni}+n \\ . $$\n", "We underline the variable names $\\underline{ni}$ and $\\underline{nt}$ to emphasize that they are single variable names and not \"$n$ times $i$\" or \"$n$ times $t$\".\n", "\n", "It is then convenient to represent the tree in a heap-like manner\n", "with an array $A[1:\\underline{nt}]$ of size $\\underline{nt}$, where \n", "$A[1]$ is the root, the internal nodes are $A[1:\\underline{ni}]$, and\n", "the leaves are $A[\\underline{ni}+1:\\underline{nt}]$.\n", "The children of internal node $i$ are at positions \n", "$3i-1$, $3i$, $3i+1$ (when these positions are\n", "not more than $\\underline{nt}$).\n", "\n", "This representation is preferred over grouping by threes\n", "bevause it has at most one internal node with two\n", "children; all other internal nodes have three children.\n", "\n", "Producing the tree and computing the TPT winner then works as follows.\n", "\n", "1. Arrange the $n$ votes into a list. \n", "\n", "2. Permute this list pseudorandomly based on a random seed.\n", "\n", "3. Allocate an array $A[1:\\underline{nt}]$ of length $\\underline{nt}=\\underline{ni}+n$ where\n", "$\\underline{ni} = (n-1)/(k-1)$ (rounded up as necessary) and where $k=3$.\n", "\n", "4. Copy the votes into positions $A[\\underline{ni}+1:\\underline{nt}]$ \n", "(the leaves of the tree represented by this array).\n", "\n", "5. For each internal node $A[i]$, where $i=\\underline{ni}, \\underline{ni}-1, ..., 1$ compute the value of \n", "$A[i]$ as the plurality winner of the values at its children. This is a \"bottom-up\"\n", "computation using the tree structure.\n", "\n", "6. The value at the root $A[1]$ is the TPT winner, by definition.\n", "\n", "This completes our description of the TPT winner computation algorithm. Julia code\n", "implementing this method is given below. \n", "\n", "The method generalizes for $k$-ary trees for\n", "others values of $k$, but $k=3$ is our recommended choice, as choosing $k=2$ yeilds a method that is not sensitive to all input votes, and choosing $k>3$ works but has \n", "an auditing procedure that is less efficient.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Handling multiple candidates" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Handling multiple candidates is really no different. The ternary-input function at each internal node still evaluates the 3-input plurality function. However, with more than two candidates, it is possible to have a three-way tie at a node; so a tie-breaking mechanism is needed to break ties. TPT uses a pseudorandom number generator to pick one of the three candidates to be the winner of a three-way tie. Each of the three candidates in a three-way tie has the same probability of being picked." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Handling missing or invalid values" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We now consider elections in which some ballots may not have choices indicated for the contest---we call such values \"missing\", or for which the voter made an \"invalid\" choice.\n", "\n", "Such values can be easily handled by treating them as if they \"just didn't happen\"---they have a count of 0.\n", "\n", "See the `plurality_winners` function in the Julia code below, which sets the count of 'missing' values to 0.\n", "\n", "Invalid values can be treated as \"missing\" values." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Auditing" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We consider _tabulation audits_, which aim to demonstrate that the contest winner was\n", "correctly computed from the collection of cast paper ballots.\n", "\n", "In this note we consider only _ballot comparison audits_, where each paper ballot has a corresponding electronic record. A fundamental operation for the audit consists of manually examining a selected paper ballot to check that the electronic record of that ballot matches the auditor's interpretation of that ballot.\n", "\n", "For a ballot comparison audit to work, one must be able to retrieve a cast paper ballot\n", "together with its corresponding electronic record. This may be managed using a _ballot id_ printed on the ballot and also contained in the electronic record.\n", "\n", "A key audit input is a _ballot manifest_, which lists all $n$ cast paper ballots, giving their ballot ids and the physical location of the cast paper ballot. The ballot manifest lists all and only the ballots used in the tabulation.\n", "\n", "The ballot manifest and the collection of electronic records may be digitally\n", "signed and posted (or otherwise committed to) after the polls close, so that they\n", "may not be changed later without detection.\n", "\n", "The tabulation computation produces a _reported contest outcome_ from the electronic\n", "records.\n", "\n", "The audit proceeds by manually examining selected paper ballots until sufficient\n", "confidence is gained that the reported contest outcome is correct.\n", "\n", "With a statistical risk-limiting audit, ballots are selected at random for manual\n", "examination. The main property of the risk limiting audit is that if the reported \n", "contest outcome is incorrect, then the audit has a guaranteed minimum chance of \n", "escalating to a manual examination of all cast paper ballots (which by definition\n", "gives the correct contest outcome).\n", "\n", "A TPT audit is different in character, and never examines more than a fraction of\n", "the cast paper ballots (assuming that the tabulation is correct), and only examines ballots that are reported to be votes for the reported contest winner.\n", "\n", "The _workload_ of an audit is the number of cast paper ballots that \n", "are manually examined. \n", "\n", "With at statistical audit the workload is a random variable that depends on the \"luck of the draw\".\n", "The unpredictability of the workload is a consideration when planning or using\n", "a statistical audit.\n", "\n", "There is a notion, called _query complexity_ (or _decision-tree complexity_) in the theoretical literature.\n", "This is the worst-case number of ballots that need to be examined to determine\n", "the winner, in the absence of prior information about the ballots contents.\n", "\n", "The _audit complexity_ is the minimum number of ballots whose contents need to be\n", "confirmed, given prior information on the ballots contents. The contents of the\n", "other ballots don't affect the contest outcome.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Auditing a TPT election\n", "\n", "The root node is always marked for auditing.\n", "\n", "If a node is not marked for auditing, then neither are its children.\n", "\n", "Otherwise, if a node is marked for auditing, then either all of its\n", "children are marked for auditing (the default case), or else, if\n", "a majority of the children have a value equal to the value of the parent (the common case), then a minimal such majority of child nodes are audited.\n", "\n", "The latter condition is what allows the audit to audit only two out of three children\n", "nodes in a two-candidate race. \n", "\n", "When there are more than two candidates, or when \"missing\" values are allowed, a TPT\n", "audit of the value at a node may require auditing __all three__ of the values at the \n", "node's children. For example, if the node's children report winners A, B, and C, and\n", "the tie-breaker picks A as the node's winner, then the values at all three children must\n", "be audited, since if any one of them is incorrect the node's winner may be incorrect.\n", "\n", "The TPT rules leaves unspecified __which__ majority set of child nodes are audited; it\n", "doesn't matter for the correctness of the audit.\n", "\n", "We give a table that shows how slowly $a$ grows with $n$, where\n", "$n=3^d$ is the number of paper ballots cast, and $a=2^d$ is the number of paper\n", "ballots manually examined during a TPT audit. This table is for two candidates,\n", "with no errors found during the audit. It is a __worst-case__ figure: this is the __maximum__ number of ballots that must be audited, even if the race is very close.\n", "\n", "Note, for example, that with $n=531,441$ ballots cast, at most $a=4,096$ ballots\n", "need to be examined manually; this is less than 1%.\n", "\n", "$d$ | $n=3^d$ | $a=2^d$ | $a/n$ as % \n", "---|---|----|---\n", "1 | 3 | 2 | $~~~~~~~~$66.666\n", "2 | 9 | 4 | 44.444\n", "3 | 27 | 8 | 29.630\n", "4 | 81 | 16 | 19.753\n", "5 | 243 | 32 | 13.168\n", "6 | 729 | 64 | 8.779\n", "7 | 2187 | 128 | 5.853\n", "8 | 6561 | 256 | 3.901\n", "9 | 19,683 | 512 | 2.601\n", "10 | 59,049 | 1,024 | 1.734\n", "11 | 177,147 | 2,048 | 1.156\n", "12 | 531,441 | 4,096 | 0.771\n", "13 | 1,594,323 | 8,192 | 0.514\n", "14 | 4,782,969 | 16,384 | 0.343\n", "15 | 14,348,907 | 32,768 | 0.228\n", "16 | 43,046,721 | 65,536 | 0.152\n", "17 | 129,140,163 | 131,072 | 0.101\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Effect of interpretation errors\n", "\n", "An audit may uncover discrepancies between a cast paper ballot and its corresponding electronic record. Such discrepancies should cause the audit to \"work harder\" to \n", "nonetheless confirm the reported contest outcome, or else to proceed to determine that the reported contest outcome was incorrect, and that another candidate was in fact the correct contest winner. \"Working harder\" means examining additional cast paper ballots, beyond\n", "those originally selected for examination. (An RLA may proceed through a series of \"rounds\", each one examining additional randomly selected ballots.)\n", "\n", "Whenever a TPT audit discovers a discrepancy, the recovery process is relatively\n", "straightforward:\n", "- Retabulate the contest, using the revised information about the discrepant ballot(s).\n", "- Recompute the audit plan, based on the new ternary plurality tree data.\n", "- Proceed with the audit, continuing by manually examining new ballots as indicated\n", " by the revised audit plan.\n", " \n", "In general, one would expect the revised audit plan (corresponding to the binary\n", "tree embedded within the ternary plurality tree) to be quite similar to the\n", "original audit plan, so that not much additional work would be required in the\n", "revised audit.\n", "\n", "Of course, if the retabulation indicates that the previous reported contest winner was\n", "incorrect, then the new audit plan is \"back to square one\", since the new audit\n", "plan will have all leaves looking at votes for the new winner, instead of all leaves looking at votes for the earlier winner. The new tree will be entirely disjoint from the\n", "original tree. \n", "\n", "The Julia code below provides an example of a TPT audit for a \"mock election\" with 1M voters. The margin of victory is 3%. \n", "\n", "If there are no discrepancies found during the audit between the electronic (reported) records and the manually examined paper ballots, the TPT audit of this mock election requires the examination of 7169 cast paper ballots.\n", "\n", "When there is a 0.1% discrepancies rate between the electronic records and the cast paper ballots, then the TPT audit finds 5 discrepancies, and the total number of ballots audited rises modestly, to 7208.\n", "\n", "Additional experimental and theoretical work is almost certainly required to evaluate and quantify the impact of discrepancies on a TPT audit, but these initial experimental results are very encouraging." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Discussion\n", "\n", "The TPT method may be compared with BatchVote\n", "(http://people.csail.mit.edu/rivest/pubs.html#RSP17),\n", "which also considered the design of voting systems to\n", "achieve efficient auditability while also allowing\n", "more complex voting systems to be used.\n", "\n", "The TPT method is not obviously well suited for the auditing of\n", "multiple contests; each contest must be audited \"on its own\".\n", "Typical risk-limiting audits, by contrast, have the advantage that\n", "when a ballot is retrieved for auditing, __all__ contests on that ballot\n", "may be manually examined, making progress on the audit of __all__ contests.\n", "\n", "An interesting open question is __whether there is a risk-limiting audit for \n", "TPT voting?__. Such an RLA method would be of interest when auditing a TPT\n", "election that is not close.\n", "\n", "It is worthing noting Chaum's \"Random Sample Elections\"\n", "(https://rsvoting.org/), which is interesting but doesn't\n", "quite satisfy our requirements, since once randomization is\n", "used to select the active voters, other voters are excluded.\n", "There is no sensitivity to all votes once the randomization is\n", "fixed.\n", "\n", "A TPT audit has an audit workload of about \n", "$n^{\\ln{2}/\\ln{3}} = n^{0.63092975}$.\n", "We conjecture (based on little evidence) that there may exist winner\n", "determination functions satisfying our criteria with an audit workload\n", "of about $n^{1/2}$.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Comparison with plurality elections; replication\n", "\n", "For a given set of votes in a large election, \n", "the TPT outcome and the plurality outcome are likely to be identical. \n", "\n", "For that reason, it is worth considering this relationship in more detail,\n", "and considering a TPT audit as a potential \"proxy\" for a plurality audit,\n", "even though the outcome rules are somewhat different.\n", "\n", "We can consider each layer of the TPT tree to be a \"concentration\n", "operator\", that increases the fraction of occurrences of the most\n", "common outcome that are passed on to the next higher layer.\n", "\n", "As the size (number of ballots cast) in the election increases, the\n", "probability that the TPT outcome and the plurality outcome agree\n", "increases dramatically.\n", "\n", "See the section below on the Michigan 2016 Presidential election, for\n", "an example based on a close election.\n", "\n", "The straightforward approach to using TPT for the Michigan 2016 US Presidential\n", "election gives a probability 0.7984855 \n", "that the TPT result will be equal to the plurality result. Not bad, but\n", "not terribly close to 1, either.\n", "\n", "However, one can use if desired\n", "a _replication strategy_ to improve the probability that the TPT\n", "outcome is equal to the plurality outcome.\n", "\n", "With a replication strategy each ballot is replicated a number of times\n", "equal to a pre-specified _replication factor_. This increases the number of\n", "effective ballots in the election, and increases the chance that the TPT outcome\n", "will be equal to the plurality outcome.\n", "\n", "With the Michigan example (given in detail below), a replication factor of 81\n", "(that is, $3^4$) increases the chance that the TPT outcome and the plurality outcome\n", "agree to 0.9999761, while increasing the auditing work by a factor of\n", "only 16 (that is, $2^4$). The total number of ballots that need to be manually\n", "examined from the replicated collection of cast ballots is still only a small fraction\n", "of the number of ballots cast.\n", "\n", "Furthermore, an appropriate replication factor can be determined from the reported\n", "percentage of votes cast for each candidate.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# California 2016 US Presidential\n", "\n", "Consider the 2016 US Presidential contest. The\n", "reported results are as follows.\n", "\n", "Candidate | Votes | Percent\n", ":--- | ---: | ---:\n", "Clinton | 8,753,788 | 61.73 %\n", "Trump | 4,483,810 | 31.62 %\n", "Other | 943,997 | 6.65 %\n", "Total | 14,181,595 | 100.00 %\n", "\n", "There were almost exactly $3^{15}$ votes cast.\n", "\n", "Thus, the TPT outcome for this contest could be audited by\n", "examining at most $2^{15} = 32,768$ ballots (assuming no\n", "discrepancies discovered). This is about 0.23% of the ballots cast.\n", "\n", "It is worth emphasizing that the TPT outcome would never\n", "require more than 32,768 ballots to be examined (assuming no\n", "discrepancies were discovered), no matter how small the \"margin\n", "of victory\" (a plurality term of art, not a TPT term of art).\n", "The workload for TPT is essentially a \"worst-case\" bound.\n", "\n", "A simple computation (shown below) also shows that if the\n", "ballots were actually cast in the proportions shown, then the\n", "TPT outcome and the plurality outcome are overwhelmingly likely\n", "to be equal (more than 99.99999 % of the time).\n", "\n", "For such a large margin (30 %), however, an RLA is exceptionally\n", "efficient. The usual rule of thumb says that a ballot-comparison\n", "RLA requires a workload of about $2 \\ln(1/\\alpha) / m$ ballots examined\n", "manually for a risk-limit of $\\alpha$ and a margin of victory of $m$.\n", "Thus, a ballot-comparison RLA might require examining only \n", "$2\\ln(1/0.01)/0.30 = 31$ ballots for a 1% risk limit! \n", "\n", "In the next section we consider the __Michigan__ 2016 US Presidential contest, which\n", "had a very tiny margin.\n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# TPT compared to plurality for Michigan 2016 US Presidential\n", "\n", "We now consider the 2016 __Michigan__ US Presidential election, which had the following (extremely close!) results:\n", "\n", "Candidate | Votes | Percent\n", ":--- | ---: | ---:\n", "Trump | 2,279,543 | 47.50 %\n", "Clinton | 2,268,839 | 47.27 %\n", "Other | 250,902 | 5.23 %\n", "Total | 4,799,284 | 100.00 %\n", "\n", "The total number of votes cast is close to $3^{14}$, so we would expect a\n", "TPT audit to manually examine about $2^{14} = 16,384$ ballots, no matter how\n", "\"close\" the contest is (from a plurality perspective).\n", "\n", "In fact the margin (0.23%) is quite small, so a ballot-comparison \n", "RLA of this plurality election would be expected to manually examine\n", "around $2\\ln(1/0.05)/0.0023 = 4005$ ballots for a 1% risk limit.\n", "\n", "__Can a TPT tabulation and audit be used as a proxy for a plurality\n", "tabulation and audit__? How likely are the TPT outcome and the plurality\n", "outcome to be equal (say, in this Michigan election)? Is there anything\n", "that can be done to make this probability very close to one!\n", "\n", "We develop tools for computing the likelihood that the TPT outcome will be equal to the plurality outcome. (The probability here is taken over the choice of the seed used for the TPT tabulation, which determines the ordering of the ballots and the tie-breaking procedures used when there are more than two candidates.)\n", "\n", "We apply this tool to the Michigan election, which shows that the TPT outcome and the plurality outcome are equal with probability about 0.7984855. Not bad, but not so close\n", "to one, either.\n", "\n", "We then show that using a replication factor of 81 yields a contest where the TPT outcome and the plurality outcome (for the given input distribution over voter choices)\n", "are almost certain to be identical; they are equal 99.997% of the time. A replication factor of 81 (=$3^4$) increases\n", "the audit workload by a factor of $2^4$, from 16,384 to 262,144 ballots examined manually.\n", "\n", "Even with such a replication factor, this is fairly efficient for a close contest --- less than 6% of the ballots need to examined by hand to determine that the TPT election outcome was correctly computed, and the replication factor provides assurance that the outcome is almost certainly the same as the plurality outcome." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# When might a TPT audit be a good proxy for a plurality audit?\n", "\n", "The two previous sections consider TPT audits for large (whole-state) contests.\n", "However, standard RLAs appear to be more efficient for both of these cases (with\n", "the understanding that we are comparing apples and oranges here).\n", "\n", "The primary reason is that these elections are large. For smaller contests the TPT audit might serve as a reasonable proxy for a plurality audit, in that the TPT outcome has a high probability of being equal to the plurality outcome, and the TPT audit workload is smaller than the RLA workload.\n", "\n", "In this section we identify some parameter ranges where the TPT audit might be a good proxy for a plurality audit. \n", "\n", "To begin this heuristic analysis, we assume that the RLA audit requires examining\n", "$6/\\mu$ ballots, where $\\mu$ is the margin of victory. The number of ballots cast is\n", "$n=3^d$, and the TPT audit workload is $2^d$. These workloads are equal when $\\mu = 6/2^d$. We assume a two-candidate contest ($m=2$). The probability that a vote is for the reported winner is thus $p=1/2 + \\mu/2 = 1/2+3/2^d$." ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "p (generic function with 1 method)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p(d) = 1/2 + 3/(2^d)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The probability that a node at depth $i-1$ is for the reported winner, given that a node at depth $i$ is for the reported winner, is $p2(p) = p^3 + 3p^2(1-p)$:" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "p2 (generic function with 1 method)" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p2(p) = p^2 * (3-2p)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The probability $pd(p, d)$ that the root of a depth-$d$ tree is equal to the reported winner, given that a leaf is equal to the reported winner with probability $p$ is estimated as follows. (This is an approximation, since it assumes independence of the values of children at nodes.)\n" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Probability pd(p,d) that TPT outcome == plurality outcome.\n", "d = 3 n = 27 p = 0.87500 pd = 0.99991\n", "d = 4 n = 81 p = 0.68750 pd = 0.99253\n", "d = 5 n = 243 p = 0.59375 pd = 0.96282\n", "d = 6 n = 729 p = 0.54688 pd = 0.90894\n", "d = 7 n = 2187 p = 0.52344 pd = 0.84166\n" ] } ], "source": [ "using Formatting\n", "pd(p,d) = d==1 ? p2(p) : pd(p2(p),d-1)\n", "\n", "println(\"Probability pd(p,d) that TPT outcome == plurality outcome.\")\n", "for d in 3:7\n", " println(format(\"d = {:d} n = {:5d}\"*\n", " \" p = {:8.5f} pd = {:8.5f}\", \n", " d, 3^d, p(d), pd(p(d),d)))\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We see that there are indeed a modest range of values of $n$ and $p$ where the TPT outcome\n", "is quite likely to be equal to the plurality outcome (say, greater than 95%) and the\n", "TPT audit is at least as efficient as the RLA. For example, for a two-candidate contest with 243 votes and a vote fraction for the reported winner of at most 0.594, the TPT is estimated to be more efficient (assuming no discrepancies found).\n", "\n", "However, using such an approach in practice would seem to require\n", "having reliable estimates of $p$, which, in an adversarial scenario,\n", "may not be available.\n", "\n", "Further research may shed additional light on the relationship between TPT and plurality." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Acknowledgments\n", "\n", "The author was supported for this research by the \n", "Center for Science of Information STC (CSoI), an NSF \n", "Science and Technology Center, under grant agreement\n", "CCF-0939370.\n", "\n", "Thanks also to Philip Stark for helpful feedback." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Julia code" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\u001b[32m\u001b[1m Resolving\u001b[22m\u001b[39m package versions...\n", "\u001b[32m\u001b[1m Updating\u001b[22m\u001b[39m `~/.julia/environments/v1.1/Project.toml`\n", "\u001b[90m [no changes]\u001b[39m\n", "\u001b[32m\u001b[1m Updating\u001b[22m\u001b[39m `~/.julia/environments/v1.1/Manifest.toml`\n", "\u001b[90m [no changes]\u001b[39m\n", "\u001b[32m\u001b[1m Resolving\u001b[22m\u001b[39m package versions...\n", "\u001b[32m\u001b[1m Updating\u001b[22m\u001b[39m `~/.julia/environments/v1.1/Project.toml`\n", "\u001b[90m [no changes]\u001b[39m\n", "\u001b[32m\u001b[1m Updating\u001b[22m\u001b[39m `~/.julia/environments/v1.1/Manifest.toml`\n", "\u001b[90m [no changes]\u001b[39m\n", "\u001b[32m\u001b[1m Resolving\u001b[22m\u001b[39m package versions...\n", "\u001b[32m\u001b[1m Updating\u001b[22m\u001b[39m `~/.julia/environments/v1.1/Project.toml`\n", "\u001b[90m [no changes]\u001b[39m\n", "\u001b[32m\u001b[1m Updating\u001b[22m\u001b[39m `~/.julia/environments/v1.1/Manifest.toml`\n", "\u001b[90m [no changes]\u001b[39m\n" ] } ], "source": [ "using Pkg\n", "Pkg.add(\"PyPlot\")\n", "Pkg.add(\"StatsBase\")\n", "Pkg.add(\"Formatting\")\n", "using PyPlot\n", "using Formatting\n", "using StatsBase\n", "using SHA" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "make_contest" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#\n", "# TPT Contest object and contained k-ary tree\n", "#\n", "\n", "mutable struct Contest\n", " n::Int # number of cast votes (external nodes; leaves)\n", " ni::Int # number of internal nodes\n", " nt::Int # total number of nodes: internal+external = n+ni\n", " k::Int # use k-ary tree (k=3 is default)\n", " tree # array of tree nodes (length n+ni)\n", " seed::String # used to break ties, permute values\n", "end\n", "\n", "\n", "mutable struct TreeNode\n", " index::Int # index within row (starting with 1)\n", " audit::Bool # true if node is to be part of audit\n", " audited::Bool # true if audited (tval copied to val) \n", " rval::Any # candidate chosen (as reported by scanner)\n", " aval::Any # candidate chosen on paper ballot (actual value)\n", " val::Any # if audited then aval, else rval\n", " x::Real # coordinates of center of node\n", " y::Real\n", "end\n", "\n", "TreeNode() = TreeNode(0,false,false,0,0,0,0,0)\n", "\n", "\n", "\"Compute number of internal nodes in a k-ary tree with n leaves.\"\n", "function n_internal(n, k)\n", " return Int(ceil((n-1)/(k-1)))\n", "end\n", "\n", "\n", "\"Compute index of parent of node i in heap-like k-ary tree with root 1\"\n", "function parent(i, k)\n", " return Int(ceil((i-1)/k))\n", "end \n", "\n", "\n", "\"Compute index of leftmost child of node i in heap-like k-ary \n", "tree with root 1\"\n", "function left_child(i, k)\n", " return (i-1)*k + 2\n", "end\n", "\n", "\n", "\"Compute index of rightmost child of node i in heap-like k-ary \n", "tree with root 1\"\n", "function right_child(i, k)\n", " return i*k + 1\n", "end\n", "\n", "\n", "\"Compute depth of node i in a heap-like k-ary tree with root 1\"\n", "function depth(i, k)\n", " d = 0\n", " while i>1\n", " i = parent(i, k)\n", " d += 1\n", " end\n", " return d\n", "end\n", "\n", "\n", "\"Make tree object for contest based on length-n arrays\n", "rvals of reported voter choices and avals of actual choices;\n", "val of node is set to rval, and audited of node is set false.\"\n", "function make_tree!(contest, tree, rvals, avals)\n", " for i in 1:contest.nt\n", " tree[i] = TreeNode()\n", " tree[i].index = (i==1 || depth(i-1, contest.k) != depth(i, contest.k)) ? 1 :\n", " tree[i-1].index + 1 \n", " tree[i].audit = false\n", " tree[i].audited = false \n", " tree[i].rval = i<=contest.ni ? 0 : rvals[i-contest.ni] \n", " tree[i].aval = i<=contest.ni ? 0 : avals[i-contest.ni]\n", " tree[i].val = tree[i].rval\n", " end\n", "end\n", "\n", "\n", "\"Make contest object for given array of length n of voter choices,\n", "both reported (rvals) and actual (avals).\n", "Repeat each vote a number of times equal to 'replication_factor'.\"\n", "function make_contest(rvals, avals; seed=0, k=3, replication_factor = 1)\n", " rvals = vcat([rvals for i=1:replication_factor]...)\n", " avals = vcat([avals for i=1:replication_factor]...)\n", " my_shuffle!(rvals, seed)\n", " my_shuffle!(avals, seed) # note: same shuffle order!\n", " n = length(rvals)\n", " ni = n_internal(n, k)\n", " nt = n + ni\n", " tree = Array{TreeNode}(undef,nt)\n", " contest = Contest(n, ni, nt, k, tree, string(seed))\n", " make_tree!(contest, tree, rvals, avals)\n", " return contest\n", "end" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "tabulate!" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#\n", "# TPT Tabulation (winner determination)\n", "# \n", "\n", "\"Pseudorandom number generator (PRNG, random oracle).\n", "Return nonnegative pseudorandom BigInt based on given \n", "arbitrary list of seed(s) and parameters.\"\n", "function PRNG(seeds...)\n", " seeds = [string(seed) for seed in seeds]\n", " seed = join(seeds, \":\")\n", " return parse(BigInt, bytes2hex(sha256(seed)), base=16)\n", "end \n", "\n", "\n", "\"Return pseudorandom element of array L, using given PRNG seed.\"\n", "function pick_random(L, seed)\n", " length(L) == 1 && return L[1]\n", " r = PRNG(\"pick_random\", seed)\n", " return L[mod1(r, length(L))]\n", "end\n", "\n", "\n", "\"Shuffle array L in place, using given PRNG seed.\n", "Same as Random version, except using our PRNG.\n", "Uses Fisher-Yates (Knuth) algorithm.\"\n", "function my_shuffle!(L, seed)\n", " for i in 1:length(L)\n", " r = mod1(PRNG(seed+i), i)\n", " L[i], L[r] = L[r], L[i] # swap!\n", " end\n", "end\n", "\n", "\n", "\"Return true iff a==b, even if one or both are missing.\"\n", "function my_match(a, b)\n", " if ismissing(a)\n", " return ismissing(b)\n", " elseif ismissing(b)\n", " return false\n", " else\n", " return a==b\n", " end\n", "end\n", "\n", "\n", "\"Return list of all plurality winners of given list of choices.\n", "Note that 'missing' may be present but can't win and won't be\n", "in the returned list if there are other choices voted for. \n", "Winners are returned in order they first occur, to maintain \n", "neutrality of winner function.\"\n", "function plurality_winners(vals)\n", " if length(vals) == 1\n", " return vals\n", " elseif length(vals) == 2\n", " ismissing(vals[1]) && ismissing(vals[2]) && return [missing]\n", " ismissing(vals[1]) && return [vals[2]]\n", " ismissing(vals[2]) && return [vals[1]]\n", " vals[1] != vals[2] && return vals\n", " return [vals[1]]\n", " elseif length(vals) == 3\n", " v1, v2, v3 = vals[1:3]\n", " ismissing(v1) && ismissing(v2) && ismissing(v3) && return [missing]\n", " ismissing(v1) && ismissing(v2) && return [v3]\n", " ismissing(v1) && ismissing(v3) && return [v2]\n", " ismissing(v2) && ismissing(v3) && return [v1]\n", " ismissing(v1) && return [v2, v3]\n", " ismissing(v2) && return [v1, v3]\n", " ismissing(v3) && return [v1, v2]\n", " (v1 == v2 || v1 == v3) && return [v1]\n", " v2 == v3 && return [v2]\n", " return vals\n", " end\n", " # else do general case (which happens only if k>3)\n", " tally = Dict()\n", " uniqs = [] # choices in vals, in order of first occurrence\n", " for c in vals\n", " tally[c] = 1 + get(tally, c, 0)\n", " if tally[c]==1\n", " append!(uniqs, 0) # append c this way in case c == missing\n", " uniqs[end] = c\n", " end\n", " end\n", " tally[missing] = 0 # reset tally[missing] to 0 so it can't win unless it is only one\n", " max_count = maximum(values(tally))\n", " winners = [c for c in uniqs if tally[c]==max_count] \n", " return winners\n", "end\n", " \n", " \n", "\"Return single plurality winner of given list of choices, using seed to break ties.\"\n", "function plurality_winner(vals, seed)\n", " return pick_random(plurality_winners(vals), seed)\n", "end \n", "\n", " \n", "\"Compute winner for node i, from winners of its children\"\n", "function winner(contest, i)\n", " left = left_child(i, contest.k)\n", " right = min(right_child(i, contest.k), contest.nt)\n", " vals = [contest.tree[t].val for t in left:right] \n", " return plurality_winner(vals, contest.seed*string(i))\n", "end \n", "\n", " \n", "\"Compute winner (val) for all internal nodes, bottom-up.\" \n", "function tabulate!(contest)\n", " for i in contest.ni:-1:1\n", " contest.tree[i].val = winner(contest, i)\n", " end\n", "end" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "audit!" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#\n", "# TPT Audit\n", "#\n", "\n", "\"Mark node i's children for audit as appropriate, based on children's values.\n", "Mark only two out of three children, if they form majority.\n", "Else mark all children for audit.\"\n", "function mark_is_children_for_audit!(contest, i)\n", " c1 = left_child(i, contest.k)\n", " ck = min(right_child(i, contest.k), contest.nt)\n", " n_children = ck - c1 + 1 \n", " for j in c1:ck\n", " contest.tree[j].audit = false\n", " end\n", " if contest.tree[i].audit == false\n", " return\n", " end\n", " n_hits = 0\n", " for j in c1:ck\n", " if my_match(contest.tree[j].val, contest.tree[i].val)\n", " n_hits += 1\n", " end\n", " end \n", " if n_hits <= n_children/2 # no majority winner exists, mark all children\n", " for j in c1:ck\n", " contest.tree[j].audit = true\n", " end\n", " else # majority winner exists among children, only mark majority\n", " n_hits = 0\n", " for j in c1:ck\n", " if my_match(contest.tree[j].val, contest.tree[i].val)\n", " n_hits += 1\n", " if n_hits <= Int(ceil((n_children+1)/2))\n", " contest.tree[j].audit = true\n", " end\n", " end\n", " end \n", " end\n", "end\n", " \n", " \n", "\"Mark nodes (leaves and internal nodes) in contest tree that \n", "should be audited.\" \n", "function mark_audit!(contest)\n", " contest.tree[1].audit = true\n", " for i in 1:contest.ni\n", " mark_is_children_for_audit!(contest, i) \n", " end\n", "end\n", " \n", "\n", "\"Return index of leaf to audit next, or 0 if no such leaf exists.\n", "Start checking at position i+1.\"\n", "function next_leaf_to_audit(contest, i)\n", " for j in i+1:contest.nt\n", " if contest.tree[j].audit==true && \n", " contest.tree[j].audited==false\n", " return j\n", " end\n", " end\n", " return 0 \n", "end\n", "\n", " \n", "\"Audit contest, and return number of ballots manually audited and\n", "number of discrepancies found.\n", "(This function could be implemented substantially more efficiently,\n", "if desired.)\"\n", "function audit!(contest)\n", " n_audited = 0\n", " n_discrepancies = 0\n", " i = contest.ni # index of \"last leaf audited\"\n", " while true\n", " n_audited += 1\n", " i = next_leaf_to_audit(contest, i)\n", " if i==0\n", " print(\" Done auditing. $n_audited ballots audited.\") \n", " println(\" $n_discrepancies discrepancies found.\")\n", " return n_audited, n_discrepancies\n", " end\n", " # IRL hand-to-eye audit of ballot i would happen here\n", " # but we just simulate it using aval to give \"actual value\"\n", " contest.tree[i].audited = true\n", " # following code may be inefficient if ballots are replicated\n", " # since IRL a ballot is audited at most once\n", " # contest.tree[i].aval is \"value returned by audit of ballot i\"\n", " if contest.tree[i].val == contest.tree[i].aval\n", " # audit just confirmed previously reported value\n", " continue\n", " end\n", " n_discrepancies += 1\n", " print(\" Audit ballot $(i-contest.ni).\")\n", " println(\" Reported $(contest.tree[i].rval).\" *\n", " \" Actual $(contest.tree[i].aval).\")\n", " contest.tree[i].val = contest.tree[i].aval # new value!\n", " j = parent(i, contest.k)\n", " while j != 0\n", " contest.tree[j].val = winner(contest, j)\n", " j = parent(j, contest.k)\n", " end\n", " mark_audit!(contest) # this could be redone to be more efficient!\n", " i=contest.ni # reset search for next leaf to audit\n", " end\n", "end" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "test audit: 1M votes, 3% margin, no interpretation errors\n", " Reported winner is: A\n", " Done auditing. 7169 ballots audited. 0 discrepancies found.\n", " Audited (correct) winner is: A\n", " 6.742498 seconds (61.05 M allocations: 2.785 GiB, 17.62% gc time)\n", "\n", "test audit: 1M votes, 3% margin, 0.1% interpretation error rate\n", " Reported winner is: A\n", " Audit ballot 3015. Reported A. Actual B.\n", " Audit ballot 534445. Reported A. Actual B.\n", " Audit ballot 553869. Reported A. Actual B.\n", " Audit ballot 858601. Reported A. Actual B.\n", " Audit ballot 888695. Reported A. Actual B.\n", " Done auditing. 7208 ballots audited. 5 discrepancies found.\n", " Audited (correct) winner is: A\n", " 7.714361 seconds (73.48 M allocations: 2.939 GiB, 14.32% gc time)\n" ] } ], "source": [ "#\n", "# Test audit performance on mock contest\n", "#\n", "\n", "\"Return rvals and avals for mock election, given\n", "list of (rvote, avote, count) triples.\"\n", "function make_mock_contest(triples)\n", " rvals = []\n", " avals = []\n", " for (rvote, avote, count) in triples\n", " append!(rvals, [rvote for _ in 1:count])\n", " append!(avals, [avote for _ in 1:count])\n", " end\n", " return rvals, avals\n", "end\n", "\n", "\n", "\"Test out TPT audit on plausible votes with discrepancies\"\n", "function test_audit(triples; seed)\n", " rvals, avals = make_mock_contest(triples)\n", " contest = make_contest(rvals, avals; seed=seed)\n", " tabulate!(contest)\n", " println(\" Reported winner is: \", contest.tree[1].val)\n", " mark_audit!(contest)\n", " audit!(contest)\n", " println(\" Audited (correct) winner is: \", contest.tree[1].val)\n", "end\n", "\n", "println(\"test audit: 1M votes, 3% margin, no interpretation errors\")\n", "triples = [('A', 'A', 515000), \n", " ('B', 'B', 485000)]\n", "@time test_audit(triples, seed=1)\n", "println()\n", "println(\"test audit: 1M votes, 3% margin, 0.1% interpretation error rate\")\n", "triples = [('A', 'A', 514485), \n", " ('A', 'B', 515), \n", " ('B', 'A', 485), \n", " ('B', 'B', 484515)]\n", "@time test_audit(triples, seed=1)" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeoAAAEkCAYAAADgj3L+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3deXSTZb4H8G+aNpRSoGUvCAUFZVEoUKQdihQYZBGBeiiLOAqDKD0w545X9KqXpaOMg4DCXLQuXIZBWwHZGbZKoaxtoS0tYIWhzAx4WCr7VqBtkuf+wX0zxG5Z3uTdvp9zOKdN3jz5PbzLr9/kzRuTEEKAiIiIVClA6QKIiIioemzUREREKsZGTUREpGJs1ERERCrGRk1ERKRibNREREQqxkZNRESkYmzUREREKsZGTUREpGJs1ERERCrGRk1ERKRibNREREQqxkZNRESkYmzUREREKsZGTUREpGJs1ERERCrGRk1ERKRibNREREQqxkZNRESkYmzUREREKsZGTUREpGJs1ERERCrGRk1ERKRibNREREQqxkZNRESkYmzUREREKsZGTUREpGJs1ERERCrGRk1ERKRibNREREQqxkZNRESkYmzUREREKhaodAFEpG4XLlzAvn37kJeXhxMnTqC0tBSBgYGIiIhAjx490KtXL8TGxsJsNitdKpEumYQQQukiiEh9du3ahU8//RSbN2+G3W6vcdl27dph6tSpmDJlCsLDw/1UIZExsFETkZNLly5h2rRpWLt2rduPbd68Ob744guMGjXKB5URGRMbNRE5HDhwAAkJCbhy5YrjtpYtW+KVV15BXFwcunfvjvDwcFRUVKC4uBh5eXlYv3490tPTncZ59dVX8fnnnyMwkO+uEXmLjZqIAAD79u3DkCFDcO/ePQBA48aN8cknn2D8+PEICgqq8bGnT5/Gm2++ic2bNztuS0xMxMqVK/neNZGX2KiJCP/85z8RFRWF27dvAwB+/etfIzU1Fc2bN3d5DCEEvv76a7z22msoLy8HALz55ptYuHChT2omMgo2aiKDs9vtGDBgAPbu3QsAGDZsGNavX486dep4NN727dsxcuRIVFRUwGQyYe/evejbt6+cJRMZCj9HTWRwf/nLXxxNOjIyEqtWrarUpJOTk2EymRz/6tSpg8cffxzJyckoKytzWnbo0KH48MMPATxI2ZMnT4bVavXPZIh0iI2ayMCEEPjkk08cvy9btgz169evclmLxYLs7GxkZ2cjPT0dEydOxB//+Ee88847lZZ94403EBMTAwAoLi7G1q1bfTMBIgNgoyYysH379uHEiRMAgL59+2LgwIHVLmsymRATE4OYmBjEx8fjvffew0svvYR169ZVWtZsNmPWrFmO31NSUuQvnsgg2KiJDGzTpk2On5OSktx+fP369VFRUVHlfYMHD0bbtm0BABkZGSgtLfWoRiKjY6MmMrD8/HzHz4MGDap1eavVCqvVitLSUmRkZCA1NRWJiYlVLms2mx0J3W634+jRo/IUTWQwbNREBlZQUAAAaNOmDZo0aVLjsmVlZQgKCkJQUBBCQ0MxaNAgxMbGYv78+dU+pmfPno6fCwsL5SmayGB42SAig7Lb7Y7PTbdq1arW5S0WCw4ePAgAqKioQFFREWbPno3Ro0fjb3/7G0wmU6XHPDzu9evXZaqcyFjYqInIJSaTCdHR0Y7fY2NjERYWhsTEROzYsQNDhw5VsDoi/eJL30QGFRAQ4Pgo1vnz5z0ao0uXLgCAY8eOVXn/w+PyW7WIPMNGTWRg3bt3BwD89NNPTl/E4arjx48DAJo2bVrl/Q+frBYVFeVBhUTEl76JDKxnz57Yt28fAGDnzp0YP358tcsKIZCTkwPg3+9RJycno0WLFkhISKi0vM1mw65duwA8SO9s1ESeYaImMrCRI0c6fv78889rXLa8vByxsbGIjY1F//79MW/ePAwZMgQ5OTlVvqydnp6OM2fOAHjwJR8hISGy1k5kFPxSDiIDKy4uRlRUFO7evQvgwYVJaro6matsNhvi4uIcCXzjxo1OfxQQkeuYqIkMyG63489//jO6devmaNIAMHnyZMdHtryxaNEiR5N+9NFH8dxzz3k9JpFRsVETGczp06fRr18//P73v8e9e/ec7jt79izGjRtX6Rux3LF9+3a89957jt+vXbuGjRs3ejwekdGxURMZhJSiu3btigMHDlS73LZt2zB8+HD8/PPPbo0vhMCKFSswatQox/W/p06div79+yMxMRFjx47F5cuXvZoDkRGxURMZQE0pWtK9e3cEBwcDePBedZcuXfD1119X+6Ubvxx/5MiRmDhxIsrLywEAY8aMwaeffop169Zh5cqV2LVrF7p06YK1a9fKNzEiIxBEpFs2m00sXrxY1K1bVwCo8l+9evVESkqKsNlsYv/+/aJJkyZO90dERIh33nlHbNmyRZw/f17cu3dP3Lp1S+Tl5Ykvv/xSPPvss5XGfPXVV0VFRYVTLSUlJSIhIUEAEGPGjBGXLl1S6H+FSFt41jeRTp0+fRqTJk2q8WXu/v37Y9myZWjXrp3jtsuXL2PatGlYs2aN28/ZvHlzfPHFFxg1alSV9wshsHr1akyfPh0BAQFISUnB6NGj3X4eIiPhS99EOuPKe9H16tVDSkoKMjIynJo08OAqY9999x127dqFhIQEBATUfpho164d5s+fjxMnTlTbpIEH1wsfN24cioqKEBcXx/euiVzARE2kI56m6JpcuHAB+/fvR15eHhYvXgyr1eq4r27duti5cydiY2NdaugPY7omcg0bNZEO2O12LFmyBO+++261J4vVq1cPCxYswOuvv+52U5U0atTI6esqw8PDce3aNY/Gkvz8889ISkrChg0bHCegVXftcCIj4kvfRBrnyhnd/fv3x/Hjx5GUlORxk/aV5s2b88xwohqoa48lIpd5+160mvC9a6LqsVETaZDWU3R1mK6JKtPG3ktEAPSVoqvDdE3kjI2aSCP0mqKrw3RN9IC292QiAzBCiq4O0zURGzWRqhktRVeH6ZqMTJ97NZHGGTlFV4fpmoyKjZpIZZiia8Z0TUZjrD2cSMWYol3HdE1GwkZNpAJM0Z5huiYj4N5OpCCmaO8xXZPesVETKYQpWl5M16RX3POJ/Iwp2neYrkmP2KiJ/Igp2j+YrklPeBQg8gOmaP9juia9YKMm8jGmaGUxXZPW8YhA5CNM0erBdE1axkZN5ANM0erEdE1axKMDkYyYotWP6Zq0ho2aSCZM0drCdE1awSMFkZeYorWL6Zq0gI2ayAtM0frAdE1qxqMGkQeYovWH6ZrUio2ayE1M0frGdE1qwyMIkYuYoo2D6ZrUhI2ayAVM0cbEdE1qwKMJUQ2YoonpmpTGRk1UDaZoehjTNSmFRxaiX2CKpuowXZMS2KiJHsIUTa5guiZ/4lGGCEzR5D6ma/IXNmoyPKZo8gbTNfkajzhkWEzRJBema/IlNmoyJKZo8gWma/IFHn3IUJiiydeYrklubNRkGEzR5E9M1yQXHolI95iiSSlM1yQHNmrSNVdS9IABA/DDDz8wRZPPMF2TN3hUIl1yJ0Xv3LkTbdu29W+BZDhM1+QpNmrSHaZoUjOma3IXj1CkG0zRpBVM1+QONmrSBaZo0iKma3IFj1akaUzRpHVM11QbNmrSLKZo0hOma6oOj1ykOUzRpFdM11QVNmrSFKZoMgKma3oYj2KkCUzRZDRM1yRhoybVY4omI2O6Jh7RSLWYookeYLo2NjZqUiWmaKLKmK6NiUc3UhWmaKKaMV0bDxs1qQZTNJHrmK6Ng0c6UhxTNJFnmK6NgY2aFMUUTeQ9pmt941GPFMEUTSQvpmv9YqMmv2OKJvIdpmv94RGQ/IYpmsg/mK71hY2a/IIpmsj/mK71gUdD8immaCJlMV1rHxs1+QxTNJF6MF1rF4+MJDumaCJ1YrrWJjZqkhVTNJH6MV1rC4+SJAumaCJtYbrWDjZq8hpTNJF2MV2rH4+Y5DGmaCJ9YLpWNzZq8ghTNJH+MF2rE4+e5BamaCJ9Y7pWHzZqchlTNJFxMF2rB4+kVCumaCJjYrpWB5MQQihdBMmnoqICmZmZOHz4MPLz83H+/HlYrVbUrVsXnTp1Qs+ePREfH49OnTq5NN7p06cxadKkahs08CBFL1u2jA1ap06dOoU9e/YgLy8Py5cvh9VqddwXHByMdevW4de//jUsFouCVZKvCSGwevVqTJ8+HQEBAUhJScHo0aOVLssQ2Kh14sqVK/jss8/w1Vdf4cKFC7Uu37dvX0yfPh2jR4+u8iVqu92OJUuW4N133632Ze569ephwYIFeP311/kyt84IIbBp0yYsWbIEu3fvrnX5Zs2aYcqUKZg+fTpatGjhhwpJKT///DOSkpKwYcMGjBkzBp9++imaNm3q1hglJSU4dOgQzp49C7PZDCEEhBBo0KABoqOj0blzZ5hMJh/NQIMEad53330nmjRpIgBU+S8wMLDa++Lj48U//vEPp/GKi4tFXFxctY8BIAYMGCD+9a9/KTNh8qmffvpJDB48uMbtyWQyVXlfWFiYWLFihbDb7UpPg3zIbreLlStXisaNG4umTZuKNWvWuPSY9PR0sWDBApGWlibOnDlTaTu5fv26+P7778WCBQvEsmXLRGlpqa+moCls1BpWXl4uJk2a5HSgDAgIEKNGjRKpqani5MmTwmazCSGEuHPnjjh48KBYsGCB6NSpk9NjQkJCxMaNG4XNZhOLFy8WdevWrfYgXa9ePZGSkuIYl/QlPT1dNGjQwGmdt2/fXvzpT38S+/btE7du3RJCCGGz2cSpU6fEypUrRWJiYqU/BseMGSPu37+v8GzI10pKSkRCQoJjnV+6dKnK5S5evCg++OADkZ+f7/LYly9fFh999JHYv3+/XOVqFhu1RlmtVpGYmOh0cExISBBnz56t9bF2u11s27ZNREZGOh5rNptFx44dmaINbPv27SIoKMixvlu2bCnWr1/v0h9l58+fFxMmTHDaXoYNGybKysr8UDkpqbZ0nZOTIxYvXizKy8s9Gj89PV189dVXcpSqWWzUGvX22287DogWi0V88803br/ceOvWLTFu3LgamzNTtDGcOHHC6ZWUkSNHimvXrrk9zrp165zGSUpK8kG1pEZVpevDhw+L5cuXez12YWGh+PLLL70vUqPYqDUoKytLBAQECAAiKChIbN++3eOxbDabmDhxIlO0gVmtVhETE+NY56NHjxYVFRUej7dnzx4RHBzsGG/nzp0yVktq9nC6bty4sZg1a5ZsY+/evVtkZGTINp6WsFFrjM1mE507d3YcBOfNm1flcnPmzHFquBaLRXTo0EHMmTOn0nuHZWVlomvXrkzRBvXZZ5851nuHDh2qPIHHne1JCCE+/fRTx7KRkZEev+xJ2lRSUiKGDx9e7clg7m5Pkvnz54ubN2/6qmzVCqzqTHBSr507d+LHH38EAERHR+PNN9+sdlmLxYK9e/cCAO7fv4+srCzMmTMHN2/exKJFi5yW++tf/4ro6GjY7XZYLBYUFBSgQ4cOvp0MKc5ut2Px4sWO35cvX46QkJAql3V1ewKApKQkrFmzBnv37sXZs2exadMmfubWQK5evYopU6ZUuy0B7m1PkqlTpyI1NRVJSUk+qVu1lP5LgdwzYsQIx1+hGzZsqHa5OXPmiDp16lS6feLEiaJ169ZVPmbkyJGOsdeuXStbzaRe33//vWOdDxw4sNrlPNmedu7c6fQxQDKOjz/+WFit1mrv92R7cnVsPeJVKjSkoqIC6enpAICWLVti+PDhbo9Rv359VFRUVHnf1KlTHT9v3brVsyJJU7Zs2eL4+eH176qatqcBAwagffv2AIC9e/fi9u3bnhVJmiKEQGBgIMxms9uPrWl7ksTHx9d4pUQ9YqPWkKKiIpSVlQEA+vXrh8DA2t+5sFqtsFqtKC0tRUZGBlJTU5GYmFjlss8884zjCmP5+fnyFU6q9fB67t+/f63Lu7M9BQQEOMYUQqCwsFCeoknV/vGPf7j8tpk725Oka9euKCoqkqNUzWCj1pBjx445fu7Zs2ety5eVlSEoKAhBQUEIDQ3FoEGDEBsbi/nz51e5fEhICDp37gzgwR8Ftf1lS9p39OhRAEDbtm3RuHHjGpd1d3sCnLdT6blI344cOYLu3bvXupwn2xMABAYGwmazyVWuJrBRa8iNGzccP0dERNS6vMViQW5uLnJzc5GVlYWlS5eioKAAo0ePhqjmEu/SuDabDXfv3pWncFIlu92OO3fuAPD99gQAN2/elKdwUrVr1665dO1vT7YnidGuA86zvjXE3Y3TZDIhOjra8XtsbCzCwsKQmJiIHTt2YOjQobI+H+kbtydyhclkqrXRSst5uj0ZbVtiotaQRo0aOX7+6aefPBqjS5cuAJxfRn+YNK7FYqnxoxWkfQEBAWjYsCEA329PgPP2S/rVrFkzXLx40aPH1rY9Sex2u0fjaxUbtYY8/L6Ppyd7HT9+HACqfGnq9u3bOHXqFIAHJ2y4crIaaZu0TZ0/fx4///yz24+vaXsCnLdTV963JO3r0aMHjhw54tFja9ueAKC8vBxBQUEeja9VPBJryBNPPIF69eqhtLQUmZmZKCsrQ506dapdXgiBnJwcAA8+2lVUVITk5GS0aNECCQkJlZbfuXOn4yUrV05WI+2Ljo7Gnj17AADp6el4+eWXq13W3e3JarUiIyMDAGA2m9G1a1f5J0Cq06ZNG2zYsKHW5dzdniT5+fmIioqSrV4tYKLWELPZjBEjRgB4cOWftWvX1rh8eXk5YmNjERsbi/79+2PevHkYMmQIcnJyEB4eXmn5zz//3PFzTTsK6cfD6/nh9V8Vd7enrVu34ty5cwCAoUOHom7duvIWT6pkMpkQEBCA8vLyGpdzd3uSZGVloXfv3nKXrWom4cq7/qQaBw4cQN++fQEAHTt2REFBAYKDg70ed8+ePY7PvD722GM4deqU4zPVpF9CCHTv3t3x0aktW7bgueee83rciooK9O7dGwUFBQCAbdu21XqyGenHmTNncOjQIYwdO1bWca9cuYJNmzZh8uTJso6rdjwSa0yfPn0QExMDADh58iTmzJnj9ZilpaX47W9/6/j9P//zP9mkDcJkMmHGjBmO31977TVcv37d63HnzZvnaNJdunTB4MGDvR6TtKNt27a4ePGiLNvSw7766iu89NJLso6pCYpcuJS88sMPPwiLxeK4jvKKFSs8Huv+/fti2LBhjrHi4uL4jVkGY7fbxZAhQ5yuy13dtx65Ys2aNY6vYTWbzeLw4cMyVktacffuXTF37lxht9tlGW/Dhg2G3ZYYmzSoS5cumDt3ruP3iRMnYt68eW5frefChQsYNmwYtm3bBuDBdXaXL1/ONG0wJpMJS5cudXx8as+ePRg0aBDOnj3r1jh2ux1LlizBuHHjHB+fee+999CrVy/Zayb1q1u3LhITE/HnP//Zpc9V12Tv3r0oLy837rak9F8K5Bm73S5+97vfOX2na2xsrDh06FCtj71375746quvRFhYmOOxISEhYs+ePX6onNTq0KFDon79+o5ton79+mLJkiUupeuCggIRHx/vtD1OmjSJr86QOHnypJg7d664deuW24+12+0iLS1NrFmzxgeVaQdPJtMwIQRmz57tlK6BBx+5SUxMRM+ePfHEE0/AYrHgxo0bKCwsRFZWFtLS0nDlyhXH8mFhYdiyZQv69Onj7ymQyuTn52PIkCGVto8JEyagT58+6N69Oxo1aoSKigqcOnUK+fn5WL9+PbKzs53GeeONN7Bw4UK+OkMAgDt37uCzzz5Dq1at8OKLL7q0XRw7dgzffPMNJk+ejI4dO/qhSvVio9a4wsJCry8k8eSTT+LYsWOGuywfVSaEQJ8+fSo1Xlc1a9YM3377LQYOHChzZaR1S5cuxbRp0/DOO++gefPmiIqKQlRUFOrVqwfgwfcL/P3vf0deXh5KSkqwYsUKREZGOt6aMzI2ao174YUXXLq4QG02btyIkSNHylARadnu3bs9arJPPvkk7t69i/DwcOTm5vKPPnJSXl6Oxx9/HDExMVi1ahXKysrwww8/oKCgAOfOncPatWvxwgsv4JlnnkGPHj3QqFEjrFq1CuPHj8ehQ4fw9NNPKz0FRbFRa1h1aXrZsmUICAhAfn4+ioqKkJmZiUGDBuFXv/oVevbsibS0NKxevdrpMVFRUThy5AgPsAYmhEC/fv2wf/9+p9uHDx+OpKQk5OXlYe7cuU5ffxoSEoLs7Gw89dRT2LVrFwYNGsTPTFMlS5cuxeuvv47jx487ructOXLkCHr27In8/Hz06NHDcbvNZsNTTz2Fdu3aYevWrf4uWV0Uem+cZJCQkOB08g4A0bdvX6ePQ+Tn5wsAIj8/33FbcXGxMJvNlR67ceNGJaZBKrFr165K2wQAUVhY6FgmPDzc6b7w8HDHfXa7XfTp00c8/fTTsn0kh7SvrKxMREZGirFjx1Z5f1XHKMnKlSsFAJdOktUznumhUYWFhVW+5J2cnFxrKm7fvn2VFw1ITk72+mMUpE1CCCQnJ1e6/YUXXkC3bt1cGsNkMiE5ORmHDx/Gjh07ZK6QtGrFihX46aefMGvWLLcfm5iYiE6dOuEPf/iDDyrTDjZqjXr//fcr3da3b1/HZUBrM3PmTJjNZqfbCgsLsXnzZlnqI23JzMys9JI3AMyePdutcQYOHIg+ffrwjz4C8OC96T/+8Y8YM2ZMpZe8XWE2mzF79mxs27YNhw8f9kGF2sBGrUHepGkJUzVJ5EjTEqZqepg3aVrCVM1GrUnepmkJUzUB8qVpCVM1Ad6naQlTNRu15siRpiVM1SRnmpYwVRMgT5qWGD1Vs1FrjFxpWsJUbWxyp2kJU7WxyZWmJUZP1WzUGiJnmpYwVRuXL9K0hKna2ORM0xIjp2o2ag2RO01LmKqNyVdpWsJUbUxyp2mJkVM1G7VG+CJNS5iqjceXaVrCVG1MvkjTEqOmajZqjfBVmpYwVRuLr9O0hKnaWHyVpiVGTdVs1BrgyzQtYao2Dn+kaQlTtbH4Mk1LjJiq2ag1wNdpWsJUbQz+StMSpmpj8HWalhgxVbNRq5w/0rSEqVr//JmmJUzVxuCPNC0xWqpmo1Y5f6VpCVO1vvk7TUuYqvXNX2laYrRUzUatYv5M0xKmav1SIk1LmKr1zZ9pWmKkVM1GrWL+TtMSpmp9UipNS5iq9cnfaVpipFTNRq1SSqRpCVO1/iiZpiVM1fqkRJqWGCVVs1GrlFJpWsJUrS9Kp2kJU7W+KJWmJUZJ1WzUKqRkmpYwVeuHGtK0hKlaX5RM0xIjpGo2ahVSOk1LmKr1QS1pWsJUrQ9Kp2mJEVI1G7XKqCFNS5iqtU9NaVrCVK0PakjTEr2najZqlVFLmpYwVWub2tK0hKla29SSpiV6T9Vs1CqipjQtYarWLjWmaQlTtbapKU1L9Jyq2ahVRG1pWsJUrU1qTdMSpmptUlualug5VbNRq4Qa07SEqVp71JymJUzV2qTGNC3Ra6pmo1YJtaZpCVO1tqg9TUuYqrVFrWlaotdUzUatAmpO0xKmau3QQpqWMFVri5rTtESPqZqNWgXUnqYlTNXaoJU0LWGq1ga1p2mJHlM1G7XCtJCmJUzV6qelNC1hqtYGLaRpid5SNRu1wrSSpiVM1eqmtTQtYapWN62kaYneUjUbtYK0lKYlTNXqpcU0LWGqVjctpWmJnlI1G7WCtJamJUzV6qTVNC1hqlYnraVpiZ5SNRu1QrSYpiVM1eqj5TQtYapWJy2maYleUjUbtUK0mqYlTNXqovU0LWGqVhetpmmJXlI1G7UCtJymJUzV6qGHNC1hqlYXLadpiR5SNRu1ArSepiVM1eqglzQtYapWB62naYkeUjUbtZ/pIU1LmKqVp6c0LWGqVgc9pGmJ1lM1G7Wf6SVNS5iqlaW3NC1hqlaWXtK0ROupmo3aj/SUpiVM1crRY5qWMFUrS09pWqLlVM1G7Ud6S9MSpmpl6DVNS5iqlaG3NC3Rcqpmo/YTPaZpCVO1/+k5TUuYqpWhxzQt0WqqZqP2E72maQlTtX/pPU1LmKr9S69pWqLVVM1G7Qd6TtMSpmr/MUKaljBV+5ee07REi6majdoP9J6mJUzV/mGUNC1hqvYPvadpiRZTNRu1jxkhTUuYqn3PSGlawlTtH0ZI0xKtpWo2ah8zSpqWMFX7ltHStISp2reMkqYlWkvVbNQ+ZKQ0LWGq9h0jpmkJU7VvGSlNS7SUqtmofchoaVrCVO0bRk3TEqZq3zBampZoKVWzUfuIEdO0hKlafkZO0xKmat8wYpqWaCVVs1H7iFHTtISpWl5GT9MSpmp5GTVNS7SSqtmofcDIaVrCVC0fpul/Y6qWl5HTtEQLqZqN2geMnqYlTNXyYJp2xlQtD6OnaYkWUjUbtcyYpv+Nqdp7TNOVMVXLg2n639SeqtmoZcY07Yyp2jtM01VjqvYO07QztadqNmoZMU1XxlTtOabp6jFVe4dpujI1p2o2ahkxTVeNqdozTNM1Y6r2DNN01dScqtmoZcI0XT2mavcxTdeOqdozTNPVU2uqZqOWCdN0zZiq3cM07RqmavcwTddMramajVoGTNO1Y6p2HdO065iq3cM0XTs1pmo2ahkwTbuGqdo1TNPuYap2DdO0a9SYqtmovcQ07Tqm6toxTbuPqdo1TNOuU1uqZqP2EtO0e5iqa8Y07Rmm6poxTbtHbamajdoLTNPuY6quHtO055iqa8Y07T41pWo2ai8wTXuGqbpqTNPeYaquGtO0Z9SUqtmoPcQ07Tmm6sqYpr3HVF01pmnPqSVVs1F7iGnaO0zVzpim5cFU7Yxp2jtqSdVs1B5gmvYeU/W/MU3Lh6naGdO099SQqtmoPcA0LQ+m6geYpuXFVP0A07Q81JCq2ajdxDQtH6ZqpmlfYKp+gGlaPkqnajZqNzFNy8voqZpp2jeMnqqZpuWldKpmo3YD07T8jJyqmaZ9x+ipmmlafkqm6kC/P6NCoqOjUVJS4tUYV69erXSbxWLByy+/7HRbixYtkJeX59VzVae8vBxHjx51efmTJ08CAIqKigr6pe8AAA64SURBVGCz2Vx+XLdu3WCxWNyuzxW/XBdWq7XSMoWFhWjatCmCg4O9ei5frgtvt6mysjJcuXKl0u0HDhzAI4884nSbr+bh7hxu3LhR6fdf1lodf+8XDRo0QNeuXTFjxgw0btxYlj+mfblfuLtvV6eiogKzZ8/GwIEDcffuXeTm5jrd78s5APo4RlU3hwkTJmDmzJn461//KssrFb169XJpOZPQe2z5f4888gjOnz/vl+dq1aoVzp0755Oxc3NzUVRU5NOXs6TxXd2I3KWXdaGHeehhDoA+9gs9zAHQxzz8NYeJEye6tKxhErUkICAAERERPhn74sWLsNvtPhn7Yb7e0fxFD+sC0Mc89DAHPewXepgDoI95qGkOhmvUERERukhYeqCXdaGHeehhDkR6xZPJiIiIVIyNmoiISMXYqH9B+qiV9K9OnTp4/PHHkZycjLKyMqXLc9szzzwDk8lU5cfK1E4P60IPcwD0Mw8J9wtl6WEOv+TLbcpw71G7wmKxYO/evQCA+/fvIysrC3PmzMHNmzexaNEihatz3dmzZ3HgwAEAQFpaGhISEhSuyH16WBd6mAOgn3lwv1AHPcxB4uttio26CiaTCTExMY7f4+PjUVxcjHXr1mlqA0pLS4MQAoMHD8aWLVtw8+ZNNGzYUOmy3KKHdaGHOQD6mQf3C3XQwxwkvt6m+NK3i+rXr4+Kigqly3BLWloaevfujdmzZ6OsrAxr165VuiRZaHFd/JIe5gBocx7cL9RLq3Pw9TbFRl0Nq9UKq9WK0tJSZGRkIDU1FYmJiUqX5bKCggL8+OOPmDBhAn71q1+hXbt2SEtLU7osj2h9XQD6mAOg/Xlwv1AXPczBH9sUX/quQllZGYKCgpxuGzZsGObPn69QRe5LTU1FYGAgxo4dCwAYP3485s2bh/Pnz6NVq1YKV+c6PawLPcwB0Mc8uF+ohx7mAPhnm2KiroLFYkFubi5yc3ORlZWFpUuXoqCgAKNHj9bEF0XY7XasWrUKgwYNQrNmzQA8uEat3W7Ht99+q3B17tH6ugD0MQdA+/PgfqEuepiDv7YpJuoqmEwmREdHO36PjY1FWFgYEhMTsWPHDgwdOlTB6mq3e/duXLhwAbNmzXJ8iULLli3RuXNnpKWl4a233lK4QtdpfV0A+pgDoP15cL9QFz3MwV/bFBO1i6SLsx87dkzhSmqXmpoKAEhKSkJ4eLjj348//oijR4+iqKhI4Qq9o6V1UR09zAHQ1jy4X6if1ubgr22KidpFx48fBwA0bdpU4Upqdu/ePaxfvx7PPfccZsyY4XTf3bt3MWLECKSmpuJPf/qTQhV6TyvroiZ6mAOgnXlwv9AGLc3Bn9sUG3UVhBDIyckB8OC7XYuKipCcnIwWLVqo/uIImzdvxu3bt/G73/0O8fHxle5/9tln8e233+LDDz+U5ft5fU3L60KihzkA2p4H9wv10foc/LlNsVFXoby8HLGxsQAAs9mMRx55BEOGDMEf/vAHhIeHK1xdzdLS0tCyZUsMGjSoyvtfeeUVjBs3Dvv378czzzzj5+rcp+V1IdHDHABtz4P7hfpofQ7+3KZMQiun13lJ+qo9X355vT+eIzc3FwB8/sXvvnwOvawLPTyHHuYA6GO/0MMc9PIc/pqDq+PzZDIiIiIVY6MmIiJSMTZqIiIiFWOjJiIiUjE2aiIiIhUz3MezLl68iEceecRnY/uDr6+gVFRU5LhCkC/pYV1Iz6X1eehhDnrYL/QwB+l5fD2+HtaFq2d9G65R2+12nD9/XukyPNatWzefP0eXLl388jxaXxcSPcxD63PQw36hhzkA+piHv+bgKsM06hYtWujiuSwWi08/2+cPelkXepiHHuYA6GO/0MMcAH3MQ21zMMwFT4iIiLSIJ5MRERGpGBs1ERGRirFRExERqRgbNRERkYqxURMREakYG3UVTp8+jalTpyIqKgqBgYHo2LGj0iW5be3atUhISECbNm0QEhKCzp0746OPPkJ5ebnSpbls/fr1iIuLQ5MmTRAcHIzHHnsMM2bMwI0bN5QuzWM2mw09evSAyWTCqlWrlC7HZXv27IHJZKr0b/jw4UqX5rbVq1fj6aefRkhICBo1aoSBAwf69QI53oqPj69yXZhMJsybN0/p8ly2efNmxMTEoEGDBmjWrBmef/55HDt2TOmy3LZjxw706tULwcHBiIiIwJtvvon79+/L+hyG+Ry1O4qKirB161b07t0bdrtdU81NsnDhQkRGRuKjjz5CREQEcnJy8P777+PIkSNYvXq10uW55Nq1a4iPj8dbb72Fhg0b4tixY0hOTkZWVhaysrKULs8jn3/+OS5cuKB0GR773//9X6cLNYSHhytYjfs+/vhjvPvuu5gxYwY++ugjlJaWYv/+/bIfWH0pJSUFt27dcrrtm2++QUpKCoYNG6ZQVe7ZvXs3EhIS8OKLL+L9999HaWkpPvzwQwwYMADHjx9HRESE0iW6JDMzE8899xzGjh2LuXPn4sSJE/jv//5vlJSUIC0tTb4nElSJzWZz/PzKK6+IJ554QsFqPHPp0qVKty1atEgAEGfOnFGgInl8+eWXAoA4efKk0qW4raSkRISFhYnly5cLAGLlypVKl+SyzMxMAUBkZ2crXYrHiouLRVBQkEhJSVG6FNn16tVLPPXUU0qX4bJXX31VtGvXTtjtdsdt//znPwUAsXz5cuUKc1P//v1Ft27dnG6TjrNHjx6V7Xn40ncVAgK0/9/StGnTSrf17NkTADSd6Bo3bgwACAzU3otBb731FgYPHoz4+HilSzGkv/zlL7BYLJg8ebLSpciquLgYubm5eOmll5QuxWUVFRUIDQ2FyWRy3NagQQMAgNDQNbgOHz6MZ5991um2IUOGAAA2bdok2/NovyORy/bu3Quz2YwOHTooXYpbbDYb7t+/j/z8fHzwwQd4/vnn8dhjjyldllv27duH9evXY8GCBUqX4pURI0bAbDajZcuWeOONN3D37l2lS3JZVlYWOnbsiK+//hqRkZEIDAxEt27dsH37dqVL80pqaioCAgLw4osvKl2Ky1599VWcPHkS//M//4Pr16/j3Llz+I//+A9ERkbihRdeULo8l5nNZlgsFqfb6tSpAwD48ccfZXseNmqDKC4uxvz58zFp0iQ0adJE6XLc0rhxY9StWxfR0dGIiIjAypUrlS7JLVarFdOmTcO7776L1q1bK12ORxo2bIi3334by5cvx86dOzFlyhR88cUXGDFihNKluaykpAR///vfMXPmTHzwwQfYtm0b2rRpgxEjRvj8m5J86dtvv0W/fv189u1nvhAXF4dNmzZh5syZaNSoEVq3bo3s7GxkZGSgYcOGSpfnsg4dOuDw4cNOtx06dAjAg3NsZCPbi+g6pdX3qB929epV0alTJ9GxY0dx8+ZNpctxW0FBgTh48KD48ssvRevWrUX//v2F1WpVuiyXLVy4UDz22GPi/v37Qggh/vWvf2nuPeqqSO+17969W+lSXNK+fXsBQGzatMlxW1lZmWjdurX4zW9+o2BlnsvOzhYAxLJly5QuxS3Z2dkiPDxcTJ8+XWRkZIhNmzaJuLg48eijj4qSkhKly3PZsmXLBADxySefiKtXr4qDBw+KNm3aCLPZLIYMGSLb87BR10LrjfrOnTsiJiZGtGrVSpw9e1bpcryWl5cnAIg1a9YoXYpLLl++LEJDQ8XXX38trl+/Lq5fvy6OHj3qOLjeuHFD6RI9VlpaKkwmk5g/f77Spbjk6aefFgDE7du3nW6fMGGC6NGjh0JVeWfatGkiODhYc3+AR0dHi+eff97ptlu3bomwsDDxX//1XwpV5T6bzSZ+//vfi8DAQAFABAUFiQ8++EA0bdpUTJo0Sbbn4UvfOlZeXo5Ro0bh1KlT+P7779GmTRulS/JaVFQUAgICcPr0aaVLccm5c+dw584dvPzyywgPD0d4eLjju24nT56MyMhIhSv0nPj/k34ePiFIzar7/l+73a6pj2dJrFYrvvvuOzz//POOE7G0oqioCFFRUU631a9fH+3bt0dxcbFCVbkvICAAixYtwpUrV3D06FFcunQJr7/+Oi5fvozY2Fj5nke2kUhVbDYbxo8fj+zsbGzbtg2dO3dWuiRZHDx4EHa7HY8++qjSpbikffv2yMzMdPonvcc+a9YsbNmyReEKPffdd99BCKGq7+2tifR+ekZGhuO2srIy7N+/H9HR0UqV5bH09HRcvnxZU2d7S9q2bYv8/Hyn227evIni4mK0a9dOoao817BhQ3Tt2hVhYWFYsmQJwsLCkJiYKNv42vuMix/cvXsX27ZtAwCcPXsWt2/fxtq1awEAvXr10kQKmjZtGtavX4/k5GQIIZCTk+O4r3Pnzpr4C3zw4MEYOHAgunTpgjp16qCgoAALFixA165dMWrUKKXLc0loaGilj2OdOXMGwIP1EBcX5/+iPPCb3/wGjz/+OKKiohAcHIx9+/Zh4cKFGDx4MPr166d0eS4ZMWIEYmNj8dprr+HatWuIiIjAkiVLcPXqVbz99ttKl+e21NRUNG7cGEOHDlW6FLdNnz4d06ZNQ1JSEhISEnDnzh18/PHHKCsrw5QpU5Quz2WHDx9GZmYmunfvjvv372Pz5s1Yvnw50tLSEBYWJt8TyfYiuo5IJ/tU9U8rH8aPjIysdg6ZmZlKl+eSmTNniqeeekqEhoaK0NBQ8eSTT4o5c+Zo7v24X9LiyWQffvihePLJJ0VoaKgICgoSHTp0ELNmzRL37t1TujS3XL16VUycOFGEh4eL4OBg0bdvX01exOX27dsiJCREJCUlKV2KR+x2u1i2bJno3r27CA0NFU2bNhWDBw8WOTk5SpfmloKCAtG7d28RGhoqQkJCRFxcnEhPT5f9eUxCaOjT5URERAbD96iJiIhUjI2aiIhIxdioiYiIVIyNmoiISMXYqImIiFSMjZqIiEjF2KiJiIhUjI2aiIhIxdioiYiIVIyNmoiISMXYqImIiFSMjZqIiEjF2KiJiIhUjI2aiIhIxf4PIf3oqexRTd4AAAAASUVORK5CYII=", "text/plain": [ "Figure(PyObject
)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "#\n", "# Draw TPT tree\n", "#\n", "\n", "\"Draw the TPT tree for a contest using PyPlot\" \n", "function draw_tree(contest)\n", " pygui(false) # draw in notebook instead of separate window\n", " fig, ax = PyPlot.subplots(figsize=(5,4))\n", " ax.axis(\"off\")\n", " PyPlot.tight_layout()\n", " xlim(-5, 10 * contest.k ^ depth(contest.nt, contest.k))\n", " ylim(-5, 20 * depth(contest.nt, contest.k)+10)\n", " ax.set_aspect(\"equal\")\n", " tree = contest.tree\n", " fontsize = 100 / contest.k ^ depth(contest.nt, contest.k)\n", " for i in 1:contest.nt\n", " tree[i].y = (depth(contest.nt, contest.k)-depth(i, contest.k)) * 20\n", " tree[i].x = (tree[i].index-0.5) * 10 * \n", " contest.k^(depth(contest.nt,contest.k)-depth(i, contest.k)) \n", " linewidth = tree[i].audit==1 ? 2 : 0.3\n", " if i>contest.ni\n", " # leaf (square)\n", " rect = matplotlib.patches.Rectangle(\n", " (tree[i].x, tree[i].y),5,5,\n", " linewidth=linewidth,edgecolor=\"k\",facecolor=\"w\")\n", " ax.add_patch(rect)\n", " ax.text(tree[i].x+2.5, tree[i].y+2.5,\n", " string(tree[i].val),\n", " fontsize=fontsize,\n", " horizontalalignment=\"center\",\n", " verticalalignment=\"center\")\n", " ax.text(tree[i].x+2.5, tree[i].y-3,\n", " i-contest.ni,\n", " fontsize=fontsize,\n", " horizontalalignment=\"center\",\n", " verticalalignment=\"center\")\n", " else\n", " # internal node (circle)\n", " circ = matplotlib.patches.Circle(\n", " (tree[i].x+2.5, tree[i].y+2.5),\n", " linewidth=linewidth,\n", " radius = 2.5, facecolor=\"w\", edgecolor=\"k\")\n", " ax.add_patch(circ)\n", " ax.text(tree[i].x+2.5, tree[i].y+2.5,\n", " string(tree[i].val),\n", " fontsize=fontsize,\n", " horizontalalignment=\"center\",\n", " verticalalignment=\"center\")\n", " end\n", " if i>1 \n", " # draw edge from parent\n", " xs = (tree[i].x+2.5, tree[parent(i, contest.k)].x+2.5)\n", " ys = (tree[i].y+2.5, tree[parent(i, contest.k)].y+2.5)\n", " linewidth = tree[i].audit ? 3.5 : 1\n", " # note use of zorder in next line to hide segment ends\n", " ax.plot(xs, ys, marker = \"o\", \n", " color=\"k\", linewidth=linewidth, zorder=0)\n", " end\n", " end\n", "end\n", "\n", " \n", "vals = collect(\"ABABABBBB\") \n", "contest = make_contest(vals, vals, seed=8)\n", "tabulate!(contest)\n", "mark_audit!(contest)\n", "draw_tree(contest)\n", "savefig(\"basic_fig.svg\")" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "California 2016 Presidential Election\n", "Probability of a node at given height having given winner\n", " Height Clinton Trump Other\n", " 0 0.6173000 0.3162000 0.0665000\n", " 1 0.6986824 0.2626787 0.0386389\n", " 2 0.7965204 0.1849333 0.0185462\n", " 3 0.8981017 0.0954153 0.0064830\n", " 4 0.9720774 0.0266860 0.0012366\n", " 5 0.9977687 0.0021626 0.0000687\n", " 6 0.9999854 0.0000143 0.0000003\n", " 7 1.0000000 0.0000000 0.0000000\n", " 8 1.0000000 0.0000000 0.0000000\n", " 9 1.0000000 0.0000000 0.0000000\n", " 10 1.0000000 0.0000000 0.0000000\n", " 11 1.0000000 0.0000000 0.0000000\n", " 12 1.0000000 0.0000000 0.0000000\n", " 13 1.0000000 0.0000000 0.0000000\n", " 14 1.0000000 0.0000000 0.0000000\n", " 15 1.0000000 0.0000000 0.0000000\n", "\n", "Michigan 2016 Presidential Election\n", "Probability of a node at given height having given winner\n", " Height Trump Clinton Other\n", " 0 0.4750000 0.4727000 0.0523000\n", " 1 0.4860173 0.4825768 0.0314059\n", " 2 0.4937634 0.4886077 0.0176289\n", " 3 0.4991518 0.4914207 0.0094276\n", " 4 0.5033527 0.4917573 0.0048900\n", " 5 0.5074498 0.4900579 0.0024923\n", " 6 0.5124135 0.4863284 0.0012582\n", " 7 0.5192434 0.4801247 0.0006318\n", " 8 0.5291659 0.4705178 0.0003162\n", " 9 0.5438568 0.4559855 0.0001578\n", " 10 0.5656947 0.4342270 0.0000783\n", " 11 0.5980134 0.4019481 0.0000385\n", " 12 0.6451555 0.3548260 0.0000185\n", " 13 0.7116248 0.2883667 0.0000085\n", " 14 0.7984855 0.2015111 0.0000035\n", " 15 0.8945430 0.1054558 0.0000011\n", " 16 0.9689823 0.0310175 0.0000002\n", " 17 0.9971734 0.0028266 0.0000000\n", " 18 0.9999761 0.0000239 0.0000000\n", " 19 1.0000000 0.0000000 0.0000000\n", "\n" ] } ], "source": [ "#\n", "# Compute probability that TPT winner is plurality winner\n", "#\n", "\n", "\"Return list of all length-k combinations of elements from 1:m\"\n", "# combinations(4, 3) \n", "# ==> [(1,1,1), (1,1,2), ..., (4,4,4)] (64 elements)\n", "function combinations(m, k)\n", " reverse.(Iterators.product(fill(1:m,k)...))[:]\n", "end\n", "\n", "\n", "\"Compute probability of each outcome through one k-ary plurality node\"\n", "function prob_outcomes(pi, k=3)\n", " # pi = [...] giving input probability of candidates 1...m\n", " # k = arity of node (number of children)\n", " m = length(pi)\n", " comb = combinations(m, k)\n", " po = fill(0.0, m)\n", " for c in comb\n", " pcomb = prod(pi[collect(c)]) # probability of this input combination\n", " winners = plurality_winners(collect(c))\n", " for w in winners\n", " po[w] += pcomb / length(winners)\n", " end\n", " end\n", " return po\n", "end\n", "\n", "\n", "function California()\n", " println(\"California 2016 Presidential Election\")\n", " println(\"Probability of a node at given height having given winner\")\n", " println(\" Height Clinton Trump Other\")\n", " p = [0.6173, 0.3162, 0.0665] # California: Clinton / Trump / Other from 2016\n", " for i in 0:15\n", " printfmt(\" {:6s} {:10.7f} {:10.7f} {:10.7f}\\n\", i, p[1], p[2], p[3])\n", " p = prob_outcomes(p)\n", " end\n", " println()\n", "end\n", "\n", "California()\n", "\n", "\n", "function Michigan()\n", " println(\"Michigan 2016 Presidential Election\")\n", " println(\"Probability of a node at given height having given winner\")\n", " println(\" Height Trump Clinton Other\")\n", " p = [0.4750, 0.4727, 0.0523] # Michigan: Trump / Clinton / Other from 2016\n", " for i in 0:19\n", " printfmt(\" {:6s} {:10.7f} {:10.7f} {:10.7f}\\n\", i, p[1], p[2], p[3])\n", " p = prob_outcomes(p)\n", " end\n", " println()\n", "end\n", "\n", "Michigan()\n" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.1.1", "language": "julia", "name": "julia-1.1" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.1.1" } }, "nbformat": 4, "nbformat_minor": 2 }