{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Tools for Game Theory in Games.jl" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Daisuke Oyama** \n", "*Faculty of Economics, University of Tokyo*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This notebook demonstrates the functionalities of [Games.jl](https://github.com/QuantEcon/Games.jl)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first time you run this notebook,\n", "you need to install the Games.jl package by removing the \"#\" below:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Pkg.clone(\"https://github.com/QuantEcon/Games.jl\")" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "using Games" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Normal Form Games" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An $N$-player *normal form game* is a triplet $g = (I, (A_i)_{i \\in I}, (u_i)_{i \\in I})$ where\n", "\n", "* $I = \\{1, \\ldots, N\\}$ is the set of players,\n", "* $A_i = \\{1, \\ldots, n_i\\}$ is the set of actions of player $i \\in I$, and\n", "* $u_i \\colon A_i \\times A_{i+1} \\times \\cdots \\times A_{i+N-1} \\to \\mathbb{R}$\n", " is the payoff function of player $i \\in I$,\n", "\n", "where $i+j$ is understood modulo $N$.\n", "\n", "Note that we adopt the convention that the $1$-st argument of the payoff function $u_i$ is\n", "player $i$'s own action\n", "and the $j$-th argument, $j = 2, \\ldots, N$, is player ($i+j-1$)'s action (modulo $N$)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In our package,\n", "a normal form game and a player are represented by\n", "the types `NormalFormGame` and `Player`, respectively.\n", "\n", "A `Player` carries the player's payoff function and implements in particular\n", "a method that returns the best response action(s) given an action of the opponent player,\n", "or a profile of actions of the opponents if there are more than one.\n", "\n", "A `NormalFormGame` is in effect a container of `Player` instances." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Creating a `NormalFormGame`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There are several ways to create a `NormalFormGame` instance." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first is to pass an array of payoffs for all the players, i.e.,\n", "an $(N+1)$-dimenstional array of shape $(n_1, \\ldots, n_N, N)$\n", "whose $(a_1, \\ldots, a_N)$-entry contains an array of the $N$ payoff values\n", "for the action profile $(a_1, \\ldots, a_N)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As an example, consider the following game (\"**Matching Pennies**\"):\n", "\n", "$\n", "\\begin{bmatrix}\n", "1, -1 & -1, 1 \\\\\n", "-1, 1 & 1, -1\n", "\\end{bmatrix}\n", "$" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 NormalFormGame{2,Float64}" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "matching_pennies_bimatrix = Array{Float64}(2, 2, 2)\n", "matching_pennies_bimatrix[1, 1, :] = [1, -1] # payoff profile for action profile (1, 1)\n", "matching_pennies_bimatrix[1, 2, :] = [-1, 1]\n", "matching_pennies_bimatrix[2, 1, :] = [-1, 1]\n", "matching_pennies_bimatrix[2, 2, :] = [1, -1]\n", "g_MP = NormalFormGame(matching_pennies_bimatrix)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Player{2,Float64}:\n", " 1.0 -1.0\n", " -1.0 1.0" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_MP.players[1] # Player instance for player 1" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Player{2,Float64}:\n", " -1.0 1.0\n", " 1.0 -1.0" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_MP.players[2] # Player instance for player 2" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{Float64,2}:\n", " 1.0 -1.0\n", " -1.0 1.0" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_MP.players[1].payoff_array # Player 1's payoff array" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{Float64,2}:\n", " -1.0 1.0\n", " 1.0 -1.0" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_MP.players[2].payoff_array # Player 2's payoff array" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 1.0\n", " -1.0" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_MP[1, 1] # payoff profile for action profile (1, 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If a square matrix (2-dimensional array) is given,\n", "then it is considered to be a symmetric two-player game.\n", "\n", "Consider the following game (symmetric $2 \\times 2$ \"**Coordination Game**\"):\n", "\n", "$\n", "\\begin{bmatrix}\n", "4, 4 & 0, 3 \\\\\n", "3, 0 & 2, 2\n", "\\end{bmatrix}\n", "$" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 NormalFormGame{2,Int64}" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "coordination_game_matrix = [4 0;\n", " 3 2] # square matrix\n", "g_Coo = NormalFormGame(coordination_game_matrix)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{Int64,2}:\n", " 4 0\n", " 3 2" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_Coo.players[1].payoff_array # Player 1's payoff array" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{Int64,2}:\n", " 4 0\n", " 3 2" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_Coo.players[2].payoff_array # Player 2's payoff array" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Another example (\"**Rock-Paper-Scissors**\"):\n", "\n", "$\n", "\\begin{bmatrix}\n", " 0, 0 & -1, 1 & 1, -1 \\\\\n", " 1, -1 & 0, 0 & -1, 1 \\\\\n", "-1, 1 & 1, -1 & 0, 0\n", "\\end{bmatrix}\n", "$" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 NormalFormGame{2,Int64}" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "RPS_matrix = [0 -1 1;\n", " 1 0 -1;\n", " -1 1 0]\n", "g_RPS = NormalFormGame(RPS_matrix)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The second is to specify the sizes of the action sets of the players\n", "to create a `NormalFormGame` instance filled with payoff zeros,\n", "and then set the payoff values to each entry.\n", "\n", "Let us construct the following game (\"**Prisoners' Dilemma**\"):\n", "\n", "$\n", "\\begin{bmatrix}\n", "1, 1 & -2, 3 \\\\\n", "3, -2 & 0, 0\n", "\\end{bmatrix}\n", "$" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": true }, "outputs": [], "source": [ "g_PD = NormalFormGame((2, 2)) # There are 2 players, each of whom has 2 actions\n", "g_PD[1, 1] = [1, 1]\n", "g_PD[1, 2] = [-2, 3]\n", "g_PD[2, 1] = [3, -2]\n", "g_PD[2, 2] = [0, 0];" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 NormalFormGame{2,Float64}" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_PD" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{Float64,2}:\n", " 1.0 -2.0\n", " 3.0 0.0" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_PD.players[1].payoff_array" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, a `NormalFormGame` instance can be constructed by giving an array of `Player` instances,\n", "as explained in the next section." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Creating a `Player`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A `Player` instance is created by passing an array of dimension $N$\n", "that represents the player's payoff function (\"payoff array\").\n", "\n", "Consider the following game (a variant of \"**Battle of the Sexes**\"):\n", "\n", "$\n", "\\begin{bmatrix}\n", "3, 2 & 1, 1 \\\\\n", "0, 0 & 2, 3\n", "\\end{bmatrix}\n", "$" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": true }, "outputs": [], "source": [ "player1 = Player([3 1; 0 2])\n", "player2 = Player([2 0; 1 3]);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Beware that in `payoff_array[h, k]`, `h` refers to the player's own action,\n", "while `k` refers to the opponent player's action." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{Int64,2}:\n", " 3 1\n", " 0 2" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "player1.payoff_array" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{Int64,2}:\n", " 2 0\n", " 1 3" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "player2.payoff_array" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Passing an array of Player instances is the third way to create a `NormalFormGame` instance:" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 NormalFormGame{2,Int64}" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_BoS = NormalFormGame((player1, player2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### More than two players" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Games with more than two players are also supported." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us consider the following version of $N$-player **Cournot Game**.\n", "\n", "There are $N$ firms (players) which produce a homogeneous good\n", "with common constant marginal cost $c \\geq 0$.\n", "Each firm $i$ simultaneously determines the quantity $q_i \\geq 0$ (action) of the good to produce.\n", "The inverse demand function is given by the linear function $P(Q) = a - Q$, $a > 0$,\n", "where $Q = q_1 + \\cdots + q_N$ is the aggregate supply.\n", "Then the profit (payoff) for firm $i$ is given by\n", "$$\n", "u_i(q_i, q_{i+1}, \\ldots, q_{i+N-1})\n", "= P(Q) q_i - c q_i\n", "= \\left(a - c - \\sum_{j \\neq i} q_j - q_i\\right) q_i.\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Theoretically, the set of actions, i.e., available quantities, may be\n", "the set of all nonnegative real numbers $\\mathbb{R}_+$\n", "(or a bounded interval $[0, \\bar{q}]$ with some upper bound $\\bar{q}$),\n", "but for computation on a computer we have to discretize the action space\n", "and only allow for finitely many grid points.\n", "\n", "The following script creates a `NormalFormGame` instance of the Cournot game as described above,\n", "assuming that the (common) grid of possible quantity values is stored in an array `q_grid`." ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "cournot (generic function with 1 method)" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function cournot(a::Real, c::Real, ::Val{N}, q_grid::Vector{T}) where {N,T<:Real}\n", " nums_actions = ntuple(x->length(q_grid), Val(N))\n", " S = promote_type(typeof(a), typeof(c), T)\n", " payoff_array= Array{S}(nums_actions)\n", " for I in CartesianRange(nums_actions)\n", " Q = zero(S)\n", " for i in 1:N\n", " Q += q_grid[I[i]]\n", " end\n", " payoff_array[I] = (a - c - Q) * q_grid[I[1]]\n", " end\n", " players = ntuple(x->Player(payoff_array), Val(N))\n", " return NormalFormGame(players)\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here's a simple example with three firms,\n", "marginal cost $20$, and inverse demand function $80 - Q$,\n", "where the feasible quantity values are assumed to be $10$ and $15$." ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2×2 NormalFormGame{3,Int64}" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a, c = 80, 20\n", "N = 3\n", "q_grid = [10, 15] # [1/3 of Monopoly quantity, Nash equilibrium quantity]\n", "\n", "g_Cou = cournot(a, c, Val(N), q_grid)" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2×2 Player{3,Int64}:\n", "[:, :, 1] =\n", " 300 250\n", " 375 300\n", "\n", "[:, :, 2] =\n", " 250 200\n", " 300 225" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_Cou.players[1]" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(2, 2, 2)" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_Cou.nums_actions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Nash Equilibrium" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A *Nash equilibrium* of a normal form game is a profile of actions\n", "where the action of each player is a best response to the others'." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The `Player` object has methods `best_response` and `best_responses`.\n", "\n", "Consider the Matching Pennies game `g_MP` defined above.\n", "For example, player 1's best response to the opponent's action 2 is:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/html": [ "2" ], "text/plain": [ "2" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "best_response(g_MP.players[1], 2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Player 1's best responses to the opponent's mixed action `[0.5, 0.5]`\n", "(we know they are 1 and 2):" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/html": [ "1" ], "text/plain": [ "1" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# By default, returns the best response action with the smallest index\n", "best_response(g_MP.players[1], [0.5, 0.5])" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/html": [ "2" ], "text/plain": [ "2" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# With tie_breaking='random', returns randomly one of the best responses\n", "best_response(g_MP.players[1], [0.5, 0.5], tie_breaking=\"random\") # Try several times" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`best_responses` returns an array of all the best responses:" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Int64,1}:\n", " 1\n", " 2" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "best_responses(g_MP.players[1], [0.5, 0.5])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For this game, we know that `([0.5, 0.5], [0.5, 0.5])` is a (unique) Nash equilibrium." ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/html": [ "true" ], "text/plain": [ "true" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_nash(g_MP, ([0.5, 0.5], [0.5, 0.5]))" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/html": [ "false" ], "text/plain": [ "false" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_nash(g_MP, (1, 1))" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "false" ], "text/plain": [ "false" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_nash(g_MP, ([1., 0.], [0.5, 0.5]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Finding Nash equilibria" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Our package does not have sophisticated algorithms to compute Nash equilibria (yet)...\n", "One might look at the [`game_theory`](http://quanteconpy.readthedocs.io/en/latest/game_theory.html) module in [QuantEcon.py](https://github.com/QuantEcon/QuantEcon.py) or [Gambit](http://www.gambit-project.org),\n", "which implement several such algorithms." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Brute force" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For small games, we can find pure action Nash equilibria by brute force,\n", "by calling the method [`pure_nash`](http://quantecon.github.io/Games.jl/latest/lib/computing_nash_equilibria.html#pure_nash-1)." ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "print_pure_nash_brute (generic function with 1 method)" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function print_pure_nash_brute(g::NormalFormGame)\n", " NEs = pure_nash(g)\n", " num_NEs = length(NEs)\n", " if num_NEs == 0\n", " msg = \"no pure Nash equilibrium\"\n", " elseif num_NEs == 1\n", " msg = \"1 pure Nash equilibrium:\\n$(NEs[1])\"\n", " else\n", " msg = \"$num_NEs pure Nash equilibria:\\n\"\n", " for (i, NE) in enumerate(NEs)\n", " i < num_NEs ? msg *= \"$NE,\" : msg *= \"$NE\"\n", " end\n", " end\n", " println(join([\"The game has \", msg]))\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Matching Pennies:" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The game has no pure Nash equilibrium\n" ] } ], "source": [ "print_pure_nash_brute(g_MP)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Coordination game:" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The game has 2 pure Nash equilibria:\n", "(1, 1),(2, 2)\n" ] } ], "source": [ "print_pure_nash_brute(g_Coo)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Rock-Paper-Scissors:" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The game has no pure Nash equilibrium\n" ] } ], "source": [ "print_pure_nash_brute(g_RPS)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Battle of the Sexes:" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The game has 2 pure Nash equilibria:\n", "(1, 1),(2, 2)\n" ] } ], "source": [ "print_pure_nash_brute(g_BoS)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Prisoners' Dillema:" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The game has 1 pure Nash equilibrium:\n", "(2, 2)\n" ] } ], "source": [ "print_pure_nash_brute(g_PD)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Cournot game:" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The game has 1 pure Nash equilibrium:\n", "(2, 2, 2)\n" ] } ], "source": [ "print_pure_nash_brute(g_Cou)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Sequential best response" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In some games, such as \"supermodular games\" and \"potential games\",\n", "the process of sequential best responses converges to a Nash equilibrium." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here's a script to find *one* pure Nash equilibrium by sequential best response, if it converges." ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "sequential_best_response (generic function with 1 method)" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function sequential_best_response(g::NormalFormGame;\n", " init_actions::Union{Vector{Int},Void}=nothing,\n", " tie_breaking=\"smallest\",\n", " verbose=true)\n", " N = num_players(g)\n", " a = Array{Int}(N)\n", " if init_actions == nothing\n", " init_actions = ones(Int, N)\n", " end\n", " copy!(a, init_actions)\n", " if verbose\n", " println(\"init_actions: $a\")\n", " end\n", " \n", " new_a = Array{Int}(N)\n", " max_iter = prod(g.nums_actions)\n", " \n", " for t in 1:max_iter\n", " copy!(new_a, a)\n", " for (i, player) in enumerate(g.players)\n", " if N == 2\n", " a_except_i = new_a[3-i]\n", " else\n", " a_except_i = (new_a[i+1:N]..., new_a[1:i-1]...)\n", " end\n", " new_a[i] = best_response(player, a_except_i,\n", " tie_breaking=tie_breaking)\n", " if verbose\n", " println(\"player $i: $new_a\")\n", " end\n", " end\n", " if new_a == a\n", " return a\n", " else\n", " copy!(a, new_a)\n", " end\n", " end\n", " \n", " println(\"No pure Nash equilibrium found\")\n", " return a\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A Cournot game with linear demand is known to be a potential game,\n", "for which sequential best response converges to a Nash equilibrium.\n", "\n", "Let us try a bigger instance:" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "13×13×13 NormalFormGame{3,Float64}" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a, c = 80, 20\n", "N = 3\n", "q_grid = collect(linspace(0, a-c, 13)) # [0, 5, 10, ..., 60]\n", "g_Cou = cournot(a, c, Val(N), q_grid)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "init_actions: [1, 1, 1]\n", "player 1: [7, 1, 1]\n", "player 2: [7, 4, 1]\n", "player 3: [7, 4, 2]\n", "player 1: [5, 4, 2]\n", "player 2: [5, 4, 2]\n", "player 3: [5, 4, 3]\n", "player 1: [4, 4, 3]\n", "player 2: [4, 4, 3]\n", "player 3: [4, 4, 4]\n", "player 1: [4, 4, 4]\n", "player 2: [4, 4, 4]\n", "player 3: [4, 4, 4]\n", "Nash equilibrium indices: [4, 4, 4]\n", "Nash equilibrium quantities: [15.0, 15.0, 15.0]\n" ] } ], "source": [ "a_star = sequential_best_response(g_Cou) # By default, start with (1, 1, 1)\n", "println(\"Nash equilibrium indices: $a_star\")\n", "println(\"Nash equilibrium quantities: $(q_grid[a_star])\")" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "init_actions: [13, 13, 13]\n", "player 1: [1, 13, 13]\n", "player 2: [1, 1, 13]\n", "player 3: [1, 1, 7]\n", "player 1: [4, 1, 7]\n", "player 2: [4, 2, 7]\n", "player 3: [4, 2, 5]\n", "player 1: [4, 2, 5]\n", "player 2: [4, 3, 5]\n", "player 3: [4, 3, 4]\n", "player 1: [4, 3, 4]\n", "player 2: [4, 4, 4]\n", "player 3: [4, 4, 4]\n", "player 1: [4, 4, 4]\n", "player 2: [4, 4, 4]\n", "player 3: [4, 4, 4]\n" ] }, { "data": { "text/plain": [ "3-element Array{Int64,1}:\n", " 4\n", " 4\n", " 4" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Start with the largest actions (13, 13, 13)\n", "sequential_best_response(g_Cou, init_actions=[13, 13, 13])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The limit action profile is indeed a Nash equilibrium:" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/html": [ "true" ], "text/plain": [ "true" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_nash(g_Cou, tuple(a_star...))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In fact, the game has other Nash equilibria\n", "(because of our choice of grid points and parameter values):" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The game has 7 pure Nash equilibria:\n", "(5, 4, 3),(4, 5, 3),(5, 3, 4),(4, 4, 4),(3, 5, 4),(4, 3, 5),(3, 4, 5)\n" ] } ], "source": [ "print_pure_nash_brute(g_Cou)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Make it bigger:" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "61×61×61×61 NormalFormGame{4,Float64}" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "N = 4\n", "q_grid = collect(linspace(0, a-c, 61)) # [0, 1, 2, ..., 60]\n", "g_Cou = cournot(a, c, Val(N), q_grid)" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "init_actions: [1, 1, 1, 1]\n", "player 1: [31, 1, 1, 1]\n", "player 2: [31, 16, 1, 1]\n", "player 3: [31, 16, 8, 1]\n", "player 4: [31, 16, 8, 5]\n", "player 1: [18, 16, 8, 5]\n", "player 2: [18, 17, 8, 5]\n", "player 3: [18, 17, 12, 5]\n", "player 4: [18, 17, 12, 9]\n", "player 1: [13, 17, 12, 9]\n", "player 2: [13, 15, 12, 9]\n", "player 3: [13, 15, 14, 9]\n", "player 4: [13, 15, 14, 11]\n", "player 1: [12, 15, 14, 11]\n", "player 2: [12, 14, 14, 11]\n", "player 3: [12, 14, 14, 11]\n", "player 4: [12, 14, 14, 12]\n", "player 1: [12, 14, 14, 12]\n", "player 2: [12, 13, 14, 12]\n", "player 3: [12, 13, 14, 12]\n", "player 4: [12, 13, 14, 13]\n", "player 1: [12, 13, 14, 13]\n", "player 2: [12, 13, 14, 13]\n", "player 3: [12, 13, 13, 13]\n", "player 4: [12, 13, 13, 13]\n", "player 1: [13, 13, 13, 13]\n", "player 2: [13, 13, 13, 13]\n", "player 3: [13, 13, 13, 13]\n", "player 4: [13, 13, 13, 13]\n", "player 1: [13, 13, 13, 13]\n", "player 2: [13, 13, 13, 13]\n", "player 3: [13, 13, 13, 13]\n", "player 4: [13, 13, 13, 13]\n" ] }, { "data": { "text/plain": [ "4-element Array{Int64,1}:\n", " 13\n", " 13\n", " 13\n", " 13" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sequential_best_response(g_Cou)" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "init_actions: [1, 1, 1, 31]\n", "player 1: [16, 1, 1, 31]\n", "player 2: [16, 8, 1, 31]\n", "player 3: [16, 8, 5, 31]\n", "player 4: [16, 8, 5, 18]\n", "player 1: [17, 8, 5, 18]\n", "player 2: [17, 12, 5, 18]\n", "player 3: [17, 12, 9, 18]\n", "player 4: [17, 12, 9, 13]\n", "player 1: [15, 12, 9, 13]\n", "player 2: [15, 14, 9, 13]\n", "player 3: [15, 14, 11, 13]\n", "player 4: [15, 14, 11, 12]\n", "player 1: [14, 14, 11, 12]\n", "player 2: [14, 14, 11, 12]\n", "player 3: [14, 14, 12, 12]\n", "player 4: [14, 14, 12, 12]\n", "player 1: [13, 14, 12, 12]\n", "player 2: [13, 14, 12, 12]\n", "player 3: [13, 14, 13, 12]\n", "player 4: [13, 14, 13, 12]\n", "player 1: [13, 14, 13, 12]\n", "player 2: [13, 13, 13, 12]\n", "player 3: [13, 13, 13, 12]\n", "player 4: [13, 13, 13, 13]\n", "player 1: [13, 13, 13, 13]\n", "player 2: [13, 13, 13, 13]\n", "player 3: [13, 13, 13, 13]\n", "player 4: [13, 13, 13, 13]\n" ] }, { "data": { "text/plain": [ "4-element Array{Int64,1}:\n", " 13\n", " 13\n", " 13\n", " 13" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sequential_best_response(g_Cou, init_actions=[1, 1, 1, 31])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Sequential best response does not converge in all games:" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2×2 NormalFormGame{2,Float64}" ] } ], "source": [ "print(g_MP) # Matching Pennies" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "init_actions: [1, 1]\n", "player 1: [1, 1]\n", "player 2: [1, 2]\n", "player 1: [2, 2]\n", "player 2: [2, 1]\n", "player 1: [1, 1]\n", "player 2: [1, 2]\n", "player 1: [2, 2]\n", "player 2: [2, 1]\n", "No pure Nash equilibrium found\n" ] }, { "data": { "text/plain": [ "2-element Array{Int64,1}:\n", " 2\n", " 1" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sequential_best_response(g_MP)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Support enumeration" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The routine [`support_enumeration`](http://quantecon.github.io/Games.jl/latest/lib/computing_nash_equilibria.html#support_enumeration-1),\n", "which is for two-player games, visits all equal-size support pairs\n", "and checks whether each pair has a Nash equilibrium (in mixed actions) by the indifference condition.\n", "(This should thus be used only for small games.)\n", "For nondegenerate games, this routine returns all the Nash equilibria." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Matching Pennies:" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1-element Array{Tuple{Array{Real,1},Array{Real,1}},1}:\n", " (Real[0.5, 0.5], Real[0.5, 0.5])" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "support_enumeration(g_MP)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Coordination game:" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element Array{Tuple{Array{Real,1},Array{Real,1}},1}:\n", " (Real[1.0, 0.0], Real[1.0, 0.0]) \n", " (Real[0.0, 1.0], Real[0.0, 1.0]) \n", " (Real[0.666667, 0.333333], Real[0.666667, 0.333333])" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "support_enumeration(g_Coo)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Rock-Paper-Scissors:" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "1-element Array{Tuple{Array{Real,1},Array{Real,1}},1}:\n", " (Real[0.333333, 0.333333, 0.333333], Real[0.333333, 0.333333, 0.333333])" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "support_enumeration(g_RPS)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider the $6 \\times 6$ game by von Stengel (1997), page 12:" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "collapsed": true }, "outputs": [], "source": [ "player1 = Player(\n", " [ 9504 -660 19976 -20526 1776 -8976;\n", " -111771 31680 -130944 168124 -8514 52764;\n", " 397584 -113850 451176 -586476 29216 -178761;\n", " 171204 -45936 208626 -263076 14124 -84436;\n", " 1303104 -453420 1227336 -1718376 72336 -461736;\n", " 737154 -227040 774576 -1039236 48081 -300036]\n", ")\n", "\n", "player2 = Player(\n", " [ 72336 -461736 1227336 -1718376 1303104 -453420;\n", " 48081 -300036 774576 -1039236 737154 -227040;\n", " 29216 -178761 451176 -586476 397584 -113850;\n", " 14124 -84436 208626 -263076 171204 -45936;\n", " 1776 -8976 19976 -20526 9504 -660;\n", " -8514 52764 -130944 168124 -111771 31680]\n", ")\n", "\n", "g_vonStengel = NormalFormGame(player1, player2);" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/html": [ "75" ], "text/plain": [ "75" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "length(support_enumeration(g_vonStengel))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that the $n \\times n$ game where the payoff matrices are given by the identy matrix\n", "has $2^n−1$ equilibria.\n", "It had been conjectured that this is the maximum number of equilibria of\n", "any nondegenerate $n \\times n$ game.\n", "The game above, the number of whose equilibria is $75 > 2^6 - 1 = 63$,\n", "was presented as a counter-example to this conjecture." ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "Next, let us study the **All-Pay Acution**,\n", "where, unlike standard auctions,\n", "bidders pay their bids regardless of whether or not they win.\n", "Situations modeled as all-pay auctions include\n", "job promotion, R&D, and rent seeking competitions, among others.\n", "\n", "Here we consider a version of All-Pay Auction with complete information,\n", "symmetric bidders, discrete bids, bid caps, and \"full dissipation\"\n", "(where the prize is materialized if and only if\n", "there is only one bidder who makes a highest bid)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Specifically, each of $N$ players simultaneously bids an integer from $\\{0, 1, \\ldots, c\\}$,\n", "where $c$ is the common (integer) bid cap.\n", "If player $i$'s bid is higher than all the other players',\n", "then he receives the prize, whose value is $r$, common to all players,\n", "and pays his bid $b_i$.\n", "Otherwise, he pays $b_i$ and receives nothing (zero value).\n", "In particular, if there are more than one players who make the highest bid,\n", "the prize gets *fully dissipated* and all the players receive nothing.\n", "Thus, player $i$'s payoff function is\n", "$$\n", "u_i(b_i, b_{i+1}, \\ldots, b_{i+N-1}) =\n", "\\begin{cases}\n", "r - b_i & \\text{if $b_i > b_j$ for all $j \\neq i$}, \\\\ - b_i & \\text{otherwise}.\n", "\\end{cases}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The following is a script to construct a `NormalFormGame` instance\n", "for the All-Pay Auction game:" ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "all_pay_auction (generic function with 1 method)" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function all_pay_auction(r::T, c::Integer, ::Val{N};\n", " dissipation::Bool=true) where {N,T<:Real}\n", " nums_actions = ntuple(x->c+1, Val(N))\n", " S = typeof(zero(T)/one(T))\n", " payoff_array= Array{S}(nums_actions)\n", " num_ties = 0\n", " for bids in CartesianRange(nums_actions)\n", " payoff_array[bids] = -(bids[1]-1)\n", " num_ties = 1\n", " for j in 2:N\n", " if bids[j] > bids[1]\n", " num_ties = 0\n", " break\n", " elseif bids[j] == bids[1]\n", " if dissipation\n", " num_ties = 0\n", " break\n", " else\n", " num_ties += 1\n", " end\n", " end\n", " end\n", " if num_ties > 0\n", " payoff_array[bids] += r / num_ties\n", " end\n", " end\n", " players = ntuple(x->Player(payoff_array), Val(N))\n", " return NormalFormGame(players)\n", "end" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "collapsed": true }, "outputs": [], "source": [ "N = 2\n", "c = 5 # odd\n", "r = 8;" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6×6 Player{2,Float64}:\n", " 0.0 0.0 0.0 0.0 0.0 0.0\n", " 7.0 -1.0 -1.0 -1.0 -1.0 -1.0\n", " 6.0 6.0 -2.0 -2.0 -2.0 -2.0\n", " 5.0 5.0 5.0 -3.0 -3.0 -3.0\n", " 4.0 4.0 4.0 4.0 -4.0 -4.0\n", " 3.0 3.0 3.0 3.0 3.0 -5.0" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g_APA_odd = all_pay_auction(r, c, Val(N))\n", "g_APA_odd.players[1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Clearly, this game has no pure-action Nash equilibrium.\n", "Indeed:" ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0-element Array{Tuple{Int64,Int64},1}" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pure_nash(g_APA_odd)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As pointed out by Dechenaux et al. (2006),\n", "there are three Nash equilibria when the bid cap `c` is odd\n", "(so that there are an even number of actions for each player):" ] }, { "cell_type": "code", "execution_count": 58, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element Array{Tuple{Array{Real,1},Array{Real,1}},1}:\n", " (Real[0.5, 0.0, 0.25, 0.0, 0.25, 0.0], Real[0.0, 0.25, 0.0, 0.25, 0.0, 0.5]) \n", " (Real[0.0, 0.25, 0.0, 0.25, 0.0, 0.5], Real[0.5, 0.0, 0.25, 0.0, 0.25, 0.0]) \n", " (Real[0.125, 0.125, 0.125, 0.125, 0.125, 0.375], Real[0.125, 0.125, 0.125, 0.125, 0.125, 0.375])" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "support_enumeration(g_APA_odd)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In addition to a symmetric, totally mixed equilibrium (the third),\n", "there are two asymmetric, \"alternating\" equilibria (the first and the second)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If `e` is even, there is a unique equilibrium, which is symmetric and totally mixed.\n", "For example:" ] }, { "cell_type": "code", "execution_count": 59, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1-element Array{Tuple{Array{Real,1},Array{Real,1}},1}:\n", " (Real[0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.25], Real[0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.25])" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c = 6 # even\n", "g_APA_even = all_pay_auction(r, c, Val(N))\n", "support_enumeration(g_APA_even)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Further Reading\n", "\n", "* [A Recursive Formulation of Repeated Games](https://nbviewer.jupyter.org/github/QuantEcon/QuantEcon.notebooks/blob/master/recursive_repeated_games.ipynb)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## References\n", "\n", "* E. Dechenaux, D. Kovenock, and V. Lugovskyy (2006),\n", " \"Caps on bidding in all-pay auctions:\n", " Comments on the experiments of A. Rapoport and W. Amaldoss,\"\n", " Journal of Economic Behavior and Organization 61, 276-283.\n", "\n", "* B. von Stengel (1997),\n", " \"[New Lower Bounds for the Number of Equilibria in Bimatrix Games](http://www.maths.lse.ac.uk/personal/stengel/TEXTE/264.pdf).\"" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Julia 0.6.0", "language": "julia", "name": "julia-0.6" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "0.6.0" } }, "nbformat": 4, "nbformat_minor": 1 }