On the impossibility of achieving no regrets in repeated games

Regret-minimizing strategies for repeated games have been receiving increasing attention in the literature. These are simple adaptive behavior rules that lead to no regrets and, if followed by all players, exhibit nice convergence properties: the average play converges to correlated equilibrium, or even to Nash equilibrium in certain classes of games. However, the no-regret property relies on a strong assumption that each player treats her opponents as unresponsive and fully ignores the opponents’ possible reactions to her actions. We show that if at least one player is slightly responsive, it is impossible to achieve no regrets, and convergence results for regret minimization with responsive opponents are unknown.     

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     

Learning to play games in extensive form by valuation

Game theoretic models of learning which are based on the strategic form of the game cannot explain learning in games with large extensive form. We study learning in such games by using valuation of moves. A valuation for a player is a numeric assessment of her moves that purports to reflect their desirability. We consider a myopic player, who chooses moves with the highest valuation. Each time the game is played, the player revises her valuation by assigning the payoff obtained in the play to each of the moves she has made. We show for a repeated win-lose game that if the player has a winning strategy in the stage game, there is almost surely a time after which she always wins. When a player has more than two payoffs, a more elaborate learning procedure is required. We consider one that associates with each move the average payoff in the rounds in which this move was made. When all players adopt this learning procedure, with some perturbations, then, with probability 1 there is a time after which strategies that are close to subgame perfect equilibrium are played. A single player who adopts this procedure can guarantee only her individually rational payoff.     

Aggregate comparative statics

In aggregative games, each playerʼs payoff depends on her own actions and an aggregate of the actions of all the players. Many common games in industrial organization, political economy, public economics, and macroeconomics can be cast as aggregative games. This paper provides a general and tractable framework for comparative static results in aggregative games. We focus on two classes of games: (1) aggregative games with strategic substitutes and (2) nice aggregative games, where payoff functions are continuous and concave in own strategies. We provide simple sufficient conditions under which positive shocks to individual players increase their own actions and have monotone effects on the aggregate. The results are illustrated with applications to public good provision, contests, Cournot competition and technology choices in oligopoly.     

Moral Hazard and Private Monitoring

We clarify the role of mixed strategies and public randomization (sunspots) in sustaining near-efficient outcomes in repeated games with private monitoring. We study a finitely repeated game, where the stage game has multiple equilibria and show that mixed strategies can support partial cooperation, but cannot approximate full cooperation even if monitoring is “almost perfect.” Efficiency requires extensive form correlation, where strategies can condition upon a sunspot at the end of each period. For any finite number of repetitions, we approximate the best equilibrium payoff under perfect monitoring, assuming that monitoring is sufficiently accurate and sunspots are available. Journal of Economic Literature Classification Numbers: C73, D82.     

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.     

Monotone Games with Positive Spillovers

A monotone game comprises the infinitely repeated play of an n-person stage game, subject to the constraint that players' actions be monotonically nondecreasing over time. These games represent a variety of strategic situations in which players are able to make (partial) commitments. If the stage games have positive spillovers and satisfy certain other conditions, then the limit points of the subgame perfect equilibria are precisely the approachable action profiles. This characterization is applied to voluntary contribution games, market games, and coordination games. Journal of Economic Literature Classification Number: C7.     

Cooperation through imitation

This paper characterizes long-run outcomes for broad classes of symmetric games, when players select actions on the basis of average historical performance. Received wisdom suggests that when agent's interests are partially opposed, behavior is excessively competitive: “keeping up with the Jones' ” lowers everyones' welfare. Here, we study the long-run consequences of imitative behavior when agents have sufficiently long memories and evaluate past actions in terms of (weighted) average payoff. Imitation robustly leads to cooperative outcomes (with highest symmetric payoffs) in the long run. Furthermore, lengthening memory reinforces this effect. This provides a rationale, for example, for collusive cartel-like behavior without collusive intent.     

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.     

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.     

Learning aspiration in repeated games

We study infinitely repeated symmetric 2×2 games played by bounded rational agents who follow a simple rule of thumb: each agent continues to play the same action if the current payoff exceeds the average of the past payoffs, and switches to the other action with a positive probability otherwise. By applying the stochastic approximation technique, we characterize the asymptotic outcomes for all 2×2 games. In the prisoners’ dilemma game, for example, the players cooperate in the limit if and only if the gain from defecting against cooperation is “modest.”     

A folk theorem for repeated games played on a network

I consider repeated games on a network where players interact and communicate with their neighbors. At each stage, players choose actions and exchange private messages with their neighbors. The payoff of a player depends only on his own action and on the actions of his neighbors. At the end of each stage, a player is only informed of his payoff and of the messages he received from his neighbors. Payoffs are assumed to be sensitive to unilateral deviations. The main result is to establish a necessary and sufficient condition on the network for a Nash folk theorem to hold, for any such payoff function.     

Minimizing Regret: The General Case

In repeated games with differential information on one side, the labelling “general case” refers to games in which the action of the informed player is not known to the uninformed, who can only observe a signal which is the random outcome of his and his opponent's action. Here we consider the problem of minimizing regret (in the sense first formulated by J. Hannan (1956, in Contributions to the Theory of Games, Vol. III, Annals of Mathematics Studies, Vol. 39, Princeton, NJ: Princeton Univ. Press.) when the information available is of this type. We give a simple condition describing the approachable set. Journal of Economic Literature Classification Number: D81, D82, D83.     

A “Super” Folk Theorem for dynastic repeated games

We analyze dynastic repeated games. These are repeated games in which the stage game is played by successive generations of finitely-lived players with dynastic preferences. Each individual has preferences that replicate those of the infinitely-lived players of a standard discounted infinitely-repeated game. Individuals live one period and do not observe the history of play that takes place before their birth, but instead create social memory through private messages received from their immediate predecessors. Under mild conditions, when players are sufficiently patient, all feasible payoff vectors (including those below the minmax of the stage game) can be sustained by sequential equilibria of the dynastic repeated game with private communication. In particular, the result applies to any stage game with n  ≥  4 players for which the standard Folk Theorem yields a payoff set with a non-empty interior. We are also able to characterize fully the conditions under which a sequential equilibrium of the dynastic repeated game can yield a payoff vector not sustainable as a subgame perfect equilibrium of the standard repeated game. For this to be the case it must be that the players’ equilibrium beliefs violate a condition that we term “inter-generational agreement.” A previous version of this paper was circulated as Anderlini et al. (2005). We are grateful to Jeff Ely, Leonardo Felli, Navin Kartik, David Levine, Stephen Morris, Michele Piccione, Andrew Postlewaite, Lones Smith and to seminar audiences at Bocconi, Cambridge, CEPR-Guerzensee, Chicago, Columbia, Edinburgh, Essex, Georgetown, Leicester, LSE, Northwestern, Oxford, Rome (La Sapienza), Rutgers, SAET-Vigo, Stanford, SUNY-Albany, UCL, UC-San Diego, Venice and Yale for helpful feedback.     

Revisiting games of incomplete information with analogy-based expectations

This paper studies the effects of analogy-based expectations in static two-player games of incomplete information. Players are assumed to be boundedly rational in the way they forecast their opponent's state-contingent strategy: they bundle states into analogy classes and play best-responses to their opponent's average strategy in those analogy classes. We provide general properties of analogy-based expectation equilibria and apply the model to a variety of well known games. We characterize conditions on the analogy partitions for successful coordination in coordination games under incomplete information [Rubinstein, A., 1989. The electronic mail game: Strategic behavior under ‘almost common knowledge’. Amer. Econ. Rev. 79, 385–391], we show how analogy grouping of the receiver may facilitate information transmission in Crawford and Sobel's cheap talk games [Crawford, V.P., Sobel, J., 1982. Strategic information transmission. Econometrica 50, 1431–1451], and we show how analogy grouping may give rise to betting in zero-sum betting games such as those studied to illustrate the no trade theorem.     

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.     

Correlated Equilibrium in Stochastic Games

We study the existence of uniform correlated equilibrium payoffs in stochastic games. The correlation devices that we use are either autonomous (they base their choice of signal on previous signals, but not on previous states or actions) or stationary (their choice is independent of any data and is drawn according to the same probability distribution at every stage). We prove that any n-player stochastic game admits an autonomous correlated equilibrium payoff. When the game is positive and recursive, a stationary correlated equilibrium payoff exists. Journal of Economic Literature Classification Numbers: C72, C73.     

Learning with perfect information

For extensive form games with perfect information, consider a learning process in which, at any iteration, each player unilaterally deviates to a best response to his current conjectures of others' strategies; and then updates his conjectures in accordance with the induced play of the game. We show that, for generic payoffs, the outcome of the game becomes stationary, and is consistent with Nash equilibrium. In general, if payoffs have ties or if players observe more of each others' strategies than is revealed by plays of the game, the same result holds provided a rationality constraint is imposed on unilateral deviations: no player changes his moves in subgames that he deems unreachable, unless he stands to improve his payoff there. Moreover, with this constraint, the sequence of strategies and conjectures also becomes stationary, and yields a self-confirming equilibrium.     

Fault tolerance in large games

A Nash equilibrium is an optimal strategy for each player under the assumption that others play according to their respective Nash strategies, but it provides no guarantees in the presence of irrational players or coalitions of colluding players. In fact, no such guarantees exist in general. However, in this paper we show that large games are innately fault tolerant. We quantify the ways in which two subclasses of large games – λ-continuous games and anonymous games – are resilient against Byzantine faults (i.e. irrational behavior), coalitions, and asynchronous play. We also show that general large games have some non-trivial resilience against faults.     

Robust rational turnout

We show that equilibria of a class of participation games (Palfrey and Rosenthal in Public Choice 41(1):7–53, 1983; Journal of Public Economics 24(2):171–193, 1984) exhibit minimal heterogeneity of behavior so that players’ mixed strategies are summarized by at most two probabilities. We then establish that, except for a finite set of common costs of participation, these games are regular. Thus, equilibria of these voting games are robust to general payoff perturbations and survive in nearby games of incomplete information. Thanks to participants of the 2006 MPSA conference for comments on an early version.