Strategic complexity in repeated extensive games

This paper studies a machine (finite automaton) playing a two-player repeated game of a simple extensive-form game with perfect information. We introduce a new complexity measure called multiple complexity which incorporates a strategyʼs responsiveness to information in the stage game as well as the number of states of the machine. We completely characterize the Nash equilibrium of the machine game. In the sequential-move prisonerʼs dilemma, cooperation can be sustained as an equilibrium.     

Does Neutral Stability Imply Lyapunov Stability?

A central concept in evolutionary game theory is that of an evolutionarily stable strategy. However, many games of interest for economics have only strategies which meet the weaker requirement of neutral stability. While neutral stability implies Lyapunov stability under the replicator dynamics in pairwise interactions, we give here an example in which an evolutionarily stable strategy is not Lyapunov stable in a more general context. We propose to use instead the notions of (strong) uninvadability and (strong) unbeatability, refinements of evolutionary and neutral stability, respectively. Strong uninvadability implies asymptotic stability, and strong unbeatability implies Lyapunov stability under the replicator dynamics. Journal of Economic Literature Classification Number: C72.     

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.     

Markov Perfect Equilibrium: I. Observable Actions

We define Markov strategy and Markov perfect equilibrium (MPE) for games with observable actions. Informally, a Markov strategy depends only on payoff-relevant past events. More precisely, it is measurable with respect to the coarsest partition of histories for which, if all other players use measurable strategies, each player's decision-problem is also measurable. For many games, this definition is equivalent to a simple affine invariance condition. We also show that an MPE is generically robust: if payoffs of a generic game are perturbed, there exists an almost Markovian equilibrium in the perturbed game near the initial MPE. Journal of Economic Literature Classification Numbers: C72, C73.     

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     

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.     

The power of ESS: An experimental study

Abstract. Our experimental design mimics a traditional evolutionary game framework where players are matched pairwise to play a symmetric 33 bimatrix game that has two Nash equilibria. One equilibrium is an evolutionary stable state, or ESS; the other is an equilibrium in dominated strategies. Our primary experimental result is the observation that the ESS becomes extremely attractive when subjects have minimal information about the payoff functions, although the dominated equilibrium assures the highest equilibrium payoff. The attractiveness of the ESS is only moderate when players are completely informed about the 33 payoff matrix. Correspondence to: S.K. Berninghaus     

Cooperative Outcomes through Noncooperative Games

This paper shows the equivalence between the stable solution set of any cooperative game in characteristic form (G1) and the subgame perfect Nash equilibria in pure strategies of a certain noncooperative game (G2). Players of G1 are named "agents." G2 is played by different players ("principals") who compete in wages to attract agents. The equivalence result holds when there are enough principals (if the game is superadditive, two principals suffice). Finally, another related cooperative game (G3) is constructed with both principals and agents as players. For G2 and G3 the same result is then proven, for any number of principals. Journal of Economic Literature Classification Numbers: C71 and C72.     

On the Relationship between Risk-Dominance and Stochastic Stability

In a 2 × 2 symmetric game with two symmetric equilibria, one risk-dominates another if and only if the equilibrium strategy is a unique best response to any mixture that gives itself at least a probability of one-half. In a two-person strategic form game, we call a Nash equilibriumglobally risk-dominantif it consists of strategies such that each one of them is a unique best response to any mixture that gives the other at least a probability of one-half. We show that if a weakly acyclic two-person game has a globally risk-dominant equilibrium, then this is the one that is selected by the stochastic equilibrium selection process of Young.Journal of Economic LiteratureClassification Numbers: C72, C73.     

Commitment Robust Equilibria and Endogenous Timing

This paper investigates which equilibria of a game are still viable when players have the opportunity to commit themselves. To that end we study a model of endogenous timing in which players face the trade-off between committing early and moving late. It is shown that mixed (resp. pure) equilibria of the original game are subgame perfect (resp. persistent) in the timing game only when no player has an incentive to move first. Consequently, mixed equilibria are viable only if no player has an incentive to move first. One needs strong evolutionary solution concepts to draw that conclusion for pure equilibria.Journal of Economic LiteratureClassification Number: C72.     

Convex Games and Stable Sets

It is well known that the core of a convex coalitional game with a finite set of players is the unique von Neumann–Morgenstern stable set of the game. We extend the definition of a stable set to coalitional games with an infinite set of players and give an example of a convex simple game with a countable set of players which does not have a stable set. But if a convex game with a countable set of players is continuous at the grand coalition, we prove that its core is the unique von Neumann–Morgenstern stable set. We also show that a game with a countable (possibly finite) set of players which is inner continuous is convex iff the core of each of its subgames is a stable set.Journal of Economic LiteratureClassification Numbers: C70, C71.     

How Proper Is Sequential Equilibrium?

A strategy profile of a normal form game is proper if and only if it is quasi-perfect in every extensive form (with that normal form). Thus, properness requires optimality along a sequence of supporting trembles, while sequentiality only requires optimality in the limit. A decision-theoretic implementation of sequential rationality, strategic independence respecting equilibrium (SIRE), is defined and compared to proper equilibrium, using lexicographic probability systems. Finally, we give tremble-based characterizations, which do not involve structural features of the game, of the rankings of strategies that underlie proper equilibrium and SIRE.Journal of Economic LiteratureClassification Numbers: C70, C72.     

Is limit pricing evolutionarily stable?

We have analyzed the question whether or not limit-pricing behavior can be viewed as a strategy, which survives the replicator dynamics in a game in which firms change strategies through imitation. Our results show that, regardless of the proportion of low cost incumbents in the population, potential entrants that play the strategy "enter" when they observe limit output are wiped out. The unique ESS consists of all low cost incumbents playing the "limit output" strategy, and all high cost incumbents playing the "monopoly output". This ESS includes potential entrants playing "stay out" after observing the limit output, and playing "enter" if monopoly output is observed in the first stage. Hence, limit pricing survives the replicator dynamics and appears in the stable state of the population.JEL Classification: B25, C73, L11We would like to thank an anonymous referee for valuable comments on an earlier version of this paper. Correspondence to: U. Soytas     

Existence and Uniqueness of Nash Equilibrium in Electoral Competition Games: The Hybrid Case

This paper analyzes the traditional unidimensional, two‐party electoral competition game when parties have mixed motivations, in the sense that they are interested in winning the election, but also in the policy implemented after the contest. In spite of having discontinuous payoffs, this game, referred to as the hybrid election game, is shown to be payoff secure and reciprocally upper semi‐continuous. Conditional payoffs, however, are not quasi‐concave. Hence, the existence of a pure strategy Nash equilibrium (psne ) is ensured only if parties have homogenous interests in power. In that case, an equilibrium not only exists, but it is also unique. Instead, if parties have heterogeneous motivations, depending upon the relationship between the electoral uncertainty, the aggregate opportunism, and its distribution across parties, a psne may or may not exist. The mixed extension, however, is always better reply secure. Therefore, a mixed strategy Nash equilibrium does indeed exist.     

Equivalence and Invariance of the Index and Degree of Nash Equilibria

Associated with each component of the Nash equilibria of a game are its index and degree. Its index is the local degree of the displacement map whose roots are the Nash equilibria of the game. Its degree is the local degree of the projection map from the Nash graph to the space of games. We show that the index and the degree of each component are the same. Further, they are invariant to adding or deleting redundant strategies, so they depend only on the reduced normal form of the game. Applications include Kohlberg and Mertens' existence theorems for stable sets and a simple procedure for calculating the degree of a component.Journal of Economic LiteratureClassification Number: C72.     

Does truth win when teams reason strategically?

We study behavior in the race game with the aim of assessing whether teams can create synergies. The race game has the advantage that the optimal strategy depends neither on beliefs about other players nor on distributional or efficiency concerns. Our results reveal that teams not only outperform individuals but that they can also beat the “truth-wins” benchmark. In particular, varying the length of the race game we find that the team advantage increases with the complexity of the game.     

Evolution and Mixed Strategies

Selten (1980, J. Theoret. Biol., 84, 93–101) showed that no mixed equilibria are evolutionarily stable when players can condition their strategies on their roles in a game. Alternatively, Harsanyi's (1973, Int. J. Game Theory, 2, 1–23) purification argument implies that all mixed equilibria are approximations of strict, and hence evolutionarily stable, equilibria of games with slightly perturbed payoffs. This paper reconciles these results: Approximations of mixed equilibria have high invasion barriers, and hence are likely to persist, when payoff perturbations are relatively important and role identification is relatively noisy. When payoff perturbations are unimportant and role identification is precise, approximations of mixed equilibria will have small invasion barriers and are unlikely to persist. Journal of Economic Literature Classification Numbers: C70, C78.     

Sowing Doubt Optimally in Two-Person Repeated Games

Consider a two-person repeated game, where one of the players, P1, can sow doubt, in the mind of his opponent, as to what P1's payoffs are. This results in a two-person repeated game with incomplete information. By sowing doubt, P1 can sometimes increase his minimal equilibrium payoff in the original game. We prove that this minimum is maximal when only one payoff matrix, the negative of the payoff matrix of the opponent, is added (the opponent thus believes that he might play a zero-sum game). We obtain two formulas for calculating this maximal minimum payoff. Journal of Economic Literature Classification Numbers: C7, D8.     

Perfect Information and Potential Games

Games with perfect information giving rise to potential normal forms are described. For agent normal forms, a potential is defined such that a strategy profile is a maximizer for the potential if and only if it is a subgame perfect equilibrium. In the normal form of any game with perfect information, every better reply path where the players do not change their choices at irrelevant nodes leads to an equilibrium. Journal of Economic Literature Classification Number: C72.