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.     

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.     

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.     

Unobserved heterogeneity and equilibrium: an experimental study of Bayesian and adaptive learning in normal form games

We describe an experiment based on a simple two-person game designed so that different learning models make different predictions. Econometric analysis of the experimental data reveals clear heterogeneity in the subjects’ learning behavior. But the subjects follow only a few decision rules for basing their play on their information, and these rules have simple cognitive interpretations. There is a unique equilibrium in pure strategies, and many equilibria in mixed strategies. We find that the only equilibrium consistent with the data is one of the mixed strategy equilibria. This equilibrium is shown, surprisingly, to be consistent with Jordan's Bayesian model.     

Competitive behavior in market games: Evidence and theory

We explore whether competitive outcomes arise in an experimental implementation of a market game, introduced by Shubik (1973) [21]. Market games obtain Pareto inferior (strict) Nash equilibria, in which some or possibly all markets are closed. We find that subjects do not coordinate on autarkic Nash equilibria, but favor more efficient Nash equilibria in which all markets are open. As the number of subjects participating in the market game increases, the Nash equilibrium they achieve approximates the associated competitive equilibrium of the underlying economy. Motivated by these findings, we provide a theoretical argument for why evolutionary forces can lead to competitive outcomes in market games.     

Evolution in Bayesian games II: Stability of purified equilibria

We study the evolutionary stability of purified equilibria of two-player normal form games, providing simple sufficient conditions for stability and for instability under the Bayesian best response dynamic.     

Signaling without a common prior: Results on experimental equilibrium selection

The common prior assumption is pervasive in game-theoretic models with incomplete information. This paper investigates experimentally the importance of inducing a correct common prior in a two-person signaling game. Equilibrium selection arguments predict that different equilibria may be selected depending on whether the common prior is induced or not. Indeed, for a specific probability distribution of the sender?s type, the long-run behavior without an induced common prior is shown to be different from the long-run behavior when a common prior is induced, while for other distributions long-run behavior is similar under both regimes. We also present a learning model that allows players to learn about the other players? strategies and the prior distribution of the sender?s type. We show that this learning model accurately accounts for all main features of the data.     

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.     

Multiple equilibria and limit cycles in evolutionary games with Logit Dynamics

This note shows, by means of two simple, three-strategy games, the existence of stable periodic orbits and of multiple, interior steady states in a smooth version of the Best-Response Dynamics, the Logit Dynamics. The main finding is that, unlike Replicator Dynamics, generic Hopf bifurcation and thus, stable limit cycles, occur under the Logit Dynamics, even for three-strategy games. We also show that the Logit Dynamics displays another bifurcation which cannot occur under the Replicator Dynamics: the fold bifurcation, with non-monotonic creation and disappearance of steady states.     

The effects of costless pre-play communication: Experimental evidence from games with Pareto-ranked equilibria

Cheap talk is shown to facilitate coordination on the unique efficient equilibrium in experimental order-statistic games. This result is roughly consistent with theoretical predictions according to which cheap talk promotes efficient Nash play. The evidence concerning the mechanisms that theory appeals to is mixed: Frequent agreement of messages and actions is consistent with messages being viewed as self-committing. Risk in the underlying game and the absence of self-signaling messages may explain why message profiles are not unanimous. Time-varying message profiles can be interpreted as evidence for players trying to negotiate equilibria and/or trying to rely on secret handshakes.     

Hope springs eternal: learning and the stability of cooperation in short horizon repeated games

This paper considers learning rates in finitely repeated prisoners’ dilemmas. If players think their opponents might be relatively cooperative (e.g., tit-for-tat or grim types), they will cooperate in finitely repeated prisoners’ dilemmas (see Kreps et al., J. Econom. Theory 27 (1982) 245). However, if there are actually no cooperative types, players will eventually learn this and cooperation will break down. This paper shows that this learning is extremely slow, so it will take an extremely long time for cooperation to break down.Thus, suppose the world is either “good” or “bad.” The probability of a grim type is δ>0 if the world is good, and zero if the world is bad. Successive generations pair up to play finitely repeated prisoners’ dilemmas. Players observe play in previous generations and use Bayes’ rule to update their prior, π, that the world is good. We show that, if the world is really bad, then π falls per generation on average. Thus, if δ is small, there is less cooperation if the world is good, but cooperation may become more stable. For a representative 19 period repeated prisoners’ dilemma, beliefs fall one percentage point on average after a thousand generations.To derive these learning rates, we must refine existing results on the sensitivity of repeated games to Kreps et al. (1982) type perturbations. Specifically, we show cooperation is possible in perturbed prisoners’ dilemmas repeated O(log(1/δ)) times. This improves significantly on the O(1/δ) results in previous work. The paper thus provides two new reasons why cooperation tends to be stable, even in short horizon repeated games.     

Between-game rule learning in dissimilar symmetric normal-form games

Rule learning posits that decision makers, rather than choosing over actions, choose over behavioral rules with different levels of sophistication. Rules are reinforced over time based on their historically observed payoffs in a given game. Past works on rule learning have shown that when playing a single game over a number of rounds, players can learn to form sophisticated beliefs about others. Here we are interested in learning that occurs between games where the set of actions is not directly comparable from one game to the next. We study a sequence of ten thrice-played dissimilar games. Using experimental data, we find that our rule learning model captures the ability of players to learn to reason across games. However, this learning appears different from within-game rule learning as previously documented. The main adjustment in sophistication occurs by switching from non-belief-based strategies to belief-based strategies. The sophistication of the beliefs themselves increases only slightly over time.     

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.     

Decentralized learning from failure

We study decentralized learning in organizations. Decentralization is captured through Crawford and Haller's [Learning how to cooperate: optimal play in repeated coordination games, Econometrica 58 (1990) 571-595] attainability constraints on strategies. We analyze a repeated game with imperfectly observable actions. A fixed subset of action profiles are successes and all others are failures. The location of successes is unknown. The game is played until either there is a success or the time horizon is reached. We partially characterize optimal attainable strategies in the infinite horizon game by showing that after any fixed time, agents will occasionally randomize while at the same time mixing probabilities cannot be uniformly bounded away from zero.     

Stationary equilibria in stochastic games: structure, selection, and computation

This paper introduces an algorithm to compute stationary equilibria in stochastic games that is guaranteed to converge for almost all such games. Since in general the number of stationary equilibria is overwhelming, we pay attention to the issue of equilibrium selection. We do this by extending the linear tracing procedure to the class of stochastic games, called the stochastic tracing procedure. As a by-product of our results, we extend a recent result on the generic finiteness of stationary equilibria in stochastic games to oddness of equilibria.     

Adaptive learning in extensive form games and sequential equilibrium

Summary. This paper studies adaptive learning in extensive form games and provides conditions for convergence points of adaptive learning to be sequential equilibria. Precisely, we present a set of conditions on learning sequences such that an assessment is a sequential equilibrium if and only if there is a learning sequence fulfilling the conditions, which leads to the assessment. Received: November 5, 1996; revised version: May 28, 1997     

Knightian games and robustness to ambiguity

This paper introduces a notion of robustness to ambiguous beliefs for Bayesian Nash equilibria. An equilibrium is robust if the corresponding strategies remain approximately optimal for a class of games with ambiguous beliefs that results from an appropriately defined perturbation of the belief structure of the original non-ambiguous belief game. The robustness definition is based on a novel definition of equilibrium for games with ambiguous beliefs that requires equilibrium strategies to be approximate best responses for all measures that define a player's belief. Conditions are derived under which robustness is characterized by a newly defined strategic continuity property, which can be verified without reference to perturbations and corresponding ambiguous belief games.     

Delay and information aggregation in stopping games with private information

We consider equilibrium timing decisions in a model with a large number of players and informational externalities. The players have private information about a common payoff parameter that determines the optimal time to invest. They learn from each other in real time by observing past investment decisions. We develop new methods of analysis for such large games, and we give a full characterization of symmetric equilibria. We show that the equilibrium statistical inferences are based on an exponential learning model. Although the beliefs converge to truth, learning takes place too late. Ex-ante welfare is strictly between that without observational learning and that with full information.     

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.     

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.