Repeated Games

RepeatedGame{N,T}

Type representing an N-player repeated game.

Fields

• sg::NormalFormGame{N, T} : The stage game used to create the repeated game.
• delta::Float64 : 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::Float64 : The common discount rate at which all players discount the future.

Returns

• ::RepeatedGame : The repeated game.

outerapproximation(rpd; nH=32, tol=1e-8, maxiter=500, check_pure_nash=true,
                   verbose=false, nskipprint=50,
                   plib=CDDLib.Library(),
                   lp_solver=GameTheory.highs_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 HiGHS.Optimizer) if no option is needed, or a function (such as GameTheory.highs_optimizer_silent) to supply options.

Returns

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

unpack(rpd)

Helper function that unpacks the elements of a repeated game.

Arguments

• rpd::RepeatedGame : The repeated game.

Returns

• ::Tuple{NormalFormGame, Float64} : 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=highs_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 HiGHS.Optimizer) if no option is needed, or a function (such as GameTheory.highs_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}.

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.