{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Manipulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.604899Z",
     "start_time": "2023-09-28T09:20:15.017893Z"
    }
   },
   "outputs": [],
   "source": [
    "import svvamp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a population of 9 voters with preferences over 5 candidates, using the Spheroid model (which extends Impartial Culture to utilities):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.621345Z",
     "start_time": "2023-09-28T09:20:16.604899Z"
    }
   },
   "outputs": [],
   "source": [
    "random_profile = svvamp.GeneratorProfileSpheroid(n_v=9, n_c=5)\n",
    "profile = random_profile()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define a voting rule (Instant Runoff Voting) and load the profile:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.637439Z",
     "start_time": "2023-09-28T09:20:16.621345Z"
    }
   },
   "outputs": [],
   "source": [
    "rule = svvamp.RuleIRV()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ask whether the voting rule meets the Condorcet criterion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.653344Z",
     "start_time": "2023-09-28T09:20:16.637439Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.meets_condorcet_c_rk"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-12T07:25:11.854673Z",
     "start_time": "2021-07-12T07:25:11.837718Z"
    }
   },
   "source": [
    "Load the profile:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.669339Z",
     "start_time": "2023-09-28T09:20:16.653344Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<svvamp.rules.rule_irv.RuleIRV at 0x2899517e520>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule(profile)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Coalitional Manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a definition of this notion, cf the *Reference* section (`Rule.is_cm_`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Decide coalitional manipulation (CM):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.701406Z",
     "start_time": "2023-09-28T09:20:16.669339Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "nan"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.is_cm_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each voting system, SVVAMP uses by default its most precise algorithm running in polynomial time. For IRV, the decision problem is NP-complete, so this polynomial algorithm is not exact. For that reason, is_cm_ can be a boolean (whether the election is manipulable or not), or the conventional value `nan` meaning that the algorithm was not able to decide."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`log_CM_` is a string representing the options used to compute CM:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.717404Z",
     "start_time": "2023-09-28T09:20:16.701406Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cm_option = fast, fast_algo = c_minus_max, icm_option = exact, tm_option = exact'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.log_cm_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Check the possible options:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.733407Z",
     "start_time": "2023-09-28T09:20:16.717404Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'iia_subset_maximum_size': {'allowed': <function svvamp.utils.type_checker.is_number(value)>,\n",
       "  'default': 2},\n",
       " 'im_option': {'allowed': ['lazy', 'exact'], 'default': 'lazy'},\n",
       " 'tm_option': {'allowed': ['exact'], 'default': 'exact'},\n",
       " 'um_option': {'allowed': ['fast', 'exact'], 'default': 'fast'},\n",
       " 'icm_option': {'allowed': ['exact'], 'default': 'exact'},\n",
       " 'cm_option': {'allowed': ['fast', 'slow', 'exact'], 'default': 'fast'},\n",
       " 'fast_algo': {'allowed': ['c_minus_max', 'minus_max', 'hardest_first'],\n",
       "  'default': 'c_minus_max'}}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.options_parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main option is `cm_option`. Change it and compute CM again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.757411Z",
     "start_time": "2023-09-28T09:20:16.733407Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.cm_option = 'exact'\n",
    "rule.is_cm_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, the return value is necessarily a Boolean."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You could have set the option as soon as you defined the rule with the following syntax:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.765827Z",
     "start_time": "2023-09-28T09:20:16.757411Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<svvamp.rules.rule_irv.RuleIRV at 0x289b815e310>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule = svvamp.RuleIRV(cm_option='exact')\n",
    "rule(profile)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or, as a one-liner:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.782007Z",
     "start_time": "2023-09-28T09:20:16.765827Z"
    }
   },
   "outputs": [],
   "source": [
    "rule = svvamp.RuleIRV(cm_option='exact')(profile)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get more details about CM:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.797982Z",
     "start_time": "2023-09-28T09:20:16.782007Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0., 0., 0., 0., 0.])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.candidates_cm_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, SVVAMP returns an array of boolean indicating which candidates can benefit from CM."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SVVAMP is clever enough:\n",
    "\n",
    "1. Not to do obviously useless computation,\n",
    "2. Not to do the same computation twice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other Notions of Coalitional Manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ignorant-Coalition Manipulation (cf *Reference* section, `Rule.is_icm_`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.814021Z",
     "start_time": "2023-09-28T09:20:16.797982Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.is_icm_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.830086Z",
     "start_time": "2023-09-28T09:20:16.814021Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0., 0., 0., 0., 0.])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.candidates_icm_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Trivial Manipulation (cf *Reference* section, `Rule.is_tm_`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.839181Z",
     "start_time": "2023-09-28T09:20:16.830086Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.is_tm_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.854352Z",
     "start_time": "2023-09-28T09:20:16.839759Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0., 0., 0., 0., 0.])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.candidates_tm_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unison Manipulation (cf *Reference* section, `Rule.is_um_`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.870355Z",
     "start_time": "2023-09-28T09:20:16.854352Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.is_um_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.886366Z",
     "start_time": "2023-09-28T09:20:16.870355Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0., 0., 0., 0., 0.])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.candidates_um_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Individual Manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a definition of this notion, cf the *Reference* section (`Rule.is_im_`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Decide Individual Manipulation (IM):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.902286Z",
     "start_time": "2023-09-28T09:20:16.886366Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.im_option = 'exact'\n",
    "rule.is_im_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More details about IM:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.918534Z",
     "start_time": "2023-09-28T09:20:16.903420Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0.]])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.v_im_for_c_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each voter *v* and candidate *c*, `v_im_for_c_[v, c]` indicates whether voter *v* can manipulate in favor of *c*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Independence of Irrelevant Alternatives"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a definition of this notion, cf the *Reference* section (`Rule.is_iia_`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Modify the option in order to compute IIA with an exact (non-polynomial) algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.934544Z",
     "start_time": "2023-09-28T09:20:16.918534Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "rule.iia_subset_maximum_size = np.inf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Decide IIA:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.950918Z",
     "start_time": "2023-09-28T09:20:16.934544Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.is_iia_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More details about IIA:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.967001Z",
     "start_time": "2023-09-28T09:20:16.950918Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "nan"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.example_subset_iia_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-09-28T09:20:16.982935Z",
     "start_time": "2023-09-28T09:20:16.967001Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "nan"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rule.example_winner_iia_"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}