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.     

On designing economic agents that behave like human agents

This paper explores the idea of constructing theoretical economic agents that behave like actual human agents and using them in neoclassical economic models. It does this in a repeated-choice setting by postulating artificial agents who use a learning algorithm calibrated against human learning data from psychological experiments. The resulting calibrated algorithm appears to replicate human learning behavior to a high degree and reproduces several stylized facts of learning. It can therefore be used to replace the idealized, perfectly rational agents in appropriate neoclassical models with calibrated agents that represent actual human behavior. The paper discusses the possibilities of using the algorithm to represent human learning in normal-form stage games and in more general neoclassical models in economics. It explores the likelihood of convergence to long-run optimality and to Nash behavior, and the characteristic learning time implicit in human adaptation in the economy.     

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.     

Can evolutionary algorithms describe learning processes?

Evolutionary algorithms have attracted more and more the attention of economists in recent years. Repeatedly it is claimed that they are an adequate tool to describe learning processes within a population of individuals. The present paper examines this claim. To this end, a learning model is set up that contains the three elements of variation, elimination, and imitation that are claimed to correspond with the processes of mutation, selection, and replication of biological evolution. Subsequently, this model is compared with a formulation of evolutionary algorithms. The comparison reveals that although both processes have a similar structure there are crucial differences between the two dynamics.     

Global convergence of adaptive learning in models of pure exchange

Summary. This paper develops an adaptive learning scheme for a standard version of the OLG model with pure exchange. Perfect forecasting rules which generate perfect foresight orbits are approximated by cubic spline functions. These approximations are successively constructed using historical data only. Trajectories generated by this scheme converge to perfect foresight orbits globally for all initial conditions. This result holds for all parameterizations guaranteeing the existence of a monetary steady state and hence is independent of consumers' savings behavior. It generalizes to all one-dimensional models of the Cobweb type. Received: October 5, 2000; revised version: February 15, 2001     

The market for preferences

Learning processes are widely held to be the mechanism by whichboundedly rational agents adapt to environmental changes. Weargue that this same outcome might also be achieved by a differentmechanism, namely specialisation and the division of knowledge,which we here extend to the consumer side of the economy. Wedistinguish between high-level preferences and low-level preferencesas nested systems of rules used to solve particular choice problems.We argue that agents, while sovereign in high-level preferences,may often find it expedient to acquire, in a pseudo-market,the low-level preferences in order to make good choices whenpurchasing complex commodities about which they have littleor no experience. A market for preferences arises when environmentalcomplexity overwhelms learning possibilities and leads agentsto make use of other people's specialised knowledge and decisionrules.     

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.     

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.     

Brown–von Neumann–Nash dynamics: The continuous strategy case

Brown and von Neumann introduced a dynamical system that converges to saddle points of zero sum games with finitely many strategies. Nash used the mapping underlying these dynamics to prove existence of equilibria in general games. The resulting Brown–von Neumann–Nash dynamics are a benchmark example for myopic adjustment dynamics that, in contrast to replicator dynamics, allow for innovation, but require less rationality than the best response dynamics. This paper studies the BNN dynamics for games with infinitely many strategies. We establish Nash stationarity for continuous payoff functions. For negative semidefinite games (that include zero sum games), we generalize the results of Brown and von Neumann. In addition, we show that evolutionarily robust Nash equilibria are asymptotically stable. A complete stability analysis for doubly symmetric games is also obtained.     

Learning by trial and error

A person learns by trial and error if he occasionally tries out new strategies, rejecting choices that are erroneous in the sense that they do not lead to higher payoffs. In a game, however, strategies can become erroneous due to a change of behavior by someone else. We introduce a learning rule in which behavior is conditional on whether a player experiences an error of the first or second type. This rule, called interactive trial and error learning, implements Nash equilibrium behavior in any game with generic payoffs and at least one pure Nash equilibrium.     

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.     

Learning and behavioral stability An economic interpretation of genetic algorithms

This article tries to connect two separate strands of literature concerning genetic algorithms. On the one hand, extensive research took place in mathematics and closely related sciences in order to find out more about the properties of genetic algorithms as stochastic processes. On the other hand, recent economic literature uses genetic algorithms as a metaphor for social learning. This paper will face the question of what an economist can learn from the mathematical branch of research, especially concerning the convergence and stability properties of the genetic algorithm. It is shown that genetic algorithm learning is a compound of three different learning schemes. First, each particular scheme is analyzed. Then it is shown that it is the combination of the three schemes that gives genetic algorithm learning its special flair: A kind of stability somewhere in between asymptotic convergence and explosion.     

Using co-evolutionary programming to simulate strategic behaviour in markets

This paper describes the use of a genetic algorithm (GA) to model several standard industrial organisation games: Bertrand and Cournot competition, a vertical chain of monopolies, and a simple model of an electricity pool. The intention is to demonstrate that the GA performs well as a modelling tool in these standard settings, and that evolutionary programming therefore has a potential role in applied work requiring detailed market simulation. The advantages of using a GA over scenario analysis for applied market simulation are outlined. Also explored are the way in which the equilibria discovered by the GA can be interpreted, and what the market analogue for the GA process might be.     

Collective learning,innovation and growth in a boundedly rational,evolutionary world

We formulate a simple multiagent evolutionary scheme as a model of collective learning, i.e. a situation in which firms experiment, interact, and learn from each other. This scheme is then applied to a stylized endogenous growth economy in which firms have to determine how much to invest in R&D, where innovations are the stochastic product of their R&D activity, spillovers occur, but technological advantages are only relative and temporary and innovations actually diffuse, both at the intra and interfirm levels. The model demonstrates both the existence of a unique long-run growth attractor (in the linear case) and distinct growth phases on the road to that attractor. We also compare the long-run growth patterns for a linear and a logistic innovation function, and produce some evidence for a bifurcation in the latter case.     

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.     

On economic applications of evolutionary game theory

Evolutionary games have considerable unrealized potential for modeling substantive economic issues. They promise richer predictions than orthodox game models but often require more extensive specifications. This paper exposits the specification of evolutionary game models and classifies the possible asymptotic behavior for one and two dimensional models.