Skip to content

Instantly share code, notes, and snippets.

@cc7768
Created November 9, 2016 19:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cc7768/cbc9cddd15a49630d30ad2e45bfcb739 to your computer and use it in GitHub Desktop.
Save cc7768/cbc9cddd15a49630d30ad2e45bfcb739 to your computer and use it in GitHub Desktop.
Display the source blob
Display the rendered blob
Raw
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### A Recursive Formulation of Repeated Games\n",
"\n",
"**Authors**: Chase Coleman and Thomas Sargent\n",
"\n",
"This notebook describes Julia code that implements an algorithm for computing equilibrium values and associated equilibrium strategy profiles for repeated games with $N$ players and finite actions.\n",
"\n",
"The code builds on ideas of Abreu, Pearce, Stachetti (1986, 1990).\n",
"\n",
"It uses a numerical algorithm invented by Judd, Yeltekin, Conklin (2003).\n",
"\n",
"We focus on a particularly simple example, namely, a repeated prisoner's dilemma.\n",
"\n",
"Our friends Timothy Hills and Ben Tengelsen provided useful comments about detailed aspects of the algorithm.\n",
"\n",
"Note that the `Games` library is currently under development and is not a published Julia package -- This means that to get it, you'll need to run `Pkg.clone(\"https://github.com/QuantEcon/Games.jl.git\")`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"using Clp\n",
"using MathProgBase\n",
"using Games\n",
"using PlotlyJS"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Introduction\n",
"\n",
"Ideas in play in this notebook are a one-shot or stage **game** and its **Nash equilibria**; a **repeated game**\n",
"and the values associated with its **subgame perfect equilibria**; **backward induction** and **dynamic programming**; and **linear programming**\n",
"\n",
"Each of these concepts is worth studying in its own right\n",
"\n",
"### A Game\n",
"\n",
"A *game* consists of\n",
" * a list of players\n",
" * a set of actions available to each player\n",
" * a description of payoffs to each player as a function of actions chosen by all players\n",
" * a timing protocol telling who chooses what when\n",
"\n",
"\n",
"### Nash equilibrium\n",
"\n",
"A *Nash equilibrium* is a collection of actions that pass the following test:\n",
"the action of each player gives that player the highest payoff, taking as given the actions of all other players.\n",
"\n",
"### A Repeated Game\n",
"\n",
"A *repeated game* in discrete time consists of\n",
" * A game replayed by the same players at a sequence of dates $t =0, 1, \\ldots, T$, where $T$ might be infinity\n",
" * A common discount rate at which all players discount future payoffs\n",
" * For each player a *strategy* in the form of a sequence of functions; the time $t$ component of this sequence prescribes an action at time $t$ as a function of information available to that player at $t$ \n",
"\n",
"### Subgame Perfect Equilibria\n",
"\n",
"A *Subgame Perfect equilibrium* is a collection of strategies, one for each player, that satisfies the test that, given other players' strategies, each player's wants to adhere to his strategy at each date $t \\geq 0$ for all possible histories\n",
"\n",
"A *Subgame Perfect value* is the expected discounted utility that an agent receives within a subgame perfect equilibrium.\n",
"\n",
"### Backwards Induction and Dynamic Programming\n",
"\n",
"We will encounter an operator reminscent of the *Bellman operator* associated with dynamic programming. This new operator maps a **set** of a vector of continuation values into a **set** of a vector of values. The $i$th element of a vector of values is the discounted value assigned to agent $i$. Continuation value vectors are be drawn from a *set* of candidate value vectors. For good reasons, we will be tempted to iterate to convergence on this operator. \n",
"\n",
"#### Linear programming\n",
"\n",
"We'll use linear programs to do most of the heavy lifting\n",
"\n",
"\n",
"#### Prisoner's Dilemma\n",
"\n",
"We'll use the prisoner's dilemma as our example "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## One-Shot Prisoner's Dilemma\n",
"\n",
"The Prisoners' Dilemma is a list of two players and a $2 \\times 2$ payoff matrix designed to express the following situation.\n",
"\n",
"Two suspects are in police custody. Without a confession or testimony from one of the suspects, the police have evidence indicating but not proving that together the two committed a serious crime. But the police have enough evidence to convict both suspects on a less serious crime. The police offer both the suspects the following deal: If you betray your partner by testifying against him, then we'll let you walk free while your partner is punished for the serious crime; but if you accuse each other, then we'll convict both of you of the lesser crime. The suspects know that the police have only enough evidence to convict them of the lesser charge if neither of them betrays the other.\n",
"\n",
"We represent this game with the following payoff matrix:\n",
"\n",
"<table align=\"center\">\n",
" <tr>\n",
" <td style=\"border-style:hidden hidden hidden hidden; \"> </td>\n",
" <td style=\"border-style:hidden hidden solid hidden;\"> B Silent </td>\n",
" <td style=\"border-style:hidden hidden solid hidden;\"> B Betray </td>\n",
" </tr>\n",
" \n",
" <tr>\n",
" <td style=\"border-style:hidden solid hidden hidden;\"> A Silent </td>\n",
" <td style=\"color:blue; border-style:solid;\"> (9, 9) </td>\n",
" <td style=\"color:blue; border-style:solid;\"> (10, 1) </td>\n",
" </tr>\n",
" \n",
" <tr>\n",
" <td style=\"border-style:hidden solid hidden hidden;\"> A Betray </td>\n",
" <td style=\"color:blue; border-style:solid;\"> (1, 10) </td>\n",
" <td style=\"color:blue; border-style:solid;\"> (3, 3) </td>\n",
" </tr>\n",
"</table>\n",
"\n",
"There is a unique Nash equilibrium in which both A and B choose to betray and receive payoffs (3, 3)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Repeated Prisoner's Dilemma\n",
"\n",
"We change the game by repeating it forever.\n",
"\n",
"The same two criminals repeatedly face the prisoner's dilemma an infinite number of times. \n",
"\n",
"They play the game described above in every period with the same per period payoffs. Both players discount the future at $\\delta \\in (0, 1)$.\n",
"\n",
"In the unique Nash equilibrium of a single shot prisoners dilemma, both players betray.\n",
"\n",
"Do there exist subgame perfect equilibria of the **repeated prisoner's dilemma game** in which the prisoners always remain silent?\n",
"\n",
"If the prisoners are patient enough, i.e., $\\delta$ is close enough to one, the answer is **yes**.\n",
"\n",
"In the repeated game, the prisoners' payoffs depend on sequences of both players' actions.\n",
"\n",
"Let $\\vec{a}$ ($\\vec{b}$) denote the history of actions of prisoner A (B) and let $a_t$ ($b_t$) denote the action taken by A (B) at period $t$. \n",
"\n",
"Then A's present value of payoffs is\n",
"\n",
"$$v^A(\\vec{a}, \\vec{b}) = (1-\\delta) \\sum_{t=0}^{\\infty} \\delta^t u(a_t, b_t)$$\n",
"\n",
"and B's present value of payoffs is\n",
"\n",
"$$v^B(\\vec{a}, \\vec{b}) = (1-\\delta) \\sum_{t=0}^{\\infty} \\delta^t u(b_t, a_t)$$\n",
"\n",
"where\n",
"\n",
"$$u(a_t, b_t) = \\begin{cases} 9 \\text{ if } a_t = b_t = \\text{silent} \\\\ 10 \\text{ if } a_t = \\text{betray} \\ \\& \\ b_t = \\text{silent} \\\\ 1 \\text{ if } a_t = \\text{silent} \\ \\& \\ b_t = \\text{betray} \\\\ 3 \\text{ if } a_t = b_t = \\text{betray} \\end{cases}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We use the QuantEcon `Games` library to represent the game"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"2×2 NormalFormGame{2,Float64}"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pd_payoff = [9.0 1.0\n",
" 10.0 3.0]\n",
"\n",
"A = Player(pd_payoff)\n",
"B = Player(pd_payoff)\n",
"\n",
"pd = NormalFormGame((A, B))"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"Games.RepeatedGame{2,Float64}(2×2 NormalFormGame{2,Float64},0.5)"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"rpd = RepeatedGame(pd, 0.5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### APS Insight\n",
"\n",
"We follow Abreu, Pearce, Stachetti (1986, 1990) (whom we denote APS hereon) who created a set of practical techniques for characterizing an important subset of subgame equilibria, a subset sufficiently big to support all possible subgame equilibrium **values**. \n",
"\n",
"APS use the following objects and flow of ideas.\n",
"\n",
" * A history of action pairs $a^t, b^t = (a_0,b_0), (a_1, b_1), \\ldots , (a_t,b_t) $\n",
"\n",
" * A strategy $\\sigma^i$ for player is a time $0$ action and a sequence of functions $\\{\\sigma_t^i\\}_{t=0}^\\infty $, the $t$th component of which maps a history $a^{t-1}, b^{t-1}$ into a time $t$ action for player $i$\n",
" \n",
" * A strategy profile $\\sigma = (\\sigma^A, \\sigma^B)$ for our two players.\n",
" \n",
" * The observation that a strategy profile determines a pair of present discounted values $(v^A, v^B)$ for our two players (just plug the implied sequence of action pairs into the appropriate expressions for discounted utility).\n",
"\n",
" * A definition of **subgame equilibria** as strategy profiles that satisfy the requirement that given the other player's strategy, each player wants to adhere to his strategy at each date $t \\geq 0$ for all possible histories. \n",
" \n",
" * The observation that a strategy consists of a first-period action and a (continuation) strategy to be followed subsequently.\n",
" \n",
" * The observation that continuation strategy profiles have associated present values\n",
"$\\tilde v^A, \\tilde v^B$ too. \n",
" \n",
" * The observation that a subgame equilibrium consists of first period actions for both players chosen in light of players' (rational) expectations about the consequences of those choices for future utilities. \n",
" \n",
" * A characterization of subgame equilibrium values $v^i, i= A, B$ in terms of a first period action pair $a^A, a^B$ and a pair of subgame perfect continuation values $\\tilde v^i, \\check v^i$ that satisfy recursions\n",
"$$v^i = (1-\\delta) u(a^i, a^{-i}) + \\delta \\tilde v^i \\geq (1- \\delta ) u( \\check a^i, a^{-i} ) + \\delta \\check v^i \\quad (\\dagger) $$\n",
"where $a^i$ is the action chosen by player $i$ and $a^{-i}$ is the action chosen by player $-i$ (the other player). Here $\\tilde v^i$ is the continuation value that player $i$ receives if he adheres to a strategy that prescribes first period action $a^i$ this period and\n",
"$\\check v^i$ is the continuation value in a subgame perfect equilibrium value prescribed if the player deviates from the strategy by choosing $\\check a^i \\neq a^i$.\n",
"\n",
"APS note that\n",
"\n",
" * Equation $(\\dagger)$ for each player $i$ maps **pairs** of subgame perfect equilibrium continuation values $\\tilde v^i, \\check v^i$ into a single value $v^i$. \n",
" \n",
" * Equation $(\\dagger)$ characterizes **all** subgame perfect equilibrium values. This means that $\\tilde v^i$ and $\\check v^i$ each satisfy versions of this equation where they are now on the **left** side of the equation and another pair of continuation values are on the right side. That $\\check v^i$ is itself a subgame perfect equilibrium value captures the notion that it is value associated with a strategy that is a **credible threat** that deters player $i$ from deviating from first-period action $a^i$.\n",
" \n",
" * APS use this insight together with the backward induction inherent in equation ($\\dagger$) to characterize the set of subgame perfect equilibrium values $V \\in \\mathbb{R}^2$ as the largest fixed point of iterations of a set-to-set mapping $\\mathcal{B}$ that takes maps four-tuples of continuation values, two for player $A$, two for player $B$, into pairs of values, one for player $A$ and one for player $B$.\n",
" \n",
" APS's operator $\\mathcal{B}$ starts from a generous (meaning it might be too big) set of candidate continuation values $W$. From this set, it draws two pairs $\\tilde v^i, \\check v^i$ for $i=A, B$, where $\\tilde v^i, \\check v^i$ are both drawn from the $i$ component of W (usually, $\\tilde v^i$ a high value and $\\check v^i$ a low value) for $i=A,B$. It then finds a feasible first period \n",
"action pair and associated pair of values $v^A, v^B$ that satisfies inequalities $(\\dagger)$. The set of **all** value pairs $v^A, v^B$ that satisfy these inequalities for \n",
"a given set of candidate continuation values is a new set $\\mathcal{B}(W)$. \n",
"\n",
" * APS show that $\\mathcal{B}$ is a **monotone operator** in the sense that if $V \\subset V'$ then $\\mathcal{B}(V) \\subset \\mathcal{B}(V')$\n",
"\n",
" * The monotonicity of $\\mathcal{B}$ means that if we start from a sufficiently large initial guess $W_0$, iterations on $\\mathcal{B}$ converge to the set of all subgame equilibrium values.\n",
"\n",
"Judd, Yeltekin, Conklin (2003) simplify a candidate value set by *convexifying* it. This can be accomplished with **public randomization**\n",
"\n",
"-- Public randomization enables players to coordinate by making their actions depend on a commonly observed public signal. For example: At the beginning of every period every player observes a realization of a uniform random variable with domain on the interval $[0,1]$. If the realization is less than 0.5, then the players take some previously agreed upon action while if the number is greater than 0.5 then they each take a (possibly different) previously specified action. This device ensures the convexity of value sets. If players can achieve $V = (v_1, v_2)$ and $W = (w_1, w_2)$, then public randomization lets players achieve any value $Z = \\lambda V + (1-\\lambda) W$.\n",
"\n",
"-- For example, think of $\\lambda$ as a probability of an event that leads players to choose SPE actions with value $V$, while the complement of $\\lambda$ is an event that prompts SPE actions with value $W$.\n",
"\n",
"We have left out many technical details here, but if you are interested in understanding this material further then we recommend reading APS, APS, JYC, AS. <!-- TODO: Add citations for these papers -->\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Approximating the set\n",
"\n",
"A key recommendation of JYC 2003 is a way to approximate the set of subgame perfect equilibrium values. \n",
"\n",
"As mentioned above, we use a public randomization to assure that sets are convex\n",
"\n",
"A convenient property of convex sets (polytopes in particular) is that because we only need to keep track of extreme points, they can be represented easily inside a computer.\n",
"\n",
"It is also useful to recognize that a polytopes can be represented as the intersection of a finite number of half-spaces. \n",
"\n",
"While we use this half-space representation, we also mention other representations because we will need to think about going from one to the other and back.\n",
"\n",
"We approximate the set with half-spaces in the following way: Consider a set of subgradients (think about these as directional vectors) $H$. For example, let $H = \\{ (1, 0), (0, 1), (-1, 0), (0, -1) \\}$. Let $C$ be a set of hyperplane levels, for example, $C = \\{4, 3, 2, 1\\}$. The halfspace corresponding to a specific subgradient, $h \\in H$, and hyperplane level, $c \\in C$, is described by the set $s = \\{ (x, y) | h \\cdot (x, y) \\leq c \\}$. In our example, the set of half-spaces would be $S = \\{s_1, s_2, s_3, s_4\\}$, where\n",
"\n",
"\\begin{align*}\n",
" s_1 &:= \\{ (x, y) | x \\leq 4 \\} \\\\\n",
" s_2 &:= \\{ (x, y) | y \\leq 3 \\} \\\\\n",
" s_3 &:= \\{ (x, y) | -x \\leq 2 \\} \\\\\n",
" s_4 &:= \\{ (x, y) | -y \\leq 1 \\}\n",
"\\end{align*}\n",
"\n",
"We draw the following below:\n",
"\n",
" * Each of the half-spaces (draw their hyper-planes)\n",
" * Intersection of the half-spaces (shaded red)\n",
" * Subgradients ($h_i$)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"<div id=\"522f0284-8c9e-4074-8bcb-6a3fd4f6800a\" class=\"plotly-graph-div\"></div>\n",
"\n",
"<script>\n",
" window.PLOTLYENV=window.PLOTLYENV || {};\n",
" window.PLOTLYENV.BASE_URL=\"https://plot.ly\";\n",
" require(['plotly'], function(Plotly) {\n",
" Plotly.newPlot('522f0284-8c9e-4074-8bcb-6a3fd4f6800a', [{\"y\":[-5.0,5.0],\"name\":\"s_1\",\"type\":\"scatter\",\"x\":[4,4]},{\"y\":[3,3],\"name\":\"s_2\",\"type\":\"scatter\",\"x\":[-5.0,5.0]},{\"y\":[-5.0,5.0],\"name\":\"s_3\",\"type\":\"scatter\",\"x\":[-2,-2]},{\"y\":[-1,-1],\"name\":\"s_4\",\"type\":\"scatter\",\"x\":[-5.0,5.0]}],\n",
" {\"yaxis\":{\"range\":[-3.0,4.0]},\"annotations\":[{\"arrowwidth\":2,\"arrowhead\":2,\"ay\":0,\"x\":1,\"arrowsize\":1,\"ax\":-105,\"showarrow\":true,\"y\":0},{\"arrowwidth\":2,\"arrowhead\":2,\"ay\":65,\"x\":0,\"arrowsize\":1,\"ax\":0,\"showarrow\":true,\"y\":1},{\"arrowwidth\":2,\"arrowhead\":2,\"ay\":0,\"x\":-1,\"arrowsize\":1,\"ax\":105,\"showarrow\":true,\"y\":0},{\"arrowwidth\":2,\"arrowhead\":2,\"ay\":-65,\"x\":0,\"arrowsize\":1,\"ax\":0,\"showarrow\":true,\"y\":-1},{\"arrowhead\":2,\"x\":1,\"text\":\"h_1\",\"showarrow\":false,\"y\":0.25},{\"arrowhead\":2,\"x\":0.25,\"text\":\"h_2\",\"showarrow\":false,\"y\":1},{\"arrowhead\":2,\"x\":-1,\"text\":\"h_3\",\"showarrow\":false,\"y\":0.25},{\"arrowhead\":2,\"x\":0.25,\"text\":\"h_4\",\"showarrow\":false,\"y\":-0.75}],\"xaxis\":{\"range\":[-3.5,4.5]},\"title\":\"Intersection of Half-spaces\",\"margin\":{\"r\":50,\"l\":50,\"b\":50,\"t\":60},\"shapes\":[{\"opacity\":0.4,\"x0\":-2,\"x1\":4,\"y0\":-1,\"type\":\"rect\",\"y1\":3,\"fillcolor\":\"red\",\"line\":{\"width\":0}}]}, {showLink: false});\n",
"\n",
" });\n",
" </script>\n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"n = 2\n",
"ls_m5_p5 = linspace(-5, 5, n)\n",
"\n",
"# Build traces\n",
"t_s1 = scatter(;x=fill(4, n), y=ls_m5_p5, name=\"s_1\")\n",
"t_s2 = scatter(;x=ls_m5_p5, y=fill(3, n), name=\"s_2\")\n",
"t_s3 = scatter(;x=fill(-2, n), y=ls_m5_p5, name=\"s_3\")\n",
"t_s4 = scatter(;x=ls_m5_p5, y=fill(-1, n), name=\"s_4\")\n",
"\n",
"# Build layout\n",
"h_s1 = Dict(\"x\"=>1, \"y\"=>0,\"arrowhead\"=>2, \"arrowsize\"=>1, \"arrowwidth\"=>2,\n",
" \"showarrow\"=>true, \"ax\"=>-105, \"ay\"=>0)\n",
"h_s2 = Dict(\"x\"=>0, \"y\"=>1,\"arrowhead\"=>2, \"arrowsize\"=>1, \"arrowwidth\"=>2,\n",
" \"showarrow\"=>true, \"ax\"=>0, \"ay\"=>65)\n",
"h_s3 = Dict(\"x\"=>-1, \"y\"=>0,\"arrowhead\"=>2, \"arrowsize\"=>1, \"arrowwidth\"=>2,\n",
" \"showarrow\"=>true, \"ax\"=>105, \"ay\"=>0)\n",
"h_s4 = Dict(\"x\"=>0, \"y\"=>-1,\"arrowhead\"=>2, \"arrowsize\"=>1, \"arrowwidth\"=>2,\n",
" \"showarrow\"=>true, \"ax\"=>0, \"ay\"=>-65)\n",
"\n",
"h_1 = Dict(\"x\"=>1, \"y\"=>0.25,\"arrowhead\"=>2, \"text\"=>\"h_1\", \"showarrow\"=>false)\n",
"h_2 = Dict(\"x\"=>0.25, \"y\"=>1,\"arrowhead\"=>2, \"text\"=>\"h_2\", \"showarrow\"=>false)\n",
"h_3 = Dict(\"x\"=>-1, \"y\"=>0.25,\"arrowhead\"=>2, \"text\"=>\"h_3\", \"showarrow\"=>false)\n",
"h_4 = Dict(\"x\"=>0.25, \"y\"=>-0.75,\"arrowhead\"=>2, \"text\"=>\"h_4\", \"showarrow\"=>false)\n",
"\n",
"shapes = [rect(-2, 4, -1, 3, fillcolor=\"red\", opacity=0.4, line_width=0)]\n",
"l = Layout(;shapes=shapes, title=\"Intersection of Half-spaces\",\n",
" xaxis_range=[-3.5, 4.5], yaxis_range=[-3.0, 4.0],\n",
" annotations=[h_s1, h_s2, h_s3, h_s4,\n",
" h_1, h_2, h_3, h_4])\n",
"\n",
"plot([t_s1, t_s2, t_s3, t_s4], l)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We promised to show you three things:\n",
" * Each of the half-spaces\n",
" * Intersection of the half-spaces\n",
" * Subgradients\n",
"\n",
"We have delivered on these promises by plotting the subgradients (directional vectors) as black arrows, plotting the hyperplane of each half space, and shading the intersection of the 4 half-spaces in red. The blue line corresponds to the hyperplane for the first half-space and everything to the left of this line is an element of the half-space. The orange line corresponds to the hyperplane for the second half-space and everything below this line is an element of the half-space. The green line corresponds to the hyperplane for the third half-space and everything to the right of this line is an element of the half-space. The red line corresponds to the hyperplane for the fourth half-space and everything above this line is an element of the half-space.\n",
"\n",
"This picture also provides insights into relationships among the subgradient, hyperplane level, and the hyperplane/half-space. In particular, note that the hyperplane of the half-space is orthogonal to its corresponding subgradient -- The subgradient determines the slope and orientation of the set (whether it lies to the left, right, above, or below the hyperplane). The hyperplane level determines the location of the hyperplane -- It expresses how far from the origin the hyperplane lies. We will see this highlighted again when we plot value sets associated with the repeated game."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In practice how do we map our $\\mathcal{B}$ operator into the correct set of half-spaces?\n",
"\n",
"We accomplish this by transforming the $\\mathcal{B}$ operator into a sequence of linear programs that constructs the smallest convex set that contains the fixed point of the $\\mathcal{B}$ operator. We call this smallest convex set the **outer hyperplane approximation**.\n",
"\n",
"Here is an outline of the alogrithm.\n",
"\n",
"1. Initialize elements of our algorithm\n",
" * Subgradients, $H$\n",
" * Hyperplane levels, $C$\n",
"2. Given a set of subgradients and corresponding hyperplane levels\n",
" * For each subgradient, $h \\in H$,\n",
" 1. Solve a linear program for each action in the action space\n",
" 2. Find maximum to update hyperplane level\n",
" 3. Find the associated $(w_1, w_2)$ pair \n",
"3. Check whether hyperplane levels changed more than the set tolerance. If so, return to 2. Else, proceed.\n",
"4. Set of vertices is described by $Z$ and define $W^* = \\text{co}(Z)$.\n",
"\n",
"We discuss each of these steps in more detail below"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Step 1: Initilization Step\n",
"\n",
"#### Unit Circle\n",
"\n",
"There is not a unique way to pick the initial subgradients and hyperplane levels. However, a way that seems to work quite well is simply to partition a unit circle. If there are $N$ subgradients, set\n",
"\n",
"$$h_i = \\left( \\cos \\left( 2 \\pi \\frac{i}{N} \\right), \\sin \\left(2 \\pi \\frac{i}{N} \\right) \\right)$$\n",
"\n",
"Here is a function that produces such a set of subgradients. We plot them below."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"<div id=\"0aacc892-6189-4dc9-80ef-cc07aeffda3a\" class=\"plotly-graph-div\"></div>\n",
"\n",
"<script>\n",
" window.PLOTLYENV=window.PLOTLYENV || {};\n",
" window.PLOTLYENV.BASE_URL=\"https://plot.ly\";\n",
" require(['plotly'], function(Plotly) {\n",
" Plotly.newPlot('0aacc892-6189-4dc9-80ef-cc07aeffda3a', [{\"type\":\"scatter\"},{\"y\":[0.0,0.0],\"showlegend\":false,\"name\":\"Subgradient 1\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,1.0],\"mode\":\"lines\"},{\"y\":[0.0,0.3090169943749474],\"showlegend\":false,\"name\":\"Subgradient 2\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,0.9510565162951535],\"mode\":\"lines\"},{\"y\":[0.0,0.5877852522924731],\"showlegend\":false,\"name\":\"Subgradient 3\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,0.8090169943749475],\"mode\":\"lines\"},{\"y\":[0.0,0.8090169943749475],\"showlegend\":false,\"name\":\"Subgradient 4\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,0.5877852522924731],\"mode\":\"lines\"},{\"y\":[0.0,0.9510565162951535],\"showlegend\":false,\"name\":\"Subgradient 5\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,0.30901699437494745],\"mode\":\"lines\"},{\"y\":[0.0,1.0],\"showlegend\":false,\"name\":\"Subgradient 6\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,6.123233995736766e-17],\"mode\":\"lines\"},{\"y\":[0.0,0.9510565162951536],\"showlegend\":false,\"name\":\"Subgradient 7\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,-0.30901699437494734],\"mode\":\"lines\"},{\"y\":[0.0,0.8090169943749475],\"showlegend\":false,\"name\":\"Subgradient 8\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,-0.587785252292473],\"mode\":\"lines\"},{\"y\":[0.0,0.5877852522924732],\"showlegend\":false,\"name\":\"Subgradient 9\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,-0.8090169943749473],\"mode\":\"lines\"},{\"y\":[0.0,0.3090169943749475],\"showlegend\":false,\"name\":\"Subgradient 10\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,-0.9510565162951535],\"mode\":\"lines\"},{\"y\":[0.0,1.2246467991473532e-16],\"showlegend\":false,\"name\":\"Subgradient 11\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,-1.0],\"mode\":\"lines\"},{\"y\":[0.0,-0.3090169943749473],\"showlegend\":false,\"name\":\"Subgradient 12\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,-0.9510565162951536],\"mode\":\"lines\"},{\"y\":[0.0,-0.587785252292473],\"showlegend\":false,\"name\":\"Subgradient 13\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,-0.8090169943749475],\"mode\":\"lines\"},{\"y\":[0.0,-0.8090169943749473],\"showlegend\":false,\"name\":\"Subgradient 14\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,-0.5877852522924732],\"mode\":\"lines\"},{\"y\":[0.0,-0.9510565162951535],\"showlegend\":false,\"name\":\"Subgradient 15\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,-0.30901699437494756],\"mode\":\"lines\"},{\"y\":[0.0,-1.0],\"showlegend\":false,\"name\":\"Subgradient 16\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,-1.8369701987210297e-16],\"mode\":\"lines\"},{\"y\":[0.0,-0.9510565162951536],\"showlegend\":false,\"name\":\"Subgradient 17\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,0.30901699437494723],\"mode\":\"lines\"},{\"y\":[0.0,-0.8090169943749476],\"showlegend\":false,\"name\":\"Subgradient 18\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,0.5877852522924729],\"mode\":\"lines\"},{\"y\":[0.0,-0.5877852522924734],\"showlegend\":false,\"name\":\"Subgradient 19\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,0.8090169943749473],\"mode\":\"lines\"},{\"y\":[0.0,-0.3090169943749476],\"showlegend\":false,\"name\":\"Subgradient 20\",\"type\":\"scatter\",\"line\":{\"color\":\"grey\"},\"x\":[0.0,0.9510565162951535],\"mode\":\"lines\"}],\n",
" {\"title\":\"Subgradients from Unit Circle\",\"margin\":{\"r\":50,\"l\":50,\"b\":50,\"t\":60}}, {showLink: false});\n",
"\n",
" });\n",
" </script>\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"n = 20\n",
"pts = Games.unitcircle(n)\n",
"p = plot(scatter(), Layout(;title=\"Subgradients from Unit Circle\"))\n",
"\n",
"for i=1:n\n",
" xi, yi = pts[i, :]\n",
" ti = scatter(;x=[0.0, xi], y=[0.0, yi], mode=\"lines\",\n",
" name=\"Subgradient $i\", line_color=\"grey\",\n",
" showlegend=false)\n",
" addtraces!(p, ti)\n",
"end\n",
"\n",
"p"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here there are $n$ lines. Each line is a single subgradient. Try to conceive a half-space at the end of each of these subgradients -- Points that determine the shape of the polygon aren't actually the points at the end of the subgradients, but rather points at which the halfspaces intersect. As we drive the number of lines to infinity, we will obtain a circle."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Hyperplanes\n",
"\n",
"In addition to choosing the subgradient directions, we must also pick initial hyperplane levels. One way (again this isn't unique) is to pick an origin and a radius, then to compute points that would be along the circle in the direction of each subgradient. Once we have these points then we can use them to compute the hyperplane levels simply by $H \\cdot Z'$.\n",
"\n",
"Recall that continuation payoffs are $\\sum \\delta^t (1-\\delta) u(a_t, b_t)$. If a player receives his worst (or best) utility every period, then that is his discounted value. Therefore, values are bounded above by a player's maximum possible payoff and bounded below by a player's minimum possible payoff. It is infeasible for a player to receive a value smaller (or bigger) than this, and so, using our circle as a starting point, we can crop the size of this set along those values. We use this information (though it isn't necessary) in the function that generates an initial set for our iteration process. This set has to be \"big enough,\" but the bigger the set is the longer it takes to compute the equilibrium value set. There is a tradeoff between ensuring that our set is big enough and saving computation time.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice how the points are no longer forumlated around the unit circle, but instead are now a (cropped as described above) circle of radius 10 around (4.5, 4.5)."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"<div id=\"99c44f93-a9a2-4b69-892d-139e3ab5bfa5\" class=\"plotly-graph-div\"></div>\n",
"\n",
"<script>\n",
" window.PLOTLYENV=window.PLOTLYENV || {};\n",
" window.PLOTLYENV.BASE_URL=\"https://plot.ly\";\n",
" require(['plotly'], function(Plotly) {\n",
" Plotly.newPlot('99c44f93-a9a2-4b69-892d-139e3ab5bfa5', [{\"y\":[4.5,7.5901699437494745,10.0,10.0,10.0,10.0,10.0,10.0,10.0,7.5901699437494745,4.500000000000001,1.4098300562505273,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.4098300562505237,4.5],\"type\":\"scatter\",\"x\":[10.0,10.0,10.0,10.0,7.5901699437494745,4.500000000000001,1.4098300562505264,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.4098300562505246,4.499999999999998,7.590169943749473,10.0,10.0,10.0,10.0]}],\n",
" {\"yaxis\":{\"range\":[0.5,10.5],\"title\":\"w_2\"},\"xaxis\":{\"range\":[0.5,10.5],\"title\":\"w_1\"},\"title\":\"Starting Set\",\"margin\":{\"r\":50,\"l\":50,\"b\":50,\"t\":60}}, {showLink: false});\n",
"\n",
" });\n",
" </script>\n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"n = 20\n",
"C, H, Z = Games.create_unitcircle_points(rpd, n, [4.5, 4.5], 10.0)\n",
"t = scatter(;x=vcat(Z'[:, 1], Z[1, 1]), y=vcat(Z'[:, 2], Z[2, 1]))\n",
"l = Layout(;title=\"Starting Set\", xaxis_title=\"w_1\", yaxis_title=\"w_2\",\n",
" xaxis_range=[0.5, 10.5], yaxis_range=[0.5, 10.5])\n",
"p = plot(t, l)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that we had a very large radius in this picture, so the code trimmed it down to a rectangle along the minimum and maximum payoffs that the players can each have."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Step 2: Iterative Step\n",
"\n",
"The general idea of this step will be to push each hyperplane (which defines the set's boundary) as far in a given direction as possible -- We are trying to make the set of continuation values as large as possible while satisfying the constraints of the $\\mathcal{B}$ operator. The linear program takes the following form. Given an action for today, maximize the dot product of the agents' values and the subgradient:\n",
"\n",
"\\begin{align*}\n",
" \\max_{w} \\; &h_i \\cdot (u(a) + \\delta w) \\\\\n",
" &\\text{subject to} \\\\\n",
" &H \\cdot w \\leq C \\\\\n",
" &u_1(a) + \\delta w_1 \\geq u_1(a_{-1}) + \\delta \\underline{w}_1 \\\\\n",
" &u_2(a) + \\delta w_2 \\geq u_2(a_{-2}) + \\delta \\underline{w}_2\n",
"\\end{align*}\n",
"\n",
"The constraint $H \\cdot w \\leq C$ is the same as requiring $w \\in W$ where $W$ is the set defined by intersection of the our half-spaces. Representing $w \\in W$ in this way is what makes the half-space representation so useful for us.\n",
"\n",
"The next two constraints are just incentive compatiblity constraints. $\\underline{w}_i$ is the minimum possible continuation value from the set $W$ for agent $i$.\n",
"\n",
"In order to apply the standard linear programming routines, we need to change this problem into the form\n",
"\n",
"\\begin{align*}\n",
" \\max_x \\; & c^T x \\\\\n",
" &\\text{subject to } \\\\\n",
" &Ax = b\n",
"\\end{align*}\n",
"\n",
"The following observations guide us.\n",
"\n",
"1) $\\max_w h_i \\cdot (u(a) + \\delta w)$ produces the same solution, $w$, as $\\max_w h_i \\cdot \\delta w$.\n",
"\n",
"2) $w \\in W$ is equivalent to $H \\cdot w \\leq C$ (where $C$ are our hyperplane levels and $H$ are our subgradients). We can make it $=$ instead of $\\leq$ by concatentating an identity matrix to $H$ and adding \"slack variables\" which we will restrict to be positive.\n",
"\n",
"3) $(1-\\delta) u_i(a) + \\delta w_i \\geq (1-\\delta) u^*_i(a_{-i}) + \\delta \\underline{w}_i$ can be rewritten as $-\\delta w_i \\leq (1-\\delta) (u_i(a) - u^*_i(a_{-i})) - \\delta \\underline{w}_i)$. Again we can change $\\leq$ to $=$ by adding a slack variable. We will refer to the matrices that define this as $\\text{IC}$ below to simplify notation.\n",
"\n",
"Denote a slack variable by a $\\lambda_i$. Then:\n",
"\n",
"* Variable we maximize over is $x = \\begin{bmatrix} w_1 \\\\ w_2 \\\\ \\lambda_1 \\\\ \\dots \\\\ \\lambda_{nH + 2} \\end{bmatrix}$\n",
"* The objective vector will be $c^T = \\begin{bmatrix} h_1 & h_2 & 0 & \\dots & 0 \\end{bmatrix}$\n",
"* $A$ and $b$ are then made up of combinations of the matrices and vectors from the constraints: $A = \\begin{bmatrix} H & I \\\\ \\text{IC} & I \\end{bmatrix}$ and $b = \\begin{bmatrix} C \\\\ \\underline{w_1} \\\\ \\underline{w_2} \\end{bmatrix}$.\n",
"\n",
"The functions which implement these steps can be found in the [Games.jl](https://github.com/QuantEcon/Games.jl) library. Applying these steps repeatedly is the basis for the outer hyperplane approximation theorem we have been discussing. We can see the output of this below."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"Games.RepeatedGame{2,Float64}(2×2 NormalFormGame{2,Float64},0.75)"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pd_payoff = [9.0 1.0\n",
" 10.0 3.0]\n",
"\n",
"A = Player(pd_payoff)\n",
"B = Player(pd_payoff)\n",
"\n",
"pd = NormalFormGame((A, B))\n",
"rpd = RepeatedGame(pd, 0.75)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"5\t0.1611101417973142\t(2.3671874999999982, 2.367187500000002)\n",
"10\t0.039748957194302825\t(2.8498306274414036, 2.8498306274414085)\n",
"15\t0.009432613865444583\t(2.9643641039729096, 2.9643641039729136)\n",
"20\t0.002238403485647744\t(2.991543434829507, 2.9915434348295107)\n",
"25\t0.0005311836396604264\t(2.997993217444891, 2.9979932174448947)\n",
"30\t0.00012605236761498162\t(2.9995237810928774, 2.999523781092881)\n",
"35\t2.991281770503562e-5\t(2.9998869910210626, 2.999886991021066)\n",
"40\t7.098451858755794e-6\t(2.9999731824395677, 2.9999731824395695)\n",
"45\t1.6844958996564685e-6\t(2.999993636067202, 2.999993636067202)\n",
"50\t3.9973877319354756e-7\t(2.9999984898089163, 2.9999984898089163)\n"
]
}
],
"source": [
"hp_pts = outerapproximation(rpd; nH=64, maxiter=100, nskipprint=5, tol=1e-8);"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"<div id=\"0d8a97a5-84b9-4a80-afb0-7225e90abe20\" class=\"plotly-graph-div\"></div>\n",
"\n",
"<script>\n",
" window.PLOTLYENV=window.PLOTLYENV || {};\n",
" window.PLOTLYENV.BASE_URL=\"https://plot.ly\";\n",
" require(['plotly'], function(Plotly) {\n",
" Plotly.newPlot('0d8a97a5-84b9-4a80-afb0-7225e90abe20', [{\"y\":[3.0,6.8882,9.0,9.4201,9.803,3.0],\"type\":\"scatter\",\"x\":[9.803,9.4201,9.0,6.8882,3.0,3.0],\"mode\":\"markers\"}],\n",
" {\"yaxis\":{\"range\":[0,15],\"title\":\"w_2\"},\"xaxis\":{\"range\":[0,15],\"title\":\"w_1\"},\"title\":\"Set of Subgame Perfect Values\",\"margin\":{\"r\":50,\"l\":50,\"b\":50,\"t\":60}}, {showLink: false});\n",
"\n",
" });\n",
" </script>\n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"plot(scatter(;x=hp_pts'[:, 1], y=hp_pts'[:, 2], mode=\"markers\"),\n",
" Layout(;xaxis_range=[0, 15], yaxis_range=[0, 15],\n",
" title=\"Set of Subgame Perfect Values\",\n",
" xaxis_title=\"w_1\",\n",
" yaxis_title=\"w_2\"))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The approximation of the set of subgame perfect equilibrium values are presented above. Here each point represents an extreme point of the set and the set of values would be the convex hull of this set of points.\n",
"\n",
"There are several things to take note of:\n",
" * The criminals can sustain silence (The (9, 9) payoff is an element of the set)\n",
" * One of the criminals could possibly do better than the silence payoff though the other would do worse."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We could think about varying the discount factor. How would this change the set of achievable values?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"pd_payoff = [9.0 1.0\n",
" 10.0 3.0]\n",
"\n",
"A = Player(pd_payoff)\n",
"B = Player(pd_payoff)\n",
"\n",
"pd = NormalFormGame((A, B))\n",
"rpd1 = RepeatedGame(pd, 0.85)\n",
"rpd2 = RepeatedGame(pd, 0.25)\n",
"\n",
"hp_pts1 = outerapproximation(rpd1; nH=128, maxiter=100, nskipprint=25, tol=1e-5);\n",
"hp_pts2 = outerapproximation(rpd2; nH=128, maxiter=100, nskipprint=25, tol=1e-5);"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"<div id=\"66e0c013-5257-43a9-898e-54bf4f4b67e4\" class=\"plotly-graph-div\"></div>\n",
"\n",
"<script>\n",
" window.PLOTLYENV=window.PLOTLYENV || {};\n",
" window.PLOTLYENV.BASE_URL=\"https://plot.ly\";\n",
" require(['plotly'], function(Plotly) {\n",
" Plotly.newPlot('66e0c013-5257-43a9-898e-54bf4f4b67e4', [{\"y\":[2.9999,4.7455,9.0,9.6311,9.803,3.0,3.0,2.9999],\"name\":\"High Discount\",\"type\":\"scatter\",\"x\":[9.803,9.6311,9.0,4.7455,2.9999,2.9999,3.0,3.0],\"mode\":\"markers\"},{\"y\":[3.0,5.809,9.0,9.4733,9.75,3.0],\"name\":\"Low Discount\",\"type\":\"scatter\",\"x\":[9.75,9.4733,9.0,5.809,3.0,3.0],\"mode\":\"markers\"}],\n",
" {\"yaxis\":{\"range\":[0,15],\"title\":\"w_2\"},\"xaxis\":{\"range\":[0,15],\"title\":\"w_1\"},\"title\":\"Set of Subgame Perfect Values\",\"margin\":{\"r\":50,\"l\":50,\"b\":50,\"t\":60}}, {showLink: false});\n",
"\n",
" });\n",
" </script>\n"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t1 = scatter(;x=hp_pts1'[:, 1], y=hp_pts1'[:, 2], mode=\"markers\", name=\"High Discount\")\n",
"t2 = scatter(;x=hp_pts2'[:, 1], y=hp_pts2'[:, 2], mode=\"markers\", name=\"Low Discount\")\n",
"\n",
"plot([t1, t2],\n",
" Layout(;xaxis_range=[0, 15], yaxis_range=[0, 15],\n",
" title=\"Set of Subgame Perfect Values\",\n",
" xaxis_title=\"w_1\",\n",
" yaxis_title=\"w_2\"))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The differences are pretty small. It does appear that high discount factor supports a slightly larger set of equilibrium though (which isn't surprising)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Deducing SPE strategies\n",
"\n",
"In addition to wanting SPE values, we also want strategy profiles that attain them. Some of these are obvious -- For example, (9, 9) is sustained by maintaining silence and (3, 3) is sustained by always betraying. Others are less obvious and involve mixtures of silence and betrayal.\n",
"\n",
"Here is how APS would deduce a SPE equilbrium strategy profile associated with a SPE value profile $v\\in V$.\n",
"\n",
"Let $s \\in U[0,1]$ be the uniform random variable used to effect public randomization and let\n",
"$V$ be the set of SPE values. \n",
"\n",
"Start with two $v$s that are extreme points of the final outer hyperplane approximation. \n",
"Let $v_1 = (1-\\delta) u(a_1) + \\delta v_1'$ and for let $v_2 = (1-\\delta) u(a_2) + \\delta v_2'$ be two such SPE values with associated first period actions and continuation value pairs $(a_1, v_1')$, $(a_2,v_2')$, respectively. Because $v_1$ and $v_2$ are values obtained as extreme points from the outer hyperplane approximation, they use no public randomization. The linear programming algorithm that produces the outer hyperplane approximation computes pairs $(a_1, v_1')$, $(a_2,v_2')$ that attain these $v$'s.\n",
"\n",
"Now we activate public randomization.\n",
"\n",
"For probability $p \\in [0,1]$, we obtain a continuation value profile $v \\in V$ from \n",
"an appropriate version of the equality\n",
"\n",
"$$ v = p [ (1-\\delta) u(a_1) + \\delta v_1'] + (1-p) [ (1-\\delta) u(a_2) + \\delta v_2'] $$\n",
"\n",
"The value profile $v$ is then attained by a strategy profile that can be represented recursively with the pair of functions\n",
"\n",
"$$ a = f (v,s) $$\n",
"\n",
"$$ v' = g( v, a, s) $$\n",
"\n",
"where $s \\in [0,1]$ is a realization of the public random variable.\n",
"\n",
"If we iterate these functions starting from a SPE value profile $v_0 \\in V$, we obtain a sequence of functions representing a SPE strategy profile that attains $v_0$:\n",
"\n",
"$$ a_0 = \\tilde f_0(a_0, s_0, v_0) $$\n",
"\n",
"$$ a_t = \\tilde f_t (a^{t-1}, s^t, v_0) , \\quad t \\geq 1 $$\n",
"\n",
"Here $s^t $ denotes the history $s_t, s_{t-1}, \\ldots, s_0$ and $a^{t-1}$\n",
"denotes the history $a_{t-1}, \\ldots, a_0$. \n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TODO (Tom and Chase)\n",
"\n",
"* ~~Fix the description changes~~\n",
"* ~~Add another graph with high and low delta sets shown. Talk about how the set size changes.~~\n",
"* Change the payoffs to be asymmetric etc... (TOM: I think this is more interesting as an exercise)\n",
"* ~~Talk about what each of these points mean -- These are values that can be sustained by some equilibrium.~~\n",
"* Exercise: John and Chase: shall we add a Cournot game?\n",
"* ~~Independent thing: Describe the strategy profile that attains one of these points.~~\n",
"* ~~The repeated game code can be put into the Games library without too much trouble. Would make this cleaner if we could move lots of the boiler plate code out and have it within Games library.~~"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"#### References\n",
"\n",
"Abreu, Dilip, David Pearce, and Ennio Stacchetti, 1986. ``Optimal Cartel Equilibria with Imperfect Monitoring'', Journal of Economic Theory, 39, 251-269.\n",
"\n",
"Abreu, Dilip, David Pearce, and Ennio Stacchetti, 1990. ``Toward a Theory of Discounted Repeated Games with Imperfect Monitoring'', Econometrica, 58, 1041-1063.\n",
"\n",
"Judd,Kenneth , Sevin Yeltekin, and James Conklin, 2003.\n",
"``Computing Supergame Equilibria,'' Econometrica, Econometric Society, \n",
"vol. 71(4), pages 1239-1254, 07.\n",
"\n"
]
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Julia 0.5.0-rc3",
"language": "julia",
"name": "julia-0.5"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "0.5.0"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
@oyamad
Copy link

oyamad commented Nov 10, 2016

The statement "The monotonicity of B means that ..." is not precise enough. (For example, the identity mapping, the mapping defined by B(V) = V for any V, is monotone, but iteration of it does not converge to the set of SPE payoff profiles.)

@oyamad
Copy link

oyamad commented Nov 11, 2016

Other (minor) comments I typed yesterday but which disappeared:

  • In Step 2, (1 - delta) is missing in the IC constraints.
  • In Step 2, the last two two elements in b should be the right hand side of the second inequality in 3). Delete the ) after underline_w_i there.
  • The pictures would look better if drawn with equal aspect ratio.
  • Maybe better to connect the vertices in the pictures of the payoff profile sets.

@oyamad
Copy link

oyamad commented Nov 11, 2016

  • max_x c^T x should be min_x c^T x: in the code, the linear program is set up as a minimization problem.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment