Sophisticated Imitation in Cyclic Games^{∗}

Josef Hofbauer Department of Mathematics University of Vienna Strudlhofgasse 4, A-1090 Wien, Austria Josef.Hofbauer@univie.ac.at

Karl H. Schlag Economics Department European University Institute

Via dei Roccettini 9, 50016 San Domenico di Fiesole, Italy schlag@iue.it

11 August 2000

Abstract

Individuals belonging to two large populations are repeatedly randomly matched to play a cyclic 2 × 2 game such as Matching Pennies. Between matching rounds, individuals sometimes change their strategy after observing a finite sample of other outcomes within their population. Individuals from the same population follow the same behavioral rule. In the resulting discrete time dynamics the unique Nash equilibrium is unstable. However, for sample sizes greater than one, we present an imitation rule where long run play cycles closely around the equilibrium.

∗We would like to thank Drew Fudenberg, two referees and the associate editor for helpful comments and suggestions on an earlier version of this paper. Financial support from the Deutsche Forschungsgemeinschaft, Sonderforschungsbereich 303 at the University of Bonn and the Austrian FWF, project P10717-MAT is gratefully acknowledged.

Keywords: strictly improving, matching pennies game, replicator dynamics, limit cycle, discretization JEL classification number: C79.

1 Introduction

Evolutionary Game Theory has provided dynamic models of replication, imitation and learning for analyzing change of play in games. The interpretation of a mixed strategy as a polymorphic population state in which each individual chooses a pure strategy is particularly appealing. However, in multi-population models where individuals do not interact with their kin, mixed population states are rarely predicted. This phenomenon first appeared when Selten (1980) showed that Evolutionarily Stable Strategies of truly asymmetric contests cannot be mixed. More recently, focus has shifted away from static concepts and now lies more on analyzing the population dynamics directly. However, none of the multipopulation models based on boundedly rational individual behavior with limited individual information and memory have been able to predict mixed equilibria. In fact, most of them generate the same population dynamics, namely the standard replicator dynamics known from population biology (Björnerstedt and Weibull, 1995; Börgers and Sarin, 1997; Gale et al., 1995; Posch, 1997; Schlag, 1998).

Only models in which individuals have substantial information or memory are known to predict mixed equilibria. Björnerstedt and Weibull (1996) present a model where individuals imitate others but need to know the average payoff of each strategy being played in the population in order to know when to imitate. This generates the adjusted replicator dynamics for which it is known that the mixed equilibrium of Matching Pennies is asymptotically stable (Maynard Smith, 1982, Appendix J). Fictitious play (Brown, 1951) and the continuous best response dynamics (Hofbauer, 1995a) will also predict the mixed equilibrium in Matching Pennies, and more generally in games that are equivalent to zero-sum games. Under fictitious play, individuals remember all previous moves of their opponent, the continuous time best response dynamics models a scenario in which each individual knows the current distribution of pure strategies in the opponent population(s).

The instability of interior equilibria under the more realistic scenarios of information and memory have biased the evolutionary game theory literature to focus on pure strategy equilibria and on set-valued solution concepts (cf. Ritzberger and Weibull, 1995). However these approaches are of little use in Matching Pennies: they either select the empty set or the entire strategy space. One might then come to the conclusion that only individuals with substantial information and/or extensive memory will learn to play a mixed equilibrium. We show that this conclusion is not true; individuals only need to observe two other individuals, to remember own outcome in the previous round and then to update appropriately — imitating others in a sophisticated manner.

We consider discrete time evolutionary dynamics in cyclic 2 × 2 games such as Matching Pennies where it is assumed that individuals play pure strategies. We will analyze the properties of discrete time aggregate monotone dynamics (Samuelson and Zhang, 1992) both in general and specifically when they can be generated from the following micro model. Assume that individuals from two large (i.e., infinite) populations are repeatedly randomly matched to play a two person game such as a cyclic 2×2 game. Some individuals receive the opportunity to change their strategy between rounds. Each of these observes a random sample of the previous play and payoff of n other individuals from the population. n will be called the sample size.

In this micro model, we assume that individuals belonging to the same population use the same behavioral rule. We restrict attention to individual behavior (what to play next) that is only a function of the information in the sample and of the own choice and payoff in the previous round. An example of such a behavioral rule is the sequentially evaluated Proportional Observation Rule (SPOR_{n}, Schlag, 1999). Given this imitation rule, an individual considers each individual in his sample separately, switching to the strategy observed with a probability that is proportional to the observed payoff. This seemingly unintuitive behavior, to ignore own payoff, is uniquely selected by Schlag (1999) who models optimal individual boundedly rational behavior. We review the underlying arguments from a new perspective in the appendix.

We find that when all individuals use SPOR_{n}, then the resulting population dynamics is an aggregate payoff monotone dynamics — a class of evolutonary dynamics closely related to the replicator dynamics. This fact was previously only known for n = 1 and n = 2 (Schlag, 1998, 1999). Interestingly enough, the dynamics generated by SPOR_{n} tends to Maynard Smith’s adjusted replicator dynamics when the sample size n grows to infinity.

Before analyzing these dynamics, which are technically more involved as they are in discrete time, we consider as a benchmark the usual continuous time version which arises in the limit as the fraction of sampling individuals tends to zero. Pollock and Schlag (1999) show that payoff monotonicity (which is considerably more general than aggregate payoff monotonicity) and sample size one induces continuous time dynamics that are — at least for 2×2 games — still very similar to the standard replicator dynamics. This enables them to show that for cyclic 2 × 2 games all solutions are periodic and cycle around the equilibrium, compare also Hofbauer (1995b). In particular, this means that none of the behavioral rules based on a single observation predicts play of the mixed equilibrium.

We find that a particular class of continuous time aggregate monotone dynamics, such as those induced by SPOR_{n} for n ≥ 2, make the mixed equilibrium globally asymptotically stable. The condition for this result is that their scaling factors are strictly decreasing in the current average population payoffs. Thus, SPOR_{n} (n ≥ 2) is the first example of an individual rule that induces a payoff monotone dynamics that predicts play of a mixed equilibrium in the long run. This is not a complete coincidence even though SPOR_{n} was developed for its local performance. Behavioral rules with sample size one selected in (Schlag, 1998) lead to the standard replicator dynamics which has closed orbits in the continuous version. SPOR_{n} is selected in (Schlag, 1999) as it leads to a stronger increase in play of the current best response than under the selected single sample rules, thus pushing the dynamics towards the mixed equilibrium.

It is important to consider the continuous time dynamics only as a benchmark as almost all realistic learning processes take place in discrete time. Hence we return to the discrete time dynamics. For sample size one, we follow Pollock and Schlag (1999) to show that trajectories starting close to, but not in the mixed equilibrium spiral to the border. Our investigation shows that the mixed equilibrium remains unstable under any aggregate payoff monotone dynamic, much in the spirit of Eshel and Akin (1983) and Crawford (1985). However, although the population state is always pushed away from the mixed equilibrium, we find that the discrete time trajectories of those dynamics that lead to play of the mixed equilibrium in continuous time (such as SPOR_{n} for n ≥ 2) will stay close if the fraction γ of individuals updating their play in each round is small.^{1} Consequently, mixed strategy equilibria need not be ruled out as predictors under simple but sophisticated rules of behavior. At the same time we cannot expect the long run population state to be exactly in the mixed Nash equilibrium. While larger sample sizes under SPOR_{n} tend to decrease the distance of long run play from the equilibrium, we show that this distance is bounded away from 0 for any given γ.

Some intuition may be helpful. The condition of aggregate monotonicity induces a specific structure of the linearized dynamics near the equilibrium. Movement within one population only depends on play in the other which causes trajectories to cycle in continuous time and spiral out in discrete time. This instability of the equilibrium under the linearized dynamics cannot be overturned by considering the explicit nonlinear dynamics. However, differences between the linearized and the actual dynamics arise when the state is not close to the equilibrium. These differences depend on the rule used. The trajectories of the discrete time dynamics approximate those of the continuous time dynamics when γ is small. As the continuous time dynamics under SPOR_{n} for n ≥ 2 lead trajectories into the equilibrium, their discrete time dynamics will lead trajectories close to the equilibrium when γ is small. Our calculations reveal that γ ≤ \frac{n−1}{2n} already suffices to lead trajectories under SPOR_{n} away from the boundary.

The paper is organized as follows. Section 2 introduces how payoffs are realized and how individuals can learn. SPOR_{n} is introduced and the associated population dynamics are derived. Section 3 defines cyclic games and introduces aggregate monotone dynamics. While continuous time dynamics are analyzed in Section 4, Section 5 contains the more interesting and relevant discrete time analysis. It is divided into subsections concerned with dynamics close to the boundary and close to the equilibrium before considering the specific dynamics induced by SPOR_{n}. Section 6 contains the conclusion and the appendix contains more details on the foundations of SPOR_{n}.

1In the paper, we allow for different fractions γ_{k} ∈ (0, 1] in each population k, k = 1, 2.

2 Playing and updating

Consider a two person normal form (or bimatrix) game Γ in which player k chooses a pure strategy from S^{k} = {1, …, n_{k}} where the payoff π^{k} (i, j) that player k receives after play (i, j) ∈ S^{1} × S^{2} is contained in a bounded open interval (α^{k}, ω^{k}) . Let Δ (S^{k}) denote the set of mixed strategies of player k and let π^{k} (p, q) = ∑_{i,j} π^{k} (i, j) p_{i}q_{j} denote the expected payoff of player k when player 1 chooses the mixed strategy p ∈ Δ (S^{1}) and player 2 the mixed strategy q ∈ Δ (S^{2}) . e_{r} ∈ Δ (S^{k}) denotes the choice of pure strategy r with probability one.

In the following we describe a model of boundedly rational individuals playing this game. Assume that individuals have fixed roles in the game Γ. They belong to two infinite populations, one corresponding to each player in the game. In a sequence of rounds, individuals from each population are randomly matched to play the game.^{2}

A state (p, q) ∈ Δ (S^{1}) × Δ (S^{2}) describes the proportions of pure strategies used in each population. Thus, the average payoff in population k is equal to π^{k} (p, q) in state (p, q) .

Between rounds, each individual belonging to population k independently receives the opportunity to change or update his play with probability γ_{k}. With probability 1 − γ_{k} he must play the same pure strategy again. We will refer to 1 − γ_{k} as the level of inertia in population k.

An updating individual gathers information by sequentially and independently sampling n individuals from the same population and observes the (pure) strategy used and the payoff obtained in the previous round by each of these individuals (n ∈ ℕ, 0 < γ_{k} ≤ 1, k = 1, 2). Sampling probabilities are modelled as if populations were finite and each individual not yet observed is sampled equally likely. Formally, the probability that an individual from population 1 with the opportunity to update after round t observes an individual who obtained the payoff π^{1} (i, j) is set equal to p_{i}^{t}q_{j}^{t}. The case n = 1 is called single sampling, n = 2 double sampling.

The individual’s decision what to play in the next round as a function of his previous information will be called his behavioral rule. We will restrict attention to simple behavioral rules that only depend on information gathered since the previous round and not on previous information or play nor on the number of the round. For example, a behavioral rule under single sampling can be described as a map

2As the populations are infinite, this means that an individual in population 1 is matched with an individual playing j in population 2 with probability q_{j} in state (p, q).

F : S^{k} × (α^{k}, ω^{k}) × S^{k} × (α^{k}, ω^{k}) → Δ (S^{k})

where F (i, x, j, y)_{r} is the probability of playing strategy r in the next round after playing strategy i and receiving payoff x and observing an individual who used strategy j and obtained payoff y. More generally, a behavioral rule for sample size n is a map

F : S^{k} × (α^{k}, ω^{k}) × (S^{k} × (α^{k}, ω^{k}))^{n} → Δ (S^{k}) .

Throughout we will be concerned with common updating where all individuals belonging to the same population follow the same behavioral rule. In this way, the population dynamics given individual behavior is uniquely described by the change of the state over time, as given by recurrence equations

\begin{aligned}p_{i}^{t+1} & = p_{i}^{t} + γ_{1} · f_{i} (p^{t}, q^{t}) · p_{i}^{t} \\ q_{j}^{t+1} & = q_{j}^{t} + γ_{2} · g_{j} (p^{t}, q^{t}) · q_{j}^{t} \end{aligned}  (1)

for appropriately chosen functions f_{i}, g_{j} : Δ (S^{1}) × Δ (S^{2}) → ℝ (i ∈ S^{1}, j ∈ S^{2}), such that (p^{t}, q^{t}) ↦ (p^{t+1}, q^{t+1}) defines a map from Δ(S^{1}) × Δ(S^{2}) into itself.

2.1 An important example

Consider the following simple algorithm to construct a behavioral rule for general sample sizes n using a single sampling rule F. Apply the rule F in sequence to each individual in the sample, replacing own strategy and payoff by observed strategy and payoff whenever the rule F prescribes to switch strategies. The strategy left with after applying this procedure to each individual in the sample is the strategy to be played in the next round. This generates a behavioral rule for sample size n we will refer to as sequentially evaluating the rule F. In the following we will demonstrate this procedure and the resulting dynamic equations in more detail for the Proportional Observation Rule.

The Proportional Observation Rule F̃ (POR, Schlag, 1999) for an individual in population k is defined by

\begin{aligned}F̃ (i, x, i, y)_{i} & = 1 \\ F̃ (i, x, j, y)_{j} & = \frac{y − α^{k}}{ω^{k} − α^{k}} = 1 − F̃ (i, x, j, y)_{i} , i ≠ j. \end{aligned}

Notice that POR is an imitation rule since it either prescribes to switch to a strategy sampled or not to switch at all. POR specifies to imitate the observed individual with a probability that is proportional to the payoff of the sampled individual and independent of own payoff.

When all individuals use the respective POR the population state changes according to (a discrete version of) the standard replicator dynamics of Taylor (1979) (with step-sizes γ_{k}, see Schlag, 1998):

\begin{aligned}p_{i}^{t+1} & = p_{i}^{t} + \frac{γ_{1}}{ω^{1} − α^{1}} [π^{1} (i, q^{t}) − π^{1} (p^{t}, q^{t})] · p_{i}^{t} \\ q_{j}^{t+1} & = q_{j}^{t} + \frac{γ_{2}}{ω^{2} − α^{2}} [π^{2} (p^{t}, j) − π^{2} (p^{t}, q^{t})] · q_{j}^{t} \end{aligned}  (2)

Next we sequentially evaluate POR to obtain a double sampling rule F̃^{(2)} (which we also will denote by SPOR_{2}) for n = 2. It follows, for i ≠ j and r ≠ j that

F̃^{(2)} (i, x, j, y, j, z)_{j} = \frac{y − α^{k}}{ω^{k} − α^{k}} + \frac{ω^{k} − y}{ω^{k} − α^{k}} \frac{z − α^{k}}{ω^{k} − α^{k}}
F̃^{(2)} (i, x, r, y, j, z)_{j} = \frac{z − α^{k}}{ω^{k} − α^{k}}
F̃^{(2)} (i, x, j, y, r, z)_{j} = \frac{y − α^{k}}{ω^{k} − α^{k}} \frac{ω^{k} − z}{ω^{k} − α^{k}} .

When all individuals use the SPOR_{2} applied to the appropriate payoff range (α^{k}, ω^{k}) then we obtain the population dynamics (see Schlag, 1999)

p_{i}^{t+1} = p_{i}^{t} + \frac{γ_{1}}{ω^{1} − α^{1}} (1 + \frac{ω^{1} − π^{1} (p^{t}, q^{t})}{ω^{1} − α^{1}}) [π^{1} (i, q^{t}) − π^{1} (p^{t}, q^{t})] p_{i}^{t}
q_{j}^{t+1} = q_{j}^{t} + \frac{γ_{2}}{ω^{2} − α^{2}} (1 + \frac{ω^{2} − π^{2} (p^{t}, q^{t})}{ω^{2} − α^{2}}) [π^{2} (p^{t}, j) − π^{2} (p^{t}, q^{t})] q_{j}^{t} .

(3)

When verifying (3), it is helpful to consider switching behavior even when an individual observes someone using the same strategy. Then the additional term

\frac{ω^{1} − π^{1} (p^{t}, q^{t})}{ω^{1} − α^{1}} = ∑_{i∈S^{1}} p_{i}^{t} (1 − \frac{π^{1} (i, q^{t}) − α^{1}}{ω^{1} − α^{1}} )

as compared to the single sampling case (2) is the probability that an individual does not switch after evaluating POR to the first individual in the sample.

For general n, if each individual uses the rule derived by sequentially evaluating POR (which we will call SPOR_{n}) we obtain the following population dynamics

p_{i}^{t+1} − p_{i}^{t} =\frac{γ_{1}}{ω^{1} − α^{1}} [1 + \frac{ω^{1} − π^{1} (p^{t}, q^{t})}{ω^{1} − α^{1}} + ⋯ + (\frac{ω^{1} − π^{1} (p^{t}, q^{t})}{ω^{1} − α^{1}})^{n−1}]
· [π^{1} (i, q^{t}) − π^{1} (p^{t}, q^{t})] · p_{i}^{t}
q_{j}^{t+1} − q_{j}^{t} =\frac{γ_{2}}{ω^{2} − α^{2}} [1 + \frac{ω^{2} − π^{2} (p^{t}, q^{t})}{ω^{2} − α^{2}} + ⋯ + (\frac{ω^{2} − π^{2} (p^{t}, q^{t})}{ω^{2} − α^{2}})^{n−1}]
· [π^{2} (p^{t}, j) − π^{2} (p^{t}, q^{t})] · q_{j}^{t} .

(4)

The population dynamics induced by SPOR_{n} satisfies

π^{1} (p^{t+1}, q^{t}) − π^{1} (p^{t}, q^{t}) = ∑_{i∈S^{1}} (p_{i}^{t+1} − p_{i}^{t}) [π^{1} (i, q^{t}) − π^{1} (p^{t}, q^{t})]

= \frac{γ_{1}}{ω^{1}−α^{1}} [1 + \frac{ω^{1}−π^{1}(p^{t},q^{t})}{ω^{1}−α^{1}} + .. + (\frac{ω^{1}−π^{1}(p^{t},q^{t})}{ω^{1}−α^{1}})^{n−1}]
· ∑_{i∈S^{1}} [π^{1} (i, q^{t}) − π^{1} (p^{t}, q^{t})]^{2} · p_{i}^{t} ≥ 0

where π^{1} (p^{t+1}, q^{t}) > π^{1} (p^{t}, q^{t}) whenever π^{1} (i, q^{t}) > π^{1} (p^{t}, q^{t}) holds for some i with p_{i}^{t} > 0. This property of SPOR_{n} is called strictly improving and is the starting point that leads Schlag (1999) to argue (also from an individual standpoint) that this rule is the best sequentially evaluated single sampling rule for n = 2. In the appendix we rephrase the essential arguments in a new light and add why sampling more is better under this rule (Proposition 6).

In the limit n → ∞, (4) converges to (a discretization of) the so-called adjusted replicator dynamic introduced by Maynard Smith (1982, Appendix J):

p_{i}^{t+1} = p_{i}^{t} + γ_{1} · p_{i}^{t} · \frac{π^{1} (i, q^{t}) − π^{1} (p^{t}, q^{t})}{π^{1} (p^{t}, q^{t}) − α^{1}}
q_{j}^{t+1} = q_{j}^{t} + γ_{2} · q_{j}^{t} · \frac{π^{2} (p^{t}, j) − π^{2} (p^{t}, q^{t})}{π^{2} (p^{t}, q^{t}) − α^{2}} .

(5)

3 Cyclic 2×2 games and aggregate monotonicity

In the remaining sections we restrict attention to cyclic 2 × 2 games. We call the bimatrix game Γ with |S^{1}| = |S^{2}| = 2 a cyclic 2 × 2 game if the four pure states form a best response cycle, or equivalently, if it has a unique Nash equilibrium E = (p̂, q̂) where E is in the interior of Δ (S^{1})×Δ (S^{2}) = [0, 1]^{2}. Examples include the buyer–seller game (Friedman, 1991, see also Pollock and Schlag, 1999), the model by Cressman et al. (1998) of crime deterrence, Dawkins’ battle of the sexes game (see Maynard Smith, 1982, or Hofbauer and Sigmund, 1988) and (generalized) Matching Pennies, the latter given by the following normal form

\begin{aligned}& 1 & 2 \\ 1 & ν, μ & μ, ν \\ 2 & μ, ν & ν, μ \end{aligned}  (6)

where μ ≠ ν and E = ((\frac{1}{2}, \frac{1}{2}) , (\frac{1}{2}, \frac{1}{2})) . Cyclic games are a simple testing ground for whether bounded rational learning rules such as SPOR_{n} can lead large populations (close) to a completely mixed Nash equilibrium.

General discrete time dynamics as given in (1) (not necessarily derived from the sampling scenario in Section 2) are aggregate monotone regular selection dynamics (Samuelson and Zhang, 1992) if there exist strictly positive continuous functions ϕ^{k} such that (1) can be rewritten as:

p_{i}^{t+1} = p_{i}^{t} + γ_{1}p_{i}^{t} [π^{1}(i, q^{t}) − π^{1}(p^{t}, q^{t})] ϕ^{1} (p^{t}, q^{t})
q_{j}^{t+1} = q_{j}^{t} + γ_{2}q_{j}^{t} [π^{2}(p^{t}, j) − π^{2}(p^{t}, q^{t})] ϕ^{2} (p^{t}, q^{t}) .

(7)

The dynamics (4) induced by SPOR_{n} belongs to this class, with the factors ϕ^{k} depending on the state (p, q) only through the average payoffs: ϕ^{k} = Φ^{k} ∘ π^{k} for some functions Φ^{k}. As a benchmark we will also consider the continuous time version of (7) that results, after replacing t + 1 in (7) by t + Δt and setting γ_{1} = γ_{2} = Δt, as the limit Δt → 0, and is given by the system of differential equations

ṗ_{i} = p_{i}(π^{1}(i, q) − π^{1}(p, q))ϕ^{1} (p^{t}, q^{t})
q̇_{j} = q_{j}(π^{2}(p, j) − π^{2}(p, q))ϕ^{2} (p^{t}, q^{t}) .

(8)

The first aggregate monotone dynamics, besides the standard replicator dynamics of Taylor (1979), for which the factors ϕ^{k} are identical 1, was suggested by Maynard Smith (1982, Appendix J), with

ϕ^{k}(p, q) = \frac{1}{C_{k} + π^{k}(p, q)},  (9)

the C_{k} being positive constants (standing for background fitness). However, no convincing derivation has been given for this choice. As seen from (5) in Section 2, this choice arises now from the imitation rule SPOR_{n} in the limit n → ∞.

4 The continuous time limit

It is popular in evolutionary game theory to simplify analysis by taking appropriate limits and transforming discrete dynamics into continuous time dynamics. For us this approach helps understanding the discrete time dynamics in the next section.

It is well known that the trajectories of the continuous time version (8) of the population dynamics (2) for POR ≡ SPOR_{1} form closed orbits around E. Hofbauer (1995b) and Pollock and Schlag (1999) extend this to more general imitation rules with n = 1. Our next result shows that the mixed equilibrium can be the unique predictor when n ≥ 2. This happens for aggregate monotone dynamics (8) where the multipliers are strictly decreasing functions of the average population payoff.

Theorem 1 If ϕ^{k} ≡ Φ^{k}∘π^{k} for some strictly decreasing strictly positive functions Φ^{k}, as under SPOR_{n} for n ≥ 2, or Maynard Smith’s choice (9), then the mixed equilibrium E is globally asymptotically stable for (8).

While the proof is more technical we can provide some intuition behind this result for SPOR_{n}. Trajectories under the continuous best response dynamics converge to E (Brown, 1951, and Hofbauer, 1995a) while SPOR_{1} just barely does not increase best responses enough as it induces the standard replicator dynamics which have closed orbits around E. Proposition 6 in the appendix implies that SPOR_{n} for n ≥ 2 leads in almost all states to a stronger increase of the best response in 2 × 2 games than SPOR_{1}.

Proof. It was shown in Hofbauer and Sigmund (1988, p. 282), that for Maynard Smith’s choice (9), after dividing the vectorfield (8) by the common factor ∏ p_{i} ∏ q_{j} (which has only the effect of a change of time scale), the divergence is negative and hence the flow on int Δ(S^{1}) × Δ(S^{2}) decreases volume. The same calculation actually applies to strictly decreasing multiplier functions Φ^{k}.^{3} For 2 × 2 games this means that the flow of (8) is area decreasing in (0, 1)^{2}. The theorems of Poincaré–Bendixson and Bendixson–Dulac (see Hofbauer and Sigmund, 1988) imply then the global asymptotic stability of the mixed equilibrium E for cyclic 2 × 2 games. □

3Compare also the proof of proposition 5 in Ritzberger and Weibull (1995, p. 1396) for an opposite result for increasing multiplier functions.

5 The discrete time dynamics

Next we consider the discrete time aggregate monotone dynamics (7). Pollock and Schlag (1999) suggest that for n = 1 all orbits (except the equilibrium E) converge to the boundary (for every γ_{k} ∈ (0, 1]), see Proposition 4 below for more details. This implies that most of the time, all individuals in the same population are playing the same pure (non-equilibrium) strategy. Thus, we can only expect predictive power of E if n ≥ 2.

Before going into details we briefly summarize our results. While the Nash equilibrium E remains locally unstable for any aggregate monotone dynamics, we get more positive results for the dynamics (4) induced by SPOR_{n}. The proportion γ_{k} of individuals in each population receiving information plays an important role. For a given sample size n ≥ 2, if too many individuals receive information (i.e., if γ_{k} are too large) then the boundary remains attracting. However, if γ_{k} ≤ \frac{n−1}{2n} then the boundary is repelling in all cyclic 2×2 games and long run play is closer to the equilibrium than under a single sample. For Matching Pennies games we derive the much better correct bound in (19). If γ_{k} is sufficiently small then the long run states form a limit cycle which is close to E. Simulations are added in section 5.3 to exemplify the specific relations. There we observe that a limit cycle is reached whenever the boundary is repelling.

5.1 Behavior near the boundary

In the following we present sufficient conditions for determining the behavior of the dynamics close to the boundary of the square {(p, q) |p_{1} · p_{2} · q_{1} · q_{2} = 0} .

At the corner (e_{i}, e_{j}) we find (e_{r} − e_{i}, 0) to be the eigenvector corresponding to the eigenvalue

λ_{ij→rj} := 1 + γ_{1} [π^{1}(r, j) − π^{1}(i, j)] ϕ^{1}(i, j)  (10)

and (0, e_{l} − e_{j}) the eigenvector corresponding to the eigenvalue

λ_{ij→il} := 1 + γ_{2} [π^{2}(i, l) − π^{2}(i, j)] ϕ^{2}(i, j) .  (11)

Notice that λ_{ij→rj} is the growth rate p_{r}^{t+1}/p_{r}^{t} when almost all individuals in population one play i and the rest play r and all individuals in population two play j. Since payoffs to player k are from the open interval (α^{k}, ω^{k}), the eigenvalues (10, 11) are positive for (4) and (5) and all 0 ≤ γ_{k} ≤ 1.

Consider now a cyclic 2 × 2 bimatrix game as defined in section 3. Assume that the best reply cycle runs clockwise as

\begin{matrix}π^{1} (2, 1) < π^{1} (1, 1) , & π^{2} (1, 1) < π^{2} (1, 2) , \\ π^{1} (1, 2) < π^{1} (2, 2) , & π^{2} (2, 2) < π^{2} (2, 1) . \end{matrix}  (12)

Then the boundary of the unit square is invariant under the dynamics (7) and forms a heteroclinic cycle, i.e., a closed loop of stable/unstable manifolds of saddle points. The stability of this heteroclinic cycle is determined by the quantity

ρ = ρ_{11→12} · ρ_{12→22} · ρ_{22→21} · ρ_{21→11}  (13)

with (β, δ denoting pairs of numbers belonging to {1, 2})

ρ_{β→δ} = \frac{log λ_{β→δ}}{| log λ_{δ→β}|}.  (14)

Note that ρ is the product of logs of ‘outgoing’ eigenvalues divided by the product of logs of ‘incoming’ eigenvalues around the cycle (12). ρ is well-defined since the eigenvalues (10, 11) are different from 1 whenever γ_{k} > 0. The following is a discrete time version of a related result for differential equations, see e.g. Hofbauer and Sigmund (1988, p. 213f).

Lemma 1 If ρ > 1 (resp. ρ < 1) then the boundary of the square is repelling (resp. attracting) for the dynamics (7).

Proposition 1 Assume that the multipliers in the aggregate monotone dynamics (7) depend only on average payoffs, i.e., have the form ϕ^{k} ≡ Φ^{k} ∘ π^{k} and let ψ^{k}(x) := 1/Φ^{k}(x). Suppose that \frac{dψ^{k}(x)}{dx} > γ_{k} holds in the payoff range of player k for k = 1, 2. Then ρ > 1 and the boundary of the square is repelling: There exists δ > 0 such that for each completely mixed initial condition (p^{0}, q^{0}), there exists t_{0} such that p_{i}(t) > δ and q_{i}(t) > δ for i = 1, 2 and t ≥ t_{0}.

This means that each pure strategy will be used with a certain positive probability δ > 0 after time t_{0}.

Proof. We show that ρ_{12→22} > 1, the other three factors in (13) being analogous. Inserting (10) into (14) we obtain

ρ_{12→22} = \frac{log(1 + γ_{1}(π^{1}(2, 2) − π^{1}(1, 2))Φ^{1} (π^{1} (1, 2)))}{| log(1 + γ_{1}(π^{1}(1, 2) − π^{1}(2, 2))Φ^{1} (π^{1} (2, 2)))|}  (15)

Denote a := π^{1}(2, 2)−π^{1}(1, 2) > 0 and b := π^{1}(1, 2). Then the inequality ρ_{12→22} > 1 can be equivalently reformulated as

ρ_{12→22} = \frac{log(1 + γ_{1}aΦ^{1}(b))}{− log(1 − γ_{1}aΦ^{1}(b + a))} > 1
log(1 + γ_{1}aΦ^{1}(b)) > − log(1 − γ_{1}aΦ^{1}(b + a))
(1 + γ_{1}aΦ^{1}(b))(1 − γ_{1}aΦ^{1}(b + a)) > 1  (16)
Φ^{1}(b) − Φ^{1}(b + a) > γ_{1}aΦ^{1}(b)Φ^{1}(b + a)
ψ^{1}(b + a) − ψ^{1}(b) > γ_{1}a

By the mean value theorem, this last inequality holds whenever (ψ^{1})′(x) > γ_{1} for all x in the payoff range. □

A similar calculation shows:

Proposition 2 Under the assumptions of Proposition 1, if \frac{dψ^{k}(x)}{dx} < γ_{k} holds in the payoff range of player k for k = 1, 2 then ρ < 1 and the boundary of the square is locally asymptotically stable.

5.2 Behavior near the interior equilibrium

Linearizing (7) at an interior equilibrium E leads to a matrix of the form I + γJ with I the identity matrix, γ = diag (γ_{1}, γ_{2}), and J the linearization of the corresponding differential equation (8) at E. For 2 × 2 games, (8) can be written (with p = p_{1} and q = q_{1}) as

ṗ =p(1 − p)(π^{1}(1, q) − π^{1}(2, q))ϕ^{1} (p^{t}, q^{t})
q̇ =q(1 − q)(π^{2}(p, 1) − π^{2}(p, 2))ϕ^{2} (p^{t}, q^{t}) .

(17)

Given an interior equilibrium E = (p̂, q̂) of a 2 × 2 game, (17) can be written in the form

ṗ = (q − q̂)c_{1}(p, q) q̇ = (p̂ − p)c_{2}(p, q)  (18)

where the factors c_{i}(p, q) (which are essentially the ϕ^{i}) have constant sign on (0, 1)^{2}. For a cyclic 2 × 2 game (12) both c_{i}(p, q) are positive. From (18) one can

read off the linearization at E, J = (\begin{matrix}0 & c_{1} \\ −c_{2} & 0 \end{matrix}), with c_{i} = c_{i}(p̂, q̂) for short. Hence

the eigenvalues of J are the imaginary numbers ±i\sqrt{c_{1}c_{2}}, showing the oscillatory behavior of the solutions near E. Hence the eigenvalues of the discrete model (7) at E are given by 1 ± i\sqrt{γ_{1}γ_{2}c_{1}c_{2}}. Since their absolute value is larger than 1 we obtain (compare also Eshel and Akin, 1983 and Crawford, 1985):

Proposition 3 E is a spiral repeller for (7) for every choice of the multiplier functions ϕ^{k} and of the step sizes γ_{k} > 0.

We provide some geometric intuition for this result. Aggregate monotonicity causes there to be almost no change of frequencies in population 1 (2) when q_{1} (p_{1}) is near the equilibrium value q̂_{1} (p̂_{1}). This eliminates own population effects, nearby the equilibrium the dynamics in one population are mainly driven by the frequencies in the other population. This causes first order effects (determined by the linearization) of the continuous dynamics near the equilibrium to lead to closed orbits. The discrete dynamics moves tangent to the trajectories of the continuous dynamics, so in each round the first order effect of the dynamics crosses orbits of the continuous dynamics, moving outwards away from the equilibrium. Thus, the first order effects of the discrete dynamics spiral out which carries over to the actual discrete dynamics to yield our result that E is a spiral repeller. In other words, the first order effects of an aggregate monotone dynamics in a cyclic game have the same properties as the dynamics of the standard replicator dynamic: in the continuous version E is neutrally stable, in the discrete version it is a spiral repeller.

The above is a purely local result, however. If the resulting dynamics is aggregate monotone with multipliers Φ^{k} that are decreasing functions, as under SPOR_{n} or the Maynard Smith dynamics (5), we can be say more. Recall the global stability result for the continuous dynamics given in Theorem 1. Using a perturbation argument from numerical dynamics, namely the upper-semicontinuity of an asymptotically stable set, see e.g. Stuart (1994), there is an attractor A(γ) in the discrete time model (7), with strictly decreasing Φ^{k}, which converges to E, as γ = γ_{1} = γ_{2} → 0. In other words, for small γ, the attractor^{4} of (7) is close to the equilibrium E. Furthermore, it follows from the investigation in Hofbauer and Iooss (1984) that for small γ, this attractor A(γ) of (7) is a stable ‘limit cycle’, i.e., a closed invariant curve surrounding the equilibrium (most likely with an irrational rotation–like dynamics on it).

4General theory implies also that the basin of attraction of A(γ) contains most of the state space, e.g. (δ, 1 − δ)^{2} \ E with δ = δ(γ) → 0 as γ → 0. It is very likely that A(γ) attracts all interior orbits except E. However, the technicalities of such a proof are beyond the scope of this paper.

5.3 Application to the SPOR_{n} imitation dynamics

Now we apply the above results to the imitation models SPOR_{n} introduced in section 2. In the case n = 1, i.e., for (2), the multipliers are simply constants ϕ^{k} = (ω^{k} − α^{k})^{−1}. Hence ψ′ = 0 and proposition 2 implies that the boundary is attracting. In fact it is globally attracting:

Proposition 4 For cyclic 2 × 2 game all orbits (except the equilibrium) of the discrete version of the replicator dynamics (2) converge to the boundary (for every γ_{k} ∈ (0, 1]).

Proof. If we incorporate the factors \frac{γ_{k}}{ω^{k}−α^{k}} into the payoff functions π^{k} then the increment of the map (2) is precisely the vector field (8) or (17), with ϕ^{k} ≡ 1, of the standard replicator dynamics. For cyclic 2 × 2 games this has a constant of motion of the form P = p_{1}^{β_{1}}p_{2}^{β_{2}}q_{1}^{β_{3}}q_{2}^{β_{4}} (with β_{i} > 0), see Hofbauer and Sigmund (1988). Since this function P is strictly concave, its tangent vector field (17) points everywhere outwards. Therefore P decreases monotonically along each trajectory of (2) (except E and on the boundary) and tends to 0. This shows that the boundary is a global attractor for (2). □

In the case n = 2, i.e., for the aggregate monotone dynamics (3), the multipliers Φ^{k} are given by Φ^{k}(x) = \frac{1}{ω^{k}−α^{k}} (1 + \frac{ω^{k}−x}{ω^{k}−α^{k}} ) . Hence ψ(x) = \frac{(ω^{k}−α^{k})^{2}}{2ω^{k}−α^{k}−x} and ψ′(x) = \frac{(ω^{k}−α^{k})^{2}}{(2ω^{k}−α^{k}−x)^{2}} . Since ψ is convex, ψ′ attains its minimum and maximum value at the ends of its domain, i.e., α^{k} and ω^{k} resp. Hence \frac{1}{4} < ψ′(x) < 1.

More generally, for finite n ≥ 2, a longer calculation shows \frac{n−1}{2n} < ψ′(x) < 1. In the limiting case n → ∞, for the map (5) we have Φ(x) = (x − α^{k})^{−1},

hence ψ′(x) = 1. Then proposition 1 shows that the boundary is repelling for every γ^{k} < 1.

Summarizing, we obtain the following results for the dynamics (4) resulting under the use of SPOR_{n} for given n:^{5} Theorem 2 1. The Nash equilibrium is unstable for every cyclic 2 × 2 game.

5Under continuous dynamics (8) obtained through taking the limit γ_{1} = γ_{2} → 0, trajectories cycle in closed orbits around E when n = 1 whereas E is globally attracting for n ≥ 2, as we have seen in section 4.

2. For γ_{1} = γ_{2} = 1 the boundary is attracting for every cyclic 2 × 2 game and for every n. The same holds for n = 1 and 0 < γ_{k} ≤ 1.

3. For γ_{k} ≤ \frac{n−1}{2n} the boundary is repelling for every cyclic 2 × 2 game.

4. For any given cyclic 2×2 game, and any n, there is a value γ(n) ∈ (\frac{n−1}{2n}, 1) with γ(n) → 1 as n → ∞ such that for 0 < γ_{k} < γ(n), the boundary is repelling, while for γ(n) < γ_{k} ≤ 1, the boundary is attracting.

5. For 0 < γ_{k} < γ(n), the interior attractor A(n, γ) is a closed, annulus– shaped set, disjoint from E and the boundary. If γ_{k} = γc_{k} (with c_{k} positive constants) then for small γ > 0, this attractor is a smooth closed invariant curve close to E.

6. For a given cyclic 2 × 2 game and given 0 < γ_{1}, γ_{2} < 1, there is a finite n(γ) such that for n ≥ n(γ) the boundary is repelling. The attractors A(n, γ) converge^{6} to the interior attractor A(∞, γ) of (5). Hence, the attractors A(n, γ) are bounded away from E, uniformly in n.

Statements 1–3 were shown above. Statement 4 follows from the monotone dependence of (13, 14, 15) on the step-sizes γ_{k} and the fact that ψ′(x) → 1 as n → ∞ uniformly on each compact subinterval of the open interval (α^{k}, ω^{k}). Statement 5 follows from the discussion at the end of Section 5.2. Statement 6 follows again from the upper semicontinuity of asymptotically stable sets (here A(∞, γ)) and the robustness of the repellors E and the boundary against perturbations (from (5) to (4) with large n).

Following Theorem 2, when γ_{k} < γ (n) then all long run outcomes will be bounded away both from E and from the boundary. General results for the location and the form of this attracting set are not known. Only for sufficiently small γ there are rigorous results: In this case it is a smooth curve surrounding E, and the distance of this ‘limit cycle’ from the equilibrium behaves like a constant (depending on n) times \sqrt{γ}, so it increases faster than linear (see Hofbauer and Iooss (1984) for details). Numerical simulations suggest that the attractor remains a smooth curve for larger values of γ until it merges the boundary heteroclinic cycle. No ‘fat’ annuli have been observed in these simulations. Figure 2 shows the behavior of the distance of these curves from the equilibrium.

6in the sense that every neighbourhood of A(∞, γ) contains A(n, γ) for all large enough n

For a Matching Pennies game (6) with payoffs μ < ν in the interval (α, ω), the critical values γ (n) follow from the calculation in (16):

γ (n) = \frac{ψ_{n}(ν) − ψ_{n}(μ)}{ν − μ} = \frac{1}{ν − μ}[\frac{ν − α}{1 − (\frac{ω−ν}{ω−α})^{n}} − \frac{μ − α}{1 − (\frac{ω−μ}{ω−α})^{n}} ].  (19)

Figure 1 shows a plot of these values γ(n) against n = 1, …, 10 for (μ, ν) = (1, 2) and payoff range (α, ω) = (0, 3). The figure indicates that for n ≥ 2 the range of values γ below the curve (for which there exists a limit cycle) is substantial and quickly grows towards 1.

Figure 2: For Matching Pennies with (μ, ν) = (1, 2) and payoff range (α, ω) = (0, 3) we plot the distance of the attracting limit cycle from the Nash equilibrium (measured on the ray q = \frac{1}{2}, p > \frac{1}{2}) against the step-size γ. In the left diagram we use n = 2, for which the boundary is reached for γ ≈ .4 ^{7} while the right diagram shows the graph for the limit case n = ∞, for which the boundary is reached only at γ = 1.

(schlag1.ps)

Figure 1: The critical value γ (n) as a function of sample size n for Matching Pennies with (μ, ν) = (1, 2) and (α, ω) = (0, 3) .

(schlag3.ps)

Figure 2: Distance of the limit cycle from E as a function of γ in Matching Pennies with (μ, ν) = (1, 2) and (α, ω) = (0, 3); left: n = 2, right: n = ∞.

6 Conclusion

In cyclic 2 × 2 games, there is a basic difference in the long run dynamics of POR≡SPOR_{1} on the one hand and SPOR_{n} for n ≥ 2 on the other hand. The discrete time dynamics resulting from single sampling diverges to the boundary, leading to a strange aperiodic oscillatory behavior, with geometrically increasing sojourn times near the pure states, similar to the behavior of fictitious play in Shapley’s example. In practical terms this would mean that almost surely one of these pure (non-equilibrium) states is reached and the population is stuck there because it is an absorbing state for imitators. It would need some best reply players to get away again.

7This value is taken from numerical simulations, while the precise value follows from (19)

as \frac{9}{20} = 0.45. This discrepancy reflects the extremely quick approach to the boundary: the distance of the limit cycle to the boundary seems to be a flat function (all derivatives 0) at the critical value of γ.

In contrast, if two or more individuals are sampled, and if the γ_{k} are not too large, then the population dynamics runs into a limit cycle repeating behavior in a periodic or quasi-periodic fashion. Moreover, this limit cycle shrinks to the Nash equilibrium when the fractions γ_{k} of individuals receiving information between rounds goes to zero.

In this sense the interior Nash equilibrium (for Matching Pennies like games) can still be justified by evolutionary arguments based on the SPOR_{n} model for n ≥ 2, while it cannot for n = 1.

Differences among the SPOR_{n} for different sample sizes n ≥ 2 are less severe. SPOR_{2} clearly has the advantage that it relies on the least observations and hence can be argued to be least costly. On the other hand, we find that sampling more is better. For interior states where players are not indifferent, current best responses increase stronger in each round under higher sample sizes (see Proposition 6 on the last page of the appendix). Thus, it is very plausible that higher sample sizes should lead long run play closer to the equilibrium. However, there is a limit to what larger sample sizes can achieve as play is uniformly bounded away from the equilibrium for all sample sizes (see Theorem 2 (6) ). An interesting topic for future research is to assume that sampling is costly, that individuals have different sample sizes n and that individuals using SPOR_{n} not only imitate successful strategies but also the associated sample size.

SPOR_{n} is a sophisticated imitation rule. Here, sophistication is in the sense that the probabilities of switching under POR are chosen to ensure the strictly improving condition for SPOR_{n}. Strictly improving requires “nice” behavior in a large variety of environments and one might wonder which alternative behavior selected specifically for a given cyclic game might yield an aggregate monotone dynamics and stabilize the Nash equilibrium too. We cited (Pollock and Schlag 1999) to show that sample sizes larger than one are necessary. Probabilistic strategy selection also remains a necessary ingredient. It is easily verified that deterministic imitation rules such as the popular, simple, and seemingly more intuitive, imitation rules Imitate The Best (Axelrod, 1984) and Imitate Best Average (Ellison and Fudenberg, 1993) do not induce a payoff monotone dynamics (the Nash equilibrium even fails to be a rest point) for almost all cyclic 2 × 2 games. This is due to the insensitivity of these rules to small payoff changes. A similar result also holds when individuals play a best response to a finite sample of previous strategies among their potential opponents. This rule fails to respond sufficiently accurately to the frequencies of strategies played in the opponent population (see Pollock and Schlag, 1999).

Some sophistication on the part of the players is required to lead them away from unreasonable behavior and bring them closer to Nash equilibrium. It may be worth pointing out another case, where sophistication has a stabilizing effect: In biology, (2) and related (discrete time) models are based on the not always realistic assumption of haploid, asexual individuals which reproduce by cloning. Taking account of the genetic structure, namely diploid inheritance, again leads to a stable limit cycle in the games^{8} considered here, see Maynard Smith and Hofbauer (1987), or Hofbauer and Sigmund (1988, p. 312 ff).

Some comments on the feasible set of behavioral rules may be added. Individuals do not remember occurrences prior to the previous round. All individuals belonging to the same population use the same rule. While an investigation of weaker assumptions seems interesting, both of these assumptions are necessary if the dynamics should take the standard form of evolutionary dynamics. These dynamics are autonomous with the state of the process being the vector of frequencies of play Another important assumption is that individuals do not know which round they are in. This generates stationary behavioral rules. If nonstationary rules were to be allowed then it is conceivable that some lead to play of the Nash equilibrium in the long run. We believe that this is true for the nonstationary rule that specifies for round t to use SPOR_{n} (n ≥ 2) with probability 1/t and to keep the previous strategy otherwise.^{9}

Notice that the stabilizing behavior of double (or more) sampling in cyclic 2×2 games also has an important impact on the following “larger” game. Oechssler and Schlag (2000) find for a simple extensive-form game that the backwards induction outcome ceases to be stable under single sampling sophisticated imitation once observations are imperfect. Our analysis can be used to show that stability is recovered under double (or more) sampling.

8Cyclic 2 × 2 games arise in biology as the ‘battle of the sexes’ game introduced by Dawkins as a model of the parental investment conflict, see Maynard Smith (1982).

9General theorems like in Garay and Hofbauer (1997) imply that such a trajectory converges either to E or to the boundary. That the latter does not occur seems rather plausible, but it requires a proof.

Despite our positive results, stability of interior equilibria or even convergence of learning processes should not be generally expected in any game that has a unique equilibrium, even under sufficiently sophisticated learning rules, such as fictitious play or SPOR_{n}, and even with continuous time (Shapley, 1964; Gaunersdorfer and Hofbauer, 1995; Hofbauer and Swinkels, 1995). However, cyclic games such as Matching Pennies are sufficiently simple. Individuals have an incentive to take advantage of cyclic patterns and to invest in more information or in more memory if necessary. Hence, when payoffs in such games are important, then we expect individuals to choose sophisticated behavior that leads to (or approximates behavior of) the Nash equilibrium. To explicitly model evolution of rules in this context is an interesting topic of future research with useful results already contained in (Pollock and Schlag, 1999).

7 References

Axelrod, R. M. (1984): The Evolution of Cooperation. Basic Books, New York.

J. Björnerstedt, and J. Weibull (1996): Nash equilibrium and evolution by imitation. In: The Rational Foundations of Economic Behaviour (K. Arrow and E. Colombatto, eds.). Macmillan.

Börgers, T. and R. Sarin (1997): Learning through reinforcement and replicator dynamics. J. Econ. Theory 77, 1-14.

Brown G. W. (1951): Iterative solution of games by fictitious play. In: Activity Analysis of Production and Allocation (T.C. Koopmans, ed), pp. 374–376. Wiley, New York.

Crawford, V. P. (1985): Learning behavior and mixed-strategy Nash equilibrium. J. Econ. Behavior Organ. 6, 69–78.

Cressman, R., W. G. Morrison and J.-F. Wen (1998): On the evolutionary dynamics of crime, Canadian Journal of Economics 31(5), 1101–1112.

Ellison, G. and D. Fudenberg (1995): Word-of-mouth communication and social learning, Quart. J. Econ. 440, 93-125.

Eshel, I. and E. Akin (1983): Coevolutionary instability of mixed Nash solutions. J. Math. Biology 18, 123–133.

Friedman, D. (1991): Evolutionary games in economics. Econometrica 59, 637–66.

Gale, J., K. G. Binmore, and L. Samuelson (1995): Learning to be imperfect: the Ultimatum Game. Games Econ. Beh. 8, 56–90.

Garay, B. and J. Hofbauer (1997): Chain recurrence and discretization. Bull. Austral. Math. Soc. 55, 63–71.

Gaunersdorfer, A. and J. Hofbauer (1995): Fictitious play, Shapley polygons, and the replicator equation. Games and Economic Behaviour 11, 279–303.

Hofbauer, J. (1995a): Stability for the best response dynamics. Mimeo, University of Vienna.

Hofbauer, J. (1995b): Imitation dynamics for games. Mimeo, University of Vienna.

Hofbauer, J. and G. Iooss (1984): A Hopf bifurcation theorem for difference equations approximating a differential equation. Monatsh. Math. 98, 99-113.

Hofbauer, J. and K. Sigmund (1988): The Theory of Evolution and Dynamical Systems. Cambridge University Press.

Hofbauer, J. and J. Swinkels (1995): A universal Shapley example. Mimeo. Maynard Smith, J. (1982): Evolution and the Theory of Games. Cambridge

University Press.

Maynard Smith, J. and J. Hofbauer (1987): The “battle of the sexes”: a genetic model with limit cycle behavior. Theor. Pop. Biol. 32, 1–14.

Oechssler, J. and K. H. Schlag (2000): Loss of commitment? An evolutionary analysis of Bagwell’s example, International Game Theory Review, to appear.

Pollock, G. and K. H. Schlag (1999): Social roles as an effective learning mechanism. Rationality and Society 11(4), 371–397.

Posch M. (1997): Cycling in a stochastic learning algorithm for normal form games. J. Evolutionary Economics 7, 193–207.

Ritzberger, K. and J. W. Weibull (1995): Evolutionary selection in normalform games. Econometrica 63, 1371–1399.

Samuelson, L. and J. Zhang (1992): Evolutionary stability in asymmetric games. J. Economic Theory 57, 363–391.

Schlag K. H. (1998): Why imitate, and if so, how? A bounded rational approach to multi-armed bandits, J. Economic Theory 78, 130-156.

Schlag K. H. (1999): Which one should I imitate? J. Mathematical Economics 31, 493-522.

Selten R. (1980): A note on evolutionarily stable strategies in asymmetric animal conflicts. J. Theor. Biol. 84, 93-101.

Shapley L. (1964): Some topics in two–person games. Ann. Math. Studies 5, 1–28.

Stuart A. M. (1994): Numerical analysis of dynamical systems. In: Iserles, A. (ed.), Acta Numerica 1994. Cambridge University Press. pp. 467–572

Taylor, P. D. (1979): Evolutionarily stable strategies with two types of players. J. Appl. Prob. 16, 76–83.

Weibull, J. (1995): Evolutionary Game Theory. Cambridge, MA: MIT Press.

A Sophisticated Imitation

In the following we will briefly review the properties of SPOR_{1} and SPOR_{2} in a new light using a domination argument to then argue why SPOR_{n} can be considered the best sequentially evaluated rule.

A.1 Strictly improving behavior

Schlag (1998) develops a theory of optimal behavior for individuals that are boundedly rational in the following sense. Each individual only knows his own strategy set together with the bounded interval containing his payoffs. Whenever an individual changes his choice then he only uses information he has obtained since the previous round.

Various scenarios are introduced to motivate the following selection among behavioral rules. The individual searches for a rule F that, when used by all others in his population, always causes the average payoff in his population to increase over time should the individuals in the other population not change their play. This increase should be strict whenever not all strategies played in population k achieve the same expected payoff. Formally this means (for an individual of population 1) that the induced dynamics satisfy

π^{1} (p^{t+1} (F) , q^{t}) ≥ π^{1} (p^{t}, q^{t}) for all (p^{t}, q^{t}) ∈ Δ (S^{1}) × Δ (S^{2})
where > holds if there exists i  (20)
s.t. π^{1} (i, q^{t}) > π^{1} (p^{t}, q^{t}) and p_{i}^{t} > 0 .

Notice that we wrote p^{t+1} (F) instead of p^{t+1} to emphasize that dynamics in population 1 are driven by the behavioral rule F. Given the individual’s knowledge, the above condition is required for any round t, any state (p^{t}, q^{t}) in round t, and game Γ with strategy sets S^{1} and S^{2} that generates payoffs for player k in (α^{k}, ω^{k}). A behavioral rule for an individual belonging to population 1 with this property is called strictly improving.

When |S^{1}| = 2 then (21) implies that the proportion of individuals in population 1 playing a best response to the population state of the last round always increases.

It is easily shown that rules of the general form presented in Section 2 which are strictly improving are imitating.^{10} Of course, not all imitating rules are strictly improving.

Consider now the population dynamics (4) under SPOR_{n}. Then

π^{1} (p^{t+1}, q^{t}) − π^{1} (p^{t}, q^{t}) = ∑_{i∈S^{1}} (p_{i}^{t+1} − p_{i}^{t}) [π^{1} (i, q^{t}) − π^{1} (p^{t}, q^{t})]

= \frac{γ_{1}}{ω^{1}−α^{1}} [1 + \frac{ω^{1}−π^{1}(p^{t},q^{t})}{ω^{1}−α^{1}} + .. + (\frac{ω^{1}−π^{1}(p^{t},q^{t})}{ω^{1}−α^{1}})^{n−1}]
· ∑_{i∈S^{1}} [π^{1} (i, q^{t}) − π^{1} (p^{t}, q^{t})]^{2} · p_{i}^{t} ≥ 0 .

which leads to the following result (see also Schlag 1998 and 1999 for n = 1, 2).

Proposition 5 SPOR_{n} generates a strictly improving rule for any sample size n.

A.2 A Case for Optimality

As demonstrated above, SPOR_{n} is strictly improving. In the following we will demonstrate the unique properties of SPOR_{n}. While we will be relying on many results obtained in other papers, the presentation below will put these in new light.

10The proof for n = 1, 2 contained in (Schlag, 1999) extends immediately to general sample sizes n.

Consider two behavioral rules F and G for player one. We say that F dominates G if the terms in (20) are always larger under F than under G, with strict inequality in some cases, i.e., if

π^{1} (p^{t+1} (F) , q^{t}) ≥ π^{1} (p^{t+1} (G) , q^{t})

for any feasible payoff distributions in Γ and any state (p^{t}, q^{t}) in round t, and not “≡”. Notice that a strictly improving rule dominates the rule “never switch strategies”. The notion of domination is a very stringent condition and hence only defines a partial order on the set of behavioral rules. In the following we will point out some rules that are best according to dominance in a given set of rules. We will say that F is undominated in the set of rules D if F ∈ D and if there is no rule G ∈ D that dominates F.

The properties of SPOR_{n} for single (Schlag 1998) and double (Schlag 1999) sampling, stated in terms of dominance, are as follows.

(Single sampling) SPOR_{1} ≡POR is undominated among the strictly improving single sampling behavioral rules. Any other single sampling rule with this property^{11} induces the same population adjustment (2) as POR.

(Double sampling) SPOR_{2} is the unique rule that is undominated among the sequentially evaluated rules. SPOR_{2} dominates POR. In fact, in 2 × 2 games, SPOR_{2} is undominated among the double sampling rules that dominate POR. Any other double sampling rule with this property leads to the same population adjustment (3) as SPOR_{2}.

Some notes are in place. The bounded rationality assumptions underlying this model make it natural to restrict attention to simple rules of behavior such as through sequential evaluation of a single sampling rule. Two questions arise.

Why use POR in this construction? The fact that POR prescribes to forget own previous payoff is counterintuitive. However, reformulating the uniqueness statement for double sampling made above, any other single sampling rule either does not generate a strictly improving double sampling rule under sequential evaluation or is dominated by SPOR_{2}. In fact, it turns out to be difficult to generate interesting strictly improving rules through sequential evaluation. In particular, the Proportional Imitation Rule, selected in (Schlag 1998) as the “best” single sampling rule does not generate a strictly improving double sampling rule when it is evaluated sequentially.

11such as the Proportional Imitation Rule and the Proportional Reviewing Rule (Schlag, 1998).

Can alternative, possibly more complicated, methods for constructing a double sampling rule outperform SPOR_{2}? Strictly improving double sampling rules that are not dominated by SPOR_{2} exist (Schlag, 1999). However, such rules do not dominate POR (or any other single sampling rule that is undominated among the strictly improving single sampling rules). Restricting attention to rules that dominate POR reflects the condition that optimal behavior under multiple sampling should outperform optimal behavior under single sampling. In this class, SPOR_{2} performs best.

As for behavioral rules based on sample sizes n > 2 general results on optimality have not been derived. Of course, in want of one procedure that works well for all sample sizes, it is natural to employ SPOR_{n}. Notice that, following (20), SPOR_{n} performs better the larger the sample size. Hence,

Proposition 6 SPOR_{n} dominates SPOR_{m} for all n > m ≥ 1.