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.     

Correlated equilibrium in evolutionary models with subpopulations

We study a version of the multipopulation replicator dynamics, where each population is comprised of multiple subpopulations. We establish that correlated equilibrium is a natural solution concept in this setting. Specifically, we show that every correlated equilibrium is equivalent to a stationary state in the replicator dynamics of some subpopulation model. We also show that every interior stationary state, Lyapunov stable state, or limit of an interior solution is equivalent to a correlated equilibrium. We provide an example with a Lyapunov stable limit state whose equivalent correlated equilibrium lies outside the convex hull of the set of Nash equilibria. Finally, we prove that if the matching distribution is a product measure, a state satisfying any of the three conditions listed above is equivalent to a Nash equilibrium.     

On the evolutionary selection of sets of Nash equilibria

It is well established for evolutionary dynamics in asymmetric games that a pure strategy combination is asymptotically stable if and only if it is a strict Nash equilibrium. We use an extension of the notion of a strict Nash equilibrium to sets of strategy combinations called ‘strict equilibrium set’ and show the following. For a large class of evolutionary dynamics, including all monotone regular selection dynamics, every asymptotically stable set of rest points that contains a pure strategy combination in each of its connected components is a strict equilibrium set. A converse statement holds for two-person games, for convex sets and for the standard replicator dynamic.     

ECONOMIC FLUCTUATIONS WITH INTERACTIVE AGENTS: DYNAMIC AND STOCHASTIC EXTERNALITIES*

This paper proposes a general modelling framework for macroeconomic dynamic behaviour of a large collection of interacting agents, and illustrates the procedure for a simple case of agents having the same binary decision set. Evolution over time of the fractions of agents using the same technology is modelled as a birth-and-death stochastic process with endogenized transition rates, and its master equation (Chapman-Kolmogorov backward equation) is expanded into power series in the total number of agents in the model. The first term of the expansion is the aggregate (macroeconomic) dynamic model. Stochastic dynamics of the proportions of agents using the same technology can exhibit multiple equilibria; this paper discusses an example with one locally unstable and two locally stable equilibria, with some simulation computer runs. There are two results of broad implication. One is the demonstration that stochastic dynamics allocates positive probabilities to all locally stable equilibria. Stochastic dynamics thus stands in sharp contrast to deterministic dynamics. In the latter, history (initial conditions) and expectations (often exogenously introduced discontinuous changes in trajectories) uniquely select the basin of attraction in which trajectories are eventually located. The second is the illustration of the usefulness of jump Markov processes in general, and birth-and-death processes in particular in economic modelling. Among several results specific to these processes, we show that the mean first passage time from one locally stable equilibrium to another is proportional to the exponential function of the height of the potential barrier separating the two basins of attraction of these two locally stable equilibria.     

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.     

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.     

Fictitious Play, Shapley Polygons, and the Replicator Equation

For many normal form games, the limiting behavior of fictitious play and the time-averaged replicator dynamics coincide. In particular, we show this for three examples, where this limit is not a Nash equilibrium, but a Shapley polygon. Journal of Economic Literature Classification Numbers: C72, C73.     

Equilibrium selection in bargaining models

This paper examines evolutionary equilibrium selection in bargaining models. We show that random best-response and continuous best-response learning dynamics give rise to (different) simple sufficient conditions for identifying outcomes as stochastically stable. This allows us to characterize the implications of these dynamics in simple bargaining games.     

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.     

Testing the TASP: An experimental investigation of learning in games with unstable equilibria

We report experiments studying mixed strategy Nash equilibria that are theoretically stable or unstable under learning. The Time Average Shapley Polygon (TASP) predicts behavior in the unstable case. We study two versions of Rock-Paper-Scissors that include a fourth strategy, Dumb. The unique Nash equilibrium is identical in the two games, but the predicted frequency of Dumb is much higher in the game where the NE is stable. Consistent with TASP, the observed frequency of Dumb is lower and play is further from Nash in the high payoff unstable treatment. However, Dumb is played too frequently in all treatments.     

Learning to Learn, Pattern Recognition, and Nash Equilibrium

The paper studies a large class of bounded-rationality, probabilistic learning models on strategic-form games. The main assumption is that players “recognize” cyclic patterns in the observed history of play. The main result is convergence with probability one to a fixed pattern of pure strategy Nash equilibria, in a large class of “simple games” in which the pure equilibria are nicely spread along the lattice of the game. We also prove that a necessary condition for convergence of behavior to a mixed strategy Nash equilibrium is that the players consider arbitrarily long histories when forming their predictions.Journal of Economic LiteratureClassification Numbers: C72, D83.     

Cooperation in the sporadically repeated prisoners�� dilemma via reputation mechanisms

We consider the sporadically repeated Prisoners’ Dilemma, examine a class of two-state reputation mechanisms and find that only three have efficient robust perfect Nash equilibria in Markov strategies. Since the asymptotic stability properties are crucial to their plausibility as realistic solutions, we examine replicator dynamics for the simplest reputation mechanism that entails both punishment and penitence. The strategy to cooperate with Good opponents and defect against Bad opponents is a global attractor of replicator dynamics, and hence cooperation is successfully sustained in the long run.     

Unequal Contributions from Symmetric Agents in a Local Interaction Model

The main findings of the theory on the private provision of public goods under the assumptions of symmetric agents and normality are that (1) there exists a unique Nash equilibrium in which everybody contributes the same; and (2) this pattern is stable. We show that these findings no longer hold in a context characterized by local interaction. In this context, it is always possible to find preferences satisfying the assumption of normality such that the symmetric Nash equilibrium is unstable, and there exist asymmetric Nash equilibria which are locally stable.     

The number of pure Nash equilibria in a random game with nondecreasing best responses

We randomly draw a game from a distribution on the set of two-player games with a given size. We compute the distribution and the expectation of the number of pure-strategy Nash equilibria of the game conditional on the game having nondecreasing best-response functions. The conditional expected number of pure-strategy Nash equilibria becomes much larger than the unconditional expected number as the size of the game grows.     

ENDOGENOUS TIMING IN QUALITY CHOICES AND PRICE COMPETITION

We modify the price‐setting version of the vertically differentiated duopoly model by Aoki (2003) by introducing an extended game in which firms noncooperatively choose the timing of moves at the quality stage. Our results show that there are multiple equilibria in pure strategies, whereby firms always select sequential play at the quality stage. We also investigate the mixed‐strategy equilibrium, revealing that the probability of generating outcomes out of equilibrium is higher than the probability of playing one Nash equilibria in pure strategies. In the alternative case with full market coverage, we show that the quality stage is solved in dominant strategies and therefore the choice of roles becomes irrelevant as the Nash and Stackelberg solutions coincide. With full market coverage and corner solution, the results show that the game has a unique subgame perfect equilibrium in pure strategies, where the high‐quality firm takes the lead in the quality stage.     

Equilibrium Unemployment Dynamics

The global dynamics of Pissarides' (1990) equilibrium model of aggregate unemployment are studied in the case of increasing returns to scale in production and constant returns to scale in the matching process. An equilibrium is a dynamic path for the aggregate number of matches generated by best-response search and recruiting investment decisions under rational expectations. Necessary and sufficient conditions for multiple equilibria, including limit cycles, are derived, and illustrative examples are computed. The application of saddle-loop bifurcation theory is a novel feature of the analysis. Since one equilibrium Pareto dominates all the others, a macroeconomic coordination problem exists.     

Cycling in a stochastic learning algorithm for normal form games

In this paper we study a stochastic learning model for 2×2 normal form games that are played repeatedly. The main emphasis is put on the emergence of cycles. We assume that the players have neither information about the payoff matrix of their opponent nor about their own. At every round each player can only observe his or her action and the payoff he or she receives. We prove that the learning algorithm, which is modeled by an urn scheme proposed by Arthur (1993), leads with positive probability to a cycling of strategy profiles if the game has a mixed Nash equilibrium. In case there are strict Nash equilibria, the learning process converges a.s. to the set of Nash equilibria.     

Mixed equilibria are unstable in games of strategic complements

In games with strict strategic complementarities, properly mixed Nash equilibria—equilibria that are not in pure strategies—are unstable for a broad class of learning dynamics.     

Strategy-Specific Barriers to Learning and Nonmonotonic Selection Dynamics

The replicator dynamics are generalized to allow for strategy-specific barriers to learning. The resulting dynamics satisfy neither payoff monotonicity nor payoff positivity, but do satisfy weak payoff positivity. It is shown that initial states from which trajectories converge to a rest point under the replicator dynamics may yield trajectories which approach a stable limit cycle under the generalized replicator dynamics. Furthermore, strategies which are strictly dominated by other pure strategies may survive indefinitely along such nonconvergent paths.Journal of Economic LiteratureClassification Numbers: C73.     

Learning behavior and mixed-strategy Nash equilibria

The paper considers whether an adaptive justification, like those commonly available for non-interactive optimization models, can be found for the mixed-strategy Nash equilibrium. Although it is known that such a justification is frequently available for pure-strategy equilibria, it is shown that all members of a wide class of behaviorally plausible learning mechanisms must fail to converge in ‘almost all’ games in which the equilibrium involves mixed strategies. An exact formal analogy is developed, which allows these learning mechanisms to be viewed as discrete ta?tonnement processes in properly chosen competitive exchange economies. In the analogy, the instability derives from the independence of excess demand functions (except at the boundaries) from ‘own’ prices. This independence arises because of the linearity in probabilities of von Neumann-Morgenstern risk preferences, and therefore does not extend to pure-strategy equilibria in general. Thus, assuming that agents will play equilibrium strategies implicitly assumes more sophistication when the equilibrium involves mixed strategies than when it involves only pure strategies.