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

Appendix

PROOFS OF SELECTED THEOREMS

lemma 3.1 Freidlin and Wentzell, 1984). Let P be an irreducible Markov process defined о i a finite state space Z. The stationary distribution p ofP has the property that the probability of each state z is proportional to the sum of the likelihoods of its z-trees, that is,

p(z) = v(z)/ v(w), where v(z) = ^ P(T). (A.l)

:ceZ TeT_;

PROOF. Let us view the states as vertices of a graph. For any two distinct states z and z' denote the edge directed from z to z' by the ordered pair (z, z'). Fix a particular state z. A z-cycle is a subset С of directed edges such that: (i) С contains a single directed cycle, which involves z, and (ii) for every state w not in the cycle there is a unique directed path in С from w to the cycle. See Figure A.l for an illustration of this concept. Let C_z denote the set of all z-cycles. Recall that a w-tree T is a set of directed edges such that from every vertex w' Ф w there is a unique directed path from w' to w. Observe that every z-cycle С can be written in the form C = TU {(zi>. z)), where T is a w-tree and w ф z. Similarly, every z-cycle can be written in the form С = TU((z, w)), where T is a z-tree and w ф z. We shall exploit these equivalent representations below.

Let P be an irreducible Markov process on Z, where P_:Z' denotes the probability of transiting from z to z' in one period. For any subset S of directed edges, define

P(S)= П

(z.z')eS

For each z e Z let

v(z) = £ P(T).

TeT_t

Note that v(z) > 0 because the process is irreducible. By virtue of the connection between z-cycles and да-trees remarked on above, we have

Figure A.l. Illustration of a z-cycle.

the identities

£ P(C) = Y v(w)P„.

CeC- w.u&z

P(C) = v(z) ( P*

It follows that

J2 V(w)P_m = V(2) ( J2 P-~w)

w-.w^tz \u>:u&z J

We also have the identity

( £ Pzu) =

\w:w^z /

Combining (A.4) and (A.5) we deduce that

Y v(w)^pwz = v(z).

WeZ

In other words, v satisfies the stationarity equation for P. Hence its normalization д does also, so д is the stationary distribution of P. This concludes the proof of lemma 3.1.

Theorem 3.1. Let P' be a regular perturbed Markov process and let p' be the unique stationary distribution of P' for each e > 0. Then lim_f _₀ p^e = p^{) exists, and is a stationary distribution of P°. The stochastically stable states are precisely those states that are contained in the recurrent class(es) of P" having minimum stochastic potential.

proof. Let P^e be a regular, perturbed Markov process defined for all e € [0. £*], and denote the recurrence classes of P° by E], E₂,..., E*.

Construct a graph Г⁰ having vertices 1.2............... K. where the /th vertex

corresponds to the class E_;. Given two vertices 1 < / ф j < K, let r_i; denote the resistance of the least resistant path in Z that begins in E, and ends in Ej. Recall that, for each j, the stochastic potential yj of the class Ej is defined to be the resistance of the least resistant j-tree in Г°. To prove the theorem, we need to show that lim,_₀ p' = p° exists, and that m"(z) > 0 if and only if z 6 E, where j minimizes yj.

We begin by characterizing the stochastically stable classes (and states) in terms of rooted trees whose vertex set is the entire space Z. Since P' is a regular perturbation, for every pair of distinct states z and z' there exists a number r(z, z') such that P£_. converges to at a rate on the order of £^r{z-^{z )}. (See expression 3.12.) We adopt the convention that r(z. z') = oo if P'_zz. is identically zero on the interval [0. e*]. Let Г* be the complete directed graph whose vertex set is Z such that each directed edge (z. z') has weight r(z. z'). Let T' denote the set of all z-trees on Z. Define the function y: Z —> R as follows:

y(z) = min J2 ^r(²'-^z")- (^A-⁷>

Note that, since P' is irreducible for each e > 0, there exists a positive probability path from each vertex z' to the vertex z. Hence there exists at least one z-tree T" for which the sum of the resistances is finite, hence y(z) is finite. We are going to show that the stochastically stable states minimize y(z). Then we shall show that у is constant on each recurrence class Ej, and that its value is —the stochastic potential of class /defined above.

Lemma 3.2. Let P' be a regular perturbed Markov process, and for each e € [0. e*] let p ^f be the unique stationary distribution of P'. Then lim_£^o p^r = p° exists, p° is a stationary distribution of P", and n°(z) > 0 if and only if у achieves its minimum at z.

Proof. For each state 2 e Z let

= £ n Ъ*-

T'eT.* <1'.₂")бТ'

By lemma 3.1, the stationary distribution // is just the normalization of v' that satisfies £ M^f (2) = 1. Let = min- y(2). We are going to show that lim,(2) > 0 if and only if у(2) = у. For each 2-tree Г* e T*, the resistance of T* is

г(Г)= £ r(2',2"). (A.8)

(z^,.z")eT

Given 2 e Z, there exists (by the definition of y) a 2-tree Г* whose resistance equals )/(z). Consider the identity

П = П е-'^Пг- (A.9)

tf.z")eT' (2'.г")бТ*

Since у (2) is finite, it follows from the definition of the resistance function r that

0 < lim < 00 for every (2', 2") 6 T. (A.10)

If 2 does not minimize y, then r(T*) = y(z) > y, and it follows from (A.9) and (A.10) that

Bm."' П ^"=0.

V.neT-

By assumption, r(T) > y(z) > у for every T 6 T*, hence

lim e~*v^e(z) = 0. (A.ll)

Similarly, if г(Г*) = y(z) = y, we obtain

lim e->V(2) > 0. (A.12)

From lemma 3.1 we know that

M^e(z) = e~^fv°(z)/ £e"V(z). (A.13)

zzZ

From (A.11), (A.12), and (A.13) it follows that

lim p^e(z) = 0 if y(z) > y.

e-*0*

and

lim (z) > 0 if v(z) = y.

c-> o*

In particular, we have shown that linv_»₀+ M^f = exists, and that its support is precisely the set of states z that minimize y(z). Since satisfies the equation n^FP^e = ц^е for every s > 0, and by assumption P^r -> P°, we conclude that ц^аР° = In other words, is a stationary distribution of P°. This completes the proof of lemma 3.2.

Since/i° is a sta tionary distribution of Р°,д°(г) = 0 for every transient state z. Thus to find the stochastically stable states, it suffices to compute the function у only on the recurrent states. We claim that in fact у is constant on each recurrence class of P°. To see this, suppose that z is in the recurrence class £_; and let T* be a z-tree on Z with resistance у (2). Let 1/ be some other vertex in E_;. Choose a path of zero resistance from 2 to 1/. The edges of this path, together with the edges of T\ contain a y-tree T' that has the same resistance as T*. From this it follows that у(y) < y(z). A symmetric argument shows that y(y) > y(2). Hence у is constant on Ej.

To establish the theorem, it remains only to show that the value of у on Ej is precisely the stochastic potential у that was defined with respect to the graph Г⁰.

Lemma 3.3. For every recurrence class Ej of P°, у (2) = у, for all z e Ej.

PROOF. Fix a particular state z, in each recurrent class Ej. We shall show first that y(Zj) < yj, and then we shall show the reverse inequality.

Fix a class Ej and a j-tree T, in Г⁰ whose resistance r(T,) equals yj. For every i Ф j, there exists exactly one outgoing edge (i, /') e Tj, and its weight is r,?. Recall that Г* is the complete directed graph with vertex set Z, and the weight on each edge (2,2') is the resistance r(2, z'). Choose a directed path in Г* that begins at 2, and ends at zand that has total resistance r,-,>. Call this path . By construction, <*. is a least resistant path from £, to £,-. For each i Ф j, choose a set of directed edges T* in Г* that form a z,-tree with respect to the subset of vertices £,. (Thus T* contains |E,| - 1 edges.) Since E, is a recurrence class of P°, the resistance of T* equals zero. Finally, for each transient state z £ LIE,, let be a directed path from z to UE, having zero resistance.

Let E be the union of all of the edges in all of the trees T', i ф j, together with all of the edges in the directed paths such that (;', /') e T,, and all of the edges in the directed paths for z UE,. By construction, E contains at least one directed path from every vertex in Z to the fixed vertex Zj. Therefore it contains a subset of edges that form a z_;-tree T* in Г*. The resistance of T is clearly less than or equal to the sum of the resistances of the paths C,*,, so it is less than or equal to r(T_;). Thus y(Zj) < yj = r(Jj) as claimed.

To show that y(Zj) > yj, fix a class E, and a least resistant z,-tree T* among all z,-trees in the graph Г*. Label each of the specially chosen vertices z, by the index "/" of the class E, to which it belongs. These will be called special vertices. A junction in T* is any vertex i/ with at least two incoming edges in T*. If the junction 1/ is not a special vertex, label it "i" if there exists a path of zero resistance from 1/ to E,. (There exists at least one such class because these are the recurrence classes of P°; if there are several such classes choose any one of them as label.) Every labeled vertex is either a special vertex or a junction (or both), and the label identifies a recurrence class to which there is a path of zero resistance from that point. (Since a special vertex is already in a recurrence class, the path of zero resistance in this case is trivial.)

Define the special predecessors of a state z 6 Z to be the special vertices z, that strictly precede z in the fixed tree T* (i.e., such that there is a path from z, to z in Г-) and such that there is no other special vertex z,-- on the path from z, to z. We claim that

If Zj is a special predecessor of the labeled vertex z, then the unique path in the tree from z, to z has resistance at least r_lk, where к is the label of z. (A.14)

Property (АЛ4) clearly holds for the tree T* because any path from the special vertex z, to a vertex labeled "k" can be extended by a zero resistance path to the class £*, so the total path must have resistance at least r_lk. We shall now perform certain operations on the tree T* that preserve property (A.14), and bring it into a form that can be mapped onto a j-tree in F°. We shall do this by successively eliminating all junctions that are not special vertices.

Suppose that T* contains a junction у that is not a special vertex, and

let its label be "k." We distinguish two cases, depending on whether the special vertex zк is or is not a predecessor of t/ in the tree.

Case 1. If 2/t is a predecessor of 1/ (see Figures A.2 and A.3), cut off the subtree consisting of all edges and vertices that precede у (except for the path from z* to у and all of its predecessors) and paste them onto z*.

CASE 2. If zк is not a predecessor of у in the tree (see Figures A.4 and

О <0

Figure А.4. Case 2 surgery: before.

ут О О

Figure А.5. Case 2 surgery: after.

A.5), cut off the subtree consisting of all edges and vertices that precede у and paste them onto the tree at the vertex z*.

After the operation, remove y's label, since it is no longer a junction. Both of the above operations preserve property (A.14) because z* and у had the same label. Each operation reduces by one the number of junctions that are not special vertices. Thus we eventually obtain a z_;- tree T" in which every junction is a special vertex, property (A.14) is satisfied, and Г** has the same resistance as the original tree T*.

Now construct a j-tree T° on the reduced graph Г⁰ as follows. For every two classes /' and /' put the directed edge (i, /') in T° if and only if z, is a special predecessor of z,< in T**. By construction, T° forms a j-tree.

Let be the unique path in T" from z, to z_f. By property (A.14) its resistance is at least r_№. The paths are edge-disjoint because every junction is one of the special vertices. Since T" contains their union, the resistance of T" is at least as large as the resistance of T°, that is,

y(z,) = r(TJ') > Y ^rif = r(T°). </.f)er°

Obviously r(T°) > Yj, since the latter is the resistance of the least resistant j-tree in Г⁰. Thus y(Zj) > yj as claimed. This completes the proof of lemma 3.3, which, together with lemma 3.2 establishes theorem 3.1.

Theorem 6.2. Let С be a symmetric two-person coordination game with payoff matrix

A В

Assume that equilibrium (A, A) is strictly risk dominant, that is, a - d > b-c > 0. Let r* = (b - c)/((a - d) + (b - c)) < 1/2, and let Q be a class of graphs that are (r, k)-close-knit for some fixed r > r* and some fixed к > 1. Given any p e (0.1), there exists a P_p such that for each fixed p > /),„ the p-inertia of the process P^[fi is bounded above for all Г e Q, and in particular it is bounded independently of the number of vertices in Г.

proof. Let Q be as hypothesized in the theorem, and let Г be a graph in Q with vertex set V and edge set £. Choose an r-close-knit set S of size k. Consider the discrete time process in which each player in S updates according to the probability distribution in (6.3) with response rate p > 0, while each player in S = V - S always chooses action В and does not update. States of this restricted process P^{r s}<P will be denoted by y, and states of the unrestricted process P^{r fl} will be denoted by x. Let Es denote the set of restricted states, and S the set of all states.

For every two nonempty subsets of vertices S', S" с V, let E(S'. S") be the set of all undirected edges {/, /) such that i e S' and j e S". Let e(S', S") be the number of such edges. The 2x2 game has the following potential function p:

p(A, A) = a — d p(A, В) = 0 p(B.A) = 0 p(B, B) = b — с

APPENDIX

The corresponding potential function for the spatial game is

I'./leE

(Recall that all edges are assumed to have unit weight.) It is straight­forward to show (using an argument similar to that in section (6.1)) that the stationary distribution n^r-^s-^fi(y) of P^{r S /f} satisfies M^{r S /i}(y) a for all у 6 3s-

Let A_s denote the state in 3_S such that everyone in S chooses action A, and everyone in S chooses action B. We claim that A_s uniquely maximizes p*(y) among all restricted states y. To see this, consider any restricted state у and let S' = {/' e S:y, - B}. Substituting the values of p we obtain

p*(y) = (a- d)e(S -S\S- S') + (b - c)[«?<S\ S') + e(S', S) + e(S. S)]. and

p*(A_s) = (a - d)e(S, S) + (b - c)e(S, S).

It follows that

P*(As) — p*(y) = (a-d)e(S',S)-(b-c)[e(S',S') + e(S',S)l

— (a — d)e(S', S)-(b - c)le(S\ S') + e(S', V) - e(S', S)].

Thus p'(A_s) — p*(y) > 0 if and only if

[(a — d) + (b — c)]e(S\ S) > (b - c)[e(S', V) + e(S\ S')].

The latter holds because by assumption

e(S\ S)/[e(S', V) + e(S', S')] > r* = (b - c)/[(a - d) - (b - c)].

(Note that e(5'. V) + e(S'. S') > 0, because there are no isolated vertices.) Thus у = As uniquely maximizes p'(y) as claimed. It follows that ^r.s.fl _puts arbitrarily high probability on the state A_s whenever fi is sufficiently large.

Now fix p e (0,1). It follows from the preceding discussion that there exists a finite value fi(V. S. p) such that /y^r-^{S /f}(A_s) > 1 - p²/2 for all fi > fi(Г. S, p). Fix such a value fi. Consider the continuous time process P^{r S /f} in which the agents in S update according to independent Poisson processes with unit expectation. Beginning in an initial state y", let the random variable y^r denote the state of this process at time r. As т goes to infinity, the number of transitions of the corresponding finite process P^{r S /(} up to time r also goes to infinity almost surely. Since P^{1 s /f} is irreducible and aperiodic, it follows (see (3.10)) that limr-^ Pr[y^r = A_s] = ii^rsp(As). Since the number of initial states is finite, there is a finite time г(Г. S, p, fi) such that, from any initial state y°,

Vfi > fi(Г. S. p), Vr > г(Г. S, p. fi), Pr[y^r = A_s] > 1 - p².

Observe now that the continuous process P^{1 S /f} and the embedded fi­nite process P^rsp depend on Г and S only through the configuration of internal edges that link vertices of S to other vertices of S, and on the con­figuration of external edges that link vertices of S to vertices outside of S. Since S is of size k, there are a finite number of internal edges and a finite number of ways in which they can be configured. Since S is of size к and r-close-knit, there are a finite number of external edges, and a finite num­ber of ways in which they can be configured vis-^-vis vertices outside of S. Thus for a given r and к there are a finite number of distinct pro­cesses P^r-^S-P up to isomorphism. In particular, we can find fi(r, k. p) and r(r, k, p, fi) such that, among all graphs Г in Q and all r-close-knit subsets S with к vertices, the following holds independently of the initial state:

V/J > fi(r, k, p), Vr > r(r, k, p, fi), Pr[y^r = A_s] > 1 - p². (A.15)

For the remainder of the discussion, we shall fix r, k, and p as in the theorem. Let us also fix fi* > fi(r, k, p) and r* = г(r. k. p. fi*).

Let Г be a graph in Q with m vertices, and let S be an r-close-knit subset in Г of size k. We denote the unrestricted process by P^{r ft}' and the restricted process by P^{r s} f. We may couple these two processes as follows. (For general results on coupled processes see Liggett (1985).) Create two disjoint isomorphic copies of the graph Г, say Г] and Г2, where the /th vertex in П corresponds to the /'th vertex in Г2. We will define a single continuous time process that mimics P^{r /i}' on Г], and mimics P^r-^S-P' on Г₂. For each state x of the unrestricted process P^{r /r}, let q,(A | x) denote the probability that ichooses A when /' updates, given that the current state is x. Similarly, for each state у of the restricted pro­cess P^{r S li}', let q\(A | у) denote the probability that /'chooses A when /' up­dates, given that the current state is y. Note that q\ (A | у) = 0 for all/' e s.

The coupled process operates as follows. The state at time г is a pair (х^г, у^r) where x- is the choice (Л or B) at the /th vertex in П, and y] is the choice (A or В) at the /'th vertex in Г2. Each matched pair of vertices in the two graphs is governed by a Poisson process with unit expectation, and these processes are independent among the /// matched pairs. Thus whenever the /th agent in Г1 updates the /'th agent in Г₂ updates, and vice versa. Let U be a random variable that is distributed uniformly on the interval [0, lj. Suppose that the /'th pair of individuals updates at time r. Draw a value of U at random, and denote it by //. The /'th indi­vidual in Г1 chooses A if // < q,(A | x^r) and chooses В if // > q,(A | x^r). Similarly, the /'th individual in Г₂ chooses A if 1/ < q'_t(A \ y') and chooses В if 1/ > q'{A I y^T).

For every two states x and у on П and Г₂ respectively, write x >_A у if y, = A implies x, = A for all /'. In other words, if A appears at the /'th vertex in у then A appears at the /'th vertex in x. It is evident that x >_/t у implies q_t(A | x) > q'j(A | y) for all /'. Thus, if x >_A у and /' chooses A in the restricted process, then /' chooses A in the unrestricted process. It follows that if x^r >a y^r at some time r, then х^г >a y' at all subsequent times r' > r.

Now let the coupled process begin in the initial state x° on Г[ and y° on Г₂, where xf = yf for all /' e S, and у? = В for all /' € S. Obviously we have x° >_A y" initially, hence we have x^r >_A y' for all r > 0. From (A.15) and the choice of r* we know that

Vr > r*,Pr[y^r = A_s] > 1 -p²,

hence

Vr > r*.Pr[x^r = A_s] > 1 -p².

This holds for every r-close-knit set S in Г. Since every vertex /' is, by hypothesis, contained in such a set, it follows that

Vr > г*. Pr[x,^T = A] > 1 - p².

Letting o?^r be the proportion of individuals in Г1 playing action A at time r, it follows that

Vr > r*,E[a^r] > 1 -p². (A.16)

We claim that this implies

Vr > r*,Pr[a^r > 1 -p] > 1 -p. (A.17)

If this were false, the probability would be greater than p that more than p of the individuals at time r were playing B. But this would imply that E\a'] < 1 ~ P²' contradicting (A.16). Thus (A.17) holds. It follows that the expected waiting time in P^{r p}' until at least 1 -p of the individuals are playing action A is bounded above by r'/O - p). Moreover, once such a state is reached, the probability is at least 1 - p that the process is in such a state at all subsequent times. Since the time r* holds for all graphs Г in the family Q, the p-inertia of the family of processes |P^{r /,}'lreg is bounded as claimed. This concludes the proof of theorem 6.2.

We remark that the assumption of strict risk-dominance in the theorem is important. Suppose, on the contrary, that G is a 2 x 2 coordination game in which both equilibria are weakly risk-dominant, that is, r* = 1/2. Given any graph Г and any subset of vertices S, the number of internal edges in S divided by the sum of degrees of members of S is at most 1/2. Hence the conditions of the theorem cannot be satisfied, because there exists no (r, k)-close-knit graph for any value of к such that r > r*. Suppose, however, that we consider graphs that are exactly (1 /2, fc)-close-knit for some value of k. For example, let Q be the family of graphs that consist of a number of disjoint, complete subgraphs (called cliques), each of size к > 2. These graphs are obviously (1/2, /c)-close- knit, but the theorem fails to hold for this situation. Indeed, at any given time it is likely that about half of the cliques will be playing action A while the other half will be playing action B; moreover, the waiting time until, say, 99% of them are playing action A becomes arbitrarily large as the number of cliques goes to infinity.

Theorem 7.1. Let G be a weakly acyclic n-person game, and let P"'^se be adaptive piny. If s/m is sufficiently small, the unperturbed process P^{m s 0} converges with probability one to a convention from any initial state. If, in addition, e is sufficiently small, the perturbed process puts arbitrarily high probability on the convention(s) that minimize stochastic potential.

Proof. By theorem 3.1, it suffices to show that the recurrent classes of pm.s.o _correSp_oncj _one to one with the conventions whenever s/m is sufficiently small. Consider any initial state h°. There is a positive probability that all n agents in the first period sample from the most recent s entries in h°. There is also a positive probability that for the next s periods, the agents who play always draw precisely these fixed samples. (This assumes that s/m < 1 /2.) Since e = 0, the agents always choose best replies to their samples. Since all best replies have positive probability, there is a positive probability that the same strategy-tuple .v* is played for these s periods. In other words, after s periods have elapsed, the process arrives with positive probability at a state in which the last s entries equal x*. Call this state h^l.

Since G is weakly acyclic, there exists a best-reply path x* = x°. x¹, ..., x^k ending in some strict Nash equilibrium x^k = x**. If s/m is suf­ficiently small, there is a positive probability that, beginning after the history /;', x¹ will be chosen for the next s periods. Then there is a posi­tive probability that x² will be chosen for the next s periods, and so forth. Continuing in this fashion, we eventually obtain a history h^k in which the last s entries consist exclusively of repetitions of x* = x*\ (All of this assumes that s/m < 1 /(к + 1).) From h^k there is a positive probability that in m — s more periods the process reaches a state /;** consisting of m repetitions of x**. Since x" is a strict Nash equilibrium, /i" is a conven­tion, that is, an absorbing state of P"' ^{s 0}. We have therefore proved that there is a positive probability of reaching a convention within a number of periods that is bounded independently of the initial state. It follows that the unperturbed process converges with probability one to a con­vention for any s, provided that s/m is sufficiently small. This proves that the recurrent classes are precisely the conventions, and theorem 7.1 follows at once from theorem 3.1.

Theorem 7.2. Let G be a generic n-person game on the finite strategy space X, and let P"'^s-^e be adaptive plai/. If s/m is sufficiently small and s is sufficiently large, the unperturbed process p^{m s 0} converges with probability one to a min­imal curb configuration. If, in addition, e is sufficiently small, the perturbed process puts arbitrarily high probability on the minimal curb configuration(s) that minimize stochastic potential.

Date: 2016-04-22; view: 562