GameTracer

GNMResult

Result of gnm_solve.

Fields

• NEs::Vector{NTuple{N, Vector{Float64}}}: Vector of computed Nash equilibrium mixed actions.
• ret_code::Int: Return code from the underlying C shim.

IPAResult

Result of ipa_solve.

Fields

• NE::NTuple{N, Vector{Float64}}: Tuple of computed Nash equilibrium mixed actions.
• ret_code::Int: Return code from the underlying C shim.

gnm_solve([rng=Random.GLOBAL_RNG, ]g; kwargs...)

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

Arguments

• rng::AbstractRNG: Random number generator used when the default ray is used.
• g::NormalFormGame: A NormalFormGame instance with N >= 2 players.

Keyword Arguments

• ray::AbstractVector{<:Real} = rand(rng, sum(g.nums_actions)): Perturbation ray. Its length must equal sum(g.nums_actions).
• steps::Integer = 100: Maximum number of steps.
• fuzz::Real = 1e-12: Cutoff value for a variety of things.
• lnmfreq::Integer = 3: Frequency parameter. A Local Newton Method subroutine will be run every LNMFreq steps to decrease accumulated errors.
• lnmmax::Integer = 10: Maximum number of iterations within the LNM algorithm.
• lambdamin::Real = -10.0: Minimum lambda value. 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: The equilibrium error tolerance for doing a wobble. If wobbles are disabled, the GNM algorithm terminates if the error reaches this threshold.

Returns

• res::GNMResult{N}: Result object containing information about the computed equilibria.
  • res.NEs: Vector of computed Nash equilibrium mixed actions.
  • res.ret_code: Return code from the underlying C shim.

Examples

Consider the following 2x2x2 game with 9 Nash equilibria from McKelvey and McLennan (1996):

julia> using GameTheory, GameTracer, Random

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> ray = [0.87, 0.04, 0.81, 0.97, 0.17, 0.04]

julia> res = gnm_solve(g; ray=ray);

julia> println(res.ret_code)
9

julia> println(length(res.NEs))
9

julia> println(all(NE -> is_nash(g, NE), 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.

ipa_solve([rng=Random.GLOBAL_RNG, ]g; kwargs...)

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

Arguments

• rng::AbstractRNG: Random number generator used when the default ray is used.
• g::NormalFormGame: A NormalFormGame instance with N >= 2 players.

Keyword Arguments

• ray::AbstractVector{<:Real} = rand(rng, sum(g.nums_actions)): Perturbation ray. Its length must equal sum(g.nums_actions).
• z_init::AbstractVector{<:Real} = ones(sum(g.nums_actions)): Initial point for the iteration. Its length must equal sum(g.nums_actions).
• alpha::Real = 0.02: Step size parameter. Must satisfy 0 < alpha < 1.
• fuzz::Real = 1e-6: Cutoff accuracy for the computed equilibrium.

Returns

• res::IPAResult{N}: Result object containing information about the computed equilibrium.
  • res.NE: Tuple of computed Nash equilibrium mixed actions.
  • res.ret_code: Return code from the underlying C shim.

Examples

Consider the following 3x2 game from von Stengel (2007):

julia> using GameTheory, GameTracer, Random

julia> player1 = Player([3 3; 2 5; 0 6]);  

julia> player2 = Player([3 2 3; 2 6 1]);

julia> g = NormalFormGame(player1, player2);

julia> ray = [0.87, 0.04, 0.81, 0.97, 0.17];

julia> res = ipa_solve(g; ray=ray);

julia> println(res.ret_code > 0)
true

julia> println(length(res.NE))
2

julia> println(is_nash(g, res.NE; tol=1e-6))
true

References

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