sgamesolver 1.0.2

A homotopy-based solver for stochastic games

sgamesolver

Stochastic game solver, short: sgamesolver, is a python package to compute stationary or Markov-perfect equilibria of stochastic games, using the homotopy continuation method.

Some useful links:

• Source code is hosted on github
• Also on github is an issue tracker for bug reports and feature requests
• Documentation is found on readthedocs

sgamesolver is free and open source, under the MIT license. If you use the program for any published research, please cite Eibelshäuser/Poensgen (2019).

Installation

sgamesolver is hosted on PyPI, so installation is usually as simple as

pip install sgamesolver

Head over to the docs for other options for installation.

Usage

Solving a stochastic game is done in three steps:

• define a game
• pick a homotopy function
• set up and run the solver

import sgamesolver

game = sgamesolver.SGame.random_game(64, 2, 4, seed=42)

qre = sgamesolver.homotopy.QRE(game)

qre.solver_setup()
qre.solve()

print(qre.equilibrium)

A quick rundown of these steps – more details are found in the docs:

1. Set up a stochastic game

game = sgamesolver.SGame.random_game(64, 2, 4, seed=42)

Stochastic games are represented by the class SGame. For this quick example, we are using the method random_game to randomize a game with 64 states, 2 players, and 4 actions per player and state. (Setting a seed just makes the result reproducible.)

Of course, you probably didn't come here to solve a random game, but have a specific game in mind. The documentation contains instructions and examples on how to create an SGame which represents the stochastic game you want to solve. (By the way, sgamesolver can also solve normal form games, sequential games, repeated games, and also finite Markov decision problems – each of these is just a simple case of a stochastic game.)

2. Select and set up a homotopy function for your game

qre = sgamesolver.homotopy.QRE(game)

sgamesolver uses the homotopy principle to solve stochastic games, a general technique to solve systems of non-linear equations. In short, the idea is as follows: Instead of solving some very hard problem directly (in our case: finding an equilibrium), a continuous transformation is applied to the system, yielding a related, but much simpler problem, for which one can easily obtain a solution. This transformation is then gradually reversed while tracking the solution, until arriving at a solution for the original problem – here, the desired stationary equilibrium. (You can find more background in the documentation – although such knowledge is not necessary for using the program.)

The (mathematical) function used for this transformation is called homotopy function. In general, there are many possibilities to construct a suitable one. sgamesolver currently includes two: The one we picked for this example, sgamesolver.homotopy.QRE, is based on an extension of quantal response equilibrium to stochastic games (Eibelshäuser/Poensgen 2019b). The other, sgamesolver.homotopy.LogTracing, implements the logarithmic tracing procedure for stochastic games (Eibelshäuser/Klockmann/Poensgen/von Schenk 2022). Which one to pick? In our experience, the former is more robust – while the latter has the advantage that it allows to search for multiple equilibria. More homotopy functions are to come! In any case, please make sure to cite the paper that introduced whichever homotopy you end up using.

3. Let the homotopy solver do its job

Finally, we will set up the solver and start it:

qre.solver_setup()
qre.solve()

Then it's time to lean back and watch for a bit:

==================================================
Start homotopy continuation
Step    37: t =  3.612 ↑, s =  20.47, ds =  3.418

... until ...

Step   247: t = 1.147e+04 ↑, s = 9.385e+04, ds =  1000.
Step   247: Continuation successful. Total time elapsed: 0:00:15
End homotopy continuation
==================================================
An equilibrium was found via homotopy continuation.

... success! Ideally, the solver will be able to find a solution without requiring any further interaction, as in this example. In cases where this does not work out, check out the section on troubleshooting in the documentation.

4. Aftermath

We can now display the solution:

print(qre.equilibrium)

which outputs equilibrium strategies and values for all 64 states:

+++++++++ state00 +++++++++
                       a0    a1    a2    a3  
player0 : v=15.09, σ=[1.000 0.000 0.000 0.000]
player1 : v=15.63, σ=[0.000 0.000 1.000 0.000]

+++++++++ state01 +++++++++
                       a0    a1    a2    a3  
player0 : v=14.76, σ=[0.000 0.961 0.000 0.039]
player1 : v=15.61, σ=[0.354 0.000 0.000 0.646]

+++++++++ state02 +++++++++
                       a0    a1    a2    a3  
player0 : v=14.84, σ=[1.000 0.000 0.000 0.000]
player1 : v=15.61, σ=[0.000 0.000 1.000 0.000]

... (abridged here for brevity) ...

+++++++++ state63 +++++++++
                       a0    a1    a2    a3  
player0 : v=14.92, σ=[0.000 1.000 0.000 0.000]
player1 : v=15.75, σ=[1.000 0.000 0.000 0.000]

Of course, you now also can access equilibrium strategies (and values) as numpy arrays and use them for further calculations or simulations.

eq_strat = qre.equilibrium.strategies
eq_values = qre.equilibrium.values