{
 "metadata": {
  "name": "payforpredictions"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "# Solving the pay for prediction challenge\n",
      "\n",
      "This document is a collaboratively developed IPython Notebook to solve the [\"Pay for prediction\" challenge][PFPC].\n",
      "\n",
      "###### Hit Esc to see an overview of the pages\n",
      "\n",
      "[PFPC]: http://www.climatecentre.org/site/paying-for-predictions"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "## Outline\n",
      "\n",
      "- Overview of the challenge\n",
      "- The simulator\n",
      "- The solutions\n",
      "- Factoring the problem"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "### Overview\n",
      "\n",
      "[from the competition website]\n",
      "\n",
      "#### Strategy competition\n",
      "\n",
      "What is the best strategy to reduce the risk of disaster as a humanitarian worker? Red Cross Red Crescent workers must balance their time and resources between long-term programming such as hygiene promotion, preparing right before a disaster happens, and responding to disasters when they happen. Fortunately, there are many tools to help with this, including science-based forecasts that can help people anticipate a disaster. While forecasts can be confusing, making a strategy for how to act based on a forecast can help humanitarian workers best manage their time and resources.\n",
      " \n",
      "The Red Cross Red Crescent Climate Centre is launching a competition to find the best strategy for how to manage disaster risk in the game Paying for Predictions. This game demonstrates the many responsibilities of a humanitarian worker, from long-term preparedness to short-term anticipation of a disaster. In this global competition, we would like you to submit a strategy which you think will make a player win this game more often than other strategies.\n",
      "\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "#### How does this work?\n",
      "\n",
      "You submit your strategy by Thursday, February 28th, 2013.\n",
      "\n",
      "A computer programme will use your strategy as if you were a person playing this game against other people over and over again. After many games are played, the programme will show which strategy wins most often.\n",
      "\n",
      "We will announce the winners in March 2013. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "#### Competition rules\n",
      "\n",
      "[Origin of the rules](http://www.climatecentre.org/downloads/File/Games/Competition%20Rules.pdf)\n",
      "\n",
      "Game License: http://creativecommons.org/licenses/by-nc/3.0/\n",
      "\n",
      "The basic parameters of how the game will be simulated by computers for this competition:\n",
      "\n",
      "- 10 teams of 3 people are playing this game (30 people total)\n",
      "- Players are unable to communicate with each other, but they are able to see what other players \n",
      "on their team are doing. They are not able to see what players are doing who are not on their \n",
      "team.\n",
      "- There are 10 rounds in this game."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "#### Game setup\n",
      "\n",
      "Each player receives 10 beans (resources), and one \n",
      "six-sided die which represent the local rainfall of his/her area. \n",
      "Each team receives a cup and one six-sided die which represents \n",
      "the regional rainfall of their zone.\n",
      "\n",
      "#### WINNING\n",
      "\n",
      "- The individual WINNER is the person with the most beans.\n",
      "- The team WINNER is the team with fewest total  humanitarian crises. If there is a tie the team with most total beans combined is the team winner.\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "### Simulator\n",
      "\n",
      "The simulator is setup with some default strategies. These are for illustrative purposes."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "\n",
      "n_teams = 10\n",
      "n_persons_per_team = 3\n",
      "n_beans = 10\n",
      "n_rounds = 10\n",
      "n_die_change = 7\n",
      "target_rain = 10\n",
      "penalty = 4\n",
      "\n",
      "def initialize():\n",
      "    beans = n_beans * np.ones((n_teams, n_persons_per_team))\n",
      "    forecast_teams = np.ones((n_teams)) # receive regional forecast\n",
      "    drr_teams = np.ones((n_teams))  # have disaster risk reduction\n",
      "    return beans, forecast_teams, drr_teams"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def get_forecast_bids(beans):\n",
      "    \"\"\" Defines how each person or team will bid for regional forecast\n",
      "\n",
      "    Example\n",
      "    -------\n",
      "\n",
      "    return np.random.randint(0, np.max(beans) * .4, size=beans.shape)\n",
      "    \"\"\"\n",
      "    return np.ones(beans.shape)\n",
      "\n",
      "def get_drr_bids(beans):\n",
      "    \"\"\" Defines how each person or team will bid for disaster risk reduction\n",
      "\n",
      "    Example\n",
      "    -------\n",
      "\n",
      "    bids = np.zeros(beans.shape)\n",
      "    for i in range(beans.shape[0]):\n",
      "        for j in range(beans.shape[1]):\n",
      "            bids[i, j] = np.random.randint(0, beans[i, j] * .2)\n",
      "    \"\"\"\n",
      "    bids = np.ones(beans.shape)\n",
      "    return bids\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "##### Gameplay: Stage 1 perform bids"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "beans, forecast_teams, drr_teams = initialize()\n",
      "\n",
      "# perform forecast bids\n",
      "forecast_bids = get_forecast_bids(beans)\n",
      "forecast_team_bids = np.sum(forecast_bids, axis=1)\n",
      "sort_index = np.argsort(forecast_team_bids)\n",
      "forecast_teams[sort_index[:n_teams/2]] = 0\n",
      "\n",
      "# Winning teams pay their beans\n",
      "beans = beans - (forecast_teams[:, None] * forecast_bids)\n",
      "print beans.T\n",
      "print forecast_teams"
     ],
     "language": "python",
     "metadata": {
      "slideshow": {
       "slide_type": "-"
      }
     },
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[ 10.  10.  10.  10.  10.   9.   9.   9.   9.   9.]\n",
        " [ 10.  10.  10.  10.  10.   9.   9.   9.   9.   9.]\n",
        " [ 10.  10.  10.  10.  10.   9.   9.   9.   9.   9.]]\n",
        "[ 0.  0.  0.  0.  0.  1.  1.  1.  1.  1.]\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# perform drr bids\n",
      "drr_bids = get_drr_bids(beans)\n",
      "drr_team_bids = np.sum(drr_bids, axis=1)\n",
      "sort_index = np.argsort(drr_team_bids)\n",
      "drr_teams[sort_index[:-2]] = 0\n",
      "\n",
      "# Winning teams pay their beans\n",
      "beans = beans - (drr_teams[:, None] * drr_bids)\n",
      "print beans.T\n",
      "print forecast_teams\n",
      "print drr_teams"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[ 10.  10.  10.  10.  10.   9.   9.   9.   8.   8.]\n",
        " [ 10.  10.  10.  10.  10.   9.   9.   9.   8.   8.]\n",
        " [ 10.  10.  10.  10.  10.   9.   9.   9.   8.   8.]]\n",
        "[ 0.  0.  0.  0.  0.  1.  1.  1.  1.  1.]\n",
        "[ 0.  0.  0.  0.  0.  0.  0.  0.  1.  1.]\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "#### Round"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def get_insurance_payments(regional_predictions, drr_teams, beans, round_idx):\n",
      "    # determine the likelihood of a flood\n",
      "    likelihood = (7 - (target_rain - regional_predictions)) / 6\n",
      "    # if likelihood > .2 pay, or if you didn't have a prediction pay one bean\n",
      "    payments = ((likelihood > .2) + (regional_predictions < 1))[:, None] * np.ones(beans.shape)\n",
      "    return (payments * (beans > 0)).astype(int)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def generate_rainfall(n_sides):\n",
      "    regional_rainfall = np.random.randint(1, n_sides, size=(n_teams))\n",
      "    local_rainfall = np.random.randint(1, 7, size=(n_teams, n_persons_per_team))\n",
      "    total_rainfall = local_rainfall + regional_rainfall[:, None]\n",
      "    flooded = (total_rainfall >= target_rain).astype(np.int)\n",
      "    return regional_rainfall, flooded\n",
      "\n",
      "def adjust_beans(beans, payments, flooded, round_idx, drr_teams):\n",
      "    if round_idx < 3:\n",
      "        drr_penalty = 4\n",
      "    else:\n",
      "        drr_penalty = 2\n",
      "    penalized = np.maximum(flooded - payments, 0)\n",
      "    beans_to_remove = drr_penalty * penalized * (drr_teams[:, None] == 1) + penalty * penalized * (drr_teams[:, None] == 0)\n",
      "    already_in_crisis = beans * (beans < 0)\n",
      "    beans[already_in_crisis < 0] = 0\n",
      "    beans = beans - payments - beans_to_remove\n",
      "    beans_joining_crisis = beans < 0 \n",
      "    beans = beans * (beans > 0)\n",
      "    in_crisis = already_in_crisis - beans_joining_crisis\n",
      "    return beans + in_crisis"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "#### Simulate"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print beans.T\n",
      "for turn in range(n_rounds):\n",
      "    n_sides = 6\n",
      "    if turn == 6: # 7th round\n",
      "        n_sides = 8\n",
      "    regional_rainfall, flooded = generate_rainfall(n_sides=n_sides)\n",
      "    payments = get_insurance_payments(regional_rainfall * forecast_teams, drr_teams, beans, turn + 1)\n",
      "    beans = adjust_beans(beans.copy(), payments, flooded, turn + 1, drr_teams)\n",
      "    if turn % 2 == 0:\n",
      "        print turn + 1, flooded.T - payments.T\n",
      "print beans.T"
     ],
     "language": "python",
     "metadata": {
      "slideshow": {
       "slide_type": "-"
      }
     },
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[ 10.  10.  10.  10.  10.   9.   9.   9.   8.   8.]\n",
        " [ 10.  10.  10.  10.  10.   9.   9.   9.   8.   8.]\n",
        " [ 10.  10.  10.  10.  10.   9.   9.   9.   8.   8.]]\n",
        "1 [[-1 -1 -1  0  0  0  0  0  0  0]\n",
        " [-1 -1 -1 -1 -1  0 -1 -1  0  0]\n",
        " [-1 -1 -1 -1 -1  0 -1 -1  0  0]]\n",
        "3 [[-1 -1 -1  0 -1  0  0  0  0  0]\n",
        " [ 0  0 -1  0 -1 -1  0  0 -1  0]\n",
        " [ 0 -1 -1 -1  0 -1  0  0 -1  0]]\n",
        "5 [[-1 -1 -1 -1 -1 -1  0  0  0  0]\n",
        " [ 0 -1 -1  0 -1 -1  0  0  0  0]\n",
        " [-1 -1 -1 -1 -1 -1  0  0  0  0]]\n",
        "7 [[ 0 -1 -1 -1 -1  0 -1  0  0  0]\n",
        " [-1 -1 -1 -1 -1  0  0  0  1  0]\n",
        " [ 0 -1 -1 -1 -1  0 -1  0  0  0]]\n",
        "9 [[-1 -1 -1  0 -1 -1  0  0  0  0]\n",
        " [-1 -1 -1  0 -1 -1  0  0  0 -1]\n",
        " [-1 -1 -1 -1 -1 -1  0  0  0 -1]]\n",
        "[[ 0.  0.  0.  0.  0.  5.  6.  7.  3.  4.]\n",
        " [ 0.  0.  0.  0.  0.  5.  6.  7.  3.  4.]\n",
        " [ 0.  0.  0.  0.  0.  5.  6.  7.  5.  4.]]\n"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "### Solutions\n",
      "\n",
      "Example from challenge guidelines\n",
      "\n",
      "    # This is a complete example submission for the \"Paying for Predictions\" game.\n",
      "    # Blank lines or lines beginning with \"#\" are ignored.\n",
      "    # Bids:\n",
      "    Bid 1 for the forecast.\n",
      "    Bid 3 beans for DRR.\n",
      "    # Conditions:\n",
      "    If I won the forecast and the dice is less than 5 and the beans remaining are more than 7, then take \n",
      "    early action.\n",
      "    If I have forecast and the dice rolls more than the number of rounds remaining, then take early \n",
      "    action.\n",
      "    If I don't have DRR and the dice rolls more than 5 and the rounds played are more than 6, then take \n",
      "    early action.\n",
      "    Else, take no early action.\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Solution from the strategies chosen for the simulation\n",
      "\n",
      "    # This is a complete example submission for the \"Paying for Predictions\" game.\n",
      "    # Blank lines or lines beginning with \"#\" are ignored.\n",
      "    # Bids:\n",
      "    Bid 1 for the forecast.\n",
      "    Bid 1 beans for DRR.\n",
      "    # Conditions:\n",
      "    If I have forecast and the rolled dice is more than 4 then take early action.\n",
      "    If I don't have forecast then take early action.\n",
      "    By default take no action.\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "## Factoring the problem\n",
      "\n",
      "The problem can be factored into five independent strategies: one for each of the four possible bidding outcomes and one for placing the initial bid."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "### Strategy 1: winning no bids\n",
      "\n",
      "In each round, the only choice is whether to buy insurance for one bean.\n",
      "\n",
      "For rounds 1-6, the expected cost of no insurance is $4\\left(\\frac{7}{36}\\right) = \\frac{7}{9} < 1$, so we should never buy insurance.\n",
      "\n",
      "For rounds 7-10, the expected cost of no insurance is $4\\left(\\frac{15}{48}\\right) = \\frac{5}{4} > 1$, so we should always buy insurance.\n",
      "\n",
      "The expected final bean count (neglecting running out of beans) is $10-6\\left(\\frac{7}{9}\\right)-4 = \\frac{4}{3}$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "### Strategy 2: DRR only\n",
      "\n",
      "For rounds 1-2, DRR is not available, so strategy 1 applies.\n",
      "\n",
      "For rounds 3-6, the expected cost of no insurance is $2\\left(\\frac{7}{36}\\right) = \\frac{7}{18} < 1$, so we should never buy insurance.\n",
      "\n",
      "For rounds 7-10, the expected cost of no insurance is $2\\left(\\frac{15}{48}\\right) = \\frac{5}{8} < 1$, so we should never buy insurance.\n",
      "\n",
      "*I.e.*, the net strategy is to never buy insurance.\n",
      "\n",
      "The expected final bean count (neglecting running out of beans) is $10-2\\left(\\frac{7}{9}\\right)-4\\left(\\frac{7}{18}\\right)-4\\left(\\frac{5}{8}\\right) \\approx 4.39$.\n",
      "\n",
      "This suggests that DDR is worth slightly more than three beans."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "### Strategy 3: Forecast only\n",
      "\n",
      "Given a regional forecast $\\leq 4$, the expected cost of no insurance is $\\leq \\frac{2}{3}$, so we should never buy insurance for these cases.\n",
      "\n",
      "Given a regional forecast $\\geq 5$, the expected cost of no insurance is $\\geq \\frac{4}{3}$, so we should always buy insurance for these cases.\n",
      "\n",
      "The expected final bean count is: $10-6\\left(\\frac{1}{6}\\frac{2}{3}+\\frac{1}{3}\\right)-4\\left(\\frac{1}{8}\\frac{2}{3}+\\frac{1}{2}\\right) = 5$.\n",
      "\n",
      "This suggests that the forecast is worth slightly less than 4 beans."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "### Strategy 4: DRR and Forecast\n",
      "\n",
      "Again, rounds 1-2 match strategy 3.\n",
      "\n",
      "For the DRR rounds:\n",
      "\n",
      "* Given a regional forecast $\\leq 5$, the expected cost of no insurance is $\\leq \\frac{2}{3}$, so we should never buy insurance.\n",
      "* Given a regional forecast $\\geq 7$, the expected cost of no insurance is $\\geq \\frac{4}{3}$, so we should always buy insurance.\n",
      "* Given a regional forecast of 6, the expected cost of no insurance is 1, so it shouldn't matter if we buy insurance.  Since there is no way to aquire beans,\n",
      "  it is probably best to not buy insurance for this case.  This also implies that we should never buy insurance for rounds 3-6, independent of forecast.\n",
      "\n",
      "The expected final bean count is: $10 - 2\\left(\\frac{1}{6}\\frac{2}{3}+\\frac{1}{3}\\right)-4\\left(\\frac{1}{6}\\frac{1}{3}+\\frac{1}{6}\\frac{2}{3}+\\frac{1}{6}\\right)-4\\left(\\frac{1}{8}\\frac{1}{3}+\\frac{1}{8}\\frac{2}{3}+\\frac{3}{8}\\right) \\approx 5.77$\n",
      "\n",
      "This suggests that, given the forecast, DRR is worth less than one bean."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "### Strategy 5: Initial bid\n",
      "\n",
      "Because there is no tracking of opponents across games, there is no reason to change the opening bid between games (as there would be in, *e.g.*, the tit-for-tat strategy in the Prisoner's Dilemma).  Therefore, the initial bid strategy is a choice among the $11^2 = 121$ possible opening bids.  Although this is the only\n",
      "stage of the game with any interaction with the other players, I think that it is still not an interactive choice.  That is, independently for each of the two\n",
      "bids, it should always be optimal to bid the \"fair market value\" of the resource (*i.e.*, the difference in expected final beans with or without the resource).\n",
      "Winning the resource by overbidding will tend to put our final score below an optimal play without the resource.  Underbidding *may* be a reasonable strategy as\n",
      "losing the bidding is free.  I think that the influence of bids from teammates can be disregarded.\n",
      "\n",
      "From the expectation values above, neither resource should ever be worth more than three beans; so, the interesting space to explore has $4^2 = 16$ choices."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "subslide"
      }
     },
     "source": [
      "#### Solution\n",
      "\n",
      "    # This is a complete example submission for the \"Paying for Predictions\" game.\n",
      "    # Blank lines or lines beginning with \"#\" are ignored.\n",
      "    # Bids:\n",
      "    Bid 2 for the forecast.\n",
      "    Bid 2 beans for DRR.\n",
      "    # Conditions:\n",
      "    If I have neither DRR nor forecast and round greater than 6 then take early action.\n",
      "    If I have forecast and the rolled dice is more than 4 then take early action.\n",
      "    If I have DRR and forecast and round greater than 6 and dice greater than 6 then take early action.\n",
      "    By default take no action."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "!/software/challenges/nbconvert/nbconvert.py -f reveal /software/challenges/payforpredictions/payforpredictions.ipynb"
     ],
     "language": "python",
     "metadata": {
      "slideshow": {
       "slide_type": "skip"
      }
     },
     "outputs": [],
     "prompt_number": 8
    }
   ],
   "metadata": {}
  }
 ]
}