GameTracer.jl

ipa_solve(g; kwargs...)
ipa_solve(rng, g; kwargs...)

Compute one mixed-action approximate Nash equilibrium of g with the iterated polymatrix approximation (IPA) algorithm (Govindan and Wilson, 2004).

Arguments

• rng::AbstractRNG = Random.GLOBAL_RNG: Random number generator used to randomly generate the default ray.
• g::GameTheory.NormalFormGame: NormalFormGame instance with N >= 2 players.

Keywords

• ray::AbstractVector{<:Real} = rand(rng, sum(g.nums_actions)): Perturbation ray for the IPA homotopy. Its length must equal sum(g.nums_actions), and entries are interpreted in player-concatenated order. Different rays may lead to different equilibria.
• zh_init::AbstractVector{<:Real} = ones(sum(g.nums_actions)): Initial condition for $\hat{z}$. Its length must equal sum(g.nums_actions). IPA starts with the projection of zh_init onto the mixed-action simplex product.
• alpha::Real = 0.02: Step size fraction of an update of $\hat{z}$. Must satisfy 0 < alpha < 1.
• fuzz::Real = 1e-6: Stopping tolerance for the computed equilibrium.
• max_iter::Integer = 100000: Maximum number of iterations (polymatrix approximations). Must be positive. If it is reached before the stopping tolerance fuzz is met, the last iterate is returned with res.converged == false.
• max_pivots::Integer = 1000000: Maximum number of pivoting steps along the Lemke-Howson path in each solve of a polymatrix approximation. Must be positive. If it is reached, the solver gives up and the last iterate is returned with res.converged == false.

Returns

• res::IPAResult: Result object containing information about the computed equilibrium. res.NE contains an N tuple of mixed actions, one for each player, which is an approximate Nash equilibrium if res.converged is true. See IPAResult for the other fields.

Examples

Consider the following 2x2x2 game from McKelvey and McLennan (1996), which is known to have 9 Nash equilibria:

julia> using GameTheory, GameTracer, Random

julia> rng = MersenneTwister(0);

julia> g = NormalFormGame((2, 2, 2));

julia> g[1, 1, 1] = [9, 8, 12];

julia> g[2, 2, 1] = [9, 8, 2];

julia> g[1, 2, 2] = [3, 4, 6];

julia> g[2, 1, 2] = [3, 4, 4];

julia> g
2×2×2 NormalFormGame{3, Float64}:
[:, :, 1] =
 (9.0, 8.0, 12.0)  (0.0, 0.0, 0.0)
 (0.0, 0.0, 0.0)   (9.0, 8.0, 2.0)

[:, :, 2] =
 (0.0, 0.0, 0.0)  (3.0, 4.0, 6.0)
 (3.0, 4.0, 4.0)  (0.0, 0.0, 0.0)

julia> res = ipa_solve(rng, g);

julia> Base.active_repl.options.iocontext[:compact] = true;  # Reduce digits to display

julia> res.NE
([1.0, 0.0], [1.0, 0.0], [1.0, 0.0])

julia> is_nash(g, res.NE)
true

julia> res.converged  # Whether an equilibrium was found
true

julia> res.num_iter  # Number of iterations performed
28

Calls with different rays generally yield different equilibria (here, rng generates a different ray on each call as its state advances):

julia> res = ipa_solve(rng, g);

julia> res.NE
([0.25, 0.75], [0.5, 0.5], [0.333334, 0.666666])

julia> is_nash(g, res.NE; tol=1e-5)  # Relax tolerance
true

References

• S. Govindan and R. Wilson, "Computing Nash equilibria by iterated polymatrix approximation," Journal of Economic Dynamics and Control, 28 (2004), 1229-1241.

IPAResult

Struct that stores the output of the IPA solver.

Fields

• NE::NTuple{N, Vector{Float64}}: Tuple of computed (approximate) Nash equilibrium mixed actions.
• converged::Bool: Whether an equilibrium was found, i.e., whether the stopping tolerance was met within max_iter iterations without the solver giving up.
• ret_code::Int: Return code from the underlying C shim: 1 on success, 0 if max_iter was reached or the solver gave up.
• num_iter::Int: Number of iterations (polymatrix approximations) performed.
• max_iter::Int: Maximum number of iterations.
• ray::Vector{Float64}: Perturbation ray used by the solver.

gnm_solve(g; kwargs...)
gnm_solve(rng, g; kwargs...)

Compute multiple mixed-action Nash equilibria of g with the global Newton method (GNM) algorithm (Govindan and Wilson, 2003).

Arguments

• rng::AbstractRNG = Random.GLOBAL_RNG: Random number generator used to randomly generate the default ray.
• g::GameTheory.NormalFormGame: NormalFormGame instance with N >= 2 players.

Keywords

• ray::AbstractVector{<:Real} = rand(rng, sum(g.nums_actions)): Perturbation ray for the GNM homotopy. Its length must equal sum(g.nums_actions), and entries are interpreted in player-concatenated order. Different rays may lead to different sets of equilibria.
• steps::Integer = 100: Number of steps to take within a support cell.
• fuzz::Real = 1e-12: Numerical zero threshold used throughout GNM.
• lnmfreq::Integer = 3: Frequency of local newton method (LNM) corrections. An LNM subroutine will be run every lnmfreq steps to decrease accumulated errors.
• lnmmax::Integer = 10: Maximum number of iterations within the LNM subroutine.
• lambdamin::Real = -10.0: Minimum value for the continuation parameter $\lambda$. The equilibrium search terminates if $\lambda$ falls below this value. Must be negative.
• wobble::Bool = false: Whether to use "wobbles" of the perturbation vector to remove accumulated errors. This removes the theoretical guarantee of convergence, but in practice may help keep GNM on the path.
• threshold::Real = 1e-2: Error threshold used to trigger a wobble. If wobble == false, the GNM algorithm terminates if the error reaches this threshold.
• max_iter::Integer = 5000: Maximum number of iterations, where an iteration is the traversal of one support cell. Must be positive. If it is reached, the equilibria found so far are returned.

Returns

• res::GNMResult: Result object containing information about the computed equilibria. res.NEs contains a vector of N tuples of mixed actions, one for each equilibrium. See GNMResult for the other fields.

Examples

Consider the following 2x2x2 game from McKelvey and McLennan (1996), which is known to have 9 Nash equilibria:

julia> using GameTheory, GameTracer, Random

julia> rng = MersenneTwister(50);

julia> g = NormalFormGame((2, 2, 2));

julia> g[1, 1, 1] = [9, 8, 12];

julia> g[2, 2, 1] = [9, 8, 2];

julia> g[1, 2, 2] = [3, 4, 6];

julia> g[2, 1, 2] = [3, 4, 4];

julia> g
2×2×2 NormalFormGame{3, Float64}:
[:, :, 1] =
 (9.0, 8.0, 12.0)  (0.0, 0.0, 0.0)
 (0.0, 0.0, 0.0)   (9.0, 8.0, 2.0)

[:, :, 2] =
 (0.0, 0.0, 0.0)  (3.0, 4.0, 6.0)
 (3.0, 4.0, 4.0)  (0.0, 0.0, 0.0)

julia> res = gnm_solve(rng, g);

julia> Base.active_repl.options.iocontext[:compact] = true;  # Reduce digits to display

julia> res.NEs
2-element Vector{Tuple{Vector{Float64}, Vector{Float64}, Vector{Float64}}}:
 ([0.0, 1.0], [0.0, 1.0], [1.0, 0.0])
 ([0.0, 1.0], [0.333333, 0.666667], [0.333333, 0.666667])

julia> res.num_iter  # Number of iterations performed
3

Calls with different rays generally yield different sets of equilibria (here, rng generates a different ray on each call as its state advances):

julia> res = gnm_solve(rng, g);

julia> res.NEs
9-element Vector{Tuple{Vector{Float64}, Vector{Float64}, Vector{Float64}}}:
 ([1.0, 0.0], [0.0, 1.0], [0.0, 1.0])
 ([0.5, 0.5], [0.333333, 0.666667], [0.25, 0.75])
 ([0.0, 1.0], [0.0, 1.0], [1.0, 0.0])
 ([0.0, 1.0], [0.333333, 0.666667], [0.333333, 0.666667])
 ([0.25, 0.75], [0.5, 0.5], [0.333333, 0.666667])
 ([0.5, 0.5], [0.5, 0.5], [1.0, 0.0])
 ([1.0, 0.0], [1.0, 0.0], [1.0, 0.0])
 ([0.25, 0.75], [1.0, 0.0], [0.25, 0.75])
 ([0.0, 1.0], [1.0, 0.0], [0.0, 1.0])

julia> all([is_nash(g, NE) for NE in res.NEs])
true

References

• S. Govindan and R. Wilson, "A global Newton method to compute Nash equilibria," Journal of Economic Theory, 110 (2003), 65-86.

GNMResult

Struct that stores the output of the GNM solver.

Fields

• NEs::Vector{NTuple{N, Vector{Float64}}}: Vector of tuples of computed Nash equilibrium mixed actions.
• ret_code::Int: Return code from the underlying C shim: the number of equilibria found.
• num_iter::Int: Number of iterations (support cells entered) performed.
• max_iter::Int: Maximum number of iterations.
• ray::Vector{Float64}: Perturbation ray used by the solver.