Choosing a homotopy

After having defined the stochastic game of interest, the next step is to choose a suitable homotopy.

In sGameSolver, the following homotopies are implemented:

  1. Quantal response equilibrium (QRE)

  2. Logarithmic tracing procedure

Quantal response equilibrium (QRE)

For background information on the QRE homotopy, see section Quantal response equilibrium (QRE).

The QRE homotopy is parameter-free and does not require additional primitives. Importantly, it respects symmetries: If the game is symmetric, the QRE homotopy will only find symmetric equilibria, never asymmetric ones. In our experience, the QRE homotopy is numerically robust and able to solve any game (that fits into working memory).

The QRE homotopy can be initialized through the class sgamesolver.homotopy.QRE. Specifying the QRE homotopy for a given game of class sgamesolver.SGame (see section Defining games) amounts to

homotopy = sgamesolver.homotopy.QRE(game)

Logarithmic tracing procedure

For background information on the logarithmic tracing homotopy, see section Logarithmic tracing procedure.

The logarithmic tracing homotopy can be initialized through the class sgamesolver.homotopy.LogTracing. It depends on three parameters:

  1. prior beliefs \(\boldsymbol{\rho}=(\rho_{sia})_{s\in S,i\in I, a\in A_{si}}\)

  2. action-specific logarithmic penalty weights \(\boldsymbol{\nu}=(\nu_{sia})_{s\in S,i\in I, a\in A_{si}} > \boldsymbol{0}\)

  3. general logarithmic penalty weight \(\eta>0\)

Unless specified otherwise, the prior belief defaults to the centroid strategy profile while all penalty weights are set to one. In this case, specifying the logarithmic tracing homotopy for a given game of class sgamesolver.SGame (see section Defining games) amounts to

homotopy = sgamesolver.homotopy.LogTracing(game)

Prior beliefs

By default, the prior belief \(\boldsymbol{\rho}\) is chosen to be the centroid strategy profile.

homotopy = sgamesolver.homotopy.LogTracing(game, rho='centroid')

Alternatively, a (uniformly) random prior can be drawn at initialization.

homotopy = sgamesolver.homotopy.LogTracing(game, rho='random')

This is particularly helpful when searching the prior space for different equilibria, see section Log Tracing: Searching the prior space.

Finally, a custom prior can be specified. The prior must be submitted in the form of a 3-dimensional array (with indices [state, player, action]) of the same shape as a strategy profile. If the game in question features different numbers of actions across states or players, the action dimension must equal the largest number of actions and nonexisting actions in other states must be submitted with value zero.

Let’s take the dynamic version of Rock Paper Scissors again as an example. Suppose we would like to start from the prior that both players play rock in all three states. This can be submitted as follows.

import numpy as np

rho = np.array([  # state0
                [[1, 0, 0],    # player0
                 [1, 0, 0]],   # player1
                  # state1
                [[1, 0, 0],    # player0
                 [1, 0, 0]],   # player1
                  # state2
                [[1, 0, 0],    # player0
                 [1, 0, 0]]])  # player1

homotopy = sgamesolver.homotopy.LogTracing(game, rho=rho)

Logarithmic penalty weights

Even though the defaults \(\boldsymbol{\nu}=\boldsymbol{1}\) and \(\eta=1\) work very well in our experience, users have the option to set different values. Here is an example again for the dynamic version of Rock Paper Scissors.

import numpy as np

nu = np.array([  # state0
               [[1, 2, 3],    # player0
                [1, 2, 3]],   # player1
                 # state1
               [[1, 2, 3],    # player0
                [1, 2, 3]],   # player1
                 # state2
               [[1, 2, 3],    # player0
                [1, 2, 3]]])  # player1

homotopy = sgamesolver.homotopy.LogTracing(game, nu=nu, eta=0.5)