05-Tables.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "5eea08c9",
   "metadata": {},
   "source": [
    "\n",
    "# Tables 1, 2, and 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b9f2d945",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import partial\n",
    "from multiprocess import Pool, cpu_count, current_process\n",
    "import pandas as pd\n",
    "from tqdm.notebook import tqdm\n",
    "\n",
    "from pref_voting.generate_weighted_majority_graphs import *\n",
    "from pref_voting.voting_methods import *\n",
    "\n",
    "from pref_voting.generate_profiles import *\n",
    "\n",
    "# needed to ensure that random numbers are different in each process (for multiprocessing)\n",
    "from os import register_at_fork\n",
    "register_at_fork(after_in_child=np.random.seed)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "46b30879",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Condorcetian Candidates\n",
    "\n",
    "def is_condorcetian(vm, cand, edata): \n",
    "    \"\"\"\n",
    "    Definition 4.4: Return True if cand is Condorcetian in edata according to vm\n",
    "    \"\"\"\n",
    "    candidates = edata.candidates\n",
    "    \n",
    "    for c in edata.dominates(cand): # cand is majority preferred to c\n",
    "        ws_minus = vm(edata, curr_cands = [_c for _c in candidates if _c != c])\n",
    "        if cand in ws_minus: \n",
    "            return True\n",
    "    return False\n",
    "\n",
    "        \n",
    "def is_weak_condorcetian(vm, cand, edata): \n",
    "    \"\"\"\n",
    "    Definition 4.4: Return True if cand is weak Condorcetian in edata according to vm\n",
    "    \"\"\"\n",
    "    \n",
    "    candidates = edata.candidates\n",
    "    \n",
    "    for c in edata.candidates:\n",
    "        if edata.majority_prefers(cand, c) or edata.is_tied(cand, c):\n",
    "            ws_minus = vm(edata, curr_cands = [_c for _c in candidates if _c != c])\n",
    "            if cand in ws_minus: \n",
    "                return True        \n",
    "    return False\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "a23e3d62",
   "metadata": {},
   "source": [
    "## Table 1\n",
    "\n",
    "Of four-candidate linear profiles in which $BP(\\mathbf{P}) \\neq SC(\\mathbf{P})$, find the percentage in which Beat Path violates strong stability for winners, i.e., there are $a,b\\in X(\\mathbf{P})$ such that $a\\in BP(\\mathbf{P}_{-b})$, $Margin_\\mathbf{P}(a, b) \\geq 0$, and $a\\notin BP(\\mathbf{P})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9e124bca",
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.read_csv(\"./tables-data-FINAL/violations_ssw.csv\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "779b251d",
   "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>vm</th>\n",
       "      <th>comparison_vm</th>\n",
       "      <th>num_cands</th>\n",
       "      <th>num_voters</th>\n",
       "      <th>num_profiles</th>\n",
       "      <th>probmod</th>\n",
       "      <th>perc_diff_ws</th>\n",
       "      <th>perc_ssw_violation</th>\n",
       "      <th>perc_ssw_violation_cond_diff_ws</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(10, 11)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IC</td>\n",
       "      <td>0.005159</td>\n",
       "      <td>0.005148</td>\n",
       "      <td>0.997868</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(20, 21)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IC</td>\n",
       "      <td>0.008280</td>\n",
       "      <td>0.008157</td>\n",
       "      <td>0.985085</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(50, 51)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IC</td>\n",
       "      <td>0.010549</td>\n",
       "      <td>0.010040</td>\n",
       "      <td>0.951749</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(100, 101)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IC</td>\n",
       "      <td>0.011314</td>\n",
       "      <td>0.010560</td>\n",
       "      <td>0.933316</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(500, 501)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IC</td>\n",
       "      <td>0.012127</td>\n",
       "      <td>0.010996</td>\n",
       "      <td>0.906778</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(1000, 1001)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IC</td>\n",
       "      <td>0.012480</td>\n",
       "      <td>0.011239</td>\n",
       "      <td>0.900521</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(5000, 5001)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IC</td>\n",
       "      <td>0.012315</td>\n",
       "      <td>0.011045</td>\n",
       "      <td>0.896914</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(10, 11)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IAC</td>\n",
       "      <td>0.005325</td>\n",
       "      <td>0.005313</td>\n",
       "      <td>0.997746</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(20, 21)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IAC</td>\n",
       "      <td>0.008195</td>\n",
       "      <td>0.007975</td>\n",
       "      <td>0.973034</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(50, 51)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IAC</td>\n",
       "      <td>0.009745</td>\n",
       "      <td>0.009069</td>\n",
       "      <td>0.930631</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(100, 101)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IAC</td>\n",
       "      <td>0.010417</td>\n",
       "      <td>0.009502</td>\n",
       "      <td>0.912119</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(500, 501)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IAC</td>\n",
       "      <td>0.010665</td>\n",
       "      <td>0.009595</td>\n",
       "      <td>0.899583</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(1000, 1001)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IAC</td>\n",
       "      <td>0.010786</td>\n",
       "      <td>0.009680</td>\n",
       "      <td>0.897506</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(5000, 5001)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>IAC</td>\n",
       "      <td>0.010708</td>\n",
       "      <td>0.009588</td>\n",
       "      <td>0.895494</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(10, 11)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>MALLOWS-RELPHI-R</td>\n",
       "      <td>0.001169</td>\n",
       "      <td>0.001167</td>\n",
       "      <td>0.998290</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(20, 21)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>MALLOWS-RELPHI-R</td>\n",
       "      <td>0.001352</td>\n",
       "      <td>0.001337</td>\n",
       "      <td>0.989275</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(50, 51)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>MALLOWS-RELPHI-R</td>\n",
       "      <td>0.001103</td>\n",
       "      <td>0.001066</td>\n",
       "      <td>0.966455</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>17</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(100, 101)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>MALLOWS-RELPHI-R</td>\n",
       "      <td>0.000825</td>\n",
       "      <td>0.000777</td>\n",
       "      <td>0.941248</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>18</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(500, 501)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>MALLOWS-RELPHI-R</td>\n",
       "      <td>0.000370</td>\n",
       "      <td>0.000337</td>\n",
       "      <td>0.910811</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>19</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(1000, 1001)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>MALLOWS-RELPHI-R</td>\n",
       "      <td>0.000276</td>\n",
       "      <td>0.000246</td>\n",
       "      <td>0.889693</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>20</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(5000, 5001)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>MALLOWS-RELPHI-R</td>\n",
       "      <td>0.000139</td>\n",
       "      <td>0.000124</td>\n",
       "      <td>0.895683</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>21</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(10, 11)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>URN-R</td>\n",
       "      <td>0.002235</td>\n",
       "      <td>0.002217</td>\n",
       "      <td>0.991946</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>22</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(20, 21)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>URN-R</td>\n",
       "      <td>0.003344</td>\n",
       "      <td>0.003241</td>\n",
       "      <td>0.969054</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>23</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(50, 51)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>URN-R</td>\n",
       "      <td>0.003941</td>\n",
       "      <td>0.003652</td>\n",
       "      <td>0.926678</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>24</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(100, 101)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>URN-R</td>\n",
       "      <td>0.004167</td>\n",
       "      <td>0.003827</td>\n",
       "      <td>0.918287</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>25</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(500, 501)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>URN-R</td>\n",
       "      <td>0.004281</td>\n",
       "      <td>0.003886</td>\n",
       "      <td>0.907615</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>26</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(1000, 1001)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>URN-R</td>\n",
       "      <td>0.004402</td>\n",
       "      <td>0.003961</td>\n",
       "      <td>0.899818</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>27</th>\n",
       "      <td>Beat Path</td>\n",
       "      <td>Split Cycle</td>\n",
       "      <td>4</td>\n",
       "      <td>(5000, 5001)</td>\n",
       "      <td>2000000</td>\n",
       "      <td>URN-R</td>\n",
       "      <td>0.004375</td>\n",
       "      <td>0.003925</td>\n",
       "      <td>0.897029</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "           vm comparison_vm  num_cands    num_voters  num_profiles  \\\n",
       "0   Beat Path   Split Cycle          4      (10, 11)       2000000   \n",
       "1   Beat Path   Split Cycle          4      (20, 21)       2000000   \n",
       "2   Beat Path   Split Cycle          4      (50, 51)       2000000   \n",
       "3   Beat Path   Split Cycle          4    (100, 101)       2000000   \n",
       "4   Beat Path   Split Cycle          4    (500, 501)       2000000   \n",
       "5   Beat Path   Split Cycle          4  (1000, 1001)       2000000   \n",
       "6   Beat Path   Split Cycle          4  (5000, 5001)       2000000   \n",
       "7   Beat Path   Split Cycle          4      (10, 11)       2000000   \n",
       "8   Beat Path   Split Cycle          4      (20, 21)       2000000   \n",
       "9   Beat Path   Split Cycle          4      (50, 51)       2000000   \n",
       "10  Beat Path   Split Cycle          4    (100, 101)       2000000   \n",
       "11  Beat Path   Split Cycle          4    (500, 501)       2000000   \n",
       "12  Beat Path   Split Cycle          4  (1000, 1001)       2000000   \n",
       "13  Beat Path   Split Cycle          4  (5000, 5001)       2000000   \n",
       "14  Beat Path   Split Cycle          4      (10, 11)       2000000   \n",
       "15  Beat Path   Split Cycle          4      (20, 21)       2000000   \n",
       "16  Beat Path   Split Cycle          4      (50, 51)       2000000   \n",
       "17  Beat Path   Split Cycle          4    (100, 101)       2000000   \n",
       "18  Beat Path   Split Cycle          4    (500, 501)       2000000   \n",
       "19  Beat Path   Split Cycle          4  (1000, 1001)       2000000   \n",
       "20  Beat Path   Split Cycle          4  (5000, 5001)       2000000   \n",
       "21  Beat Path   Split Cycle          4      (10, 11)       2000000   \n",
       "22  Beat Path   Split Cycle          4      (20, 21)       2000000   \n",
       "23  Beat Path   Split Cycle          4      (50, 51)       2000000   \n",
       "24  Beat Path   Split Cycle          4    (100, 101)       2000000   \n",
       "25  Beat Path   Split Cycle          4    (500, 501)       2000000   \n",
       "26  Beat Path   Split Cycle          4  (1000, 1001)       2000000   \n",
       "27  Beat Path   Split Cycle          4  (5000, 5001)       2000000   \n",
       "\n",
       "             probmod  perc_diff_ws  perc_ssw_violation  \\\n",
       "0                 IC      0.005159            0.005148   \n",
       "1                 IC      0.008280            0.008157   \n",
       "2                 IC      0.010549            0.010040   \n",
       "3                 IC      0.011314            0.010560   \n",
       "4                 IC      0.012127            0.010996   \n",
       "5                 IC      0.012480            0.011239   \n",
       "6                 IC      0.012315            0.011045   \n",
       "7                IAC      0.005325            0.005313   \n",
       "8                IAC      0.008195            0.007975   \n",
       "9                IAC      0.009745            0.009069   \n",
       "10               IAC      0.010417            0.009502   \n",
       "11               IAC      0.010665            0.009595   \n",
       "12               IAC      0.010786            0.009680   \n",
       "13               IAC      0.010708            0.009588   \n",
       "14  MALLOWS-RELPHI-R      0.001169            0.001167   \n",
       "15  MALLOWS-RELPHI-R      0.001352            0.001337   \n",
       "16  MALLOWS-RELPHI-R      0.001103            0.001066   \n",
       "17  MALLOWS-RELPHI-R      0.000825            0.000777   \n",
       "18  MALLOWS-RELPHI-R      0.000370            0.000337   \n",
       "19  MALLOWS-RELPHI-R      0.000276            0.000246   \n",
       "20  MALLOWS-RELPHI-R      0.000139            0.000124   \n",
       "21             URN-R      0.002235            0.002217   \n",
       "22             URN-R      0.003344            0.003241   \n",
       "23             URN-R      0.003941            0.003652   \n",
       "24             URN-R      0.004167            0.003827   \n",
       "25             URN-R      0.004281            0.003886   \n",
       "26             URN-R      0.004402            0.003961   \n",
       "27             URN-R      0.004375            0.003925   \n",
       "\n",
       "    perc_ssw_violation_cond_diff_ws  \n",
       "0                          0.997868  \n",
       "1                          0.985085  \n",
       "2                          0.951749  \n",
       "3                          0.933316  \n",
       "4                          0.906778  \n",
       "5                          0.900521  \n",
       "6                          0.896914  \n",
       "7                          0.997746  \n",
       "8                          0.973034  \n",
       "9                          0.930631  \n",
       "10                         0.912119  \n",
       "11                         0.899583  \n",
       "12                         0.897506  \n",
       "13                         0.895494  \n",
       "14                         0.998290  \n",
       "15                         0.989275  \n",
       "16                         0.966455  \n",
       "17                         0.941248  \n",
       "18                         0.910811  \n",
       "19                         0.889693  \n",
       "20                         0.895683  \n",
       "21                         0.991946  \n",
       "22                         0.969054  \n",
       "23                         0.926678  \n",
       "24                         0.918287  \n",
       "25                         0.907615  \n",
       "26                         0.899818  \n",
       "27                         0.897029  "
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "01136ef8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Of the profiles in which the Beat Path and Split Cycle winners are different, the percent of strong stability for winners violations for Beat Path (Table 1).\n"
     ]
    },
    {
     "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>num_voters</th>\n",
       "      <th>(10, 11)</th>\n",
       "      <th>(100, 101)</th>\n",
       "      <th>(1000, 1001)</th>\n",
       "      <th>(20, 21)</th>\n",
       "      <th>(50, 51)</th>\n",
       "      <th>(500, 501)</th>\n",
       "      <th>(5000, 5001)</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>probmod</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>IAC</th>\n",
       "      <td>0.997746</td>\n",
       "      <td>0.912119</td>\n",
       "      <td>0.897506</td>\n",
       "      <td>0.973034</td>\n",
       "      <td>0.930631</td>\n",
       "      <td>0.899583</td>\n",
       "      <td>0.895494</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IC</th>\n",
       "      <td>0.997868</td>\n",
       "      <td>0.933316</td>\n",
       "      <td>0.900521</td>\n",
       "      <td>0.985085</td>\n",
       "      <td>0.951749</td>\n",
       "      <td>0.906778</td>\n",
       "      <td>0.896914</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>MALLOWS-RELPHI-R</th>\n",
       "      <td>0.998290</td>\n",
       "      <td>0.941248</td>\n",
       "      <td>0.889693</td>\n",
       "      <td>0.989275</td>\n",
       "      <td>0.966455</td>\n",
       "      <td>0.910811</td>\n",
       "      <td>0.895683</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>URN-R</th>\n",
       "      <td>0.991946</td>\n",
       "      <td>0.918287</td>\n",
       "      <td>0.899818</td>\n",
       "      <td>0.969054</td>\n",
       "      <td>0.926678</td>\n",
       "      <td>0.907615</td>\n",
       "      <td>0.897029</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "num_voters        (10, 11)  (100, 101)  (1000, 1001)  (20, 21)  (50, 51)  \\\n",
       "probmod                                                                    \n",
       "IAC               0.997746    0.912119      0.897506  0.973034  0.930631   \n",
       "IC                0.997868    0.933316      0.900521  0.985085  0.951749   \n",
       "MALLOWS-RELPHI-R  0.998290    0.941248      0.889693  0.989275  0.966455   \n",
       "URN-R             0.991946    0.918287      0.899818  0.969054  0.926678   \n",
       "\n",
       "num_voters        (500, 501)  (5000, 5001)  \n",
       "probmod                                     \n",
       "IAC                 0.899583      0.895494  \n",
       "IC                  0.906778      0.896914  \n",
       "MALLOWS-RELPHI-R    0.910811      0.895683  \n",
       "URN-R               0.907615      0.897029  "
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"\\nOf the profiles in which the Beat Path and Split Cycle winners are different, the percent of strong stability for winners violations for Beat Path (Table 1).\")\n",
    "df_table = df.pivot(index=\"probmod\", columns=\"num_voters\", values=\"perc_ssw_violation_cond_diff_ws\")\n",
    "df_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "9287cea7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "The percent of strong stability for winners violations for Beat Path.\n"
     ]
    },
    {
     "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>num_voters</th>\n",
       "      <th>(10, 11)</th>\n",
       "      <th>(100, 101)</th>\n",
       "      <th>(1000, 1001)</th>\n",
       "      <th>(20, 21)</th>\n",
       "      <th>(50, 51)</th>\n",
       "      <th>(500, 501)</th>\n",
       "      <th>(5000, 5001)</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>probmod</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>IAC</th>\n",
       "      <td>0.005313</td>\n",
       "      <td>0.009502</td>\n",
       "      <td>0.009680</td>\n",
       "      <td>0.007975</td>\n",
       "      <td>0.009069</td>\n",
       "      <td>0.009595</td>\n",
       "      <td>0.009588</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IC</th>\n",
       "      <td>0.005148</td>\n",
       "      <td>0.010560</td>\n",
       "      <td>0.011239</td>\n",
       "      <td>0.008157</td>\n",
       "      <td>0.010040</td>\n",
       "      <td>0.010996</td>\n",
       "      <td>0.011045</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>MALLOWS-RELPHI-R</th>\n",
       "      <td>0.001167</td>\n",
       "      <td>0.000777</td>\n",
       "      <td>0.000246</td>\n",
       "      <td>0.001337</td>\n",
       "      <td>0.001066</td>\n",
       "      <td>0.000337</td>\n",
       "      <td>0.000124</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>URN-R</th>\n",
       "      <td>0.002217</td>\n",
       "      <td>0.003827</td>\n",
       "      <td>0.003961</td>\n",
       "      <td>0.003241</td>\n",
       "      <td>0.003652</td>\n",
       "      <td>0.003886</td>\n",
       "      <td>0.003925</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "num_voters        (10, 11)  (100, 101)  (1000, 1001)  (20, 21)  (50, 51)  \\\n",
       "probmod                                                                    \n",
       "IAC               0.005313    0.009502      0.009680  0.007975  0.009069   \n",
       "IC                0.005148    0.010560      0.011239  0.008157  0.010040   \n",
       "MALLOWS-RELPHI-R  0.001167    0.000777      0.000246  0.001337  0.001066   \n",
       "URN-R             0.002217    0.003827      0.003961  0.003241  0.003652   \n",
       "\n",
       "num_voters        (500, 501)  (5000, 5001)  \n",
       "probmod                                     \n",
       "IAC                 0.009595      0.009588  \n",
       "IC                  0.010996      0.011045  \n",
       "MALLOWS-RELPHI-R    0.000337      0.000124  \n",
       "URN-R               0.003886      0.003925  "
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"\\nThe percent of strong stability for winners violations for Beat Path.\")\n",
    "\n",
    "df_table = df.pivot(index=\"probmod\", columns=\"num_voters\", values=\"perc_ssw_violation\")\n",
    "df_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a86cbc2d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "The percent of profiles in which Beat Path and Split Cycle have different winners.\n"
     ]
    },
    {
     "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>num_voters</th>\n",
       "      <th>(10, 11)</th>\n",
       "      <th>(100, 101)</th>\n",
       "      <th>(1000, 1001)</th>\n",
       "      <th>(20, 21)</th>\n",
       "      <th>(50, 51)</th>\n",
       "      <th>(500, 501)</th>\n",
       "      <th>(5000, 5001)</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>probmod</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>IAC</th>\n",
       "      <td>0.005325</td>\n",
       "      <td>0.010417</td>\n",
       "      <td>0.010786</td>\n",
       "      <td>0.008195</td>\n",
       "      <td>0.009745</td>\n",
       "      <td>0.010665</td>\n",
       "      <td>0.010708</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IC</th>\n",
       "      <td>0.005159</td>\n",
       "      <td>0.011314</td>\n",
       "      <td>0.012480</td>\n",
       "      <td>0.008280</td>\n",
       "      <td>0.010549</td>\n",
       "      <td>0.012127</td>\n",
       "      <td>0.012315</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>MALLOWS-RELPHI-R</th>\n",
       "      <td>0.001169</td>\n",
       "      <td>0.000825</td>\n",
       "      <td>0.000276</td>\n",
       "      <td>0.001352</td>\n",
       "      <td>0.001103</td>\n",
       "      <td>0.000370</td>\n",
       "      <td>0.000139</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>URN-R</th>\n",
       "      <td>0.002235</td>\n",
       "      <td>0.004167</td>\n",
       "      <td>0.004402</td>\n",
       "      <td>0.003344</td>\n",
       "      <td>0.003941</td>\n",
       "      <td>0.004281</td>\n",
       "      <td>0.004375</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "num_voters        (10, 11)  (100, 101)  (1000, 1001)  (20, 21)  (50, 51)  \\\n",
       "probmod                                                                    \n",
       "IAC               0.005325    0.010417      0.010786  0.008195  0.009745   \n",
       "IC                0.005159    0.011314      0.012480  0.008280  0.010549   \n",
       "MALLOWS-RELPHI-R  0.001169    0.000825      0.000276  0.001352  0.001103   \n",
       "URN-R             0.002235    0.004167      0.004402  0.003344  0.003941   \n",
       "\n",
       "num_voters        (500, 501)  (5000, 5001)  \n",
       "probmod                                     \n",
       "IAC                 0.010665      0.010708  \n",
       "IC                  0.012127      0.012315  \n",
       "MALLOWS-RELPHI-R    0.000370      0.000139  \n",
       "URN-R               0.004281      0.004375  "
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"\\nThe percent of profiles in which Beat Path and Split Cycle have different winners.\")\n",
    "df_table = df.pivot(index=\"probmod\", columns=\"num_voters\", values=\"perc_diff_ws\")\n",
    "df_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e46c60c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def has_strong_stability_for_winners_violation(vm, edata, weak_condorcetian_candidates = None): \n",
    "    \"\"\"\n",
    "    Definition 4.2.3: Return True if there are candidates a and b such that\n",
    "      1. a in a winner according to vm in edata without b in the election, \n",
    "      2. a is majority preferred to b or tied with b, and \n",
    "      3. a is not a winner in edata\n",
    "    \n",
    "    This is equivalent to requiring that all weak Condorcetian candidates are winners in edata according to vm. \n",
    "    \"\"\"\n",
    "    candidates = edata.candidates\n",
    "    \n",
    "    if weak_condorcetian_candidates is None: \n",
    "        weak_condorcetian_candidates = [c for c in candidates if is_weak_condorcetian(vm, c, edata)]\n",
    "    \n",
    "    ws = vm(edata)\n",
    "        \n",
    "    return not set(weak_condorcetian_candidates).issubset(set(ws))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "bc66d3b8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def record_strong_stability_for_winners_violation(vms, main_vm, num_cands, num_voters, probmod,  t): \n",
    "    \n",
    "    prof = generate_profile(num_cands, num_voters, probmod=probmod)\n",
    "    \n",
    "    data = {vm.name: dict() for vm in vms}\n",
    "    for vm in vms: \n",
    "        weak_condorcetian_candidates = [c for c in prof.candidates if is_weak_condorcetian(vm, c, prof)]\n",
    "        \n",
    "        main_ws = main_vm(prof)\n",
    "        vm_ws = vm(prof)\n",
    "        data[vm.name] =  {\n",
    "            \"diff_ws\": main_ws != vm_ws, \n",
    "            \"ssw_violation\": has_strong_stability_for_winners_violation(vm, prof, weak_condorcetian_candidates = weak_condorcetian_candidates)\n",
    "        }\n",
    "    return data\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "98417c33",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPUS: 12\n",
      "SKIP_SIMULATION is set to True\n"
     ]
    }
   ],
   "source": [
    "## Parameters for the simulation\n",
    "\n",
    "# WARNING: The simulation takes a very long time!  \n",
    "# Set the following to True to skip running the simulation\n",
    "SKIP_SIMULATION = True  \n",
    "\n",
    "num_trials = 1_000_000 # WARNING: This takes a very long time to run!\n",
    "\n",
    "numbers_of_candidates = [\n",
    "#     3,\n",
    "    4,\n",
    "#     5,\n",
    "#     6,\n",
    "#     7,\n",
    "#     8,\n",
    "#     10, \n",
    "#     15, \n",
    "#     20\n",
    "]\n",
    "\n",
    "numbers_of_voters = [\n",
    "    (10, 11),\n",
    "    (20, 21),\n",
    "    (50, 51),\n",
    "    (100, 101),\n",
    "    (500, 501),\n",
    "    (1000, 1001),\n",
    "    (5000, 5001),\n",
    "] \n",
    "\n",
    "# uncomment probability models as needed\n",
    "prob_models = [\n",
    "    \"IC\", \n",
    "    \"IAC\", \n",
    "    \"MALLOWS-RELPHI-R\", \n",
    "    \"URN-R\"\n",
    "]\n",
    " \n",
    "vms = [\n",
    "    beat_path,\n",
    "#     llull,\n",
    "#     copeland,\n",
    "#     minimax,\n",
    "#     uc_gill, # uncovered set\n",
    "#     instant_runoff,  \n",
    "#     borda,\n",
    "#     plurality,\n",
    "#     getcha\n",
    "]\n",
    "\n",
    "main_vm = split_cycle\n",
    "\n",
    "# use parallel processing to speed up the search\n",
    "cpus = cpu_count()\n",
    "print(f'CPUS: {cpus}')\n",
    "pool = Pool(10) # set to cpus when you can use all the processors\n",
    "\n",
    "print(f\"SKIP_SIMULATION is set to {SKIP_SIMULATION}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "d8265d04",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2 µs, sys: 0 ns, total: 2 µs\n",
      "Wall time: 3.1 µs\n"
     ]
    }
   ],
   "source": [
    "%%time \n",
    "\n",
    "if not SKIP_SIMULATION:\n",
    "    data_for_df = {\n",
    "        \"vm\": list(),\n",
    "        \"comparison_vm\": list(),\n",
    "        \"num_cands\": list(), \n",
    "        \"num_voters\": list(),\n",
    "        \"num_profiles\": list(),\n",
    "        \"probmod\": list(),\n",
    "        \"perc_diff_ws\": list(),\n",
    "        \"perc_ssw_violation\": list(),\n",
    "        \"perc_ssw_violation_cond_diff_ws\": list()\n",
    "    }\n",
    "\n",
    "    for probmod in prob_models:\n",
    "\n",
    "        print(probmod)\n",
    "\n",
    "        voting_scenarios = list(product(numbers_of_candidates, numbers_of_voters))\n",
    "\n",
    "        data = {vm.name: {_vs: {\"total_profiles\": 0, \n",
    "                                \"total_even\": list(),\n",
    "                                \"total_odd\": list()} \n",
    "                        for _vs in voting_scenarios} \n",
    "                for vm in vms}\n",
    "\n",
    "        for vs in voting_scenarios:\n",
    "            print(f\"     {vs}\")\n",
    "            num_candidates = vs[0]\n",
    "            num_voters_even = vs[1][0]\n",
    "            num_voters_odd = vs[1][1]\n",
    "\n",
    "            # find the violations in parallel\n",
    "\n",
    "            record_violations_even = partial(\n",
    "                record_strong_stability_for_winners_violation,\n",
    "                vms, \n",
    "                main_vm, \n",
    "                num_candidates, \n",
    "                num_voters_even, \n",
    "                probmod)\n",
    "\n",
    "            record_violations_odd = partial(\n",
    "                record_strong_stability_for_winners_violation,\n",
    "                vms, \n",
    "                main_vm, \n",
    "                num_candidates, \n",
    "                num_voters_odd, \n",
    "                probmod)\n",
    "\n",
    "            violations_even = pool.map(record_violations_even, range(num_trials))\n",
    "            violations_odd = pool.map(record_violations_odd, range(num_trials))\n",
    "\n",
    "            # done calculating the violations\n",
    "            for vm in vms:\n",
    "                data_even = [d[vm.name] for d in violations_even]\n",
    "                data_odd = [d[vm.name] for d in violations_odd]\n",
    "                all_data = data_even + data_odd\n",
    "\n",
    "                num_profiles = len(all_data)\n",
    "\n",
    "                data_for_df[\"vm\"].append(vm.name)\n",
    "                data_for_df[\"comparison_vm\"].append(main_vm.name)\n",
    "                data_for_df[\"num_cands\"].append(num_candidates)\n",
    "                data_for_df[\"num_voters\"].append(str((num_voters_even, num_voters_odd)))\n",
    "                data_for_df[\"probmod\"].append(probmod)            \n",
    "                data_for_df[\"num_profiles\"].append(num_profiles)\n",
    "\n",
    "                data_for_df[\"perc_diff_ws\"].append(sum([d[\"diff_ws\"] for d in all_data]) / num_profiles)\n",
    "                data_for_df[\"perc_ssw_violation\"].append(sum([d[\"ssw_violation\"] for d in all_data]) / num_profiles)\n",
    "                \n",
    "                data_with_diff_ws = [d for d in all_data if d[\"diff_ws\"]]\n",
    "                \n",
    "                if len(data_with_diff_ws) > 0: \n",
    "                    data_for_df[\"perc_ssw_violation_cond_diff_ws\"].append(sum([d[\"ssw_violation\"] for d in data_with_diff_ws]) / len(data_with_diff_ws))\n",
    "                else: \n",
    "                    data_for_df[\"perc_ssw_violation_cond_diff_ws\"].append(0.0)\n",
    "                    \n",
    "            df = pd.DataFrame(data_for_df)\n",
    "            df.to_csv(f\"./violations_ssw.csv\",index=False)\n",
    "            \n",
    "\n",
    "\n",
    "    print(\"done.\")\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "7dbe45fe",
   "metadata": {},
   "source": [
    "## Table 2\n",
    "\n",
    "Of four-candidate linear profiles in which $BP(\\mathbf{P})\\neq SV(\\mathbf{P})$ find the percentage in which Beat Path violates strong stability for winners with tiebreaking."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "2bdb0d7e",
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.read_csv(\"./tables-data-FINAL/violations_ssw_w_tb.csv\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "499291c5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Of the profiles in which the Beat Path and Stable Voting winners are different, \n",
      "the percent of strong stability for winners with tiebreaking violations for Beat Path (Table 2).\n"
     ]
    },
    {
     "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>num_voters</th>\n",
       "      <th>(10, 11)</th>\n",
       "      <th>(100, 101)</th>\n",
       "      <th>(1000, 1001)</th>\n",
       "      <th>(20, 21)</th>\n",
       "      <th>(50, 51)</th>\n",
       "      <th>(500, 501)</th>\n",
       "      <th>(5000, 5001)</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>probmod</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>IAC</th>\n",
       "      <td>0.275862</td>\n",
       "      <td>0.333333</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.176471</td>\n",
       "      <td>0.230769</td>\n",
       "      <td>0.333333</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IC</th>\n",
       "      <td>0.129032</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.428571</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>1.000000</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>MALLOWS-RELPHI-R</th>\n",
       "      <td>0.222222</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.400000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>URN-R</th>\n",
       "      <td>0.260870</td>\n",
       "      <td>0.428571</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.142857</td>\n",
       "      <td>0.222222</td>\n",
       "      <td>0.500000</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "num_voters        (10, 11)  (100, 101)  (1000, 1001)  (20, 21)  (50, 51)  \\\n",
       "probmod                                                                    \n",
       "IAC               0.275862    0.333333           0.0  0.176471  0.230769   \n",
       "IC                0.129032    0.000000           0.0  0.428571  0.000000   \n",
       "MALLOWS-RELPHI-R  0.222222    0.000000           0.0  0.400000  0.000000   \n",
       "URN-R             0.260870    0.428571           0.0  0.142857  0.222222   \n",
       "\n",
       "num_voters        (500, 501)  (5000, 5001)  \n",
       "probmod                                     \n",
       "IAC                 0.333333           1.0  \n",
       "IC                  1.000000           0.0  \n",
       "MALLOWS-RELPHI-R    0.000000           0.0  \n",
       "URN-R               0.500000           0.0  "
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"\\nOf the profiles in which the Beat Path and Stable Voting winners are different, \")\n",
    "print(\"the percent of strong stability for winners with tiebreaking violations for Beat Path (Table 2).\")\n",
    "df_table = df.pivot(index=\"probmod\", columns=\"num_voters\", values=\"perc_ssw_w_tb_violation_cond_diff_ws\")\n",
    "df_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "090689f8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "The percent of strong stability for winners with tiebreaking violations for Beat Path.\n"
     ]
    },
    {
     "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>num_voters</th>\n",
       "      <th>(10, 11)</th>\n",
       "      <th>(100, 101)</th>\n",
       "      <th>(1000, 1001)</th>\n",
       "      <th>(20, 21)</th>\n",
       "      <th>(50, 51)</th>\n",
       "      <th>(500, 501)</th>\n",
       "      <th>(5000, 5001)</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>probmod</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>IAC</th>\n",
       "      <td>0.08</td>\n",
       "      <td>0.020</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.030</td>\n",
       "      <td>0.015</td>\n",
       "      <td>0.005</td>\n",
       "      <td>0.01</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IC</th>\n",
       "      <td>0.06</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.045</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.045</td>\n",
       "      <td>0.00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>MALLOWS-RELPHI-R</th>\n",
       "      <td>0.01</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.010</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>URN-R</th>\n",
       "      <td>0.03</td>\n",
       "      <td>0.015</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.010</td>\n",
       "      <td>0.010</td>\n",
       "      <td>0.005</td>\n",
       "      <td>0.00</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "num_voters        (10, 11)  (100, 101)  (1000, 1001)  (20, 21)  (50, 51)  \\\n",
       "probmod                                                                    \n",
       "IAC                   0.08       0.020           0.0     0.030     0.015   \n",
       "IC                    0.06       0.000           0.0     0.045     0.000   \n",
       "MALLOWS-RELPHI-R      0.01       0.000           0.0     0.010     0.000   \n",
       "URN-R                 0.03       0.015           0.0     0.010     0.010   \n",
       "\n",
       "num_voters        (500, 501)  (5000, 5001)  \n",
       "probmod                                     \n",
       "IAC                    0.005          0.01  \n",
       "IC                     0.045          0.00  \n",
       "MALLOWS-RELPHI-R       0.000          0.00  \n",
       "URN-R                  0.005          0.00  "
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"\\nThe percent of strong stability for winners with tiebreaking violations for Beat Path.\")\n",
    "df_table = df.pivot(index=\"probmod\", columns=\"num_voters\", values=\"perc_ssw_w_tb_violation\")\n",
    "df_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "9658fa8b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "The percent of profiles in which Beat Path and Stable Voting have different winners.\n"
     ]
    },
    {
     "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>num_voters</th>\n",
       "      <th>(10, 11)</th>\n",
       "      <th>(100, 101)</th>\n",
       "      <th>(1000, 1001)</th>\n",
       "      <th>(20, 21)</th>\n",
       "      <th>(50, 51)</th>\n",
       "      <th>(500, 501)</th>\n",
       "      <th>(5000, 5001)</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>probmod</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>IAC</th>\n",
       "      <td>0.290</td>\n",
       "      <td>0.060</td>\n",
       "      <td>0.010</td>\n",
       "      <td>0.170</td>\n",
       "      <td>0.065</td>\n",
       "      <td>0.015</td>\n",
       "      <td>0.01</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IC</th>\n",
       "      <td>0.465</td>\n",
       "      <td>0.105</td>\n",
       "      <td>0.045</td>\n",
       "      <td>0.105</td>\n",
       "      <td>0.105</td>\n",
       "      <td>0.045</td>\n",
       "      <td>0.00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>MALLOWS-RELPHI-R</th>\n",
       "      <td>0.045</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.025</td>\n",
       "      <td>0.010</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>URN-R</th>\n",
       "      <td>0.115</td>\n",
       "      <td>0.035</td>\n",
       "      <td>0.000</td>\n",
       "      <td>0.070</td>\n",
       "      <td>0.045</td>\n",
       "      <td>0.010</td>\n",
       "      <td>0.00</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "num_voters        (10, 11)  (100, 101)  (1000, 1001)  (20, 21)  (50, 51)  \\\n",
       "probmod                                                                    \n",
       "IAC                  0.290       0.060         0.010     0.170     0.065   \n",
       "IC                   0.465       0.105         0.045     0.105     0.105   \n",
       "MALLOWS-RELPHI-R     0.045       0.000         0.000     0.025     0.010   \n",
       "URN-R                0.115       0.035         0.000     0.070     0.045   \n",
       "\n",
       "num_voters        (500, 501)  (5000, 5001)  \n",
       "probmod                                     \n",
       "IAC                    0.015          0.01  \n",
       "IC                     0.045          0.00  \n",
       "MALLOWS-RELPHI-R       0.000          0.00  \n",
       "URN-R                  0.010          0.00  "
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"\\nThe percent of profiles in which Beat Path and Stable Voting have different winners.\")\n",
    "df_table = df.pivot(index=\"probmod\", columns=\"num_voters\", values=\"perc_diff_ws\")\n",
    "df_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "baaa5138",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "def has_strong_stability_for_winners_with_tiebreaking_violation(vm, edata, condorcetian_candidates = None, weak_condorcetian_candidates = None): \n",
    "\n",
    "    \"\"\"\n",
    "    Definition 4.20: Return True if there is a vioalation of strong stability winners with tiebreaking.  \n",
    "    This function returns True when: \n",
    "       \n",
    "       1.  vm vioaltes stability for winners with tiebreaking for edata, or\n",
    "       2.  there some candidate is weakly Condorcetian for vm in edata and no candidate is Condorcetian for vm in edata, and\n",
    "           it is not the case that all candidates who win in edata according to vm are weakly Condorcetian for vm in edata.\n",
    "\n",
    "    \"\"\"\n",
    "    candidates = edata.candidates\n",
    "    \n",
    "    if condorcetian_candidates is None: \n",
    "        condorcetian_candidates = [c for c in candidates if is_condorcetian(vm, c, edata)]\n",
    "        \n",
    "    if weak_condorcetian_candidates is None: \n",
    "        weak_condorcetian_candidates = [c for c in candidates if is_weak_condorcetian(vm, c, edata)]\n",
    "        \n",
    "    ws = vm(edata)\n",
    "        \n",
    "    return (len(condorcetian_candidates) > 0 and not set(ws).issubset(set(condorcetian_candidates)))\\\n",
    "    or (len(weak_condorcetian_candidates) != 0 and len(condorcetian_candidates) == 0 and not set(ws).issubset(set(weak_condorcetian_candidates)))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "8bf039f4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def record_strong_stability_for_winners_with_tiebreaking_violation(\n",
    "    vms, \n",
    "    main_vm, \n",
    "    num_cands, \n",
    "    num_voters, \n",
    "    probmod, \n",
    "    t): \n",
    "    \n",
    "    np.random.seed(current_process().pid)\n",
    "    prof = generate_profile(num_cands, num_voters, probmod=probmod)\n",
    "    \n",
    "    data = {vm.name: dict() for vm in vms}\n",
    "    for vm in vms: \n",
    "        condorcetian_candidates = [c for c in prof.candidates if is_condorcetian(vm, c, prof)]\n",
    "        weak_condorcetian_candidates = [c for c in prof.candidates if is_weak_condorcetian(vm, c, prof)]\n",
    "        \n",
    "        main_ws = main_vm(prof)\n",
    "        vm_ws = vm(prof)\n",
    "        data[vm.name] =  {\n",
    "            \"diff_ws\": main_ws != vm_ws, \n",
    "            \"ssw_w_tb_violation\": has_strong_stability_for_winners_with_tiebreaking_violation(vm, \n",
    "                                                                                               prof, \n",
    "                                                                                               condorcetian_candidates = condorcetian_candidates,\n",
    "                                                                                               weak_condorcetian_candidates = weak_condorcetian_candidates)\n",
    "        }\n",
    "    return data\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "8d90f95e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPUS: 12\n",
      "SKIP_SIMULATION is set to True\n"
     ]
    }
   ],
   "source": [
    "## Parameters for the simulation\n",
    "\n",
    "# WARNING: The simulation takes a very long time!  \n",
    "# Set the following to True to skip running the simulation\n",
    "SKIP_SIMULATION = True  \n",
    "\n",
    "num_trials = 100#_000\n",
    "\n",
    "numbers_of_candidates = [\n",
    "#     3,\n",
    "    4,\n",
    "#     5,\n",
    "#     6,\n",
    "#     7,\n",
    "#     8,\n",
    "#     10, \n",
    "#     15, \n",
    "#     20\n",
    "]\n",
    "\n",
    "numbers_of_voters = [\n",
    "    (10, 11),\n",
    "    (20, 21),\n",
    "    (50, 51),\n",
    "    (100, 101),\n",
    "    (500, 501),\n",
    "    (1000, 1001),\n",
    "    (5000, 5001),\n",
    "] \n",
    "\n",
    "# uncomment probability models as needed\n",
    "prob_models = [\n",
    "    \"IC\", \n",
    "    \"IAC\", \n",
    "    \"MALLOWS-RELPHI-R\", \n",
    "    \"URN-R\"\n",
    "]\n",
    " \n",
    "vms = [\n",
    "    beat_path,\n",
    "#     llull,\n",
    "#     copeland,\n",
    "#     minimax,\n",
    "#     uc_gill, # uncovered set\n",
    "#     instant_runoff,  \n",
    "#     borda,\n",
    "#     plurality,\n",
    "#     getcha\n",
    "]\n",
    "\n",
    "main_vm = stable_voting\n",
    "\n",
    "# use parallel processing to speed up the search\n",
    "cpus = cpu_count()\n",
    "print(f'CPUS: {cpus}')\n",
    "pool = Pool(10) # set to cpus when you can use all the processors\n",
    "\n",
    "print(f\"SKIP_SIMULATION is set to {SKIP_SIMULATION}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "2462dac3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2 µs, sys: 1 µs, total: 3 µs\n",
      "Wall time: 3.1 µs\n"
     ]
    }
   ],
   "source": [
    "%%time \n",
    "\n",
    "if not SKIP_SIMULATION:\n",
    "    data_for_df = {\n",
    "        \"vm\": list(),\n",
    "        \"comparison_vm\": list(),\n",
    "        \"num_cands\": list(), \n",
    "        \"num_voters\": list(),\n",
    "        \"num_profiles\": list(),\n",
    "        \"probmod\": list(),\n",
    "        \"perc_diff_ws\": list(),\n",
    "        \"perc_ssw_w_tb_violation\": list(),\n",
    "        \"perc_ssw_w_tb_violation_cond_diff_ws\": list()\n",
    "    }\n",
    "\n",
    "    for probmod in prob_models:\n",
    "\n",
    "        print(probmod)\n",
    "\n",
    "        voting_scenarios = list(product(numbers_of_candidates, numbers_of_voters))\n",
    "\n",
    "        data = {vm.name: {_vs: {\"total_profiles\": 0, \n",
    "                                \"total_even\": list(),\n",
    "                                \"total_odd\": list()} \n",
    "                        for _vs in voting_scenarios} \n",
    "                for vm in vms}\n",
    "\n",
    "        for vs in voting_scenarios:\n",
    "            print(f\"     {vs}\")\n",
    "            num_candidates = vs[0]\n",
    "            num_voters_even = vs[1][0]\n",
    "            num_voters_odd = vs[1][1]\n",
    "\n",
    "            # find the violations in parallel\n",
    "\n",
    "            record_violations_even = partial(\n",
    "                record_strong_stability_for_winners_with_tiebreaking_violation,\n",
    "                vms, \n",
    "                main_vm, \n",
    "                num_candidates, \n",
    "                num_voters_even, \n",
    "                probmod)\n",
    "\n",
    "            record_violations_odd = partial(\n",
    "                record_strong_stability_for_winners_with_tiebreaking_violation,\n",
    "                vms, \n",
    "                main_vm, \n",
    "                num_candidates, \n",
    "                num_voters_odd, \n",
    "                probmod)\n",
    "\n",
    "            violations_even = pool.map(record_violations_even, range(num_trials))\n",
    "            violations_odd = pool.map(record_violations_odd, range(num_trials))\n",
    "\n",
    "            # done calculating the violations\n",
    "            for vm in vms:\n",
    "                data_even = [d[vm.name] for d in violations_even]\n",
    "                data_odd = [d[vm.name] for d in violations_odd]\n",
    "                all_data = data_even + data_odd\n",
    "                num_profiles = len(all_data)\n",
    "\n",
    "                data_for_df[\"vm\"].append(vm.name)\n",
    "                data_for_df[\"comparison_vm\"].append(main_vm.name)\n",
    "                data_for_df[\"num_cands\"].append(num_candidates)\n",
    "                data_for_df[\"num_voters\"].append(str((num_voters_even, num_voters_odd)))\n",
    "                data_for_df[\"num_profiles\"].append(num_profiles)\n",
    "                data_for_df[\"probmod\"].append(probmod)\n",
    "                data_for_df[\"perc_diff_ws\"].append(sum([d[\"diff_ws\"] for d in all_data]) / num_profiles)\n",
    "                data_for_df[\"perc_ssw_w_tb_violation\"].append(sum([d[\"ssw_w_tb_violation\"] for d in all_data]) / num_profiles)\n",
    "                \n",
    "                data_with_diff_ws = [d for d in all_data if d[\"diff_ws\"]]\n",
    "                \n",
    "                if len(data_with_diff_ws) > 0: \n",
    "                    data_for_df[\"perc_ssw_w_tb_violation_cond_diff_ws\"].append(sum([d[\"ssw_w_tb_violation\"] for d in data_with_diff_ws]) / len(data_with_diff_ws))\n",
    "                else: \n",
    "                    data_for_df[\"perc_ssw_w_tb_violation_cond_diff_ws\"].append(0.0)\n",
    "                    \n",
    "            df = pd.DataFrame(data_for_df)\n",
    "            df.to_csv(f\"./violations_ssw_w_tb.csv\",index=False)\n",
    "            \n",
    "    print(\"done.\")\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "c6f0fa8f",
   "metadata": {},
   "source": [
    "## Table 3\n",
    "\n",
    "Estimated average sizes of winning sets for profiles with a given number of candidates in the limit as the number of voters goes to infinity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "152e27e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.read_csv(\"./tables-data-FINAL/irresoluteness_inf_voters_ADDITIONAL_TEST2.csv\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "06536603",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " Average Winning Set Size (Table 3)\n",
      "\n"
     ]
    },
    {
     "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>num_cands</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "      <th>7</th>\n",
       "      <th>8</th>\n",
       "      <th>9</th>\n",
       "      <th>10</th>\n",
       "      <th>20</th>\n",
       "      <th>30</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>vm</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>Copeland</th>\n",
       "      <td>1.175648</td>\n",
       "      <td>1.260324</td>\n",
       "      <td>1.288842</td>\n",
       "      <td>1.301580</td>\n",
       "      <td>1.309300</td>\n",
       "      <td>1.312284</td>\n",
       "      <td>1.312722</td>\n",
       "      <td>1.311334</td>\n",
       "      <td>1.278053</td>\n",
       "      <td>1.247802</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>GETCHA</th>\n",
       "      <td>1.175648</td>\n",
       "      <td>1.440927</td>\n",
       "      <td>1.786059</td>\n",
       "      <td>2.210534</td>\n",
       "      <td>2.715445</td>\n",
       "      <td>3.299664</td>\n",
       "      <td>3.956272</td>\n",
       "      <td>4.678948</td>\n",
       "      <td>13.524865</td>\n",
       "      <td>22.914119</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Split Cycle</th>\n",
       "      <td>1.000000</td>\n",
       "      <td>1.012480</td>\n",
       "      <td>1.032526</td>\n",
       "      <td>1.056392</td>\n",
       "      <td>1.082383</td>\n",
       "      <td>1.109546</td>\n",
       "      <td>1.136609</td>\n",
       "      <td>1.164322</td>\n",
       "      <td>1.417049</td>\n",
       "      <td>1.624962</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Uncovered Set</th>\n",
       "      <td>1.175648</td>\n",
       "      <td>1.350626</td>\n",
       "      <td>1.529297</td>\n",
       "      <td>1.710961</td>\n",
       "      <td>1.896472</td>\n",
       "      <td>2.084839</td>\n",
       "      <td>2.274966</td>\n",
       "      <td>2.468487</td>\n",
       "      <td>4.550156</td>\n",
       "      <td>6.840625</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "num_cands            3         4         5         6         7         8   \\\n",
       "vm                                                                          \n",
       "Copeland       1.175648  1.260324  1.288842  1.301580  1.309300  1.312284   \n",
       "GETCHA         1.175648  1.440927  1.786059  2.210534  2.715445  3.299664   \n",
       "Split Cycle    1.000000  1.012480  1.032526  1.056392  1.082383  1.109546   \n",
       "Uncovered Set  1.175648  1.350626  1.529297  1.710961  1.896472  2.084839   \n",
       "\n",
       "num_cands            9         10         20         30  \n",
       "vm                                                       \n",
       "Copeland       1.312722  1.311334   1.278053   1.247802  \n",
       "GETCHA         3.956272  4.678948  13.524865  22.914119  \n",
       "Split Cycle    1.136609  1.164322   1.417049   1.624962  \n",
       "Uncovered Set  2.274966  2.468487   4.550156   6.840625  "
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"\\n Average Winning Set Size (Table 3)\\n\")\n",
    "df_table = df.pivot(index=\"vm\", columns=\"num_cands\", values=\"avg_ws_size\")\n",
    "df_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "e8342e1d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " Proportion with Multiple Winners\n",
      "\n"
     ]
    },
    {
     "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>num_cands</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "      <th>7</th>\n",
       "      <th>8</th>\n",
       "      <th>9</th>\n",
       "      <th>10</th>\n",
       "      <th>20</th>\n",
       "      <th>30</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>vm</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>Copeland</th>\n",
       "      <td>0.087824</td>\n",
       "      <td>0.175313</td>\n",
       "      <td>0.217052</td>\n",
       "      <td>0.234268</td>\n",
       "      <td>0.242372</td>\n",
       "      <td>0.246132</td>\n",
       "      <td>0.247617</td>\n",
       "      <td>0.247456</td>\n",
       "      <td>0.227518</td>\n",
       "      <td>0.206849</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>GETCHA</th>\n",
       "      <td>0.087824</td>\n",
       "      <td>0.175313</td>\n",
       "      <td>0.251198</td>\n",
       "      <td>0.315078</td>\n",
       "      <td>0.369246</td>\n",
       "      <td>0.415267</td>\n",
       "      <td>0.454564</td>\n",
       "      <td>0.488688</td>\n",
       "      <td>0.681362</td>\n",
       "      <td>0.764981</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Split Cycle</th>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.012480</td>\n",
       "      <td>0.031932</td>\n",
       "      <td>0.054349</td>\n",
       "      <td>0.077936</td>\n",
       "      <td>0.101794</td>\n",
       "      <td>0.124684</td>\n",
       "      <td>0.147368</td>\n",
       "      <td>0.322293</td>\n",
       "      <td>0.432342</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Uncovered Set</th>\n",
       "      <td>0.087824</td>\n",
       "      <td>0.175313</td>\n",
       "      <td>0.251198</td>\n",
       "      <td>0.315078</td>\n",
       "      <td>0.369246</td>\n",
       "      <td>0.415267</td>\n",
       "      <td>0.454564</td>\n",
       "      <td>0.488688</td>\n",
       "      <td>0.681362</td>\n",
       "      <td>0.764981</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "num_cands            3         4         5         6         7         8   \\\n",
       "vm                                                                          \n",
       "Copeland       0.087824  0.175313  0.217052  0.234268  0.242372  0.246132   \n",
       "GETCHA         0.087824  0.175313  0.251198  0.315078  0.369246  0.415267   \n",
       "Split Cycle    0.000000  0.012480  0.031932  0.054349  0.077936  0.101794   \n",
       "Uncovered Set  0.087824  0.175313  0.251198  0.315078  0.369246  0.415267   \n",
       "\n",
       "num_cands            9         10        20        30  \n",
       "vm                                                     \n",
       "Copeland       0.247617  0.247456  0.227518  0.206849  \n",
       "GETCHA         0.454564  0.488688  0.681362  0.764981  \n",
       "Split Cycle    0.124684  0.147368  0.322293  0.432342  \n",
       "Uncovered Set  0.454564  0.488688  0.681362  0.764981  "
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"\\n Proportion with Multiple Winners\\n\")\n",
    "df_table = df.pivot(index=\"vm\", columns=\"num_cands\", values=\"perc_mult_winners\")\n",
    "df_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "c8a16dbc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " Proportion of Profiles with a Condorcet Winner\n",
      "\n"
     ]
    },
    {
     "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>num_cands</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "      <th>7</th>\n",
       "      <th>8</th>\n",
       "      <th>9</th>\n",
       "      <th>10</th>\n",
       "      <th>20</th>\n",
       "      <th>30</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>vm</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>Copeland</th>\n",
       "      <td>0.912176</td>\n",
       "      <td>0.824687</td>\n",
       "      <td>0.748802</td>\n",
       "      <td>0.684922</td>\n",
       "      <td>0.630754</td>\n",
       "      <td>0.584733</td>\n",
       "      <td>0.545436</td>\n",
       "      <td>0.511312</td>\n",
       "      <td>0.318638</td>\n",
       "      <td>0.235018</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>GETCHA</th>\n",
       "      <td>0.912176</td>\n",
       "      <td>0.824687</td>\n",
       "      <td>0.748802</td>\n",
       "      <td>0.684922</td>\n",
       "      <td>0.630754</td>\n",
       "      <td>0.584733</td>\n",
       "      <td>0.545436</td>\n",
       "      <td>0.511312</td>\n",
       "      <td>0.318638</td>\n",
       "      <td>0.235018</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Split Cycle</th>\n",
       "      <td>0.912176</td>\n",
       "      <td>0.824687</td>\n",
       "      <td>0.748802</td>\n",
       "      <td>0.684922</td>\n",
       "      <td>0.630754</td>\n",
       "      <td>0.584733</td>\n",
       "      <td>0.545436</td>\n",
       "      <td>0.511312</td>\n",
       "      <td>0.318638</td>\n",
       "      <td>0.235018</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Uncovered Set</th>\n",
       "      <td>0.912176</td>\n",
       "      <td>0.824687</td>\n",
       "      <td>0.748802</td>\n",
       "      <td>0.684922</td>\n",
       "      <td>0.630754</td>\n",
       "      <td>0.584733</td>\n",
       "      <td>0.545436</td>\n",
       "      <td>0.511312</td>\n",
       "      <td>0.318638</td>\n",
       "      <td>0.235018</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "num_cands            3         4         5         6         7         8   \\\n",
       "vm                                                                          \n",
       "Copeland       0.912176  0.824687  0.748802  0.684922  0.630754  0.584733   \n",
       "GETCHA         0.912176  0.824687  0.748802  0.684922  0.630754  0.584733   \n",
       "Split Cycle    0.912176  0.824687  0.748802  0.684922  0.630754  0.584733   \n",
       "Uncovered Set  0.912176  0.824687  0.748802  0.684922  0.630754  0.584733   \n",
       "\n",
       "num_cands            9         10        20        30  \n",
       "vm                                                     \n",
       "Copeland       0.545436  0.511312  0.318638  0.235018  \n",
       "GETCHA         0.545436  0.511312  0.318638  0.235018  \n",
       "Split Cycle    0.545436  0.511312  0.318638  0.235018  \n",
       "Uncovered Set  0.545436  0.511312  0.318638  0.235018  "
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"\\n Proportion of Profiles with a Condorcet Winner\\n\")\n",
    "df_table = df.pivot(index=\"vm\", columns=\"num_cands\", values=\"perc_condorcet_winner\")\n",
    "df_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "625490ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "all_num_cands = [\n",
    "        3,\n",
    "        4,\n",
    "        5,\n",
    "        6,\n",
    "        7,\n",
    "        8,\n",
    "        9, \n",
    "        10,\n",
    "        20,\n",
    "        30\n",
    "    ]\n",
    "\n",
    "vms = [\n",
    "    split_cycle, \n",
    "    copeland, \n",
    "    uc_gill,\n",
    "    getcha\n",
    "]\n",
    "num_cpus = 10\n",
    "num_trials = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "16d25ef9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def record_ws_data(vms, num_cand, t): \n",
    "    np.random.seed(current_process().pid)\n",
    "    mg = generate_edge_ordered_tournament_infinite_limit(num_cand)\n",
    "    winning_sets = {vm.name: vm(mg) for vm in vms}\n",
    "    return {\n",
    "        \"has_cw\": mg.condorcet_winner() is not None,\n",
    "        \"winning_set_sizes\": {vm.name: len(winning_sets[vm.name]) for vm in vms}\n",
    "        }\n",
    "\n",
    "def find_irresoluteness_data_inf_voters(\n",
    "    vms, \n",
    "    num_trials = 10, \n",
    "    all_num_cands = [\n",
    "        3,\n",
    "        4,\n",
    "        5,\n",
    "        6,\n",
    "        7,\n",
    "        8,\n",
    "        9, \n",
    "        10,\n",
    "        20,\n",
    "        30\n",
    "    ],\n",
    "    num_cpus = 10\n",
    "):\n",
    "    data_for_df = {\n",
    "        \"num_cands\": list(), \n",
    "        \"num_margin_graphs\": list(),\n",
    "        \"vm\": list(),\n",
    "        \"perc_mult_winners\": list(),\n",
    "        \"avg_ws_size\": list(),\n",
    "        \"perc_condorcet_winner\": list()\n",
    "    }\n",
    "    \n",
    "    \n",
    "    for num_cands in tqdm(all_num_cands): \n",
    "        print(num_cands)\n",
    "        \n",
    "        get_ws_data= partial(record_ws_data,\n",
    "                             vms,\n",
    "                             num_cands)\n",
    "\n",
    "        pool = Pool(num_cpus) # set to cpus when you can use all the processors\n",
    "        total_ws_data = pool.map(get_ws_data, range(num_trials))\n",
    "        \n",
    "        for vm in vms: \n",
    "            data = [d[\"winning_set_sizes\"][vm.name] for d in total_ws_data]\n",
    "            data_for_df[\"num_cands\"].append(num_cands)\n",
    "            data_for_df[\"num_margin_graphs\"].append(len(data))\n",
    "            data_for_df[\"vm\"].append(vm.name)\n",
    "            data_for_df[\"perc_mult_winners\"].append(sum([d > 1 \n",
    "                                                         for d in data]) / len(data) \n",
    "                                                    if len(data) > 0 else np.nan)\n",
    "            data_for_df[\"avg_ws_size\"].append(np.average([d for d in data]))\n",
    "            data_for_df[\"perc_condorcet_winner\"].append(sum([d[\"has_cw\"]  for d in total_ws_data]) / len(total_ws_data))\n",
    "            \n",
    "        df = pd.DataFrame(data_for_df)\n",
    "        df.to_csv(f\"./irresoluteness_inf_voters.csv\",index=False)\n",
    "            \n",
    "    \n",
    "    print(\"done.\")\n",
    "    return df"
   ]
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "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.11.6"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  },
  "vscode": {
   "interpreter": {
    "hash": "5c7b89af1651d0b8571dde13640ecdccf7d5a6204171d6ab33e7c296e100e08a"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}