The fictitious play algorithm implemented in Nashpy
is based on the one described in [Fudenberg1998].
The algorithm is as follows:
For a game (A, B) ∈ ℝm × n define κti : S − 1 → ℕ 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.
Thus:
In practice:
κt1 ∈ ℤn κt2 ∈ ℤm
At stage t, each player assumes their opponent is playing a mixed strategy based on κt − 1:
They calculate the expected value of each strategy, which is equivalent to:
st1 ∈ argmaxs ∈ S1Aκt − 12 st2 ∈ argmaxs ∈ S2BTκt − 11
In the case of multiple best responses, a random choice is made.
Note that this algorithm will not always converge and sometimes it depends on the form of the game.
For example:
>>> 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 = tuple(game.fictitious_play(iterations=iterations))
>>> play_counts[-1]
[array([5464., 1436., 3100.]), array([2111., 4550., 3339.])]
We can visualise the lack of convergence:
>>> import matplotlib.pyplot as plt
>>> plt.figure() # doctest: +SKIP
>>> probabilities = [row_play_counts / np.sum(row_play_counts) for row_play_counts, col_play_counts in play_counts]
>>> for number, strategy in enumerate(zip(*probabilities)):
... plt.plot(strategy, label=f"$s_{number}$") # doctest: +SKIP
>>> plt.xlabel("Iteration") # doctest: +SKIP
>>> plt.ylabel("Probability") # doctest: +SKIP
>>> plt.title("Actions taken by row player") # doctest: +SKIP
>>> plt.legend() # doctest: +SKIP
If we modify the game slightly we obtain a different outcome:
>>> 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)
>>> np.random.seed(0)
>>> play_counts = tuple(game.fictitious_play(iterations=iterations))
>>> play_counts[-1]
[array([3290., 3320., 3390.]), array([3356., 3361., 3283.])]
With a clear convergence now visible:
>>> import matplotlib.pyplot as plt
>>> plt.figure() # doctest: +SKIP
>>> probabilities = [row_play_counts / np.sum(row_play_counts) for row_play_counts, col_play_counts in play_counts]
>>> for number, strategy in enumerate(zip(*probabilities)):
... plt.plot(strategy, label=f"$s_{number}$") # doctest: +SKIP
>>> plt.xlabel("Iteration") # doctest: +SKIP
>>> plt.ylabel("Probability") # doctest: +SKIP
>>> plt.title("Actions taken by row player") # doctest: +SKIP
>>> plt.legend() # doctest: +SKIP