Skip to content

Computing mixed-strategy Nash Equilibria for games involving multiple players

License

Notifications You must be signed in to change notification settings

forrestlaine/TensorGames.jl

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

TensorGames.jl

CI codecov License

Efficient functionality for computing mixed-strategy Nash equilibrium points of a multi-player, finite action, general-sum game. Uses the PATH solver to compute, via PATHSolver.jl.

Usage:

Supply a vector of cost tensors (one for each player) as input to the function compute_equilibrium. cost_tensors[i][j1,j2,...,jN] is the cost faced by player i when player 1 plays action j1, player 2 plays action j2, etc.

Additional functionality is provided via ChainRulesCore.jl to automatically differentiate solutions with respect to the elements of the cost tensors.

Examples:

The unique Nash equilibrium for the classic rock-paper-scissors game can be found as follows:

julia> A = [0 1 -1; -1 0 1; 1 -1 0];
julia> B = -A;
julia> compute_equilibrium([A, B]).x
2-element Vector{Vector{Float64}}:
 [0.3333333333333333, 0.3333333333333333, 0.3333333333333333]
 [0.3333333333333333, 0.3333333333333333, 0.3333333333333333]

A more complicated random 6 player game looks like this:

julia> d = [3,3,3,3,3,3]; N = 6; cost_tensors = [ randn(d...) for i = 1:N];
julia> sol = compute_equilibrium(cost_tensors);
julia> sol.x
6-element Vector{Vector{Float64}}:
 [0.6147367189021904, 0.0, 0.3852632810978094]
 [0.0, 0.13423377322536922, 0.8657662267746299]
 [0.30978296032333746, 0.6902170396766623, 0.0]
 [0.0, 0.9999999999999994, 0.0]
 [0.5483759176454717, 0.20182657833950027, 0.24979750401502793]
 [0.4761196190151526, 0.38291994996153766, 0.1409604310233093]

Use the function expected_cost(sol.x, cost_tensor) to compute the equilibrium cost for the player whose objective is represented by cost_tensor.

Equilibrium points can also be found when minimum strategy weights are enforced. In other words, for fixed strategies of players (-i), player i's strategy is optimal among those with minimum weight specified by ϵ:

julia> d = [3,3,3,3,3,3]; N = 6; cost_tensors = [ randn(d...) for i = 1:N];
julia> sol = compute_equilibrium(cost_tensors; ϵ=0.05);
julia> sol.x
6-element Vector{Vector{Float64}}:
 [0.41301195721648803, 0.17743767597659854, 0.40955036680691337]
 [0.05, 0.05, 0.8999999999999998]
 [0.05, 0.28627171177928123, 0.6637282882207187]
 [0.07255559962614289, 0.05, 0.8774444003738571]
 [0.1925535715622543, 0.7574464284377457, 0.05]
 [0.8560862135625118, 0.05, 0.0939137864374882]

See additional examples of usage in the test directory, in which checks for the satisfaction of equilibrium conditions and derivative correctness are performed.