[ANN] StrategicGames.jl - Analyse and find 1-all Nash equilibria on generic N-players strategic games

StrategicGames is a new package that, as the name implies, allows to work with strategic games (only in normal form currently). This is the first “feature-useful” release of the package.
All functions work with generic N players, with the payoff of the game encoded as a N-players+1 dimensional array.
Informal benchmarking shows that the package competes favourably with existing libraries (a “formal” benchmarking is in the TODO list, together with parallelisation/code optimisation) and brings to Julia a novelty generalisation to N players of the classical complementarity formulation and the support enumeration method to retrieve the Nash equlibrium/a.

  • Implemented functions:
    • Computatio of the Nash equilibrium
      • nash_se: find one - ∞ Nash equilibria (pure or mixed) using a Support Enumeration algorithm based on certain heuristic and pruning (largely based on Porter-Nudelman-Shoham (2008) )
      • nash_lcp: find one Nash equilibrium using a generalisation to N-players of the classical LCP (linear complementarity) algorithm implemented using JuMP/Ipopt
      • nash_on_support: verify the existence (and eventually compute it) of a Nash equilibrium given a specific support profile
    • Other
      • expected_payoff: compute the expected payoff given a payoff array and a mixed strategy profile
      • dominated_strategies: find (by default iteratively) the strategies that are dominated and hence can’t be in the support of a Nash equilibrium
      • best_response: compute the best response of a given player conditional to the strategy of the other players (using JuMP/GLPK or HiGHS)
      • is_best_response, is_nash: determine whether a particular strategy is a best response and if a strategy profile is a Nash equilibrium
    • Utility functions
      • expand_dimensions: utility function to transform a N-players dimensional array of tuples to a N-players+1 dimensional array of scalars
      • unstack_payoff: unstack a payoff encoded in long format, where the first half of the columns are the action positions for each player and the second half of the columns are the payoffs for the various players, to a N-players+1 dimensional array

Development of this package is done as complement of the student’s notes I am writing concerning the Game Theory MOOC course I am currently attending on Coursera.

7 Likes

Version v0.0.7 released

Here a brief history:

  • v0.0.7 implemented Iterative removal of dominated strategies considering also mixed strategies domination
  • v0.0.6 added precompilation using PrecompileTools.jl
  • v0.0.5 various optimizations for 2 players game
  • v0.0.3 multithreaded nash_se function
  • v0.0.2 main functions implemented, all working at N players (nash_se, nash_lcp, nash_on_support, expected_payoff, best_response, is_best_response, is_nash, expand_dimensions, unstack_payoff)
1 Like