Stochastic fictitious play

The stochastic fictitious play algorithm implemented in Nashpy is based on the one given in [Hofbauer2002].

As explained in [Fudenberg1998] stochastic fictitious play “avoids the discontinuity inherent in standard fictitious play, where a small change in the data can lead to an abrupt change in behaviour.”

The algorithm is designed to converge in cases where fictitious play does not converge. Note that in some cases this will require a thoughtful choice of the etha and epsilon_bar parameters.

For a game \((A, B)\in\mathbb{R}^{m\times n}\) define \(\kappa_t^{i}:S^{-1}\to\mathbb{N}\) to be a function that in a given time interval \(t\) for a player \(i\) maps a strategy \(s\) from the opponent’s strategy space \(S^{-1}\) to a number of total times the opponent has played \(s\).

As per standard Fictitious play, each player assumes their opponent is playing a mixed strategy based on \(\kappa_{t-1}\). If no play has taken place, then the probability of playing each action is assumed to be equal. The assumed mixed strategies of a player’s opponent are multplied by the player’s own payoff matrices to calculate the expected payoff of each action.

A stochastic pertubation \(\epsilon_i\) is added to each expected payoff \(\pi_i\) to give a pertubated payoff. Each \(\epsilon_i\) is independent of each \(\pi_i\) and is a random number between 0 and epsilon_bar.

A logit choice function is used to map the pertubated payoff to a non-negative probability distribution, corresponding to the probability with which each strategy is chosen by the player. The logit choice function can be seen below:

\[L_i( \pi ) = \frac{\exp (\eta ^{-1} \pi_i )}{\sum_{j}\exp (\eta ^{-1} \pi_j)}\]

Discussion

Using the same game from the fictitious play discussion section, we can visualise a lack of convergence when using the default value of epsilon_bar:

>>> import numpy as np
>>> import nashpy as nash
>>> A = np.array([[0, 1, 0], [0, 0, 1], [1, 0, 0]])
>>> B = np.array([[0, 0, 1], [1, 0, 0], [0, 1, 0]])
>>> game = nash.Game(A, B)
>>> iterations = 10000
>>> np.random.seed(0)
>>> play_counts_and_distribuions = tuple(game.stochastic_fictitious_play(iterations=iterations))
>>> play_counts, distributions = play_counts_and_distribuions[-1]
>>> print(play_counts)
[array([3937., 1907., 4156.]), array([2823., 5458., 1719.])]

>>> import matplotlib.pyplot as plt
>>> plt.figure() 
>>> probabilities = [
...     row_play_counts / np.sum(row_play_counts)
...     if np.sum(row_play_counts) != 0
...     else row_play_counts + 1 / len(row_play_counts)
...     for (row_play_counts, col_play_counts), _ in play_counts_and_distribuions]
>>> for number, strategy in enumerate(zip(*probabilities)):
...     plt.plot(strategy, label=f"$s_{number}$") 
>>> plt.xlabel("Iteration") 
>>> plt.ylabel("Probability") 
>>> plt.title("Actions taken by row player") 
>>> plt.legend() 
../_images/main7.svg

Observe below that the game converges when passing values for etha and epsilon_bar:

>>> A = np.array([[1 / 2, 1, 0], [0, 1 / 2, 1], [1, 0, 1 / 2]])
>>> B = np.array([[1 / 2, 0, 1], [1, 1 / 2, 0], [0, 1, 1 / 2]])
>>> game = nash.Game(A, B)
>>> iterations = 10000
>>> etha = 0.1
>>> epsilon_bar = 10**-1
>>> np.random.seed(0)
>>> play_counts_and_distribuions = tuple(game.stochastic_fictitious_play(iterations=iterations, etha=etha, epsilon_bar=epsilon_bar))
>>> play_counts_and_distribuions[-1]
([array([3300., 3293., 3407.]), array([3320., 3372., 3308.])], [array([0.33502382, 0.41533594, 0.24964024]), array([0.18890743, 0.42793694, 0.38315563])])
>>> import matplotlib.pyplot as plt
>>> plt.figure() 
>>> probabilities = [
...     row_play_counts / np.sum(row_play_counts)
...     if np.sum(row_play_counts) != 0
...     else row_play_counts + 1 / len(row_play_counts)
...     for (row_play_counts, col_play_counts), _ in play_counts_and_distribuions]
>>> for number, strategy in enumerate(zip(*probabilities)):
...     plt.plot(strategy, label=f"$s_{number}$") 
>>> plt.xlabel("Iteration") 
>>> plt.ylabel("Probability") 
>>> plt.title("Actions taken by row player") 
>>> plt.legend() 
../_images/main8.svg