On the approximation performance of fictitious play in finite games

Abstract

We study the performance of Fictitious Play (FP), when used as a heuristic for finding an approximate Nash equilibrium of a two-player game. We exhibit a class of two-player games having payoffs in the range $[0,1]$ that show that FP fails to find a solution having an additive approximation guarantee significantly better than $1/2$. Our construction shows that for $n\times n$ games, in the worst case both players may perpetually have mixed strategies whose payoffs fall short of the best response by an additive quantity $1/2 - O(1/n^{1-\delta })$ for arbitrarily small $\delta$. We also show an essentially matching upper bound of $1/2 - O(1/n)$.

Appendices

Appendix A: Proof of Claim 1

Proof

We first show the claim for $i=4n$. At time step $t^\star$, FP prescribes to play $4n$. This in particular means that the action $4n$ achieves a payoff which is at least as much as that of action $2n+1$ after $t^\star -1$ time steps. We write down the inequality given by this fact focusing only on the last $2n$ actions (we will consider actions $1, 2, \ldots , n$ below) and obtain:

$$\begin{aligned}&p_{t^\star -1}(4n) +\alpha p_{t^\star -1}(4n-1)+\beta p_{t^\star -1}(3n) \ge \alpha p_{t^\star -1}(4n)\nonumber \\&\quad +p_{t^\star -1}(2n+1) +\beta p_{t^\star -1}(4n-1) \end{aligned}$$

(18)

and then since $\alpha >1$

$$\begin{aligned} \frac{p_{t^\star -1}(4n)}{p_{t^\star -1}(4n-1)} \le \frac{\alpha -\beta }{\alpha -1}+ \frac{\beta }{\alpha -1} \frac{p_{t^\star -1}(3n)}{p_{t^\star -1}(4n-1)} - \frac{1}{\alpha -1} \frac{p_{t^\star -1}(2n+1)}{p_{t^\star -1}(4n-1)}. \end{aligned}$$

Similarly to the proof of Lemma 3 above this can be shown to imply

$$\begin{aligned} \frac{p_{t^\star }(4n)}{p_{t^\star }(4n-1)}&\le \frac{1}{t^\star }+\frac{\alpha -\beta }{\alpha -1}+ \frac{\beta }{\alpha -1} \frac{p_{t^\star }(3n)}{p_{t^\star }(4n-1)} - \frac{1}{\alpha -1} \frac{p_{t^\star }(2n+1)}{p_{t^\star }(4n-1)} \nonumber \\&\le \frac{1}{t^\star }+\frac{\alpha -\beta }{\alpha -1}+ \frac{\beta }{\alpha -1} \frac{p_{t^\star }(3n)}{p_{t^\star }(4n-1)}. \end{aligned}$$

(19)

We now bound from above the ratio $\frac{\beta }{\alpha -1}\frac{p_{t^\star }(3n)}{p_{t^\star }(4n-1)}$. By repeatedly using Lemmas 3 and 4 we have that

$$\begin{aligned} p_{t^\star }(4n-1)&\ge \frac{\alpha -\beta }{\alpha -1}p_{t^\star }(4n-2) \ge \left(\frac{\alpha -\beta }{\alpha -1}\right)^2 p_{t^\star }(4n-3) \\&\ge \cdots \ge \left(\frac{\alpha -\beta }{\alpha -1}\right)^{n-1} p_{t^\star }(3n). \end{aligned}$$

This yields

$$\begin{aligned} \frac{\beta }{\alpha -1}\frac{p_{t^\star }(3n)}{p_{t^\star }(4n-1)}\le \frac{\beta }{\alpha -1} \left(\frac{\alpha -1}{\alpha -\beta }\right)^{n-1} \le \frac{1}{4 n^{1-\delta }}, \end{aligned}$$

where the last inequality has been proved above (see 11). Therefore, since $t \ge n^{1-\delta }$, (19) implies

$$\begin{aligned} \frac{p_{t^\star }(4n)}{p_{t^\star }(4n-1)} \le 1+\frac{2}{n^{1-\delta }}+\frac{1}{4n^{1-\delta }}. \end{aligned}$$

To conclude this part of the proof we must now consider the contribution to (18) of the actions $1,\ldots , 2n$ that are not in the last block. However, Lemma 5 shows that all those actions are played with probability $1/2^{n^{\delta }}$ at time $t^\star$. Thus the overall contribution of these actions is bounded from above by $\frac{1}{2^{n^{\delta }}} (\alpha -\beta ) \le \frac{1}{2^{n^{\delta }}}$. Similarly to the above, we observe that, for $n$ sufficiently large, $n^\delta \ge \log _2(4n)\ge (1-\delta ) \log _2(4n)$, which implies that $\frac{1}{2^{n^{\delta }}} \le \frac{1}{4n^{1-\delta }}$. This concludes the proof of the upper bound at time $t^\star$ for $i=4n$.

Consider now the case $i=2n+1$. At time step $t^\star +1$, $4n$ is not played by FP, which means that $4n$ is not a best response after $t^\star$ time steps. By Lemma 1, the best response is $2n+1$; then, in particular, the payoff of $2n+1$ is not smaller than the payoff of $4n$ at that time. We write down the inequality given by this fact focusing only on the last $2n$ actions (we will consider the actions in $\{1, 2, \ldots , 2n\}$ below) and obtain

$$\begin{aligned} p_{t^\star }(4n)+\alpha p_{t^\star }(4n-1)+\beta p_{t^\star }(3n) \le \alpha p_{t^\star }(4n)+p_{t^\star }(2n+1)+\beta p_{t^\star }(4n-1) \end{aligned}$$

and then since $\alpha >1$

$$\begin{aligned} \frac{p_{t^\star }(4n)}{p_{t^\star }(4n-1)} \ge \frac{\alpha -\beta }{\alpha -1}+ \frac{\beta }{\alpha -1} \frac{p_{t^\star }(3n)}{p_{t^\star }(4n-1)} - \frac{1}{\alpha -1} \frac{p_{t^\star }(2n+1)}{p_{t^\star }(4n-1)}. \end{aligned}$$

(20)

We next show that $\frac{\beta p_{t^\star }(3n) - p_{t^\star }(2n+1)}{(\alpha -1)p_{t^\star }(4n-1)}\ge$ $- \frac{1}{4n^{1-\delta }}$ or equivalently that $\frac{p_{t^\star }(3n)}{p_{t^\star }(2n+1)} \ge \frac{1}{\beta }-\frac{(\alpha -1)p_{t^\star }(4n-1)}{4\beta n^{1-\delta } p_{t^\star }(2n+1)}$. To prove this it is enough to show that $\frac{p_{t^\star }(3n)}{p_{t^\star }(2n+1)} \ge \frac{1}{\beta }$. We observe that

$$\begin{aligned} \frac{p_{t^\star }(3n)}{p_{t^\star }(2n+1)} = \frac{p_{t^\star }(3n)}{p_{t^\star }(3n-1)}\frac{p_{t^\star }(3n-1)}{p_{t^\star }(3n-2)}\cdots \frac{p_{t^\star }(2n+2)}{p_{t^\star }(2n+1)}\ge \left(\frac{\alpha -\beta }{\alpha -1}\right)^{n-1} \ge \frac{1}{\beta }, \end{aligned}$$

where the first inequality follows from Lemma 3 and the second inequality follows from the observation (similar to the above) that for $n$ sufficiently large $n^{\delta }\ge 2 \log _2(2n)$. Then to summarize, for $\alpha$ and $\beta$ as in the hypothesis, (20) implies that

$$\begin{aligned} \frac{p_{t^\star }(4n)}{p_{t^\star }(4n-1)} \ge 1 + \frac{1}{n^{1-\delta }}-\frac{1}{4 n^{1-\delta }}. \end{aligned}$$

As above we consider actions $1,\ldots , 2n$ and observe that their contribution to the payoffs is bounded from above by $\frac{1}{4n^{1-\delta }}$. Now to conclude the proof of the claim for the case $i=2n+1$ we simply notice that the above implies $p_{t^\star }(4n-1)<p_{t^\star }(4n)$ and Lemmas 3 and 4 imply that $p_{t^\star }(2n+1)<p_{t^\star }(4n-1)$ which together prove the claim. $\square$

Appendix B: Proof of Claim 2

Proof

To prove the claim we first focus on the last block of the game, i.e., the block in which players have actions in $\{2n+1,\ldots ,4n\}$. Recall that our notation uses circular arithmetic on the number of actions of the block.

The fact that action $i+1$ is better than action $i$ after $t-1$ time steps implies that

$$\begin{aligned} p_{t-1}(i)+\alpha p_{t-1}(i-1)+\beta p_{t-1}(i-n) \le \alpha p_{t-1}(i)+p_{t-1}(i+1)+\beta p_{t-1}(i-1), \end{aligned}$$

and then since $\alpha >1$,

$$\begin{aligned} \frac{p_{t-1}(i)}{p_{t-1}(i-1)} \ge \frac{\alpha -\beta }{\alpha -1}+ \frac{\beta }{\alpha -1} \frac{p_{t-1}(i-n)}{p_{t-1}(i-1)} - \frac{1}{\alpha -1} \frac{p_{t-1}(i-2n+1)}{p_{t-1}(i-1)}. \end{aligned}$$

(21)

We next show that $\frac{\beta p_{t-1}(i-n) - p_{t-1}(i-2n+1)}{(\alpha -1)p_{t-1}(i-1)}\ge - \frac{1}{4n^{1-\delta }}$ or equivalently

$$\begin{aligned} \frac{p_{t-1}(i-n)}{p_{t-1}(i-2n+1)} \ge \frac{1}{\beta }-\frac{(\alpha -1)p_{t-1}(i-1)}{4\beta n^{1-\delta } p_{t-1}(i-2n+1)}. \end{aligned}$$

To prove this it is enough to show that $\frac{p_{t-1}(i-n)}{p_{t-1}(i-2n+1)} \ge \frac{1}{\beta }$. We observe that

$$\begin{aligned} \frac{p_{t-1}(i-n)}{p_{t-1}(i-2n+1)} = \frac{p_{t-1}(i-n)}{p_{t-1}(i-n-1)}\cdots \frac{p_{t-1}(i-2n+2)}{p_{t-1}(i-2n+1)}\ge \left(\frac{\alpha -\beta }{\alpha -1}\right)^{n-1} \ge \frac{1}{\beta }, \end{aligned}$$

where the first inequality follows from inductive hypothesis (we can use the inductive hypothesis as all the actions involved above are different from $i$ and $i+1$) and the second inequality follows from the aforementioned observation that, for sufficiently large $n$, $n^{\delta }\ge 2 \log _2(2n)$. Then to summarize, for $\alpha$ and $\beta$ as in the hypothesis, (21) implies that

$$\begin{aligned} \frac{p_{t}(i)}{p_{t}(i-1)} = \frac{p_{t-1}(i)}{p_{t-1}(i-1)} \ge 1 + \frac{1}{n^{1-\delta }}-\frac{1}{4 n^{1-\delta }}, \end{aligned}$$

where the first equality follows from $\ell _{t-1}(i)=\ell _{t}(i)$ and $\ell _{t-1}(i-1)=\ell _{t}(i-1)$, which are true because $s_t=i+1$.

Since action $i+1$ is worse than action $i$ at time step $t-1$ we have that

$$\begin{aligned} p_{t-1}(i)+\alpha p_{t-1}(i-1)+\beta p_{t-1}(i-n) \ge \alpha p_{t-1}(i)+p_{t-1}(i+1)+\beta p_{t-1}(i-1) \end{aligned}$$

and then since $\alpha >1$

$$\begin{aligned} \frac{p_{t-1}(i)}{p_{t-1}(i-1)} \le \frac{\alpha -\beta }{\alpha -1}+ \frac{\beta }{\alpha -1} \frac{p_{t-1}(i-n)}{p_{t-1}(i-1)} - \frac{1}{\alpha -1} \frac{p_{t-1}(i-2n+1)}{p_{t-1}(i-1)}. \end{aligned}$$

Similarly to the proof of Lemma 3 above this can be shown to imply

$$\begin{aligned} \frac{p_{t}(i)}{p_{t}(i-1)}&\le \frac{1}{t}+\frac{\alpha -\beta }{\alpha -1}+ \frac{\beta }{\alpha -1} \frac{p_{t}(i-n)}{p_{t}(i-1)} - \frac{1}{\alpha -1} \frac{p_{t}(i-2n+1)}{p_{t}(i-1)} \nonumber \\&\le \frac{1}{t}+\frac{\alpha -\beta }{\alpha -1}+ \frac{\beta }{\alpha -1} \frac{p_{t}(i-n)}{p_{t}(i-1)}. \end{aligned}$$

(22)

We now bound from above the ratio $\frac{\beta }{\alpha -1}\frac{p_{t}(i-n)}{p_{t}(i-1)}$. By repeatedly using the inductive hypothesis (14) we have that

$$\begin{aligned} p_t(i-1) \ge \frac{\alpha -\beta }{\alpha -1}p_t(i-2) \ge \left(\frac{\alpha -\beta }{\alpha -1}\right)^2 p_t(i-3) \ge \left(\frac{\alpha -\beta }{\alpha -1}\right)^{n-1} p_t(i-n). \end{aligned}$$

(Note again that we can use the inductive hypothesis as none of the actions above is $i$ or $i+1$.) This yields

$$\begin{aligned} \frac{\beta }{\alpha -1}\frac{p_{t}(i-n)}{p_{t}(i-1)}\le \frac{\beta }{\alpha -1} \left(\frac{\alpha -1}{\alpha -\beta }\right)^{n-1} \le \frac{1}{4 n^{1-\delta }}, \end{aligned}$$

where the last inequality is proved above (see 11). Therefore, since $t \ge n^{1-\delta }$, (22) implies that

$$\begin{aligned} \frac{p_{t}(i)}{p_{t}(i-1)} \le 1+\frac{2}{n^{1-\delta }}+\frac{1}{4 n^{1-\delta }}. \end{aligned}$$

To conclude the proof we must now consider the contribution to the payoffs of the actions $1,\ldots , 2n$ that are not in the last block. However, Lemma 5 shows that all those actions are played with probability $1/2^{n^{\delta }}$ at time $t^\star$. Since we prove above (see Lemma 1) that these actions are not played anymore after time step $t^\star$ this implies that $\sum _{j=1}^{2n} p_{t}(j) \le \sum _{j=1}^{2n} p_{t^\star }(j) \le 2^{-n^{\delta }}$. Thus the overall contribution of these actions is bounded from above by $\frac{1}{2^{n^{\delta }}} (\alpha -\beta ) \le \frac{1}{2^{n^{\delta }}} \le \frac{1}{4n^{1-\delta }}$ where the last bound follows from the aforementioned fact that, for $n$ sufficiently large, $n^\delta \ge (1-\delta )\log _2(4n)$. This concludes the proof of Claim 2. $\square$

Appendix C: Proof of Claim 3

Proof

From (21) (and subsequent arguments) we get $p_t(i)>p_t(i-1)$ and from (14) we get $p_t(i-1) > p_t(i-2) > \ldots > p_t(i-2n+1)=p_t(i+1)$. Therefore, $p_t(i)>p_t(i+1)$ thus proving the upper bound. $\square$