game_theory_jl.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tools for Game Theory in GameTheory.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 [GameTheory.jl](https://github.com/QuantEcon/GameTheory.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": {},
   "outputs": [],
   "source": [
    "# using Pkg; Pkg.add(\"GameTheory\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "using GameTheory"
   ]
  },
  {
   "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": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 NormalFormGame{2, Float64}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matching_pennies_bimatrix = Array{Float64}(undef, 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": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2×2 NormalFormGame{2, Float64}:\n",
      " [1.0, -1.0]  [-1.0, 1.0]\n",
      " [-1.0, 1.0]  [1.0, -1.0]"
     ]
    }
   ],
   "source": [
    "print(g_MP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "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[1]  # Player instance for player 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Player{2, Float64}:\n",
       " -1.0   1.0\n",
       "  1.0  -1.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.players[2]  # Player instance for player 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Matrix{Float64}:\n",
       "  1.0  -1.0\n",
       " -1.0   1.0"
      ]
     },
     "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": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Matrix{Float64}:\n",
       " -1.0   1.0\n",
       "  1.0  -1.0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_MP.players[2].payoff_array  # Player 2's payoff array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Vector{Float64}:\n",
       "  1.0\n",
       " -1.0"
      ]
     },
     "execution_count": 9,
     "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": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 NormalFormGame{2, Int64}"
      ]
     },
     "execution_count": 10,
     "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": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2×2 NormalFormGame{2, Int64}:\n",
      " [4, 4]  [0, 3]\n",
      " [3, 0]  [2, 2]"
     ]
    }
   ],
   "source": [
    "print(g_Coo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Matrix{Int64}:\n",
       " 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": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Matrix{Int64}:\n",
       " 4  0\n",
       " 3  2"
      ]
     },
     "execution_count": 13,
     "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": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 NormalFormGame{2, Int64}"
      ]
     },
     "execution_count": 14,
     "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": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3×3 NormalFormGame{2, Int64}:\n",
      " [0, 0]   [-1, 1]  [1, -1]\n",
      " [1, -1]  [0, 0]   [-1, 1]\n",
      " [-1, 1]  [1, -1]  [0, 0]"
     ]
    }
   ],
   "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": 16,
   "metadata": {},
   "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": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2×2 NormalFormGame{2, Float64}:\n",
      " [1.0, 1.0]   [-2.0, 3.0]\n",
      " [3.0, -2.0]  [0.0, 0.0]"
     ]
    }
   ],
   "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": 18,
   "metadata": {},
   "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": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Matrix{Int64}:\n",
       " 3  1\n",
       " 0  2"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "player1.payoff_array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Matrix{Int64}:\n",
       " 2  0\n",
       " 1  3"
      ]
     },
     "execution_count": 20,
     "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": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 NormalFormGame{2, Int64}"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_BoS = NormalFormGame((player1, player2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2×2 NormalFormGame{2, Int64}:\n",
      " [3, 2]  [1, 1]\n",
      " [0, 0]  [2, 3]"
     ]
    }
   ],
   "source": [
    "print(g_BoS)"
   ]
  },
  {
   "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": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "cournot (generic function with 1 method)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function cournot(a::Real, c::Real, ::Val{N}, q_grid::AbstractVector{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}(undef, nums_actions)\n",
    "    for I in CartesianIndices(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": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2×2 NormalFormGame{3, Int64}"
      ]
     },
     "execution_count": 24,
     "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": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2×2×2 NormalFormGame{3, Int64}:\n",
      "[:, :, 1] =\n",
      " [300, 300, 300]  [250, 375, 250]\n",
      " [375, 250, 250]  [300, 300, 200]\n",
      "\n",
      "[:, :, 2] =\n",
      " [250, 250, 375]  [200, 300, 300]\n",
      " [300, 200, 300]  [225, 225, 225]"
     ]
    }
   ],
   "source": [
    "print(g_Cou)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "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": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_Cou.players[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 2, 2)"
      ]
     },
     "execution_count": 27,
     "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": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 28,
     "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": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 29,
     "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": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 30,
     "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": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Vector{Int64}:\n",
       " 1\n",
       " 2"
      ]
     },
     "execution_count": 31,
     "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": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_nash(g_MP, ([0.5, 0.5], [0.5, 0.5]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_nash(g_MP, (1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 34,
     "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": [
    "There are a few algorithms implemented to compute Nash equilibria:\n",
    "\n",
    "* Brute force  \n",
    "  Find all pure-action Nash equilibria of an $N$-player game (if any).\n",
    "* Sequential best response  \n",
    "  Find one pure-action Nash equilibrium of an $N$-player game (if any).\n",
    "* Support enumeration  \n",
    "  Find all mixed-action Nash equilibria of a two-player nondegenerate game.\n",
    "* lrsNash  \n",
    "  Find all mixed-action Nash equilibria (or equilibrium components) of a two-player game.\n",
    "\n",
    "For more variety of algorithms, one should 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)."
   ]
  },
  {
   "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`](https://quantecon.github.io/GameTheory.jl/latest/lib/computing_nash_equilibria.html#GameTheory.pure_nash-Tuple{NormalFormGame})."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "print_pure_nash_brute (generic function with 1 method)"
      ]
     },
     "execution_count": 35,
     "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": 36,
   "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": 37,
   "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": 38,
   "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": 39,
   "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": 40,
   "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": 41,
   "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": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "sequential_best_response (generic function with 1 method)"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function sequential_best_response(g::NormalFormGame{N};\n",
    "                                  init_actions::Vector{Int}=ones(Int, N),\n",
    "                                  tie_breaking=:smallest,\n",
    "                                  verbose=true) where N\n",
    "    a = copy(init_actions)\n",
    "    if verbose\n",
    "        println(\"init_actions: $a\")\n",
    "    end\n",
    "    \n",
    "    new_a = Array{Int}(undef, N)\n",
    "    max_iter = prod(g.nums_actions)\n",
    "    \n",
    "    for t in 1:max_iter\n",
    "        copyto!(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",
    "            copyto!(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": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13×13×13 NormalFormGame{3, Int64}"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a, c = 80, 20\n",
    "N = 3\n",
    "q_grid_size = 13\n",
    "q_grid = range(0, step=div(a-c, q_grid_size-1), length=q_grid_size)  # [0, 5, 10, ..., 60]\n",
    "g_Cou = cournot(a, c, Val(N), q_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "scrolled": true
   },
   "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, 15, 15]\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": 45,
   "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 Vector{Int64}:\n",
       " 4\n",
       " 4\n",
       " 4"
      ]
     },
     "execution_count": 45,
     "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": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 46,
     "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": 47,
   "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": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "61×61×61×61 NormalFormGame{4, Int64}"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N = 4\n",
    "q_grid_size = 61\n",
    "q_grid = range(0, step=div(a-c, q_grid_size-1), length=q_grid_size)  # [0, 1, 2, ..., 60]\n",
    "g_Cou = cournot(a, c, Val(N), q_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "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 Vector{Int64}:\n",
       " 13\n",
       " 13\n",
       " 13\n",
       " 13"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequential_best_response(g_Cou)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "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 Vector{Int64}:\n",
       " 13\n",
       " 13\n",
       " 13\n",
       " 13"
      ]
     },
     "execution_count": 50,
     "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": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2×2 NormalFormGame{2, Float64}:\n",
      " [1.0, -1.0]  [-1.0, 1.0]\n",
      " [-1.0, 1.0]  [1.0, -1.0]"
     ]
    }
   ],
   "source": [
    "print(g_MP)  # Matching Pennies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "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 Vector{Int64}:\n",
       " 2\n",
       " 1"
      ]
     },
     "execution_count": 52,
     "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`](https://quantecon.github.io/GameTheory.jl/latest/lib/computing_nash_equilibria.html#GameTheory.support_enumeration-Union{Tuple{NormalFormGame{2,%20T}},%20Tuple{T}}%20where%20T),\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": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1-element Vector{Tuple{Vector{Float64}, Vector{Float64}}}:\n",
       " ([0.5, 0.5], [0.5, 0.5])"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support_enumeration(g_MP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Coordination game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Vector{Tuple{Vector{Float64}, Vector{Float64}}}:\n",
       " ([1.0, 0.0], [1.0, 0.0])\n",
       " ([0.0, 1.0], [0.0, 1.0])\n",
       " ([0.6666666666666666, 0.3333333333333333], [0.6666666666666666, 0.3333333333333333])"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support_enumeration(g_Coo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rock-Paper-Scissors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1-element Vector{Tuple{Vector{Float64}, Vector{Float64}}}:\n",
       " ([0.3333333333333333, 0.3333333333333333, 0.3333333333333333], [0.3333333333333333, 0.3333333333333333, 0.3333333333333333])"
      ]
     },
     "execution_count": 55,
     "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": 56,
   "metadata": {},
   "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": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "75"
      ]
     },
     "execution_count": 57,
     "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": {},
   "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": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "all_pay_auction (generic function with 1 method)"
      ]
     },
     "execution_count": 58,
     "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}(undef, nums_actions)\n",
    "    num_ties = 0\n",
    "    for bids in CartesianIndices(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": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 2\n",
    "c = 5  # odd\n",
    "r = 8;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6×6 NormalFormGame{2, Float64}:\n",
      " [0.0, 0.0]  [0.0, 7.0]    [0.0, 6.0]    [0.0, 5.0]    [0.0, 4.0]    [0.0, 3.0]\n",
      " [7.0, 0.0]  [-1.0, -1.0]  [-1.0, 6.0]   [-1.0, 5.0]   [-1.0, 4.0]   [-1.0, 3.0]\n",
      " [6.0, 0.0]  [6.0, -1.0]   [-2.0, -2.0]  [-2.0, 5.0]   [-2.0, 4.0]   [-2.0, 3.0]\n",
      " [5.0, 0.0]  [5.0, -1.0]   [5.0, -2.0]   [-3.0, -3.0]  [-3.0, 4.0]   [-3.0, 3.0]\n",
      " [4.0, 0.0]  [4.0, -1.0]   [4.0, -2.0]   [4.0, -3.0]   [-4.0, -4.0]  [-4.0, 3.0]\n",
      " [3.0, 0.0]  [3.0, -1.0]   [3.0, -2.0]   [3.0, -3.0]   [3.0, -4.0]   [-5.0, -5.0]"
     ]
    }
   ],
   "source": [
    "g_APA_odd = all_pay_auction(r, c, Val(N))\n",
    "print(g_APA_odd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Clearly, this game has no pure-action Nash equilibrium.\n",
    "Indeed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Tuple{Int64, Int64}[]"
      ]
     },
     "execution_count": 61,
     "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": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Vector{Tuple{Vector{Float64}, Vector{Float64}}}:\n",
       " ([0.5, 0.0, 0.25000000000000006, 0.0, 0.24999999999999994, 0.0], [0.0, 0.25, 0.0, 0.25000000000000006, 0.0, 0.5])\n",
       " ([0.0, 0.25, 0.0, 0.25000000000000006, 0.0, 0.5], [0.5, 0.0, 0.25000000000000006, 0.0, 0.24999999999999994, 0.0])\n",
       " ([0.125, 0.125, 0.12500000000000003, 0.12499999999999997, 0.125, 0.375], [0.125, 0.125, 0.12500000000000003, 0.12499999999999997, 0.125, 0.375])"
      ]
     },
     "execution_count": 62,
     "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": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1-element Vector{Tuple{Vector{Float64}, Vector{Float64}}}:\n",
       " ([0.125, 0.125, 0.12500000000000003, 0.12499999999999997, 0.125, 0.12500000000000003, 0.25], [0.125, 0.125, 0.12500000000000003, 0.12499999999999997, 0.125, 0.12500000000000003, 0.25])"
      ]
     },
     "execution_count": 63,
     "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": [
    "Note:\n",
    "`support_enumeration` is executed with exact arithmetic for input games with `Rational` payoffs.\n",
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 NormalFormGame{2, Rational{Int64}}"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_Coo_rational = NormalFormGame(Rational{Int}, g_Coo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2×2 NormalFormGame{2, Rational{Int64}}:\n",
      " Rational{Int64}[4//1, 4//1]  Rational{Int64}[0//1, 3//1]\n",
      " Rational{Int64}[3//1, 0//1]  Rational{Int64}[2//1, 2//1]"
     ]
    }
   ],
   "source": [
    "print(g_Coo_rational)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Vector{Tuple{Vector{Rational{Int64}}, Vector{Rational{Int64}}}}:\n",
       " ([1//1, 0//1], [1//1, 0//1])\n",
       " ([0//1, 1//1], [0//1, 1//1])\n",
       " ([2//3, 1//3], [2//3, 1//3])"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support_enumeration(g_Coo_rational)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6×6 NormalFormGame{2, Rational{Int64}}"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N = 2\n",
    "c = 5  # odd\n",
    "r = 8//1  # Rational\n",
    "g_APA_odd_rational = all_pay_auction(r, c, Val(N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Vector{Tuple{Vector{Rational{Int64}}, Vector{Rational{Int64}}}}:\n",
       " ([1//2, 0//1, 1//4, 0//1, 1//4, 0//1], [0//1, 1//4, 0//1, 1//4, 0//1, 1//2])\n",
       " ([0//1, 1//4, 0//1, 1//4, 0//1, 1//2], [1//2, 0//1, 1//4, 0//1, 1//4, 0//1])\n",
       " ([1//8, 1//8, 1//8, 1//8, 1//8, 3//8], [1//8, 1//8, 1//8, 1//8, 1//8, 3//8])"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support_enumeration(g_APA_odd_rational)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### lrsNash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The routine [`lsrnash`](https://quantecon.github.io/GameTheory.jl/latest/lib/computing_nash_equilibria.html#GameTheory.lrsnash-Tuple{NormalFormGame{2,%20%3C:Union{Int64,%20Rational}}}) calls the Nash equilibrium computation routine in [`lrslib`](http://cgm.cs.mcgill.ca/~avis/C/lrs.html) (through its Julia wrapper [`LRSLib.jl`](https://github.com/JuliaPolyhedra/LRSLib.jl)), which computes in exact arithmetic all extreme mixed-action Nash equilibria of a two-player game with Integer or Rational payoffs, based on the \"lexicographic reverse search\" vertex enumeration algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2×2 NormalFormGame{2, Int64}:\n",
      " [4, 4]  [0, 3]\n",
      " [3, 0]  [2, 2]"
     ]
    }
   ],
   "source": [
    "print(g_Coo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Vector{Tuple{Vector{Rational{BigInt}}, Vector{Rational{BigInt}}}}:\n",
       " ([2//3, 1//3], [2//3, 1//3])\n",
       " ([0//1, 1//1], [0//1, 1//1])\n",
       " ([1//1, 0//1], [1//1, 0//1])"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lrsnash(g_Coo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "75"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length(lrsnash(g_vonStengel))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Vector{Tuple{Vector{Rational{BigInt}}, Vector{Rational{BigInt}}}}:\n",
       " ([1//8, 1//8, 1//8, 1//8, 1//8, 3//8], [1//8, 1//8, 1//8, 1//8, 1//8, 3//8])\n",
       " ([1//2, 0//1, 1//4, 0//1, 1//4, 0//1], [0//1, 1//4, 0//1, 1//4, 0//1, 1//2])\n",
       " ([0//1, 1//4, 0//1, 1//4, 0//1, 1//2], [1//2, 0//1, 1//4, 0//1, 1//4, 0//1])"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lrsnash(g_APA_odd_rational)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Further Reading\n",
    "\n",
    "* [A Recursive Formulation of Repeated Games](https://nbviewer.jupyter.org/github/QuantEcon/QuantEcon.notebooks/blob/main/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": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "kernelspec": {
   "display_name": "Julia 1.8.5",
   "language": "julia",
   "name": "julia-1.8"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}