Large deviations and equilibrium selection in large populations

This paper uses the theory of large deviations to analyse equilibrium selection in one-dimensional games with large populations where the system evolves according to a jump Markov process. The equilibria selected maximise a quasi-potential function which can be determined by solving a polynomial equation. Estimates of waiting times are also given. It shows that the equilibria about which there is more noise are less likely to be selected and clarifies the role of the limiting deterministic dynamic in selection.     

Basins of Attraction, Long-Run Stochastic Stability, and the Speed of Step-by-Step Evolution

The paper examines the behaviour of "evolutionary" models with ɛ-noise like those which have been used recently to discuss the evolution of social conventions. The paper is built around two main observations: that the"long run stochastic stability" of a convention is related tothe speed with which evolution toward and away from the convention occurs,and that evolution is more rapid (and hence more powerful) when it mayproceed via a series of small steps between intermediate steady states. Theformal analysis uses two new measures, the radius and modified coradius, tocharacterize the long run stochastically stable set of an evolutionary modeland to bound the speed with which evolutionary change occurs. Though notuniversally powerful, the result can be used to make many previous analysesmore transparent and extends them by providing results on waiting times. Anumber of applications are also discussed. The selection of the riskdominant equilibrium in 2×2 games is generalized to the selection of½-dominant equilibria in arbitrary games. Other applications involvetwo-dimensional local interaction and cycles as long run stochasticallystable sets.     

Cooperation in an Overlapping Generations Experiment

Recent theoretical work shows that folk theorems can be developed for infinite overlapping generations games. Cooperation in such games can be sustained as a Nash equilibrium. But, of course, there are other equilibria. This paper investigates experimentally whether cooperation actually occurs in a simple overlapping generations game. Subjects both play the game and formulate strategies. Our main finding is that subjects fail to exploit the intertemporal structure of the game. Even when we provided subjects with a recommendation to play the grim trigger strategy, most of the subjects still employed safe history-independent strategies. Journal of Economic Literature Classification Numbers: C72, C92, D90.     

Subgame Monotonicity in Extensive Form Evolutionary Games

A theory of subgame monotonicity is developed for finite extensive form games to model evolutionary processes that respect the subgame structure of the game. It is shown how these evolutionary processes can be decomposed into their evolution on smaller games and also recombined to simplify the analysis of the original game. When applied to the replicator dynamic, a generalization of the Wright manifold from population genetics is a natural consequence of monotonicity. Subgame monotonicity and the Wright manifold are also shown to arise naturally in imitation models based on the extensive form. Journal of Economic Literature Classification Numbers: C70, C72.     

Timing and Virtual Observability in Ultimatum Bargaining and “Weak Link” Coordination Games

Previous studies have shown that simply knowing one player moves first can affect behavior in games, even when the first-mover's moves are known to be unobservable. This observation violates the game-theoretic principle that timing of unobserved moves is irrelevant, but is consistent with virtual observability, a theory of how timing can matter without the ability to observe actions. However, this previous research only shows that timing matters in games where knowledge that one player moved first can help select that player's preferred equilibrium, presenting an alternative explanation to virtual observability. We extend this work by varying timing of unobservable moves in ultimatum bargaining games and “weak link” coordination games. In the latter, the equilibrium selection explanation does not predict any change in behavior due to timing differences. We find that timing without observability affects behavior in both games, but not substantially.     

Long persuasion games

This paper characterizes geometrically the sets of all Nash and perfect Bayesian equilibrium payoffs achievable with unmediated communication in persuasion games, i.e., games with an informed expert and an uninformed decisionmaker in which the expert's information is certifiable. The first equilibrium characterization is provided for unilateral persuasion games, and the second for multistage, bilateral persuasion games. As in Aumann and Hart [R.J. Aumann, S. Hart, Long cheap talk, Econometrica 71 (6) (2003) 1619-1660], we use the concepts of diconvexification and dimartingale. A leading example illustrates both geometric characterizations and shows how the expert, whatever his type, can increase his equilibrium payoff compared to all equilibria of the unilateral persuasion game by delaying information certification.     

Cooperation without Reputation: Experimental Evidence from Prisoner's Dilemma Games

This paper investigates cooperative play in prisoner's dilemma games by designing an experiment to evaluate the ability of two leading theories of observed cooperation: reputation building and altruism. We analyze both one-shot and finitely repeated games to gauge the importance of these theories. We conclude that neither altruism nor reputation building alone can explain our observations. The reputation model is inconsistent with play in both one-shots and finitely repeated games while the model with altruism is unable to explain observed play in the finitely repeated games.Journal of Economic LiteratureClassification Numbers: C72, C92.     

A Stackelberg strategy for routing flow over time

Routing games are studied to understand the impact of individual users' decisions on network efficiency. Most prior work on efficiency in routing games uses a simplified model where all flows exist simultaneously, and users care about either their maximum delay or their total delay. Both these measures are surrogates for measuring how long it takes to get all of a user's traffic through the network. We attempt a more direct study of network efficiency by examining routing games in a flow over time model. Flows over time are commonly used in transportation research. We show that in this model, by reducing network capacity judiciously, the network owner can ensure that the equilibrium is no worse than a small constant times the optimal in the original network, for two natural measures of optimality. These are the first upper bounds on the price of anarchy in this model for general networks.     

Repeated Games with Almost-Public Monitoring

In repeated games with imperfect public monitoring, players can use public signals to coordinate their behavior, and thus support cooperative outcomes, but with private monitoring, such coordination may no longer be possible. Even though grim trigger is a perfect public equilibrium (PPE) in games with public monitoring, it often fails to be an equilibrium in arbitrarily close games with private monitoring. If a PPE has players' behavior conditioned only on finite histories, then it induces an equilibrium in all close-by games with private monitoring. This implies a folk theorem for repeated games with almost-public almost-perfect monitoring. Journal of Economic Literature Classification Numbers: C72, C73.     

Equilibrium selection in coordination games with simultaneous play

Summary. We apply the dynamic stochastic framework proposed in recent evolutionary literature to a class of coordination games played simultaneously by the entire population. In these games payoffs, and hence best replies, are determined by a summary statistic of the population strategy profile. We demonstrate that with simultaneous play, the equilibrium selection depends crucially on how best responses to the summary statistic remain piece-wise constant. In fact, all the strict Nash equilibria in the underlying stage game can be made stochastically stable depending on how the best response mapping generates piece-wise constant best responses. Received: February 12, 2001; revised version: October 29, 2001     

Competition and waiting times in hospital markets

This paper studies the impact of hospital competition on waiting times. We use a Salop-type model, with hospitals that differ in (geographical) location and, potentially, waiting time, and two types of patients: high-benefit patients who choose between neighbouring hospitals (competitive segment), and low-benefit patients who decide whether or not to demand treatment from the closest hospital (monopoly segment). Compared with a benchmark case of monopoly, we find that hospital competition leads to longer waiting times in equilibrium if the competitive segment is sufficiently large. Given a policy regime of hospital competition, the effect of increased competition depends on the parameter of measurement: Lower travelling costs increase waiting times, higher hospital density reduces waiting times, while the effect of a larger competitive segment is ambiguous. We also show that, if the competitive segment is large, hospital competition is socially preferable to monopoly only if the (regulated) treatment price is sufficiently high.     

Stochastic Cooperative Games: Superadditivity, Convexity, and Certainty Equivalents

This paper extends the notions of superadditivity and convexity to stochastic cooperative games. It is shown that convex games are superadditive and have nonempty cores, and that these results also hold in the context of NTU games. Furthermore, a subclass of stochastic cooperative games to which one can associate a deterministic cooperative game is considered. It is shown that such a stochastic cooperative game satisfies properties like nonemptiness of the core, superadditivity, and convexity if and only if the corresponding deterministic game satisfies these properties.Journal of Economic LiteratureClassification Number: C71.     

The One-Shot-Deviation Principle for Sequential Rationality

This article analyzes the fictitious play process originally proposed for strategic form games by Brown (1951) and Robinson (1951). We interpret the process as a model of preplay thinking performed by players before acting in a one-shot game. This model is one of bounded rationality. We discuss how fictitious play should then be defined for extensive form games and conclude that this is somewhat problematic. We therefore study two alternative definitions. For either of these, under a weak condition of initial uncertainty, a convergence point of a fictitious play sequence is a sequential equilibrium. For generic games of perfect information initial uncertainty also implies convergence of fictitious play.Journal of Economic LiteratureClassification Number: C72.     

Fictitious Play in Extensive Form Games

This article analyzes the fictitious play process originally proposed for strategic form games by Brown (1951) and Robinson (1951). We interpret the process as a model of preplay thinking performed by players before acting in a one-shot game. This model is one of bounded rationality. We discuss how fictitious play should then be defined for extensive form games and conclude that this is somewhat problematic. We therefore study two alternative definitions. For either of these, under a weak condition of initial uncertainty, a convergence point of a fictitious play sequence is a sequential equilibrium. For generic games of perfect information initial uncertainty also implies convergence of fictitious play.Journal of Economic LiteratureClassification Number: C72.     

Learning from Personal Experience: One Rational Guy and the Justification of Myopia

The paper examines a large population analog of fictitious play in which players learn from personal experience, focusing on what happens when a single rational player is added to the population. Because the learning process naturally generates contagion dynamics, the rational player at times has an incentive to act nonmyopically. In 2 × 2 games the dynamics are asymmetric and favor risk dominant equilibria. A variety of other examples are presented.Journal of Economic LiteratureClassification Number: C7.     

Bounded Rationality in Economics: A Game Theorist's View

In this paper, we argue that it is essential to incorporate bounded rationality into game theory. Game theory has been applied to aspects of economics such as industrial organizati on on the basis of the naive interpret ation of game theory, which requires players to be ideally rational in an extremely unrealistic way. We stress the importance of establishing the perceptive interpretation of game theory by taking boundedly rational players' inductive reasoning processes into account. We explain my recent work, Matsushima (1997), which shows that the subjective games perceived by players in the long run are entirely different from the true objective game, and are trivial games in the sense that there exists a strictly dominant and subjectively Pareto-efficient strategy profile among the set of pure strategy profiles.
JEL Classification Numbers: C70, C90, D43, D80     

Action-Graph Games

Representing and reasoning with games becomes difficult once they involve large numbers of actions and players, because the space requirement for utility functions can grow unmanageably. Action-Graph Games (AGGs) are a fully-expressive game representation that can compactly express utility functions with structure such as context-specific independence, anonymity, and additivity. We show that AGGs can be used to compactly represent all games that are compact when represented as graphical games, symmetric games, anonymous games, congestion games, and polymatrix games, as well as games that require exponential space under all of these existing representations. We give a polynomial-time algorithm for computing a player's expected utility under an arbitrary mixed-strategy profile, and show how to use this algorithm to achieve exponential speedups of existing methods for computing sample Nash equilibria. We present results of experiments showing that using AGGs leads to a dramatic increase in the size of games accessible to computational analysis.²     

Equilibrium Selection inn-Person Coordination Games

This paper investigates several approaches to equilibrium selection and the relationships between them. The class of games we study aren-person generalized coordination games with multiple Pareto rankable strict Nash equilibria. The main result is that all selection criteria select the same outcome (namely the risk dominant equilibrium) in two-person games, and that most equivalences break for games with more than two players. All criteria select the Pareto efficient equilibrium in voting games, of which pure coordination games are special cases.Journal of Economic LiteratureClassification Numbers: C70, C72, D82.     

On Renegotiation-Proof Equilibria in Finitely Repeated Games

This paper studies renegotiation-proof equilibria of Beno?̂t and Krishna (1993) in finitely repeated games with more than two players. We provide a simple characterization of the set of average payoffs from renegotiation-proof equilibria: the limiting set of average equilibrium payoffs is either efficient or dimensionally small as the horizon of the repeated game goes to infinity. Two sufficient conditions for the former to occur are provided. An example shows that those conditions cannot be weakened.Journal of Economic LiteratureClassification Numbers: C72, C73.     

Perfect and Proper Equilibria of Large Games

This paper deals with the existence and other related issues of perfect and proper equilibria of games with a continuum of players. A sufficient condition for the existence of a perfect (proper) equilibrium as an almost everywhere limit of a sequence of ε-perfect (ε-proper) equilibria is given. An example shows that almost everywhere convergence need not obtain if the condition is violated. Extension to the case where the set of actions available to the players can differ is discussed.Journal of Economic LiteratureClassification Number: C79.