{
 "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 `Player` and `NormalFormGame` types\n",
    "in [QuantEcon/Games.jl](https://github.com/QuantEcon/Games.jl)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first time you run this notebook,\n",
    "you need to install the Games.jl package by removing the \"#\" below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Pkg.clone(\"https://github.com/QuantEcon/Games.jl\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "using Games"
   ]
  },
  {
   "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 = \\{1, \\ldots, N\\}$ is the set of players,\n",
    "* $A_i = \\{1, \\ldots, n_i\\}$ 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 $1$-st argument of the payoff function $u_i$ is\n",
    "player $i$'s own action\n",
    "and the $j$-th argument, $j = 2, \\ldots, N$, is player ($i+j-1$)'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 types `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": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 NormalFormGame{2,Float64}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matching_pennies_bimatrix = Array(Float64, 2, 2, 2)\n",
    "matching_pennies_bimatrix[:, 1, 1] = [1, -1]\n",
    "matching_pennies_bimatrix[:, 1, 2] = [-1, 1]\n",
    "matching_pennies_bimatrix[:, 2, 1] = [-1, 1]\n",
    "matching_pennies_bimatrix[:, 2, 2] = [1, -1]\n",
    "g_MP = NormalFormGame(matching_pennies_bimatrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 Player{2,Float64}:\n",
       "  1.0  -1.0\n",
       " -1.0   1.0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.players[1]  # Player instance for player 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 Player{2,Float64}:\n",
       " -1.0   1.0\n",
       "  1.0  -1.0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.players[2]  # Player instance for player 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 Array{Float64,2}:\n",
       "  1.0  -1.0\n",
       " -1.0   1.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.players[1].payoff_array  # Player 1's payoff array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 Array{Float64,2}:\n",
       " -1.0   1.0\n",
       "  1.0  -1.0"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.players[2].payoff_array  # Player 2's payoff array"
   ]
  },
  {
   "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": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 NormalFormGame{2,Int64}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coordination_game_matrix = [4 0;\n",
    "                            3 2]  # square matrix\n",
    "g_Coo = NormalFormGame(coordination_game_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 Array{Int64,2}:\n",
       " 4  0\n",
       " 3  2"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_Coo.players[1].payoff_array  # Player 1's payoff array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 Array{Int64,2}:\n",
       " 4  0\n",
       " 3  2"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_Coo.players[2].payoff_array  # Player 2'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": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3x3 NormalFormGame{2,Int64}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "RPS_matrix = [0 -1 1;\n",
    "              1 0 -1;\n",
    "              -1 1 0]\n",
    "g_RPS = NormalFormGame(RPS_matrix)"
   ]
  },
  {
   "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": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g_PD = NormalFormGame((2, 2))  # There are 2 players, each of whom has 2 actions\n",
    "g_PD[1, 1] = [1, 1]\n",
    "g_PD[1, 2] = [-2, 3]\n",
    "g_PD[2, 1] = [3, -2]\n",
    "g_PD[2, 2] = [0, 0];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2x2 NormalFormGame{2,Float64}"
     ]
    }
   ],
   "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": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "player1 = Player([3 1; 0 2])\n",
    "player2 = Player([2 0; 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": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 Array{Int64,2}:\n",
       " 3  1\n",
       " 0  2"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "player1.payoff_array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 Array{Int64,2}:\n",
       " 2  0\n",
       " 1  3"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "player2.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": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2 NormalFormGame{2,Int64}"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_BoS = NormalFormGame((player1, player2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### More than two players"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Games with more than two players are also supported."
   ]
  },
  {
   "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_1 + \\cdots + q_N$ 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": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "cournot (generic function with 1 method)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "immutable Cournot{N} end\n",
    "\n",
    "function Base.call{N,T<:Real}(::Type{Cournot{N}},\n",
    "                              a::Real, c::Real, q_grid::Vector{T})\n",
    "    nums_actions = tuple([length(q_grid) for i in 1:N]...)::NTuple{N,Int}\n",
    "    S = promote_type(typeof(a), typeof(c), T)\n",
    "    payoff_array= Array{T}(nums_actions)\n",
    "    for I in CartesianRange(nums_actions)\n",
    "        Q = zero(S)\n",
    "        for i in 1:N\n",
    "            Q += q_grid[I[i]]::T\n",
    "        end\n",
    "        payoff_array[I] = (a - c - Q) * q_grid[I[1]]\n",
    "    end\n",
    "    players = tuple([Player(payoff_array) for i in 1:N]...)::NTuple{N,Player{N,T}}\n",
    "    return NormalFormGame(players)\n",
    "end\n",
    "\n",
    "cournot{T<:Real}(a::Real, c::Real, N::Integer, q_grid::Vector{T}) =\n",
    "    Cournot{N}(a, c, q_grid)"
   ]
  },
  {
   "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": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2x2x2 NormalFormGame{3,Int64}"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2x2x2 Player{3,Int64}:\n",
      "[:, :, 1] =\n",
      " 300  250\n",
      " 375  300\n",
      "\n",
      "[:, :, 2] =\n",
      " 250  200\n",
      " 300  225"
     ]
    }
   ],
   "source": [
    "print(g_Cou.players[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2,2,2)"
      ]
     },
     "execution_count": 21,
     "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": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_response(g_MP.players[1], 2)"
   ]
  },
  {
   "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": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# By default, returns the best response action with the smallest index\n",
    "best_response(g_MP.players[1], [0.5, 0.5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# With tie_breaking='random', returns randomly one of the best responses\n",
    "best_response(g_MP.players[1], [0.5, 0.5], tie_breaking=\"random\")  # Try several times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Array{Int64,1}:\n",
       " 1\n",
       " 2"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# With tie_breaking=False, returns an array of all the best responses\n",
    "best_responses(g_MP.players[1], [0.5, 0.5])"
   ]
  },
  {
   "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": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_nash(g_MP, ([0.5, 0.5], [0.5, 0.5]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_nash(g_MP, (1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_nash(g_MP, (1, [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...\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": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "find_pure_nash_brute (generic function with 1 method)"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function find_pure_nash_brute{N,T}(g::NormalFormGame{N,T})\n",
    "    NEs = Array(NTuple{N,Int}, 0)\n",
    "    for I in CartesianRange(g.nums_actions)\n",
    "        a::NTuple{N,Int} = tuple([I[i] for i in 1:N]...)  # Convert CartesianIndex to Tuple\n",
    "        if is_nash(g, a)\n",
    "            push!(NEs, a)\n",
    "        end\n",
    "    end\n",
    "    return NEs\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "print_pure_nash_brute (generic function with 1 method)"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function print_pure_nash_brute(g::NormalFormGame)\n",
    "    NEs = find_pure_nash_brute(g)\n",
    "    num_NEs = length(NEs)\n",
    "    if num_NEs == 0\n",
    "        msg = \"no pure Nash equilibrium\"\n",
    "    elseif num_NEs == 1\n",
    "        msg = \"1 pure Nash equilibrium:\\n$NEs\"\n",
    "    else\n",
    "        msg = \"$num_NEs pure Nash equilibria:\\n$NEs\"\n",
    "    end\n",
    "    println(join([\"The game has \", msg]))\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Matching Pennies:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has no pure Nash equilibrium\n"
     ]
    }
   ],
   "source": [
    "print_pure_nash_brute(g_MP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Coordination game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has 2 pure Nash equilibria:\n",
      "[(1,1),(2,2)]\n"
     ]
    }
   ],
   "source": [
    "print_pure_nash_brute(g_Coo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rock-Paper-Scissors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has no pure Nash equilibrium\n"
     ]
    }
   ],
   "source": [
    "print_pure_nash_brute(g_RPS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Battle of the Sexes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has 2 pure Nash equilibria:\n",
      "[(1,1),(2,2)]\n"
     ]
    }
   ],
   "source": [
    "print_pure_nash_brute(g_BoS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prisoners' Dillema:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has 1 pure Nash equilibrium:\n",
      "[(2,2)]\n"
     ]
    }
   ],
   "source": [
    "print_pure_nash_brute(g_PD)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cournot game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has 1 pure Nash equilibrium:\n",
      "[(2,2,2)]\n"
     ]
    }
   ],
   "source": [
    "print_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": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "sequential_best_response (generic function with 1 method)"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function sequential_best_response(g::NormalFormGame;\n",
    "                                  init_actions::Union{Vector{Int},Void}=nothing,\n",
    "                                  tie_breaking=\"smallest\",\n",
    "                                  verbose=true)\n",
    "    N = num_players(g)\n",
    "    a = Array{Int}(N)\n",
    "    if init_actions == nothing\n",
    "        init_actions = ones(Int, N)\n",
    "    end\n",
    "    copy!(a, init_actions)\n",
    "    if verbose\n",
    "        println(\"init_actions: $a\")\n",
    "    end\n",
    "    \n",
    "    new_a = Array{Int}(N)\n",
    "    max_iter = prod(g.nums_actions)\n",
    "    \n",
    "    for t in 1:max_iter\n",
    "        copy!(new_a, a)\n",
    "        for (i, player) in enumerate(g.players)\n",
    "            if N == 2\n",
    "                a_except_i = new_a[3-i]\n",
    "            else\n",
    "                a_except_i = (new_a[i+1:N]..., new_a[1:i-1]...)\n",
    "            end\n",
    "            new_a[i] = best_response(player, a_except_i,\n",
    "                                     tie_breaking=tie_breaking)\n",
    "            if verbose\n",
    "                println(\"player $i: $new_a\")\n",
    "            end\n",
    "        end\n",
    "        if new_a == a\n",
    "            return a\n",
    "        else\n",
    "            copy!(a, new_a)\n",
    "        end\n",
    "    end\n",
    "    \n",
    "    println(\"No pure Nash equilibrium found\")\n",
    "    return a\n",
    "end"
   ]
  },
  {
   "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": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13x13x13 NormalFormGame{3,Float64}"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a, c = 80, 20\n",
    "N = 3\n",
    "q_grid = collect(linspace(0, a-c, 13))  # [0, 5, 10, ..., 60]\n",
    "g_Cou = cournot(a, c, N, q_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [1,1,1]\n",
      "player 1: [7,1,1]\n",
      "player 2: [7,4,1]\n",
      "player 3: [7,4,2]\n",
      "player 1: [5,4,2]\n",
      "player 2: [5,4,2]\n",
      "player 3: [5,4,3]\n",
      "player 1: [4,4,3]\n",
      "player 2: [4,4,3]\n",
      "player 3: [4,4,4]\n",
      "player 1: [4,4,4]\n",
      "player 2: [4,4,4]\n",
      "player 3: [4,4,4]\n",
      "Nash equilibrium indices: [4,4,4]\n",
      "Nash equilibrium quantities: [15.0,15.0,15.0]\n"
     ]
    }
   ],
   "source": [
    "a_star = sequential_best_response(g_Cou)  # By default, start with (0, 0, 0)\n",
    "println(\"Nash equilibrium indices: $a_star\")\n",
    "println(\"Nash equilibrium quantities: $(q_grid[a_star])\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [12,12,12]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3-element Array{Int64,1}:\n",
       " 4\n",
       " 4\n",
       " 4"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "player 1: [1,12,12]\n",
      "player 2: [1,1,12]\n",
      "player 3: [1,1,7]\n",
      "player 1: [4,1,7]\n",
      "player 2: [4,2,7]\n",
      "player 3: [4,2,5]\n",
      "player 1: [4,2,5]\n",
      "player 2: [4,3,5]\n",
      "player 3: [4,3,4]\n",
      "player 1: [4,3,4]\n",
      "player 2: [4,4,4]\n",
      "player 3: [4,4,4]\n",
      "player 1: [4,4,4]\n",
      "player 2: [4,4,4]\n",
      "player 3: [4,4,4]\n"
     ]
    }
   ],
   "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": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_nash(g_Cou, tuple(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": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The game has 7 pure Nash equilibria:\n",
      "[(5,4,3),(4,5,3),(5,3,4),(4,4,4),(3,5,4),(4,3,5),(3,4,5)]\n"
     ]
    }
   ],
   "source": [
    "print_pure_nash_brute(g_Cou)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make it bigger:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "61x61x61x61 NormalFormGame{4,Float64}"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N = 4\n",
    "q_grid = collect(linspace(0, a-c, 61))  # [0, 1, 2, ..., 60]\n",
    "g_Cou = cournot(a, c, N, q_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [1,1,1,1]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4-element Array{Int64,1}:\n",
       " 13\n",
       " 13\n",
       " 13\n",
       " 13"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "player 1: [31,1,1,1]\n",
      "player 2: [31,16,1,1]\n",
      "player 3: [31,16,8,1]\n",
      "player 4: [31,16,8,5]\n",
      "player 1: [18,16,8,5]\n",
      "player 2: [18,17,8,5]\n",
      "player 3: [18,17,12,5]\n",
      "player 4: [18,17,12,9]\n",
      "player 1: [13,17,12,9]\n",
      "player 2: [13,15,12,9]\n",
      "player 3: [13,15,14,9]\n",
      "player 4: [13,15,14,11]\n",
      "player 1: [12,15,14,11]\n",
      "player 2: [12,14,14,11]\n",
      "player 3: [12,14,14,11]\n",
      "player 4: [12,14,14,12]\n",
      "player 1: [12,14,14,12]\n",
      "player 2: [12,13,14,12]\n",
      "player 3: [12,13,14,12]\n",
      "player 4: [12,13,14,13]\n",
      "player 1: [12,13,14,13]\n",
      "player 2: [12,13,14,13]\n",
      "player 3: [12,13,13,13]\n",
      "player 4: [12,13,13,13]\n",
      "player 1: [13,13,13,13]\n",
      "player 2: [13,13,13,13]\n",
      "player 3: [13,13,13,13]\n",
      "player 4: [13,13,13,13]\n",
      "player 1: [13,13,13,13]\n",
      "player 2: [13,13,13,13]\n",
      "player 3: [13,13,13,13]\n",
      "player 4: [13,13,13,13]\n"
     ]
    }
   ],
   "source": [
    "sequential_best_response(g_Cou)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [1,1,1,31]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4-element Array{Int64,1}:\n",
       " 13\n",
       " 13\n",
       " 13\n",
       " 13"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "player 1: [16,1,1,31]\n",
      "player 2: [16,8,1,31]\n",
      "player 3: [16,8,5,31]\n",
      "player 4: [16,8,5,18]\n",
      "player 1: [17,8,5,18]\n",
      "player 2: [17,12,5,18]\n",
      "player 3: [17,12,9,18]\n",
      "player 4: [17,12,9,13]\n",
      "player 1: [15,12,9,13]\n",
      "player 2: [15,14,9,13]\n",
      "player 3: [15,14,11,13]\n",
      "player 4: [15,14,11,12]\n",
      "player 1: [14,14,11,12]\n",
      "player 2: [14,14,11,12]\n",
      "player 3: [14,14,12,12]\n",
      "player 4: [14,14,12,12]\n",
      "player 1: [13,14,12,12]\n",
      "player 2: [13,14,12,12]\n",
      "player 3: [13,14,13,12]\n",
      "player 4: [13,14,13,12]\n",
      "player 1: [13,14,13,12]\n",
      "player 2: [13,13,13,12]\n",
      "player 3: [13,13,13,12]\n",
      "player 4: [13,13,13,13]\n",
      "player 1: [13,13,13,13]\n",
      "player 2: [13,13,13,13]\n",
      "player 3: [13,13,13,13]\n",
      "player 4: [13,13,13,13]\n"
     ]
    }
   ],
   "source": [
    "sequential_best_response(g_Cou, init_actions=[1, 1, 1, 31])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sequential best response does not converge in all games:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2x2 NormalFormGame{2,Float64}"
     ]
    }
   ],
   "source": [
    "print(g_MP)  # Matching Pennies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [1,1]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2-element Array{Int64,1}:\n",
       " 2\n",
       " 1"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "player 1: [1,1]\n",
      "player 2: [1,2]\n",
      "player 1: [2,2]\n",
      "player 2: [2,1]\n",
      "player 1: [1,1]\n",
      "player 2: [1,2]\n",
      "player 1: [2,2]\n",
      "player 2: [2,1]\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": {
  "kernelspec": {
   "display_name": "Julia 0.4.3",
   "language": "julia",
   "name": "julia-0.4"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}