Original citation: Dyer, M., Goldberg, Leslie Ann, Greenhill, C., Istrate, G. and Jerrum, M. (2000) Convergence of the iterated prisoner's dilemma game. University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished) CS-RR-376 Permanent WRAP url: http://wrap.warwick.ac.uk/61133 Copyright and reuse: The Warwick Research Archive Portal (WRAP) makes this work by researchers of the University of Warwick available open access under the following conditions. Copyright © and all moral rights to the version of the paper presented here belong to the individual author(s) and/or other copyright owners. To the extent reasonable and practicable the material made available in WRAP has been checked for eligibility before being made available. Copies of full items can be used for personal research or study, educational, or not-forprofit purposes without prior permission or charge. Provided that the authors, title and full bibliographic details are credited, a hyperlink and/or URL is given for the original metadata page and the content is not changed in any way. A note on versions: The version presented in WRAP is the published version or, version of record, and may be cited as it appears here.For more information, please contact the WRAP Team at: [email protected] http://wrap.warwick.ac.uk/ Convergene of the Iterated Prisoner's Dilemma Game Martin Dyer y Leslie Ann Goldberg Gabriel Istrate { z Catherine Greenhill Mark Jerrum x k Otober 23, 2000 Abstrat We onsider a stohasti proess based on the iterated prisoner's dilemma game. During the game, eah of n players has a state, either ooperate or defet. The players are onneted by an \interation graph". During eah step of the proess, an edge of the graph is hosen uniformly at random and the states of the players onneted by the edge are modied aording to the Pavlov strategy. The proess onverges to a unique absorbing state in whih all players ooperate. We prove two onjetures of Kittok: The onvergene rate is exponential in n when the interation graph is a omplete graph, and it is polynomial in n when the interation graph is a yle. In fat, we show that the rate is O(n log n) in the latter ase. 1 Introdution In a two-player prisoner's dilemma game [1, 8℄, eah player may hoose to ooperate or to defet. If both players ooperate, they eah reeive a reward of R points. If both players defet, they eah reeive only P points. If exatly one player ooperates, he reeives S points while his opponent reeives T points. The parameters satisfy T > R > P > S This work was supported in part by the EPSRC Researh Grant \Sharper Analysis of Randomised Algorithms: a Computational Approah" and by the ESPRIT Projets RAND-APX and ALCOM-FT. y Shool of Computing, University of Leeds, Leeds LS2 9JT, United Kingdom, email: dyeromp.leeds.a.uk z Department of Computer Siene, University of Warwik, Coventry CV4 7AL, United Kingdom, email: leslieds.warwik.a.uk x Department of Mathematis and Statistis, University of Melbourne, Parkville VIC 3502, Australia, email: sgms.unimelb.edu.au Supported by an Australian Researh Counil Postdotoral Fellowship { Center for Nonlinear Siene and CIC-3 Division, Los Alamos National Laboratory, Mail Stop B258, Los Alamos, NM 87545, email: istratelanl.gov k Shool of Computer Siene, University of Edinburgh, King's Building, Edinburgh EH9 3JZ, United Kingdom, email: mrjds.ed.a.uk 1 and 2R > T + S . Thus, in a single round, it is best for eah player to defet even though this is not globally optimal. In the iterated prisoner's dilemma game, rounds are played repeatedly and players may base their deisions on the outomes of previous rounds. Empirial evidene indiates that an eetive strategy for this game is the so-alled \Pavlov" strategy: If a player is \rewarded" with T or R points during a given round, then he repeats his previous move next time. If he is \punished" with P or S points then he does not repeat his previous move. A small ase analysis reveals that the Pavlov strategy an also be stated as follows: A player ooperates if and only if he has made the same hoie as his opponent during the previous round. Kittok [4℄ studied the Pavlov strategy in a distributed setting: n players are onneted by an \interation graph". During a round of the game, an edge of the graph is seleted uniformly at random. The two players onneted by the edge play one round, using the Pavlov strategy. That is, if a player agreed with his (previous) opponent last time he was hosen to play, then he ooperates this time. Otherwise he defets. As long as the interation graph is onneted, the game onverges to a unique absorbing state in whih every player ooperates. Kittok was interested in determining the absorbtion time | that is, the time required to reah the absorbing state. He provided empirial evidene for the onjeture that the absorbtion time is exponential in n if the graph is the omplete graph, and polynomial in n if the graph is a yle. In this note, we prove Kittok's onjetures. The basi method whih we use to prove both theorems is to dene an appropriate potential funtion so that the progress of the Pavlov proess may be ompared to that of a one-dimensional random walk. See, for example, [5℄. Similar tehniques are often used to analyse the mixing time of Markov hains via oupling arguments. In the oupling ontext, the observed state spae is taken to be the set of pairs of Markov-hain states, and the potential funtion is dened to be the distane between the states in the pair, with respet to some metri. See, for example, [6, 7, 2, 3℄. 1 2 2 Preliminaries We are given a population of n 4 players situated at the verties of a onneted graph Eah player has an initial state X (i) 2 f 1; 1g. The 1 values enode the deision \ooperate" and are referred to as pluses. The 1 values enode the deision \defet" and are referred to as minuses. During eah step of the Pavlov proess, we G = (V; E ). 1 Axelrod [1℄ hosted a omputer tournament in whih strategies proposed by game theorists were played against eah other. Surprisingly, a simple Markovian strategy won the tournament. That is, the winning strategy has the property that the deision of a given player in a given round depends only on the outome of the previous round, and not on the rest of the history of the game. Nowak and Sigmund [8℄ did a omputational study of all suh Markovian strategies, and found the Pavlov strategy to be \best". 2 Kittok's paper is desribed using AI language, but the iterated prisoner's dilemma strategy that he studies (whih he alls the zero-memory HCR strategy) is preisely the Pavlov strategy. For more information about the ontext of Kittok's work and the HCR generalisation of the Pavlov strategy, see Shoham and Tennenholtz's paper [9℄. 2 hoose a pair fi; j g 2 E uniformly at random and replae X (i) and X (j ) by X (i)X (j ). The state X with X (i) = 1 for all v 2 V is an absorbing state of this proess. If G ontains no isolated verties then X is the unique absorbing state and there exists a sequene of moves whih an transform X to X , for every X 2 f1; 1gV . We are interested in the absorbtion time ; that is, the time required for the Pavlov proess to reah the absorbing state. We investigate two families of graphs, namely yles and omplete graphs. Using a oupon-olletor-like argument, Shoham and Tennenholtz [9℄ proved that, for a large lass of strategies, the absorbtion time for both of these families is (n log n). We prove the following theorems, showing that the Pavlov proess has optimal absorbtion time when G is a yle, and exponential absorbtion time when G is a omplete graph. Let G be a yle on n verties and let " > 0 be given. With probability at ", the Pavlov proess reahes the absorbing state in Theorem 1 least 1 49 n log 49n 2 94" steps. Theorem 2 Let Tn denote the absorbtion time of Pavlov proess on the graph Kn starting from a onguration X0 with at most 0:61n pluses. Then there exists a onstant > 1 suh that with probability 1 o(1) we have Tn n . 3 Optimal absorbtion on yles Let G be a yle on the the vertex set [n℄ = f0; : : : ; n 1g. That is, G has n edges fi; i + 1g for 0 i < n. Here, and throughout the paper, addition and subtration on verties is performed modulo n. We dene a potential funtion : f1; 1g ! R to measure the distane of a given state X from the absorbing state X . First, we must introdue some terminology. Let X 2 f1; 1g be given. A run in X is an interval [i; j ℄ where 0 i; j < n, suh that V V X (`) = 1 for ` = i; i + 1; : : : ; j 1; j and X (i 1) = 1, X (j + 1) = 1. (It is possible to have j < i, sine we are working modulo n.) Clearly all runs are disjoint. We an dene the set R(X ) of all runs in X . By onvention, the all-minuses onguration is not onsidered a run, sine it has no bordering pluses. Suppose that r = [i; j ℄. The length of the run r, denoted by `(r), equals the number of minuses in the run. We will refer to a run of length ` as an `-run. A 1-run will also be alled a singleton and a 2-run will also be alled a pair. Then the potential funtion is given by (X ) = j fi : X (i) = 1g j + jR(X )j + j fr 2 R(X ) : r is a singletong j + Æ j fr 2 R(X ) : r is a pairg j: 3 The parameters , and Æ will be set below. Note that a singleton is a barrier to absorbtion sine a singleton minus annot be hanged to a plus in one step. The singleton must rst beome part of a longer run. So we set > 0 to penalise singletons. On the other hand, pairs give the opportunity for two minuses to be hanged at one step. Thus pairs are helpful, and we reet this by setting Æ < 0. We also set > 0. Clearly (X ) = 0 for any values of , , Æ sine X (i) = 1 for all i, and R(X ) = ;. For to be a well-dened potential funtion, we must also show that (X ) > 0 whenever X 6= X . This is ahieved if 2 < Æ < 0, sine there an be at most half as many pairs in X as there are minuses. 3.1 The analysis We now analyse the Pavlov proess using the potential funtion . Let X 2 f1; 1gV be xed. Clearly if X = X there is nothing to prove. So, suppose that X ontains at least one minus. Let X be the result of performing one step of the proess from starting point X . We will nd an upper bound for E [ (X ) (X )℄. Note that eah edge overlaps at most one run in R(X ), and that there are ` + 1 edges whih overlap a given `-run. Speially, if r = [i; j ℄ then these `(r) + 1 edges are 0 0 0 1 0 1 0 0 fi 1; ig ; : : : ; fj; j + 1g : Let L(X ) be dened by 0 X L(X0 ) = r (`(r) + 1): 2R(X0 ) Then L(X ) equals the number of edges whih overlap some run in X . Denote by [ (X ) (X ) j e℄ the value of (X ) (X ) given that the edge e has been hosen by the Pavlov proess in step 1. Let r be an `-run and let 0 E 1 0 0 1 0 X (r ) = E (X ) j e℄ : [ (X ) 1 0 e overlaps r By denition we have E [ (X ) 1 X (X )℄ = n1 E [ (X ) 0 (X ) j e℄ ; 1 2 0 e E sine there are n edges in G. When X ontains both pluses and minuses we an also state that X (r ); E [ (X ) (X )℄ = n1 0 1 0 r 2R(X0 ) sine runs are disjoint and an edge whih does not overlap a run makes no hange to X . Let M = M (X ) be dened by (r ) M = max j r 2 R( X ) : `(r) + 1 0 0 0 4 That is, M is the maximum over all runs of the average ontribution of eah edge in that run. The way in whih M will be used is desribed below. We ignore two ongurations: the all-pluses onguration X , and the all-minuses onguration. The latter is treated separately in Setion 3.2. Suppose that X0 ontains both pluses and minuses. With M, as above, we have ML(X0 ) E [ (X1 )℄ 1 + (X )n (X0): 0 Lemma 1 . From above, we have and L dened Proof E [ (X ) 1 (X )℄ = n1 0 n1 We an rearrange this inequality to give [ (X )℄ 1 r 2R(X0 ) X 2R(X0 ) ML(X0 ) n = E X (X0) + MLn(X0 ) (r ) (`(r) + 1)M r = (X0 ) 1 + ML (X0)n (X ); 0 as stated. Suppose that the values of , , Æ ould be set to ensure that M < 0. Then, by Lemma 1, the value of dereases in expetation at every step. This will be used in Setion 3.2 to alulate an upper bound for the absorbtion time of the Pavlov proess. Let r = [i; j ℄ be a run. Then there are two outer rim edges assoiated with r, namely fi 1; ig and fj; j + 1g. If r has length at least 3 then there are also two inner rim edges assoiated with r, namely fi; i + 1g and fj 1; j g. If r is a singleton then there are no inner rim edges, while if r is a pair [i; i + 1℄ then there is a unique inner rim edge fi; i + 1g. All other edges whih overlap r are stritly inside the interval [i; j ℄, and we all these edges internal edges. Suppose that there are two runs in R(X ) whih are only separated by a single plus, i.e. [i; j ℄ and [j + 2; k℄ for some i, j , k. Then there are two edge hoies fj; j + 1g and fj + 1; j + 2g whih ause the two runs to merge (note that these edges are both outer rim edges for the runs whih they overlap). For simpliity, we will rst assume that there are no edge hoies whih ause runs to merge. That is, in Lemma 2 we assume that all adjaent runs in R(X ) are separated by at least two pluses. By arefully hoosing values for , and Æ in this ase, we show that M is negative: speially M = 1=14. In Lemma 3 we return to ongurations whih ontain adjaent runs separated by a single plus. 0 0 5 Before presenting Lemma 2, we make a few general remarks. When all adjaent runs are separated by at least two pluses, hoosing an outer rim edge will always ause r to inrease in length by 1, introduing an extra minus. Similarly, hoosing an inner rim edge will always ause r to derease in length by 2, hanging two minuses to pluses. When the length of r is small there might be additional eets from these four edges, as we shall see. When any internal edge is hosen, the run r is split into two runs whih are separated by two pluses. If the two runs have length k and ` we say that this edge hoie produes a (k; `)-split. We an now prove that M is negative for ertain xed values of , and Æ, when X ontains both pluses and minuses and all adjaent runs are separated by at least two pluses. 0 Lemma 2 Let X0 ontain both pluses and minuses, and suppose that adjaent runs in X0 are separated by at least two pluses. Then setting = 27=14, = 4=7 and Æ = 4=7 we obtain M = 1=14. . We will onsider runs r of dierent lengths in turn, and alulate (r)=(`(r)+1) in eah ase. Then M is the maximum of these values. Proof A 1-run. Let r be a 1-run [i; i℄. The only edges whih overlap r are the outer rim edges fi 1; ig and fi; i + 1g. When either of these edges are hosen, a vertex adjaent to the 1-run hanges from a plus to a minus. This introdues an extra minus and hanges a 1-run (singleton) to a 2-run (a pair), without hanging the total number of runs. Therefore (r ) 1: = 1 +Æ = (1) 2 7 Suppose that r = [i; i + 1℄. There are 3 edges whih overlap r. When either of the outer rim edges fi 1; ig or fi + 1; i + 2g are hosen the 2-run beomes a 3-run, introduing an extra minus and deleting a pair. There is only one inner rim edge, the edge fi; i + 1g. When this edge is hosen, both minuses in the pair beome pluses. Here we lose two minuses and delete a pair, dereasing the number of runs by 1. Adding these ontributions and dividing by 3 we nd that + 3Æ 1: (r) 2(1 Æ ) (2 + + Æ ) = = = (2) 3 3 3 14 A 2-run. Suppose that r = [i; i + 2℄. There are 4 edges whih overlap r, namely the two outer rim edges and the two inner rim edges. Choosing an outer rim edge turns the 3-run into a 4-run, introduing an extra minus. Choosing an inner rim edge turns the 3-run into a 1-run. Hene (r) 2 + 2( 2 + ) 1+ = 3 : = = (3) 4 4 2 14 6 A 3-run. Suppose that r = [i; i + 3℄ for some i. There are 5 edges whih overlap r. Choosing an outer rim edge auses r to inrease in length by 1, introduing a new minus. Choosing an inner rim edge auses the length of r to derease by 2: in this ase this introdues a new pair. Finally, there is one internal edge fi + 1; i + 2g. Choosing this edge produes a (1; 1)-split. This introdues two singletons and inreases the total number of runs by 1, while removing two minuses. Adding these ontributions together and dividing by 5, we obtain (r) 2 + 2( 2 + Æ ) + ( 2 + + 2 ) 4 + + 2 + 2Æ = 29 : = = (4) 5 5 5 70 A 4-run. Let r = [i; i + 4℄ for some i. There are six edges whih overlap r. Choosing an outer rim edge auses r to inrease in length by 1. Choosing an inner rim edge auses the length or r to derease by 2. There are two internal edges, fi + 1; i + 2g and fi + 2; i + 3g. Choosing either of these edges produes a (1; 2)-split, deleting two minuses, introduing a singleton and a pair, as well as inreasing the number of runs by 1. Adding the ontributions from all of these edges together, and dividing by 6, we obtain 3+++Æ = 5 : (r) 2 4 + 2( 2 + + + Æ ) = = (5) 6 6 3 14 A 5-run. Let r = [i; i + 5℄. There are 7 edges whih overlap r. If an outer rim edge is hosen then r inreases in length by 1. If an inner rim edge is hosen then r dereases in length by 2. There are 3 internal edges. Choosing fi + 1; i + 2g or fi + 3; i + 4g produes a (1; 3)-split, dereasing the number of minuses by 2 while inreasing the number of singletons and the number of runs by 1. Finally, hoosing the edge fi + 2; i + 3g produes a (2; 2)-split, dereasing the number of minuses by 2, inreasing the number of runs by 1 and the number of pairs by 2. Combining this information we nd that (r) 2 4 + 2( 2 + + ) + ( 2 + + 2Æ ) 8 + 3 + 2 + 2Æ = 31 : (6) = = 7 7 7 98 A 6-run. An `-run, where ` 7. Now suppose that r = [i; j ℄ is an `-run for some ` 7. Choosing either of the two outer rim edges auses r to inrease in length by 1. Choosing either of the two inner rim edges auses r to derease in length by 2. There are 4 internal edges whih need areful analysis. Choosing either fi + 1; i + 2g or fj 2; j 1g produes a (1; ` 3)-split, introduing a singleton and inreasing the number of runs by 1, while dereasing the number of minuses by 2. Similarly, hoosing either fi + 2; i + 3g or fj 3; j 2g produes a (2; ` 4)-split, introduing a pair and inreasing the number 7 of runs by 1, while dereasing the number of minuses by 2. There are ` 7 other internal edges whih split r into pairs of runs, eah of length at least 3. In eah ase, the number of minuses dereases by 2 while the number of runs inreases by 1, but the numbers of singletons and pairs are unhanged. We obtain 2 4 + 2( 2 + + ) + 2( 2 + + Æ) + (` 7)( 2 + ) (r ) = `+1 `+1 4 6 2 2Æ = 2 `+1 1 12 : = 14 (7) 7(` + 1) Now M is equal to the maximum of the right hand sides of (1){(7). It is easy to verify that the maximum is 1=14, as stated. For the remainder of this setion, the values of = 27=14, = 4=7 and Æ = 4=7 are xed. These values were hosen without explanation for use in the proof of Lemma 2 above. They were originally derived by setting = 2 , = 1=2 + and Æ = , and hoosing to minimize M . The interested reader an easily verify that = 1=14 is the optimal hoie. We now show that the value M = 1=14 an still be used in Lemma 1 even when the initial onguration has adjaent runs whih are separated by a single plus. Suppose that X0 2 f1; onlusion of Lemma 1 holds with Lemma 3 1g ontains both pluses and minuses. Then the M 1: = 14 . By Lemma 2, we have M = 1=14 whenever no two adjaent runs in X are separated by a single plus. So now suppose that there are exatly s distint values i 2 f0; : : : ; n 1g suh that X (i 1) = 1, X (i) = 1 and X (i + 1) = 1, where s 1. We will all suh an i a rim vertex. Dene a new yle G0 = (V 0 ; E 0 ) from G by splitting the vertex i into two new verties, i0 and i00 , for eah rim vertex i. Thus G0 is a graph on n + s verties. Let the edges of G0 be obtained from the edges of G by deleting the edges fi 1; ig, fi; i + 1g and adding the edges fi 1; i0g, fi0 ; i00g, fi0 ; i + 1g, for eah rim vertex i. Thus G0 forms a yle on n + s verties. Construt the onguration X 0 2 f1; 1gV from X by replaing the single plus at i by two pluses on i0 , i00 , for eah rim vertex i. That is, let Proof 0 0 0 0 0 0 ( X 0 (j ) X0 0 (j ) = if j is unprimed, otherwise: 1 8 0 By denition, X 0 has no two adjaent runs separated by a single plus. Note also that L(X 0 ) = L(X ). Let X 0 be the result of running the Pavlov proess for one step from X 0 . Combining Lemma 1 and Lemma 2, we see that L(X 0 ) 0 0 E [ (X ) (X )℄ 14(n + s) : Suppose that we ould show that 0 0 0 1 0 1 X 2 E [ (X 0 ) 0 0 [ (X ) ( X ) j e℄ : 1 X E [ (X 0 ) n + s e2E G X E [ (X ) n +1 s e2E G ( X 0 ) j e℄ 0 E 2 1 0 (8) e E (G) e E (G0 ) Then we would have E X (X 0 ) j e℄ 1 [ (X 0 ) (X 0)℄ = 1 0 1 ( 0 0 ) ( X ) j e℄ 1 = n ( n+s E 0 ) [ (X ) (X )℄ : 1 0 From this we ould onlude that n [ (X 0) (X 0)℄ L(X 0 ) 14(n + s) = 14(L(nX+)s) : Multiplying this inequality through by (n + s)=n proves the lemma. Hene it suÆes to establish (8). It is not diÆult to see that any edge whih does not overlap a rim vertex in X makes the same ontribution in both the primed and unprimed settings. For these edges e belong to both E (G) and E (G0 ), and n+s E (X )℄ [ (X ) 1 0 E 1 0 0 0 0 E [ (X 0 ) (X 0) j e℄ = E [ (X ) 1 0 (X ) j e℄ : 1 0 Therefore, to prove (8) it suÆes to prove that Y 0 > Y for all rim verties i, where Y = E [ (X ) 1 (X ) j fi 1; ig℄ + E [ (X ) 0 1 (X ) j fi; i + 1g℄ 0 and Y 0 = E [ (X1 0 ) (X 0 ) j fi 1; i0 g℄ + E [ (X 0) 0 1 9 (X 0 ) j fi00; i + 1g℄ : 0 (Clearly the edge fi0; i00 g makes no ontribution to E [ (X 0) (X 0)℄.) Let r and r be the two runs whih are separated by i in X , and dene a and b by 1 0 1 2 0 a = j fj 2 f1; 2g j rj is a singletong j and b = j fj 2 f1; 2g j rj is a pairg j: Then 0 a + b 2. Consider hoosing either fi 1; i0g or fi00 ; i + 1g for X 0. Clearly 0 either hoie will ause a minus to be introdued. For a of these hoies a singleton is removed and a pair is reated, while for b of these hoies a pair is removed. Therefore Y0 =2 a + aÆ bÆ: Now onsider hoosing either fi 1; ig or fi; i + 1g in X . The expeted hange of is idential for either hoie. Choosing either of these edges introdues a minus, dereases the number of runs by 1, and deletes all singletons or pairs whih are present in X . The merged run whih is reated has length `(r ) + `(r ) + 1 3, so no singletons or pairs are reated. Therefore 0 0 1 Y = 2(1 2 bÆ ): a Hene, using the values of , and Æ we obtain Y0 Y = 2 + a( + Æ) + bÆ 2( + Æ) > 0; proving the lemma. 3.2 Bounding the absorbtion time P We have xed = 27=14, = 4=7, Æ = 4=7. Reall that L(X ) = r2R X0 (`(r) + 1). Combining Lemmas 1, 2, 3 we obtain L(X ) E [ (X )℄ 1 14 (X )n (X ); (9) for all X whih ontain both pluses and minuses. We need the following result. 0 0 1 0 ( ) 0 0 Lemma 4 Let X 2 f1; 1gV and let , L be as dened above. Then (X ) 7L(4X ) if X ontains both pluses and minuses, while for all X 6= X . 47 (X ) 7n 14 4 10 (10) . First suppose that X ontains both pluses and minuses. Let (r) denote the potential of the run r, for all r 2 R(X ). That is, Proof 8 > <1 + + if r is a singleton, (r) = >2 + + Æ if r is a pair, : `(r) + otherwise. Clearly X (X ) = r 2R(X ) (r ): It is not diÆult to hek that the inequality (r ) 7 `(r) + 1 4 holds, with equality if and only if r is a singleton. Hene X X 7(`(r ) + 1) 7L(X ) ; (X ) = (r ) = 4 4 r 2R X r 2R X ( ) ( ) as stated. Now L(X ) denotes the number of edges whih overlap some run in X . Sine there are at exatly n edges in G, it follows that (X ) 74n whenever X ontains both pluses and minuses. Sine the all-minuses onguration has potential n, this proves the upper bound in (10). Finally, note that (r) 47 14 ; with equality if and only if r is a pair. Therefore the lowest potential of all ongurations with both minuses and pluses is obtained on any onguration whih ontains a unique run, this unique run being a pair. The all-minuses onguration has potential n, but we have assumed that n is at least 4. This proves the lower bound in (10). Combining (9) and the upper bound given in (10), we an onlude that 2 E [ (X )℄ 1 49n (X ) (11) for all X whih ontain both pluses and minuses. However, (11) also holds for the all-minuses onguration, as follows. Let X~ be the all-minuses onguration, dened by X~ (i) = 1 for all i. Let X~ be the result of running the Pavlov proes for one step from X~ . No matter whih edge is hosen, the number of minuses dereases by 2 and the Proof of Theorem 1. 1 0 0 0 1 0 11 h i (X~ ) (X~ ) = 2 = 1=14. number of runs inreases from 0 to 1. Therefore E Sine (X~ ) = n, we onlude that h i 1 2 ~ ~ E (X ) = 1 14n (X ) < 1 49n (X~ ); as laimed. So now let X 2 f1; 1gV satisfy X 6= X . Starting from X , run the Pavlov proess for t steps and let the resulting state be Xt . By applying (11) iteratively t times we obtain t t 2 2 E [ (Xt )℄ 1 49n (X ) 1 49n 74n ; 1 0 0 1 0 0 0 0 0 0 using the rst statement of Lemma 4 for the last inequality. Let " > 0 be given. Let = 47"=14. Whenever 7n 49 t n log 2 4 we have E [ (Xt )℄ . Using (10), any nonzero value of must be at least 47=14. Applying Markov's Lemma, we have 47 Prob [ (Xt) 6= 0℄ = Prob (Xt) 14 14 47 = ": This ompletes the proof. 4 Exponential absorbtion on the omplete graph In this setion we prove Theorem 2, showing that the absortion time of the Pavlov proess is exponential on the omplete graph Kn. We will use the notation Xt 2 f1; 1gn to refer to a onguration after t steps of the Pavlov proess. Let Nt be the number of nodes in Xt with label 1. Clearly Xt is equal to the all-pluses absorbing state if and only if Nt = n. We will assume that N 0:61n. The basis of our proof is the observation that the proess Nt is simple to analyse, even if the proess Xt is not. Let pt , qt denote the labels of the two nodes hosen at step t. Then the transition probabilities of Nt are given by the following rule: 0 Nt+1 8 < Nt 1 if ptqt = 1 (probability Nt(n Nt )= n ); if pt = qt = 1 (probability N = n ); = : Nt Nt + 2 if pt = qt = 1 (probability n N = n ): 2 t 2 2 t 2 Let I denote the interval [0:61n; 0:7n℄. 12 2 Suppose that N 2 I. Let T = min ft > j N 62 I g. Then the proess N ; : : : ; NT is stohastially dominated by the proess Q ; : : : ; QT where Qt is the simple Markov hain in whih Q = N and for t , Lemma 5 Qt+1 8 < Qt = : Qt 1 Qt + 2 with probability 0:35; with probability 0:49; with probability 0:16: Proof. For t 2 [; T 1℄, the pair (Nt ; Qt ) an be hosen from the following joint distribution whih satises Nt Qt . 8 (Nt 1; Qt 1) with probability 0:35; > > > > with probability Nt (n Nt)= n 0:35; < (Nt 1; Qt ) with probability [ N + n N ℄= n 0:16; (Nt ; Qt ) = > (Nt ; Qt ) > ( Nt ; Qt + 2) with probability 0 :16 n N = n ; > > : (Nt + 2; Qt + 2) with probability n N = n : Note that the probabilities are all between 0 and 1 sine Nt 2 I . +1 +1 +1 t t +1 2 2 2 t 2 t 2 2 2 2 To nish, we just need one more lemma. We show that if Qt is in the lower half of the interval I , then it is very likely to exit I by dropping below 0:61n (rather than by rising above 0:7n). Lemma 6 Suppose that 0:61n Qt 0:65n for some t. Dene T T = min ft0 > t j Qt 62 I g : by 0 There exists a onstant d > 1 suh that Prob [QT < 0:61n℄ 1 d n: . P Let M = 3n. For every m 2 [1; : : : ; M ℄, let xm = Qt m Qt m and Sm = mi xi . The random variables fxm g are independent of eah other sine, for all m, the variable xm is fully determined by the random hoie made by the Markov hain Q at time t + m. By denition, Qt m = Qt + Sm . Note that E[Sm ℄ = 0:03m. Using the value of E[SM ℄, we nd that Prob(SM 0:04n) is equal to Prob(SM E[SM ℄ + 0:05n). By a Cherno-Hoeding bound, this is at most exp( 2(0:05n) =(9M )), whih is less than (1=2)d n if d is hosen to be suÆiently lose to 1. Similarly, Proof + + 1 + 2 M X Prob(Sm 0:05n) m=1 M X Prob(Sm E[Sm℄ + 0:05n) m=1 < M X exp( 2(:05n) =(9m)) 2 m=1 (1=2)d 13 n ; =1 by hoosing d even loser to 1, if neessary. Thus, with probability at least 1 every m 2 [1; : : : ; M ℄ we have Qt+m and Qt+M d n , for = Qt + Sm < 0:65n + 0:05n = 0:7n = Qt + SM < 0:65n 0:04n = 0:61n: To omplete the proof of Theorem 2, note that every time the hain enters the interval I from below, the probability that it exits out the top of the region (rather than the bottom) is at most d n. Thus, the probability that the hain reahes absorbtion in as few as ((d + 1)=2)n visits to the region is at most d+1 2d n = o(1): 5 Other topis Several issues remain for further study. A natural extension of our results would be to investigate the Pavlov proess for other families of graphs. Two other ases seem partiularly interesting: degree-bounded trees and random graphs. Another possible ingredient to our model is random noise (or player mistakes). The importane of this parameter has been previously reognized in [8℄. Referenes [1℄ R. Axelrod, The Evolution of Cooperation, Basi Books, New York, 1984. [2℄ C. Cooper and A. Frieze, Mixing properties of the Swendsen-Wang proess on lasses of graphs, Random Strutures and Algorithms 15 (1999) 242{261. [3℄ M. Dyer and C. Greenhill, On Markov hains for independent sets, Journal of Algorithms, 35 (2000) 17{49. [4℄ J. E. Kittok, Emergent onventions and the struture of multi-agent systems, in L. Nadel and D. Stein, eds., 1993 Letures in Complex systems: the proeedings of the 1993 Complex systems summer shool, Santa Fe Institute Studies in the Sienes of Complexity Leture Volume VI, Santa Fe Institute, Addison-Wesley, 1995. [5℄ B. Hajek, Hitting-time and oupation-time bounds implied by drift analysis with appliations, Adv. Appl. Prob. 14 (1982) 502{525. 14 [6℄ M. Luby, D. Randall and A. Sinlair, Markov hain algorithms for planar lattie strutures, Proeedings of the Symposium on Foundations of Computer Siene (IEEE) 36 (1995) 150{159. [7℄ M. Luby and E. Vigoda, Approximately ounting up to four, Proeedings of the ACM Symposium on the Theory of Computing 29 (1997) 682{687. [8℄ M. Nowak and K. Sigmund, A strategy of win-stay, lose-shift that outperforms titfor-tat in the Prisoner's Dilemma game, Nature 364 (1993), pp. 56-58. [9℄ Y. Shoham and M. Tennenholtz, On the emergene of soial onventions: modelling, analysis and simulations, Artiial Intelligene, 94 (1997), pp. 139{166. 15

© Copyright 2021 DropDoc