{ "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 }