On the limit perfect public equilibrium payoff set in repeated and stochastic games

This paper provides a dual characterization of the existing ones for the limit set of perfect public equilibrium payoffs in a class of finite stochastic games (in particular, repeated games) as the discount factor tends to one. As a first corollary, the folk theorems of Fudenberg et al. (1994), Kandori and Matsushima (1998) and Hörner et al. (2011) obtain. As a second corollary, it is shown that this limit set of payoffs is a convex polytope when attention is restricted to perfect public equilibria in pure strategies. This result fails for mixed strategies, even when attention is restricted to two-player repeated games.     

Existence of nontrivial equilibria in repeated games with imperfect private monitoring

We consider finitely repeated games with imperfect private monitoring, and provide several sufficient conditions for such a game to have an equilibrium whose outcome is different from repetition of Nash equilibria of the stage game. Surprisingly, the conditions are consistent with uniqueness of the stage game equilibrium. A class of repeated chicken is shown to satisfy the condition.     

Repeated signaling games

I analyze a class of repeated signaling games in which the informed player's type is persistent and the history of actions is perfectly observable. In this context, a large class of possibly complex sequences of signals can be supported as the separating equilibrium actions of the “strong type” of the informed player. I characterize the set of such sequences. I also characterize the sequences of signals in least cost separating equilibria (LCSE) of these games. In doing this, I introduce a state variable that can be interpreted as a measure of reputation. This gives the optimization problem characterizing the LCSE a recursive structure. I show that, in general, the equilibrium path sequences of signals have a simple structure. The shapes of the optimal sequences depend critically on the relative concavities of the payoff functions of different types, which measure the relative preferences towards payoff smoothing.     

Learning with bounded memory in games

We study learning with bounded memory in zero-sum repeated games with one-sided incomplete information. The uninformed player has only a fixed number of memory states available. His strategy is to choose a transition rule from state to state, and an action rule, which is a map from each memory state to the set of actions. We show that the equilibrium transition rule involves randomization only in the intermediate memory states. Such randomization, or less frequent updating, is interpreted as a way of testing the opponent, which generates inertia in the player's behavior and is the main short-run bias in information processing exhibited by the bounded memory player.     

Nash equilibrium when players account for the complexity of their forecasts

Nash equilibrium is often interpreted as a steady state in which each player holds the correct expectations about the other players' behavior and acts rationally. This paper investigates the robustness of this interpretation when there are small costs associated with complicated forecasts. The model consists of a two-person strategic game in which each player chooses a finite machine to implement a strategy in an infinitely repeated 2×2 game with discounting. I analyze the model using a solution concept called Nash Equilibrium with Stable Forecasts (ESF). My main results concern the structure of equilibrium machine pairs. They provide necessary and sufficient conditions on the form of equilibrium strategies and plays. In contrast to the “folk theorem,” these structural properties place severe restrictions on the set of equilibrium paths and payoffs. For example, only sequences of the one-shot Nash equilibrium can be generated by any ESF of the repeated game of chicken.     

Breeding hybrid strategies: optimal behaviour for oligopolists

Oligopolistic pricing decisions-in which the choice variable is not dichotomous as in the simple prisoner's dilemma but continuous-have been modeled as a generalized prisoner's dilemma (GPD) by Fader and Hauser, who sought, in the two MIT Computer Strategy Tournaments, to obtain an effective generalization of Rapoport's Tit for Tat for the three-person repeated game. Holland's genetic algorithm and Axelrod's representation of contingent strategies provide a means of generating new strategies in the computer, through machine learning, without outside submissions.The paper discusses how findings from two-person tournaments can be extended to the GPD, in particular how the author's winning strategy in the Second MIT Competitive Strategy Tournament could be bettered. The paper provides insight into how oligopolistic pricing competitors can successfully compete, and underlines the importance of niche strategies, successful against a particular environment of competitors.Bootstrapping, or breeding strategies against their peers, provides a means of examining whether repetition leads to cooperation: we show that it can, under certain conditions, for simple and extended two- and three-person GPD repeated games. The paper concludes with a discussion of the relationship between Selten's trembling-hand perfect equilibrium and Maynard Smith's evolutionarily stable strategies, with practical simulations of successful and unsuccessful invasions by new strategies.     

Purification in the infinitely-repeated prisoners' dilemma

This paper investigates the Harsanyi [Harsanyi, J.C., 1973. Games with randomly disturbed payoffs: A new rationale for mixed-strategy equilibrium points. International Journal of Game Theory 2 (1), 1–23]-purifiability of mixed strategies in the repeated prisoners' dilemma with perfect monitoring. We perturb the game so that in each period, a player receives a private payoff shock which is independently and identically distributed across players and periods. We focus on the purifiability of one-period memory mixed strategy equilibria used by Ely and Välimäki [Ely, J.C., Välimäki, J., 2002. A robust folk theorem for the prisoner's dilemma. Journal of Economic Theory 102 (1), 84–105] in their study of the repeated prisoners' dilemma with private monitoring. We find that any such strategy profile is not the limit of one-period memory equilibrium strategy profiles of the perturbed game, for almost all noise distributions. However, if we allow infinite memory strategies in the perturbed game, then any completely-mixed equilibrium is purifiable.     

Communication in repeated games with costly monitoring

We study repeated games with discounting where perfect monitoring is possible, but costly. It is shown that if players can make public announcements, then every payoff vector which is an interior point in the set of feasible and individually rational payoffs can be implemented in a sequential equilibrium of the repeated game when the discount factor is high enough. Thus, efficiency can be approximated even when the cost of monitoring is high, provided that the discount factor is high enough.     

Reputation with observed actions

Summary A single long-run player plays a fixed stage game (simultaneous orsequential move) against an infinite sequence of short-run opponents that play only once but can observe all past realized actions. Assuming that the probability distributions over types of long and short-run players have full support, we show that the long-run player can always establish a reputation for theStackelberg strategy and is therefore guaranteed almost his Stackelberg payoff in all Nash equilibria of the repeated game.The financial support of the National Science Foundation, Grant SES 90-7999, and of Consiglio Nazionale delle Ricerche is gratefully acknowledged. I wish to thank David Levine, Wolfgang Pesendorfer and Seminar Participants at UCLA, Universidad Carlos III de Madrid and University of Naples for useful discussions and suggestions.     

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.     

Perfect communication equilibria in repeated games with imperfect monitoring

This paper introduces an equilibrium concept called perfect communication equilibrium for repeated games with imperfect private monitoring. This concept is a refinement of Myerson's [Myerson, R.B., 1982. Optimal coordination mechanisms in generalized principal agent problems, J. Math. Econ. 10, 67–81] communication equilibrium. A communication equilibrium is perfect if it induces a communication equilibrium of the continuation game, after every history of messages of the mediator. We provide a characterization of the set of corresponding equilibrium payoffs and derive a Folk Theorem for discounted repeated games with imperfect private monitoring.     

Communication equilibrium payoffs in repeated games with imperfect monitoring

We characterize the set of communication equilibrium payoffs of any undiscounted repeated matrix-game with imperfect monitoring and complete information. For two-player games, a characterization is provided by Mertens, Sorin, and Zamir (Repeated games, Part A (1994) CORE DP 9420), mainly using Lehrer's (Math. Operations Res. (1992) 175) result for correlated equilibria. The main result of this paper is to extend this characterization to the n-player case. The proof of the characterization relies on an analogy with an auxiliary 2-player repeated game with incomplete information and imperfect monitoring. We use Kohlberg's (Int. J. Game Theory (1975) 7) result to construct explicitly a canonical communication device for each communication equilibrium payoff.     

A folk theorem for minority games

We study a particular case of repeated games with public signals. In the stage game an odd number of players have to choose simultaneously one of two rooms. The players who choose the less crowded room receive a reward of one euro (whence the name “minority game”). The players in the same room do not recognize each other, and between the stages only the current majority room is publicly announced. We show that in the infinitely repeated game any feasible payoff can be achieved as a uniform equilibrium payoff, and as an almost sure equilibrium payoff. In particular we construct an inefficient equilibrium where, with probability one, all players choose the same room at almost all stages. This equilibrium is sustained by punishment phases which use, in an unusual way, the pure actions that were played before the start of the punishment.     

Non-computable strategies and discounted repeated games

Summary A number of authors have used formal models of computation to capture the idea of bounded rationality in repeated games. Most of this literature has used computability by a finite automaton as the standard. A conceptual difficulty with this standard is that the decision problem is not closed. That is, for every strategy implementable by an automaton, there is some best response implementable by an automaton, but there may not exist any algorithm forfinding such a best response that can be implemented by an automaton. However, such algorithms can always be implemented by a Turing machine, the most powerful formal model of computation. In this paper, we investigate whether the decision problem can be closed by adopting Turing machines as the standard of computability. The answer we offer is negative. Indeed, for a large class of discounted repeated games (including the repeated Prisoner's Dilemma) there exist strategies implementable by a Turing machine for whichno best response is implementable by a Turing machine.The work was begun while Nachbar was a visitor at The Center for Mathematical studies in Economics and Management Science at Northwestern University; he is grateful for their hospitality. We are also grateful to Robert Anderson and Neil Gretsky and to seminar audiences at UCLA for useful comments, and to the National Science Foundation and the UCLA Academic Senate Committee on Research for financial support. This paper is an outgrowth of work reported in Learning and Computability in Discounted Supergames.     

Stated beliefs versus inferred beliefs: A methodological inquiry and experimental test

Belief elicitation in game experiments may be problematic if it changes game play. We experimentally verify that belief elicitation can alter paths of play in a two-player repeated asymmetric matching pennies game. Importantly, this effect occurs only during early periods and only for players with strongly asymmetric payoffs, consistent with a cognitive/affective effect on priors that may serve as a substitute for experience. These effects occur with a common scoring rule elicitation procedure, but not with simpler (unmotivated) statements of expected choices of opponents. Scoring rule belief elicitation improves the goodness of fit of structural models of belief learning, and prior beliefs implied by such models are both stronger and more realistic when beliefs are elicited than when they are not. We also find that “inferred beliefs” (beliefs estimated from past observed actions of opponents) can predict observed actions better than the “stated beliefs” from scoring rule belief elicitation.     

Plausible cooperation

There is a large repeated games literature illustrating how future interactions provide incentives for cooperation. Much of the earlier literature assumes public monitoring. Departures from public monitoring to private monitoring that incorporate differences in players' observations may dramatically complicate coordination and the provision of incentives, with the consequence that equilibria with private monitoring often seem unrealistically complex or fragile. We set out a model in which players accomplish cooperation in an intuitively plausible fashion. Players process information via a mental system – a set of psychological states and a transition function between states depending on observations. Players restrict attention to a relatively small set of simple strategies, and consequently, might learn which perform well.     

How complex are networks playing repeated games?

Summary. This paper examines implications of complexity cost in implementing repeated game strategies through networks with finitely many classifiers. A network consists of individual classifiers that summarize the history of repeated play according to a weighted sum of the empirical frequency of the outcomes of the stage game, and a decision unit that chooses an action in each period based on the summaries of the classifiers. Each player maximizes his long run average payoff, while minimizing the complexity cost of implementing his strategy through a network, measured by its number of classifiers. We examine locally stable equilibria where the selected networks are robust against small perturbations. In any locally stable equilibrium, no player uses a network with more than a single classifier. Moreover, the set of locally stable equilibrium payoff vectors lies on two line segments in the payoff space of the stage game. Received: May 9, 1997; revised version: November 18, 1997