Logarithmic tracing procedure

The idea of the logarithmic tracing procedure is to start from a common prior belief about players’ strategies and gradually feed in information about players’ true strategies.

A homotopy parameter \(t\) is introduced: At \(t=0\), players optimize their strategies only with respect to the prior belief about how the other players play. As \(t\) increases, players optimize against a convex combination of prior and equilibrium belief. Finally, at \(t=1\), player optimize only with respect to equilibrium beliefs, i.e. they hold true beliefs about the other players’ strategies and best-respond to them - stationary equilibrium is reached.

Mathematical formulation

In the linear tracing procedure, first introduced by Harsanyi (1975) and Harsanyi/Selten (1988) and later generalized to stochastic games by Herings/Peeters (2004), the game in question is augmented with a set of prior beliefs about players’ strategies as additional primitive. The procedure then performs a gradual transformation of these priors into equilibrium beliefs. Specifically, a set of auxiliary games is defined using a homotopy parameter \(t\in[0,1]\). For \(t=0\), all players choose their optimal strategy in best response only to the prior belief about what the other players play. For \(t\in(0,1)\), players optimize against a convex combination of prior and best responses of other players. For \(t=1\), players optimize only against others’ best responses, beliefs are thus consistent and and equilibrium is reached.

The logarithmic tracing procedure applies the exact same logic, but additionally features logarithmic penalty terms which fade out as \(t\rightarrow1\). For \(t\in[0,1)\), these penalty terms make it artificially costly to play actions with zero probability, leading to fully mixed best responses in the corresponding auxiliary games.

Consider an auxiliary game with prior beliefs \(\boldsymbol{\rho}=(\rho_{sia})_{s\in S,i\in I, a\in A_{si}}\) and homotopy parameter \(t\in[0,1]\). A stationary strategy profile \(\boldsymbol{\sigma}=(\sigma_{sia})_{s\in S,i\in I, a\in A_{si}}\) together with state-player values \(\boldsymbol{V}=(V_{si})_{s\in S,i\in I}\) constitutes a stationary equilibrium in the auxiliary game if and only if

\[\sigma_{si} \; \in \; \underset{\sigma_{si}\in\Delta(A_{si})}{\arg\max} \;\; V_{si}\]
\[\text{s.t. } \quad V_{si} \; = \; \bar{u}^t_{si}(\boldsymbol{\sigma}_s) + \delta_i \sum\limits_{s'\in S} \bar{\phi}^t_{s\rightarrow s'}(\boldsymbol{\sigma}_s) \, V_{s'i} + (1-t) \, \eta \sum\limits_{a\in A_{si}} \nu_{sia} \log(\sigma_{sia})\]

for all states \(s\in S\) and players \(i\in I\), where

\[\bar{u}^t_{si}(\boldsymbol{\sigma}_{s}) \; = \; t \, u_{si}(\boldsymbol{\sigma}_{si}, \boldsymbol{\sigma}_{s,-i}) + (1-t) \, u_{si}(\boldsymbol{\sigma}_{si}, \boldsymbol{\rho}_{s,-i})\]
\[\bar{\phi}^t_{s\rightarrow s'}(\boldsymbol{\sigma}_{s}) \; = \; t \, \phi_{s\rightarrow s'}(\boldsymbol{\sigma}_{si}, \boldsymbol{\sigma}_{s,-i}) + (1-t) \, \phi_{s\rightarrow s'}(\boldsymbol{\sigma}_{si}, \boldsymbol{\rho}_{s,-i})\]

and where \(\eta>0\) and \(\boldsymbol{\nu}=(\nu_{sia})_{s\in S,i\in I, a\in A_{si}} > \boldsymbol{0}\) denote general and action-specific logarithmic penalty weights, respectively. (In our experience, simply using \(\eta=0\) and \(\boldsymbol{\nu}=\boldsymbol{0}\) works fine.)

The equilibrium found by the logarithmic tracing procedure crucially depends on the chosen prior belief \(\boldsymbol{\rho}\).

  • A natural choice for the prior is the centroid strategy profile (uniform mixing over available actions), which is also used in the original work by Harsanyi and Selten.

  • Alternatively, depending on the application, a specific prior different from the centroid might be reasonable.

  • Finally, sGameSolver also allows to use random strategy profiles as priors.

By using the procedure repeatedly with different prior beliefs, one can potentially find multiple different equilibria. If the prior space is searched systematically, one can find all equilibria with a basin of attraction of given size, see section Log Tracing: Searching the prior space.

Further details on the construction of the logarithmic tracing homotopy can be found in Eibelshäuser/Klockmann/Poensgen/v.Schenk (2022).