ECONOMETRICA jourtixi dp tiir i.r-nM'niHT.rRir jnnicnr Evolutionary Games in Economics Author(s): Daniel Friedman Source: Econometrics, Vol. 59, No. 3 (May, 1991), pp. 637-666 Published by: The Econometric Society Stable URL: http://www.jstor.org/stable/2938222 Accessed: 01/11/2009 17:39 Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at http://www.jstor.org/page/info/about/policies/terms.jsp. JSTOR's Terms and Conditions of Use provides, in part, that unless you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you may use content in the JSTOR archive only for your personal, non-commercial use. Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained at http://www.jstor.org/action/showPublisher?publisherCode=econosoc. Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed page of such transmission. JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact support@jstor.org. 9 STOR The Econometric Society is collaborating with JSTOR to digitize, preserve and extend access to Econometrica. http://www.jstor.org Econometrica, Vol. 59, No. 3 (May, 1991), 637-666 EVOLUTIONARY GAMES IN ECONOMICS By Daniel Friedman 1 Evolutionary games are introduced as models for repeated anonymous strategic interaction. The basic idea is that actions (or behaviors) which are more "fit," given the current distribution of behaviors, tend over time to displace less fit behaviors. Simple numerical examples motivate the key concepts of fitness function and compatible dynamics, and illustrate the relation to previous biological models. Cone fields are introduced to characterize the continuous-time dynamical processes compatible with a given fitness function. The analysis focuses on dynamic steady state equilibria and their relation to the static equilibria known as NE (Nash equilibrium) and ESS (evolutionary stable state). For large classes of dynamics it is shown that all stable dynamic steady states are NE and that all NE are dynamic steady states. The biologists' ESS condition is less closely related to the dynamic equilibria. The paper concludes with a brief survey of economic applications. Keywords: Evolutionary games, evolutionary stable strategies, cone field dynamics. 1. introduction In an evolutionary game each individual chooses among alternative actions or behaviors whose payoff or fitness depends on the choices of others. Over time the distribution of observed behavior in a population evolves, as fitter strategies become more prevalent. The very prevalence of a behavior can make it (and other behaviors) more fit or less fit, so dynamics can be quite complex. One can ask which behaviors become extinct and which survive over time, whether the system approaches some stable steady-state, and so forth. The present paper has two goals. The first is to propose a tractable framework for evolutionary games which incorporates the relevant previous work by John Maynard Smith and his collaborators in biology and mathematics, but which is suitable for economic applications. The second goal is to derive substantive results on the relation between evolutionary steady states and static equilibria of the payoff or fitness function. Meeting these goals should encourage economists to employ evolutionary models in serious applied work. The biologists emphasize pairwise interactions of individuals drawn randomly from a single population and center their analysis on a static equilibrium concept known as ESS, for "evolutionarily stable" strategy or state. The inequalities defining ESS are intended to capture the intuition of an "uninvadable" state of the population: if the population is in an ESS then a small minority employing any deviant behavior (an "invasion of mutants") will eventually disappear under natural selection. Mathematicians, beginning with Taylor and 1 My thanks to audiences at UCLA and the Santa Fe Institute for useful suggestions. I especially wish to thank Jack Hirshleifer for getting me to think about this topic, for introducing me to the literature, and for many stimulating exchanges of views. I also wish to thank Nirvikar Singh, John Riley, and Eric Rasmusen for their constructive comments, Joel Yellin for useful discussions on technique, and a co-editor and two anonymous referees for generous editorial advice. The usual caveat shields them all. 637 638 daniel friedman Jonker (1978), confirmed that ESS was sufficient (although not necessary) for stability under natural selection dynamics. Economists and other social scientists can, I believe, usefully employ many of the ideas introduced by the biologists, but the biologists' formal structure needs to be adapted and extended. A fundamental point is that biologists almost always deal with the genetic mechanism of natural selection. This mechanism admits a simple, canonical dynamical representation, which I refer to below as the Malthusian dynamic.2 For economists the social mechanisms of learning and imitation are usually more important than the genetic mechanism. A wide variety of learning and imitation processes are conceivable and the appropriate dynamical representation seems to be highly context-dependent. To deal compactly with a diverse set of possible dynamics my formal analysis employs the device of cone fields, introduced by Smale (1976). It is not my purpose to propose any general theory of learning, so I rely on examples and references to existing literature to suggest specific dynamical processes which may be of interest. Two other, less fundamental extensions are worth noting briefly. Most of the existing biological models consider the evolution of a single species rather than the coevolution of several distinct species. My basic model, by contrast, features interactions of several strategically distinct populations, so as to represent economic relationships between buyers and sellers, or between residents in different jurisdictions, etc. Most biological models have (bi)linear specifications and are interpreted in terms of interactions between randomly matched individuals. By contrast, my basic model allows some nonlinearities to capture possible interactions with a whole population, a possibility biologists refer to as "playing the field." Evolutionary games as presented here are quite distinct from supergames and from differential games, even though all three examine the dynamics of repeated strategic interaction. Differential games allow payoffs to depend on the time paths of all individual players' actions, and supergames allow strategies defined on time paths even though current payoffs depend only on current actions. Such intertemporal strategies and payoffs are ruled out in evolutionary games. Thus a natural interpretation is of essentially anonymous interactions, in which the individuals one deals with today are not recognizably the same as those dealt with yesterday. Another distinction is that my analysis of evolutionary games focuses on the distribution of behaviors in populations rather than on the behavior of rational individuals.3 From the standpoint of an economist specializing in game theory, the static features of my formal model are minor variants of standard normal form games, 2 These dynamics are also referred to as replicator dynamics or as (the radial projection onto the simplex of) the Lotka-Volterra equations. 3 That is, I interpret the evolving state as a distribution of strategies across a population. One could also interpret it as the evolving (virtual or actual) mixed strategy employed by an individual, but one must then deal with some deep issues regarding rationality. In Section 4 I will cite some recent papers that employ this individualistic interpretation. evolutionary games in economics 639 but the dynamic features and evolutionary perspective will perhaps seem novel. Even for an economist interested only in long run equilibrium outcomes, a dynamic approach offers important benefits. First, one can distinguish stable from unstable equilibria. More generally, one can find the basins of attraction, i.e., the regions of initial conditions that eventually lead to a given equilibrium. Thus in principle one can identify which equilibrium point (if any4) is relevant. The next section briefly presents the formal ingredients of the model: spaces of states and strategies, fitness functions (variants of payoff functions) to specify strategic interaction, and systems of ordinary differential equations to specify dynamics. I then provide five simple examples. The first two are intended to give the reader an intuitive grasp of evolutionary games' structure and behavior and to motivate the pivotal concept of compatibility. The remaining examples make connections to previous literature from biology and elsewhere. Next I show how compatible dynamics can be summarized as cone fields, and end the section by defining static and dynamic equilibrium concepts. The analytic results are collected in Section 3. The most important demonstrate a close general relationship between the dynamic equilibria and the Nash equilibria (NE) of a fitness function—viz: all NE are compatible dynamic equilibria (Proposition 3.2) and all compatible dynamic stable equilibria are NE (Proposition 3.3). Of secondary interest is the relationship between ESS and the dynamic equilibria. The ESS are always a subset of the NE, so to the extent that Maynard Smith correctly identifies the dynamically stable equilibria in terms of his ESS criteria, he provides game theorists with an appealing refinement of NE. Unfortunately in general ESS is neither necessary nor sufficient for compatible dynamic stability, although there are some interesting special cases for which it is (Proposition 3.4 and counterexamples). Section 4 briefly summarizes the argument, points to some possible generalizations of the model, and surveys some recent and prospective applications of evolutionary games. Notational conventions, technical definitions, and proofs are collected in an Appendix. 2. the model 2.1. Basic Elements Consider a set of interacting populations, indexed k = 1,..., K. A member of each population k has available a finite number of actions (sometimes called "behaviors" or "strategies") indexed i = 1,..., N. (The increased generality in allowing TV" to depend on k is negligible and not worth the increased notational burden.) Any point rk in the TV-simplex Sk ■={x = {xl,..., xN): xt > 0, Ex, = 1} represents a possible mixed strategy for an individual member of population k. Any point sk in the same simplex also represents the fractions of population k employing each available strategy. Hence the Cartesian product of K copies of 4 In general dynamical systems, the state ultimately may approach a limit cycle or chaotic attractor rather than an equilibrium point. The analysis in the present paper, however, focuses on equilibrium points. 640 daniel friedman the simplex, S ■= S1 X • ■ • xSK, is the set of strategy profiles and also is the state space under the maintained interpretation that interactions are anonymous. It will be used for both purposes below.5 Strategic interaction is summarized in a fitness function which specifies for individuals in each population the evolutionarily relevant payoff as a function of own strategy and current state. Formally a fitness function consists of maps /*: Sk X S -* R, k = 1,..., K, which are assumed linear in the first (own strategy) argument rkeSk and continuously differentiable in the second (population state) argument s e S.6 The fitness function can be written more compactly as /: SxS->RK, with f(r,s)-=(f1(r\s\...,fK(rK,s)\ The linearity in x = rk can be regarded as a "large numbers" assumption: for large populations the fitness of a mixed strategy is the expected fitness of its component pure strategies. This linearity permits an alternative representation in terms of the fitness gradient vector fk(s) eRN for population k individuals given state s e S, with x -fk(s) =fk(x, s) for all x e Sk. The final basic model element is a dynamical structure specifying how a state s evolves over time. In continuous time7 one specifies the time derivatives s = (s1,..., sK), with sk ■■= (if,..., s^,) := (dsk/dt,..., ds^/dt), by means of some function F: S->RNK. Thus (2.1) s = F(s) is an autonomous system of ordinary differential equations whose solution curve s(t) from given initial conditions s(0) e S describes the evolution of all populations beginning at any state of interest. Some restrictions are required for legitimate dynamics. Say that F: S -+RNK is admissible if: N (a) £ Fk(s) = 0 for all s e S and k = 1,..., N; i=l (b) sk = 0 implies Fk(s) = 0, and (c) F is continuous and piecewise differentiable on 5. The first two conditions ensure that sk doesn't leave the simplex Sk: by (a) the 5 The dual role of S and its relation to the anonymous population interpretation will be discussed further in the last section. 6 Crawford (1989) shows that assuming continuity of the fitness function (in its second argument) has real bite. It may be worth mentioning that although the fitness function is closely related to the traditional payoff function of normal form games, there are formal and (in some contexts) conceptual differences. In the special case that /* depends perhaps on the state of other populations s~k but does not depend on own population sk, the standard payoff function g with components gk(s\ilx) ■■= fk(x,s) is equivalent to the fitness function /. Own population effects and some conceptual distinctions will be illustrated in Examples 3 and 5 of the next subsection. 71 will not analyze discrete time dynamics (difference equations) in this paper. Apart from some minor but annoying technicalities concerning behavior at the boundary of the simplex, it appears to be a routine exercise to obtain discrete time analogs for most of my results. Indeed Nachbar (1989) and Samuelson (1987), working independently and using different techniques, obtain difference equation analogues of (the order-compatible version of) my Propositions 3.2 and 3.3 for fairly general fitness functions. evolutionary games in economics 641 TABLE I Payoff Bimatrix for Basic Buyer / Seller Game Seller: 1 ("honest") 2 ("cheat") Buyer: 1 ("inspect") (3,2) (2,1) 2 ("don't") (4,3) (1,4) population fractions will continue to sum to unity, and (b) prevents fractions from becoming negative. Also (b) prevents the revival of extinct strategies.8 Condition (c) is a mild technical condition to help ensure "well-behaved" solutions; actually, the weaker assumption of Lipshitz continuity guarantees unique solution curves and would suffice for most purposes. An admissible F henceforth will be referred to as a dynamical system (or, simply, a dynamic) on S. 2.2. Some Simple Examples Example 1: Basic ideas. Consider a stylized interaction between two populations, called "buyers" (k = 1) and "sellers" (k = 2). Each seller has available two possible actions or strategies, "honest" (i = 1) and "cheat" (i = 2); and each buyer also has two alternative strategies, "inspect" (i = 1) and "don't inspect" (/ = 2). Since the strategy/state simplices here are 1-dimensional the state s = ((s{, s\), (s2, sf)) can be described by a point (p, q) in the square [0,1] x [0,1], with s\=p as the fraction of buyers who inspect and s2 = q as the fraction of honest sellers, so s\ = 1 —p and s\ = 1 - q. The populations interact in an unorganized market in which individual buyers and sellers of, say, used cars meet and participation is occasional so reputational effects, etc., are negligible. The fitness of a strategy depends on the population mix of chosen strategies, e.g., cheating is less attractive to sellers when more buyers inspect, but otherwise matters are as simple as possible (e.g., random matching, no externalities, and risk neutrality). Specifically, assume that the fitness function is bilinear and given by the bimatrix of Table I.9 Thus for a buyer the fitness of e1 = (1,0) = inspect with probability 1, is f1(e1;s) = 3q + 2(1 - q) = q + 2 (independent of p) and f\e2; s) = 4q + (1 - q) = 3q + 1 is the fitness of not inspecting. Likewise f2(e1; s) = 3 —p is the fitness for a seller of being honest with probability 1 and f2(e2; s) = 4 - 3p is the fitness of cheating. 8 Presumably imitation and perhaps simple versions of Bayesian learning would not permit the revival of extinct strategies, but more flexible ideas of learning might well permit it. The direct restriction (b) has no bite in stability analysis, since all strategies, extinct or otherwise, are contemplated in a general small perturbation. See also Remark 3.2 below. 9 The table entries are from Game 72 of Rapoport and Guyer (1966). Pitchik and Schotter (1987) analyze essentially the same strategic situation in greater depth. However, their comparative static results implicitly assume that the interior NE is stable, and the analysis to follow shows that this assumption is problematic. See also Frank (1987) for a single-population game with a similar flavor. 642 daniel friedman q=1 q=1/2 0 0 p=1/2 Figure 1 p=1 As for dynamics, assume with Malthus that the growth rate of a strategy is proportional to or (with an appropriate choice of time scale) equal to its relative fitness. That is, the growth rate of inspection (In p)=p/p is equal to its fitness /He1; s) less the population average fitness among buyers f\p;s)-= pf\e\s) + (1 -p)fl(e2; s). Hence, (2.2) p=p(l-p)(l-2q). The growth rate q/q of honesty among sellers is its relative fitness f2(e1; s) -f2(q;s) = (l-q)(2p-l\ so (2.3) q = q(l-q)(2p-l). It is easy to check that the system (2.2)-(2.3) of coupled differential equations has five fixed points (i.e., steady-states), at the center and at the four corners of the p — q square. It can be shown (see the Appendix) that all other points are on periodic trajectories circling counterclockwise, as shown in Figure 1. Thus under Malthusian dynamics the four corner fixed points are unstable and the center point is neutral, neither asymptotically stable nor unstable. Example 2: Alternative dynamics. Economically plausible alternatives to Malthusian dynamics can be constructed from specific models of imitation and learning. For example, suppose that each used car buyer transacts only once; before making his or her own choice, the buyer observes the choice of a single, randomly selected previous buyer and, with a small exogeneous probability a, also observes the predecessor's payoff. Assuming that all participants are Bayesians with diffuse priors over p and q and with common knowledge of the information structure, it evidently is rational for the new buyer to imitate the predecessor's choice when the outcome is not observed, and to make a "best reply" to the inferred seller choice when the outcome is observed. This behavior yields the discrete-time dynamic Ap = a(-q + [1 - q]). Choosing the time scale so that At = 2a and taking the limit as the information lag At -* 0 one obtains the differential equation p = \— q. By strict analogy the sellers' population obeys the differential equation q =p — \. evolutionary games in economics 643 q=1 q=1/2 0 p=1/2 p=1 Figure 2 One can also directly postulate linear dynamics by setting the rate of change (not the growth rate as in Malthus) of a strategy equal to its fitness relative to the simple average (not population-weighted average) of all strategies currently employed.10 From the Table I fitness function one calculates p=f\e';s)-\[f\el;s)+f\e2;s)\ = \[fl{el;s)-f\e2;s)\, i.e., (2.4) p = \-q and similarly, (2.5) q=p-\ for (p, q) in the interior of the square. To keep p and q in [0,1], override (2.4) and (2.5) by (2.6) p = 0if p = 0,l; 0) strategies by I(sk). Say the dynamic F: S -* RNK is order compatible with a fitness function / if, for each k = 1,..., K, we have Fk(s) > Fjk(s) iff /*( fk(eJ, s) for all i, j e I(sk), and Fk(s) = 0 for i e I'(sk). The last qualification applies the ordinal relationship only to nonextinct strategies, and repeats the admissibility condition (b) that F can't revive extinct strategies. An alternative, less stringent requirement is that there is just a positive correlation between the components of the velocity vector sk = (sk,...,sfr) and those of the fitness gradient fk(s) = (fk(e1,s),..., fk(eN,s)). Formally, say the dynamic F: S -> RNK is weak compatible with a fitness function / if, for all k = l,...,K, and s e S, we have Fk(s)~ On iff fk(el, s) = a for some aefi1 and all / e I(sk), and otherwise Fk(s) -fk(s) > 0. The first part of the definition allows the tangent vector to be zero only where all nonextinct strategies are equally fit; elsewhere the tangent vector Fk(s) and the fitness vector /* make an angle of less than 90°. 13 My thanks to John Riley for suggesting this interpretation. 648 daniel friedman Compatible Dynamics e1 [y1 e1 Weak Compatible Figure 5 Both concepts of compatibility are illustrated in Figure 5. A point x = sk in the interior of the unit 3-simplex Sk is chosen for reference, and the isoquant (a) through sk as well as two nearby isoquants (a ± e) are shown for some fitness function /*. Order compatible dynamics will have solution curves with tangent vectors at sk which lie inside the cone sketched on the left of Figure 5. Here fk(el,s)>fk(el,s)>fk(ei,s) so the cone is open, bounded by the rays [e' = el > ej] and [e' > e1 = eJ], and contains the projection irT of fk(s) onto the tangent plane. Similarly, the diagram to the right of the simplex shows the open half-space of weak compatible admissible tangent vectors for /* at sk. Thus weak-compatible dynamics will have trajectories which move towards higher isoquants.14 In some contexts one might prefer to impose compatibility conditions on the growth rates (In' sk) = sk/sk rather than directly on the rates of change sk of population fractions. Thus, let G: S -* RNK be differentiate and let D(s) represent the NKxNK diagonal matrix with the components of the vector s e RNK down the diagonal. Suppose Gk(s) is perpendicular to sk for each k, and G is compatible (order or weak) with a fitness function /. Then F: S -»RNK, denned by F(s) ■•= D(s)G(s), will be a (n admissible) dynamic whose growth rates by construction are compatible with /. I will refer to differentiable functions G: S -* RNK with Gk perpendicular to sk as predynamics for this reason. A compact summary of all compatible dynamics greatly simplifies proofs of the main results. As illustrated in Figure 5, the admissible tangent vectors that are order (or weak) compatible with a given fitness function at a given state form a cone in the tangent space of S at that state. This observation suggests 14Of course, as s = s(t) evolves, /*(•, s) and its isoquants will shift. evolutionary games in economics 649 that the technical device of cone fields, introduced in the context of exchange dynamics by Smale (1976), will be equally useful in the present context of game dynamics. In each version of compatibility (order or weak, dynamics or predy-namics) one specifies for each population k and each state s in S a subset of tangent vectors (a cone Z) that are admissible and compatible in the appropriate sense. The Appendix contains formal definitions. Two specific compatible dynamics obtained directly from the fitness function are worth mentioning. The first merely sets Fk(s) equal to the orthogonal projection of fk(s) onto the tangent space of the (sub)simplex. Hence if / is bilinear this dynamic is piecewise linear, and linear on each open subsimplex. Intuitively, its trajectories head straight up the "fitness hill" on each Sk (or on the appropriate subsimplex, if some strategies are extinct in population k). We encountered this dynamic in Example 2, equations (2.4)-(2.6). I will denote it by Lf and call it the linear dynamic. The other dynamic, denoted Mf, is analogous for growth rates. Intuitively, one renormalizes the fitness vector so it is a predynamic and then the corresponding dynamic will feature strategy growth rates equal to relative strategy fitness—that is, we obtain the Malthusian dynamic. Since Mf works with growth rates, strategies never become extinct in finite time in the trajectories it defines, while they certainly can under the Lf dynamic. The precise construction of Lf and Mf for an arbitrary fitness function / can be found in the Appendix. 2.4. Equilibrium Concepts Two static concepts of equilibrium can be denned directly from the fitness function. Say that s is a Noncooperative (or Nash) equilibrium point for the fitness function /, and write seNE(f), if fk(x, s) ^fk(sk, s) for all xeSk, k = \,...,K. The intuition is the same as in standard game theory: the inequality says that sk is a (weak) best reply against s for all k. Say that s is an evolutionary stable state for the fitness function /, and write s e ESS(f), if for each k = l,...,K and xi=sk&Sk, we have either (a) fk(x, s) 0 sufficiently small. The notation s\kx means (s1,...,sk~l,x,sk+l,...,sK), and s\kxs means (1 — e)s + e(s\kx), i.e., a slight perturbation of sk towards x. Of course, in the case that / is bilinear, the references to s can be dropped from the definition. Remark 2.1: Obviously ESS is a refinement of NE, i.e., ESS(f) czNE(f). Remark 2.2: An equivalent definition for ESS is simply that fk(x,s\kxe) < fk(sk,s\kxe) for e>0 sufficiently small. However, a two-part definition is traditional, and helps distinguish two useful cases. Remark 2.3: Maynard Smith's intuition, explained at length in his 1982 book, is that ESS is a stability condition. Think of x as a mutant strategy, so s\kxe is the state after a small invasion of population k mutants. The inequalities 650 daniel friedman defining ESS say that mutants are less fit than the dominant group (and hence presumably will disappear) either because (a) they do less well in encounters with the dominant group or (b) they do equally well in encounters with the dominant group but less well in encounters with other mutants. I will refer to an assertion that ESS is necessary or sufficient for dynamic stability as a Maynard Smith conjecture. Remark 2.4: Nash equilibrium points exist for every fitness function. The proof is a minor variant on the standard existence proof for NE in normal form games, using the Kakutani fixed point theorem. Remark 2.5: NE states can be characterized as those whose "extinct" strategies (i.e., i such that sk = 0) are no more fit than nonextinct strategies (sk > 0) and whose nonextinct strategies are equally fit. Formally, we have the following: Let ak ■= max{fk(e', s): i = 1,..., AO. Then s is a Nash equilibrium point iff, for each k, fk(e', s) = ak for all i such that sk > 0. The proof again is standard, with details available from the author. Remark 2.6: It is tempting in light of the previous remark to conjecture that ESS are the subset of NE for which extinct strategies are strictly less fit than nonextinct strategies for each population, and for which the nonextinct strategies reach peak fitness in some sense (say a negative-definiteness condition). Taylor and Jonker (1978) show that this conjecture is almost but not quite true. Following their approach, define i*e5 to be a regular ESS if (a) fk(e', s*) < a-=fk(s*k,s*) for all i such that sk = 0, and (b) the matrix Ak ■= ((dfk(e',s*)/dsf)) is negative definite on the tangent space at sk, {z^RN: £z, = 0, and sfk = 0 => z}■ = 0}, for each k = 1,..., K. Taylor and Jonker argue that every regular ESS is an ESS, and almost every ESS is regular.15 The dynamic equilibrium concepts are conceptually straightforward: we seek to characterize steady states, and states to which the dynamic process returns following a small perturbation. Such equilibria are defined in terms of the function F that specifies the dynamical system on S. Say that s is a fixed point (a.k.a. steady state or equilibrium point) for the dynamic F, and write s e FP(F), if all components of F(s) are 0. Such states are steady in that s(t) = s(0) for all t e [0, co) iff i(0) e FP(F). Say that s is an evolutionary equilibrium (a.k.a. stable equilibrium or persistent state) for F, and write s e EE(F), if s is a locally asymptotically stable fixed point, i.e., if s is a fixed point and it has some open neighborhood NcS such that s(t) ->s as t -> oo wherever s(0) eN. Thus all states near an evolutionary equilibrium will eventually evolve towards it. 15 The matrix could be only negative semi-definite, yet the inequality in part (b) of the ESS definition might still hold because of higher-order terms. The regularity condition rules out this unlikely situation. The condition will be used only in Proposition 3.4. evolutionary games in economics 651 3. results Given the four equilibrium concepts just defined, the theorist will instinctively ask about their relationships. The applied researcher investigating a specific fitness function / and compatible dynamic F also has a stake in the question. Evolutionary equilibria of F, as the persistent states of the model, provide the basic predictions for observables, but these equilibria may be difficult to compute directly and need not exist. The more convenient static equilibria of / take on added interest once the investigator has theoretical reassurance of their relationships to evolutionary equilibria. For standard biological models the relationships among the equilibria are by now well known: for the Malthusian dynamic Mf of a bilinear single-population fitness function / we have ESS(f) oEE(Mf) cffi(/) cFP(M/); see van Damme (1987) for instance. In particular, the static ESS concept is sufficient and NE is necessary for evolutionary equilibrium in standard biological models. This section will show that the last two inclusions are quite general: for any dynamic F even weakly compatible with a given (possibly nonlinear and multi-population) fitness function /, the evolutionary equilibria of F must all be NE of / (Proposition 3.2) and all NE of / must be fixed points of the dynamic F. These results allow the researcher to confidently apply known existence results for NE and simple computational devices for FP. On the other hand, the first inclusion does not generalize as well (Proposition 3.4 and counterexamples), so the researcher can avoid possibly misleading analyses of ESS. We begin with the preliminary result that, as Figure 5 and the choice of terminology suggest, order compatibility implies weak compatibility. The result streamlines the statement and proof of the main propositions. Proposition 3.1: For every fitness function f, for every state s in S, and for k = l,...,K, the order compatible cones ZgC(f, s) for dynamics and Z^p(f, s) for predynamics are subsets of the corresponding weak compatible cones Z*c(f, s) and Z£,(/,s). See the Appendix for a proof of this and the other propositions. The next result confirms that a static equilibrium concept (NE) is a sufficient condition for dynamic equilibrium (FP) for any compatible dynamic. Existence of dynamic equilibrium is a corollary. The proposition also shows that the static and dynamic concepts actually coincide for interior equilibria, i.e., equilibria with no extinct strategies. Proposition 3.2: Let the dynamic F be weak compatible with the fitness function f. Alternatively, let the predynamic G be weak compatible with f and let F{s) = D(s)G(s). In either case, all Nash equilibria are fixed points and all in- 652 daniel friedman terior fixed points are Nash equilibria, i.e., NE(f) (^FP(F) and NE(f)nS° = FP(F) n S°. Corollary 3.2.1: Proposition 3.2 also holds with "order compatible" replacing "weak compatible." Proof: Follows directly from Proposition 3.1. Corollary 3.2.2: Let the dynamic F be weak or order compatible with some fitness function f. Alternatively, let F(s) = D(s)G(s) with G weak or order compatible with f. Then F has an equilibrium point, i.e., FP(F) ^ 0. Proof: Follows from Remark 2.4, Proposition 3.2, and Corollary 3.2.1. As a complement to the previous proposition, the next result confirms that the evolutionary equilibria (EE) are always NE for a corresponding fitness function. Proposition 3.3: Let the dynamic F be weak compatible with the fitness function f, or alternatively let F(s) = D(s)G(s) and let G be a predynamic which is weak compatible with f. Then all stable equilibria of F are Nash equilibria, i.e., EE(F)cNE(f). Corollary 3.3.1: Proposition 3.3 also holds with "order compatible" replacing "weak compatible." Proof: Follows directly again from Proposition 3.1. Remark 3.1: By analogy with the last part of Proposition 3.2, one migh-; wonder if EE(F) sometimes coincides with NE(f). In particular, for SE = {e1,eN}K representing the extreme points of S (i.e., each population adopts a single strategy with probability 1) it is reasonable to conjecture that NE(f) n SE = EE(F) n SE for F compatible with /, so strict NE implies ESS. It is not difficult to see that the conjecture is true if the values fk(e', s) are distinct (across i) for s e SB, which usually (i.e., for generic /) is the case. Remark 3.2: One could weaken the definition of admissibility, so that extinct strategies i e F(s) could be revived (without perturbing the state) and only further decreases for such strategies (i.e., choice by a negative fraction of a population) are excluded. Weakening admissibility means reducing the number of fixed points, since F(s) ¥> 0 is possible more often. Indeed, under the weakened definition NE(f) = FP(F) and examples of unstable fixed points are harder to come by. No similar modification seems appropriate for the growth rate case, since it employs no boundary condition. evolutionary games in economics 653 Remark 3.3: It can be shown that Propositions 3.2 and 3.3, together with Remark 2.5 and the definitions, offer convenient computational algorithms for equilibria of evolutionary games, particularly when the fitness function is bilinear. In this case, the definition of FP provides for each subsimplex a square system of linear equations stating that the fitnesses of nonextinct strategies are equal, and that points lie in the relevant subsimplex. Solutions to the system can be tested for the additional NE, ESS, and EE properties. For details, see Friedman (1987) and the biological literature, especially Haigh (1975). The last proposition collects positive results concerning Maynard Smith conjectures. If one is interested only in linear or Malthusian dynamics, or if one has a symmetric fitness function, then the conjectures are mostly correct. The conjectures evidently arose from consideration of a bilinear fitness function for one population and two strategies (illustrated in Figure 6 below and discussed in the last proof in the Appendix), so it is no surprise that they also hold in this case. Proposition 3.4: Let s be a regular ESS for some fitness function f. Then: (a) s is an EE under Malthusian and also under linear dynamics; (b) if s ^S° and f is bilinear, then ESS(f) = EE(Mf) = EE(Lf) = {s}; (c) if N = 2, K=l, and f is bilinear, then ESS(f) = EE(F) for all weak compatible dynamics F; and (d) iff is symmetric, then s e EE(F) for any dynamic F which is weak or order compatible with f. Remark 3.4: The symmetry condition in Proposition 3.4(d) of course is that f(r,s)=f(s,r), suggesting team games. Readers acquainted with the biological literature might be confused on this point because Maynard Smith refers to the single population case (K=l) as the "the symmetric case" and to certain special cases of K > 1 as "the asymmetric case."16 Remark 3.5: I suspect that Proposition 3.4 holds even if the ESS is not regular, but I have not been able to find a proof for part (a) when .$ is not interior. I conclude this section with three counterexamples that show that ESS is neither necessary nor sufficient for the dynamic stability of a fixed point of a compatible dynamic, and that ESS and EE do not always exist. See Friedman (1987) for details. 16 Maynard Smith applies the term "asymmetric case" to a single genetic population whose members sometimes play different "roles" (e.g., owner or intruder in a territorial contest) and have role-dependent strategy sets. The most natural way to formalize this idea in the present framework is to write an underlying general fitness function with K = the number of possible roles, and then reduce it (by taking the expectation with respect to role probabilities) to a single-population fitness function defined on role-contingent strategies. See Selten (1980) for a different formal approach. 654 daniel friedman e1 p* e2 1) a,b>0 o—«-o 81 p* e2 2) a,b<0 > « 0 » « ei e2 3) a>0>b,es. • •*-o ei e2 4) a<0 e > 0, {s} = ESS(f) = EE(Lf) = EE(Mf). is a saddle point and ESS(f) = EE(Lf) = (here 3-dimen- 0. There is a stable limit cycle with a shape in S sional) like the seam of a baseball. 656 daniel friedman 4. discussion 4.1. Interpretations and Extensions The results of the last section indicate that NE is a very useful static concept for analyzing steady states of evolutionary games. Whether one works with a specific dynamic, such as the Malthusian or the linear, or knows only that the dynamic is compatible (even just weakly compatible) with a fitness function /, the results of the last section ensure that there is always a nonempty set NE(f) of points all of which are steady states and which contain all dynamically stable steady states. An important message of the results is that ESS has no such general usefulness. There are special cases, as indicated in Proposition 3.4, in which ESS's (if they exist) will be dynamically stable steady states and therefore represent an interesting refinement of NE. However, the counterexamples show that in general the ESS property is neither necessary nor sufficient for dynamic stability of order compatible (much less weak compatible) evolutionary processes. The evolutionary framework suggests some NE refinements with greater general appeal than ESS. Larry Samuelson (1987) shows for bilinear K=2 discrete time games that convergent evolutionary processes obeying a somewhat stronger condition than order compatibility will converge to perfect NE, and that even nonconvergent processes will lead to asymptotic extinction of nonra-tionalizable strategies. Nachbar (1989) establishes in somewhat greater generality that the NE refinement dominance solvability (and, in some cases, weak dominance solvability) suffices to ensure the convergence of order-compatible dynamics. Significantly sharper refinements may not be possible. Given the variety of economically plausible dynamics, it seems unreasonable to expect any static definition to pick out precisely the economically relevant equilibria. From an evolutionary perspective the quest for the ideal (static) NE refinement thus appears futile. A search for useful classes of learning and imitation dynamics seems more promising because ambiguities vanish regarding the relevant equilibrium once the dynamics (and initial conditions) are determined. The formal framework employed here can be modified in several ways. For example, I have assumed that the evolution of the system is everywhere governed by a given compatible dynamic F, so that s = F(s) e Z(/, s). Instead one could merely require that s e Z(f, s), i.e., allow the learning rule to vary over time and state. Such "nondeterministic" or "differential inclusion" dynamics allow self-intersecting trajectories, but it is reasonable to conjecture that the main results will still hold, given the results of Friedman (1979) and Aubin and Cellina (1984). A more substantial generalization of the present framework allows analysis of nonanonymous strategic interaction. The idea is that fitness could depend on which agents employ the various strategies, and not just on the population distributions of strategies. Hines (1980) takes a step in this direction. Building evolutionary games in economics 657 on the biologists' distinction between monomorphic models (all individuals play the same mixed strategy except for a small subpopulation of mutants who all deviate to some other mixed strategy) and polymorphic models (all individuals play pure strategies which may differ across individuals), Hines regards states as distributions of mixed strategies (i.e., measures on S rather than points in 5). He shows that the population mean evolves under Malthusian dynamics in a manner similar to that of the basic model (in essence one replaces the fitness matrix A by CA where C is the population covariance matrix), but that ESS is necessary for stability in this state space. Schmeidler (1973) provides the static elements for general nonanonymous evolutionary games: a continuum of agents t e T = [0,1] and Lebesgue-measur-able strategy profiles x mapping T into the JV-simpIex. The state space is the set of all such strategy profiles and the payoff function is assumed linear in own (mixed) strategy and continuous in the state. Masso (1988) employs these static elements together with "memory strategy" dynamics adapted from Smale (1980). Both authors focus on existence of NE and emphasize the special "anonymous" case (Masso, Assumption A.2, page 61) in which the payoff depends on the state x only through its mean JTx. In the anonymous case the Schmeidler payoff function and auxiliary function reduce respectively to a fitness function / and fitness vector / as defined in Section 2.1 above. Schmeidler and Masso each show that under the anonymity assumption any NE is implementable in pure strategy choices for each player iel. The general nonanonymous model in my view will be useful when the number of strategically distinct types of interacting agents is unbounded; otherwise the evolutionary game framework of Section 2, taking K as the bound on the number of types, seems adequate. Infinite-dimensional state spaces can also arise when there are infinitely many pure strategies, as in games of timing; for example, see Riley (1979) who also discusses the effects of finite population size in biological models. 4.2. Applications The applications to substantial questions in economics and other social sciences will ultimately measure the value of evolutionary games. Here I will briefly and nonsystematically survey some recent applications related to evolutionary games, and then suggest some new areas of application. Several more systematic surveys are now available. Hines (1987) is a relatively recent and mathematically sophisticated summary of the biological ESS literature. Chapter 9 of van Damme (1987) provides a compact summary of game theoretic results relating to ESS and an introduction to Malthusian dynamics. Hofbauer and Sigmund (1988) is a delightful compendium of biological applications of dynamic systems theory, whose "red thread" is Malthusian dynamics. A recent brief theoretical survey can be found in Nachbar (1989). Conlisk (1980) provides an early evolutionary approach using discrete time dynamics with lags and stochastic components. He postulates two pure strate- 658 daniel friedman gies, "optimization" and "imitation," and looks for an equilibrium population ratio of these two strategies where a quadratic loss function for nonoptimizers must balance a constant positive cost to optimization. The main result is that the fraction of optimizers in the population does not asymptotically converge to 1 as long as imitation is fitter than optimization when the population is almost all optimizers. Clearly this conclusion would also follow for any true order compatible dynamics. The question of whether an investor should purchase securities information or just rely on (nearly?) efficient asset prices has a similar flavor to Conlisk's optimization vs. imitation discussion. Cornell and Roll (1981) answer this question in terms of an interior ESS of a model formally equivalent to the biologists' simplest (K=l, N — 2) static territorial conflict model. They also discuss biologists' "asymmetric" models as a device to explain the seniority system in hierarchical organizations. James Friedman and Robert Rosenthal (1986) introduce migration dynamics for bilinear K = 2 games with no externalities, in order to explain deviations from NE observed in laboratory oligopolies and similar experiments. For reasons discussed in Example 2.5 above, the NE of their payoff functions are not typically dynamic equilibria. Schofield (e.g., 1978) studies dynamic games of social choice, inspired more by nontatonnement processes than by evolutionary considerations. The idea is that at each point of policy space individual preferences and the choice rules (e.g., majority vote) define policy increments that are feasible and preferred by a relevant coalition (e.g., a majority); such increments form a cone in the tangent space at that point. Schofield shows that piecewise smooth paths (called "optimizing" curves for some reason) whose tangent vector at each point lies in the cone need not converge. Indeed, given a condition called "null dual" that is often satisfied, optimizing curves exist between most pairs of points so cycles are very common. By contrast, Smale (1976) and followers (e.g., Friedman (1979)) obtain quite strong convergence results for cone field dynamics in exchange economies. Recently several authors have begun to model dynamic games with an evolutionary perspective on individual (not population) choice. Skyrms (1986) discusses some philosophical issues regarding rationality in games, and introduces a virtual "deliberational dynamic" (describing the adjustment of the mixed strategy contemplated by an individual) that seems formally equivalent to the linear dynamic. Binmore (1987/88) points out several other problems with rationality in the static specification of games; he emphasizes extensive-form games of imperfect information but some of the problems also arise in standard normal-form games with several NE. He suggests a dynamic resolution to the problems, and distinguishes between "eductive" processes (reminiscent of Skyrms) and "evolutive" processes in which some sort of selection mechanism operates on boundedly-rational automated players. Possibly the general non-anonymous model sketched above will be useful in pursuing the individualistic interpretation of evolutionary games. evolutionary games in economics 659 Crawford (1989) examines laboratory games in which subjects are motivated to match the minimum or median contribution towards a public good (so the payoff is not bilinear; these are "playing the field" fitness functions). He sketches an adaptive model inspired by ESS literature (evidently a stochastic version of the linear dynamic) that seems capable of explaining the data. The paper more generally shows the promise of laboratory experiments as an empirical tool for finding specific evolutionary dynamics of economic interest. A computerized tournament in which several game theorists submitted automated strategies for the repeated prisoners' dilemma, reported in Axelrod and Hamilton (1981), spawned an extensive and fascinating body of literature. I will not attempt a survey; see Axelrod and Dion (1988). Marks (1989) also contains a recent review that draws connections to the Holland (1980) "genetic algorithm." The tournament does not fit neatly into the present framework since it involves a supergame viz., nonanonymous repeated encounters in the Prisoner's Dilemma. However, Hirshleifer and Martinez-Coll (1987) re-express this supergame as an evolutionary game and show that "tit-for-tat" is not as robust a strategy as some authors have claimed. Arthur (1989) employs a stochastic version of Malthusian dynamics arising from a learning algorithm rather than from the genetic mechanism. He shows that the limit points must be NE. Boyd and Richerson (1985) explore a variety of models that contrast and often combine genetic and social selection mechanisms. Inasmuch as economists regard a single generation of 30 years as "long-run" or "very long-run," the time scales in the latter article are exceedingly long for economic applications. New potential economic applications of (population) evolutionary games include monetary theory, industrial organization, and international economics.18 A recurrent question in the first field is how a medium of exchange might emerge in a laissez-faire barter economy with transactions costs—e.g., see Jones (1976) and the recent survey by Cowen and Kroszner (1987). It seems natural to address this question in terms of an evolutionary game with pure strategies representing an agent's willingness to accept specific goods he does not ultimately wish to hold; one looks for the presence of corner EE and absence of interior EE to justify a single medium of exchange.19 In industrial organization, one might study the "fitness" of alternative strategies such as independent entry, franchising, and merger under specific assumptions regarding product pricing.20 One might also usefully consider K = 2 models for worker and firm populations, in which one could consider issues regarding unionization, apprenticeship vs. other methods of acquiring specific 18 This list of topics is certainly not exhaustive. For example, the perspectives in Hirshleifer (1977) indicate that the economics of law is a natural area for applied models of evolutionary games. 191 was pleased to discover recently that Marimon, McGrattan, and Sargent (1989) take just such an approach to the issue, using dynamics based on Holland's genetic and classifier algorithms. 20 It might be amusing to model Porter's (1980) popular "generic competitive strategies" (cost leadership, differentiation, and focus) in an evolutionary game and see whether an interior EE is possible. 660 daniel friedman skills, and compensation methods. For instance, with regard to the last issue, one wonders whether Weitzman's (1984) proposed share economy is dynamically stable, given workers' incentive not to dilute their ownership shares; one could use an evolutionary model to test the conjecture that firms which promise not to dilute might successfully invade an industry of Weitzmanian firms. In international economics, one could consider the sectoral investment choices of entrepreneurs in autarky as a K=\ model. Then, for n countries, one obtains a K = n evolutionary model by coupling the autarky models under some (not necessarily free) trading regime. Such a model may be useful for discussing the dynamic impact of trade and capital restrictions on sectoral investment and output. Another potentially fruitful avenue of investigation can be taken in conjunction with applications such as those just described or on its own: the systematic exploration of specific learning and imitation rules and their dynamic implications. Department of Economics, University of California, Santa Cruz, CA 95064, U.SA. Manuscript received April, 1988; final revision received April, 1990. APPENDIX A.l. Notation and Definitions R" denotes Euclidean space of finite dimension n> \ with the usual basis el,...,en, where e' = (0,..., 1,..., 0), the 1 being in the ith place. Vectors, denoted x, v, e', etc., are column vectors for purposes of matrix calculations but usually are written as row vectors as above to simplify typography. The symbol — means "is denned as." For vectors or scalars xl,...,xm and y, the notation |* refers to replacement of the &th component; e.g., if x = (x1,..., xm), then x\^y— (x1,..., xk~1, y, xk + l,..., xm). X° denotes the (relative) interior of a set XcR". For I a finite set, #1 is the number of elements of /. The usual inner product is denoted by a dot, i.e., x -y ■=Y!l-ixiyl for x = (xv..., xn) and y = (V],..., y„) e R". H(x, a) — {v eii": v ■ x = a) is the (n - 1 dimensional) hyperplane with normal xeR" translated from the origin On = (0,...,0) along x for the distance aeR1. The corresponding closed and open positive half-spaces are H+(x, a) ■■= [v e Rn: v ■ x > a) and H+(x, a) ■■— {v eii": vx>a). Negative half-spaces H_ are analogously denned. H(x) •■= H(x, 0) and similarly for the half-spaces. The positive orthant thus is /?"== (~1+(«'), and the unit simplex is A ■= H(ln, 1) n R"+, where 1„ = (1,..., 1) e R" is the diagonal vector. For seA, let I(s) ■= {/ = 1,..., N: s, > 0} and I'(s) ■■= {/: s, = 0), and let be the subspace of RN spanned by {e'\ i e Us)). Then s is in the subsimplex AI{S) ■■= H(\N, 1) n Its tangent space is H(lN)nR'(s). The order-cone for xeR" is C(x) = {yeRn: y, RNK is a dynamic which is order compatible with the fitness function / iff Fk(s) e C(fk(s))r\H(lN)r\R'(sk) for all s e S and all k. Hence define the order compatible cone for / at s Zkoc(f,s) <= C(fk(s))nH(lN)nR'^ evolutionary games in economics 661 Likewise, G is an order compatible predynamic if Gk{s) e C(fk(s)) n H{sk) n i?/ RNK by Mf(s) ■■= D(sXf(s) ~ a*(s)), where a*(s) £RKN has its fe-components (all N of them) equal to fk(sk, s) = Y.skfk(e', s), the populations-weighted average fitness of population k strategies. It is immediate that s ■ (f(s) -a*(s)) = 0 so f(s) — a*(s) is indeed a predynamic which is order-compatible with /. If / is bilinear, then Mf will specify differential equations of degree 3. Before presenting proofs of the Propositions, I sketch the analysis behind Example 1 and Figure 1 for readers who are interested. The center point and the four corner points are clearly the only solutions to 0 = p = q in equations (2.2) and (2.3). Summarizing the equations as (p,q) = F(p,q), one readily calculates the Jacobian whose eigenvalues are purely imaginary at ±i/2, so up to first order the trajectories are (counterclockwise) concentric circles of period 4i7. The higher order terms could stabilize or destabilize this fixed point, so further analysis is required. One employs new variables that translate the fixed point to the origin, x = p - \, y = q — and re-expresses equations (2.2)-(2.3) as x=X(x,y)<= -2y(\-x2) and y = Y(x, y) ■■= 2x(+y2). Observe that dx/d(-t) = -X(x, y) =X(x, -y) and dy/d(-t)= — Y(x,y)= -Y(x,-y). Hence for initial conditions x(0)=x0>0 and y(0) = 0, the solution curve satisfies x(t) = x(-t) and y(t)= -y(-t) for all t eR. In particular, y(tg) = 0 for some smallest t0 > 0 (for x0 small, t0 = 2v) by the first order approximation, so the solution curve is a closed loop of period 2t0 which has x = 0 as an axis of symmetry. Similarly, y = 0 is also an axis of symmetry, and a simple argument shows that x = y and x = -y are further axes of symmetry. Alternatively, one observes that the function H(p,q) = pq(l -p\\ — q) is constant on solution curves and has closed isoquants. Consequently the phase portrait is the same (up to time reparameterization) as the isoquant map. Re-expressing the equations in the polar coordinates x = rcos 8, y = r sin 8, one finds that f = l/2r3 sin 48 and 8 = l/2 - r2(l - cos 40), which yield the squarish trajectories of Figure 1. A.2. Proofs Hence, at the corners (p, q = 0 or 1) we have which implies that these are all saddle points. At the center point we have Remark A.l: It is not always the case that the order cone of a vector lies in its own positive half-space. For instance, take x = (1,2,3) so for y = (-3, -2, - Owe have y e C(x) but y £ H+(x). Consequently the proof of Proposition 3.1 uses the following lemma. 662 daniel friedman Lemma A.l: For N > 2, let x, y e H(\N) and y eC(x). Then x y > 0 Mrtfow x =y = O^. Proof: Define ~ max{|x, |: i = 1,..., A?}—the "sup norm," and set !/ = Uefi"; \\x\\ = 1} —the unit vectors. Let d = (1,2,..., AO and Z ~ C(v) n H(lN) n I/. Inspection of the extreme points of Z discloses that inf{xy: x, y eZ) is achieved for x and y at the "diagonally opposite corners," viz, = (-1,——) and y*=[--— \ AT- 1 N-l) \ Af — 1 1 ,1^ N-l But 2 AT-2 N x*-y* =---~ =-7>0. A7-! (Af-1)2 (AT-l)2 Note that for any x si?", the cone C(x) is isometric to C(v) (possibly with N replaced by n \\x\\-\\y\\N/(N- 1)2>0. If * = On then C(x) = {«1^: «eR') so y = ec\N for a such that 0 = \N-y = ffljv • 1/v = «N> i-e., a = 0 and y = Ow. Since y e C(x) iff x e C(y), we also conclude that y = Ojy implies x = O^. Hence either * = Ow and x = y = O^, or else x # Ojv and x ■ y > 0. Remark A.2: The same conclusion can be established by essentially the same argument when x, y eH(w) n for given iceS* One takes a vc-weighted sup norm (that is, w,\x,\ replaces |jc,|) and replaces x* and y* by appropriate functions of w. Proposition 3.1: For every fitness function f, for every state s in S, and for k= 1,...,K, the order compatible cones Zkc(f, s) for dynamics and Zkp(f, s) for predynamics are subsets of the corresponding weak compatible cones Zkc(f, s) and Zkp( f, s). Proof: If N =1, the state space is a singleton and the cones are all the zero vector. For given N>2, fix /, s, and k. Set y =/*(«) and let i£Zjt(/,s) = C(y)nH(llV)nfi'<,'). If x = On then (by definition of order-cones) it must be the case that y =a\sk; hence x eZkc(f,s). On the other hand, if x # On the lemma implies that x e Hi so again x e Zkc( f, s). This establishes the desired conclusion for dynamic cones. For predynamics cones one repeats the same argument using the extension of the lemma noted in Remark A.2 with w — sk. Q.E.D. Proposition 3.2: Let the dynamic F be weak compatible with the fitness function f. Alternatively, let the predynamic G be weak compatible with f and let F(s) = D(s)G(s). In either case, all Nash equilibria are fixed points and all interior fixed points are Nash equilibria, i.e., NE(f)cFP(F) and NE(f)nS0 = FP(F)nS0. Proof: Let seNE(f) and fix k. By Remark 2.5 a ~ fk(sk, s) = fk(e',s) for all iel(.sk), so fk(s) = ct\sk and consequently Fk(s) = On. Alternatively, if the predynamic G is weak compatible, then the relevant cone is Zkp(f, s) = C(On) n H(sk) = {On}. In either case we conclude that seFP(F). For the last part of the proof, let s e FP(F) n 5°. Then {On} e C(fk(s) n H(\N) for each k by the compatibility condition for F. The properties of order cones noted after their definition now imply fk(s) = y\N for some y e R1. Alternatively if G is compatible, then On = Fk(s) = D(sk)Gk(s) since s eFP(F), and so 0N = Gk(s) since D(sk) is invertible for 5 e 5°. But then fk(s)eC(0N) so again fk(s) = yl^. Thus in either case we have fk(e', s) = y = fk(sk, s) for all i = 1,..., N. Since this is true for each k = 1,..., K, we conclude from Remark 2.5 that s e NE(/). Q.E.D. Proposition 3.3: Let the dynamic F be weak compatible with the fitness function f, or alternatively let F(s) = D(s)G(s) and let G be a predynamic which is weak compatible with f. Then all stable equilibria of F are Nash equilibria, i.e., EE(F) cNE(f). evolutionary games in economics 663 Proof: Let seEEiF). Since seFP(F), the last argument in Proposition 3.2 tells us that fkie', s) = a for all i eIisk) for some a eR1. Suppose /3 — max{fk{e', s): i = 1,... ,N) > a. Then set /' ■■= {i: fkie', s) = p] and / ■■= {/: fkie', s) < 0) d Hsk). Thus C>= {r e 5: fk(e',r) >fk(e', r) V/ e/, V; e/'} is a cone in 5, which (since / is continuous) is an open neighborhood of 5 e S. For r e C n 5° we have Ftkir)> Fkir) for all ie/' and y'e/ so T.l^rrk>0>T.J^Jrk if F is compatible, or alternatively £,^yilhrk) > 0 if G is compatible. Hence T.lt^rrk (or alternatively FI,£;'r') is a positive increasing function of time for all KO) e C n 5°. Since this function is 0 at r = s, it follows that 5 is not stable, i.e. s EE(F). Consequently, the supposition that jS > a is false. We conclude that N f(x,s) = YJ^J(e,,s) R1 by V(r)=±(r-s)-(r - s). Clearly V is minimized (strictly) on 5 at s, so it will follow that s e EE(Lf) if one can show that V < 0 on 5, i.e., that V is a Liapunov function for L, (cf. Hirsch and Smale, Theorem 9.3.1, for instance). Let A ■■= Df(s). Thus, the NK x NK matrix A has entries ^kj = —Jk(e',r) . dry For reS, let ak(r)-= 1N -fk{r)/lN ■ 1N = N~lLfk(e', r) and let air) ■■= (a\r)lN,..., ak{r)\N) e RNK. Then up to first order for r near s we have f = Lfir) ~Ar — air), and V(r) = (r - s) ■ f ~ (r - s) ■ (Ar - a(r)) = (r - s) ■ Ar = (r - s) ■ A(r - s). The last two equalities use the facts that rk-\N=\=sk-\N (since s and r are in the simplex) and As =ais) (since s eFPiLf) by Proposition 3.1). Since 5 eNEif) the initial hypothesis together with Remark 2.5 tells us that condition (b) of the definition of ESS holds for each k, so rAs = sAs and rAr \: one shows in essence that Vir) = log rk is a Liapunov function under Malthusian dynamics if 5 is an ESS. This establishes part (a) of the Proposition. Note that the Liapunov functions are defined on all of 5° if s e S° n ESSif) and the "first order approximations" in the previous paragraph are exact if / is bilinear. Hence using Theorem 9.3.2 of Hirsch and Smale one can show that there is no other point in EEiMf) or EEiLf) in this case, so (using part (a) of the Proposition) part (b) follows. When N=2 the simplexes Sk are 1-dimensional for each k, so weak and order compatibility coincide. When K = 1 also, the function sip)=pe] +(1 -p)e2 defines an isomorphism between s 664 daniel friedman in S and p in [0,1]. If / is bilinear in this case then it has the matrix representation (al]), i, j = 1,2. Define a = a12 — a22 and b = a2l — and se' P* — a/(.a + b). It is well known that ESS(f) and EE(Mf) are always the same subset Q of {s(p*\ e1, e2}, where Q depends on the signs of a and b as indicated in Figure 6; this result can be easily verified for arbitrary compatible F by direct calculation of the fitness functions at s( p). Suppose finally that / is symmetric and s is a given regular ESS. Now / must be bilinear, so f(s)=As. Since /* is independent of rm for m ¥=k, it must also be independent of sm for m¥=k. Thus A is a symmetric block diagonal matrix. The argument in the first paragraph of this proof establishes that A is negative definite on H(1N)K. For V(r) ■■= - \rAr we have Lf(r) = Lf(r - s) = A(r - s) - a(r - s) = A(r - s) = -gradK(/ -s), i.e., W(r) V(r - s) is a potential function for Lf. Consequently, by Theorem 9.4.3 of Hirsch and Smale, the trajectories of linear dynamics cross the level surfaces of W(r) orthogonally, with W < 0. If F is weak compatible with /, then F(r) -Lf{r) > 0 so W is a Liapunov function for any weak (or, by Proposition 3.1, any order) compatible dynamics F, and therefore 5 e EE(F). Q.E.D. Details for counterexample 2: Figure 7 shows the cones of (admissible and) compatible tangent vectors for / projected on the xl—x2 plane. On the lines Ft( x) = Fj(x) the cone is a single ray; e.g., at the point labelled x we have F3(x) > F2(x) = F^x) since at that point e3Ax > e2Ax = e1Ax. Since T.F = 0 by admissibility, we must have F^x) =_F2(x) = - |F3(x) < 0, giving the indicated ray. Similarly one defines the cones at points such as x on the other lines defined by e'Ax = e'Ax, i # j. Between such lines the cone is an open 2-dimensional cone bounded by the rays defined at the adjacent lines, e.g., at the point labelled y the cone is bounded by the rays obtained from x and x. For x eS, elAx > e2Ax as — 5*! + 34x2 — 29(1 — x, — x2) > —26xl — 5x2 + 31(1— x1— x2) as 13*! + 7x2>20/3, so the line Ft(x) = F2(x) passes through s = (|, j, |) and has slope (after projection into the xl —x2 plane) of —13/7 = —1.86. Similarly, the lines F\(x) — F3(x) and F2{x) = F3(x) also pass through 5 and have slopes 37/50 = 0.74 and 50/43 = 1.16 respectively. Evidently, by always picking tangent vectors close to the outer edge of the cones, one can intersect each of these lines at a point increasingly distant from s, i.e., one can obtain a compatible dynamic F whose trajectories spiral rapidly outwards from s. Specifically, one can choose a partition of unity (see, e.g. Rudin (1966, pg. 40)) subordinate to the cover of 5 consisting of the six open regions bounded by the lines F' = F' together with open epsilon neighborhoods of the lines. This partition of unity can be used to piece together local dynamics which take on the value of Lf at the nearest point on the clockwise boundary line in the regions, and take on the value of Lf at the nearest point on the line in the neighborhoods of the F' — F] lines. For epsilon sufficiently small, such a dynamic will be arbitrarily close to the unstable dynamic whose trajectories have tangents at the outer edge of the cones. REFERENCES Arthur, W. Brian (1989): "A Nash-Discovering Classifier System for Finite-Action Games," Manuscript, Santa Fe Institute. Aubin, Jean-Pierre, and Arrigo Cellina (1984): Differential Inclusions. Berlin: Springer-Verlag. Axelrod, Robert, and Douglas Dion (1988): "The Further Evolution of Cooperation," Science, 242, 1385-1390. Axelrod, Robert, and William D. Hamilton (1981): "The Evolution of Cooperation," Science, 211, 1390-1396. Binmore, Ken (1987 & 1988): "Modeling Rational Players," Parts I and II, Economics and Philosophy, 3, 179-214, and 4, 9-55. evolutionary games in economics 665 Boyd, Robert, and Peter Richerson (1985): Culture and the Evolutionary Process. Chicago: University of Chicago Press. Cornell, Bradford, and Richard Roll (1981): "Strategies for Pairwise Competitions in Markets and Organizations," Bell Journal, 12, 201-213. Conlisk, John (1980): "Costly Optimizers versus Cheap Imitators," Journal of Economic Behavior and Organization, 1, 275-293. Cowen, Tyler, and Randall Kroszner (1987): "The Development of the New Monetary Economics," Journal of Political Economy, 95, 567-590. Crawford, Vincent P. (1989): "An 'Evolutionary' Explanation of Van Huyck, Battalio, and Beil's Experimental Results on Coordination," Manuscript, Department of Economics, University of California, San Diego. Frank, Robert H. (1987): "If Homo Economicus Could Choose His Own Utility Function, Would He Want One with a Conscience?" American Economic Review, 77, 593-604. Friedman, Daniel (1987): "Evolutionary Economic Games," UCSC Working Papers in Applied Economics #156. -(1979): "Money-Mediated Disequilibrium Processes in a Pure Exchange Economy," Journal of Mathematical Economics, 6, 149-167. Friedman, James W., and Robert W. Rosenthal (1986): "A Positive Approach to Non-Cooper- ative Games," Journal of Economic Behavior and Organization, 7, 235-251. Haigh, John (1975): "Game Theory and Evolution," Advances in Applied Probability, 6, 8-11. Hines, W. G. S. (1987): "Evolutionary Stable Strategies: A Review of Basic Theory," Theoretical Population Biology, 31, 195-272. - (1980): "Strategy Stability in Complex Populations," Journal of Applied Probability, 17, 600-611. Hirsch, Morris, and Stephen Smale (1974): Differential Equations, Dynamical Systems, and Linear Algebra. New York: Academic Press. Hirshleifer, Jack (1977): "Economics from a Biological Viewpoint," The Journal of Law and Economics, 20, 1-52. Hirshleifer, Jack, and Juan Carlos Martinez Coll (1988): "What Strategies Can Support the Evolutionary Emergence of Cooperation?" Journal of Conflict Resolution, 32, 367-398. Hofbauer, Josef, and Karl Sigmund (1988): The Theory of Evolution and Dynamical Systems. Cambridge: Cambridge University Press. Holland, J. H. (1980): "Adaptive Algorithms for Discovering and Using General Patterns in Growing Knowledge Bases," International Journal of Policy Analysis and Information Systems, 4, 245-268. Jones, Robert A. (1976): "The Origin and Development of Media of Exchange," Journal of Political Economy, 84, 757-775. Marks, Robert E. (1989): "Niche Strategies: The Prisoner's Dilemma Computer Tournament Revisited," Working Paper 89-009, Australian Graduate School of Management, University of New South Wales. Marimon, Ramon, Ellen McGrattan, and Thomas J. Sargent (1989): "Money as a Medium of Exchange in an Economy with Artificially Intelligent Agents," draft manuscript, Stanford University. Maynard Smith, John (1982): Evolution and the Theory of Games. Cambridge: Cambridge University Press. Masso, Jordi (1988): "Essays on Repeated Games with Continuum Player Sets," Ph.D. Dissertation, Economics Department, SUNY at Stony Brook. Nachbar, John H. (1989): "'Evolutionary' Selection Dynamics in Games: Convergence and Limit Properties," RAND Manuscript, forthcoming in the International Journal of Game Theory. Nelson, Richard R., and Sidney G. Winter (1982): An Evolutionary Theory of Economic Change. Cambridge, Massachusetts: Harvard University Press. Pitchik, Carolyn, and Andrew Schotter (1987): "Honesty in a Model of Strategic Information Transmission," American Economic Review, 77, 1032-1036. Porter, Michael (1980): Competitive Strategy. NY: Free Press. Rappoport, Anatol, and Melvin Guyer (1966): "A Taxonomy of 2 x 2 Games," General Systems, 11, 203-214. Riley, John G. (1979): "Evolutionary Equilibrium Strategies," Journal of Theoretical Biology, 76, 109-123. Rudin, Walter (1966): Real and Complex Analysis. NY: McGraw-Hill. 666 daniel friedman Samuelson, Larry (1987): "Evolutionary Foundations of Solution Concepts for Finite, 2-Player, Normal-Form Games," Manuscript. Samuelson, Paul A. (1948): Foundations of Economic Analysis. Cambridge: Harvard U. Press. Schmeidler, David (1973): "Equilibrium Points of Nonatomic Games," Journal of Statistical Physics, 7, 295-300. Schofield, Norman (1978): "Instability of Simple Dynamic Games," Review of Economic Studies, 45, 575-594. Selten, Reinhard (1980): "A Note on Evolutionary Stable Strategies in Asymmetric Animal Conflicts," Journal of Theoretical Biology, 84, 93-101. Shefrin, H. M. (1981): "Games with Self-Generating Distributions," Review of Economics and Statistics, 48, 511-519. Skyrms, Brian (1986): "Deliberational Equilibria," Topoi, 5, 59-67. Smale, Stephen (1976): "Exchange Processes with Price Adjustment," Journal of Mathematical Economics, 3, 211-226. - (1980): "The Prisoner's Dilemma and Dynamical Systems Associated to Noncooperative Games," Econometrica, 48, 1617-1634. Taylor, Peter D., and Leo B. Jonker (1978): "Evolutionary Stable Strategies and Game Dynamics," Mathematical Biosciences, 40, 145-156. van Damme, Eric (1987): Stability and Perfection of Nash Equilibria. Berlin: Springer-Verlag. Weitzman, Martin (1984): The Share Economy. Cambridge: Harvard University Press. Zeeman, E. Christopher (1979): "Population Dynamics from Game Theory," Proceedings of the International Conference on the Global Theory of Dynamical Systems, Northwestern University, Evanston.