Learning to alternate

The Individual Evolutionary Learning (IEL) model explains human subjects’ behavior in a wide range of repeated games which have unique Nash equilibria. Using a variation of ‘better response’ strategies, IEL agents quickly learn to play Nash equilibrium strategies and their dynamic behavior is like that of humans subjects. In this paper we study whether IEL can also explain behavior in games with gains from coordination. We focus on the simplest such game: the 2 person repeated Battle of Sexes game. In laboratory experiments, two patterns of behavior often emerge: players either converge rapidly to one of the stage game Nash equilibria and stay there or learn to coordinate their actions and alternate between the two Nash equilibria every other round. We show that IEL explains this behavior if the human subjects are truly in the dark and do not know or believe they know their opponent’s payoffs. To explain the behavior when agents are not in the dark, we need to modify the basic IEL model and allow some agents to begin with a good idea about how to play. We show that if the proportion of inspired agents with good ideas is chosen judiciously, the behavior of IEL agents looks remarkably similar to that of human subjects in laboratory experiments.     

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.     

Nearly compact and continuous normal form games: characterizations and equilibrium existence

Normal form games are nearly compact and continuous (NCC) if they can be understood as games played on strategy spaces that are dense subsets of the strategy spaces of larger compact games with jointly continuous payoffs. There are intrinsic algebraic, measure theoretic, functional analysis, and finite approximability characterizations of NCC games. NCC games have finitely additive equilibria, and all their finitely additive equilibria are equivalent to countably additive equilibria on metric compactifications. The equilibrium set of an NCC game depends upper hemicontinuously on the specification of the game and contains only the limits of approximate equilibria of approximate games.     

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.     

Co-ordination, Spillovers, and Cheap Talk

We analyze the role of cheap-talk in two player games with one-sided incomplete information. We identify conditions under which (1) players can fully communicate and coordinate on efficient Nash equilibria of the underlying complete information game; and (2) players cannot communicate so cheap-talk does not alter the equilibrium set of the Bayesian game. We present examples that illustrate several issues that arise when there is two-sided incomplete information. Journal of Economic Literature Classification Numbers: C72, D82.     

Information structures and decentralizability of equilibria

Summary Decentralizability with respect to an equilibrium concept means that those equilibria for an extensive game and its agent normal form game coincide for any given payoffs. We consider decentralizability of Nash equilibrium, subgame perfect equilibrium, and perfect equilibrium. For each equilibrium concept we give a necessary and sufficient condition on the information structure of an extensive game for decentralizability to hold. When it holds it does not matter if agents with the same objectives decide independently or have someone coordinate their actions.The author thanks Satish Chand, Mamoru Kaneko, Akira Okada and participants at seminars at the Australian National University, Kyoto University, University of Tsukuba, and The First Decentralization Conference in Japan held at Keio University for valuable suggestions and comments.     

Equilibrium play in matches: Binary Markov games

We study two-person extensive form games, or “matches,” in which the only possible outcomes (if the game terminates) are that one player or the other is declared the winner. The winner of the match is determined by the winning of points, in “point games.” We call these matches binary Markov games. We show that if a simple monotonicity condition is satisfied, then (a) it is a Nash equilibrium of the match for the players, at each point, to play a Nash equilibrium of the point game; (b) it is a minimax behavior strategy in the match for a player to play minimax in each point game; and (c) when the point games all have unique Nash equilibria, the only Nash equilibrium of the binary Markov game consists of minimax play at each point. An application to tennis is provided.     

Robust equilibria under non-common priors

This paper considers the robustness of equilibria to a small amount of incomplete information, where players are allowed to have heterogeneous priors. An equilibrium of a complete information game is robust to incomplete information under non-common priors if for every incomplete information game where each player's prior assigns high probability on the event that the players know at arbitrarily high order that the payoffs are given by the complete information game, there exists a Bayesian Nash equilibrium that generates behavior close to the equilibrium in consideration. It is shown that for generic games, an equilibrium is robust under non-common priors if and only if it is the unique rationalizable action profile. Set-valued concepts are also introduced, and for generic games, a smallest robust set is shown to exist and coincide with the set of a posteriori equilibria.     

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.     

Stochastic strategy adjustment in coordination games

Summary. The paper explores a model of equilibrium selection in coordination games, where agents from an infinite population stochastically adjust their strategies to changes in their local environment. Instead of playing perturbed best-response, it is assumed that agents follow a rule of ‘switching to better strategies with higher probability’. This behavioral rule is related to bounded-rationality models of Rosenthal (1989) and Schlag (1998). Moreover, agents stay with their strategy in case they successfully coordinate with their local neighbors. Our main results show that both strict Nash equilibria of the coordination game correspond to invariant distributions of the process, hence evolution of play is not ergodic but instead depends on initial conditions. However, coordination on the risk-dominant equilibrium occurs with probability one whenever the initial fraction contains infinitely many agents, independent of the spatial distribution of these agents. Received: March 14, 2000; revised version: June 21, 2001     

Knowing What Others Know: Coordination Motives in Information Acquisition

We explore how optimal information choices change the predictions of strategic models. When a large number of agents play a game with strategic complementarity, information choices exhibit complementarity as well: if an agent wants to do what others do, they want to know what others know. This makes heterogeneous beliefs difficult to sustain and may generate multiple equilibria. In models with substitutability, agents prefer to differentiate their information choices. We use these theoretical results to examine the role of information choice in recent price-setting models and to propose modelling techniques that ensure equilibrium uniqueness.     

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.     

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.     

Essential equilibria of large generalized games

We characterize the essential stability of games with a continuum of players, where strategy profiles may affect objective functions and admissible strategies. Taking into account the perturbations defined by a continuous mapping from a complete metric space of parameters to the space of continuous games, we prove that essential stability is a generic property and every game has a stable subset of equilibria. These results are extended to discontinuous large generalized games assuming that only payoff functions are subject to perturbations. We apply our results in an electoral game with a continuum of Cournot-Nash equilibria, where the unique essential equilibrium is that only politically engaged players participate in the electoral process. In addition, employing our results for discontinuous games, we determine the stability properties of competitive prices in large economies.     

On the endogeneity of Cournot-Nash and Stackelberg equilibria: games of accumulation

We characterize equilibria of games with two properties: (i) Agents have the opportunity to adjust their strategic variable after their initial choices and before payoffs occur; but (ii) they can only add to their initial amounts. The equilibrium set consists of just the Cournot-Nash outcome, one or both Stackelberg outcomes, or a continuum of points including the Cournot-Nash outcome and one or both Stackelberg outcomes. A simple theorem that uses agents’ standard one-period reaction functions and the one-period Cournot-Nash and Stackelberg equilibria delineates the equilibrium set. Applications include contribution, oligopoly, and rent-seeking games.     

On Sustaining Cooperation without Public Observations

This paper examines a dynamic game in which each player only observes a private and imperfect signal on the actions played. Our main result is that in a repeated prisoner's dilemma where defections are irreversible (at least for a long enough period of time), patient enough players may achieve almost efficient outcomes. Dealing with models of imperfect private monitoring is difficult because (i) continuation games are games of incomplete information, hence they do not have the same structure as the original game. In particular, continuation equilibria are correlated equilibria. (ii) Players are typically uncertain about their opponents' past observations and actions, and they use their entire own private history to learn about these actions. As a result equilibrium strategies are in general nontrivial and increasingly complex functions of past observations. We bypass these difficulties by looking at correlated equilibria of the original game and find correlated equilibria in which the decision problem faced by each player remains the same over time. Journal of Economic Literature Classification Numbers: C72.     

A three way equivalence

In view of the well known core equivalence results in atomless economies, coincidence of market game equilibrium allocations with competitive allocations is tantamount to a three way equivalence between market game mechanisms, competitive equilibria and the core. Based on this idea we study equilibrium refinements of market games, which allow us to use the core equivalence machinery in order to provide an exact market game characterization of competitive equilibria.     

Properties and applications of dual reduction

The dual reduction process, introduced by Myerson, allows a finite game to be reduced to a smaller-dimensional game such that any correlated equilibrium of the reduced game is an equilibrium of the original game. We study the properties and applications of this process. It is shown that generic two-player normal form games have a unique full dual reduction (a known refinement of dual reduction) and all strategies that have probability zero in all correlated equilibria are eliminated in all full dual reductions. Among other applications, we give a linear programming proof of the fact that a unique correlated equilibrium is a Nash equilibrium, and improve on a result due to Nau, Gomez-Canovas and Hansen on the geometry of Nash equilibria and correlated equilibria.     

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.     

Existence of equilibria in countable games: An algebraic approach

Although mixed extensions of finite games always admit equilibria, this is not the case for countable games, the best-known example being Waldʼs pick-the-larger-integer game. Several authors have provided conditions for the existence of equilibria in infinite games. These conditions are typically of topological nature and are rarely applicable to countable games. Here we establish an existence result for the equilibrium of countable games when the strategy sets are a countable group, the payoffs are functions of the group operation, and mixed strategies are not requested to be σ-additive. As a byproduct we show that if finitely additive mixed strategies are allowed, then Waldʼs game admits an equilibrium. Finally we extend the main results to uncountable games.