{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "#### A Recursive Formulation of Repeated Games\n", "\n", "**Authors**: Chase Coleman with 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 called the _outer hyperplane approximation 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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Technical Julia Advisory\n", "\n", "The quant-econ `Games` library is currently under development and not yet a published Julia package\n", "\n", "To get it, please run\n", "\n", " `Pkg.clone(\"https://github.com/QuantEcon/Games.jl.git\")`. \n", " \n", "This command may also install some additional packages such as `Clp`, `MathProgBase`, `QuantEcon`, `Polyhedra`, and `CDDLib` (and whatever dependencies these packages rely on).\n", "\n", "Plotting in this notebook uses the package `PlotlyJS`.\n", "\n", "A cautionary note: occasionally (but not always) users of this notebook have experienced difficulty installing `CDDLib` and `Polyhedra` (sometimes due to no fault of their own).\n", "\n", "This, the first version of this notebook, uses the following versions of various packages:\n", "\n", "* `CDDLib` -> v0.1.2\n", "* `Games` -> v0.0.1\n", "* `Polyhedra` -> v0.1.3\n", "* `PlotlyJS` -> v0.5.2\n", "\n", "Please verify that you have the correct versions of these packages [1, 2]. \n", "\n", "We have found that occasionally users have struggled to get `CDDLib` to build. \n", "\n", "If this happens to you, make sure that you have [libgmp](https://gmplib.org/) installed.[3] After it has been installed, please run `Pkg.build(\"CDDLib\")`.\n", "\n", "If you encounter problems beyond these, please raise an issue about them in the package's repository or in the [QuantEcon.notebooks repository](https://github.com/QuantEcon/QuantEcon.notebooks).\n", "\n", "[1] You can do this by creating a dictionary `d = Pkg.installed()` and then looking at version associated with `d[\"PackageName\"]`\n", "\n", "[2] You can specify that you'd like to download a particular version of a package with `Pkg.add(\"PackageName\", v\"x.y.z\")` where `x.y.z` refers to the version number (Note that the `v` is before the quotations on purpose).\n", "\n", "[3] On an Ubuntu machine, you can do this with `sudo apt-get install libgmp-dev`\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "\n", " \n", "
Plotly javascript loaded.
\n", "To load again call
init_notebook(true)\n", " " ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "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** and the values associated with its **subgame perfect equilibria**; **backward induction** and **dynamic programming**; and **linear programming**\n", "\n", "While each of these concepts is worth studying in its own right, here we will focus only on the mechanics necessary to understand the outer approximation algorithm.\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 which specifies who chooses what when\n", "\n", "\n", "### Nash equilibrium\n", "\n", "A *Nash equilibrium* is a collection of actions that pass the following test: 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, $\\mathcal{B}$, 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", "### Prisoner's Dilemma\n", "\n", "We'll use the prisoner's dilemma as an 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 more serious crime but with a slightly lesser sentence than if you had stayed quiet. 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", "
(9, 9) | \n", "(10, 1) | \n", "
(1, 10) | \n", "(3, 3) | \n", "