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.

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.

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.

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

_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.