When 8is sufficiently small, the first term is the smaller of the two, and it is well approximated by the expression 4 page

Proof. We shall in fact prove a slightly sharper version of this result by formulating the sense in which the game must be generic. Given an н-person game G on the finite strategy space X = |~[ X„ let B~^l(Xi) denote the set of all probability mixtures p-i 6 Д-, = П,#1 MXj) s¹¹⁰'¹ that x, is a best reply to We say that G is nondegenerate in best replies
(NDBR) if for every i and every x, e X„ either B~'(x,) is empty or it contains a nonempty subset that is open in the relative topology of Д _,. The set of NDBR games is open and dense in the space R"^|X|, so NDBR is a generic property.

Given a positive integer s, we say that the probability distribution p- _G д, has precision s if sp,(x,) is integer for all x, e X,. We shall denote the set of all such distributions by Д ■. For each subset Y, of X„ let Д*( Y,) denote the set of distributions p; e Д- such that /?,(*,) > 0 implies x, e Y,. For each positive integer s, let BRj(X_,) be the set of pure-strategy best replies by i to some product distribution p., e Д1 ,(X_,) = f],^, A;(X,). Similarly ВЦ (Y_,) denotes the set of all best replies by i to some product distribution € Д1 ,(Y_;).

For each product set Y and player i, define the mapping 0,(Y) = Y, U BRj(Y-j), and let p(Y) = П ft(Y). Similarly for each integer s > 1 let

fif(Y) = Yi U BR*(Y_,) and 0^S(Y) = f] pf(Y).

Clearly, p*(Y) с p(Y) for every product set Y. We claim that if G is NDBR, then 0^S(Y) = 0(Y) for all sufficiently large s. To establish this claim, suppose that x, e Д(У). If x, e Y„ then obviously .v, e Pf(Y). If Xt 6 Pi(Y)-Y„ then В~^г(х,) Ф И, so by hypothesis, the set of distributions p-i = ]-I_;7s, Pi^to which .v, is a best reply contains a nonempty open subset of Д_,. Hence there exists an integer s,(.r,, Y_,) such that дг, is a best reply to some distribution pi, = ^e A^S_,(Y_,) for alls > Y_,). Since

there are n strategy sets, all of which are finite, it follows that there is an integer s(Y) such that p^s(Y) = p(Y) for all s > s(Y). Since the number of product sets Y is finite, it follows that there is an integer s* such that PHY) = p(Y) for all s > s* and all product sets Y, as claimed.

Now consider the process P'" ^{f 0}. We shall show that ifs is large enough and s/m is small enough, the spans of the recurrent classes correspond one to one with the minimal curb sets of G. We begin by choosing s large enough that p^s = p. Then we choose m such that m > s|X|.

Fix a recurrent class E* of P"' ^{s 0}, and choose any h° e Ejt as the initial state. We shall show that the span of Ejt, S(E*), is a minimal curb set. As in the proof of theorem 7.1 above, there is a positive probability of reaching a state h^] in which the most recent s entries involve a repetition of some fixed x* e X. Note that It¹ € E_k, because E_k is a recurrent class. Let p^li^] denote the /-fold iteration of p and consider the nested sequence

!**} с /3((х*}) с 0^,2,({.v*}) с ... с ^({.г')) с

Since X is finite, there exists some point at which this sequence becomes constant, say, 0<"({x')) = 0⁽'⁺¹⁾({x*}) = У*. By construction, У* is a curb set.

Assume that the above sequence is nontrivial, that is, £((x*)) Ф {х*}. (If (f(x*) = {.v*}, then the following argument is not needed.) There is a positive probability that, beginning after the history li\ some x¹ e 0({x*)) - |x*} will be chosen for the next s periods. Call the resulting history lr. Then there is a positive probability that x² e f)({x' |) - (x*. x¹) will be chosen for the next s periods, and so forth. Continuing in this fashion, we eventually obtain a history h^k such that all members of /j(|x*)), including the original X*, appear at least s times. All we need assume is that m is large enough so that the original s repetitions of x* have not been forgotten. This is clearly assured if m > s|X|. Continuing this argument, we see that there is a positive probability of eventually obtaining a history h' in which all members of У* = /^({х*|) appear at least s times within the last s|Y*| periods. In particular, S(/i*) contains У, which by construction is a curb set.

We claim that У* is in fact a minimal curb set. To establish this, let Z* be a minimal curb set contained in Y*, and choose 2* e Z*. Beginning with the history h" already constructed, there is a positive probability that 2* will be chosen for the next s periods. After this, there is a positive probability that only members of /3({z*)) will be chosen, or members of fi⁽²⁾({2*}), or members of ^^(3>(|z*)), and so on. This happens if agents always draw samples from the "new" part of the history that follows It*, which they will do with positive probability.

The sequence /J'*4(2*}) eventually becomes constant with value Z* because Z* is a minimal curb set. Moreover, the part of the history before the s-fold repetition of x* will be forgotten within m periods. Thus there is a positive probability of obtaining a history //** such that S(h**) с Z*. From such a history the process P^{m s0} can never generate a history with members that are not in Z* because Z* is a curb set.

Since the chain of events that led to //" began with a state in Ejt, which is a recurrent class, h" is also in E/t; moreover, every state in E_k is reachable from /1". It follows that У* с S(E_k) с Z*, from which we conclude that Y* = S(Ek) = Z* as claimed.

Conversely, we must show that if Y* is a minimal curb set, then Y* = S(Ek) for some recurrent class E_k of P^{m s0}. Choose an initial his­tory h° that involves only strategies in У*. Starting at li°, the process P" ^s0 generates histories that involve no strategies that lie outside of S(h°), fi(S(//⁰)). fi⁽²⁾(S(h⁰)), and so on. Since Y* is a curb set, all of these strategies must occur in У*. With probability one the process eventu­ally enters a recurrent class, say £;. It follows that S(E_k) с У*. Since у* is a minimal curb set, the earlier part of the argument shows that 5(£_;) = У*. This establishes the one-to-one correspondence between minimal curb sets and the recurrent classes of P^{m s}-°. Theorem 7.2 now follows immediately from theorem 3.1.

remark. If G is degenerate in best replies, the theorem can fail. Con­sider the following example:

In this game, с is a best reply to A, A is a best reply to я, я is a best reply to C, and С is a best reply to c. Hence any curb set that involves one or more of (А. С, я, с) must involve all of them. Hence it must involve b, because b is a best reply to the probability mixture 1/(1 + ,/2) on A and ,/2/(1 + y/2) on C. Hence it must involve B, because В is a best reply to b. However, d is the unique best reply to B, and D is the unique best reply to d. From this it follows that every curb set contains (d, D). Since the latter is a minimal curb set (a strict Nash equilibrium), we conclude that ((d. D)) is the unique minimal curb set. However, {(d. D)) does not correspond to the unique recurrent class under adaptive learning.

To see why, consider any probability mixture (q,\. qn. qc. qD) over col­umn's strategies. It can be checked that strategy b is a best reply (by row) if and only if q_B = 0, q_c = (J2)q_A, q_D = 1 - (1 + s/2)q_A, and в a > 1/(2 + ^2), in which case я and с are also best replies. In this situa­tion at least one of q_A and qc must be an irrational number. In adaptive learning, however, row responds to sample frequencies, which can only be rational numbers. It follows that, when s — 0, row will never choose b as a best reply to sample information no matter how large s is. Thus, with finite samples, the unperturbed process has two recurrent classes: one with span {я. с) ж (А. С), the other with span {(d. D)). Hence theo­rem 7.2 does not hold for this (nongeneric) two person game.

Theorem 9.1. Let G be a two-person pure coordination game, and let p^{m s} * be adaptive play. If s/m is sufficiently small, every stochastically stable state is a convention; moreover, if s is sufficiently large, every such convention is efficient and approximately maximin in the sense that its welfare index is at least (iv⁺ - or)/(l + a), where

a = w~( 1 - (го⁺)²)/(1 + w~)(w⁺ + w~). (A.19)

Proof. Let G be a pure coordination game with diagonal payoffs (a_r bj) > (0,0). 1 < j < K, and off-diagonal payoffs (0, 0). Assume that the payoffs have been normalized so that max, яу = max,b_; = 1. The welfare index of the yth coordination equilibrium is defined to be W; = я, л b,, and a>⁺ = maxy Wj. We also recall that a~ = min |я,:Ьу = 1}, b~ = min [bj-.aj = 1), and w~ = a~ v b~.

Let P' = p"' ^Sf denote adaptive learning with parameters m, s, and e. Theorem 7.1 shows that if s/m is sufficiently small, the only recur­rent classes of the unperturbed process P"^KS-° are the К conventions h\. //2,... Jik corresponding to the К coordination equilibria. From (9.5) we know that for every two conventions lij and hk, the resistance to the transition hj —► hk is

r)_k = \srjk1 where r_jk = aj/ia, + a_k) л b_t/(bj + b_k). (A.20)

It will be convenient to do calculations in terms of the "reduced resis­tances" rjk, which are more or less proportional to the actual resistances when s is large.

Construct a directed graph with К vertices, one for each of the con­ventions [h].li2 Iik). Let the weight on the directed edge hj —> hk

be the reduced resistance rjk. Assume that hj is stochastically stable for some value of s. By theorem 3.1, the stochastic potential computed ac­cording to the resistances is minimized at hj. If s is large enough, the stochastic potential computed according to the reduced resistances rjk must be minimized at hj also, that is, there is a j-tree T, such that ^r(Tj) < r(T) for all rooted trees T. (In general, r(T) denotes the sum of reduced resistances of all directed edges in the set T.) We need to show that this implies

Wj > (w⁺ -«)/(! +ff).

e

Clearly this follows if zvj — zu⁺. Hence we may assume that zv, < iv⁺, that is, j is not a maximin equilibrium. (For brevity we shall refer to the equilibria by their indices.) Without loss of generality, let us suppose that equilibrium 1 is maximin (zvj = zv⁺), j > 2, and in equilibrium / the row players are "worse off" than the column players: Wj = aу < by.

Let /' be an equilibrium with payoffs fly = 1 and bf = b~. Since <ij < zv⁺ < 1, j and f must be distinct. Assume for the moment that /' Ф 1. (Later we shall dispose of the case / = 1, that is, b~ = w⁺.) Without loss of generality, let j' = 2: thus a₂ = 1 and b₂=b'.

Fix a least resistant /-tree Ту. Since j -ф 1.2, there is a unique edge e\. in Ту exiting from vertex 1, and a unique edge e₂- exiting from vertex 2 (see Figure A.6).

Delete the edges e\- and e₂- from Tj and add the edges e_/2 from j to 2 and e₂\ from 2 to 1. This results in a 1-tree T\. (This is also true ifey and e₂■ point toward the same vertex, or if e₂- is the same as e₂\.) We know that r(Tj) < r(Ti), so

Г]. + r₂- < rj2 + r₂i.

Let us eval uate the four reduced resistances in this expression. By (A.20),

* Гуг = А//(А/ + "2) A bj/(bj + b₂) = 0,1(0, + 1) Л bj/(bj + b~).

Since zvj = я_; < bj by hypothesis, it follows that

Г12 = ZVj/(ZVj + 1).

By (A.20), the minimum reduced resistance from 1 to any other vertex is

min [ci\/(ci\ + a_k) л b\/(b_x + b_k)). к

Since 1 is a maximin equilibrium, we have П\, b\ > w⁺. Moreover, a_k, b_k < 1 for all k. Hence

min + a_k) л b\/(b\ + b_k)) > w⁺/(w⁺ + 1).

к

It follows that

rj. > w⁺/(w⁺ + 1). (A.23)

A similar argument shows that

r₂. > b~/(b~ + 1).

Finally, since a_lr b\ > w⁺, we have

r₂i = a₂/(a₂ + <?i) лЬ₂/(Ь₂ + bi) < 1/(1+ w⁺) л b~/(b~ + a>⁺).

and in particular,

r₂\ < b~/{b~ + w⁺). (A.25)

Combining (A.22)-(A.25) yields the inequality

iv⁺ b~ Wj b~

------------ 1--------- <-------- i---- 1------------ .

w⁺ + 1 b~ + 1 ~ Wj + 1 b~ + w+

After some algebraic manipulation, this leads to the equivalent expres­sion

Wj > (w⁺ - a(fr))/(1 + a(b~)).

where a(x) = [x(l - (a>⁺)²)]/[(l +.r)(w⁺ + x)]. It is straightforward to show that a(x) is increasing on the domain {лг: x² < го⁺). In particular, ct(b~) < a(w~) because b~ < w~ < w⁺ < 1, and therefore (b~)², (иг)² <
w⁺. Letting a = a(w~), we therefore obtain

Wj > (w⁺ - or)/(l + or),

which is the inequality claimed in the theorem.

It remains to dispose of the case j' = 1, that is, the maximin equilib­rium has payoffs (1. b~) and w⁺ — b~. Change the tree T, by deleting the edge <?i- and adding the edge ej\. The result is a 1-tree Tj. Now

r_fl = cij/icij + я,) л bj/(bj + &i) = aj/(cij + 1) л bj/(bj + b~).