On the Rate of Convergence of Continuous-Time Fictitious Play

This paper shows, first, that continuous-time fictitious play converges (in both payoff and strategy terms) uniformly at ratet ^{− 1}in any finite two-person zero-sum game. The proof is, in essence, a simple Lyapunov-function argument. The convergence of discrete-time fictitious play is a straightforward corollary of this result. The paper also shows that continuous-time fictitious play converges in all finite weighted-potential games. In this case, the convergence is not uniform. It is conjectured, however, that any given continuous-time fictitious play of a finite weighted-potential game converges (in both payoff and strategy terms) at ratet ^{− 1}.Journal of Economic LiteratureClassification Numbers: C6, C7.     

Brown's original fictitious play

What modern game theorists describe as “fictitious play” is not the learning process George W. Brown defined in his 1951 paper. Brown's original version differs in a subtle detail, namely the order of belief updating. In this note we revive Brown's original fictitious play process and demonstrate that this seemingly innocent detail allows for an extremely simple and intuitive proof of convergence in an interesting and large class of games: nondegenerate ordinal potential games.     

Generalised weakened fictitious play

A general class of adaptive processes in games is developed, which significantly generalises weakened fictitious play [Van der Genugten, B., 2000. A weakened form of fictitious play in two-person zero-sum games. Int. Game Theory Rev. 2, 307–328] and includes several interesting fictitious-play-like processes as special cases. The general model is rigorously analysed using the best response differential inclusion, and shown to converge in games with the fictitious play property. Furthermore, a new actor–critic process is introduced, in which the only information given to a player is the reward received as a result of selecting an action—a player need not even know they are playing a game. It is shown that this results in a generalised weakened fictitious play process, and can therefore be considered as a first step towards explaining how players might learn to play Nash equilibrium strategies without having any knowledge of the game, or even that they are playing a game.     

The rate of convergence of continuous fictitious play★

Summary The rate of convergence to Nash equilibrium of continuous fictitious play is determined for a generic set of utilities and initial beliefs in 2 x 2 games. In addition, an example is provided comparing the rate of convergence of discrete fictitious play to the rate for continuous fictitious play. Finally, the convergent dynamic of fictitious play is related to the nonconvergent gradient process dynamic in 2 x 2 games.I would like to thank Jim Jordan for many helpful discussions and for detailed comments on this paper. I also thank an anonymous referee for several helpful suggestions.     

The One-Shot-Deviation Principle for Sequential Rationality

This article analyzes the fictitious play process originally proposed for strategic form games by Brown (1951) and Robinson (1951). We interpret the process as a model of preplay thinking performed by players before acting in a one-shot game. This model is one of bounded rationality. We discuss how fictitious play should then be defined for extensive form games and conclude that this is somewhat problematic. We therefore study two alternative definitions. For either of these, under a weak condition of initial uncertainty, a convergence point of a fictitious play sequence is a sequential equilibrium. For generic games of perfect information initial uncertainty also implies convergence of fictitious play.Journal of Economic LiteratureClassification Number: C72.     

Fictitious Play in Extensive Form Games

This article analyzes the fictitious play process originally proposed for strategic form games by Brown (1951) and Robinson (1951). We interpret the process as a model of preplay thinking performed by players before acting in a one-shot game. This model is one of bounded rationality. We discuss how fictitious play should then be defined for extensive form games and conclude that this is somewhat problematic. We therefore study two alternative definitions. For either of these, under a weak condition of initial uncertainty, a convergence point of a fictitious play sequence is a sequential equilibrium. For generic games of perfect information initial uncertainty also implies convergence of fictitious play.Journal of Economic LiteratureClassification Number: C72.     

Regret-based continuous-time dynamics

Regret-based dynamics have been introduced and studied in the context of discrete-time repeated play. Here we carry out the corresponding analysis in continuous time. We observe that, in contrast to (smooth) fictitious play or to evolutionary models, the appropriate state space for this analysis is the space of distributions on the product of the players' pure action spaces (rather than the product of their mixed action spaces). We obtain relatively simple proofs for some results known in the discrete case (related to ‘no-regret’ and correlated equilibria), and also a new result on two-person potential games (for this result we also provide a discrete-time proof).     

The geometry of inductive reasoning in games

Summary.  This paper contributes to the recent focus on dynamics in noncooperative games when players use inductive learning. The most well-known inductive learning rule, Brown’s fictitious play, is known to converge for games, yet many examples exist where fictitious play reasoning fails to converge to a Nash equilibrium. Building on ideas from chaotic dynamics, this paper develops a geometric conceptualization of instability in games, allowing for a reinterpretation of existing results and suggesting avenues for new results. Received: October 27, 1995 revised version May 2, 1996     

Fictitious play in ‘one-against-all’ multi-player games

Summary. A compound game is an (n + 1) player game based on n two-person subgames. In each of these subgames player 0 plays against one of the other players. Player 0 is regulated, so that he must choose the same strategy in all n subgames. We show that every fictitious play process approaches the set of equilibria in compound games for which all subgames are either zero-sum games, potential games, or games. Received: July 18, 1997; revised version: December 4, 1998     

Learning Dynamics in Games with Stochastic Perturbations

Consider a generalization of fictitious play in which agents′ choices are perturbed by incomplete information about what the other side has done, variability in their payoffs, and unexplained trembles. These perturbed best reply dynamics define a nonstationary Markov process on an infinite state space. It is shown, using results from stochastic approximation theory, that for 2 × 2 games it converges almost surely to a point that lies close to a stable Nash equilibrium, whether pure or mixed. This generalizes a result of Fudenherg and Kreps, who demonstrate convergence when the game has a unique mixed equilibrium. Journal of Economic Literature Classification Numbers: 000, 000, 000.     

Self-tuning experience weighted attraction learning in games

Self-tuning experience weighted attraction (EWA) is a one-parameter theory of learning in games. It addresses a criticism that an earlier model (EWA) has too many parameters, by fixing some parameters at plausible values and replacing others with functions of experience so that they no longer need to be estimated. Consequently, it is econometrically simpler than the popular weighted fictitious play and reinforcement learning models. The functions of experience which replace free parameters “self-tune” over time, adjusting in a way that selects a sensible learning rule to capture subjects’ choice dynamics. For instance, the self-tuning EWA model can turn from a weighted fictitious play into an averaging reinforcement learning as subjects equilibrate and learn to ignore inferior foregone payoffs. The theory was tested on seven different games, and compared to the earlier parametric EWA model and a one-parameter stochastic equilibrium theory (QRE). Self-tuning EWA does as well as EWA in predicting behavior in new games, even though it has fewer parameters, and fits reliably better than the QRE equilibrium benchmark.     

Fictitious play property of the Nash demand game

We show that the Nash demand game has the fictitious play property. We also show that almost every fictitious play process and its associated belief path converge to a pure-strategy Nash equilibrium in the Nash demand game.     

Learning in games with unstable equilibria

We propose a new concept for the analysis of games, the TASP, which gives a precise prediction about non-equilibrium play in games whose Nash equilibria are mixed and are unstable under fictitious play-like learning. We show that, when players learn using weighted stochastic fictitious play and so place greater weight on recent experience, the time average of play often converges in these “unstable” games, even while mixed strategies and beliefs continue to cycle. This time average, the TASP, is related to the cycle identified by Shapley [L.S. Shapley, Some topics in two person games, in: M. Dresher, et al. (Eds.), Advances in Game Theory, Princeton University Press, Princeton, 1964]. The TASP can be close to or quite distinct from Nash equilibrium.     

Coordination failure in repeated games with private monitoring

Players coordinate continuation play in repeated games with public monitoring. We investigate the robustness of such equilibrium behavior with respect to ex-ante small private-monitoring perturbations. We show that with full support of public signals, no perfect public equilibrium is robust if it induces a “regular” 2×2$2\times 2$ coordination game in the continuation play. This regularity condition is violated in all belief-free equilibria. Indeed, with an individual full rank condition, every interior belief-free equilibrium is robust. We also analyze block belief-free equilibria and point out that the notion of robustness is sensitive to whether we allow for uninterpretable signals.     

Dynamics in near-potential games

We consider discrete-time learning dynamics in finite strategic form games, and show that games that are close to a potential game inherit many of the dynamical properties of potential games. We first study the evolution of the sequence of pure strategy profiles under better/best response dynamics. We show that this sequence converges to a (pure) approximate equilibrium set whose size is a function of the “distance” to a given nearby potential game. We then focus on logit response dynamics, and provide a characterization of the limiting outcome in terms of the distance of the game to a given potential game and the corresponding potential function. Finally, we turn attention to fictitious play, and establish that in near-potential games the sequence of empirical frequencies of player actions converges to a neighborhood of (mixed) equilibria, where the size of the neighborhood increases according to the distance to the set of potential games.     

Learning from Personal Experience: One Rational Guy and the Justification of Myopia

The paper examines a large population analog of fictitious play in which players learn from personal experience, focusing on what happens when a single rational player is added to the population. Because the learning process naturally generates contagion dynamics, the rational player at times has an incentive to act nonmyopically. In 2 × 2 games the dynamics are asymmetric and favor risk dominant equilibria. A variety of other examples are presented.Journal of Economic LiteratureClassification Number: C7.     

A myopic adjustment process leading to best-reply matching

We analyze a myopic strategy adjustment process in strategic-form games. It is shown that the steady states of the continuous time limit, which is constructed assuming frequent play and slow adjustment of strategies, are exactly the best-reply matching equilibria, as discussed by Droste, Kosfeld, and Voorneveld (2000. Mimeo, Tilburg University). In a best-reply matching equilibrium every player ‘matches’ the probability of playing a pure strategy to the probability that this pure strategy is a best reply to the pure-strategy profile played by his opponents. We derive stability results for the steady states of the continuous time limit in 2×2 bimatrix games and coordination games. Analyzing the asymptotic behavior of the stochastic adjustment process in discrete time shows convergence to minimal curb sets of the game. Moreover, absorbing states of the process correspond to best-reply matching equilibria of the game.     

Evolution in games with randomly disturbed payoffs

We consider a simple model of stochastic evolution in population games. In our model, each agent occasionally receives opportunities to update his choice of strategy. When such an opportunity arises, the agent selects a strategy that is currently optimal, but only after his payoffs have been randomly perturbed. We prove that the resulting evolutionary process converges to approximate Nash equilibrium in both the medium run and the long run in three general classes of population games: stable games, potential games, and supermodular games. We conclude by contrasting the evolutionary process studied here with stochastic fictitious play.     

Learning in games with strategic complementarities revisited

Fictitious play is a classical learning process for games, and games with strategic complementarities are an important class including many economic applications. Knowledge about convergence properties of fictitious play in this class of games is scarce, however. Beyond games with a unique equilibrium, global convergence has only been claimed for games with diminishing returns [V. Krishna, Learning in games with strategic complementarities, HBS Working Paper 92-073, Harvard University, 1992]. This result remained unpublished, and it relies on a specific tie-breaking rule. Here we prove an extension of it by showing that the ordinal version of strategic complementarities suffices. The proof does not rely on tie-breaking rules and provides some intuition for the result.     

Level-k analysis of experimental centipede games

As one of the best-known examples of the paradox of backward induction, centipede games have prompted a host of studies with various approaches and explanations (McKelvey and Palfrey, 1992, Fey et al., 1996, Nagel and Tang, 1998, Rapoport et al., 2003, Palacios-Huerta and Volij, 2009). Focusing on initial plays observed in experiments, this paper attempts to offer another explanation based on thorough study of level-k models as applied to these games. Borrowing ideas from the cognitive hierarchy model (Camerer et al., 2004), the authors constructed a group of models based on levels of rationality, and also tested for various assumptions on the play of the most naïve player type in these models. It was found that level-k models generally perform better than the agent quantal response equilibrium (AQRE) model and its variant with altruistic player types for increasing-pie centipede games, while the AQRE model with altruistic player types performs better in constant-pie games.