ipynb/daisuke_oyama-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": [
                            "1"
                        ]
                    },
                    "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/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": {},
            "outputs": [],
            "source": []
        }
    ],
    "metadata": {
        "@webio": {
            "lastCommId": null,
            "lastKernelId": null
        },
        "kernelspec": {
            "display_name": "Julia 1.8.3",
            "language": "julia",
            "name": "julia-1.8"
        },
        "language_info": {
            "file_extension": ".jl",
            "mimetype": "application/julia",
            "name": "julia",
            "version": "1.8.3"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 4
}