StrategicGames.jl

A set of functions in pure Julia for Game Theory
Author sylvaticus
Popularity
7 Stars
Updated Last
10 Months Ago
Started In
March 2023

StrategicGames.jl

A set of functions in pure Julia for analysing strategic generic N-players games using concepts and tools of Game Theory.

While written in Julia, the library is easily accessible directly in Python or R using the PyJulia and JuliaCall packages respectively (Python and R examples).

Check out the companion repository GameTheoryNotes for introductory notes on the Game Theory approach and the documentation at the links below for further information on the package and how to use it.

Build status (Github Actions) codecov.io

Basic example

Other examples are available in the Examples section of the documentation.

julia> # Prisoner's dilemma (N players are also supported in all functions)
       payoff = [(-1,-1) (-3,  0);
                 ( 0,-3) (-2, -2)];
julia> # From N-dimensional array of tuples to N+1 arrays of scalars    
       payoff_array = expand_dimensions(payoff);
julia> # Find all the dominated strategies for the two players
       dominated_strategies(payoff_array)
2-element Vector{Vector{Int64}}:
 [1]
 [1]
julia> # Compute one Nash Equilibrium of the Game using complementarity formulation
       eq = nash_cp(payoff_array).equilibrium_strategies
2-element Vector{Vector{Float64}}:
 [0.0, 0.9999999887780999]
 [0.0, 0.9999999887780999]
julia> # Compute all isolated Nash equilibria using support enumeration
       eqs = nash_se(payoff_array,max_samples=Inf)
1-element Vector{NamedTuple{(:equilibrium_strategies, :expected_payoffs, :supports), Tuple{Vector{Vector{Float64}}, Vector{Float64}, Vector{Vector{Int64}}}}}:
 (equilibrium_strategies = [[0.0, 0.9999999999999999], [0.0, 0.9999999999999999]], expected_payoffs = [-1.9999999999999678, -1.9999999999999678], supports = [[2], [2]])
julia> # Best response for player 2
       best_response(payoff_array,[[0.5,0.5],[0.5,0.5]],2).optimal_strategy
2-element Vector{Float64}:
 0.0
 1.0
julia> # Expected payoffs given a specific strategy profile
       expected_payoff(payoff_array,[[1,0],[1,0]])
2-element Vector{Int64}:
 -1
 -1
julia> # Is this strategy profile a Nash equilibrium ?
       is_nash(payoff_array,[[1,0],[1,0]]) 
false

Other game-theory libraries & benchmarks

Julia

  • Nash.jl Has several functions to generate games in normal form, determine best response and if a strategy profile is a Nash Equilibrium (NE) but it doesn't provide a functionality to retrieve a NE, except for 2 players simmetric games
  • GameTheory.jl Inter alia, compute N-players pure strategy NE, 2-players mixed strategy games (lrsnash, using exact arithmetics) and N-players mixed strategies NE using a solver of the polynomial equation representation of the complementarity conditions (hc_solve). However this "generic" N-player solver is slow, as it doesn't seem to have a dominance check. Further, compilation times are huge.

Non-Julia

  • Nashpy: two players only
  • Gambit: many algorithms require installation of gambit other than pygambit. No decimal/rational payoffs in Python
  • Sage Math: two players only
  • GtNash

Benchmarks

The following benchmarks have been run on a Intel Core 5 laptop on StrategicGames v0.0.4. See benchmarks/benchmarks_other_libraries.jl for details.

benchmark_name library method time (ms) memory (MB) alloc n eqs notes
small_3x2 StrategicGames nash_se 3.43 0.55 17694 3
small_3x2 GameTheory hc_solve 15.85 2.73 38255 3
small_3x2 nashpy vertex_enumeration 21.78 3
small_3x2 nashpy lemke_howson_enumeration 1.66 5 repeated results
small_3x2 nashpy support_enumeration 2.68 3
small_3x2 pygambit lcp_solve 0.58 3
small_3x2 pygambit ExternalEnumPolySolver 2.84 3
rand_6x7 StrategicGames nash_se 223.78 346.44 7113996 1
rand_6x7 GameTheory hc_solve 24319.04 219.29 6639449 1
rand_6x7 nashpy vertex_enumeration 483.39 1
rand_6x7 nashpy lemke_howson_enumeration 10.20 13 repeated results
rand_6x7 nashpy support_enumeration 1002.63 0
rand_6x7 pygambit lcp_solve 8.61 1
rand_6x7 pygambit ExternalEnumPolySolver 466356.13 1
rand_dec_6x5 StrategicGames nash_se 61.64 61.19 1383871 3
rand_dec_6x5 GameTheory hc_solve 2891.12 12.38 129350 3
rand_dec_6x5 nashpy vertex_enumeration 115.39 3
rand_dec_6x5 nashpy lemke_howson_enumeration 4.75 11 repeated results
rand_dec_6x5 nashpy support_enumeration 247.32 3
rand_4x4x2 StrategicGames nash_se 2990.28 68.61 1243570 7 1 eq repeated
rand_4x4x2 GameTheory hc_solve 5085.48 14.03 163760 4 2 eq missing
rand_4x4x2 pygambit ExternalEnumPolySolver 924.56 5 1 eq missed
rand_6x7_1st_eq StrategicGames nash_se 7.90 3.70 81730 1
rand_6x7_1st_eq GameTheory hc_solve 20529.34 193.50 5212846 1
rand_6x7_1st_eq nashpy vertex_enumeration 221.68 1
rand_6x7_1st_eq nashpy lemke_howson_enumeration 0.83 1
rand_6x7_1st_eq nashpy support_enumeration (0.00) 0 no eq reported

Acknowledgements

The development of this package at the Bureau d'Economie Théorique et Appliquée (BETA, Nancy) was supported by the French National Research Agency through the Laboratory of Excellence ARBRE, a part of the “Investissements d'Avenir” Program (ANR 11 – LABX-0002-01).

BLogos

Used By Packages

No packages found.