Rational versus Evolutionary Dynamics for Games

Josef Hofbauer

The two prime examples of deterministic dynamic approaches to strategic games are the best response dynamics (BR), in the spirit of the rational approach, and the replicator equation (RE) from evolutionary game theory.

The best response dynamics.

ẋ = BR(x) − x  (BR)

was introduced by Gilboa and Matsui (1991).^{1}

Interpretation: In an infinite population of players, in each small time interval, a small fraction of players revises their strategies and changes to the present best choice. It is the prototype of modeling rational (but myopic) behaviour.

(BR) is the continuous time version of the classical Cournot best response or tâtonnement process. It is closely related to the fictitious play process introduced by Brown (1951). Since BR(x) will be multivalued for some x, a mathematical treatment is best done within the framework of differential inclusions. Since the best response correspondence x ↦ BR(x) is upper–semicontinuous, closed and convex, the existence of at least one solution through each initial value, defined for all positive times, is guaranteed. Furthermore, for 2 person games, piecewise linear paths can be explicitly constructed. See Hofbauer (1994) for details, and some results on the relation between fictitious play and (BR), e.g. the global attractor for (BR) contains also all limit points of FP paths.

The replicator equation.

ẋ_{i} = x_{i} (e_{i}·Ax − x·Ax)  (RE)

was introduced by Taylor and Jonker (1978) as dynamics for the evolutionary games of Maynard Smith, see Hofbauer and Sigmund (1988) for a survey of their dynamics (for 2 person games), and Weibull (1995) for extensions to n person games.

Interpretation: In an infinite population of replicating players, the growth rate of the frequencies of pure strategies is linearly related to their payoffs.

Its relevance for economics is clear since Weibull (1995) showed that it is the simplest imitation dynamics. (RE) arises in particular from the ‘proportional imitation rule’ of

Institut für Mathematik, Universität Wien, Strudlhofgasse 4, A-1090 Vienna, Austria.

Email: a8131dam @ vm.univie.ac.at This is a summary of a talk presented at the Dynamic Evolutionary Game Theory in Biology and Economics meeting, August 1995 in Waterloo and Guelph. The Conference Report is available from R. Cressman, Wilfrid Laurier University .

1BR(x) denotes the set of all pure and mixed best responses to the strategy profile x.

JOSEF HOFBAUER

Schlag (1994): ‘Imitate actions that perform better with probability proportional to how much better they perform’. For a dynamic analysis of other imitation rules see Hofbauer (1995).

Despite the different interpretation and the different dynamic character there are amazing similarities in the long run behaviour of these two dynamics, that can be summarized in the following somewhat heuristic principle.

The AR–BR principle. For many games, the long run behaviour (t → ∞) of the time averages \frac{1}{T} ∫_{0}^{T} x(t)dt of the solutions of the replicator equation (the AR–paths) is the same as for the BR paths.

I give some instances of this in the following. Others can be found in Gaunersdorfer and Hofbauer (1994), where we show this for three examples: The rock–scissors–paper game; the 3 person (2 × 2 × 2) game of Jordan (1993); and Shapley’s 3 × 3 bimatrix game. In these three examples the common attractor for (BR) and (AR) is not an equilibrium, but a Shapley polygon.

Stability against Segregation.

B = {b ∈ ∂Δ : (Ab)_{i} = (Ab)_{j} for all i, j ∈ supp(b)}

These are the NE of restricted games, or stationary points of (RE) on the boundary.

w(x) = max { ∑_{b∈B} b·Ab u^{b} : u^{b} ≥ 0, ∑_{b∈B} u^{b} = 1, ∑_{b∈B} bu^{b} = x}

Interpretation: The population in state x is decomposed into subpopulations of size u^{b} which are in states b ∈ B .............. B–segregation of x w(x) is the maximum mean payoff the population x can obtain by such a B–segregation. w(x) is the smallest concave function satisfying w(b) ≥ b·Ab for all b ∈ B.

Theorem. The following 3 conditions are equivalent:

1. There is a vector p ∈ Δ, such that p·Ab > b·Ab holds for all b ∈ B.

2. V (x) = max_{i}(Ax)_{i} − w(x) > 0 for all x ∈ Δ.

3. There exist a unique interior equilibrium x̂ and x̂·Ax̂ > w(x̂).

(x̂ is strictly stable against segregation)

These conditions imply:

• x̂ is reached in finite time by any BR path.

• Every FP path converges to x̂.

• (RE) is permanent, and time averages of interior solutions converge to x̂.

Examples.

1. Evolutionarily stable strategies: p > 0 interior ESS: p·Ab > b·Ab for all b ≠ p. ⇒ global stability of an interior ESS under (BR).

2. The rock scissors paper game

A = ( \begin{matrix}0 & −μ_{2} & λ_{3} \\ λ_{1} & 0 & −μ_{3} \\ −μ_{1} & λ_{2} & 0 \end{matrix} ) (λ_{i} > 0, μ_{i} ≥ 0).

RATIONAL VERSUS EVOLUTIONARY DYNAMICS FOR GAMES

The conditions of the Theorem are satisfied iff λ_{1}λ_{2}λ_{3} > μ_{1}μ_{2}μ_{3} ⇔ x̂·Ax̂ > 0. Then x̂ strictly stable against segregation, and globally stable for (BR) and (RE).

For games, for which the above Theorem does not apply, the following result provides an estimate for the global attractor of (BR).

Segregation Equilibria.

I suggest to call x ∈ Δ a segregation equilibrium, if there exists a B̄–segregation of x = ∑_{b∈B̄} bu^{b} (u^{b} ≥ 0, ∑_{b∈B̄} u^{b} = 1) s.t. p_{ij} = ∑_{b∈B̄} u^{b}b_{i}b_{j} is a correlated equilibrium, as defined by Aumann:

∑_{i,j} a_{ij}p_{ij} ≥ ∑_{i,j} a_{kj}p_{ij} for all k,

⇔ ∑_{b∈B̄} b·Ab u^{b} ≥ e_{k}·Ax for all k.

This means, that no player would object against this segregation.

The set SE of segregation equilibria is a convex set, which contains all NE.

x ∈ SE ⇔ V̄ (x) = max_{i}(Ax)_{i} − w̄(x) ≤ 0.

Result. For every game A, all BR paths (and FP paths) converge to the set SE of segregation equilibria. SE contains the global attractor of the BR dynamics, and all limit points of time averages of interior solutions of (RE).

Conjectures — Open Problems.

1. For generic payoff matrices A, permanence of (RE) is equivalent to global stability of the interior equilibrium under (BR).

2. If a completely mixed, regular equilibrium (p, q) of a bimatrix game is stable for either the FP process, for the BR dynamics, or (RE), then the game is equivalent to a zero sum game.

References

G. W. Brown, Iterative solution of games by fictitious play, In: Activity Analysis of Production and Allocation (T.C. Koopmans, ed), Wiley, New York, 1951, pp. 374–376. A. Gaunersdorfer, J. Hofbauer, Fictitious play, Shapley polygons and the replicator equation, Games Economic Behav. (To appear). I. Gilboa, A. Matsui, Social stability and equilibrium, Econometrica 59 (1991), 859–867. J. Hofbauer, Evolutionary dynamics for bimatrix games: a Hamiltonian system?, J. Math. Biol. (1995). J. Hofbauer, Stability for the best response dynamics, Preprint, Vienna (1994). J. Hofbauer, Imitation dynamics for games, Preprint (1995). J. Hofbauer, K. Sigmund, The Theory of Evolution and Dynamical Systems, Cambridge University Press, 1988. J. S. Jordan, Three problems in learning mixed–strategy Nash equilibria, Games Econ. Behav. 5 (1993), 368–386. J. Maynard Smith, Evolution and the Theory of Games, Cambridge University Press, 1982. K. H. Schlag, Why imitate, and if so, how?, Preprint (1994). L. Shapley, Some topics in two–person games, Ann. Math. Studies 5 (1964), 1–28. P. Taylor, L. Jonker, Evolutionarily stable strategies and game dynamics, Math. Biosciences 40 (1978), 145–156. J. W. Weibull, Evolutionary Game Theory, MIT Press. To appear, 1995.