Approximating Fixation Probabilities in the Generalized Moran Process
详细信息 查看全文
- 作者：Josep Díaz (1)
Leslie Ann Goldberg (2)
George B. Mertzios (3)
David Richerby (2)
Maria Serna (1)
Paul G. Spirakis (4) - 关键词：Evolutionary dynamics ; Markov ; chain Monte Carlo ; Approximation algorithm
- 刊名：Algorithmica
- 出版年：2014
- 出版时间：May 2014
- 年：2014
- 卷：69
- 期：1
- 页码：78-91
- 全文大小：491 KB
- 参考文献：1. Aldous, D.J., Fill, J.A.: Reversible Markov Chains and Random Walks on Graphs. Monograph in preparation. Available at http://www.stat.berkeley.edu/aldous/RWG/book.html
2. Antal, T., Scheuring, I.: Fixation of strategies for an evolutionary game in finite populations. Bull. Math. Biol. 68, 1923-944 (2006) CrossRef
3. Berger, E.: Dynamic monopolies of constant size. J. Comb. Theory, Ser. B 83, 191-00 (2001) CrossRef
4. Broom, M., Rychtá?, J.: An analysis of the fixation probability of a mutant on special classes of non-directed graphs. Proc. R. Soc. A, Math. Phys. Eng. Sci. 464(2098), 2609-627 (2008) CrossRef
5. Broom, M., Rychtá?, J., Stadler, B.: Evolutionary dynamics on small order graphs. J. Interdiscip. Math. 12, 129-40 (2009) CrossRef
6. Broom, M., Hadjichrysanthou, C., Rychtá?, J.: Evolutionary games on graphs and the speed of the evolutionary process. Proc. R. Soc. A, Math. Phys. Eng. Sci. 466(2117), 1327-346 (2010) CrossRef
7. Broom, M., Hadjichrysanthou, C., Rychtá?, J.: Two results on evolutionary processes on general non-directed graphs. Proc. R. Soc. A, Math. Phys. Eng. Sci. 466(2121), 2795-798 (2010) CrossRef
8. Durrett, R.: Lecture Notes on Particle Systems and Percolation. Wadsworth, Belmont (1988)
9. Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, Cambridge (2010) CrossRef
10. Gintis, H.: Game Theory Evolving: A Problem-Centered Introduction to Modeling Strategic Interaction. Princeton University Press, Princeton (2000)
11. Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14(3), 502-25 (1982) CrossRef
12. He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127, 57-5 (2001) CrossRef
13. Hofbauer, J., Sigmund, K.: Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge (1998) CrossRef
14. Imhof, L.A.: The long-run behavior of the stochastic replicator dynamics. Ann. Appl. Probab. 15(1B), 1019-045 (2005) CrossRef
15. Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43, 169-88 (1986) CrossRef
16. Kandori, M., Mailath, G.J., Rob, R.: Learning, mutation, and long run equilibria in games. Econometrica 61(1), 29-6 (1993) CrossRef
17. Karlin, S., Taylor, H.M.: A First Course in Stochastic Processes, 2nd edn. Academic Press, San Diego (1975)
18. Karp, R.M., Luby, M.: Monte-Carlo algorithms for enumeration and reliability problems. In: Proceedings of 24th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 56-4 (1983)
19. Kempel, D., Kleinberg, J., Tardos, E.: Influential nodes in a diffusion model for social networks. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 3580, pp. 1127-138. Springer, Berlin (2005) CrossRef
20. Lieberman, E., Hauert, C., Nowak, M.A.: Evolutionary dynamics on graphs. Nature 433, 312-16 (2005) CrossRef
21. Liggett, T.M.: Interacting Particle Systems. Springer, Berlin (1985) CrossRef
22. Luby, M., Randall, D., Sinclair, A.: Markov chain algorithms for planar lattice structures. SIAM J. Comput. 31(1), 167-92 (2001) CrossRef
23. Mertzios, G.B., Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Natural models for evolution on networks. In: Proceedings of the 7th Workshop on Internet and Network Economics (WINE), pp.?290-01 (2011) CrossRef
24. Moran, P.A.P.: Random processes in genetics. Proc. Camb. Philos. Soc. 54(1), 60-1 (1958) CrossRef
25. Mossel, E., Roch, S.: On the submodularity of influence in social networks. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 128-34 (2007)
26. Neveu, J.: Discrete-Parameter Martingales. North-Holland, Amsterdam (1975)
27. Nowak, M.A.: Evolutionary Dynamics: Exploring the Equations of Life. Harvard University Press, Cambridge (2006)
28. Ohtsuki, H., Nowak, M.A.: Evolutionary games on cycles. Proc. R. Soc. Lond. B, Biol. Sci. 273(1598), 2249-256 (2006) CrossRef
29. Rychtá?, J., Stadler, B.: Evolutionary dynamics on small-world networks. Int. J. Comput. Math. Sci. 2(1), 1- (2008)
30. Sandholm, W.H.: Population Games and Evolutionary Dynamics. MIT Press, Cambridge (2011)
31. Shakarian, P., Roos, P.: Fast and deterministic computation of fixation probability in evolutionary graphs. In: Proceedings of 6th International Conference on Computational Intelligence and Bioinformatics (2011)
32. Taylor, C., Fudenberg, D., Sasaki, A., Nowak, M.A.: Evolutionary game dynamics in finite populations. Bull. Math. Biol. 66(6), 1621-644 (2004) CrossRef
33. Taylor, C., Iwasa, Y., Nowak, M.A.: A symmetry of fixation times in evolutionary dynamics. J. Theor. Biol. 243(2), 245-51 (2006) CrossRef
34. Traulsen, A., Hauert, C.: Stochastic evolutionary game dynamics. In: Reviews of Nonlinear Dynamics and Complexity, vol. 2. Wiley, New York (2009) - 作者单位：Josep Díaz (1)
Leslie Ann Goldberg (2)
George B. Mertzios (3)
David Richerby (2)
Maria Serna (1)
Paul G. Spirakis (4)
1. Departament de Llenguatges i Sistemes Informátics, Universitat Politécnica de Catalunya, Barcelona, Spain
2. Department of Computer Science, University of Liverpool, Liverpool, UK
3. School of Engineering and Computing Sciences, Durham University, Durham, UK
4. Department of Computer Engineering and Informatics, University of Patras, Patras, Greece - ISSN：1432-0541
文摘
We consider the Moran process, as generalized by Lieberman et al. (Nature 433:312-16, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned “fitness-value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness r>0 placed uniformly at random, with every other vertex occupied by an individual of fitness?1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when r?) and of extinction (for all r>0).