easss2021-fairdiv.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fair Division of Indivisible Goods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a notebook accompanying the EASSS-2021 on Fair Allocation of Indivisible Goods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Preliminaries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from problem import Problem\n",
    "import fairness_measures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create the problem corresponding to the instance of (Herreiner and Puppe, 2007).  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1 = Problem(3,4,'empty', centralized=False)\n",
    "p1.setUtilities(\n",
    "[{'r0':5,'r1':47,'r2':45,'r3':3},\\\n",
    "{'r0':45,'r1':5,'r2':48,'r3':2},\\\n",
    "{'r0':23,'r1':25,'r2':32,'r3':20}]\n",
    ")\n",
    "print (p1)\n",
    "print (p1.printAllocation())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1.setAllocation([[0,0,1,0],[1,0,0,0],[0,1,0,1]])\n",
    "print(\"Allocation A:\\n\",p1.printAllocation())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1.setAllocation(([[0,1,0,0],[1,0,0,0],[0,0,1,1]]))\n",
    "print(\"Allocation B:\\n\", p1.printAllocation())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1.setAllocation(([[0,1,0,0],[0,0,1,0],[1,0,0,1]]))\n",
    "print(\"Allocation C:\\n\", p1.printAllocation())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1.setAllocation(([[0,1,0,0],[1,0,1,0],[0,0,0,1]]))\n",
    "print(\"Allocation D:\\n\", p1.printAllocation())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1.setAllocation(([[1,0,0,0],[0,1,0,1],[0,0,1,0]]))\n",
    "print(\"Allocation E:\\n\", p1.printAllocation())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here the problem corresponding to our second instance. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p2 = Problem(2,5,'empty', centralized=False)\n",
    "p2.setUtilities(\n",
    "[{'r0':6,'r1':6,'r2':6,'r3':0,'r4':0},\\\n",
    "{'r0':5,'r1':5,'r2':3,'r3':3,'r4':2}]\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Fairness notions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can check different fairness measures on a specific allocation. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p2.setAllocation([[1,1,1,0,0],[0,0,0,1,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"PROP:\", fairness_measures.isProportional(p2))\n",
    "em2= fairness_measures.envyMatrix(p2)\n",
    "print(\"EF:\", fairness_measures.isEnvyFree(em2))\n",
    "print(\"ESW:\", fairness_measures.egalitarianSW(p2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the allocation E on our first problem. We can output the envy matrix. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "em1 = fairness_measures.envyMatrix(p1)\n",
    "print(em1)\n",
    "print(\"There are \", fairness_measures.nbEnviousAgents(em1), \" envious agents\")\n",
    "print(\"The maximum envy among two agents is \", fairness_measures.maxEnvy(em1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"PROP:\", fairness_measures.isProportional(p1))\n",
    "print(\"ESW:\", fairness_measures.egalitarianSW(p1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. How likely is it to find an EF allocations?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How does the likelihood of EF evolve depending on the number of goods? The question is adressed by Dickerson et al. in their paper: \n",
    "* The computational Rise and Fall of Fairness, AAAI-2014\n",
    "\n",
    "For facilitating the run of several problems with varying or similar parameters, the module simulations provides a few functions. Each instance is solved via MIP. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import simulations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": [
    "## 4. What are the fairest picking sequences?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import protocols"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us play with picking sequences. Which sequences are the fairest on average, assuming some way to draw agents' preferences?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2 agents, 6 goods"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "simulations.simulationPickingSequences(1000,3,6,[1,2,2,1,2,1],'borda',verbose=False) # "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "simulations.simulationPickingSequences(1000,3,6,[1,2,1,2,2,1],'borda',verbose=False) # "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3 agents and 5 goods"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "simulations.simulationPickingSequences(1000,4,5,[1,1,1,2,3],'borda',verbose=False) # to start with a bad sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3 agents and 8 goods"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "simulations.simulationPickingSequences(1000,4,8,[1,2,3,1,2,3,1,2],'borda',verbose=False) # to start with a round robin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Last edited: 2021-07-20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}