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.     

Bounded rationality: static versus dynamic approaches

Summary. Two kinds of theories of boundedly rational behavior are possible. Static theories focus on stationary behavior and do not include any explicit mechanism for temporal change. Dynamic theories, on the other hand, explicitly model the fine-grain adjustments made by the subjects in response to their recent experiences. The main contribution of this paper is to argue that the restrictions usually imposed on the distribution of choices in the static approach are generically not supported by a dynamic adjustment mechanism. The genericity here is understood both in the measure theoretic and in the topological sense.Received: 29 April 2002, Revised: 11 February 2004, JEL Classification Numbers: C0, D7.I thank Peter Bardsley and Rabee Tourky for useful suggestions. Special thanks are due to an anonymous referee.     

Non-computable strategies and discounted repeated games

Summary A number of authors have used formal models of computation to capture the idea of bounded rationality in repeated games. Most of this literature has used computability by a finite automaton as the standard. A conceptual difficulty with this standard is that the decision problem is not closed. That is, for every strategy implementable by an automaton, there is some best response implementable by an automaton, but there may not exist any algorithm forfinding such a best response that can be implemented by an automaton. However, such algorithms can always be implemented by a Turing machine, the most powerful formal model of computation. In this paper, we investigate whether the decision problem can be closed by adopting Turing machines as the standard of computability. The answer we offer is negative. Indeed, for a large class of discounted repeated games (including the repeated Prisoner's Dilemma) there exist strategies implementable by a Turing machine for whichno best response is implementable by a Turing machine.The work was begun while Nachbar was a visitor at The Center for Mathematical studies in Economics and Management Science at Northwestern University; he is grateful for their hospitality. We are also grateful to Robert Anderson and Neil Gretsky and to seminar audiences at UCLA for useful comments, and to the National Science Foundation and the UCLA Academic Senate Committee on Research for financial support. This paper is an outgrowth of work reported in Learning and Computability in Discounted Supergames.     

Noisy Directional Learning and the Logit Equilibrium

We specify a dynamic model in which agents adjust their decisions toward higher payoffs, subject to normal error. This process generates a probability distribution of players’ decisions that evolves over time according to the Fokker–Planck equation. The dynamic process is stable for all potential games, a class of payoff structures that includes several widely studied games. In equilibrium, the distributions that determine expected payoffs correspond to the distributions that arise from the logit function applied to those expected payoffs. This “logit equilibrium” forms a stochastic generalization of the Nash equilibrium and provides a possible explanation of anomalous laboratory data.     

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.     

Ricardian equivalence with uninformed consumers?

Empirical studies have shown that the majority of people are poorly informed about the size of government debts and deficits. This paper investigates whether it is nevertheless possible for households to mimic Ricardian behavior on the basis of those variables that they actually observe. In a simple two-period model, it is shown that imperfect information about government debt can lead to departures from Ricardian equivalence even if the households' estimates of debt are unbiased. The paper discusses why households face difficulties in obtaining relevant information about government debt.     

Sampling equilibrium, with an application to strategic voting

We suggest an equilibrium concept for a strategic model with a large number of players in which each player observes the actions of only a small number of the other players. The concept fits well situations in which each player treats his sample as a prediction of the distribution of actions in the entire population, and responds optimally to this prediction. We apply the concept to a strategic voting model and investigate the conditions under which a centrist candidate can win the popular vote although his strength in the population is smaller than the strengths of the right and left candidates.     

A spectrum of equilibration processes in game theory

In game theory, four dynamic processes converging towards an equilibrium are distinguished and ordered by way of agents' decreasing cognitive capacities. In the eductive process, each player has enough information to simulate perfectly the others' behavior and gets immediately to the equilibrium. In epistemic learning, each player updates his beliefs about others' future strategies, with regard to their sequentially observed actions. In behavioral learning, each player modifies his own strategies according to the observed payoffs obtained from his past actions. In the evolutionary process, each agent has a fixed strategy and reproduces in proportion to the utilities obtained through stochastic interactions. All along the spectrum, longer term dynamics makes up for weaker rationality, and physical relations substitute for mental interactions. Convergence, if any, is towards an always stronger equilibrium notion and selection of an equilibrium state becomes more sensitive to context and history. The processes can be mixed if associated to different periods, agents or mechanisms and deepened if obtained by formal reasoning principles.     

Consumer myopia, standardization and aftermarket monopolization

In this paper, I show that the standard Bertrand competition argument does not apply when firms compete for myopic consumers who optimize period-by-period. I develop the model in the context of aftermarket. With overlapping-generations of consumers, simultaneous product offerings in the primary market and aftermarket establishes a price floor for the primary good. This constraint prevents aftermarket rents from being dissipated by the primary market competition. Duopoly firms earn positive profits despite price competition with undifferentiated products. Nonetheless, government interventions to reinforce aftermarket competition such as a standardization requirement may lead to the partial collapse of the primary market.     

Improving the performance of an economic system: Controlling chaos

In this paper we use a simple model of evolutionary market dynamics to illustrate how chaotic behavior can be controlled by making small changes in a parameter that is accessible to the decision makers. This approach is commonly referred to as `targeting' – one can easily switch from a chaotic evolution of the market to any desired regular motion. We show that complex dynamics leads to inferior performance in our model and that an application of such a correction mechanism by the decision makers of the firms yields a considerable improvement in the system's economical properties in terms of profits and profitability. We present numerical simulations in order to illustrate the effectiveness of this method.     

The partially cursed and the analogy-based expectation equilibrium

Recent literature has established a link between the fully cursed equilibrium and the analogy-based expectation equilibrium. In this note, even the partially cursed equilibrium is shown to correspond to an analogy-based expectation equilibrium.     

Derived factor demand under monopoly

Summary. We generalize the formula provided by Maurice and Ferguson (1973) for derived factor demand in a monopoly by extending it to cross-price effects and taking into account other variables which may, within an general-equilibrium framework, affect demand, such as income. Hopefully, both features increase the applicability of this formula in general-equilibrium analyses. Received: April 5, 2000; revised version: June 7, 2001     

Learning by matching patterns

We analyze a model of repeated play between two boundedly rational agents. In each stage each player recalls the outcomes from the most recent few rounds, calculates the distribution of its opponent's past reactions to this outcome pattern, and then optimizes myopically against this distribution. If both players use the same pattern length then the limit points of pattern matching are in the convex hull of the limit points of fictitious play. Thus if fictitious play converges into the set of Nash equilibria then pattern matching converges into the convex hull of Nash equilibria. If the players use different pattern lengths, the more sophisticated player may, but does not generally, succeed in playing as if it could perfectly predict its opponent's play.     

Improved grade outcomes with an e-mailed “grade nudge”

Information provided at the moment a person makes a decision can influence behavior in predictable ways. The United Kingdom's Behavioural Insights Team have used this idea to help improve the insulation of lofts, collect taxes, and even reduce litter. The authors of this article developed software that appends a personalized message to each assignment in the class regarding the student's current grade. This “grade nudge” explains precisely how the assignment will impact the student's final grade given their current standing in the class. Through a randomized trial, the authors show that the nudge improves student homework performance by about four percentage points.