notebooks/06.04-Risk-Averse-Gambler.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "<!--NOTEBOOK_HEADER-->\n",
    "*This notebook contains course material from [CBE40455](https://jckantor.github.io/CBE40455) by\n",
    "Jeffrey Kantor (jeff at nd.edu); the content is available [on Github](https://github.com/jckantor/CBE40455.git).\n",
    "The text is released under the [CC-BY-NC-ND-4.0 license](https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode),\n",
    "and code is released under the [MIT license](https://opensource.org/licenses/MIT).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "<!--NAVIGATION-->\n",
    "< [Risk Neutral Gambler](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/06.03-Risk-Neutral-Gambler.ipynb) | [Contents](toc.ipynb) | [Points after Touchdown Decision](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/06.05-Points-after-Touchdown-Decision.ipynb) ><p><a href=\"https://colab.research.google.com/github/jckantor/CBE40455/blob/master/notebooks/06.04-Risk-Averse-Gambler.ipynb\"><img align=\"left\" src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open in Colab\" title=\"Open in Google Colaboratory\"></a><p><a href=\"https://raw.githubusercontent.com/jckantor/CBE40455/master/notebooks/06.04-Risk-Averse-Gambler.ipynb\"><img align=\"left\" src=\"https://img.shields.io/badge/Github-Download-blue.svg\" alt=\"Download\" title=\"Download Notebook\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "# Risk Averse Gambler"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "## Problem Statement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "A risk averse gambler with a stake of money enters a game with the idea of betting for a fixed number of rounds $T$. With a stake $x$ and wager $u$, the resulting state is either $x+u$ with probability $p$, or $x-u$ with probability $q$ (where $p + q \\leq 1$.) The wager must be an integer smaller than the current stake or the maximum wager established for the game. The total stake is limited to an amount $N$. The gambler is risk averse where utility of the final stake is $\\log(x)$. Given an initial stake $x \\lt N$, calculate a strategy that maximizes the expected utility at the end of the game."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "## Solution by Stochastic Dynamic Programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "The function $V(k,x)$ is the expected utility after of stake $x$ after the $k^{th}$ wager. The expected utility satisfies the optimality equation \n",
    "\n",
    "$$V(k,x) = \\max_u [ p V(k+1,x+u) + q V(k+1,x-u) ]$$ \n",
    "\n",
    "where $V(T,x) = \\log(x)$. The maximization is over the set of possible bets ranging from $0$ to the minimum of $x$, $N-x$, or the bet limit $B$. Note that the state space and set of control actions are finite."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "## Solution by Linear Programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "The optimality equation can be solved by well known methods for policy iteration.  Alternatively, as shown for example by Ross in \"Introduction to Stochastic Dynamic Programming\" (Academic Press, 1983), an exact solution can be found by linear programming. We seek a solution $V[k,x]$ minimizing \n",
    "\n",
    "$$\\sum_{k=0}^{T-1}\\sum_{x=0}^N V[k,x]$$\n",
    "\n",
    "subject to \n",
    "    \n",
    "$$V[k,x] \\geq p V[k+1,x+u] + q V[k+1,x-u]$$\n",
    "\n",
    "for all feasible bets and boundary condition $V[T,x] = \\log(x)$. The set of optimal wagers $u[x]$ are found by determining the constraints that are active at optimality."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "## MathProg Model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "GLPSOL: GLPK LP/MIP Solver, v4.52\n",
      "Parameter(s) specified in the command line:\n",
      " -m /dev/stdin\n",
      "Reading model section from /dev/stdin...\n",
      "/dev/stdin:66: warning: final NL missing before end of file\n",
      "66 lines were read\n",
      "Generating OBJ...\n",
      "Generating C1...\n",
      "Generating C2...\n",
      "Model has been successfully generated\n",
      "GLPK Simplex Optimizer, v4.52\n",
      "3301 rows, 300 columns, 9800 non-zeros\n",
      "Preprocessing...\n",
      "2598 rows, 248 columns, 7596 non-zeros\n",
      "Scaling...\n",
      " A: min|aij| =  4.500e-01  max|aij| =  1.000e+00  ratio =  2.222e+00\n",
      "Problem data seem to be well scaled\n",
      "Constructing initial basis...\n",
      "Size of triangular part is 2598\n",
      "      0: obj =   1.486763158e+02  infeas =  1.962e+03 (0)\n",
      "    500: obj =   4.798199905e+02  infeas =  6.426e+02 (0)\n",
      "   1000: obj =   5.925871650e+02  infeas =  2.744e+02 (0)\n",
      "   1500: obj =   7.381673968e+02  infeas =  3.447e+01 (0)\n",
      "*  1630: obj =   7.602764649e+02  infeas =  1.050e-15 (0)\n",
      "*  1962: obj =   7.453389547e+02  infeas =  6.439e-16 (0)\n",
      "OPTIMAL LP SOLUTION FOUND\n",
      "Time used:   0.2 secs\n",
      "Memory used: 4.4 Mb (4636641 bytes)\n",
      "   Number of Wagers =    5\n",
      "      Maximum Stake =   50\n",
      "        Maximum Bet =   50\n",
      "Winning Probability =    0.550\n",
      " Losing Probability =    0.450\n",
      "\n",
      "             Wager  1     Wager  2     Wager  3     Wager  4     Wager  5  \n",
      "   Stake    CE[x] u[x]   CE[x] u[x]   CE[x] u[x]   CE[x] u[x]   CE[x] u[x]\n",
      "   -----    ---------    ---------    ---------    ---------    --------- \n",
      "       1     1.00   0     1.00   0     1.00   0     1.00   0     1.00   0\n",
      "       2     2.00   0     2.00   0     2.00   0     2.00   0     2.00   0\n",
      "       3     3.00   0     3.00   0     3.00   0     3.00   0     3.00   0\n",
      "       4     4.00   0     4.00   0     4.00   0     4.00   0     4.00   0\n",
      "       5     5.03   1     5.02   1     5.01   1     5.01   1     5.00   0\n",
      "       6     6.08   1     6.06   1     6.05   1     6.03   1     6.02   1\n",
      "       7     7.13   1     7.11   1     7.08   1     7.06   1     7.03   1\n",
      "       8     8.18   1     8.14   1     8.11   1     8.07   1     8.04   1\n",
      "       9     9.22   1     9.18   1     9.13   1     9.09   1     9.04   1\n",
      "      10    10.25   1    10.20   1    10.15   1    10.10   1    10.05   1\n",
      "      11    11.27   1    11.22   1    11.16   1    11.11   1    11.05   1\n",
      "      12    12.29   1    12.23   1    12.18   1    12.12   1    12.06   1\n",
      "      13    13.31   1    13.25   1    13.19   1    13.12   1    13.06   1\n",
      "      14    14.33   1    14.26   1    14.19   1    14.13   1    14.06   1\n",
      "      15    15.36   2    15.28   2    15.21   2    15.13   1    15.07   1\n",
      "      16    16.38   2    16.30   2    16.23   2    16.14   2    16.07   1\n",
      "      17    17.41   2    17.33   2    17.24   2    17.16   2    17.07   1\n",
      "      18    18.44   2    18.35   2    18.26   2    18.17   2    18.07   1\n",
      "      19    19.47   2    19.37   2    19.28   2    19.18   2    19.10   2\n",
      "      20    20.50   2    20.39   2    20.30   2    20.19   2    20.10   2\n",
      "      21    21.52   2    21.42   2    21.31   2    21.21   2    21.11   2\n",
      "      22    22.54   2    22.44   2    22.32   2    22.22   2    22.11   2\n",
      "      23    23.57   2    23.45   2    23.34   2    23.23   2    23.11   2\n",
      "      24    24.59   2    24.47   2    24.35   2    24.23   2    24.12   2\n",
      "      25    25.62   3    25.49   2    25.37   3    25.24   2    25.12   2\n",
      "      26    26.64   3    26.51   3    26.38   3    26.25   3    26.12   2\n",
      "      27    27.67   3    27.53   3    27.39   3    27.26   3    27.13   2\n",
      "      28    28.69   3    28.55   3    28.41   3    28.27   3    28.13   2\n",
      "      29    29.72   3    29.57   3    29.42   3    29.28   3    29.13   2\n",
      "      30    30.74   3    30.59   3    30.44   3    30.28   3    30.13   2\n",
      "      31    31.77   3    31.61   3    31.46   3    31.29   3    31.14   2\n",
      "      32    32.80   3    32.63   3    32.47   3    32.30   3    32.14   2\n",
      "      33    33.82   3    33.65   3    33.48   3    33.32   4    33.14   2\n",
      "      34    34.83   3    34.67   3    34.49   3    34.33   3    34.14   2\n",
      "      35    35.85   3    35.69   3    35.51   4    35.34   4    35.14   2\n",
      "      36    36.87   3    36.71   3    36.52   3    36.35   4    36.14   2\n",
      "      37    37.89   3    37.72   4    37.55   4    37.36   4    37.18   4\n",
      "      38    38.91   3    38.73   3    38.57   4    38.37   4    38.19   4\n",
      "      39    39.92   3    39.74   3    39.57   4    39.38   4    39.20   4\n",
      "      40    40.91   3    40.75   3    40.58   4    40.39   3    40.20   4\n",
      "      41    41.91   3    41.75   3    41.58   4    41.41   4    41.21   4\n",
      "      42    42.89   3    42.75   3    42.57   3    42.42   4    42.21   4\n",
      "      43    43.87   3    43.73   3    43.57   3    43.41   3    43.21   4\n",
      "      44    44.84   3    44.70   3    44.56   3    44.40   4    44.22   4\n",
      "      45    45.78   2    45.65   2    45.54   3    45.38   3    45.22   4\n",
      "      46    46.70   2    46.59   2    46.49   2    46.35   3    46.23   4\n",
      "      47    47.59   2    47.52   2    47.43   2    47.31   2    47.16   2\n",
      "      48    48.46   1    48.40   1    48.32   2    48.27   2    48.16   2\n",
      "      49    49.27   1    49.24   1    49.21   1    49.16   1    49.09   1\n",
      "      50    50.00   0    50.00   0    50.00   0    50.00   0    50.00   0\n",
      "Model has been successfully processed\n"
     ]
    }
   ],
   "source": [
    "%%script glpsol -m /dev/stdin\n",
    "\n",
    "/* Example:  RAGambling.mod Stochastic Dynamic Programming: Risk Averse Gambler */\n",
    "\n",
    "/* Problem Parameters.  Any of these can be adjusted in a data section.  */\n",
    "\n",
    "param T default 5 >= 1;              # Stages\n",
    "param N default 50, >= 1;            # Maximum Stake (reduce if computations are slow)\n",
    "param p default 0.55, >= 0, <= 1;    # Winning probability\n",
    "param q default 1-p, >= 0, <= 1-p;   # Losing probability\n",
    "param B default N, >= 1, <= N;       # Maximum wager size\n",
    "\n",
    "/* Set of States */\n",
    "\n",
    "set X:= 1..N;\n",
    "\n",
    "/* Sets of possible wagers. These are parameterized by the State */\n",
    "\n",
    "set U{x in X} := 0..min(B,min(N-x,x-1));\n",
    "\n",
    "/* Value function */\n",
    "\n",
    "var V{0..T,X}>=0;\n",
    "\n",
    "/* Exact Linear Program Equivalent of the DP */\n",
    "\n",
    "minimize OBJ: sum{t in 0..T-1, x in X} V[t,x] ;\n",
    "\n",
    "s.t. C1 {t in 0..T-1, x in 1..N, u in U[x]}:\n",
    "   V[t,x] >=  p*V[t+1,x+u] + q*V[t+1,x-u];\n",
    "s.t. C2 {x in X}: V[T,x] = log(x);\n",
    "\n",
    "solve;\n",
    "\n",
    "/* Find Optimal Wager */\n",
    "param w{t in 0..T-1,x in 1..N} := \n",
    "   if x==N then 0\n",
    "   else min{u in U[x]:\n",
    "      abs(-V[t,x]+p*V[t+1,x+u]+q*V[t+1,x-u])<0.000001} u;\n",
    "\n",
    "#table tab1 {x in X} OUT \"JSON\" \"Optimal Wager\" \"LineChart\" : \n",
    "#    x, w[T-1,x]~Wager;\n",
    "    \n",
    "#table tab2 {x in X} OUT \"JSON\" \"Expected Utility of the Initial Stake\" \"LineChart\" :\n",
    "#    x, exp(V[T-1,x])~ExpectedUtility;\n",
    "\n",
    "printf \"   Number of Wagers = %4d\\n\", T;\n",
    "printf \"      Maximum Stake = %4d\\n\", N;\n",
    "printf \"        Maximum Bet = %4d\\n\", B;\n",
    "printf \"Winning Probability = %8.3f\\n\", p ;\n",
    "printf \" Losing Probability = %8.3f\\n\", q ;\n",
    "printf \"\\n  %7s \",' ';\n",
    "printf {t in 0..T-1} \"   Wager %2s  \", t+1;\n",
    "printf \"\\n %7s \",'Stake';\n",
    "printf {t in 0..T-1} \"   CE[x] u[x]\";\n",
    "printf \"\\n %7s \",'-----';\n",
    "printf {t in 0..T-1} \"   %9s \", '---------';\n",
    "for {x in X}{\n",
    "   printf \"\\n %7d\", x;\n",
    "   printf {t in 0..T-1} \"   %6.2f %3d\", exp(V[t,x]), w[t,x];\n",
    "}\n",
    "printf \"\\n\";\n",
    "\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "pycharm": {}
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "<!--NAVIGATION-->\n",
    "< [Risk Neutral Gambler](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/06.03-Risk-Neutral-Gambler.ipynb) | [Contents](toc.ipynb) | [Points after Touchdown Decision](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/06.05-Points-after-Touchdown-Decision.ipynb) ><p><a href=\"https://colab.research.google.com/github/jckantor/CBE40455/blob/master/notebooks/06.04-Risk-Averse-Gambler.ipynb\"><img align=\"left\" src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open in Colab\" title=\"Open in Google Colaboratory\"></a><p><a href=\"https://raw.githubusercontent.com/jckantor/CBE40455/master/notebooks/06.04-Risk-Averse-Gambler.ipynb\"><img align=\"left\" src=\"https://img.shields.io/badge/Github-Download-blue.svg\" alt=\"Download\" title=\"Download Notebook\"></a>"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}