fairDivisionIndivisibleItems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fair Division of Indivisible Goods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a Jupyter Notebook coming along with the chapter \n",
    "* Chapter 12 (Handbook of Computational Social Choice)\n",
    "\n",
    "This notebook was used as part of the course of :\n",
    "* The COST Summer School Lecture on Fair Division of Indivisible Items (San Sebastian, July 2016)\n",
    "* COCOMA: Master ANDROIDE course at Sorbonne Université, 2016-2022\n",
    "\n",
    "This version: 10-01-2022"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Defining MARA problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By importing the module `problem`, we can define fair division problems, by specifying a number of agents, a number of resources, and a type of \"culture\" to draw the preferences from. \n",
    "\n",
    "You can either:\n",
    "* define a **centralized** MARA problem (all the resources are initially held by agent 0, who plays in this case the role of the auctioneer -- and counts as an agent)\n",
    "* define a **decentralized** MARA problem (resources are initially randomly allocated)\n",
    "\n",
    "You can also select the method to generate utilities: \n",
    "* **uniform**: utilities for each resource is drawn uniformly at random from 1 to 100\n",
    "* **normalized**: utilities are normalized in [0,1]\n",
    "* **Borda** utilities (worst resource valued 1, and so on, best one m)\n",
    "* **empty**: leaves utilites undefined. You can later use p.setUtilities() to set utilities as you wish for a problem p. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from problem import Problem\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "agent 1{'r0': 3, 'r1': 1, 'r2': 4, 'r3': 2}\n",
      "agent 2{'r0': 1, 'r1': 4, 'r2': 2, 'r3': 3}\n",
      "\n"
     ]
    }
   ],
   "source": [
    "p1 = Problem(3,4,'borda',centralized=True)\n",
    "print(p1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Printing the allocation allows to see which agent holds which resource, and the current utility of each agent. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "auctioneer            ['r0', 'r1', 'r2', 'r3']\t\n",
      "agent  1                                 []\t 0\n",
      "agent  2                                 []\t 0\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(p1.printAllocation())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is also possible to set the allocation by hand, by using the setAllocation method. The allocation is specified as a boolean array. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1.setAllocation([[0,0,0,0],[1,1,0,0],[0,0,1,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "auctioneer                                  []\t\n",
      "agent  1                       ['r0', 'r1']\t 4\n",
      "agent  2                       ['r2', 'r3']\t 5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(p1.printAllocation())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A problem also handles an (undirected) **visibility graph** among agents. Note that in the centalized case, agent 0 is isolated from the rest (his utility is irrelevant), while all the other agents are by default connected. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: [], 1: [2], 2: [1]}\n"
     ]
    }
   ],
   "source": [
    "print (p1.visibility_graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1.setVisibilityGraph({0:[],1:[],2:[]})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No one sees anyone now..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example of the course"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "agent 1{'r0': 1, 'r1': 2, 'r2': 5, 'r3': 3, 'r4': 7, 'r5': 2}\n",
      "agent 2{'r0': 2, 'r1': 6, 'r2': 8, 'r3': 1, 'r4': 1, 'r5': 2}\n",
      "agent 3{'r0': 5, 'r1': 4, 'r2': 4, 'r3': 3, 'r4': 2, 'r5': 2}\n",
      "\n",
      "auctioneer ['r0', 'r1', 'r2', 'r3', 'r4', 'r5']\t\n",
      "agent  1                                 []\t 0\n",
      "agent  2                                 []\t 0\n",
      "agent  3                                 []\t 0\n",
      "\n"
     ]
    }
   ],
   "source": [
    "p3 = Problem(4,6,'empty', centralized=True)\n",
    "p3.setUtilities(\n",
    "[{'r0':0,'r1':0,'r2':0,'r3':0,'r4':0,'r5':0},\\\n",
    "{'r0':1,'r1':2,'r2':5,'r3':3,'r4':7,'r5':2},\\\n",
    "{'r0':2,'r1':6,'r2':8,'r3':1,'r4':1,'r5':2},\\\n",
    "{'r0':5,'r1':4,'r2':4,'r3':3,'r4':2,'r5':2}]\n",
    ")\n",
    "print (p3)\n",
    "print (p3.printAllocation())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Fairness measures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The module `fairness_measures` provides a number of fairness measures for a given allocation: \n",
    "* proportionality\n",
    "* egalitarian social welfare\n",
    "* various notions of envy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "import fairness_measures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "agent 0{'r0': 0.084, 'r1': 0.19, 'r2': 0.315, 'r3': 0.059, 'r4': 0.286, 'r5': 0.066}\n",
      "agent 1{'r0': 0.009, 'r1': 0.003, 'r2': 0.296, 'r3': 0.163, 'r4': 0.239, 'r5': 0.29}\n",
      "agent 2{'r0': 0.166, 'r1': 0.041, 'r2': 0.094, 'r3': 0.294, 'r4': 0.206, 'r5': 0.2}\n",
      "\n"
     ]
    }
   ],
   "source": [
    "p2 = Problem(3,6,'normalized',centralized=False)\n",
    "print(p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n",
      "agent  0                 ['r0', 'r3', 'r5']\t0.20900000000000002\n",
      "agent  1                             ['r1']\t0.003\n",
      "agent  2                       ['r2', 'r4']\t0.3\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(p2.printAllocation())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can check various fairness properties..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "print(fairness_measures.isProportional(p2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.003\n"
     ]
    }
   ],
   "source": [
    "print(fairness_measures.egalitarianSW(p2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... and build the envy matrix from which several measures can be obtained. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.    0.    0.392]\n",
      " [0.459 0.    0.532]\n",
      " [0.36  0.    0.   ]]\n",
      "There are  3  envious agents\n",
      "The maximum envy among two agents is  0.5319999999999999\n"
     ]
    }
   ],
   "source": [
    "em2 = fairness_measures.envyMatrix(p2)\n",
    "print(em2)\n",
    "print(\"There are \", fairness_measures.nbEnviousAgents(em2), \" envious agents\")\n",
    "print(\"The maximum envy among two agents is \", fairness_measures.maxEnvy(em2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "print(fairness_measures.isEnvyFree(em2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "em1 = fairness_measures.envyMatrix(p1)\n",
    "print(fairness_measures.isEnvyFree(em1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "p1.setVisibilityGraph({0:[],1:[2],2:[1]})\n",
    "em1 = fairness_measures.envyMatrix(p1)\n",
    "print(fairness_measures.isEnvyFree(em1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create an instance involving 3 agents and 4 resources, with the following  utilities for the ressources : \n",
    "* agent 0: 6, 6, 1, 7\n",
    "* agent 1: 1, 3, 9, 7\n",
    "* agent 2: 8, 0, 4, 8\n",
    "\n",
    "Find allocations which satisfies : \n",
    "* proportionality\n",
    "* envy-freeness\n",
    "* maximizes egalitarian social welfare\n",
    "* maximizes utilitarian social welfare\n",
    "* maximizes the Nash product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 2\n",
    "\n",
    "There are a few missing notions though. Code functions which returns:\n",
    "* whether the allocation is envy-free up to **one** or **any** good\n",
    "* wether the allocation is proportional up to **one** or **any** good\n",
    "Test whether you can find a counter-example to the fact that EFX does not imply PROPX. \n",
    "\n",
    "Another missing notion is Competitive Equilibrium with equal income. Code functions which: \n",
    "* for a problem, given an allocation and a price vector, returns whether this allocation is CEEI\n",
    "* for a problem, given a price vector, checks whether there exists an allocation in CEEI\n",
    "* for a a problem, checks whether there exists a pair of price vector and allocation in CEEI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Solving via MIP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By importing `mipsolving` we get access to functions allowing to optimally solve the problems via MIP formulations (see course). \n",
    "The program uses the `Pulp` libray for linear programming. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "import mipsolving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Status: Optimal\n",
      "envy_bound\n",
      "0.0\n",
      "agent  1  gets resource r4\n",
      "agent  1  gets resource r5\n",
      "agent  2  gets resource r1\n",
      "agent  2  gets resource r2\n",
      "agent  3  gets resource r0\n",
      "agent  3  gets resource r3\n",
      "the final max envy is  0.0\n"
     ]
    }
   ],
   "source": [
    "e3 = mipsolving.envyminimizingLP(p3,verbose=True)\n",
    "print(\"the final max envy is \",e3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Note that this has not modified the initial problem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "agent  1  gets resource r1\n",
      "agent  1  gets resource r2\n",
      "agent  1  gets resource r5\n",
      "agent  2  gets resource r0\n",
      "agent  2  gets resource r3\n",
      "agent  2  gets resource r4\n",
      "0.589\n"
     ]
    }
   ],
   "source": [
    "print(mipsolving.assignmentLP(p2,verbose=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. How likely is it to get an envy-free allocation? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For facilitating the run of several problems with varying or similar parameters, the module simulations provides a few functions. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "import simulations\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us illustrate this on a specific question, adressed by Dickerson et al. in their paper: \n",
    "* The computational Rise and Fall of Fairness, AAAI-2014"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Experiments completed!\n"
     ]
    }
   ],
   "source": [
    "tested_resources = list(range(5,10)) # from 5 to 10 resources\n",
    "tested_agents = [5] # only 5 agents\n",
    "max_envy,ratio_ef = simulations.simulationOpt(50,tested_agents,tested_resources,'normalized')\n",
    "#print (max_envy,ratio_ef)\n",
    "print(\"Experiments completed!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA3wAAAEpCAYAAADIyCBPAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deZgcVb3/8fc3e0gIa1CUIEQ2AS+LLCIgIJtsQSDK4gKCclFAWRTxqhBQlE1FFFFEQLyyJiwBgqAoXPAHSFDWsIU9IAQIW0JCtvP749SQTqcn0zPpmZrpeb+ep5+Zrj5d/e2uqu7+9DlVFSklJEmSJEnNp0/ZBUiSJEmSOoeBT5IkSZKalIFPkiRJkpqUgU+SJEmSmpSBT5IkSZKalIFPkiRJkpqUgU89SmRPR0SKiDXKrkeqFhGvRsSYTpz/ThFxVI3pF0XExM563BqP95GIuD0iZhTb42pd9didISKGRMRlEfFa8XwOKrumShGxZUT8KyJmRUSnnE+pq9ehrhQRz0TEmWXX0dW68/OOiD4RcU5EvFxsc2NaabfQehkRm3Xme6zUjPqVXYDUTlsAqxX/7wf8qLxSpFLsBIwGzqqa/kNgcBfWcQawLDAKmAH8pwsfuzN8DdgD+BLwAvBkueUs4rfAVGBn4N1OeoyuXoe60l7Aa2UXoYXsDXwdOASYBExppV31erkZcCIwpjOLk5qJgU89zf7kL5cPFf93WeCLiMEppZld9XjqPRqxbqWUujqgrAOMTynd0sWP21nWAR5LKY1rrUFEBDAwpTSr68p6zzrAeSml25ZkJhHRF+ibUppdfVtXrUNlvI4ppX931WP1Fg1431oHeD2ldMHiGpXw3iY1HYd0qscovqh8FhgPXACsGxH/VXH76sWwkF2r7xcRL0XEDyumrR8RN0TE28Xlyoh4f8Xt2xbz2jkixkfEdOBXxW3HRsQ9EfFmMRTluurhpcXQ0x9GxNSIeCsiLoiI/aqHvkXEoIg4PSKej4h3I+L+6vprvA6rFfPZLyIuLOY/JSK+UNx+XES8GBGvRMRpEdGn4r7rFMPWno+IdyLi4Yg4qqrNOcV9V6qYtk/xmDu2UdtWEXFbMe/XIuJ3EbF0xe0HFfP5aET8pRgO+GhE7F3R5qRiefWpmvfuxX3XiIgzIuKp4otjZZsvR8TsiFixlfqGRMSvIuKxosani+c7rKpdiohvRsSPi9diatFuYFW7TxbLbFZE3BsRn1jc61M1/2Mi4qyIeAV4sJi+W/G6tKw3d0XEThX3GwMcC3yomEeKiIuK2xYZjhcRG0bELcVzfT0i/hQR76ujvlbv17L+AR8Gji5quHUx8+oTEcdHxORiHX88Ig6sanNrRIyNiAOKdm9FxI0RsUpFm6cj4vQa8x8beWhpv2K9P7FGm9si4qrF1PgMuZdho5bXtZg+JvIQ3a0i4h5gFvk9iIhYPiJ+G/k9YFZE/L+I2Ly9z70tUbwXAX2BX1Qt875Fjc8V8384Ig6ouv9FETExIj4TEQ8Xz2HzRR6IRdehqGN7rWi7V0T8MyJmRt72J0TEhxr0OtbznrtVsR68VVzui4jPVty+0NDGitdlx4h4oHhud0TEelXzXS7ye+aMYv36TkScWawzrapn/rHgvXz3NpZDy+u3eTHPmcW8Vo+IlSLimoiYHhGPRMSnWqnnB5HfV6dH3p6Xqbq9nuVQ832rlcdbKiLOLh5zVrH8Kt/LbiX33C0XC97LVlvca1n8fxDwy4p6Fnr/ifo/27ePiGuL5fJE5KHyfSN/trwaES9ExDFVdawXEX+OiGnF/R6JiMNbew2kbiWl5MVLj7gAOwKJPIRseWA28JOqNncDf6ia9qnifusX19cA3gRuAT4D7EMeTnIPEEWbbYv7TCF/KH0K+ERx28+BA4s2o4AJwMvAMhWPeTQwDziZPATvHOC5Yp6rVbS7njxM62tFu/OBucCGi3kdVivm8yzw4+J1ubR4vJ8CY4FPA98r2u1Xcd/tgZPIQ9e2BY4qXovvVrQZAkwGri6ur1TUeG4by2dL8lCzy4FdgS+Sh8aNrWhzUFHTg8CRxXO+rliWqxRtPlK02a5q/hcDE4v/1y7abFvV5jZg3GJqHA6cSx4SuQ3wBeAR4KaqdqlYXheRh9B9u1gux1W0+QC5t/nvwO7AocDTwDvAmDZeq0QeAnl5sax2LaYfAXyjeMwdgZ8Vy3XL4vZVgD8V9/14cflwcdtFLa9PxXN9A7iTvJ5/gbw+PwAMaOM1avV+wMDicf9T1PJxYN3FzO8cYDpwHLADcFrxnHavaHMr8Dzw/4A9ycO1XwYmVLQ5DXiGYhstpg0tXu8jius/KZZBZZuRwHxgj8XUuBFwQ7EufBz4eDF9TDH/J4H/BrYr1r2BwL+Ap8hDQD8NXAu8Dby/Pc+9jve9YUVNCTizapmfAswBvl+sM+cV7favuP9FwKvA48Wy3JFiW6vxWNXr0EG0sb0W7b5YtLuU/N4yijzkeJMGvY6Lfc8tXqM3gD8Uz28n8g8jX62YxzPAmVXPdSpwH7BvMd/HgYer1p9ryUNBv0Lezm8hr6vPtLHc2pw/C97Ld29jObS8fvcDnydvl88BdxT1fKt4zn8tal2q6nm/QH5v3IP8PvUGcGVFm3qXQ833rVae/5+K+x8J7AJcRV5XtypuX5f8efcGC97LBra1XpLfn84samm537rFbe35bJ9Mfl9ved3eIn82/KaY9ouWx6io40ny+8Su5M/SrwPH17ste/FS5qX0Arx4qfdC7tV7neLLavHGW/3l7ujiDX9gxbTfAg9XXP8j8BgVX3qBNclfxHYrrrd8KPy8jZr6kvcteBv4UsW0/wDnVLWdQEXgKz4wErBNVbv/q/wwrvGYqxX3u7Bi2rDiw/QJ8nCtlun/BC5vZT5BHtb9P8BTVbdtWbweXwTGFR90Q9t4LW4H/l41rTpsH1RcP7iizQrkMHVYxbT7gd9UXB9YLNdvVUy7g4pwz4Iv9u35Mt2veK4JWLViegL+r6rtNcBdFddPZ9EvV58v7jumjcdNwL/baNOnqO8m4IKK6WdS48smi35JPJX8ZWpYxbTNqAoENeZT1/2o+gLdyrzWKJbJgVXTLwbuqbh+a7F8l6uYdlTxmIOL6xux6Bew/Yv19H1pwXa80I8F5B9dXgL6tVHrQq9fMW1MMb89q6YfQg49a1atS08CZ7TnubdjXU0Uwba4vjz5B4cTq9pNIA9NrXxeicX8iLSYdegg2thei/X0BeCqxcy3w69jjXnVes/dpJj/0oupYaH1tXiuc6se+zPFfNYprq9fXP9sRZvB5AC9yDZY47Vsa/6rUX/gW+izghw2EnBCxbR1i2m7VD3vaVS8f5Pfp+YDH2nPcqCO962i3UeoWveL9eQhKn5cK57Xqx1YL48AUo127flsP7GiTcvr9reqel8CTiuur1i0+Wh7tlsvXrrLxSGd6hEiD6Xbi9zr1LLvyaXkD8yPVzS9Alia/OsjEdGPvGP4ZRVtdgCuBuZHHgbWjxwcnyF/cah0Q41aPh55eNNr5A/0d8g9DWsVTUYA7ycPPa1UfX0H8gfKP1rqKGq5pUYdtby371RK6S3gFeC2lNK8ijaTgQ9W1D4o8pDJyeTeuDnkXoLVi8dumd8/yL1LvyN/STkopTS9tUIiYinyAXWuqHoudxSP8bGqu9xc8VivkX8JX6Xi9suBfSpq2oW8XK+oaPP7os3Q4vpB5F/9/9xanUWtX4yIf0cepjunqBEWLL9FaixMqqpxM+AvKaV3Kqa1Omywhlrr1ioR8YeIeIG8bs0h/9pcXVs9NgNuLtYNAFJK/ySv51t1wv1q2Z78xe/qGuv4hpGHabe4J6X0esX1ScXfDxY1/JvcQ7JvRZt9gVtTSi8XbZ4g/2ByELy3r9iXgD+mlOYW0/pV1dKWBNxYNW0H4F7g6ar53MaCbbc9z70j1geWAq6smn45sFZUDMkGXkgp3bcEj7W47XVtcm/3hW3Mo6OvYz3vuU+Se1IviYg9I2LZOp/XM8U606JlnWt5bi01XPfek8j7rP21QfNvj9nkH9VaTC7+/q3GtA+ysL9UvX9fRf7Bb9Piel3LobDI+1YNmxbzf2/dTCnNL6639z2kPdrz2V657/Eir2VR71MseC2nkXt2fxMR+1ZtX1K3Z+BTT7EL+YiAEyJi2eID/VZyaNm/pVFK6QXyF/iWL4Xbk3+Zqwx8KwLfIX+ZrryMJIe1Si9XXomIVclffoI8NGlL8ofbVGBQ0axlf4FXquZVfX3Fom11HWNq1FHLG1XXZ7cybVDF9dPIw3/OIw9L2ZQFB74ZtPBduZTcs/ZQSul2Fm858i/vv2bh5/Iu0J9Fn09bdV5Gfn1a9kfZF7gzpfRcRZsryF+oP1fxxf7ili/2tUTEXuQeljvJ+xB9nPxDAiz6/Nuq8f3k5f6e4stgq8G4SvW61Yf8o8AngBPIw942JX9Jrq6tHitXP0bF4y7fCferZUXyevEmC68XF5F7EFauaFvr9YaFn/vlwGcjG0b+Yeeyqvv9Hhgded/RTwEfYuEwUr29teX1tOgBTlYkrzvV8/oyC9b19jz3jmi5f/Wyarm+XI1pHbW4bWGF4m9bR2nt0OtYz3tu8UPBTuT3miuAV4r9uEZ24HnBwu/lb6dFDy5T/V7e0fm3x9tFCKme13uPUfH6Vs+/tfeplnWonvW5RT3r0srA9Kofw1ruu1RU7QvdQO35bK/1urW6nhev/U7kH2kvAF6KvM/oRg1+DlKn8Cid6ilaQl31r9mQv/AfXdGzdTlwakQMJgeFf1f9yjqN/Cvg+TXm9WrV9VR1/dPkX9X3TCnNgPd6ESu/CL9U/B1edd/q69PIQ6E+U6OOzvJZ4JcppfcOfhERu1U3Kp7TeeR9d9aLiENTSuctZr5vUAxlJA8pq/Zie4pMKT1V7KS/b0TcQd735H+q2syIiMvIvTnPkr/YX9TGrD8L3J1S+nrLhIjYpj21VXiJvH/je4p1bmjt5ouoXrfWIA9b3CWl9F4vZTHPjvhPdX2F95F/zW/0/WqZRu6R2ZIczqtNrTFtcS4DfkDuJVidHKiqe1WvBM4mL+vtyMt7UsXtm9I+1csJ8vOaSN73ttq7FW0a+dyrtQSslVj4dAMtB+WZVjGt1nNolJbHbivAdvR1rOc9l5TSncCni+1lB/IIhUtYeARIe70ELB0Rg6pCX/V7eUe1zHNA1fT2/rDSltbep1rWoXqWQ4t61qX/AEMjYqmq0Pc+4J2UUmedVqQ9n+3tllJ6lDyqpD+wNfkH1BsiYpWqMC51OwY+dXvFkL3dyT1O1aFjI/IH+3YsGGZzJXmH672Ky0+q7nMLeTjUvSml9n4RGkz+8lbZi/Q5Ft6Wnid/UdiTvP9Vi1E16jiW/Evoo+2so6MGU/EBXgwr269Gu/8hD9X6L/LBCs6MiJtTSs/UmmkRvu4C1k4pndygWi8jH3jmb0XdtcL+74G7yEHzrpTSI23Mc6HnX/h8B+u7Bzi46kvNIkcvbIeWYFe5fD5EDgwPVLSr7mlszd3A1yJi6ZTS28X8NiUPg76jE+5Xy9/IoWyZlNJf2nnfRaSUJkXEQ+QfclYnD1V7rarNzIi4FDicfNj3Y6pub8SJxW8h/9r/XEqpteDW0Odew0PkoY2fJe+n2OJzwOMppXp7oZbUY+Qfrg6kYuhjnep5Het5z31P0Xt1XUSsD3y3nfVUa1lXRlEMJy/C0o7kfQiX1FRyD9RHWiYUn3dbkH/EapQdI2JoxbDOvcnBreX51bMc2uOeYv6jySMqWoZXj6b97yG1zC7mWR3El+SzvW4ppTnA3yKi5UeFZVn4Bxap2zHwqSfYk/wL7y9SSndX3hAR/yCHgv0pAl9KaWrkwzSfSX4jvoKFjSEfzOSGiLiA/MvfB8kf4hellG5dTC0tX+IujIjfA+uRh0hWDg+ZFxFnAGdEPnT1P8hfGD5aNGn5JfAv5ED4l4g4jXz0tmHAhsCglNKSflmp5S/A4cU+fNPIX4qrTzWwEfmof0emlJ6OiJPIgfuCiNh+MR+kxwG3RMR88pFC3wZWBXYDvpdSerydtV5BPrn3GeQDqCwyZCyldHfkQ81vRR7u1Za/AOdExPfIwablaGsdcRb59bu++OD/APkLZkfPS/Uo+WiYP42IH5D3WTyJ/GW6ut37Ih+e/CHyQQ+eqTG/n5F/sb+pWL+Gkg/I8iD5QDyt6ej9FpFSeiwifgNcFvmUChPJYXU9YK2U0lfaM7/C5cA3gWWAr7bS5vfAYeRlUT3ksxEuLuZ/a+RD/T9FHtq4GfBSSunn9T73YjleCKze2g8qtaSUpkXEWcD3I2JuMf+9yev0/ou9cwOllOZHxHHAnyLiT+Qf5hJ5OO2lbQTsNl9H6njPLUYpHEw+sNJz5Pfz/2bh/ds68tweiojrgHOLIcIvkX9AeIfavbbtnf/8iLiWfHqTZ8nP6Vg6/h7Smpnkz7szyD2xZ5D3h2/p+a5nOdQtpfRI8aPLr4qh15PJ2+o61O5FbK+WH0i/GRF/A95KKT3Gkn22L1bkU0CdSX7/eYo8ZPo7wP0pJcOeuj334VNPsD/wRHXYg/d+absC2Ltqv4DLyB9sd1V/iSqCx8fJH9rnkfeROoncszKZxUgpPUjer2Fz8ikVDiD/wv5mVdOfk0+Z8HXyl+TliuuQD/9MEZz2Ju8PcBQ5/P2W/OtuI34FreVI8o7/5xSP+xAVPaARMYB8aPO/p5R+W9Q5m/zr/Vbko6PVlFK6A/gkebjTH8m/9h9H7vFs9z5EKaWWw/SvzOK/tF9D/V/sf0s+dcU3yUMBP0Rehu1W7C+6K3m/kXHkZf0F8nrVkfm9S14f5pID8w/Jy6b6RNtXkIeunk7+JX1MK/N7hdzzPYv8Jfwc8rLfsca+VEt8v8U4vHguXyIP972I/CPA/3VgXrBg/8755GW/iCJktBw5snrbXGJFr8J25B8QTiLvY/YL8hEB/1nRtJ7nvhS5x6IjdZ5AXke+Rn4/+iTwhZRSZ4TcVqWULiEfAn8d8rp7cfH/YnsZ63kd63zPnUwOmT8u5nE6+eBNBzfg6R1E/jHxbPJ75m3FvN9azH3a4wjyj4K/Jm9rl7KEQbWGy8inj/k9+YeqG8lH5gTatT63x1fJnyU/IJ/i4UPko5E24rPtdnJo/Sb5h7uWz6oOf7bX4SXy59j3ivn+mnwal+qRO1K31HJeEkmdLCLOJ39p/lDZtTSTiPgn+TD0Xyy7FnUPEbEuucd8h5TSLW21L1NE/AGYn1L6ctm1qG3F/oMPkfcNPbDseiSpHg7plDpBsf/IvuQeqvnko4x+mTwERA0QEZuQh41tSu5JUS8XESuQ9z39IflLeaN7SjrDFuTeMXVDEfFZ8nDtB8lD7r9K7vn6Upl1SVJ7GPikzjGDBUMgh5B3wP8OeTihGuMe8j4v300p3VN2MeoW9iAPu3sU+GJnHrihUVJKHTnHorrODPKPdWuQ9yV8ENgj5XNTSlKP4JBOSZIkSWpSpfXwrbjiimm11VYr6+ElSZIkqWnce++9r6aUFjlXaGmBb7XVVmPixEacDkmSJEmSerfiFC+L8LQMkiRJktSkDHySJEmS1KQMfJIkSZLUpAx8kiRJktSkDHySJEmS1KQMfJIkSZLUpNoMfBFxQURMjYiHWrk9IuLsiJgcEQ9ExMaNL1OSJEmS1F719PBdBHx6MbfvAqxZXA4Fzl3ysiRJkiRJS6rNwJdS+j9g2mKa7AlcnLK7gGUjYuVGFShJkiRJZZs3D+bOLbuK9uvXgHl8EHi+4vqUYtp/GjBvSZIkSU1q/nyYPbvzLnPmNG5e8+fD6afDt79d9qvWPo0IfFFjWqrZMOJQ8rBPVl111QY8tCRJkqRKlSGqkYGnMwLXvHmd8xr06wcDBtR3GTas/rZbbtk59XamRgS+KcCIiuurAC/WaphSOg84D2CTTTapGQolSZKk7mb+/I6FpzICV1eGqP79awejpZeuP0QtyaXW4/fvD308F8F7GhH4xgNHRMRlwObAmyklh3NKkiRpsVLq/EDUqPl31r5bffvWH26GDq0/cHVGsDJE9UxtBr6IuBTYFlgxIqYAJwL9AVJKvwEmALsCk4F3gC93VrGSJEnqWg88ANddB7NmNT5wzZnTOTVHwMCB9QWZpZaCZZdtbA9Te+7bt2/nvAZSizYDX0pp/zZuT8DhDatIkiRJpXvkETjxRLjyyny9tRBVK/AMHgzLLFPekD5DlLRAI4Z0SpIkqUlMngwnnQSXXJJ7v37wAzj6aFhuubIrk9QRBj5JkiTx7LPwwx/CRRflXrJvfSsffn7FFcuuTNKSMPBJkiT1Yi+8AKecAuefnw/KceSRcPzx8L73lV2ZpEYw8EmSJPVCL78Mp54K556bTznwla/A//wPrLJK2ZVJaiQDnyRJUi/y2mtwxhnwy1/Cu+/CgQfm/fRWW63syiR1BgOfJElSL/DGG/Czn8FZZ8H06XDAAfkonGuuWXZlkjqTgU+SJKmJvf02nH02nHlmDn2jR8OYMbDeemVXJqkrGPgkSZKa0DvvwK9/DaedBq++CqNG5dMtbLhh2ZVJ6kp9yi5AkiRJjTNrVu7R+/CH82kVPvYxuPtuuPZaw57UG9nDJ0mS1ARmz4YLL4Qf/QimTIFtt4Urr4Sttiq7MkllsodPkiSpB5s7N58sfe214bDDYNVV4ZZb4O9/N+xJMvBJkiT1SPPmwSWX5IOvfPnLsMIKMGEC3HEHfOpTZVcnqbsw8EmSJPUg8+fDuHGwwQbw+c/DwIFwzTVwzz2wyy4QUXaFkroTA58kSVIPkBJcf30+CMvo0bmH7/LL4b77YM89DXqSajPwSZIkdWMpwc03wxZbwB575PPqXXwxPPQQfO5z0Mdvc5IWw7cISZKkbuq222CbbWDnneE//4Hzz4dHHoEvfhH69i27Okk9gYFPkiSpm7nzTthhh3xqhSefhHPOgccfh0MOgf79y65OUk9i4JMkSeom7r0XdtsNPvEJePBB+NnPYPJk+PrX88FZJKm9PPG6JElSyR58EE48Ea6+GpZfHk49FY44AoYMKbsyST2dgU+SJKkkjz4KY8bAFVfA0kvDSSfBUUfBsGFlVyapWRj4JEmSutiTT8LJJ8P//i8MHgzf/S4ce2zu3ZOkRjLwSZIkdZHnnoMf/QguvBD69YNjjoHjjoPhw8uuTFKzMvBJkiR1shdfhB//GH73u3z9a1/LvXorr1xuXZKan4FPkiSpk0ydCqedBr/+NcydCwcfDN//PowYUXZlknoLA58kSVKDTZsGZ54JZ58NM2fmE6WfcAKMHFl2ZZJ6GwOfJElSg7z5Jvz85/ny9tuw7775KJxrr112ZZJ6KwOfJEnSEpo+HX75SzjjDHj9ddh773yKhfXXL7sySb2dgU+SJKmDZs6Ec8/NJ0p/5RXYbbd8uoWNNy67MknK+pRdgCRJUk/z7rvwq1/Bhz+cz5+3wQZw551w/fWGPUndiz18kiRJdZozBy66CH74Q3j+edh6a7jsMvjkJ8uuTJJqs4dPkiSpDfPmwcUXwzrrwKGHwgc+ADffDLfdZtiT1L0Z+CRJkloxf37uwVtvPTjwQFhmmTxs8847YccdIaLsCiVp8Qx8kiRJVVKCq6+GDTeE/feHfv1g3Di49958YBaDnqSewsAnSZJUSAkmTIBNN82nVnj3XbjkErj//nzdoCeppzHwSZKkXi8luOUW2HLL3IM3bVo+OMvDD+cevr59y65QkjrGwCdJknq122+H7baDHXbIR9787W/hscfyPnv9PJ65pB6ursAXEZ+OiMciYnJEHF/j9lUj4u8R8e+IeCAidm18qZIkSY3zz3/Czjvno2w+9hicfTY88UQ+Cmf//mVXJ0mN0Wbgi4i+wDnALsC6wP4RsW5Vs+8DV6SUNgL2A37d6EIlSZIa4b77YNQo2Hxz+Ne/4Mwz4ckn4cgjYdCgsquTpMaqp4dvM2BySumplNJs4DJgz6o2CRhW/L8M8GLjSpQkSVpyDz8Mo0fDRhvlYZynnAJPPQXHHgtLLVV2dZLUOeoZmf5B4PmK61OAzavajAFujogjgSHADg2pTpIkaQk9/jicdBJceikMHQonnABHHw3LLlt2ZZLU+erp4at1AOJUdX1/4KKU0irArsAfI2KReUfEoRExMSImvvLKK+2vVpIkqU5PPw0HHwzrrgvXXAPf+U6edtJJhj1JvUc9gW8KMKLi+iosOmTzEOAKgJTSncAgYMXqGaWUzkspbZJS2mT48OEdq1iSJGkxpkyBww6DtdbK59D7xjfy0M2f/ARWWKHs6iSpa9UT+O4B1oyI1SNiAPmgLOOr2jwHbA8QER8hBz678CRJUpd56SX45jdhjTXgggvy0TaffBJ+9jN43/vKrk6SytHmPnwppbkRcQRwE9AXuCCl9HBEnAxMTCmNB44FfhcRR5OHex6UUqoe9ilJktRwr74Kp58Ov/oVzJ4NBx0EP/gBfOhDZVcmSeWr63SiKaUJwISqaSdU/D8J2LKxpUmSJLXu9dfhpz+FX/wCZsyAL3whH5BljTXKrkySuo+6Ap8kSVJ38dZbOeT99Kfw5pvwuc/BmDHwkY+UXZkkdT8GPkmS1CPMmAHnnAOnnQbTpsGee+Yjbm6wQdmVSVL3ZeCTJEnd2qxZ8Jvf5KNsTp0Ku+wCJ58Mm2xSdmWS1P3Vc5ROSZKkLjd7Npx7bt4n7+ijYf314R//gAkTDHuSVC8DnyRJ6lbmzs2nVVhrLfj612G11eBvf4NbboFPfKLs6iSpZzHwSZKkbmHePPjf/80HXznkEFhpJfjzn+H222G77cquTpJ6JgOfJEkq1fz5cOWV8NGPwhe/CEOGwLXXwt13w847Q0TZFUpSz2XgkyRJpUgJxo+HjTfOp1aAHPz+9S8YNcqgJ0mNYOCTJEldKqU8VHPzzfOpFWbMyEM5H3wQRo+GPn47kaSG8S1VkiR1mb//HbbeOp9aYepU+P3v4ZFH4POfh759y65OkpqPgU+SJHW6f/wDPvWpfHnmmXy6hccfh4MPhn6eFViSOo2BT5IkdZqJE3Nv3lZbwaRJcNZZMHkyHHYYDBhQdnWS1FkteKsAAB32SURBVPwMfJIkqeEeeAA+8xnYdFO45x447TR48kn45jdh0KCyq5Ok3sNBFJIkqWEeeQROPDEfbXOZZeCHP4RvfAOGDSu7MknqnQx8kiRpiU2eDCedBJdcAkstBd//PhxzDCy3XNmVSVLvZuCTJEkd9uyzuRfvoovyPnnHHgvHHQcrrlh2ZZIkMPBJkqQOeOEFOOUUOP/8fIL0ww+H734X3v/+siuTJFUy8EmSpLq9/DKcemo+rcK8efCVr8D3vgerrFJ2ZZKkWgx8kiSpTa+9BmecAb/8JcyaBQceCD/4Aay+etmVSZIWx8AnSZJa9cYb8LOf5fPnTZ8O+++fj8K51lplVyZJqoeBT5IkLeLtt+Hss+HMM3Po22effBTO9dYruzJJUnsY+CRJ0nveeQd+/et8ovRXX4U99shBb6ONyq5MktQRfcouQJIklW/WrNyj9+EPw7e/DRtvDHfdBePHG/YkqSezh0+SpF5s9my48EL40Y9gyhTYZhu44grYeuuyK5MkNYI9fJIk9UJz5+aTpa+9Nhx2GIwYAX/9K/z974Y9SWomBj5JknqRefPgkkvywVe+/GVYfnm44Qb4xz9g++3zSdQlSc3DwCdJUi8wfz6MGwcbbACf/zwMGABXXw0TJ8Kuuxr0JKlZGfgkSWpiKcH118PHPgajR+ehnJddBvffD5/5jEFPkpqdgU+SpCaUEvzlL7DFFvnUCm+9BX/4Azz0EOy7L/TxG4Ak9Qq+3UuS1GT+7//y0TZ32glefBF+9zt49FH40pegn8fnlqRexcAnSVKTuOsu2HHHHPYmT4Zf/QqeeAK+8hXo37/s6iRJZTDwSZLUw/3rX7D77nn45v33w09/Ck8+CYcfDgMHll2dJKlMDuyQJKmHevBBOPHEfLTN5ZaDn/wEjjgChg4tuzJJUndh4JMkqYd57DEYMwYuvxyWXjr/f9RRsMwyZVcmSepuDHySJPUQTz0FJ58Mf/wjDB4Mxx8P3/pWPnm6JEm1GPgkSermnnsOfvQjuPDCfJTNo4+G446DlVYquzJJUndn4JMkqZv6z3/gxz+G887L59U77DD47nfhAx8ouzJJUk9R11E6I+LTEfFYREyOiONbafO5iJgUEQ9HxCWNLVOSpN7jlVfyUM2RI+Hcc+HAA/NpFn75S8OeJKl92uzhi4i+wDnAjsAU4J6IGJ9SmlTRZk3gu8CWKaXXI8JBJpIktdO0aXDmmXD22TBzJnzhC3DCCfDhD5ddmSSpp6pnSOdmwOSU0lMAEXEZsCcwqaLNV4FzUkqvA6SUpja6UEmSmtWbb8JZZ8HPfgZvvQX77puPvLnOOmVXJknq6eoZ0vlB4PmK61OKaZXWAtaKiH9ExF0R8elaM4qIQyNiYkRMfOWVVzpWsSRJTWL6dDj1VFh99Rzwtt8eHngALrvMsCdJaox6Al/UmJaqrvcD1gS2BfYHzo+IZRe5U0rnpZQ2SSltMnz48PbWKklSU5g5M/fmjRyZD8KyxRYwcSJcdRV89KNlVydJaib1BL4pwIiK66sAL9Zoc21KaU5K6WngMXIAlCRJhXffhXPOyfvkHXss/Nd/wf/7f3DDDfCxj5VdnSSpGdUT+O4B1oyI1SNiALAfML6qzTXAdgARsSJ5iOdTjSxUkqSeas4cOP98WGstOOIIWGMNuPVW+Otfc++eJEmdpc3Al1KaCxwB3AQ8AlyRUno4Ik6OiFFFs5uA1yJiEvB34Nsppdc6q2hJknqCefPg4ovz/nhf/Sq8//1w001w222wzTZlVydJ6g3qOvF6SmkCMKFq2gkV/yfgmOIiSVKvNn8+XHllPhDLo4/ChhvCddfBbrtB1NozXpKkTlLXidclSVLbUoJrrskBb7/9oG9fGDsW7r0Xdt/dsCdJ6noGPkmSllBKMGECbLop7LUXzJoFf/oT3H8/7LMP9PHTVpJUEj+CJEnqoJTglltgyy3zcM3XXoMLL4RJk+CAA3IPnyRJZTLwSZLUAbffDtttBzvsAM8/D7/5DTz2GBx0EPSraw95SZI6n4FPkqR2+Oc/Yeed4ZOfzAdk+cUv4Ikn4L//GwYMKLs6SZIWZuCTJKkO990Ho0bB5pvng7CccQY89RR84xswaFDZ1UmSVJuDTiRJWoyHH4YTT4Rx42DZZeFHP8ohb+mly65MkqS2GfgkSaoyYwb8+c9w6aVw1VUwdCj84AdwzDE59EmS1FMY+CRJAt5+G66/PvfkTZgAM2fC8OFw3HHw7W/DCiuUXaEkSe1n4JMk9VpvvAHjx+eQd9NN8O678P73w8EH5/Pnbb21R9yUJPVsfoxJknqVV1+Fa6+FsWPzOfTmzIERI+BrX4PRo2GLLTxRuiSpeRj4JElN7+WX4eqrc8i79VaYNw9GjoSjjsohb9NNIaLsKiVJajwDnySpKb3wQj7gytix+STpKcFaa8F3vpND3oYbGvIkSc3PwCdJahrPPJP3xxs3Du68M09bf/18WoV99oH11jPkSZJ6FwOfJKlHe+KJHPDGjs0nRAfYaCM45ZQc8tZeu9z6JEkqk4FPktTjTJq0IOQ98ECettlmcPrpOeSNHFlufZIkdRcGPklSt5dSDnZjx+ag98gjeWjmllvCz38Oe+8Nq65adpWSJHU/Bj5JUreUUh6i2RLyJk/Op0vYZhs44gjYay9YeeWyq5QkqXsz8EmSuo358+GuuxYceOXZZ/OJzz/1KTjuONhzT1hppbKrlCSp5zDwSZJKNW8e3HHHgpD34oswYADsuCOMGQOjRsHyy5ddpSRJPZOBT5LU5ebOzSdAHzs2nxB96lQYNAh22SUfdGX33WGZZcquUpKkns/AJ0nqErNnwy235JB37bXw2mswZAjstlsOebvuCkOHll2lJEnNxcAnSeo0s2bBzTfnkDd+PLz5JgwbBnvsAaNHw847w+DBZVcpSVLzMvBJkhpqxgy48ca8P97118P06bDccvnUCfvsAzvsAAMHll2lJEm9g4FPkrTE3noLbrghh7wJE2DmTBg+HA44IIe87baD/v3LrlKSpN7HwCdJ6pDXX4frrsvDNW++Gd59N58X7+CD83DNrbbKp1SQJEnl8aNYklS3V1/NB1wZOzYfgGXOHBgxAr72tRzyttginxxdkiR1DwY+SdJivfRSPnXCuHH5VArz5sHIkXDUUTnkbbopRJRdpSRJqsXAJ0laxJQpcNVVOeTdfjukBGuvDccfn/fJ23BDQ54kST2BgU+SBMAzz+SAN3Ys3HVXnrb++nDiibknb911DXmSJPU0Bj5J6sWeeCIHvHHj4N5787SNN4ZTTsk9eWuvXW59kiRpyRj4JKmXmTRpQch74IE8bfPN4fTTc8gbObLc+iRJUuMY+CSpyaWUg93Ysfny6KN5aOaWW8JZZ+UToo8YUXaVkiSpMxj4JKkJpQQTJy7YJ+/JJ/PpErbZBo48EvbaK58zT5IkNTcDnyQ1ifnz88FWxo3Ll2efzSc+/9Sn4Dvfgc98BoYPL7tKSZLUlQx8ktSDzZsHd9yRe/GuugpefBEGDICddoIxY2DUKFh++bKrlCRJZakr8EXEp4FfAH2B81NKp7bSbjRwJbBpSmliw6qUJL1nzhy47bYc8q6+GqZOhUGDYJdd8ukTdtsNllmm7ColSVJ30Gbgi4i+wDnAjsAU4J6IGJ9SmlTVbmngG8DdnVGoJPVms2fDX/+ah2pecw1MmwZDhuRwN3p0DntDh5ZdpSRJ6m7q6eHbDJicUnoKICIuA/YEJlW1+yFwOvCthlYoSb3UzJlw88055I0fD2++CcOG5WGa++wDO+8MgweXXaUkSerO6gl8HwSer7g+Bdi8skFEbASMSCldHxEGPknqoBkz4MYb83DNG26A6dNhueXyqRNGj4btt4eBA8uuUpIk9RT1BL6oMS29d2NEH+DnwEFtzijiUOBQgFVXXbW+CiWpyb31Vg53Y8fmsDdzZj6a5gEH5JC37bbQv3/ZVUqSpJ6onsA3Bag8Je8qwIsV15cG1gdujQiA9wPjI2JU9YFbUkrnAecBbLLJJglJ6qVefx2uuy6HvJtuyvvorbwyHHxwDnlbbw19+5ZdpSRJ6unqCXz3AGtGxOrAC8B+wAEtN6aU3gRWbLkeEbcC3/IonZK0sFdfzQdcGTcuH4Bl7lwYMQIOPzzvk7fFFvnk6JIkSY3SZuBLKc2NiCOAm8inZbggpfRwRJwMTEwpje/sIiWpp3rppXzqhHHj4NZb83nzRo6EY47JIW/TTSFqDZyXJElqgLrOw5dSmgBMqJp2Qittt13ysiSp55oyJZ8EfezYfFL0lGDtteH44/NwzQ02MORJkqSuUVfgkyQt3tNP5168cePgrrvytI9+FE48MYe8ddc15EmSpK5n4JOkDnr88QUh795787SNN4ZTTsnDNddeu9z6JEmSDHyS1A6TJuWhmmPHwoMP5mmbbw5nnJHPlTdyZLn1SZIkVTLwSdJipAT335978caOhUcfzUMzt9wSzjorh7wRI9qejyRJUhkMfJJUJSWYODEHvHHj4Mkn8+kStt0WjjwS9tornzNPkiSpuzPwSRIwf34+2EpLyHvuOejXD7bfHr7zHfjMZ2D48LKrlCRJah8Dn6Rea968fNqEsWPzaRRefBEGDICddoKTT4Y99oDlly+7SkmSpI4z8EnqVebMySdAHzcunxB96lQYNAh23TUfWXP33WHYsLKrlCRJagwDn6SmN3s2/PWvOeRdcw1MmwZDhuRwt88+sMsuMHRo2VVKkiQ1noFPUlOaORNuvjkP17zuOnjzzdxzN2pUPhH6TjvB4MFlVylJktS5DHySmsaMGXDjjTnk3XADTJ+e98Hbe+8c8rbfHgYOLLtKSZKkrmPgk9SjvfUWXH99Hq554425Z2/4cDjggBzytt0W+vcvu0pJkqRyGPgk9Tivvw7jx+eQd9NNeR+9lVeGQw7J++RtvTX07Vt2lZIkSeUz8EnqEV59NR9wZexYuOUWmDsXRoyAww/PPXkf/3g+ObokSZIWMPBJ6rZeeimfOmHsWLjttnzevJEj4ZhjcsjbZBOIKLtKSZKk7svAJ6lbef75fBL0cePySdFTgrXXhuOPzyFvgw0MeZIkSfUy8Ekq3dNP54A3dizcfXee9tGPwpgxeZ+8ddc15EmSJHWEgU9SKR5/fEHI+9e/8rSNN4Yf/ziHvLXWKrc+SZKkZmDgk9QlUoJJkxaEvAcfzNM33xzOOCOHvNVXL7dGSZKkZmPgk9RpUoL7788Bb9w4ePTRPDRzq63grLPyCdFHjCi7SkmSpOZl4JPUUCnBxIkLQt6TT+bTJWy7LRx5JOy1Vz5nniRJkjqfgU/SEps/H+66a0HIe+456NcPtt8+H11zzz1h+PCyq5QkSep9DHySOmTePLj99hzwrroKXnwRBgyAnXeGk0+GUaNgueXKrlKSJKl3M/BJqtucOXDrrbkn75prYOpUGDwYdtklH3Rl991h2LCyq5QkSVILA5+kxXr3Xbjllhzyrr0Wpk2DIUNyuBs9Ooe9IUPKrlKSJEm1GPgkMXcuzJgB06cv+PvMM3D11TB+PLz1Vu65GzUqh7yddso9e5IkSereDHxSD5JS7nGbPn3RS0tQ68hl1qzaj7f88jng7bNPPgDLwIFd+3wlSZK0ZAx8UieZP7/+ENaesDZvXv01DB4MQ4cufFl66XxahOrpQ4fmoZkt/6+4Imy2GfTv33mvkSRJkjqXgU8CZs/uWM/Y4oLaO+/U//h9+uQgVhm4hg6F970PPvzh2uGsrcA2ZAj07dt5r5kkSZK6PwOfepT582HmzI4PXWwtqM2ZU38NgwbVDlsrrbRoYKv3MnAgRHTe6yZJkqTeycCnTjNnTuP2MaucR70iaoer4cNh9dXb7iFr7fZ+bjWSJEnqIfzqKlJafK9ZR4Pa7Nn11zBwYO3AtcIK7espq7z/4MH2mkmSJKl3M/D1MJWHz2/kgUBSqr+GWkFr+eVh1VU7NqRxyBAPDCJJkiR1BgNfJ1nc4fOXJKy1dvj8Wvr1ywcCqQ5Yq6xSXw9ZrcvgwfkAI5IkSZK6PwNflWeegddfb0xQa8/h81uCVmXgGjYMPvCBjg9pHDCg014mSZIkST2Aga/KZz8LEye2fnvfvrV7zVqCWUeGNC61lL1mkiRJkhqvrsAXEZ8GfgH0Bc5PKZ1adfsxwFeAucArwMEppWcbXGuX+PGP8/nTWgtnAwZ4IBBJkiRJPUObgS8i+gLnADsCU4B7ImJ8SmlSRbN/A5uklN6JiK8BpwP7dkbBnW3HHcuuQJIkSZIao56BhJsBk1NKT6WUZgOXAXtWNkgp/T2l9E5x9S5glcaWKUmSJElqr3oC3weB5yuuTymmteYQ4MYlKUqSJEmStOTq2Yev1h5rNc/aFhFfADYBtmnl9kOBQwFWXXXVOkuUJEmSJHVEPT18U4ARFddXAV6sbhQROwDfA0allN6tNaOU0nkppU1SSpsMHz68I/VKkiRJkupUT+C7B1gzIlaPiAHAfsD4ygYRsRHwW3LYm9r4MiVJkiRJ7dVm4EspzQWOAG4CHgGuSCk9HBEnR8SootkZwFDgyoi4LyLGtzI7SZIkSVIXqes8fCmlCcCEqmknVPy/Q4PrkiRJkiQtoXqGdEqSJEmSeiADnyRJkiQ1KQOfJEmSJDUpA58kSZIkNSkDnyRJkiQ1KQOfJEmSJDUpA58kSZIkNSkDnyRJkiQ1KQOfJEmSJDUpA58kSZIkNSkDnyRJkiQ1KQOfJEmSJDUpA58kSZIkNSkDnyRJkiQ1KQOfJEmSJDUpA58kSZIkNSkDnyRJkiQ1KQOfJEmSJDUpA58kSZIkNSkDnyRJkiQ1KQOfJEmSJDUpA58kSZIkNSkDnyRJkiQ1KQOfJEmSJDUpA58kSZIkNSkDnyRJkiQ1qX5lF9DtPPggzJ0LQ4YsfOnfv+zKJEmSJKldDHzVDjkE7rln0en9+8NSSy0aBDt6qZzX4MEQ0fXPVZIkSVJTM/BVO+ssmDoVZsyo7/LGG/DCCwtPe+ed9j1mxJKHycXdv2/fznmtJEmSJHVrBr5qn/jEks9j/nyYOXNB+Ks3PNa6vPbawkFyxow85LQ9Bg5sbICsvAwYYO+kJEmS1E0Z+DpDnz4LAlFnmD17yUJkS3h85RV45pmFp8+a1b5a+vZtXHisvgwenF9LSZIkSR1i4OuJBgzIl+WWa/y8581rf69krfZvvw0vvbTo9JTaV0+tsNiofSn7ufpLkiSpufmNVwvr2xeWXjpfGi2l3IPY3vBY6/Lii4tOmzOnffUMGNDYAFkZSAcNcqirJEmSSmfgU9eJyMM0Bw+GFVds/PznzOl4gKy8TJsGzz+/8LSZM9tXS58+jQmSrfVweiAeSZIk1cHAp+bRvz8su2y+NFrlgXiW9PLKK4sG0Xnz2lfPoEGNP5pr5YF4JEmS1BQMfFI9OvNAPCkt2YF4KsPjyy8vevu777avnn79Fu5J7MpLv35d/5iNvDiMV5IkdTMGPqlsEfnUGQMHwvLLN37+c+fWP7S1st077+Sex/ZeZs9e8P/cuR2bR+WlJ4koP3SWfWl0aDdES5K0ROoKfBHxaeAXQF/g/JTSqVW3DwQuBj4GvAbsm1J6prGlSuqQfv1g2LB86Ynmz1/y0NjTL5UhuhGX9h4tt0w9PUSX0Wu9uMfs08cQLUm9TJuBLyL6AucAOwJTgHsiYnxKaVJFs0OA11NKa0TEfsBpwL6dUbCkXqZPn3zp37/sSppHSh0Pi43ote0Ol94covv0af5g25WPaYCW1M3V08O3GTA5pfQUQERcBuwJVAa+PYExxf9jgV9FRKTUkz4BJamXiMhfXD0XZePUCtFlhOOyAvm77zZ2fvPnl71E69fZvdDdJdh2995ha+sYa2u/ddaBkSPLrqJd6vm0/yDwfMX1KcDmrbVJKc2NiDeBFYBXKxtFxKHAoQCrrrpqB0uWJKmbMUQ3VkptD+du9kDd0gvdqMeU1BinnQbHHVd2Fe1SzydTrXhd3XNXTxtSSucB5wFssskm9v5JkqRFVfaaqTHasz90rZDZnXtdu/OAMmvrmO5c2yqrlF1Bu9UT+KYAIyqurwK82EqbKRHRD1gGmNaQCiVJkrRk3B9a6rX61NHmHmDNiFg9IgYA+wHjq9qMBw4s/h8N/M399yRJkiSpXG328BX75B0B3AT0BS5IKT0cEScDE1NK44HfA3+MiMnknr39OrNoSZIkSVLb6tq7PKU0AZhQNe2Eiv9nAZ9tbGmSJEmSpCVRz5BOSZIkSVIPZOCTJEmSpCZl4JMkSZKkJmXgkyRJkqQmZeCTJEmSpCZl4JMkSZKkJhVlnR89Il4Bni3lwdu2IvBq2UX0ci6D8rkMugeXQ/lcBuVzGZTPZVA+l0H30J2Xw4dSSsOrJ5YW+LqziJiYUtqk7Dp6M5dB+VwG3YPLoXwug/K5DMrnMiify6B76InLwSGdkiRJktSkDHySJEmS1KQMfLWdV3YBchl0Ay6D7sHlUD6XQflcBuVzGZTPZdA99Ljl4D58kiRJktSk7OGTJEmSpCbVqwNfRDwTEQ9GxH0RMbHG7RERZ0fE5Ih4ICI2LqPOZlbHMtg2It4sbr8vIk4oo85mFhHLRsTYiHg0Ih6JiC2qbnc76GR1LAO3g04WEWtXvL73RcRbEXFUVRu3hU5U5zJwW+hkEXF0RDwcEQ9FxKURMajq9oERcXmxHdwdEauVU2nzqmMZHBQRr1RsB18pq9ZmFRHfLF7/h6vfh4rbe9TnQb+yC+gGtksptXYujV2ANYvL5sC5xV811uKWAcDtKaXdu6ya3ucXwJ9TSqMjYgCwVNXtbgedr61lAG4HnSql9BiwIUBE9AVeAK6uaua20InqXAbgttBpIuKDwDeAdVNKMyPiCmA/4KKKZocAr6eU1oiI/YDTgH27vNgmVecyALg8pXREV9fXG0TE+sBXgc2A2cCfI+KGlNITFc161OdBr+7hq8OewMUpuwtYNiJWLrsoqVEiYhjwSeD3ACml2SmlN6qauR10ojqXgbrW9sCTKaVnq6a7LXSd1paBOl8/YHBE9CP/+PRi1e17An8o/h8LbB8R0YX19QZtLQN1ro8Ad6WU3kkpzQVuA/aqatOjPg96e+BLwM0RcW9EHFrj9g8Cz1dcn1JMU+O0tQwAtoiI+yPixohYryuL6wVGAq8AF0bEvyPi/IgYUtXG7aBz1bMMwO2gK+0HXFpjuttC12ltGYDbQqdJKb0AnAk8B/wHeDOldHNVs/e2g+LL8JvACl1ZZzOrcxkA7FMMJRwbESO6tMjm9xDwyYhYISKWAnYFql/jHvV50NsD35YppY3J3bKHR8Qnq26v9YuVhzVtrLaWwb+AD6WUNgB+CVzT1QU2uX7AxsC5KaWNgBnA8VVt3A46Vz3LwO2gixRDakcBV9a6ucY0t4UGa2MZuC10oohYjtxzsTrwAWBIRHyhulmNu7odNEidy+A6YLWU0n8Bf2VBj6saIKX0CHmo8l+APwP3A3OrmvWo7aBXB76U0ovF36nk/QQ2q2oyhYUT/SrYrd5QbS2DlNJbKaXpxf8TgP4RsWKXF9q8pgBTUkp3F9fHksNHdRu3g87T5jJwO+hSuwD/Sim9XOM2t4Wu0eoycFvodDsAT6eUXkkpzQGuAj5R1ea97aAYcrgMMK1Lq2xubS6DlNJrKaV3i6u/Az7WxTU2vZTS71NKG6eUPklev5+oatKjPg96beCLiCERsXTL/8BO5C7cSuOBLxVH4vk4uVv9P11catOqZxlExPtb9g2IiM3I6+xrXV1rs0opvQQ8HxFrF5O2ByZVNXM76ET1LAO3gy61P60PJXRb6BqtLgO3hU73HPDxiFiqeJ23Bx6pajMeOLD4fzTwt+RJnRupzWVQta/YqOrbteQiYqXi76rA3iz6ntSjPg9681E63wdcXXxu9AMuSSn9OSIOA0gp/QaYQB63Oxl4B/hySbU2q3qWwWjgaxExF5gJ7OcHS8MdCfypGEb1FPBlt4Mu19YycDvoAsW+GjsC/10xzW2hC9WxDNwWOlFK6e6IGEseOjsX+DdwXkScDExMKY0nH2DqjxExmdzzsV9pBTehOpfBNyJiVHH7NOCgsuptYuMiYgVgDnB4Sun1nvx5EL5PSpIkSVJz6rVDOiVJkiSp2Rn4JEmSJKlJGfgkSZIkqUkZ+CRJkiSpSRn4JEmSJKlJGfgkSZIkqUkZ+CRJkiSpSRn4JEmSJKlJ/X9sKueIWi6K1AAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 900x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "from IPython.core.pylabtools import figsize\n",
    "import networkx as nx\n",
    "import pylab\n",
    "figsize(12.5, 4)\n",
    "p = np.linspace(tested_resources[0], tested_resources[0]+len(tested_resources)-1,len(tested_resources))\n",
    "#print(p)\n",
    "plt.plot(p, max_envy[0], color='red')\n",
    "plt.plot(p, ratio_ef[0], color = 'blue')\n",
    "legende = \"Average max envy and ratio of envy-free, for increasing number of items\"\n",
    "plt.suptitle(legende, y=1.02, fontsize=15)\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 3\n",
    "Play a little bit with these simulations and try to determine:\n",
    "* for 2 agents, how the max envy evolves, from which number of items\n",
    "you can be reasonably sure to get an envy-free allocation\n",
    "* same question for 5 agents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Envy-Freeness on Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Agents can only envy their neighbours in the visibility (Idea: you can't envy someone you don't see). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Augment the code of mipsolving so as to account for graph envy-freeness, ie. an envy is only considered among agents which are neighbours in the graph. Then, test how likely it is to get a graph-envy free allocation:\n",
    "* on a line of 10 agents, with Borda utilities,\n",
    "* on a star of 10 agents, with Borda utilities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}