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.     

Disappearing private reputations in long-run relationships

For games of public reputation with uncertainty over types and imperfect public monitoring, Cripps et al. [Imperfect monitoring and impermanent reputations, Econometrica 72 (2004) 407-432] showed that an informed player facing short-lived uninformed opponents cannot maintain a permanent reputation for playing a strategy that is not part of an equilibrium of the game without uncertainty over types. This paper extends that result to games in which the uninformed player is long-lived and has private beliefs, so that the informed player's reputation is private. The rate at which reputations disappear is uniform across equilibria and reputations also disappear in sufficiently long discounted finitely repeated games.     

Uniform payoff security and Nash equilibrium in compact games

We introduce a condition, uniform payoff security, for games with compact Hausdorff strategy spaces and payoffs bounded and measurable in players’ strategies. We show that if any such compact game G is uniformly payoff secure, then its mixed extension is payoff secure. We also establish that if a uniformly payoff secure compact game G has a mixed extension with reciprocally upper semicontinuous payoffs, then G has a Nash equilibrium in mixed strategies. We provide several economic examples of compact games satisfying uniform payoff security.     

Repeated games with present-biased preferences

We study infinitely repeated games with perfect monitoring, where players have β-δ preferences. We compute the continuation payoff set using recursive techniques and then characterize equilibrium payoffs. We then explore the cost of the present-time bias, producing comparative statics. Unless the minimax outcome is a Nash equilibrium of the stage game, the equilibrium payoff set is not monotonic in β or δ. Finally, we show how the equilibrium payoff set is contained in that of a repeated game with smaller discount factor.     

On p-rationalizability and approximate common certainty of rationality

This paper shows that common p-belief of rationality implies p-rationalizability for games with compact strategy sets. We also establish the Bayesian foundation for the perfect p-rationalizability for finite games. The p-rationalizability is then used to analyze the robustness of rationalizable sets. For any game with compact strategy sets, we show that the rationalizable set is robust, i.e., the strategies characterized by common p-belief of rationality are close to the rationalizable set when p→1.     

Games of fixed rank: a hierarchy of bimatrix games

We propose and investigate a hierarchy of bimatrix games (A, B), whose (entry-wise) sum of the pay-off matrices of the two players is of rank k, where k is a constant. We will say the rank of such a game is k. For every fixed k, the class of rank k-games strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. We study both the expressive power and the algorithmic behavior of these games. Specifically, we show that even for k = 1 the set of Nash equilibria of these games can consist of an arbitrarily large number of connected components. While the question of exact polynomial time algorithms to find a Nash equilibrium remains open for games of fixed rank, we present polynomial time algorithms for finding an ε-approximation.     

Risk-dominance and perfect foresight dynamics in N-player games

In perfect foresight dynamics, an action is linearly stable if expectation that people will always choose the action is self-fulfilling. A symmetric game is a PIM game if an opponent's particular action maximizes the incentive of an action, independently of the rest of the players. This class includes supermodular games, games with linear incentives and so forth. We show that, in PIM games, linear stability is equivalent to u-dominance, a generalization of risk-dominance, and that there is no path escaping a u-dominant equilibrium. Existing results on N-player coordination games, games with linear incentives and two-player games are obtained as corollaries.     

Existence of perfect equilibria: a direct proof

We provide a direct proof of the existence of perfect equilibria in finite normal form games and extensive games with perfect recall. It is done by constructing a correspondence whose fixed points are precisely the perfect equilibria of a given finite game. Existence of a fixed point is secured by a generalization of Kakutani theorem, which is proved in this paper. This work offers a new approach to perfect equilibria, which would hopefully facilitate further study on this topic. We also hope our direct proof would be the first step toward building an algorithm to find the set of all perfect equilibria of a strategic game.     

Equilibrium selection in global games with strategic complementarities

We study games with strategic complementarities, arbitrary numbers of players and actions, and slightly noisy payoff signals. We prove limit uniqueness: as the signal noise vanishes, the game has a unique strategy profile that survives iterative dominance. This generalizes a result of Carlsson and van Damme (Econometrica 61 (1993) 989-1018) for two-player, two-action games. The surviving profile, however, may depend on fine details of the structure of the noise. We provide sufficient conditions on payoffs for there to be noise-independent selection.     

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.     

UNIQUENESS OF EQUILIBRIUM PAYOFFS IN FINITELY REPEATED GAMES WITH IMPERFECT MONITORING*

This paper examines when a finitely repeated game with imperfect monitoring has a unique equilibrium payoff vector. This problem is nontrivial under imperfect monitoring, because uniqueness of equilibrium (outcome) in the stage game does not extend to finitely repeated games. A (correlated) equilibrium is equilibrium minimaxing if any player's equilibrium payoff is her minimax value when the other players choose a correlated action profile from the actions played in the equilibrium. The uniqueness result holds if all stage game correlated equilibria are equilibrium minimaxing and have the same payoffs. The uniqueness result does not hold under weaker conditions.     

Generalized risk-dominance and asymmetric dynamics

This paper proposes two (ordinal and cardinal) generalizations of [J.C. Harsanyi, R. Selten, A General Theory of Equilibrium Selection in Games, MIT Press, Cambridge, MA and London, 1988] risk-dominance to multi-player, multi-action games. There are three reasons why generalized risk-dominance (GR-dominance) is interesting. Extending the logic of risk-dominance, GR-dominant actions can be interpreted as best responses to conjectures that satisfy a certain type of symmetry. Second, in a local interaction game of [G. Ellison, Learning, local interaction, and coordination, Econometrica 61 (5) (1993) 1047], if an action is risk-dominant in individual binary interactions with neighbors, it is also GR-dominant in the large game on a network. Finally, we show that GR-dominant actions are stochastically stable under a class of evolutionary dynamics. The last observation is a corollary to new abstract selection results that applies to a wide class of so-called asymmetric dynamics. In particular, I show that a (strictly) ordinal GR-dominant profile is (uniquely) stochastically stable under the approximate best-response dynamics of [M. Kandori, G.J. Mailath, R. Rob, Learning, mutation, and long run equilibria in games, Econometrica 61 (1) (1993) 29]. A (strictly) cardinal GR-dominant equilibrium is (uniquely) stochastically stable under a class of payoff-based dynamics that includes [L.E. Blume, The statistical-mechanics of strategic interaction, Games Econ. Behav. 5 (3) (1993) 387-424]. Among others, this leads to a generalization of a result from [G. Ellison, Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution, Rev. Econ. Stud. 67 (230) (2000) 17] on the -dominant evolutionary selection to all networks and the unique selection to all networks that satisfy a simple, sufficient condition.     

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.     

Self-enforcing collusion in large dynamic markets

The “folk theorem” in game theory implies that any outcome that is better for all players than some single period Nash outcome can be achieved through noncooperative equilibrium in repeated games with discounting. Whether the folk theorem holds for a repeated Cournot oligopoly as the number of firms, N, increases without bound, is investigated. It is shown that the folk theorem holds in the limit iff demand increases at the same rate as the number of firms and the Cournot price sequence is bounded strictly above by the supremum of marginal cost for large N.     

A limit characterization of belief-free equilibrium payoffs in repeated games

The present paper studies repeated games with private monitoring, and characterizes the set of belief-free equilibrium payoffs in the limit as the discount factor approaches one and the noise on private information vanishes. Contrary to the conjecture by Ely et al. [J.C. Ely, J. Hörner, W. Olszewski, Belief-free equilibria in repeated games, Econometrica 73 (2005) 377-415], the equilibrium payoff set is computed by the same formula, no matter how many players there are. As an application of this result, a version of the folk theorem is established for N-player prisoner's dilemma games.     

Extensive and strategic forms: Games and models for games

This paper aims to make precise, in the context of epistemic models for games, some relations between the normal or strategic form representation of a game and the extensive or dynamic form representation. It is argued, first, that epistemic models defined for strategic form representations provide all the materials necessary for defining models for corresponding extensive form representations of the game, models that provide information about the way the game is played that is sufficient to evaluate the rationality of the choices that the players make, and are disposed to make, in the course of playing the dynamic game. Second, two definitions of rationality are compared — one for strategy choices in the normal form representation, and one for the individual choices that the player is disposed to make in the course of playing the dynamic game. It is shown that they are essentially equivalent in games with perfect recall. The main focus is on the intuitive foundational assumptions about rationality and dynamic choice that are needed to motivate the definitions. It is argued that to evaluate the rationality of a player's choices in a dynamic context, it is essential to distinguish passive knowledge (knowledge about nature and about the prior beliefs and strategy choices of other players that is based on observation and inference) fromactive knowledge (knowledge about one's own choices and future choices that is grounded in one's decisions).     

The supercore for normal-form games

This paper analyzes the supercore of a system derived from a normal-form game. For the case of a finite game with pure strategies, we define a sequence of games and show that the supercore coincides with the set of Nash equilibria of the last game in that sequence. This result is illustrated with the characterization of the supercore for the n-person prisoner's dilemma. With regard to the mixed extension of a normal-form game, we show that the set of Nash equilibrium profiles coincides with the supercore for games with a finite number of Nash equilibria.     

Using or hiding private information? An experimental study of zero-sum repeated games with incomplete information

This paper studies the value of private information in strictly competitive interactions in which there is a trade-off between (i) the short-run gain of using information, and (ii) the long-run gain of concealing it. We implement simple examples from the class of zero-sum repeated games with incomplete information. While the empirical value of information does not always coincide with the theoretical prediction, the qualitative properties of the value of information are satisfied in the laboratory: (i) it is never negative, (ii) it decreases with the number of repetitions, (iii) it is bounded below by the value of the infinitely repeated game, and (iv) it is bounded above by the value of the one-shot game. In line with the theory, the empirical use of private information is almost complete when it should be, and decreases in longer interactions.     

Collusion as public monitoring becomes noisy: Experimental evidence

This paper uses laboratory experiments to test the implications of the theory of repeated games on equilibrium payoffs and estimate strategies in an infinitely repeated prisoners' dilemma game with imperfect public monitoring. We find that subjects' payoffs (i) decrease as noise increases, and (ii) are lower than the theoretical maximum for low noise, but exceed it for high noise. Under the assumption that the subjects' strategy uses thresholds on the public signal for transition between cooperation and punishment states, we find that the best fitting strategy simply compares the most recent public signal against a single threshold.     

Higher order game dynamics

Continuous-time game dynamics are typically first order systems where payoffs determine the growth rate of the players? strategy shares. In this paper, we investigate what happens beyond first order by viewing payoffs as higher order forces of change, specifying e.g. the acceleration of the players? evolution instead of its velocity (a viewpoint which emerges naturally when it comes to aggregating empirical data of past instances of play). To that end, we derive a wide class of higher order game dynamics, generalizing first order imitative dynamics, and, in particular, the replicator dynamics. We show that strictly dominated strategies become extinct in n-th order payoff-monotonic dynamics n   orders as fast as in the corresponding first order dynamics; furthermore, in stark contrast to first order, weakly dominated strategies also become extinct for n?2$n?2$. All in all, higher order payoff-monotonic dynamics lead to the elimination of weakly dominated strategies, followed by the iterated deletion of strictly dominated strategies, thus providing a dynamic justification of the well-known epistemic rationalizability process of Dekel and Fudenberg [7]. Finally, we also establish a higher order analogue of the folk theorem of evolutionary game theory, and we show that convergence to strict equilibria in n-th order dynamics is n orders as fast as in first order.