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.     

Heterogeneous quantal response equilibrium and cognitive hierarchies

We explore an equilibrium model of games where behavior is given by logit response functions, but payoff responsiveness and beliefs about others' responsiveness are heterogeneous. We study two substantively different ways of extending quantal response equilibrium (QRE) to this setting: (1) Heterogeneus QRE, where players share identical correct beliefs about the distribution of payoff responsiveness; and (2) Truncated QRE, where players have downward looking beliefs, systematically underestimating others' responsiveness. We show that the cognitive hierarchy model is a special case of Truncated QRE. We conduct experiments designed to differentiate these approaches. We find significant evidence of payoff responsive stochastic choice, and of heterogeneity and downward looking beliefs in some games.     

A learning-based model of repeated games with incomplete information

This paper tests a learning-based model of strategic teaching in repeated games with incomplete information. The repeated game has a long-run player whose type is unknown to a group of short-run players. The proposed model assumes a fraction of ‘short-run’ players follow a one-parameter learning model (self-tuning EWA). In addition, some ‘long-run’ players are myopic while others are sophisticated and rationally anticipate how short-run players adjust their actions over time and “teach” the short-run players to maximize their long-run payoffs. All players optimize noisily. The proposed model nests an agent-based quantal-response equilibrium (AQRE) and the standard equilibrium models as special cases. Using data from 28 experimental sessions of trust and entry repeated games, including 8 previously unpublished sessions, the model fits substantially better than chance and much better than standard equilibrium models. Estimates show that most of the long-run players are sophisticated, and short-run players become more sophisticated with experience.     

Scaling Up Learning Models in Public Good Games

We study three learning rules (reinforcement learning (RL), experience weighted attraction learning (EWA), and individual evolutionary learning (IEL)) and how they perform in three different Groves–Ledyard mechanisms. We are interested in how well these learning rules duplicate human behavior in repeated games with a continuum of strategies. We find that RL does not do well, IEL does significantly better, as does EWA, but only if given a small discretized strategy space. We identify four main features a learning rule should have in order to stack up against humans in a minimal competency test: (1) the use of hypotheticals to create history, (2) the ability to focus only on what is important, (3) the ability to forget history when it is no longer important, and (4) the ability to try new things.     

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 2×n games

It is known that every discrete-time fictitious play process approaches equilibrium in nondegenerate 2×2 games, and that every continuous-time fictitious play process approaches equilibrium in nondegenerate 2×2 and 2×3 games. It has also been conjectured that convergence to the set of equilibria holds generally for nondegenerate 2×n games. We give a simple geometric proof of this for the continuous-time process, and also extend the result to discrete-time fictitious play.     

Sequential equilibrium in monotone games: A theory-based analysis of experimental data

A monotone game is an extensive-form game with complete information, simultaneous moves and an irreversibility structure on strategies. It captures a variety of situations in which players make partial commitments and allows us to characterize conditions under which equilibria result in socially desirable outcomes. However, since the game has many equilibrium outcomes, the theory lacks predictive power. To produce stronger predictions, one can restrict attention to the set of sequential equilibria, or Markov equilibria, or symmetric equilibria, or pure-strategy equilibria. This paper explores the relationship between equilibrium behavior in a class of monotone games, namely voluntary contribution games, and the behavior of human subjects in an experimental setting. Several key features of the symmetric Markov perfect equilibrium (SMPE) are consistent with the data. To judge how well the SMPE fits the data, we estimate a model of Quantal Response Equilibrium (QRE) [R. McKelvey, T. Palfrey, Quantal response equilibria for normal form games, Games Econ. Behav. 10 (1995) 6-38; R. McKelvey, T. Palfrey, Quantal response equilibria for extensive form games, Exp. Econ. 1 (1998) 9-41] and find that the decision rules of the QRE model are qualitatively very similar to the empirical choice probabilities.     

A STATISTICAL THEORY OF EQUILIBRIUM IN GAMES*

This paper describes a statistical model of equiliobrium behaviour in games, which we call Quantal Response Equilibrium (QRE). The key feature of the equilibrium is that individuals do not always play responses to the strategies of their opponents, but play better strategies with higher probability than worse strategies. we illustrate several different applications of this approach, and establish a number of theoretical properties of this equilibrium concept. We also demonstrate an equililance between this equilibrium notion and Bayesian games derived from games of complete information with perturbed payoffs     

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.     

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.     

Individual Differences in EWA Learning with Partial Payoff Information

We extend experience-weighted attraction (EWA) learning to games in which only the set of possible foregone payoffs from unchosen strategies are known, and estimate parameters separately for each player to study heterogeneity. We assume players estimate unknown foregone payoffs from a strategy, by substituting the last payoff actually received from that strategy, by clairvoyantly guessing the actual foregone payoff, or by averaging the set of possible foregone payoffs conditional on the actual outcomes. All three assumptions improve predictive accuracy of EWA. Individual parameter estimates suggest that players cluster into two separate subgroups (which differ from traditional reinforcement and belief learning).     

Regular Quantal Response Equilibrium

The structural Quantal Response Equilibrium (QRE) generalizes the Nash equilibrium by augmenting payoffs with random elements that are not removed in some limit. This approach has been widely used both as a theoretical framework to study comparative statics of games and as an econometric framework to analyze experimental and field data. The framework of structural QRE is flexible: it can be applied to arbitrary finite games and incorporate very general error structures. Restrictions on the error structure are needed, however, to place testable restrictions on the data (Haile et al., 2004). This paper proposes a reduced-form approach, based on quantal response functions that replace the best-response functions underlying the Nash equilibrium. We define a regular QRE as a fixed point of quantal response functions that satisfies four axioms: continuity, interiority, responsiveness, and monotonicity. We show that these conditions are not vacuous and demonstrate with an example that they imply economically sensible restrictions on data consistent with laboratory observations. The reduced-form approach allows for a richer set of regular quantal response functions, which has proven useful for estimation purposes. JEL Classification: D62, C73     

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.     

Sophisticated Experience-Weighted Attraction Learning and Strategic Teaching in Repeated Games

Most learning models assume players are adaptive (i.e., they respond only to their own previous experience and ignore others' payoff information) and behavior is not sensitive to the way in which players are matched. Empirical evidence suggests otherwise. In this paper, we extend our adaptive experience-weighted attraction (EWA) learning model to capture sophisticated learning and strategic teaching in repeated games. The generalized model assumes there is a mixture of adaptive learners and sophisticated players. An adaptive learner adjusts his behavior the EWA way. A sophisticated player rationally best-responds to her forecasts of all other behaviors. A sophisticated player can be either myopic or farsighted. A farsighted player develops multiple-period rather than single-period forecasts of others' behaviors and chooses to “teach” the other players by choosing a strategy scenario that gives her the highest discounted net present value. We estimate the model using data from p-beauty contests and repeated trust games with incomplete information. The generalized model is better than the adaptive EWA model in describing and predicting behavior. Including teaching also allows an empirical learning-based approach to reputation formation which predicts better than a quantal-response extension of the standard type-based approach. Journal of Economic Literature Classification Numbers: C72, C91.     

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.     

On the beliefs off the path: Equilibrium refinement due to quantal response and level-k

The extensive form game we study has multiple perfect equilibria, but it has a unique limiting logit equilibrium (QRE) and a unique level-k prediction as k approaches infinity. The convergence paths of QRE and level-k are different, but they converge to the same limit point. We analyze whether subjects adapt beliefs when gaining experience, and if so whether they take the QRE or the level-k learning path. We estimate transitions between level-k and QRE belief rules using Markov-switching rule learning models. The analysis reveals that subjects take the level-k learning path and that they advance gradually, switching from level 1 to 2, from level 2 to equilibrium, and reverting to level 1 after observing opponents deviating from equilibrium. The steady state therefore contains a mixture of behavioral rules: levels 0, 1, 2, and equilibrium with weights of 2.9%, 16.6%, 37.9%, and 42.6%, respectively.     

TESTING THE QUANTAL RESPONSE HYPOTHESIS

We develop a nonparametric test for consistency of player behavior with the quantal response equilibrium (QRE). The test exploits a characterization of the equilibrium choice probabilities in any structural QRE as the gradient of a convex function; thereby, QRE‐consistent choices satisfy the cyclic monotonicity inequalities. Our testing procedure utilizes recent econometric results for moment inequality models. We assess our test using lab experimental data from a series of generalized matching pennies games. We reject the QRE hypothesis in the pooled data but cannot reject individual‐level quantal response behavior for over half of the subjects.     

Basins of attraction and equilibrium selection under different learning rules

A deterministic learning model applied to a game with multiple equilibria produces distinct basins of attraction for those equilibria. In symmetric two-by-two games, basins of attraction are invariant to a wide range of learning rules including best response dynamics, replicator dynamics, and fictitious play. In this paper, we construct a class of three-by-three symmetric games for which the overlap in the basins of attraction under best response learning and replicator dynamics is arbitrarily small. We then derive necessary and sufficient conditions on payoffs for these two learning rules to create basins of attraction with vanishing overlap. The necessary condition requires that with probability one the initial best response is not an equilibrium to the game. The existence of parasitic or misleading actions allows subtle differences in the learning rules to accumulate.