Fictitious Play

In real life, players may be myopic and only best respond to other players without calculating or playing a Nash Equilibrium strategy. However, when playing a game repeatedly, they may adapt their strategy based on the history of other players’ actions and eventually converge to a Nash equilibrium. This process is learning in games, as players adapt their beliefs about other players and act rationally w.r.t the beliefs.

Fictitious play is an iterative method of calculating Nash Equilibrium using the above idea without actually playing the game repeatedly. Formally, each player maintain a belief that uniformly mixes the other players’ historical actions ${\mu }_i=\frac{1}{t}{\sum }_{\tau =1}^t{s}_{-i}^{\tau }$, and best respond ${\sigma }_{t+1}\in {\mathrm{BR}}_i({\mu }_i)$. Note that in fictitious play, players have a common belief as it’s generated by the observed history of actions.

Convergence of strategies

Let $({\sigma }^t{)}_{t\in \mathbb{N}}$ be the strategy profile sequence generated by fictitious play. If there exists $T$ such that ${\sigma }^t={\delta }_s$ with $s\in S$ for all $t\ge T$, then $s$ is a PSNE. And if there exists $T$ such that ${\sigma }^T=s^{\ast }$ with $s^{\ast }$ being a strict NE, then ${\sigma }^t=s^{\ast }$ for all $t\ge T$.

Convergence of beliefs

We say $({\sigma }^t{)}_{t\in \mathbb{N}}$ converges to a strategy profile $\sigma \in \Sigma$ in the time-average sense if ${\mu }_{-i}^t(s_i)\to \sigma (s_i)$ as $t\to \infty$ for all $i$ and $s_i$, i.e.,

$$\underset{t\to \infty }{\lim }\frac{1}{t}\sum _{\tau =1}^{t}1\{s_i^{\tau }=s_i\}=\sigma (s_i),$$

where $\sigma (s_i)$ is the marginal probability of $\sigma$ on $s_i$.