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.

_indiff_mixed_action!(A, b, 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 and b 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.
• 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.