{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tools for Game Theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Daisuke Oyama**  \n",
    "*Faculty of Economics, University of Tokyo*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook demonstrates the functionalities of the `game_theory` module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from quantecon.game_theory import NormalFormGame, Player"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Normal Form Games"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An $N$-player *normal form game* is a triplet $g = (I, (A_i)_{i \\in I}, (u_i)_{i \\in I})$ where\n",
    "\n",
    "* $I = \\{0, \\ldots, N-1\\}$ is the set of players,\n",
    "* $A_i = \\{0, \\ldots, n_i-1\\}$ is the set of actions of player $i \\in I$, and\n",
    "* $u_i \\colon A_i \\times A_{i+1} \\times \\cdots \\times A_{i+N-1} \\to \\mathbb{R}$\n",
    "  is the payoff function of player $i \\in I$,\n",
    "\n",
    "where $i+j$ is understood modulo $N$.\n",
    "\n",
    "Note that we adopt the convention that the $0$-th argument of the payoff function $u_i$ is\n",
    "player $i$'s own action\n",
    "and the $j$-th argument, $j = 1, \\ldots, N-1$, is player ($i+j$)'s action (modulo $N$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In our module,\n",
    "a normal form game and a player are represented by\n",
    "the classes `NormalFormGame` and `Player`, respectively.\n",
    "\n",
    "A `Player` carries the player's payoff function and implements in particular\n",
    "a method that returns the best response action(s) given an action of the opponent player,\n",
    "or a profile of actions of the opponents if there are more than one.\n",
    "\n",
    "A `NormalFormGame` is in effect a container of `Player` instances."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Creating a `NormalFormGame`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are several ways to create a `NormalFormGame` instance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first is to pass an array of payoffs for all the players, i.e.,\n",
    "an $(N+1)$-dimenstional array of shape $(n_0, \\ldots, n_{N-1}, N)$\n",
    "whose $(a_0, \\ldots, a_{N-1})$-entry contains an array of the $N$ payoff values\n",
    "for the action profile $(a_0, \\ldots, a_{N-1})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example, consider the following game (\"**Matching Pennies**\"):\n",
    "\n",
    "$\n",
    "\\begin{bmatrix}\n",
    "1, -1 & -1, 1 \\\\\n",
    "-1, 1 & 1, -1\n",
    "\\end{bmatrix}\n",
    "$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "matching_pennies_bimatrix = [[(1, -1), (-1, 1)],\n",
    "                             [(-1, 1), (1, -1)]]\n",
    "g_MP = NormalFormGame(matching_pennies_bimatrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-player NormalFormGame with payoff profile array:\n",
      "[[[ 1, -1],  [-1,  1]],\n",
      " [[-1,  1],  [ 1, -1]]]\n"
     ]
    }
   ],
   "source": [
    "print(g_MP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Player in a 2-player normal form game with payoff array:\n",
      "[[ 1, -1],\n",
      " [-1,  1]]\n"
     ]
    }
   ],
   "source": [
    "print(g_MP.players[0])  # Player instance for player 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Player in a 2-player normal form game with payoff array:\n",
      "[[-1,  1],\n",
      " [ 1, -1]]\n"
     ]
    }
   ],
   "source": [
    "print(g_MP.players[1])  # Player instance for player 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1, -1],\n",
       "       [-1,  1]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.players[0].payoff_array  # Player 0's payoff array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[-1,  1],\n",
       "       [ 1, -1]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.players[1].payoff_array  # Player 1's payoff array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1, -1])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP[0, 0]  # payoff profile for action profile (0, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If a square matrix (2-dimensional array) is given,\n",
    "then it is considered to be a symmetric two-player game.\n",
    "\n",
    "Consider the following game (symmetric $2 \\times 2$ \"**Coordination Game**\"):\n",
    "\n",
    "$\n",
    "\\begin{bmatrix}\n",
    "4, 4 & 0, 3 \\\\\n",
    "3, 0 & 2, 2\n",
    "\\end{bmatrix}\n",
    "$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "coordination_game_matrix = [[4, 0],\n",
    "                            [3, 2]]  # square matrix\n",
    "g_Coo = NormalFormGame(coordination_game_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-player NormalFormGame with payoff profile array:\n",
      "[[[4, 4],  [0, 3]],\n",
      " [[3, 0],  [2, 2]]]\n"
     ]
    }
   ],
   "source": [
    "print(g_Coo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[4, 0],\n",
       "       [3, 2]])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_Coo.players[0].payoff_array  # Player 0's payoff array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[4, 0],\n",
       "       [3, 2]])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_Coo.players[1].payoff_array  # Player 1's payoff array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another example (\"**Rock-Paper-Scissors**\"):\n",
    "\n",
    "$\n",
    "\\begin{bmatrix}\n",
    " 0,  0 & -1,  1 &  1, -1 \\\\\n",
    " 1, -1 &  0,  0 & -1,  1 \\\\\n",
    "-1,  1 &  1, -1 &  0,  0\n",
    "\\end{bmatrix}\n",
    "$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "RPS_matrix = [[ 0, -1,  1],\n",
    "              [ 1,  0, -1],\n",
    "              [-1,  1,  0]]\n",
    "g_RPS = NormalFormGame(RPS_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-player NormalFormGame with payoff profile array:\n",
      "[[[ 0,  0],  [-1,  1],  [ 1, -1]],\n",
      " [[ 1, -1],  [ 0,  0],  [-1,  1]],\n",
      " [[-1,  1],  [ 1, -1],  [ 0,  0]]]\n"
     ]
    }
   ],
   "source": [
    "print(g_RPS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second is to specify the sizes of the action sets of the players\n",
    "to create a `NormalFormGame` instance filled with payoff zeros,\n",
    "and then set the payoff values to each entry.\n",
    "\n",
    "Let us construct the following game (\"**Prisoners' Dilemma**\"):\n",
    "\n",
    "$\n",
    "\\begin{bmatrix}\n",
    "1, 1  & -2, 3 \\\\\n",
    "3, -2 & 0, 0\n",
    "\\end{bmatrix}\n",
    "$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g_PD = NormalFormGame((2, 2))  # There are 2 players, each of whom has 2 actions\n",
    "g_PD[0, 0] = 1, 1\n",
    "g_PD[0, 1] = -2, 3\n",
    "g_PD[1, 0] = 3, -2\n",
    "g_PD[1, 1] = 0, 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-player NormalFormGame with payoff profile array:\n",
      "[[[ 1.,  1.],  [-2.,  3.]],\n",
      " [[ 3., -2.],  [ 0.,  0.]]]\n"
     ]
    }
   ],
   "source": [
    "print(g_PD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, a `NormalFormGame` instance can be constructed by giving an array of `Player` instances,\n",
    "as explained in the next section."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Creating a `Player`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A `Player` instance is created by passing an array of dimension $N$\n",
    "that represents the player's payoff function (\"payoff array\").\n",
    "\n",
    "Consider the following game (a variant of \"**Battle of the Sexes**\"):\n",
    "\n",
    "$\n",
    "\\begin{bmatrix}\n",
    "3, 2 & 1, 1 \\\\\n",
    "0, 0 & 2, 3\n",
    "\\end{bmatrix}\n",
    "$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "player0 = Player([[3, 1],\n",
    "                  [0, 2]])\n",
    "player1 = Player([[2, 0],\n",
    "                  [1, 3]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beware that in `payoff_array[h, k]`, `h` refers to the player's own action,\n",
    "while `k` refers to the opponent player's action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[3, 1],\n",
       "       [0, 2]])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "player0.payoff_array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[2, 0],\n",
       "       [1, 3]])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "player1.payoff_array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Passing an array of Player instances is the third way to create a `NormalFormGame` instance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g_BoS = NormalFormGame((player0, player1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-player NormalFormGame with payoff profile array:\n",
      "[[[3, 2],  [1, 1]],\n",
      " [[0, 0],  [2, 3]]]\n"
     ]
    }
   ],
   "source": [
    "print(g_BoS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### More than two players"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `game_theory` module also supports games with more than two players."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us consider the following version of $N$-player **Cournot Game**.\n",
    "\n",
    "There are $N$ firms (players) which produce a homogeneous good\n",
    "with common constant marginal cost $c \\geq 0$.\n",
    "Each firm $i$ simultaneously determines the quantity $q_i \\geq 0$ (action) of the good to produce.\n",
    "The inverse demand function is given by the linear function $P(Q) = a - Q$, $a > 0$,\n",
    "where $Q = q_0 + \\cdots + q_{N-1}$ is the aggregate supply.\n",
    "Then the profit (payoff) for firm $i$ is given by\n",
    "$$\n",
    "u_i(q_i, q_{i+1}, \\ldots, q_{i+N-1})\n",
    "= P(Q) q_i - c q_i\n",
    "= \\left(a - c - \\sum_{j \\neq i} q_j - q_i\\right) q_i.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Theoretically, the set of actions, i.e., available quantities, may be\n",
    "the set of all nonnegative real numbers $\\mathbb{R}_+$\n",
    "(or a bounded interval $[0, \\bar{q}]$ with some upper bound $\\bar{q}$),\n",
    "but for computation on a computer we have to discretize the action space\n",
    "and only allow for finitely many grid points.\n",
    "\n",
    "The following script creates a `NormalFormGame` instance of the Cournot game as described above,\n",
    "assuming that the (common) grid of possible quantity values is stored in an array `q_grid`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from quantecon import cartesian\n",
    "\n",
    "def cournot(a, c, N, q_grid):\n",
    "    \"\"\"\n",
    "    Create a `NormalFormGame` instance for the symmetric N-player Cournot game\n",
    "    with linear inverse demand a - Q and constant marginal cost c.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    a : scalar\n",
    "        Intercept of the demand curve\n",
    "\n",
    "    c : scalar\n",
    "        Common constant marginal cost\n",
    "\n",
    "    N : scalar(int)\n",
    "        Number of firms\n",
    "\n",
    "    q_grid : array_like(scalar)\n",
    "        Array containing the set of possible quantities\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    NormalFormGame\n",
    "        NormalFormGame instance representing the Cournot game\n",
    "\n",
    "    \"\"\"\n",
    "    q_grid = np.asarray(q_grid)\n",
    "    payoff_array = \\\n",
    "        cartesian([q_grid]*N).sum(axis=-1).reshape([len(q_grid)]*N) * (-1) + \\\n",
    "        (a - c)\n",
    "    payoff_array *= q_grid.reshape([len(q_grid)] + [1]*(N-1))\n",
    "    payoff_array += 0  # To get rid of the minus sign of -0\n",
    "\n",
    "    player = Player(payoff_array)\n",
    "    return NormalFormGame([player for i in range(N)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a simple example with three firms,\n",
    "marginal cost $20$, and inverse demand function $80 - Q$,\n",
    "where the feasible quantity values are assumed to be $10$ and $15$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a, c = 80, 20\n",
    "N = 3\n",
    "q_grid = [10, 15]  # [1/3 of Monopoly quantity, Nash equilibrium quantity]\n",
    "\n",
    "g_Cou = cournot(a, c, N, q_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3-player NormalFormGame with payoff profile array:\n",
      "[[[[300, 300, 300],   [250, 250, 375]],\n",
      "  [[250, 375, 250],   [200, 300, 300]]],\n",
      "\n",
      " [[[375, 250, 250],   [300, 200, 300]],\n",
      "  [[300, 300, 200],   [225, 225, 225]]]]\n"
     ]
    }
   ],
   "source": [
    "print(g_Cou)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Player in a 3-player normal form game with payoff array:\n",
      "[[[300, 250],\n",
      "  [250, 200]],\n",
      "\n",
      " [[375, 300],\n",
      "  [300, 225]]]\n"
     ]
    }
   ],
   "source": [
    "print(g_Cou.players[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 2, 2)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_Cou.nums_actions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Nash Equilibrium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A *Nash equilibrium* of a normal form game is a profile of actions\n",
    "where the action of each player is a best response to the others'."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `Player` object has a method `best_response`.\n",
    "\n",
    "Consider the Matching Pennies game `g_MP` defined above.\n",
    "For example, player 0's best response to the opponent's action 1 is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.players[0].best_response(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Player 0's best responses to the opponent's mixed action `[0.5, 0.5]`\n",
    "(we know they are 0 and 1):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# By default, returns the best response action with the smallest index\n",
    "g_MP.players[0].best_response([0.5, 0.5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# With tie_breaking='random', returns randomly one of the best responses\n",
    "g_MP.players[0].best_response([0.5, 0.5], tie_breaking='random')  # Try several times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 1])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# With tie_breaking=False, returns an array of all the best responses\n",
    "g_MP.players[0].best_response([0.5, 0.5], tie_breaking=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this game, we know that `([0.5, 0.5], [0.5, 0.5])` is a (unique) Nash equilibrium."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.is_nash(([0.5, 0.5], [0.5, 0.5]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.is_nash((0, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.is_nash((0, [0.5, 0.5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding Nash equilibria"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our module does not have sophisticated algorithms to compute Nash equilibria (yet)...\n",
    "One might look at [Gambit](http://gambit.sourceforge.net),\n",
    "which implements several such algorithms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Brute force"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For small games, we can find pure action Nash equilibria by brute force."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def find_pure_nash_brute(g):\n",
    "    \"\"\"\n",
    "    Find all pure Nash equilibria of a normal form game by brute force.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    g : NormalFormGame\n",
    "\n",
    "    \"\"\"\n",
    "    NEs = []\n",
    "    for a in np.ndindex(*g.nums_actions):\n",
    "        if g.is_nash(a):\n",
    "            NEs.append(a)\n",
    "    num_NEs = len(NEs)\n",
    "    if num_NEs == 0:\n",
    "        msg = 'no pure Nash equilibrium'\n",
    "    elif num_NEs == 1:\n",
    "        msg = '1 pure Nash equilibrium:\\n{0}'.format(NEs)\n",
    "    else:\n",
    "        msg = '{0} pure Nash equilibria:\\n{1}'.format(num_NEs, NEs)\n",
    "\n",
    "    print('The game has ' + msg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Matching Pennies:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has no pure Nash equilibrium\n"
     ]
    }
   ],
   "source": [
    "find_pure_nash_brute(g_MP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Coordination game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has 2 pure Nash equilibria:\n",
      "[(0, 0), (1, 1)]\n"
     ]
    }
   ],
   "source": [
    "find_pure_nash_brute(g_Coo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rock-Paper-Scissors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has no pure Nash equilibrium\n"
     ]
    }
   ],
   "source": [
    "find_pure_nash_brute(g_RPS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Battle of the Sexes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has 2 pure Nash equilibria:\n",
      "[(0, 0), (1, 1)]\n"
     ]
    }
   ],
   "source": [
    "find_pure_nash_brute(g_BoS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prisoners' Dillema:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has 1 pure Nash equilibrium:\n",
      "[(1, 1)]\n"
     ]
    }
   ],
   "source": [
    "find_pure_nash_brute(g_PD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cournot game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has 1 pure Nash equilibrium:\n",
      "[(1, 1, 1)]\n"
     ]
    }
   ],
   "source": [
    "find_pure_nash_brute(g_Cou)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Sequential best response"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In some games, such as \"supermodular games\" and \"potential games\",\n",
    "the process of sequential best responses converges to a Nash equilibrium."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a script to find *one* pure Nash equilibrium by sequential best response, if it converges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def sequential_best_response(g, init_actions=None, tie_breaking='smallest',\n",
    "                             verbose=True):\n",
    "    \"\"\"\n",
    "    Find a pure Nash equilibrium of a normal form game by sequential best\n",
    "    response.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    g : NormalFormGame\n",
    "\n",
    "    init_actions : array_like(int), optional(default=[0, ..., 0])\n",
    "        The initial action profile.\n",
    "\n",
    "    tie_breaking : {'smallest', 'random'}, optional(default='smallest')\n",
    "\n",
    "    verbose: bool, optional(default=True)\n",
    "        If True, print the intermediate process.\n",
    "\n",
    "    \"\"\"\n",
    "    N = g.N  # Number of players\n",
    "    a = np.empty(N, dtype=int)  # Action profile\n",
    "    if init_actions is None:\n",
    "        init_actions = [0] * N\n",
    "    a[:] = init_actions\n",
    "\n",
    "    if verbose:\n",
    "        print('init_actions: {0}'.format(a))\n",
    "\n",
    "    new_a = np.empty(N, dtype=int)\n",
    "    max_iter = np.prod(g.nums_actions)\n",
    "\n",
    "    for t in range(max_iter):\n",
    "        new_a[:] = a\n",
    "        for i, player in enumerate(g.players):\n",
    "            if N == 2:\n",
    "                a_except_i = new_a[1-i]\n",
    "            else:\n",
    "                a_except_i = new_a[np.arange(i+1, i+N) % N]\n",
    "            new_a[i] = player.best_response(a_except_i,\n",
    "                                            tie_breaking=tie_breaking)\n",
    "            if verbose:\n",
    "                print('player {0}: {1}'.format(i, new_a))\n",
    "        if np.array_equal(new_a, a):\n",
    "            return a\n",
    "        else:\n",
    "            a[:] = new_a\n",
    "\n",
    "    print('No pure Nash equilibrium found')\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A Cournot game with linear demand is known to be a potential game,\n",
    "for which sequential best response converges to a Nash equilibrium.\n",
    "\n",
    "Let us try a bigger instance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a, c = 80, 20\n",
    "N = 3\n",
    "q_grid = np.linspace(0, a-c, 13)  # [0, 5, 10, ..., 60]\n",
    "g_Cou = cournot(a, c, N, q_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [0 0 0]\n",
      "player 0: [6 0 0]\n",
      "player 1: [6 3 0]\n",
      "player 2: [6 3 1]\n",
      "player 0: [4 3 1]\n",
      "player 1: [4 3 1]\n",
      "player 2: [4 3 2]\n",
      "player 0: [3 3 2]\n",
      "player 1: [3 3 2]\n",
      "player 2: [3 3 3]\n",
      "player 0: [3 3 3]\n",
      "player 1: [3 3 3]\n",
      "player 2: [3 3 3]\n",
      "Nash equilibrium indices: [3 3 3]\n",
      "Nash equilibrium quantities: [ 15.  15.  15.]\n"
     ]
    }
   ],
   "source": [
    "a_star = sequential_best_response(g_Cou)  # By default, start with (0, 0, 0)\n",
    "print('Nash equilibrium indices: {0}'.format(a_star))\n",
    "print('Nash equilibrium quantities: {0}'.format(q_grid[a_star]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [12 12 12]\n",
      "player 0: [ 0 12 12]\n",
      "player 1: [ 0  0 12]\n",
      "player 2: [0 0 6]\n",
      "player 0: [3 0 6]\n",
      "player 1: [3 1 6]\n",
      "player 2: [3 1 4]\n",
      "player 0: [3 1 4]\n",
      "player 1: [3 2 4]\n",
      "player 2: [3 2 3]\n",
      "player 0: [3 2 3]\n",
      "player 1: [3 3 3]\n",
      "player 2: [3 3 3]\n",
      "player 0: [3 3 3]\n",
      "player 1: [3 3 3]\n",
      "player 2: [3 3 3]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([3, 3, 3])"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Start with the largest actions (12, 12, 12)\n",
    "sequential_best_response(g_Cou, init_actions=(12, 12, 12))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The limit action profile is indeed a Nash equilibrium:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_Cou.is_nash(a_star)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, the game has other Nash equilibria\n",
    "(because of our choice of grid points and parameter values):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has 7 pure Nash equilibria:\n",
      "[(2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 3, 3), (3, 4, 2), (4, 2, 3), (4, 3, 2)]\n"
     ]
    }
   ],
   "source": [
    "find_pure_nash_brute(g_Cou)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make it bigger:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "N = 4\n",
    "q_grid = np.linspace(0, a-c, 61)  # [0, 1, 2, ..., 60]\n",
    "g_Cou = cournot(a, c, N, q_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [0 0 0 0]\n",
      "player 0: [30  0  0  0]\n",
      "player 1: [30 15  0  0]\n",
      "player 2: [30 15  7  0]\n",
      "player 3: [30 15  7  4]\n",
      "player 0: [17 15  7  4]\n",
      "player 1: [17 16  7  4]\n",
      "player 2: [17 16 11  4]\n",
      "player 3: [17 16 11  8]\n",
      "player 0: [12 16 11  8]\n",
      "player 1: [12 14 11  8]\n",
      "player 2: [12 14 13  8]\n",
      "player 3: [12 14 13 10]\n",
      "player 0: [11 14 13 10]\n",
      "player 1: [11 13 13 10]\n",
      "player 2: [11 13 13 10]\n",
      "player 3: [11 13 13 11]\n",
      "player 0: [11 13 13 11]\n",
      "player 1: [11 12 13 11]\n",
      "player 2: [11 12 13 11]\n",
      "player 3: [11 12 13 12]\n",
      "player 0: [11 12 13 12]\n",
      "player 1: [11 12 13 12]\n",
      "player 2: [11 12 12 12]\n",
      "player 3: [11 12 12 12]\n",
      "player 0: [12 12 12 12]\n",
      "player 1: [12 12 12 12]\n",
      "player 2: [12 12 12 12]\n",
      "player 3: [12 12 12 12]\n",
      "player 0: [12 12 12 12]\n",
      "player 1: [12 12 12 12]\n",
      "player 2: [12 12 12 12]\n",
      "player 3: [12 12 12 12]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([12, 12, 12, 12])"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequential_best_response(g_Cou)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [ 0  0  0 30]\n",
      "player 0: [15  0  0 30]\n",
      "player 1: [15  7  0 30]\n",
      "player 2: [15  7  4 30]\n",
      "player 3: [15  7  4 17]\n",
      "player 0: [16  7  4 17]\n",
      "player 1: [16 11  4 17]\n",
      "player 2: [16 11  8 17]\n",
      "player 3: [16 11  8 12]\n",
      "player 0: [14 11  8 12]\n",
      "player 1: [14 13  8 12]\n",
      "player 2: [14 13 10 12]\n",
      "player 3: [14 13 10 11]\n",
      "player 0: [13 13 10 11]\n",
      "player 1: [13 13 10 11]\n",
      "player 2: [13 13 11 11]\n",
      "player 3: [13 13 11 11]\n",
      "player 0: [12 13 11 11]\n",
      "player 1: [12 13 11 11]\n",
      "player 2: [12 13 12 11]\n",
      "player 3: [12 13 12 11]\n",
      "player 0: [12 13 12 11]\n",
      "player 1: [12 12 12 11]\n",
      "player 2: [12 12 12 11]\n",
      "player 3: [12 12 12 12]\n",
      "player 0: [12 12 12 12]\n",
      "player 1: [12 12 12 12]\n",
      "player 2: [12 12 12 12]\n",
      "player 3: [12 12 12 12]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([12, 12, 12, 12])"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequential_best_response(g_Cou, init_actions=(0, 0, 0, 30))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sequential best response does not converge in all games:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-player NormalFormGame with payoff profile array:\n",
      "[[[ 1, -1],  [-1,  1]],\n",
      " [[-1,  1],  [ 1, -1]]]\n"
     ]
    }
   ],
   "source": [
    "print(g_MP)  # Matching Pennies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [0 0]\n",
      "player 0: [0 0]\n",
      "player 1: [0 1]\n",
      "player 0: [1 1]\n",
      "player 1: [1 0]\n",
      "player 0: [0 0]\n",
      "player 1: [0 1]\n",
      "player 0: [1 1]\n",
      "player 1: [1 0]\n",
      "No pure Nash equilibrium found\n"
     ]
    }
   ],
   "source": [
    "sequential_best_response(g_MP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}