Computing Nash Equilibria

pure_nash(nfg; ntofind=Inf, tol=1e-8)

Finds all pure action Nash equilibria for a normal form game. It returns an empty array if there is no pure action Nash.

Currently uses a brute force algorithm, but that hopefully will change in the future.

Arguments

• nfg::NormalFormGame: Instance of N-player NormalFormGame.
• ntofind::Inf: Maximal number of pure action Nash equilibria to be found; default is prod(nfg.nums_actions).
• tol::Real : Tolerance to be used to determine best response actions.

Returns

• ne::Vector{NTuple{N,Int}}: Vector of pure action Nash equilibria.

Examples

A 4-player unanimity game example:

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

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

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

julia> println(g)
2×2×2×2 NormalFormGame{4, Float64}:
[:, :, 1, 1] =
 [3.0, 3.0, 3.0, 3.0]  [0.0, 0.0, 0.0, 0.0]
 [0.0, 0.0, 0.0, 0.0]  [0.0, 0.0, 0.0, 0.0]

[:, :, 2, 1] =
 [0.0, 0.0, 0.0, 0.0]  [0.0, 0.0, 0.0, 0.0]
 [0.0, 0.0, 0.0, 0.0]  [0.0, 0.0, 0.0, 0.0]

[:, :, 1, 2] =
 [0.0, 0.0, 0.0, 0.0]  [0.0, 0.0, 0.0, 0.0]
 [0.0, 0.0, 0.0, 0.0]  [0.0, 0.0, 0.0, 0.0]

[:, :, 2, 2] =
 [0.0, 0.0, 0.0, 0.0]  [0.0, 0.0, 0.0, 0.0]
 [0.0, 0.0, 0.0, 0.0]  [4.0, 4.0, 4.0, 4.0]

julia> pure_nash(g)
8-element Vector{NTuple{4, Int64}}:
 (1, 1, 1, 1)
 (2, 2, 1, 1)
 (2, 1, 2, 1)
 (1, 2, 2, 1)
 (2, 1, 1, 2)
 (1, 2, 1, 2)
 (1, 1, 2, 2)
 (2, 2, 2, 2)

lemke_howson(g; init_pivot=1, max_iter=10^6, capping=nothing,
             full_output=Val(false))

Find one mixed-action Nash equilibrium of a 2-player normal-form game by the Lemke–Howson algorithm (Lemke and Howson, 1964), implemented with "complementary pivoting" (see, e.g., von Stengel, 2007 for details).

Arguments

• g::NormalFormGame{2,T}: 2-player NormalFormGame instance.
• init_pivot::Int: Initial pivot, an integer k such that 1 <= k <= m+n, where integers 1, ..., m, and m+1, ..., m+n correspond to the actions of players 1 and 2, respectively.
• max_iter::Int: Maximum number of pivoting steps.
• capping::Union{Int,Nothing}: If supplied, the routine is executed with the heuristic proposed by Codenotti et al. (2008); see Notes below for details.
• full_output::Union{Val{true},Val{false}}: If Val(false), only the computed Nash equilibrium is returned. If Val(true), the return value is (NE, res), where NE is the Nash equilibrium and res is a LHResult object.

Returns

• NE::NTuple{2,Vector{S}}: Tuple of computed Nash equilibrium mixed actions, where the type S is determined by S = float(T).
• res::LHResult: Object containing information about the computation. Returned only when full_output is Val(true). See LHResult for details.

Examples

Consider the following game from von Stengel (2007):

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

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

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

julia> g = NormalFormGame(player1, player2);

julia> println(g)
3×2 NormalFormGame{2, Int64}:
 [3, 3]  [3, 2]
 [2, 2]  [5, 6]
 [0, 3]  [6, 1]

Obtain a Nash equilibrium of this game by lemke_howson with player 1's action 2 (out of the three actions 1, 2, and 3) as the initial pivot:

julia> NE = lemke_howson(g, init_pivot=2)
([0.0, 0.333333, 0.666667], [0.333333, 0.666667])

julia> is_nash(g, NE)
true

Additional information is returned if full_output is set Val(true):

julia> NE, res = lemke_howson(g, init_pivot=2, full_output=Val(true));

julia> res.converged  # Whether the routine has converged
true

julia> res.num_iter  # Number of pivoting steps performed
4

Notes

• This routine is implemented with floating-point arithmetic and thus is subject to numerical instability.

• If capping is set to a positive integer, the routine is executed with the heuristic proposed by Codenotti et al. (2008):

  • For k = init_pivot, init_pivot + 1, …, init_pivot + (m+n-2) (wrapping modulo m + n within 1:m+n), the Lemke-Howson algorithm is executed with k as the initial pivot and capping as the maximum number of pivoting steps.

  • Otherwise, the Lemke-Howson algorithm is executed with init_pivot + (m+n-1) (wrapping modulo m + n within 1:m+n) as the initial pivot, with a limit max_iter on the total number of pivoting steps.

  According to the simulation results for uniformly random games, for medium- to large-size games this heuristic outperforms the basic Lemke-Howson algorithm with a fixed initial pivot, where Codenotti et al. suggest that capping be set to 10.

References

• B. Codenotti, S. De Rossi, and M. Pagan, "An Experimental Analysis of Lemke-Howson Algorithm," arXiv:0811.3247, 2008.
• C. E. Lemke and J. T. Howson, "Equilibrium Points of Bimatrix Games," Journal of the Society for Industrial and Applied Mathematics (1964), 413-423.
• B. von Stengel, "Equilibrium Computation for Two-Player Games in Strategic and Extensive Form," Chapter 3, N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani eds., Algorithmic Game Theory, 2007.

support_enumeration(g)

Compute mixed-action Nash equilibria with equal support size for a 2-player normal form game by support enumeration. For a non-degenerate game input, these are all the Nash equilibria.

The algorithm checks all the equal-size support pairs; if the players have the same number n of actions, there are 2n choose n minus 1 such pairs. This should thus be used only for small games.

Arguments

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

Returns

• ::Vector{NTuple{2,Vector{S}}}: Mixed-action Nash equilibria that are found, where S is Float if T is Int or Float, and Rational if T is Rational.

Examples

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

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

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

julia> g = NormalFormGame(player1, player2);

julia> println(g)
3×2 NormalFormGame{2, Int64}:
 [3, 3]  [3, 2]
 [2, 2]  [5, 6]
 [0, 3]  [6, 1]

julia> support_enumeration(g)
3-element Vector{Tuple{Vector{Float64}, Vector{Float64}}}:
 ([1.0, 0.0, 0.0], [1.0, 0.0])
 ([0.8, 0.2, 0.0], [0.666667, 0.333333])
 ([0.0, 0.333333, 0.666667], [0.333333, 0.666667])

support_enumeration_task(c, g)

Task version of support_enumeration.

Arguments

• c::Channel: Channel to be binded with the support enumeration task.
• g::NormalFormGame{2}: 2-player NormalFormGame instance.

Returns

• ::Task: Runnable task for generating Nash equilibria.

Examples

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

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

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

julia> g = NormalFormGame(player1, player2);

julia> println(g)
3×2 NormalFormGame{2, Int64}:
 [3, 3]  [3, 2]
 [2, 2]  [5, 6]
 [0, 3]  [6, 1]

julia> c = Channel{Tuple{Vector{Float64},Vector{Float64}}}(0);

julia> t = support_enumeration_task(c, g);

julia> bind(c, t); schedule(t);

julia> for NE in c
           display(NE)
       end
([1.0, 0.0, 0.0], [1.0, 0.0])
([0.8, 0.2, 0.0], [0.666667, 0.333333])
([0.0, 0.333333, 0.666667], [0.333333, 0.666667])

lrsnash(g)

Compute in exact arithmetic all extreme mixed-action Nash equilibria of a 2-player normal form game with Integer or Rational payoffs. This function calls the Nash equilibrium computation routine in lrslib (through its Julia wrapper LRSLib.jl) which is based on the "lexicographic reverse search" vertex enumeration algorithm.

Arguments

• g::NormalFormGame{2,<:RatOrInt}: 2-player NormalFormGame instance with Integer or Rational payoffs.

Returns

• ::Vector{NTuple{2,Vector{Rational{BigInt}}}}: Vector of mixed-action Nash equilibria.

Examples

A degenerate game example:

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

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

julia> g = NormalFormGame(player1, player2);

julia> println(g)
3×2 NormalFormGame{2, Int64}:
 [3, 3]  [3, 3]
 [2, 2]  [5, 6]
 [0, 3]  [6, 1]

julia> lrsnash(g)
3-element Vector{Tuple{Vector{Rational{BigInt}}, Vector{Rational{BigInt}}}}:
 ([1//1, 0//1, 0//1], [1//1, 0//1])
 ([1//1, 0//1, 0//1], [2//3, 1//3])
 ([0//1, 1//3, 2//3], [1//3, 2//3])

The set of Nash equilibria of this degenerate game consists of an isolated equilibrium, the third output, and a non-singleton equilibrium component, the extreme points of which are given by the first two outputs.

References

• D. Avis, G. Rosenberg, R. Savani, and B. von Stengel, "Enumeration of Nash Equilibria for Two-Player Games," Economic Theory (2010), 9-37.

hc_solve(g; ntofind=Inf, options...)

Compute all isolated mixed-action Nash equilibria of an N-player normal form game.

This function solves a system of polynomial equations arising from the nonlinear complementarity problem representation of Nash eqiulibrium, by using HomotopyContinuation.jl.

Arguments

• g::NormalFormGame: N-player NormalFormGame instance.
• ntofind=Inf: Number of Nash equilibria to find.
• options...: Optional arguments to pass to HomotopyContinuation.solve. For example, the option seed::UInt32 can set the random seed used during the computations. See the documentation for HomotopyContinuation.solve for details.

Returns

• ::Vector{NTuple{N,Vector{Float64}}}: Vector of mixed-action Nash equilibria.

Examples

Consider the 3-player 2-action game with 9 Nash equilibria in McKelvey and McLennan (1996) "Computation of Equilibria in Finite Games":

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

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> println(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> NEs = hc_solve(g, show_progress=false)
9-element Vector{Tuple{Vector{Float64}, Vector{Float64}, Vector{Float64}}}:
 ([0.0, 1.0], [0.333333, 0.666667], [0.333333, 0.666667])
 ([1.0, 0.0], [0.0, 1.0], [0.0, 1.0])
 ([0.25, 0.75], [0.5, 0.5], [0.333333, 0.666667])
 ([0.5, 0.5], [0.5, 0.5], [1.0, -7.34684e-40])
 ([0.0, 1.0], [1.0, 0.0], [-2.93874e-39, 1.0])
 ([0.0, 1.0], [0.0, 1.0], [1.0, 0.0])
 ([0.5, 0.5], [0.333333, 0.666667], [0.25, 0.75])
 ([1.0, 4.48416e-44], [1.0, -7.17465e-43], [1.0, -4.48416e-44])
 ([0.25, 0.75], [1.0, 0.0], [0.25, 0.75])

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

LHResult

Fields

• NE::NTuple{2,Vector}: Computed Nash equilibrium.
• converged::Bool: Whether the routine has converged.
• num_iter::Int: Number of iterations.
• max_iter::Int: Maximum number of iterations.
• init::Int: Initial condition used.

_get_mixed_actions(tableaux, bases)

From tableaux and bases, extract non-slack basic variables and return a tuple of the corresponding, normalized mixed actions.

Arguments

• tableaux::NTuple{2,Matrix{T}}: Tuple of two arrays containing the tableaux, of shape (n, m+n+1) and (m, m+n+1), respectively.
• bases::NTuple{2,Vector{Int}}: Tuple of two arrays containing the bases, of length n and m, respectively.

Returns

• ::NTuple{2,Vector{T}}: Tuple of mixed actions as given by the non-slack basic variables in the tableaux.

_initialize_tableaux!(payoff_matrices, tableaux, bases)

Given a tuple of payoff matrices, initialize the tableau and basis arrays in place.

For each player i, if minimum(payoff_matrices[i]) is non-positive, then stored in the tableau are payoff values incremented by abs(minimum(payoff_matrices[i])) + 1 (to ensure the tableau does not have a negative entry or a column identically zero).

Suppose that players 1 and 2 have m and n actions, respectively.

• tableaux[1] has n rows and m+n+1 columns, where columns 1:m and m+1:m+n correspond to the non-slack and slack variables, respectively.

• tableaux[2] has m rows and m+n+1 columns, where columns 1:m and m+1:m+n correspond to the slack and non-slack variables, respectively.

• In each tableaux[i], column m+n+1 contains the values of the basic variables (which are initially 1).

• bases[1] and bases[2] contain basic variable indices, which are initially m+1:m+n and 1:m, respectively.

Arguments

• payoff_matrices::NTuple{2,Matrix}: Tuple of two arrays representing payoff matrices, of shape (m, n) and (n, m), respectively.
• tableaux::NTuple{2,Matrix}: Tuple of two arrays to be used to store the tableaux, of shape (n, m+n+1) and (m, m+n+1), respectively. Modified in place.
• bases::NTuple{2,Vector{Int}}: Tuple of two arrays to be used to store the bases, of length n and m, respectively. Modified in place.

Returns

• tableaux, bases

Examples

julia> A = [3 3; 2 5; 0 6];

julia> B = [3 2 3; 2 6 1];

julia> m, n = size(A);

julia> tableaux = (Matrix{Float64}(undef, (n, m+n+1)),
                   Matrix{Float64}(undef, (m, m+n+1)));

julia> bases = (Vector{Int}(undef, n), Vector{Int}(undef, m));

julia> tableaux, bases = _initialize_tableaux!((A, B), tableaux, bases);

julia> tableaux[1]
2×6 Matrix{Float64}:
 3.0  2.0  3.0  1.0  0.0  1.0
 2.0  6.0  1.0  0.0  1.0  1.0

julia> tableaux[2]
3×6 Matrix{Float64}:
 1.0  0.0  0.0  4.0  4.0  1.0
 0.0  1.0  0.0  3.0  6.0  1.0
 0.0  0.0  1.0  1.0  7.0  1.0

julia> bases
([4, 5], [1, 2, 3])

_lemke_howson_capping!(payoff_matrices, tableaux, bases, init_pivot,
                       max_iter::Int, capping)

Execute the Lemke–Howson algorithm with the heuristic proposed by Codenotti et al.

Arguments

• payoff_matrices::NTuple{2,Matrix}: Tuple of two arrays representing payoff matrices, of shape (m, n) and (n, m), respectively.
• tableaux::NTuple{2,Matrix}: Tuple of two arrays to be used to store the tableaux, of shape (n, m+n+1) and (m, m+n+1), respectively. Modified in place.
• bases::NTuple{2,Vector{Int}}: Tuple of two arrays to be used to store the bases, of length n and m, respectively. Modified in place.
• init_pivot::Int: Integer k such that 1 <= k <= m + n.
• max_iter::Int: Maximum number of pivoting steps.
• capping::Int: Value for capping. If set equal to max_iter, the routine is equivalent to the standard Lemke–Howson algorithm.

Returns

• converged::Bool: Whether the pivoting terminated before max_iter was reached.
• total_num_iter::Int: Total number of pivoting steps performed across runs.
• init_pivot_curr::Int: The initial pivot used in the final run.

_lemke_howson_tbl!(tableaux, bases, init_pivot, max_iter)

Main body of the Lemke-Howson algorithm implementation.

Perform the complementary pivoting. Modify tableaux and bases in place.

Arguments

• tableaux::NTuple{2,Matrix}: Tuple of two arrays containing the tableaux, of shape (n, m+n+1) and (m, m+n+1), respectively. Modified in place.
• bases::NTuple{2,Vector{Int}}: Tuple of two arrays containing the bases, of length n and m, respectively. Modified in place.
• init_pivot::Int: Integer k such that 1 <= k <= m + n.
• max_iter::Int: Maximum number of pivoting steps.

Returns

• converged::Bool: Whether the pivoting terminated before max_iter was reached.
• num_iter::Int: Number of pivoting steps performed.

Examples

julia> A = [3 3; 2 5; 0 6];

julia> B = [3 2 3; 2 6 1];

julia> m, n = size(A);

julia> tableaux = (Matrix{Float64}(undef, (n, m+n+1)),
                   Matrix{Float64}(undef, (m, m+n+1)));

julia> bases = (Vector{Int}(undef, n), Vector{Int}(undef, m));

julia> tableaux, bases = _initialize_tableaux!((A, B), tableaux, bases);

julia> _lemke_howson_tbl!(tableaux, bases, 2, 10);

julia> tableaux[1]
2×6 Matrix{Float64}:
 0.875   0.0  1.0   0.375   -0.125   0.25
 0.1875  1.0  0.0  -0.0625   0.1875  0.125

julia> tableaux[2]
3×6 Matrix{Float64}:
 1.0  -1.6         0.8  0.0  0.0  0.2
 0.0   0.466667   -0.4  1.0  0.0  0.0666667
 0.0  -0.0666667   0.2  0.0  1.0  0.133333

julia> bases
([3, 2], [1, 4, 5])

The outputs indicate that in the Nash equilibrium obtained, player 1's mixed action plays actions 3 and 2 with positive weights 0.25 and 0.125, while player 2's mixed action plays actions 1 and 2 (labeled as 4 and 5) with positive weights 0.0666667 and 0.133333.

_indiff_mixed_action!(A, b, own_supp_flags, out,
                      payoff_matrix, own_supp, opp_supp)

Given a player's payoff matrix payoff_matrix, an array own_supp of this player's actions, and an array opp_supp of the opponent's actions, each of length k, compute the opponent's mixed action whose support equals opp_supp and for which the player is indifferent among the actions in own_supp, if any such exists. Return true if such a mixed action exists and actions in own_supp are indeed best responses to it, in which case the outcome is stored in out; false otherwise. Arrays A, b, own_supp_flags are used in intermediate steps.

Arguments

• A::Matrix{T}: Matrix of shape (k+1, k+1) used in intermediate steps, where T<:Real.
• b::Vector{T}: Vector of length k+1 used in intermediate steps, where T<:Real.
• own_supp_flags::BitVector: BitVector of length m used in intermediate steps.
• out::Vector{T}: Vector of length k to store the nonzero values of the desired mixed action, where T<:Real.
• payoff_matrix::Matrix: The player's payoff matrix, of shape (m, n).
• own_supp::Vector{Int}: Vector containing the player's action indices, of length k.
• opp_supp::Vector{Int}: Vector containing the opponent's action indices, of length k.

Returns

• ::Bool: true if a desired mixed action exists and false otherwise.

_support_enumeration_producer(c, payoff_matrices)

Main body of support_enumeration_task.

Arguments

• c::Channel: Channel to be binded with the support enumeration task.
• payoff_matrices::NTuple{2,Matrix{T}}: Payoff matrices of player 1 and player 2, where T<:Real.

Puts

• NTuple{2,Vector{S}}: Tuple of Nash equilibrium mixed actions, where S is Float if T is Int or Float, and Rational if T is Rational.