Equilibrium Selection via Travelling Waves

Josef Hofbauer

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

Abstract. ‘Spatial games’ in form of reaction–diffusion equations are used to justify the risk–dominant solution for 2×2 games. For more general games, we explore the differences and similarities of our new dominance relation to (generalized) Nash products and the Harsanyi– Selten risk–dominance relation.

1. Introduction

Consider a game with multiple equilibria, say two strict Nash equilibria for simplicity. Suppose, in one part of the world, one of these equilibria has become the standard, while the other part has somehow agreed to use the other equilibrium. This different evolution was made possible by an ‘iron curton’ separating the two parts. Suppose that now the iron curtain falls, and exchange of ideas and migration of players becomes possible. What will happen to the equilibria chosen. Which equilibrium will survive this process? Intuition suggests that the ‘dominant’ equilibrium will drive out the other equilibrium in form of a travelling wave front.

The problem of equilibrium selection is as old as the concept of equilibrium: Already Nash (1950) faced it in his analysis of the bargaining problem and proposed a solution for this class of games. The most prominent and complete theory of equilibrium selection is due to Harsanyi and Selten (1988), who define the concept of risk–dominance based on the tracing procedure.

In this note, I will present a new, dynamic approach to equilibrium selection, modelled after the above story. The dynamic model is deterministic, in terms of reaction diffusion equations. The reaction term in this PDE is one of the standard game dynamics, like replicator equation or best response dynamics, the diffusion part models the migration process. Outside game theory, such RD models with travelling waves appeared first in the seminal works of Fisher (1937) and Kolmogorov et al. (1937). A good introduction to this topic is Fife (1979). For games, such RD models were first considered by Hutson and Vickers (1992), for symmetric 2 × 2 games, as spatial models of evolutionary games. They allow diffusion rates to depend on the strategy, which gives an additional twist to the game. In the present paper, I assume that each strategy and each player is equally able to diffuse (migrate), in order to keep the model as simple as possible, and to introduce no new parameters: Only the normal form of the game should determine the outcome.

This paper was presented at the Conference on Game Theory, Experience, Rationality. Foundations of Social Sciences, Economics and Ethics. In Honor of John C. Harsanyi in Vienna, 12–15 June 1996.

It appeared in the Proceedings of this conference in the Vienna Circle Institute Yearbook 5/1997 (Eds.:

Werner Leinfellner and Eckehart Köhler). Dordrecht-Boston-London: Kluwer; pp. 245–259.

This research was sponsored by the Austrian FWF, Project P10717-MAT.

The present approach to equilibrium selection seems to be unique, being based on deterministic dynamics. All existing dynamic equilibrium selection theories are based on stochastic models, like Kandori et al. (1993), Kandori and Rob (1995), Young (1993), Feinberg (1994). The models closest to the present one are those of Ellison (1993) and Blume (1995), who use a stochastic model of a spatial game (on a discrete lattice).

In section 2, I consider the case of two players (and 2 actions per player) and derive the risk–dominant solution. Section 3 contains some further classes of games, now with n ≥ 3 players. For unanimity games our method turns out to be consistent with Nash’s bargaining theory, while for two person games with incomplete information (which are formally equivalent to n person potential games with linear incentives), we do not quite obtain the ‘generalized Nash property’ proposed by Harsanyi and Selten (1972), see also Selten (1995), but something similar.

2. Two Players

The model. We consider a 2×2 bimatrix game, which we can write in a normalized form

( \begin{matrix}a_{1}, a_{2} & 0, 0 \\ 0, 0 & b_{1}, b_{2} \end{matrix} ) .  (2.1)

For diagonal entries a_{i}, b_{i} > 0 this is a coordination game or unanimity game, which has two strict equilibria A, B and a mixed equilibrium E. Let p_{i} denote the frequency of the B–strategy for the i–th player. The payoffs for the i–th player playing A_{i}, or B_{i}, resp., are given by π_{i}(A_{i}, p_{−i}) = a_{i}(1−p_{−i}) and π_{i}(B_{i}, p_{−i}) = b_{i}p_{−i}, where we denote {i, −i} = {1, 2} as usual. Equating these expressions yields the mixed equilibrium E = (k_{1}, k_{2}) where k_{i} := \frac{a_{−i}}{a_{−i}+b_{−i}}. In these coordinates, we can identify the equilibria A = 0, and B = 1.

Recall the notion of risk-dominance introduced by Harsanyi and Selten (1988, see esp. p. 86). For the game (2.1), A is risk dominant over B, if

a_{1}a_{2} > b_{1}b_{2},  (2.2)

i.e., A has the higher Nash product, or equivalently, if the mixed equilibrium E is closer to B, i.e.,

k_{1} + k_{2} > 1.  (2.3)

Let us consider now two player populations distributed in space (which is assumed one– dimensional for simplicity). Hence p_{i} = p_{i}(x, t) are now functions of space x ∈ IR and time t. Then our model equations read

\frac{∂p_{i}}{∂t} = f_{i}(p) + d\frac{∂^{2}p_{i}}{∂x^{2}} .  (2.4)

The second term on the right hand side of (2.4) models random migration of players at a uniform, strategy– and player–independent rate d > 0, see Fife (1979, ch. 1).^{1}

1To be more precise, consider the densities ρ_{A_{i}}(x, t) and ρ_{B_{i}}(x, t): ∫_{a}^{b} ρ_{A_{i}}(x, t)dx denotes the number

The first term, the reaction term, f(p), models the local interaction of players and the resulting adaptations of their strategy according to their local experience. We will use the best response dynamics, f(p) = BR(p) − p, to model this interaction. This dynamics was introduced by Gilboa and Matsui (1991) and further studied by Hofbauer (1994). It models the situation that a certain proportion of players at each spot x switches to the locally best reply at any time t. For the 2 × 2 game (2.1) this means (with {i, −i} = {1, 2} again)

\begin{aligned}f_{i}(p) & = −p_{i} if p_{−i} < k_{−i} \\ & = 1 − p_{i} if p_{−i} > k_{−i}. \end{aligned}  (2.5)

Other choices for the reaction term would be to take f(p) as the replicator dynamics, i.e.,

f_{i}(p) = p_{i}(1 − p_{i})(−a_{i} + (a_{i} + b_{i})p_{−i}),  (2.6)

or more general selection, imitation, or myopic adjustment dynamics, satisfying

f_{i}(p) < 0 ⇔ π_{i}(A, p_{−i}) > π_{i}(B, p_{−i}).  (2.7)

In the best response dynamics, we have

BR_{i}(p) = 1_{+}(π_{i}(B, p) − π_{i}(A, p)),  (2.8)

where 1_{+} denotes the Heaviside function: 1_{+}(u) = 1 for u > 0, and 1_{+}(u) = 0 for u < 0.

Our choice of the best response dynamics here has two reasons. First, it is probably the most natural dynamics in game theory: It is the simplest dynamics to model rational players, and equilibrium selection theories are traditionally based on assumptions of extreme rationality. In contrast to many other dynamics it depends only on the best reply structure of the game. Second, this choice has a big mathematical advantage: The RD equation (2.4) is piecewise linear, and hence explicitely solvable, in contrast to other choices of the reaction term.^{2}

The travelling wave. Now we look for a travelling wave solution of (2.4), i.e., a solution of the form p(x, t) = P (x−ct). The constant c is called the wave speed. Then the function P (z), i.e., the shape of the wave, has to satisfy the following system of second order ODEs:

d\frac{d^{2}P}{dz^{2}} + c\frac{dP}{dz} + f(P) = 0  (2.9)

This solution should connect the two equilibria A, B, which leads to the ‘boundary conditions’

P (−∞) = 0, P (∞) = 1. (2.10)

Furthermore, we assume that each component P_{i}(z) is a monotonically increasing function of z. At points of discontinuity of f, pieces of P should be glued together in a C^{1} way.

of A_{i} players in the interval [a, b] at time t. It is these densities that satisfy a reaction–diffusion equation of the form (2.4). Then the density of the total i population, ρ_{i}(x, t) = ρ_{A_{i}}(x, t) + ρ_{B_{i}}(x, t), satisfies a diffusion equation \frac{∂ρ_{i}}{∂t} = d \frac{∂^{2}ρ_{i}}{∂x^{2}} , and hence converges under mild assumptions to a spatially constant:

ρ_{i}(x, t) → ρ_{i}, as t → ∞, i.e., each player population is equally spread over the line IR. Then the frequencies p_{i}(x, t) = \frac{ρ_{Bi} (x,t)}{ρ_{i}} satisfy (2.4).

2An extension of the present model and results to the replicator equation will be considered in Hofbauer et al (1997).

Theorem 1. There exists a unique^{3} monotone travelling wave for (2.4) that connects the two strict equilibria, i.e., satisfies (2.9) and (2.10). The wave speed c > 0, if and only if k_{1} + k_{2} > 1, i.e., A risk–dominates B.

Hence, along this special solution of the RDE, the dominating equilibrium (i.e., A, if c > 0, and B, if c < 0) drives out the other equilibrium.

The stability properties of such a ‘bistable wave’ will be discussed in section 4.

If c = 0, then p(x, t) = P (x) is a stationary solution, or a ‘standing wave’. This occurs, iff the equilibria are equally risky.

The proof. The linearized form of (2.9) is

d\frac{d^{2}P}{dz^{2}} + c\frac{dP}{dz} − P = 0  (2.11)

which has the general solution P (z) = Ae^{λz} + Be^{−μz}, where λ > 0 and −μ < 0 are the solutions of the quadratic equation dx^{2} + cx − 1 = 0, i.e.,

λ = \frac{−c + \sqrt{c^{2} + 4d}}{2d} and − μ = \frac{−c − \sqrt{c^{2} + 4d}}{2d}.  (2.12)

It will be convenient to work with λ, μ instead of c, d in the following. Since c = (μ − λ)d we have to show μ > λ in order to get a positive wave speed c > 0.

Near A, i.e., for P_{i} ≤ k_{i}, (2.5), (2.9) and (2.10) imply

P_{i}(z) = A_{i}e^{λz}  (2.13)

Near B, i.e. for P_{i} ≥ k_{i}, (2.5), (2.9) and (2.10) imply

P_{i}(z) = 1 − B_{i}e^{−μz}  (2.14)

In the intermediate region, say P_{1} > k_{1}, P_{2} < k_{2} (w.l.o.g., we assume that the curve P (t) runs through the lower right quarter; otherwise interchange indices 1 and 2, i.e., interchange the players, or reflect the unit square along the main diagonal), we know from (2.5): f_{1}(P) = −P_{1}, and f_{2}(P) = 1 − P_{2} and hence the solutions continue uniquely from the neighboring region as

P_{1}(z) = A_{1}e^{λz}, P_{2}(z) = 1 − B_{2}e^{−μz}  (2.15)

Now one has to fit P_{i} in a C^{1} way at the merging point z_{i}:

\begin{aligned}P_{i}(z_{i}) & = A_{i}e^{λz_{i}} = 1 − B_{i}e^{−μz_{i}} \\ P′_{i}(z_{i}) & = λA_{i}e^{λz_{i}} = μB_{i}e^{−μz_{i}} \end{aligned}  (2.16)

which implies

A_{i} = \frac{μ}{λ + μ}e^{−λz_{i}}, B_{i} = \frac{λ}{λ + μ}e^{μz_{i}}.  (2.17)

3Since (2.9) is autonomous, P (z + z_{0}) is a solution for any fixed z_{0}, if P (z) is a solution of (2.9). By uniqueness, we mean up to this trivial kind of nonuniqueness.

The merging values z_{i} are determined from (2.5) as the values defined by P_{i}(z_{−i}) = k_{i}. They satisfy z_{1} ≥ z_{2} since the curve P (z) runs through the lower right quarter by assumption. This results in the following two equations

P_{1}(z_{2}) = A_{1}e^{λz_{2}} = k_{1}
P_{2}(z_{1}) = 1 − B_{2}e^{−μz_{1}} = k_{2}

Together with (2.17) we obtain

\begin{aligned}\frac{μ}{λ + μ}e^{λ(z_{2}−z_{1})} & = k_{1} \\ \frac{λ}{λ + μ}e^{μ(z_{2}−z_{1})} & = 1 − k_{2} \end{aligned}  (2.18)

Hence

\frac{P_{1}(z_{2})}{1 − P_{2}(z_{1})} = \frac{k_{1}}{1 − k_{2}} = \frac{μe^{μ(z_{1}−z_{2})}}{λe^{λ(z_{1}−z_{2})}} .  (2.19)

Since z_{1} ≥ z_{2} and the function f(r) = re^{rz} is monotonically increasing in r, if z ≥ 0, the expression in (2.19) is larger than 1 if and only if μ > λ, which means c > 0. This shows the desired result for the direction of the travelling wave.^{4}

We are left to prove existence and uniqueness of the wave P (x − ct). (2.18) together with z_{2} < z_{1} implies the estimate

k_{1} < \frac{μ}{λ + μ} < k_{2}.

With the abbreviation q = \frac{μ}{λ+μ}, (2.18) can be simplified to

e^{\frac{λμ}{λ+μ} (z_{1}−z_{2})} = (\frac{q}{k_{1}} )^{q} = (\frac{1 − q}{1 − k_{2}} )^{1−q}

This equation has a unique solution q ∈ (k_{1}, k_{2}) since the left expression is increasing in q ∈ [k_{1}, k_{2}] from 1 upwards, and the right one is decreasing down to 1. Now q determines uniquely μ and λ (since λμ = \frac{1}{d} holds additionally), and z_{1} − z_{2} through (2.18). This determines the wave uniquely (up to translation), and shows also its existence. □

Remark. One could give a simpler proof of Theorem 1 (apart from the existence and uniqueness of the wave), by showing directly, that the dominance relation derived from the direction of the travelling wave satisfies the three axioms of Harsanyi and Selten (1988, p. 86) that characterize risk–dominance for 2×2 games: The first two axioms of invariance with respect to isomorphisms and best reply invariance are trivially satisfied. The third axiom of payoff monotonicity can be shown rather easily with the help of comparison arguments from PDEs.

However, this approach does not help with more complicated games, as there is no general axiomatic approach to equilibrium selection.

4One can get more information about the location of the curve P (z) in the unit square. If this curve runs through the lower right quarter, i.e., stays below E, then the slopes near 0 and 1 satisfy \frac{P_{2}(z)}{P_{1}(z)} = e^{λ(z_{1}−z_{2})} < \frac{k_{2}}{k_{1}} for z < z_{2}, and \frac{1−P_{2}(z)}{1−P_{1}(z)} = e^{μ(z_{2}−z_{1})} > \frac{1−k_{2}}{1−k_{1}} for z > z_{1}. Since z_{2} < z_{1} in this case, this implies k_{1} < k_{2}. Hence, the curve P (z) lies between the main diagonal and the equilibrium E.

3. n ≥ 3 Players

Here I consider some classes of binary, bipolar n–person games, to use the terminology of Selten (1995): Every player has two pure strategies A and B, 0 ≤ p_{i} ≤ 1 are the corresponding frequencies. The pure strategy profiles A and B, corresponding to p = 0 and p = 1, are strict Nash equilibria. The RDE (2.4) is now a system of n equations (i = 1, … n), f_{i}(p) = BR_{i}(p) − p_{i}, with BR_{i}(p) ∈ {0, 1} (or = [0, 1]) denoting the pure (or the set of all mixed) best reply (replies) for player i to a population in state p ∈ [0, 1]^{n}. Since the second order ODEs in (2.9) decouple, the formulas (2.13)–(2.17) hold again for a monotone travelling wave, i.e.,

P_{i}(z) = ϕ(z − z_{i}) (i = 1, …, n),  (3.1)

with

\begin{aligned}ϕ(z) & = \frac{μ}{λ + μ}e^{λz} for z ≤ 0 \\ & = 1 − \frac{λ}{λ + μ}e^{−μz} for z ≥ 0 \end{aligned}  (3.2)

As in (2.19) we obtain the crucial property

P_{i}(z_{j}) + P_{j}(z_{i}) > 1 ⇔ μ > λ ⇔ c > 0  (3.3)

for any two indices i, j.

Note that this holds for all binary bipolar games, whose best reply structure is monotone:

p ≤ q ⟹ BR(p) ≤ BR(q).  (3.4)

The details of the game, i.e., its best reply structure, is only needed to determine the merging values z_{i}: They are determined as the values for which the best response to P (z) switches from A to B, or where BR_{i}(P (z_{i})) is not unique.

Now I turn to some important special classes of games with a ‘simple’ best reply structure. In this section I do not bother to prove existence and uniqueness of the travelling wave, but see section 4. Here I present only some (rather simple) arguments that determine the sign of the wave, in order to demonstrate the power of the method in finding concrete criteria for dominance of equilibria.

3.1. Unanimity games: The Nash property. n–person unanimity games (or pure coordination games) are the direct generalization of the 2–person game (2.1): Each of the n players has two strategies, A, and B. If all players unanimously choose A (resp., B) then player i gets payoff a_{i} > 0 (resp., b_{i} > 0), otherwise, if there is no coordination, payoff is 0 to everybody. Nash’s bargaining theory selects the strategy with the higher ‘Nash product’: If a_{1} ⋯ a_{n} > b_{1} ⋯ b_{n} then strategy A is the preferred outcome over B.

Practically all equilibrium selection theories aim at this so–called ‘Nash property’ which is the direct generalization of (2.2). In particular, the tracing procedure of Harsanyi and Selten (1988, see pp. 213 ff) leads to it. The one proposed here enjoyes it as well.

Theorem 2. In an n–person unanimity game, A drives out B along a monotone travelling wave solution (i.e., c > 0) if and only if A has a larger Nash product than B.

Proof. For unanimity games,

BR_{i}(p) = 0 ⇔ a_{i} ∏_{j≠i}(1 − p_{j}) > b_{i} ∏_{j≠i} p_{j}.  (3.5)

Hence the merging values z_{i} satisfy the equations

a_{i} ∏_{j≠i}(1 − P_{j}(z_{i})) = b_{i} ∏_{j≠i} P_{j}(z_{i}).  (3.6)

Multiplying these n equations, and applying the inequalities 1−P_{j}(z_{i}) < P_{i}(z_{j}) from (3.3), we obtain

∏_{i} a_{i} > ∏_{i} b_{i}.  (3.7)

This completes the proof. □

3.2. Potential games with linear incentives. A binary game has linear incentives (see Selten, 1995), if the difference between the payoffs for the two strategies of a player is a linear function of the probabilities p_{j} of the other players. (Every 2 person game has linear incentives, but not every n–person game.) Hence the set of profiles p ∈ [0, 1]^{n} for which player i is indifferent between his 2 strategies can be expressed in the form

s_{i} = ∑_{j=1}^{n} α_{ij}p_{j},  (3.8)

with α_{ii} = 0. I assume further that

α_{ij} = α_{ji} > 0,  (3.9)

and, w.l.o.g.,

∑_{i,j} α_{ij} = 2.  (3.10)

The symmetry of the ‘interaction matrix’ α_{ij} implies that the game is a ‘potential game’ in the sense of Monderer and Shapley (1996). The positivity of its entries implies the monotonicity of the best reply structure (3.4). The following result is another generalization of Theorem 1 (take n = 2 and α_{12} = α_{21} = 1). The dominance relation generalizes now (2.3) in a natural way.

Theorem 3. In a bipolar binary n–person game satisfying (3.8–10), A drives out B along a monotone travelling wave, if and only if ∑_{i=1}^{n} s_{i} > 1.

Proof. The merging values z_{i} satisfy the equations

s_{i} = ∑_{j=1}^{n} α_{ij}P_{j}(z_{i}).  (3.11)

Hence (3.3) implies in the case c > 0,

S = ∑_{i} s_{i} = ∑_{i,j} α_{ij}P_{j}(z_{i}) > ∑_{i,j} α_{ij}(1 − P_{j}(z_{i})) = 2 − ∑_{i,j} α_{ji}P_{j}(z_{i}) = 2 − S

or S > 1. □

Remark. Potential games allow a simple way for equilibrium selection, see Monderer and Shapley (1996, p.134): Choose the equilibrium that maximizes the potential. For the above class of games, V (p) = \frac{1}{2} ∑_{i,j} α_{ij}p_{i}p_{j} − ∑_{i} s_{i}p_{i} is a potential. V (A) = V (0) = 0 and V (B) = V (1) = \frac{1}{2} ∑_{i,j} α_{ij} − ∑_{i} s_{i} = 1 − ∑_{i} s_{i}, hence V (A) > V (B) iff ∑_{i} s_{i} > 1. Therefore this method of equilibrium selection is consistent with Theorem 3.

The normalization (3.10) allows an interpretation of α_{ij} as the probability for choosing the (unordered) pair {i, j} from all n players. This interpretation leads to

3.3. Two–person unanimity games with incomplete information. As shown in detail in Selten (1995), such games can be reduced to potential n–person games with linear incentives, considered in section 3.2. Such games run as follows: First, out of n given players, two are chosen with above probabilities α_{ij}. (This is the incomplete information part of the game.) The two selected players i, j play a 2 × 2 unanimity game as in section 2, with payoffs a_{i}, b_{i}, and a_{j}, b_{j}, respectively. (The restriction to only two strategies A, B does not reduce generality.) Selten (1995) shows that such games reduce formally to a binary, bipolar potential game with linear incentives, the functions in (3.8) given as

α_{i} \frac{a_{i}}{a_{i} + b_{i}} = ∑ α_{ij}p_{j},  (3.12)

where α_{i} = ∑_{j} α_{ij}. Hence Theorem 3 yields

Theorem 4. Along a monotone travelling wave solution (2.9), (2.10) of (2.4) for a two– person unanimity game with incomplete information, A drives out B if and only if

∑_{i=1}^{n} α_{i} \frac{a_{i}}{a_{i} + b_{i}} > 1.  (3.13)

A more symmetric way to express (3.13) is

∑_{i=1}^{n} α_{i} \frac{a_{i}}{a_{i} + b_{i}} > ∑_{i=1}^{n} α_{i} \frac{b_{i}}{a_{i} + b_{i}} .  (3.14)

In contrast, Selten’s (1995) axiomatic approach^{5} selects strategy A according to a ‘generalized Nash property’, namely

∏_{i} a_{i}^{α_{i}} > ∏_{i} b_{i}^{α_{i}}.  (3.15)

Güth (1992) selects A according to a different generalization of the Nash property, namely iff

∏_{i} a_{i} > ∏_{i} b_{i}.  (3.16)

The generalized Nash product criterion (3.15) which goes back to Harsanyi and Selten (1972) was already criticized by Myerson (1984). He argues that the probabilities α_{ij} should occur as factors of the payoffs instead as exponenents. Our criterion (3.13) seems to heed this point.^{6} I suggest to interpret the condition (3.13) in the following way. It can be rewritten as

5Selten (1995, section 3.3) presents an example for which (3.15) leads to an opposite dominance relationship than the tracing procedure. For this example also (3.13) and (3.15) lead to opposite results.

∑_{i,j=1}^{n} α_{ij} (\frac{a_{i}}{a_{i} + b_{i}} + \frac{a_{j}}{a_{j} + b_{j}} − 1) > 0.  (3.17)

This sum can be interpreted as the expected advantage of A over B in an incomplete information game, since the term in the parenthesis,

\frac{a_{i}}{a_{i} + b_{i}} + \frac{a_{j}}{a_{j} + b_{j}} − 1 = k_{j} + k_{i} − 1 = \frac{a_{i}a_{j} − b_{i}b_{j}}{(a_{i} + b_{i})(a_{j} + b_{j})},

can be considered as a measure for the advantage of A over B in the 2 × 2 coordination game (2.1) between the two players i and j (recall (2.2) and (2.3)).

It may be worth to compare the two different dominance criteria (3.13) and (3.15) in more detail. Consider for simplicity the case of equal probabilities α_{ij} = \frac{2}{n(n−1)}. Then (3.15) and (3.16) depend only on the (unordered) set of the payoffs a_{i} and b_{i} respectively, like in an n person unanimity game from 3.1. In constrast, (3.13) in its equivalent form (3.17) takes care of the pairwise matchings occurring after the sampling of the two players.

To be more specific, consider the special case of n = 3 players, and let the payoffs be just a cyclic permutation:

(a_{1}, a_{2}, a_{3}) = (u, v, w) = (b_{2}, b_{3}, b_{1})  (3.18)

Then generalized Nash products (3.15), (3.16) would consider A and B equally strong, whereas according to (3.13), A drives out B iff

\frac{u}{u + w} + \frac{v}{v + u} + \frac{w}{w + v} > \frac{3}{2},  (3.19)

or equivalently

(u − v)(v − w)(w − u) > 0.  (3.20)

E.g., if u = 0 (or close), then A drives out B if w > v. This makes sense, since if player 3 is discarded from the game then A and B are equally strong, if player 2 is dropped, then B is stronger and if player 1 is dropped then A is stronger. However, the advantage of A over B in the third case exceeds the advantage of B over A in the second case (at least if we measure the advantage as suggested above, and not simply with Nash products).

This example shows another new feature of our dominance relation defined by (3.13): It is — in stark contrast to (3.15) or (3.16) — not transitive. As an example, consider a third strategy C in the above example, whose payoffs complete the cyclic symmetry in (3.18), i.e., (c_{1}, c_{2}, c_{3}) = (v, w, u). Then (3.19) or (3.20) implies that A drives out B, B drives out C, and C drives out A.

Finally, the discrepancy between the different dominance criteria (3.13) and (3.15) disappears, when we compute the optimal solution. Consider the bargaining problem with incomplete information, where the payoffs a_{i}, b_{i} are supposed to satisfy ∑_{i=1}^{n} a_{i} = ∑_{i=1}^{n} b_{i} = 1, i.e., the n players have to agree to a splitting of a certain amount, whose value is normalized to 1.

6I do not know whether (3.13) is compatible with Myerson’s resolution.

Theorem 5. In a bargaining game with incomplete information, described by the matrix (α_{ij}) satisfying (3.9–10), consider the following way of splitting the amount of 1

a_{i} = \frac{α_{i}}{2} .

This solution is optimal in the following two ways:

1. It drives out (in the travelling wave sense (3.13)) every other division b with ∑_{i} b_{i} = 1.

2. It maximizes the generalized Nash product (3.15) of Harsanyi and Selten.

Proof. Both statements are easy applications of Jensen’s inequality. The second is well–known. For the first, use the concavity of the function f(x) = \frac{1}{1+x}:

∑_{i=1}^{n} a_{i} \frac{a_{i}}{a_{i} + b_{i}} = ∑_{i=1}^{n} a_{i} \frac{1}{1 + \frac{b_{i}}{a_{i}}} = ∑_{i=1}^{n} a_{i}f(\frac{b_{i}}{a_{i}}) ≥ f(∑_{i=1}^{n} a_{i} \frac{b_{i}}{a_{i}}) = f(1) = \frac{1}{2}. □

3.4. Symmetric games. Another, particularly simple class are symmetric binary n– person games, which are invariant under interchanging any two players i and j. Here, the diagonal p_{1} = p_{2} = … = p_{n} is invariant, and also the corresponding wave will enjoy this symmetry. Here BR(p) = 0 if s(p) < 0, where s is a certain polynomial of degree (at most) n − 1. If the game is bipolar, then s(0) < 0 < s(1). We further assume that s has a unique zero p̂ in the interval [0, 1]. This corresponds to a symmetric mixed equilibrium of the game.

Theorem 6. For a bipolar binary symmetric games with a unique mixed symmetric equilibrium p̂, A drives out B along the unique symmetric monotone travelling wave if and only if p̂ > \frac{1}{2}.^{7}

Proof. The unique symmetric monotone travelling wave solution takes the form (3.1) or (3.2) (the value of z_{1} is arbitrary, due to translation invariance, see footnote 2). From the glueing value P_{1}(z_{1}) = ϕ(0) = \frac{μ}{μ+λ} = p̂ the claim follows immediately.^{8} □

One can compute the wave speed c explicitely in this case: c = \frac{2p̂−1}{\sqrt{p̂(1−p̂)}} \sqrt{d}.

We remark that for the present class of games our method selects precisely the long– run equilibrium of Kandori et al. (1993) and the resistant–dominant equilibrium of Güth and Kalkofen (1989), while other equilibrium selection methods, like that of Harsanyi and Selten (1988), Güth (1992), or Carlsson and van Damme (1993), lead to different results for n ≥ 3. For this see the illuminating comparison for a prominent example, the stag hunt game, in the latter paper.

Since for such symmetric binary games the reaction dynamics acts on a one dimensional state space, namely the unit interval, we can also easily discuss how a different choice of the reaction term, like (2.6), would change the equilibrium selected. For a scalar equation (2.9), the direction of the bistable travelling wave can be determined from the following criterion, see Fife (1979).

7This condition reminds of the concept of \frac{1}{2} –dominance: A is \frac{1}{2} –dominant if it is a best reply against all mixtures that place weight at least \frac{1}{2} on A. This is a rather robust sufficient (but in general not a necessary) condition for dominance, see Ellison (1995). Also in the cases considered above, it implies dominance along the travelling wave: For unanimity games, \frac{1}{2} –dominance means a_{i} > b_{i} for all i. For potential games (3.8), it means s_{i} > \frac{α_{i}}{2} .

8With other words, Theorem 6 follows immediately from (3.3) again, with i = j = 1.

c > 0 ⇔ ∫_{0}^{1} f(P)dP < 0  (3.22)

The choice f(p) = BR(p) − p leads again to Theorem 6, with a different proof. For the replicator dynamics, one has f(p) = p(1 − p)s(p). For two person games, s has degree one, so s(p) = γ(p − p̂) (with γ > 0), and (3.22) leads to p̂ > \frac{1}{2}, i.e., the same criterion as with the best response dynamics. However for n ≥ 3 players, simple examples show that replicator and best response dynamics lead to different selection criteria: the travelling waves connecting A and B may run in opposite directions!

4. Remarks on existence, uniqueness and stability

For the n ≥ 3 player games I have not considered the problem of existence and uniqueness of the travelling wave. It could be done as for 2 players, but it is more tedious. On the other hand, existence of a monotone travelling wave follows essentially from a general result of Mischaikow and Hutson (1993) and Volpert et al (1994) on bistable waves in reaction diffusion systems whose reaction term generates a monotone flow. This monotonicity assumption holds for all games considered here, see (3.4). The only technical problem is that these authors assume that the reaction term f(p) is sufficiently smooth, while in (2.4), with the best response dynamics, it is discontinuous. A way to overcome this is to approximate the best reply dynamics by smooth dynamics, i.e., approximate 1_{+} in (2.8) by a smooth monotone increasing function. Any of these approximating dynamics has a monotone travelling wave. Together with suitable apriori estimates for the shape and the speed of these waves (which can be found in the above papers) an Ascoli–Arcela type compactness argument will yield the existence of a monotone travelling wave solution also for the discontinuos limiting equation (2.4).

Volpert (1994) show also uniqueness of monotone bistable waves, but again this does not apply directly to our system (2.2). In any case, Theorems 2,3,4,6 above show, that even if there were several monotone travelling waves, they would all have the same direction, i.e., the sign of the wave speed would be the same.

I conclude with some remarks on the stability of the travelling waves. This can be achieved by constructing comparison solutions.^{9} It turns out, that besides the travelling waves satisfying the boundary conditions (2.10), there are other travelling wave solutions that have no direct physical relevance, but are good for comparison results. Instead of (3.1) we consider

P_{i}^{+}(z) = ϕ(z − z_{i}) + ε_{i}e^{λz}  (4.1)

with ϕ given as in (3.2). These are solutions of (2.9), subject to the right choice of the merging values z_{i}. If ε_{i} > 0, (4.1) is a monotone, unbounded wave, which approaches the bounded wave satisfying (2.10) from above in the limit ε_{i} → 0. Also the speed c_{+} of P^{+} (which is smaller than c) approaches the speed c of the bounded travelling wave. Analogously, we obtain travelling waves

9Mischaikow and Hutson (1993, Theorem 7.2) construct sub– and super–solutions from the travelling wave and derive from them the Lyapunov stability of the wave in the uniform topology on IR. However, their construction depends on the continuity of the reaction term f(.), and unfortunately does not work here.

P_{i}^{−}(z) = ϕ(z − z_{i}) − δ_{i}e^{−μz}.  (4.2)

Now any initial function p(x, 0) that can be squeezed between these two, i.e., P^{−}(x−x_{1}) ≤ p(x, 0) ≤ P^{+}(x+x_{2}) for some values x_{1}, x_{2}, in particular any function satisfying p(x, 0) = 0 for x ≤ x_{3}, and p(x, 0) = 1 for x ≥ x_{4}, obeys

P^{−}(x − x_{1} − c_{−}t) ≤ p(x, t) ≤ P^{+}(x + x_{2} − c_{+}t)

for all t > 0 by the monotonicity properties of our RD equations, and hence moves asymptotically with the same speed c as the bounded monotone travelling wave. Hence A drives out B along any such solution, if c > 0. This means, that if initially the dominating equilibrium strategy occupies (or predominates on) one half of the spaceline, then it will take over and invade the other half line with speed c.

This result could be strengthened further, as in Fife (1979, Prop. 4.11): Prevalence of the dominating strategy on a sufficiently large compact interval (instead of a half line as above) is already sufficient for its spread and taking over.*

5. Conclusion

I have proposed a new method for equilibrium selection in strategic games, based on a spatio–temporal model, combining a diffusion (migration) process with a local best reply dynamic. One Nash equilibrium A dominates another, B, if there is a travelling wave solution, along which B is driven out by A, as t → ∞. As demonstrated for a number of examples, one can with rather little effort explicitely compute the dominance relationship. For the basic class of n–person unanimity games, the method is consistent with Nash products and hence with most previous equilibrium selection methods. For other classes of games different criteria emerge.

Admittedly, the method has its limits: First, it seems to work well only for games whose best reply structure enjoys some monotonicity properties. Second, it enables only a pairwise or bilateral comparison of dominance relationship, preferably between strict equilibria.^{10} Hence it does not provide a complete dynamic equilibrium selection theory: In the presence of several candidates of equilibria, with cycles in the dominance relation, I cannot say anything.

References

L. E. Blume, The statistical mechanics of best–response strategy revision, Games and Economic Behav. 11 (1995), 111–145. H. Carlsson, E. van Damme, Equilibrium selection in stag hunt games, Frontiers of Game Theory (K. Binmore, A. Kirman, P. Tani, ed.), MIT Press, 1993, pp. 237–253.

*See J. Hofbauer: The spatially dominant equilibrium of a game. Ann. Operations Research 89 (1999)

233–251.

10An extension to mixed equilibria, that are stable in the best response dynamics, is possible. However such equilibria are rare for asymmetric games.

G. Ellison, Learning, local interaction, and coordination, Econometrica 61 (1993), 1047–1071. G. Ellison, Basins of attraction, long run equilibria, and the speed of step–by–step evolution, Preprint (1995). Y. Feinberg, Evolutionary selection of an equilibrium, Hebrew University Jerusalem (1994). P. Fife, Mathematical Aspects of Reacting and Diffusing Systems, Springer Lecture Notes in Biomathematics 28 (1979). R. A. Fisher, The wave of advance of advantageous genes, Ann. Eugenics 7 (1937), 353–369. I. Gilboa, A. Matsui, Social stability and equilibrium, Econometrica 59 (1991), 859–867. W. Güth, Equilibrium selection by unilateral deviation stability, R. Selten (ed.), Rational Interaction, Essays in Honor of John C. Harsanyi, Berlin: Springer, 1992, pp. 161–189. W. Güth, B. Kalkofen, Unique Solutions for Strategic Games, Springer Lecture Notes in Economics and Mathematical Systems 328 (1989). J. C. Harsanyi, R. Selten, A generalized Nash solution for 2–person bargaining games with incomplete information, Management Science 18 (5), Part II (1972), 80–106. J. C. Harsanyi, R. Selten, A General Theory of Equilibrium Selection in Games, MIT Press, 1988. J. Hofbauer, Stability for the best response dynamics, Preprint, Vienna (1994). J. Hofbauer, V. Hutson, G.T. Vickers, Travelling waves for games in economics and biology., Nonlinear Analysis, Theory, Methods & Applications 30 (1997), 1235–1244. V. C. L. Hutson, G. T. Vickers, Travelling waves and dominance of ESS’s, J. Math. Biology 30 (1992), 457–471. M. Kandori, G. J. Mailath, R. Rob, Learning, mutation and long run equilibria in games, Econometrica 61 (1993), 29–56. M. Kandori, R. Rob, Evolution of equilibria in the long run: A general theory and applications, J. Economic Theory 65 (1995), 383–414. A. N. Kolmogorov, I. G. Petrovskii, N.S. Piskunov, Studies of the diffusion equation, combined with increase in the amount of matter and its applications to a problem in biology, Bul. Moskovskovo Gos. Univ., Mat. Mekh (= Bull. Moscow Univ., Math. Mech.) 1:6 (1937), 1–26. English translation in: V. M. Tikhomirov (Ed.): Selected works of A.N.Kolmogorov, Vol. I, pp. 242–270, Kluwer, Dordrecht, 1991. K. Mischaikow, V. Hutson, Travelling waves for mutualist species, SIAM J. Math. Anal. 24 (1993), 987–1008. D. Monderer, L. Shapley, Potential games, Games Econ. Behav. 14 (1996), 124–143. R. B. Myerson, Two–person bargaining problems with incomplete information, Econometrica 52 (1984), 461–487. J. F. Nash, The bargaining problem, Econometrica 18 (1950), 361–382. R. Selten, An axiomatic theory of a risk dominance measure for bipolar games with linear incentives, Games Economic Behavior 8 (1995), 213–263. A. I. Volpert, V. A. Volpert, V. A. Volpert, Traveling wave solutions of parabolic systems, (Translations of mathematical monographs, vol. 140), American Mathematical Society, Providence, RI, 1994. H. P. Young, The evolution of conventions, Econometrica 61 (1993), 57–84.