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.     

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.     

Strategic complementarity in multi-stage games

We provide sufficient conditions in finite-horizon multi-stage games for the value function of each player, associated to extremal Markov perfect equilibria, to display strategic complementarities and for the contemporaneous equilibrium to be increasing in the state variables. The author is grateful to Federico Echenique, Rabah Amir and one anonymous referee for useful comments, project SEJ2005-08263 at UPF and Project Consolider-Ingenio CSD2006-00016 of the Spanish Ministry of Education and Science, and the Barcelona Economics Program of CREA, for financial support.     

A note on the one-deviation property in extensive form games

In an extensive form game, an assessment is said to satisfy the one-deviation property if for all possible payoffs at the terminal nodes the following holds: if a player at each of his information sets cannot improve upon his expected payoff by deviating unilaterally at this information set only, he cannot do so by deviating at any arbitrary collection of information sets. Hendon et al. (1996. Games Econom. Behav. 12, 274–282) have shown that pre-consistency of assessments implies the one-deviation property. In this note, it is shown that an appropriate weakening of pre-consistency, termed updating consistency, is both a sufficient and necessary condition for the one-deviation property. The result is extended to the context of rationalizability.     

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.     

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.     

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.     

Imperfect recall and the relationships between solution concepts in extensive games

Summary. In a game of imperfect recall, a sequential equilibrium may not be a Nash equilibrium, and a perfect equilibrium may not be a sequential equilibrium. Sufficiency conditions weaker than perfect recall are given to ensure the standard relationships hold between perfect equilibrium, sequential equilibrium and Nash equilibrium.Received: 22 October 2003, Revised: 18 November 2003, JEL Classification Numbers: C72.     

Communication in repeated network games with imperfect monitoring

I consider repeated games with private monitoring played on a network. Each player has a set of neighbors with whom he interacts: a player's payoff depends on his own and his neighbors' actions only. Monitoring is private and imperfect: each player observes his stage payoff but not the actions of his neighbors. Players can communicate costlessly at each stage: communication can be public, private or a mixture of both. Payoffs are assumed to be sensitive to unilateral deviations. First, for any network, a folk theorem holds if some Joint Pairwise Identifiability condition regarding payoff functions is satisfied. Second, a necessary and sufficient condition on the network topology for a folk theorem to hold for all payoff functions is that no two players have the same set of neighbors not counting each other.     

Strategic knowledge sharing in Bayesian games

This paper provides a model for the study of direct, public and strategic knowledge sharing in Bayesian games. We propose an equilibrium concept which takes into account communication possibilities of exogenously certifiable statements and in which beliefs off the equilibrium path are explicitly deduced from consistent possibility correspondences, without making reference to perturbed games. Properties of such an equilibrium and of revised knowledge are examined. In particular, it is shown that our equilibrium is always a sequential equilibrium of the associated extensive form game with communication. Finally, sufficient conditions for the existence of perfectly revealing or non-revealing equilibria are characterized in some classes of games. Several examples and economic applications are investigated.     

Approximate efficiency in repeated games with correlated private signals

This paper presents repeated games with hidden moves, in which players receive imperfect private signals and are able to communicate. We propose a conditional probability approach to solve the learning problem in repeated games with correlated private signals and delayed communication. We then apply this approach to symmetric n-player games to obtain an approximate efficiency result.     

When is the risk of cooperation worth taking? The prisoner’s dilemma as a game of multiple motives

This experimental article helps to understand the motives behind cooperation in the prisoner’s dilemma. It manipulates the pay-off in case both players defect in a two-player, one-shot prisoner’s dilemma and explains the degree of cooperation by a combination of four motives: efficiency, conditional cooperation, fear and greed. All motives are significant but some become only significant if one controls for all remaining ones. This seems to be the reason why earlier attempts at explaining choices in the prisoner’s dilemma with personality have not been successful.     

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.     

Non-monotonic group-size effect in repeated provision of public goods

This paper analyzes the effect of a change in group size on incentives to contribute in repeated provision of pure public goods. We develop a model in which group members interact repeatedly, and might be temporarily unable to contribute to public goods production during some periods. We show that an increase in the group size generates two opposite effects – the standard free-riding effect that suppresses cooperation, and the novel large-scale effect that enhances cooperation. Our results indicate that the former effect dominates in relatively large groups while the latter dominates in relatively small groups. We, therefore, provide a rationale for a non-monotonic group-size effect that may explain previous empirical and experimental findings.     

Collusion through mediated communication in repeated games with imperfect private monitoring

Summary. This paper studies repeated games with imperfect private monitoring when there exists a third-party mediator who coordinates play by giving non-binding instructions to players on which action to take and by collecting their private information. The paper presents a Nash-threat folk theorem for a communication equilibrium based on such mediation when monitoring is jointly -perfect in the sense that every player is almost perfectly monitored collectively by other players.JEL Classification Numbers: C72, D82.I am very grateful to Mark Armstrong, V. Bhaskar, and Michihiro Kandori for helpful comments. Part of this research was conducted while I was visiting the University College London. Their hospitality is gratefully acknowledged.     

Regret minimization in repeated matrix games with variable stage duration

Regret minimization in repeated matrix games has been extensively studied ever since Hannan's seminal paper [Hannan, J., 1957. Approximation to Bayes risk in repeated play. In: Dresher, M., Tucker, A.W., Wolfe, P. (Eds.), Contributions to the Theory of Games, vol. III. Ann. of Math. Stud., vol. 39, Princeton Univ. Press, Princeton, NJ, pp. 97–193]. Several classes of no-regret strategies now exist; such strategies secure a long-term average payoff as high as could be obtained by the fixed action that is best, in hindsight, against the observed action sequence of the opponent. We consider an extension of this framework to repeated games with variable stage duration, where the duration of each stage may depend on actions of both players, and the performance measure of interest is the average payoff per unit time. We start by showing that no-regret strategies, in the above sense, do not exist in general. Consequently, we consider two classes of adaptive strategies, one based on Blackwell's approachability theorem and the other on calibrated play, and examine their performance guarantees. We further provide sufficient conditions for existence of no-regret strategies in this model.     

Patents,imitation and welfare

We consider the effects of product and process patents on profits and welfare. In a duopoly model, we show that if the cost of imitation is not very large, prisoner's dilemma occurs under process patent, thus creating lower profit of each firm under process patent than under product patent. Welfare is higher under process (product) patent for very small (not very small) cost of imitation. Although the possibility of cross-licensing never makes lower welfare under process patent for all costs of imitation, welfare is never lower under product patent under infinitely repeated game.     

Bounded rationality,neural network and folk theorem in repeated games with discounting

Summary The perfect folk theorem (Fudenberg and Maskin [1986]) need not rely on excessively complex strategies. We recover the perfect folk theorem for two person repeated games with discounting through neural networks (Hopfield [1982]) that have finitely many associative units. For any individually rational payoff vector, we need neural networks with at most 7 associative units, each of which can handle only elementary calculations such as maximum, minimum or threshold operation. The uniform upper bound of the complexity of equilibrium strategies differentiates this paer from Ben-Porath and Peleg [1987] in which we need to admit ever more complex strategies in order to expand the set of equilibrium outcomes.I would like to thank Hao Li and John Curran for excellent research assistance. Financial support from National Science Foundation (SES-9223483), Sloan Foundation and the Division of Social Sciences at the University of Chicago is gratefully acknowledged.