Learning by replicator and best-response: the importance of being indifferent

This paper compares two learning processes, namely those generated by replicator and best-response dynamics, from the point of view of the asymptotics of play. We base our study on the intersection of the basins of attraction of locally stable pure Nash equilibria for replicator and best-response dynamics. Local stability implies that the basin of attraction has positive measure but there are examples where the intersection of the basin of attraction for replicator and best-response dynamics is arbitrarily small. We provide conditions, involving the existence of an unstable interior Nash equilibrium, for the basins of attraction of any locally stable pure Nash equilibrium under replicator and best-response dynamics to intersect in a set of positive measure. Hence, for any choice of initial conditions in sets of positive measure, if a pure Nash equilibrium is locally stable, the outcome of learning under either procedure coincides. We provide examples illustrating the above, including some for which the basins of attraction exactly coincide for both learning dynamics. We explore the role that indifference sets play in the coincidence of the basins of attraction of the stable Nash equilibria.     

Melioration learning in games with constant and frequency-dependent pay-offs

The paper explores the implications of melioration learning—an empirically significant variant of reinforcement learning—for game theory. We show that in games with invariable pay-offs melioration learning converges to Nash equilibria in a way similar to the replicator dynamics. Since melioration learning is known to deviate from optimizing behavior when an action’s rewards decrease with increasing relative frequency of that action, we also investigate an example of a game with frequency-dependent pay-offs. Interactive melioration learning is then still appropriately described by the replicator dynamics, but it indeed deviates from rational choice behavior in such a game.     

Brown–von Neumann–Nash dynamics: The continuous strategy case

Brown and von Neumann introduced a dynamical system that converges to saddle points of zero sum games with finitely many strategies. Nash used the mapping underlying these dynamics to prove existence of equilibria in general games. The resulting Brown–von Neumann–Nash dynamics are a benchmark example for myopic adjustment dynamics that, in contrast to replicator dynamics, allow for innovation, but require less rationality than the best response dynamics. This paper studies the BNN dynamics for games with infinitely many strategies. We establish Nash stationarity for continuous payoff functions. For negative semidefinite games (that include zero sum games), we generalize the results of Brown and von Neumann. In addition, we show that evolutionarily robust Nash equilibria are asymptotically stable. A complete stability analysis for doubly symmetric games is also obtained.     

Evolution with Delay

This paper analyses evolutionary models with delays in players’ observations. I apply best response dynamics to symmetric 2 × 2 games, in particular the coordination game and the game with no symmetric pure strategy equilibrium. When the dynamics have no delay, their solutions converge to symmetric Nash equilibria monotonically. However when I introduce delays to the dynamics, although these dynamics represented by differential difference equations are seemingly simple, it shows that they have periodic solutions. JEL Classification Number: C79.     

Equilibrium selection and the dynamic evolution of preferences

A population of fully rational agents plays a symmetric 2-player game in biological fitnesses, but each agent?s play is determined by his payoffs, which are free to evolve according to “survival of the fittest” pressures. An equilibrium-selection mechanism is assumed to exist, and deliver a unique outcome for any given profile of payoffs; this allows the evolution of payoffs to be modeled as a well-defined replicator dynamics. The existing static stability results that “efficient strict Nash implies stability” and “stability implies efficiency” are translated to this dynamic context, although the latter gives way to indeterminacy in the absence of a specific equilibrium-selection mechanism. A strong form of stability is established for the efficient outcome of games with common interests, whilst a weaker stability result is provided for efficient mixed-strategy equilibria of doubly symmetric games. The results are illustrated using the equilibrium-selection mechanism provided by global games.     

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.     

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.     

On the convergence of reinforcement learning

This paper examines the convergence of payoffs and strategies in Erev and Roth's model of reinforcement learning. When all players use this rule it eliminates iteratively dominated strategies and in two-person constant-sum games average payoffs converge to the value of the game. Strategies converge in constant-sum games with unique equilibria if they are pure or if they are mixed and the game is 2×2. The long-run behaviour of the learning rule is governed by equations related to Maynard Smith's version of the replicator dynamic. Properties of the learning rule against general opponents are also studied.     

Evolutionary dynamics on infinite strategy spaces

Summary. The study of evolutionary dynamics was so far mainly restricted to finite strategy spaces. In this paper we show that this unsatisfying restriction is unnecessary. We specify a simple condition under which the continuous time replicator dynamics are well defined for the case of infinite strategy spaces. Furthermore, we provide new conditions for the stability of rest points and show that even strict equilibria may be unstable. Finally, we apply this general theory to a number of applications like the Nash demand game, the War of Attrition, linear-quadratic games, the harvest preemption game, and games with mixed strategies. Received: June 25, 1999; revised version: January 31, 2000     

The replicator dynamics does not lead to correlated equilibria

It is shown that, under the replicator dynamics, all strategies played in correlated equilibrium may be eliminated, so that only strategies with zero marginal probability in all correlated equilibria survive. This occurs in particular in a family of 4×4 games built by adding a strategy to a Rock-Paper-Scissors game.     

Laboratory Federalism: The Open Method of Coordination (OMC) as an Evolutionary Learning Process

In view of the concept of laboratory federalism, the Open Method of Coordination (OMC), adopted by the EU as a mode of governance, can be interpreted as an imitative learning dynamics of the type considered in evolutionary game theory. Its iterative design and focus on good practice are captured by the behavioral rule “imitate the best.” In a redistribution game with utilitarian governments and mobile welfare recipients, we compare the outcomes of imitative behavior (long‐run evolutionary equilibria) and decentralized best‐response behavior (Nash equilibria). The learning dynamics leads to coordination on a strict subset of Nash equilibria, favoring policy choices that can be sustained by a simple majority of Member States.     

Adaptation and complexity in repeated games

The paper presents a learning model for two-player infinitely repeated games. In an inference step players construct minimally complex inferences of strategies based on observed play, and in an adaptation step players choose minimally complex best responses to an inference. When players randomly select an inference from a probability distribution with full support the set of steady states is a subset of the set of Nash equilibria in which only stage game Nash equilibria are played. When players make ‘cautious’ inferences the set of steady states is the subset of self-confirming equilibria with Nash outcome paths. When players use different inference rules, the set of steady states can lie between the previous two cases.     

Egalitarianism and Efficiency in Repeated Symmetric Games

We analyze the symmetric equilibria of repeated symmetric games where there is a conflict of interests over equilibria—the battle-of-the-sexes or the hawk–dove game are key examples. If one restricts attention to symmetric equilibria, efficient equilibria must be egalitarian. For finitely repeated games, and generic discount factors, there is a unique outcome path which ensures efficiency within the class of symmetric equilibria. This is also true for the infinitely repeated games if the players are sufficiently impatient. Journal of Economic Literature Classification Numbers: C72, C73.     

An experimental study of costly coordination

This paper reports data for coordination game experiments with random matching. The experimental design is based on changes in an effort-cost parameter, which do not alter the set of Nash equilibria nor do they alter the predictions of adjustment theories based on imitation or best response dynamics. As expected, however, increasing the effort cost lowers effort levels. Maximization of a stochastic potential function, a concept that generalizes risk dominance to continuous games, predicts this reduction in efforts. An error parameter estimated from initial two-person, minimum-effort games is used to predict behavior in other three-person coordination games.     

A Behavioral Learning Process in Games

This paper studies the cumulative proportional reinforcement (CPR) rule, according to which an agent plays, at each period, an action with a probability proportional to the cumulative utility that the agent has obtained with that action. The asymptotic properties of this learning process are examined for a decision-maker under risk, where it converges almost surely toward the expected utility maximizing action(s). The process is further considered in a two-player game; it converges with positive probability toward any strict pure Nash equilibrium and converges with zero probability toward some mixed equilibria (which are characterized). The CPR rule is compared in its principles with other reinforcement rules and with replicator dynamics. Journal of Economic Literature Classification Number: C72.     

Robustness of equilibria in anonymous local games

This paper studies the robustness of symmetric equilibria in anonymous local games to perturbations of prior beliefs. Two priors are strategically close on a class of games if players receive similar expected payoffs in equilibrium under the priors, for any game in that class. I show that if the structure of payoff interdependencies is sparse in a well-defined sense, the conditions for strategic proximity in anonymous local games are strictly weaker than the conditions for general Bayesian games of Kajii and Morris (1998) [11] when attention is restricted to symmetric equilibria. Hence, by exploiting the properties of anonymous local games, it is possible to obtain stronger robustness results for this class.     

On the Relationship between Risk-Dominance and Stochastic Stability

In a 2 × 2 symmetric game with two symmetric equilibria, one risk-dominates another if and only if the equilibrium strategy is a unique best response to any mixture that gives itself at least a probability of one-half. In a two-person strategic form game, we call a Nash equilibriumglobally risk-dominantif it consists of strategies such that each one of them is a unique best response to any mixture that gives the other at least a probability of one-half. We show that if a weakly acyclic two-person game has a globally risk-dominant equilibrium, then this is the one that is selected by the stochastic equilibrium selection process of Young.Journal of Economic LiteratureClassification Numbers: C72, C73.     

A note on control costs and logit rules for strategic games

We consider best response dynamics with endogenous noise based on a finite game in strategic form. A player can reduce the noise level by expending an extra effort and incurring some disutility or control costs. We specify control costs that result in logit adjustment rules. The stochastically stable states of the dynamic process are partial Nash configurations, that is, states where at least one player plays a best response against the others. If the game has a potential, then the stochastically stable states coincide with the Nash equilibria on which the potential is maximized. RID="*" ID="*" Instructive comments of a referee are gratefully acknowledged. Correspondence to:H. Haller     

Equilibrium selection in coordination games with simultaneous play

Summary. We apply the dynamic stochastic framework proposed in recent evolutionary literature to a class of coordination games played simultaneously by the entire population. In these games payoffs, and hence best replies, are determined by a summary statistic of the population strategy profile. We demonstrate that with simultaneous play, the equilibrium selection depends crucially on how best responses to the summary statistic remain piece-wise constant. In fact, all the strict Nash equilibria in the underlying stage game can be made stochastically stable depending on how the best response mapping generates piece-wise constant best responses. Received: February 12, 2001; revised version: October 29, 2001     

Evolutionary Analyses of Tacit Communication in Van Huyck, Battalio, and Beil's Game Experiments

This paper provides evolutionary interpretations of Van Huyck, Battalio, and Beil's experimental results on coordination game with auction. A set-valued solution concept is defined for a finite population model under a best response evolutionary dynamic and applied to their games. It is shown that our solution concept captures the role of auction as a tacit communication device and predicts the equilibria chosen by players in the real experiments. We also discuss the possibility of constructing a more realistic evolutionary learning model to explain the experimental results.Journal of Economic LiteratureClassification Numbers: C72, C92.