pav.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Proportional Approval Voting implementation\n",
    "\n",
    "See also C code at [CleanOptPRVote.c](https://rangevoting.org/CleanOptPRVote.c) for a related problem as discussed by RangeVoting\\.org at:\n",
    "* [Optimal proportional representation Part I:  methods, algorithms, advantages, and inherent flaws](https://rangevoting.org/QualityMulti.html)\n",
    "* [Optimal proportional representation Part II: The two classes and the \"holy grail\"](https://rangevoting.org/NonlinQuality.html)\n",
    "\n",
    "Todo: When it gets slow\n",
    "* use counts of unique cvrs, not all cvrs\n",
    "* use multiple threads\n",
    "* come up with more efficient algorithm, e.g. A*, which is easily distributed\n",
    "* recode in Rust :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import string\n",
    "import pandas as pd\n",
    "import collections\n",
    "import itertools\n",
    "import time\n",
    "\n",
    "import pav"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plurality results in order\n",
      "Anita_Seitz         4921\n",
      "Shannon_Bird        4823\n",
      "Maria_De_Cambra     3921\n",
      "Mark_Clark          3500\n",
      "David_DeMott        3126\n",
      "Debbie_Bergamo      2668\n",
      "Mike_Melvin         2112\n",
      "Jason_Blanckaert    2026\n",
      "Steve_Caulk         2026\n",
      "Nathan_Pearce       1229\n",
      "dtype: int64\n",
      "\n",
      "12684 CVRs, 169 unique selections of candidates\n",
      "Score is 10619.167 for plurality winners ['Anita_Seitz', 'Shannon_Bird', 'Maria_De_Cambra']\n",
      "\n",
      "Proportional Approval Voting results\n",
      "\n",
      "Top 10 scores:\n",
      "('10799.500', ['Anita_Seitz', 'Mark_Clark', 'Shannon_Bird'])\n",
      "('10619.167', ['Anita_Seitz', 'Maria_De_Cambra', 'Shannon_Bird'])\n",
      "('10607.500', ['Anita_Seitz', 'Debbie_Bergamo', 'Shannon_Bird'])\n",
      "('10588.833', ['Anita_Seitz', 'David_DeMott', 'Shannon_Bird'])\n",
      "('10366.333', ['Maria_De_Cambra', 'Mark_Clark', 'Shannon_Bird'])\n",
      "('10349.500', ['Anita_Seitz', 'Mike_Melvin', 'Shannon_Bird'])\n",
      "('10260.667', ['Anita_Seitz', 'Jason_Blanckaert', 'Shannon_Bird'])\n",
      "('10214.000', ['Anita_Seitz', 'Maria_De_Cambra', 'Mark_Clark'])\n",
      "('10078.833', ['David_DeMott', 'Maria_De_Cambra', 'Shannon_Bird'])\n",
      "('9972.833', ['Anita_Seitz', 'Debbie_Bergamo', 'Mark_Clark'])\n",
      "\n",
      "Max score ('10799.500', ['Anita_Seitz', 'Mark_Clark', 'Shannon_Bird'])\n"
     ]
    }
   ],
   "source": [
    "winner, w_cvrs, scores, df = pav.tally_pav(\"Westminster_Adams.csv\", 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<module 'pav' from '/srv/s/approvalvoting/pr_voting_methods/pav.py'>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Use this to test out new code after modifying the pav module\n",
    "import importlib\n",
    "importlib.reload(pav)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Mark_Clark</th>\n",
       "      <th>Mike_Melvin</th>\n",
       "      <th>Maria_De_Cambra</th>\n",
       "      <th>Shannon_Bird</th>\n",
       "      <th>Steve_Caulk</th>\n",
       "      <th>Debbie_Bergamo</th>\n",
       "      <th>Anita_Seitz</th>\n",
       "      <th>Jason_Blanckaert</th>\n",
       "      <th>David_DeMott</th>\n",
       "      <th>Nathan_Pearce</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Mark_Clark  Mike_Melvin  Maria_De_Cambra  Shannon_Bird  Steve_Caulk  \\\n",
       "0           0            0                0             0            0   \n",
       "1           0            0                1             1            1   \n",
       "2           0            0                0             0            0   \n",
       "3           0            0                0             0            1   \n",
       "4           0            0                0             1            0   \n",
       "\n",
       "   Debbie_Bergamo  Anita_Seitz  Jason_Blanckaert  David_DeMott  Nathan_Pearce  \n",
       "0               0            0                 0             0              0  \n",
       "1               0            0                 0             0              0  \n",
       "2               0            0                 0             0              0  \n",
       "3               0            1                 1             0              0  \n",
       "4               1            0                 0             1              0  "
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plurality results in order\n",
      "Tom_Thompson_III        81\n",
      "Jerry_L_Sauer           75\n",
      "Christopher_P_Cary      57\n",
      "Julie_Smith             56\n",
      "Donna_J_Sauer           54\n",
      "Yvonne_M_Gerhardt       47\n",
      "Jennifer_Simanovicki    36\n",
      "Margaret_A_Holeman      23\n",
      "dtype: int64\n",
      "\n",
      "121 CVRs, 50 unique selections of candidates\n",
      "Score is 182.333 for plurality winners ['Tom_Thompson_III', 'Jerry_L_Sauer', 'Christopher_P_Cary', 'Julie_Smith']\n",
      "\n",
      "Proportional Approval Voting results\n",
      "\n",
      "Top 10 scores:\n",
      "('182.333', ['Donna_J_Sauer', 'Jerry_L_Sauer', 'Julie_Smith', 'Tom_Thompson_III'])\n",
      "('182.333', ['Christopher_P_Cary', 'Jerry_L_Sauer', 'Julie_Smith', 'Tom_Thompson_III'])\n",
      "('180.833', ['Jerry_L_Sauer', 'Julie_Smith', 'Tom_Thompson_III', 'Yvonne_M_Gerhardt'])\n",
      "('179.583', ['Christopher_P_Cary', 'Jerry_L_Sauer', 'Tom_Thompson_III', 'Yvonne_M_Gerhardt'])\n",
      "('179.333', ['Christopher_P_Cary', 'Donna_J_Sauer', 'Jerry_L_Sauer', 'Tom_Thompson_III'])\n",
      "('177.583', ['Donna_J_Sauer', 'Jerry_L_Sauer', 'Tom_Thompson_III', 'Yvonne_M_Gerhardt'])\n",
      "('177.500', ['Christopher_P_Cary', 'Donna_J_Sauer', 'Julie_Smith', 'Tom_Thompson_III'])\n",
      "('174.833', ['Jennifer_Simanovicki', 'Jerry_L_Sauer', 'Julie_Smith', 'Tom_Thompson_III'])\n",
      "('174.583', ['Christopher_P_Cary', 'Donna_J_Sauer', 'Tom_Thompson_III', 'Yvonne_M_Gerhardt'])\n",
      "('173.417', ['Donna_J_Sauer', 'Julie_Smith', 'Tom_Thompson_III', 'Yvonne_M_Gerhardt'])\n",
      "\n",
      "Max score ('182.333', ['Donna_J_Sauer', 'Jerry_L_Sauer', 'Julie_Smith', 'Tom_Thompson_III'])\n"
     ]
    }
   ],
   "source": [
    "winner, a_cvrs, scores, df = pav.tally_pav(\"Byers_SD_32J_Adams.csv\", 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Timing results\n",
    "\n",
    "Note that the C code at [CleanOptPRVote.c](https://rangevoting.org/CleanOptPRVote.c) has been timed at 4V·Binomial(C,W) nanoseconds.\n",
    "\n",
    "Based on the result below of 162 seconds for 24 candidates, 12 winners, 121 ballots,\n",
    "this code might be perhaps 2 orders of magnitude slower, with a constant multiplier of 500 nanoseconds rather than 4.\n",
    "\n",
    "Takes about 12 seconds(?) for 20 candidates, 10 winners, 121 ballots\n",
    "\n",
    "Uses nearly 3 GB of memory with 24 and 12\n",
    "\n",
    "24 choose 12 = 2704156"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "def timepav(candidates, winners, cvrs):\n",
    "    \"Time how long it takes to tally a PAV contest using given cvrs with given number of candidates and winners\"\n",
    "\n",
    "    # If you need more than 62 candidates for some unusual reason, see itertools.product or this infinite recipe: https://stackoverflow.com/a/42099359/507544\n",
    "    many_candidates = tuple(string.ascii_uppercase + string.ascii_lowercase + string.digits)\n",
    "    possible_results = itertools.combinations(many_candidates[:candidates], winners)\n",
    "    t1 = time.time()\n",
    "    scores = {}\n",
    "    for result in possible_results:\n",
    "        resultset = frozenset(result)\n",
    "        scores[resultset] = sum(pav.utility(resultset, cvr) for cvr in cvrs)\n",
    "    timings.append(\"{} seconds for {} candidates, {} winners, {} ballots\".format(time.time() - t1, candidates, winners, len(cvrs)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "timings = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "timepav(12, 6, a_cvrs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "timepav(12, 6, w_cvrs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "timepav(14, 7, a_cvrs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "timepav(14, 7, w_cvrs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "timepav(18, 9, w_cvrs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0.06837797164916992 seconds for 12 candidates, 6 winners, 121 ballots',\n",
       " '5.542601108551025 seconds for 12 candidates, 6 winners, 12684 ballots',\n",
       " '0.22739052772521973 seconds for 14 candidates, 7 winners, 121 ballots',\n",
       " '19.80630850791931 seconds for 14 candidates, 7 winners, 12684 ballots',\n",
       " '309.81311416625977 seconds for 18 candidates, 9 winners, 12684 ballots']"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "Prevent overwriting of previous results below",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-59-ad22e8dc8b8e>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"Prevent overwriting of previous results below\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m: Prevent overwriting of previous results below"
     ]
    }
   ],
   "source": [
    "assert False, \"Prevent overwriting of previous results below\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 285,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0.005549907684326172 seconds for 8 candidates, 4 winners, 121 ballots',\n",
       " '0.0004897117614746094 seconds for 8 candidates, 4 winners, 121 ballots',\n",
       " '0.022046566009521484 seconds for 10 candidates, 5 winners, 121 ballots',\n",
       " '0.22809982299804688 seconds for 14 candidates, 7 winners, 121 ballots',\n",
       " '2.5786209106445312 seconds for 18 candidates, 9 winners, 121 ballots',\n",
       " '9.772108793258667 seconds for 20 candidates, 10 winners, 121 ballots',\n",
       " '39.48445129394531 seconds for 22 candidates, 11 winners, 121 ballots',\n",
       " '161.45553970336914 seconds for 24 candidates, 12 winners, 121 ballots',\n",
       " '4.725412607192993 seconds for 24 candidates, 5 winners, 121 ballots',\n",
       " '6.555292844772339 seconds for 30 candidates, 5 winners, 121 ballots']"
      ]
     },
     "execution_count": 285,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# older results\n",
    "timings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Harmonic / Psi voting\n",
    "From [Optimal proportional representation - RangeVoting\\.org](https://rangevoting.org/QualityMulti.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let C=#candidates, V=#voters, W=#winners, 0<W<C<V, and let S_v,c be the real-valued score given by voter v to candidate c on her ballot. Then here is our highly general class of quality measures Q:\n",
    "\n",
    "\n",
    "Q = ∑1≤v≤V F( ∑1≤j≤W [jth greatest S_v,c among winning c] · A_j )\n",
    "\n",
    "\"Harmonic voting.\") If F(x)=x, then PR will be assured by choosing A_j = 1/(j-1+Δ) where Δ is any positive constant.\n",
    "\n",
    "I.e. for delta = 1/2, A_j = 2 * [1, 1/3, 1/5, 1/7, ...]\n",
    "\n",
    "And for delta = 1, A_j = [1, 1/2, 1/3, 1/4, ...]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [],
   "source": [
    "def A(j, delta=0.5):\n",
    "    return 1 / (j - 1 + delta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2.0, 0.6666666666666666, 0.4, 0.2857142857142857]"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[A(j) for j in range(1, 5)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.0, 0.5, 0.3333333333333333, 0.25]"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[A(j, 1.0) for j in range(1, 5)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Older"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "candidates = 12\n",
    "winners = 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "many_candidates = tuple(string.ascii_uppercase + string.ascii_lowercase + string.digits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "possible_results = itertools.combinations(all_candidates + tuple(list(range(candidates - len(all_candidates)))), winners)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "t1 = time.time()\n",
    "scores = {}\n",
    "for result in possible_results:\n",
    "    resultset = frozenset(result)\n",
    "    scores[resultset] = sum(pav.utility(resultset, cvr) for cvr in cvrs)\n",
    "timings.append(\"{} seconds for {} candidates, {} winners, {} ballots\".format(time.time() - t1, candidates, winners, len(cvrs)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1031.4427270889282 seconds for 20 candidates, 10 winners, 121 ballots',\n",
       " '5.157426595687866 seconds for 12 candidates, 6 winners, 12684 ballots']"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timings"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.6"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "63px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}