Repeated Games

RepeatedGame{N,T,TD}

Type representing an N-player repeated game.

Fields

• sg::NormalFormGame{N, T} : The stage game used to create the repeated game.
• delta::TD : The common discount rate at which all players discount the future.

RepeatedGame(p1, p2, delta)

Helper constructor that builds a repeated game for two players.

Arguments

• p1::Player : The first player.
• p2::Player : The second player.
• delta::TD : The common discount rate at which all players discount the future.

Returns

• ::RepeatedGame : The repeated game.

AS(rpd; maxiter=1000, tol=1e-5, u=nothing, verbose=false)

Using AS algorithm to compute the set of payoff pairs of all pure-strategy subgame-perfect equilibria with public randomization for any repeated two-player games with perfect monitoring and discounting, following Abreu and Sannikov (2014).

The geometry computations are performed by direct 2D polygon clipping, with no dependence on a polyhedra library.

If the payoffs are Integer or Rational and the discount factor is Rational, this function performs exact arithmetic and returns a Matrix{Rational{BigInt}}. Otherwise, it defaults to Float64 computation. Note that in exact arithmetic the size of the rational coefficients can grow very rapidly with the number of iterations, so that full convergence is feasible only when the vertices stabilize to simple rational values after a moderate number of iterations, as in the example below; otherwise, bound the computation with maxiter.

Arguments

• rpd::RepeatedGame{2, T, TD} : Two player repeated game with T<:Real, TD<:Real.
• maxiter::Integer : Maximum number of iterations.
• plib : Deprecated and unused; kept for backward compatibility.
• tol::Float64 : Tolerance in differences of set.
• u : The punishment payoff pair if any player deviates. In default, we use minimax payoff pair. If there is better guess, you can specify it by passing a Vector with length 2 (it will be clamped to the minimum payoffs internally if it is otherwise lower).
• verbose::Bool : If true, print convergence information. Defaults to false.

Returns

• ::Matrix{S} : Vertices of the set of payoff pairs, where S is Rational{BigInt} if the payoffs are Integer or Rational and the discount factor is Rational, and Float64 otherwise.

Examples

For Prisoners' Dilemma state game:

julia> pd_payoff = [9.0 1.0; 10.0 3.0];

julia> g = NormalFormGame(pd_payoff)  # symmetric 2-player game
2×2 NormalFormGame{2, Float64}:
 (9.0, 9.0)   (1.0, 10.0)
 (10.0, 1.0)  (3.0, 3.0)

julia> rpd = RepeatedGame(g, 0.75);

julia> vertices = AS(rpd; tol=1e-9);

julia> round.(vertices, digits=6)  # vertices are accurate up to about tol
4×2 Matrix{Float64}:
 3.0   3.0
 9.75  3.0
 9.0   9.0
 3.0   9.75

If payoffs are Integer or Rational and the discount factor is Rational, the computation will be in exact arithmetic:

julia> g_int = NormalFormGame(Int, g)  # convert to Int-valued game
2×2 NormalFormGame{2, Int64}:
 (9, 9)   (1, 10)
 (10, 1)  (3, 3)

julia> rpd_rat = RepeatedGame(g_int, 3//4);  # discount factor as Rational

julia> vertices_rat = AS(rpd_rat; tol=1e-9);

julia> typeof(vertices_rat)
Matrix{Rational{BigInt}} (alias for Array{Rational{BigInt}, 2})

julia> size(vertices_rat)
(6, 2)

There is a utility uniquetolrows which can be used to remove approximately duplicate rows (the retained rows keep the exact values):

julia> V = uniquetolrows(vertices_rat, 1e-8);

julia> typeof(V)
Matrix{Rational{BigInt}} (alias for Array{Rational{BigInt}, 2})

julia> Float64.(V)
4×2 Matrix{Float64}:
 3.0   3.0
 9.75  3.0
 9.0   9.0
 3.0   9.75

outerapproximation(rpd; nH=32, tol=1e-8, maxiter=500, check_pure_nash=true,
                   verbose=false, nskipprint=50,
                   plib=CDDLib.Library(),
                   lp_solver=GameTheory.clp_optimizer_silent)

Approximates the set of equilibrium values for a repeated game with the outer hyperplane approximation described by Judd, Yeltekin, Conklin (2002).

Arguments

• rpd::RepGame2 : Two player repeated game.
• nH::Int : Number of subgradients used for the approximation.
• tol::Float64 : Tolerance in differences of set.
• maxiter::Int : Maximum number of iterations.
• check_pure_nash: Whether to perform a check about whether a pure Nash equilibrium exists.
• verbose::Bool : Whether to display updates about iterations and distance.
• nskipprint::Int : Number of iterations between printing information (assuming verbose=true).
• plib::Polyhedra.Library: Allows users to choose a particular package for the geometry computations. (See Polyhedra.jl docs for more info). By default, it chooses to use CDDLib.Library().
• lp_solver : Linear programming solver to be used internally. Pass a MathOptInterface.AbstractOptimizer type (such as Clp.Optimizer) if no option is needed, or a function (such as GameTheory.clp_optimizer_silent) to supply options.

Returns

• vertices::Matrix{Float64} : Vertices of the outer approximation of the value set.

uniquetolrows(V, tol)

Remove near-duplicate rows from matrix V: scanning from the top, a row is dropped if it is within tol, in the Chebyshev distance, of a row retained earlier. The retained rows are returned unmodified, with the element type of V preserved.

Arguments

• V::AbstractMatrix{T} : Input matrix where T<:Real.
• tol::Real : Tolerance for considering rows as duplicates.

Returns

• ::Matrix{T} : Matrix consisting of the retained rows of V.

unpack(rpd)

Helper function that unpacks the elements of a repeated game.

Arguments

• rpd::RepeatedGame : The repeated game.

Returns

• ::Tuple{NormalFormGame, TD} : A tuple containing the stage game and the delta.

See worst_value_i for documentation

See worst_value_i for documentation

worst_value_i(rpd, H, C, i, lp_solver=clp_optimizer_silent)

Given a constraint w ∈ W, this finds the worst possible payoff for agent i.

Arguments

• rpd::RepGame2 : Two player repeated game.
• H::Matrix{Float64} : Matrix of shape (nH, 2) containing the subgradients here nH is the number of subgradients.
• C::Vector{Float64} : The array containing the hyperplane levels.
• i::Int : The player of interest.
• lp_solver : Linear programming solver to be used internally. Pass a MathOptInterface.AbstractOptimizer type (such as Clp.Optimizer) if no option is needed, or a function (such as GameTheory.clp_optimizer_silent) to supply options.

Returns

• out::Float64 : Worst possible payoff for player i.

RepGame2

Type representing a 2-player repeated game; alias for RepeatedGame{2}.

_R(delta, nums_actions, payoff_array1, payoff_array2,
   best_dev_gains1, best_dev_gains2, poly, u, atol_in)

Apply the R operator of Abreu and Sannikov (2014) once: collect, over all action profiles a, the candidate extreme points of the updated payoff set, namely the stage payoff g(a) itself if it is incentive compatible and in poly, and (1-delta)g(a) + delta*w for the points w of poly clipped to the IC region that lie on an IC boundary. The payoff arrays (and u, poly) are in the internal, centered coordinates set up by AS.

Corresponds to _R in QuantEcon.py, with one difference: the IC-boundary points are collected also when g(a) itself is feasible (they are redundant in that case, and removed with the convex hull computation).

_best_dev_gains(g)

Calculate the payoff gains from deviating from the current action to the best response for each player.

Arguments

• g::NormalFormGame{2, T} : Two-player NormalFormGame.

Returns

• ::Tuple{Matrix{T}, Matrix{T}} : Tuple of best deviating gain matrices for two players. For example, for the first matrix best_dev_gains1, best_dev_gains1[i, j] is the payoff gain for player 1 for deviating to the best response from ith action given player 2 choosing jth action.

_clip(poly, i, c)

Clip the convex polygon poly to the half-plane {w : w[i] >= c}. Intersection points with the boundary line get their i-th coordinate set to exactly c.

_coefficient_type(rpd)

Helper function that determines the coefficient type for computations based on the repeated game's payoff and delta types.

Arguments

• rpd::RepeatedGame : The repeated game.

Returns

• ::Type : Rational{BigInt} if payoffs are rational/integer and delta is rational, Float64 otherwise.

_convex_hull(pts)

Convex hull of 2D points by Andrew's monotone chain algorithm. Return the vertices in counterclockwise order starting from the lexicographically smallest one; duplicate and interior (including collinear) points are dropped.

_find_C(poly, IC1, IC2, atol)

Find the vertices of the convex polygon poly clipped to the IC region {w : w[1] >= IC1, w[2] >= IC2} that lie on an IC boundary, including, when it is in the polygon, the corner point (IC1, IC2).

Corresponds to _find_C in QuantEcon.py, which walks the hull edges; here the same points are obtained by clipping, which also handles degenerate (segment- or point-shaped) polygons.

_in_polygon(q, poly, atol)

Whether the point q is in the convex polygon poly, allowing a slack of atol outside each edge.

_payoff_points(::Type{T}, g)

Return a matrix with each row being a payoff pair point in the two dimensional space.

Arguments

• g::NormalFormGame{2} : Two-player NormalFormGame.

Returns

• v::Matrix{T} : Matrix with size n by 2, where n is the number of action profiles. Each row corresponds to one payoff pair.

_simplify(poly, atol)

Simplify a convex polygon by merging consecutive vertices within atol in Chebyshev distance and dropping vertices within distance atol of the segment joining their neighbors. The distance to the segment, not to the line through it, is used: on degenerate, segment-like polygons the latter would erode true extreme points. No-op when atol is zero (exact arithmetic).

initialize_LP_matrices(rpd, H)

Initialize matrices for the linear programming problems.

Arguments

• rpd::RepeatedGame : Two player repeated game.
• H::Matrix{Float64} : Matrix of shape (nH, 2) containing the subgradients used to approximate the value set, where nH is the number of subgradients.

Returns

• c::Vector{Float64} : Vector of length nH used to determine which subgradient should be used, where nH is the number of subgradients.
• A::Matrix{Float64} : Matrix of shape (nH+2, 2) with nH set constraints and to be filled with 2 additional incentive compatibility constraints.
• b::Vector{Float64} : Vector of length nH+2 to be filled with the values for the constraints.

initialize_sg_hpl(nH, o, r)

Initializes subgradients, extreme points and hyperplane levels for the approximation of the convex value set of a 2 player repeated game.

Arguments

• nH::Int : Number of subgradients used for the approximation.
• o::Vector{Float64} : Origin for the approximation.
• r::Float64 : Radius for the approximation.

Returns

• C::Vector{Float64} : Vector of length nH containing the hyperplane levels.
• H::Matrix{Float64} : Matrix of shape (nH, 2) containing the subgradients.
• Z::Matrix{Float64} : Matrix of shape (nH, 2) containing the extreme points of the value set.

initialize_sg_hpl(rpd, nH)

Initializes subgradients, extreme points and hyperplane levels for the approximation of the convex value set of a 2 player repeated game by choosing an appropriate origin and radius.

Arguments

• rpd::RepeatedGame : Two player repeated game.
• nH::Int : Number of subgradients used for the approximation.

Returns

• C::Vector{Float64} : Vector of length nH containing the hyperplane levels.
• H::Matrix{Float64} : Matrix of shape (nH, 2) containing the subgradients.
• Z::Matrix{Float64} : Matrix of shape (nH, 2) containing the extreme points of the value set.

unitcircle(npts)

Places npts equally spaced points along the 2 dimensional unit circle and returns the points with x coordinates in first column and y coordinates in second column.

Arguments

• npts::Int : Number of points to be placed.

Returns

• pts::Matrix{Float64} : Matrix of shape (nH, 2) containing the coordinates of the points.