game_theory_jl.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tools for Game Theory in Games.jl"
   ]
  },
  {
   "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 [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": true
   },
   "outputs": [],
   "source": [
    "# Pkg.clone(\"https://github.com/QuantEcon/Games.jl\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "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 package,\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_1, \\ldots, n_N, N)$\n",
    "whose $(a_1, \\ldots, a_N)$-entry contains an array of the $N$ payoff values\n",
    "for the action profile $(a_1, \\ldots, a_N)$."
   ]
  },
  {
   "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": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 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]  # payoff profile for action profile (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": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 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": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 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": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 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": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 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": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Array{Float64,1}:\n",
       "  1.0\n",
       " -1.0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP[1, 1]  # payoff profile for action profile (1, 1)"
   ]
  },
  {
   "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": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 NormalFormGame{2,Int64}"
      ]
     },
     "execution_count": 9,
     "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": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Array{Int64,2}:\n",
       " 4  0\n",
       " 3  2"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_Coo.players[1].payoff_array  # Player 1's payoff array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Array{Int64,2}:\n",
       " 4  0\n",
       " 3  2"
      ]
     },
     "execution_count": 11,
     "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": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 NormalFormGame{2,Int64}"
      ]
     },
     "execution_count": 12,
     "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": 13,
   "metadata": {
    "collapsed": true
   },
   "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": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 NormalFormGame{2,Float64}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_PD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Array{Float64,2}:\n",
       " 1.0  -2.0\n",
       " 3.0   0.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_PD.players[1].payoff_array"
   ]
  },
  {
   "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": 16,
   "metadata": {
    "collapsed": true
   },
   "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": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Array{Int64,2}:\n",
       " 3  1\n",
       " 0  2"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "player1.payoff_array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Array{Int64,2}:\n",
       " 2  0\n",
       " 1  3"
      ]
     },
     "execution_count": 18,
     "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": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 NormalFormGame{2,Int64}"
      ]
     },
     "execution_count": 19,
     "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": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "cournot (generic function with 1 method)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function cournot(a::Real, c::Real, ::Val{N}, q_grid::Vector{T}) where {N,T<:Real}\n",
    "    nums_actions = ntuple(x->length(q_grid), Val(N))\n",
    "    S = promote_type(typeof(a), typeof(c), T)\n",
    "    payoff_array= Array{S}(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]]\n",
    "        end\n",
    "        payoff_array[I] = (a - c - Q) * q_grid[I[1]]\n",
    "    end\n",
    "    players = ntuple(x->Player(payoff_array), Val(N))\n",
    "    return NormalFormGame(players)\n",
    "end"
   ]
  },
  {
   "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": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2×2 NormalFormGame{3,Int64}"
      ]
     },
     "execution_count": 21,
     "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, Val(N), q_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2×2 Player{3,Int64}:\n",
       "[:, :, 1] =\n",
       " 300  250\n",
       " 375  300\n",
       "\n",
       "[:, :, 2] =\n",
       " 250  200\n",
       " 300  225"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_Cou.players[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 2, 2)"
      ]
     },
     "execution_count": 23,
     "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 methods `best_response` and `best_responses`.\n",
    "\n",
    "Consider the Matching Pennies game `g_MP` defined above.\n",
    "For example, player 1's best response to the opponent's action 2 is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "2"
      ],
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_response(g_MP.players[1], 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Player 1's best responses to the opponent's mixed action `[0.5, 0.5]`\n",
    "(we know they are 1 and 2):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "1"
      ],
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 25,
     "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": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "2"
      ],
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 26,
     "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": "markdown",
   "metadata": {},
   "source": [
    "`best_responses` returns an array of all the best responses:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Array{Int64,1}:\n",
       " 1\n",
       " 2"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "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": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "true"
      ],
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_nash(g_MP, ([0.5, 0.5], [0.5, 0.5]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "false"
      ],
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_nash(g_MP, (1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "false"
      ],
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_nash(g_MP, ([1., 0.], [0.5, 0.5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding Nash equilibria"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our package does not have sophisticated algorithms to compute Nash equilibria (yet)...\n",
    "One might look at the [`game_theory`](http://quanteconpy.readthedocs.io/en/latest/game_theory.html) module in [QuantEcon.py](https://github.com/QuantEcon/QuantEcon.py) or [Gambit](http://www.gambit-project.org),\n",
    "which implement 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,\n",
    "by calling the method [`pure_nash`](http://quantecon.github.io/Games.jl/latest/lib/computing_nash_equilibria.html#pure_nash-1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "print_pure_nash_brute (generic function with 1 method)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function print_pure_nash_brute(g::NormalFormGame)\n",
    "    NEs = pure_nash(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[1])\"\n",
    "    else\n",
    "        msg = \"$num_NEs pure Nash equilibria:\\n\"\n",
    "        for (i, NE) in enumerate(NEs)\n",
    "            i < num_NEs ? msg *= \"$NE,\" : msg *= \"$NE\"\n",
    "        end\n",
    "    end\n",
    "    println(join([\"The game has \", msg]))\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Matching Pennies:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "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": 33,
   "metadata": {},
   "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": 34,
   "metadata": {},
   "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": 35,
   "metadata": {},
   "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": 36,
   "metadata": {},
   "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": 37,
   "metadata": {},
   "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": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "sequential_best_response (generic function with 1 method)"
      ]
     },
     "execution_count": 38,
     "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": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13×13×13 NormalFormGame{3,Float64}"
      ]
     },
     "execution_count": 39,
     "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, Val(N), q_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "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 (1, 1, 1)\n",
    "println(\"Nash equilibrium indices: $a_star\")\n",
    "println(\"Nash equilibrium quantities: $(q_grid[a_star])\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [13, 13, 13]\n",
      "player 1: [1, 13, 13]\n",
      "player 2: [1, 1, 13]\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"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3-element Array{Int64,1}:\n",
       " 4\n",
       " 4\n",
       " 4"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Start with the largest actions (13, 13, 13)\n",
    "sequential_best_response(g_Cou, init_actions=[13, 13, 13])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The limit action profile is indeed a Nash equilibrium:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "true"
      ],
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 42,
     "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": 43,
   "metadata": {},
   "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": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "61×61×61×61 NormalFormGame{4,Float64}"
      ]
     },
     "execution_count": 44,
     "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, Val(N), q_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [1, 1, 1, 1]\n",
      "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"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4-element Array{Int64,1}:\n",
       " 13\n",
       " 13\n",
       " 13\n",
       " 13"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequential_best_response(g_Cou)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [1, 1, 1, 31]\n",
      "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"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4-element Array{Int64,1}:\n",
       " 13\n",
       " 13\n",
       " 13\n",
       " 13"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2×2 NormalFormGame{2,Float64}"
     ]
    }
   ],
   "source": [
    "print(g_MP)  # Matching Pennies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "init_actions: [1, 1]\n",
      "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"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2-element Array{Int64,1}:\n",
       " 2\n",
       " 1"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequential_best_response(g_MP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Support enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The routine [`support_enumeration`](http://quantecon.github.io/Games.jl/latest/lib/computing_nash_equilibria.html#support_enumeration-1),\n",
    "which is for two-player games, visits all equal-size support pairs\n",
    "and checks whether each pair has a Nash equilibrium (in mixed actions) by the indifference condition.\n",
    "(This should thus be used only for small games.)\n",
    "For nondegenerate games, this routine returns all the Nash equilibria."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Matching Pennies:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1-element Array{Tuple{Array{Real,1},Array{Real,1}},1}:\n",
       " (Real[0.5, 0.5], Real[0.5, 0.5])"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support_enumeration(g_MP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Coordination game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Tuple{Array{Real,1},Array{Real,1}},1}:\n",
       " (Real[1.0, 0.0], Real[1.0, 0.0])                    \n",
       " (Real[0.0, 1.0], Real[0.0, 1.0])                    \n",
       " (Real[0.666667, 0.333333], Real[0.666667, 0.333333])"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support_enumeration(g_Coo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rock-Paper-Scissors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1-element Array{Tuple{Array{Real,1},Array{Real,1}},1}:\n",
       " (Real[0.333333, 0.333333, 0.333333], Real[0.333333, 0.333333, 0.333333])"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support_enumeration(g_RPS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the $6 \\times 6$ game by von Stengel (1997), page 12:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "player1 = Player(\n",
    "    [    9504     -660    19976   -20526     1776    -8976;\n",
    "      -111771    31680  -130944   168124    -8514    52764;\n",
    "       397584  -113850   451176  -586476    29216  -178761;\n",
    "       171204   -45936   208626  -263076    14124   -84436;\n",
    "      1303104  -453420  1227336 -1718376    72336  -461736;\n",
    "       737154  -227040   774576 -1039236    48081  -300036]\n",
    ")\n",
    "\n",
    "player2 = Player(\n",
    "    [   72336  -461736  1227336 -1718376  1303104  -453420;\n",
    "        48081  -300036   774576 -1039236   737154  -227040;\n",
    "        29216  -178761   451176  -586476   397584  -113850;\n",
    "        14124   -84436   208626  -263076   171204   -45936;\n",
    "         1776    -8976    19976   -20526     9504     -660;\n",
    "        -8514    52764  -130944   168124  -111771    31680]\n",
    ")\n",
    "\n",
    "g_vonStengel = NormalFormGame(player1, player2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "75"
      ],
      "text/plain": [
       "75"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length(support_enumeration(g_vonStengel))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the $n \\times n$ game where the payoff matrices are given by the identy matrix\n",
    "has $2^n−1$ equilibria.\n",
    "It had been conjectured that this is the maximum number of equilibria of\n",
    "any nondegenerate $n \\times n$ game.\n",
    "The game above, the number of whose equilibria is $75 > 2^6 - 1 = 63$,\n",
    "was presented as a counter-example to this conjecture."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Next, let us study the **All-Pay Acution**,\n",
    "where, unlike standard auctions,\n",
    "bidders pay their bids regardless of whether or not they win.\n",
    "Situations modeled as all-pay auctions include\n",
    "job promotion, R&D, and rent seeking competitions, among others.\n",
    "\n",
    "Here we consider a version of All-Pay Auction with complete information,\n",
    "symmetric bidders, discrete bids, bid caps, and \"full dissipation\"\n",
    "(where the prize is materialized if and only if\n",
    "there is only one bidder who makes a highest bid)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Specifically, each of $N$ players simultaneously bids an integer from $\\{0, 1, \\ldots, c\\}$,\n",
    "where $c$ is the common (integer) bid cap.\n",
    "If player $i$'s bid is higher than all the other players',\n",
    "then he receives the prize, whose value is $r$, common to all players,\n",
    "and pays his bid $b_i$.\n",
    "Otherwise, he pays $b_i$ and receives nothing (zero value).\n",
    "In particular, if there are more than one players who make the highest bid,\n",
    "the prize gets *fully dissipated* and all the players receive nothing.\n",
    "Thus, player $i$'s payoff function is\n",
    "$$\n",
    "u_i(b_i, b_{i+1}, \\ldots, b_{i+N-1}) =\n",
    "\\begin{cases}\n",
    "r - b_i & \\text{if $b_i > b_j$ for all $j \\neq i$}, \\\\ - b_i & \\text{otherwise}.\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following is a script to construct a `NormalFormGame` instance\n",
    "for the All-Pay Auction game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "all_pay_auction (generic function with 1 method)"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function all_pay_auction(r::T, c::Integer, ::Val{N};\n",
    "                         dissipation::Bool=true) where {N,T<:Real}\n",
    "    nums_actions = ntuple(x->c+1, Val(N))\n",
    "    S = typeof(zero(T)/one(T))\n",
    "    payoff_array= Array{S}(nums_actions)\n",
    "    num_ties = 0\n",
    "    for bids in CartesianRange(nums_actions)\n",
    "        payoff_array[bids] = -(bids[1]-1)\n",
    "        num_ties = 1\n",
    "        for j in 2:N\n",
    "            if bids[j] > bids[1]\n",
    "                num_ties = 0\n",
    "                break\n",
    "            elseif bids[j] == bids[1]\n",
    "                if dissipation\n",
    "                    num_ties = 0\n",
    "                    break\n",
    "                else\n",
    "                    num_ties += 1\n",
    "                end\n",
    "            end\n",
    "        end\n",
    "        if num_ties > 0\n",
    "            payoff_array[bids] += r / num_ties\n",
    "        end\n",
    "    end\n",
    "    players = ntuple(x->Player(payoff_array), Val(N))\n",
    "    return NormalFormGame(players)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "N = 2\n",
    "c = 5  # odd\n",
    "r = 8;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6×6 Player{2,Float64}:\n",
       " 0.0   0.0   0.0   0.0   0.0   0.0\n",
       " 7.0  -1.0  -1.0  -1.0  -1.0  -1.0\n",
       " 6.0   6.0  -2.0  -2.0  -2.0  -2.0\n",
       " 5.0   5.0   5.0  -3.0  -3.0  -3.0\n",
       " 4.0   4.0   4.0   4.0  -4.0  -4.0\n",
       " 3.0   3.0   3.0   3.0   3.0  -5.0"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_APA_odd = all_pay_auction(r, c, Val(N))\n",
    "g_APA_odd.players[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Clearly, this game has no pure-action Nash equilibrium.\n",
    "Indeed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0-element Array{Tuple{Int64,Int64},1}"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pure_nash(g_APA_odd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As pointed out by Dechenaux et al. (2006),\n",
    "there are three Nash equilibria when the bid cap `c` is odd\n",
    "(so that there are an even number of actions for each player):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Tuple{Array{Real,1},Array{Real,1}},1}:\n",
       " (Real[0.5, 0.0, 0.25, 0.0, 0.25, 0.0], Real[0.0, 0.25, 0.0, 0.25, 0.0, 0.5])                    \n",
       " (Real[0.0, 0.25, 0.0, 0.25, 0.0, 0.5], Real[0.5, 0.0, 0.25, 0.0, 0.25, 0.0])                    \n",
       " (Real[0.125, 0.125, 0.125, 0.125, 0.125, 0.375], Real[0.125, 0.125, 0.125, 0.125, 0.125, 0.375])"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support_enumeration(g_APA_odd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In addition to a symmetric, totally mixed equilibrium (the third),\n",
    "there are two asymmetric, \"alternating\" equilibria (the first and the second)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If `e` is even, there is a unique equilibrium, which is symmetric and totally mixed.\n",
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1-element Array{Tuple{Array{Real,1},Array{Real,1}},1}:\n",
       " (Real[0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.25], Real[0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.25])"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c = 6  # even\n",
    "g_APA_even = all_pay_auction(r, c, Val(N))\n",
    "support_enumeration(g_APA_even)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Further Reading\n",
    "\n",
    "* [A Recursive Formulation of Repeated Games](https://nbviewer.jupyter.org/github/QuantEcon/QuantEcon.notebooks/blob/master/recursive_repeated_games.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "* E. Dechenaux, D. Kovenock, and V. Lugovskyy (2006),\n",
    "  \"Caps on bidding in all-pay auctions:\n",
    "  Comments on the experiments of A. Rapoport and W. Amaldoss,\"\n",
    "  Journal of Economic Behavior and Organization 61, 276-283.\n",
    "\n",
    "* B. von Stengel (1997),\n",
    "  \"[New Lower Bounds for the Number of Equilibria in Bimatrix Games](http://www.maths.lse.ac.uk/personal/stengel/TEXTE/264.pdf).\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.6.0",
   "language": "julia",
   "name": "julia-0.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}