Abstract. We investigate how well continuous-time fictitious play in two-player games performs in terms of average payoff, particularly compared to Nash equilibrium payoff. We show that in many games, fictitious play outperforms Nash equilibrium on average or even at all times, and moreover that any game is linearly equivalent to one in which this is the case. Conversely, we provide conditions under which Nash equilibrium payoff dominates fictitious play payoff. A key step in our analysis is to show that fictitious play dynamics asymptotically converges the set of coarse correlated equilibria (a fact which is implicit in the literature). Continuous-time fictitious play (FP) has been first introduced by Brown [7, 8] and it has since been a standard model for myopic learning, often used as a convenient reference algorithm due to its computational simplicity (see, for example, [11, 31] ). It has been shown to converge to Nash equilibrium in many important classes of games, such as zero-sum games [19] , non-degenerate 2 × n games [3], non-degenerate quasi-supermodular games with diminishing returns or of dimension 3 × n or 4 × 4 [5, 4], and others. On the other hand, convergence to Nash equilibrium (even when it is unique) is not guaranteed, as demonstrated by Shapley's famous example [27] of a 3 × 3 Rock-Paper-Scissors-like game with a stable limit cycle for FP. The question therefore arises whether in the non-convergent case the payoff to the players along trajectories of FP compares favourably to Nash equilibrium payoff. In this paper we investigate the relation between Nash equilibrium payoff and average payoff along FP trajectories. In particular, we show that in many two-player games, FP may in the long run earn a higher payoff to both players than Nash equilibrium play, either on average, or even at all times. We also show that every two-player game is 'linearly equivalent' to one in which FP Pareto dominates Nash equilibrium (at all times, along every non-equilibrium FP orbit). Conversely, we give conditions under which FP is dominated by Nash equilibrium in terms of payoff, and show numerical examples for this (rather atypical) behaviour. The paper is organized as follows. In Section 1 we introduce basic notation. In Section 2 we analyse the limiting behaviour of FP dynamics and show that FP converges to the socalled set of coarse correlated equilibria. In Section 3 we use this to compare the payoff along the limit sets with the Nash equilibrium payoffs. Ultimately, this allows us to show that every bimatrix game is linearly equivalent to one in which FP Pareto dominates Nash equilibrium and we discuss the conditions governing the payoff comparison of these two. In Section 4 we present a particular family of 3×3 games in which FP yields higher average payoff to both players than Nash equilibrium. In Section 5 we investigate the possibility of games in which Nash equilibrium play dominates FP. We also deduce conditions for this and numerically determine examples in which this is the case. The discussion shows that these examples are relatively 'rare'. Finally, in Section 6 we discuss the implications of these results for the notions of equilibrium (in the context of payoff performance of learning algorithms) and game equivalence. The authors would like to thank Christopher Harris, Sergiu Hart and Ulrich Berger for useful discussions and comments.
Ostrovski and van Strien REF studied the convergence and trajectories of FP in continuous time for 3 × 3 games.
Payoff Performance of Fictitious Play
ArXiv
ArXiv
Mathematics Computer Science