Portal de Periódicos da CAPES

Sampling best response dynamics and deterministic equilibrium selection

2015; Econometric Society; Volume: 10; Issue: 1 Linguagem: Inglês

10.3982/te1405

1933-6837

Daisuke Oyama, William H. Sandholm, Olivier Tercieux,

Opinion Dynamics and Social Influence

Theoretical EconomicsVolume 10, Issue 1 p. 243-281 Original ArticlesOpen Access Sampling best response dynamics and deterministic equilibrium selection Daisuke Oyama, Daisuke Oyama [email protected] Faculty of Economics, University of TokyoSearch for more papers by this authorWilliam H. Sandholm, William H. Sandholm [email protected] Department of Economics, University of WisconsinSearch for more papers by this authorOlivier Tercieux, Olivier Tercieux [email protected] Paris School of Economics CNRS We thank Drew Fudenberg, Mario Pagliero, Satoru Takahashi, Jörgen Weibull, Dai Zusai, Martin Osborne, three anonymous referees, many seminar audiences, and especially Sergiu Hart and Josef Hofbauer for helpful discussions. Financial support from JSPS Grant-in-Aid for Young Scientists (B), the Seimeikai Foundation, and NSF Grants SES-0851580 and SES-1155135 is gratefully acknowledged. Search for more papers by this author Daisuke Oyama, Daisuke Oyama [email protected] Faculty of Economics, University of TokyoSearch for more papers by this authorWilliam H. Sandholm, William H. Sandholm [email protected] Department of Economics, University of WisconsinSearch for more papers by this authorOlivier Tercieux, Olivier Tercieux [email protected] Paris School of Economics CNRS We thank Drew Fudenberg, Mario Pagliero, Satoru Takahashi, Jörgen Weibull, Dai Zusai, Martin Osborne, three anonymous referees, many seminar audiences, and especially Sergiu Hart and Josef Hofbauer for helpful discussions. Financial support from JSPS Grant-in-Aid for Young Scientists (B), the Seimeikai Foundation, and NSF Grants SES-0851580 and SES-1155135 is gratefully acknowledged. Search for more papers by this author First published: 03 February 2015 https://doi.org/10.3982/TE1405Citations: 45 AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Abstract We consider a model of evolution in games in which a revising agent observes the actions of a random number of randomly sampled opponents and then chooses a best response to the distribution of actions in the sample. We provide a condition on the distribution of sample sizes under which an iterated p-dominant equilibrium is almost globally asymptotically stable under these dynamics. We show under an additional condition on the sample size distribution that in supermodular games, an almost globally asymptotically stable state must be an iterated p-dominant equilibrium. Since our selection results are for deterministic dynamics, any selected equilibrium is reached quickly; the long waiting times associated with equilibrium selection in stochastic stability models are absent. References 1 Aubin, Jean-Pierre and Arrigo Cellina (1984), Differential Inclusions: Set-Valued Maps and Viability Theory. Springer-Verlag, Berlin. 10.1007/978-3-642-69512-4 1 Basu, Kaushik and Jörgen W. Weibull (1991), " Strategy subsets closed under rational behavior." Economics Letters, 36, 141– 146. 10.1016/0165-1765(91)90179-O 1 Beckmann, Martin J. , C. B. McGuire , and Christopher B. Winsten (1956), Studies in the Economics of Transportation. Yale University Press, New Haven. 1 Benaïm, Michel (1998), " Recursive algorithms, urn processes and chaining number of chain recurrent sets." Ergodic Theory & Dynamical Systems, 18, 53– 87. 10.1017/S0143385798097557 1 Benaïm, Michel and Jörgen W. Weibull (2003), " Deterministic approximation of stochastic evolution in games." Econometrica, 71, 873– 903. 10.1111/1468-0262.00429 1 Benaïm, Michel , Josef Hofbauer , and Sylvain Sorin (2005), " Stochastic approximations and differential inclusions." SIAM Journal on Control and Optimization, 44, 328– 348. 10.1137/S0363012904439301 1 Binmore, Kenneth G. , Larry Samuelson , and Richard Vaughan (1995), " Musical chairs: Modeling noisy evolution." Games and Economic Behavior, 11, 1– 35. Erratum: 21 (1997), 325. 10.1006/game.1995.1039 1 Conley, Charles C. (1978), Isolated Invariant Sets and the Morse Index. American Mathematical Society, Providence, Rhode Island. 1 Cressman, Ross (1997), " Local stability of smooth selection dynamics for normal form games." Mathematical Social Sciences, 34, 1– 19. 10.1016/S0165-4896(97)00009-7 1 Durrett, Richard (2005), Probability: Theory and Examples, third edition. Brooks-Cole, Belmont, California. 1 Ellison, Glenn (1993), " Learning, local interaction, and coordination." Econometrica, 61, 1047– 1071. 10.2307/2951493 1 Ellison, Glenn (2000), " Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution." Review of Economic Studies, 67, 17– 45. 10.1111/1467-937X.00119 1 Ellison, Glenn , Drew Fudenberg , and Lorens A. Imhof (2009), " Random matching in adaptive dynamics." Games and Economic Behavior, 66, 98– 114. 10.1016/j.geb.2008.04.010 1 Foster, Dean P. and H. Peyton Young (1990), " Stochastic evolutionary game dynamics." Theoretical Population Biology, 38, 219– 232. Corrigendum: 51 (1997), 77–78. 10.1016/0040-5809(90)90011-J 1 Fudenberg, Drew and David M. Kreps (1993), " Learning mixed equilibria." Games and Economic Behavior, 5, 320– 367. 10.1006/game.1993.1021 1 Fudenberg, Drew and David K. Levine (1998), The Theory of Learning in Games. MIT Press, Cambridge, Massachusetts. 1 Galesloot, Bob M. and Sanjeev Goyal (1997), " Costs of flexibility and equilibrium selection." Journal of Mathematical Economics, 28, 249– 264. 10.1016/S0304-4068(97)00810-0 1 Gilboa, Itzhak and Akihiko Matsui (1991), " Social stability and equilibrium." Econometrica, 59, 859– 867. 10.2307/2938230 1 Goyal, Sanjeev and Maarten C. W. Janssen (1997), " Non-exclusive conventions and social coordination." Journal of Economic Theory, 77, 34– 57. 10.1006/jeth.1997.2315 1 Hofbauer, Josef (1995), " Stability for the best response dynamics." Working paper, University of Vienna. 1 Hofbauer, Josef (1999), " The spatially dominant equilibrium of a game." Annals of Operations Research, 89, 233– 251. 10.1023/A:1018979708014 1 Hofbauer, Josef (2000), " From Nash and Brown to Maynard Smith: Equilibria, dynamics, and ESS." Selection, 1, 81– 88. 10.1556/Select.1.2000.1-3.8 1 Hofbauer, Josef and William H. Sandholm (2002), " On the global convergence of stochastic fictitious play." Econometrica, 70, 2265– 2294. 10.1111/1468-0262.00376 1 Hofbauer, Josef and William H. Sandholm (2007), " Evolution in games with randomly disturbed payoffs." Journal of Economic Theory, 132, 47– 69. 10.1016/j.jet.2005.05.011 1 Hofbauer, Josef and William H. Sandholm (2011), " Survival of dominated strategies under evolutionary dynamics." Theoretical Economics, 6, 341– 377. 10.3982/TE771 1 Hurkens, Sjaak (1995), " Learning by forgetful players." Games and Economic Behavior, 11, 304– 329. 10.1006/game.1995.1053 1 Kandori, Michihiro , George J. Mailath , and Rafael Rob (1993), " Learning, mutation, and long run equilibria in games." Econometrica, 61, 29– 56. 10.2307/2951777 1 Kaniovski, Yuri M. and H. Peyton Young (1995), " Learning dynamics in games with stochastic perturbations." Games and Economic Behavior, 11, 330– 363. 10.1006/game.1995.1054 1 Kreindler, Gabriel E. and H. Peyton Young (2013), " Fast convergence in evolutionary equilibrium selection." Games and Economic Behavior, 80, 39– 67. 10.1016/j.geb.2013.02.004 1 Matsui, Akihiko (1991), " Cheap-talk and cooperation in a society." Journal of Economic Theory, 54, 245– 258. 10.1016/0022-0531(91)90122-K 1 Matsui, Akihiko and Kiminori Matsuyama (1995), " An approach to equilibrium selection." Journal of Economic Theory, 65, 415– 434. 10.1006/jeth.1995.1015 1 Maynard Smith, John and George R. Price (1973), " The logic of animal conflict." Nature, 246, 15– 18. 10.1038/246015a0 1 Morris, Stephen , Rafael Rob , and Hyun Song Shin (1995), " p-dominance and belief potential." Econometrica, 63, 145– 157. 10.2307/2951700 1 Munkres, James R. (2000), Topology, second edition. Pearson, New York. 1 Nachbar, John H. (1990), " 'Evolutionary' selection dynamics in games: Convergence and limit properties." International Journal of Game Theory, 19, 59– 89. 10.1007/BF01753708 1 Osborne, Martin J. and Ariel Rubinstein (1998), " Games with procedurally rational players." American Economic Review, 88, 834– 847. 1 Osborne, Martin J. and Ariel Rubinstein (2003), " Sampling equilibrium, with an application to strategic voting." Games and Economic Behavior, 45, 434– 441. 10.1016/S0899-8256(03)00147-7 1 Oyama, Daisuke and Satoru Takahashi (2014), " Contagion and uninvadability in local interaction games: The bilingual game and general supermodular games." Working paper, University of Tokyo and National University of Singapore. 1 Oyama, Daisuke and Olivier Tercieux (2009), " Iterated potential and robustness of equilibria." Journal of Economic Theory, 144, 1726– 1769. 10.1016/j.jet.2009.03.001 1 Oyama, Daisuke , Satoru Takahashi , and Josef Hofbauer (2008), " Monotone methods for equilibrium selection under perfect foresight dynamics." Theoretical Economics, 3, 155– 192. 1 Roth, Grégory and William H. Sandholm (2013), " Stochastic approximations with constant step size and differential inclusions." SIAM Journal on Control and Optimization, 51, 525– 555. 10.1137/110844192 1 Samuelson, Larry and Jianbo Zhang (1992), " Evolutionary stability in asymmetric games." Journal of Economic Theory, 57, 363– 391. 10.1016/0022-0531(92)90041-F 1 Sandholm, William H. (2001), " Almost global convergence to p-dominant equilibrium." International Journal of Game Theory, 30, 107– 116. 10.1007/s001820100067 1 Sandholm, William H. (2010a), " Local stability under evolutionary game dynamics." Theoretical Economics, 5, 27– 50. 10.3982/TE505 1 Sandholm, William H. (2010b), Population Games and Evolutionary Dynamics. MIT Press, Cambridge, Massachusetts. 1 Sandholm, William H. (2015), " Population games and deterministic evolutionary dynamics." In Handbook of Game Theory, Vol. 4 ( H. Petyon Young and Shmuel Zamir, eds.), 703– 778, North-Holland, Amsterdam. 1 Selten, Reinhard and Thorsten Chmura (2008), " Stationary concepts for experimental 2 × 2-games." American Economic Review, 98, 938– 966. 10.1257/aer.98.3.938 1 Sethi, Rajiv (2000), " Stability of equilibria in games with procedurally rational players." Games and Economic Behavior, 32, 85– 104. 10.1006/game.1999.0753 1 Smirnov, Georgi V. (2002), Introduction to the Theory of Differential Inclusions. American Mathematical Society, Providence, Rhode Island. 1 Taylor, Peter D. and Leo B. Jonker (1978), " Evolutionarily stable strategies and game dynamics." Mathematical Biosciences, 40, 145– 156. 10.1016/0025-5564(78)90077-9 1 Tercieux, Olivier (2006), " p-best response set." Journal of Economic Theory, 131, 45– 70. 10.1016/j.jet.2005.06.001 1 Walter, Wolfgang (1970), Differential and Integral Inequalities. Springer-Verlag, Berlin. 10.1007/978-3-642-86405-6 1 Young, H. Peyton (1993), " The evolution of conventions." Econometrica, 61, 57– 84. 10.2307/2951778 1 Young, H. Peyton (1998), Individual Strategy and Social Structure. Princeton University Press, Princeton. Citing Literature Volume10, Issue1January 2015Pages 243-281 ReferencesRelatedInformation