doi: 10.3934/jdg.2021029
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Stochastic dynamics and Edmonds' algorithm

1. 

Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501, Japan

2. 

University of Wisconsin, 1180 Observatory Drive, Madison, WI 53706, USA

*Corresponding author: Jonathan Newton

Received  February 2021 Revised  October 2021 Early access November 2021

Recently, there has been a revival of interest in cyclic decompositions of stochastic dynamics. These decompositions consider the behavior of dynamics over the short, medium and long run, aggregating cycles of behavior into progressively larger cycles, eventually encompassing the entire state space. We show that these decompositions are equivalent to the aggregative stage of Edmonds' algorithm and that this equivalence can be used to recover well-known results in the literature.

Citation: Jonathan Newton, William H. Sandholm. Stochastic dynamics and Edmonds' algorithm. Journal of Dynamics & Games, doi: 10.3934/jdg.2021029
References:
[1]

C. Alós-Ferrer and N. Netzer, The logit response dynamics, Games and Economic Behavior, 68 (2010), 413-427.  doi: 10.1016/j.geb.2009.08.004.  Google Scholar

[2]

C. Alós-Ferrer and K. H. Schlag, Imitation and Learning, in The handbook of rational and social choice, Oxford University Press, 2009. doi: 10.1093/acprof:oso/9780199290420.003.0012.  Google Scholar

[3]

I. ArieliY. BabichenkoR. Peretz and H. P. Young, The speed of innovation diffusion in social networks, Econometrica, 88 (2020), 569-594.  doi: 10.3982/ECTA17007.  Google Scholar

[4]

I. Arieli and H. P. Young, Stochastic learning dynamics and speed of convergence in population games, Econometrica, 84 (2016), 627-676.  doi: 10.3982/ECTA10740.  Google Scholar

[5]

L. E. Blume, The statistical mechanics of strategic interaction, Games and Economic Behavior, 5 (1993), 387-424.  doi: 10.1006/game.1993.1023.  Google Scholar

[6]

L. E. Blume, How noise matters, Games and Economic Behavior, 44 (2003), 251-271.  doi: 10.1016/S0899-8256(02)00554-7.  Google Scholar

[7]

O. Catoni, Simulated annealing algorithms and Markov chains with rare transitions, in Séminaire de Probabilités XXXIII (eds. J. Azéma, M. Émery, M. Ledoux and M. Yor), Springer, Berlin, 1709 (1999), 69–119. doi: 10.1007/BFb0096510.  Google Scholar

[8]

I.-K. Cho and K. Kasa, Learning and model validation, The Review of Economic Studies, 82 (2014), 45-82.  doi: 10.1093/restud/rdu026.  Google Scholar

[9]

Y.-J. Chu and T.-H. Liu, On the shortest arborescence of a directed graph, Science Sinica, 14 (1965), 1396-1400.   Google Scholar

[10]

Z. Cui and J. Zhai, Escape dynamics and equilibria selection by iterative cycle decomposition, Journal of Mathematical Economics, 46 (2010), 1015–1029, URL http://www.sciencedirect.com/science/article/pii/S0304406809001438. doi: 10.1016/j.jmateco.2009.11.014.  Google Scholar

[11]

E. Dokumacı and W. H. Sandholm, Large deviations and multinomial probit choice, Journal of Economic Theory, 146 (2011), 2151-2158.  doi: 10.1016/j.jet.2011.06.013.  Google Scholar

[12]

J. Edmonds, Optimum branchings, Journal of Research of the National Bureau of Standards, 71 (1967), 233-240.  doi: 10.6028/jres.071B.032.  Google Scholar

[13]

G. Ellison, Learning, local interaction, and coordination, Econometrica, 61 (1993), 1047-1071.  doi: 10.2307/2951493.  Google Scholar

[14]

G. Ellison, Basins of attraction, long run equilibria, and the speed of step-by-step evolution, Review of Economic Studies, 67 (2000), 17-45.  doi: 10.1111/1467-937X.00119.  Google Scholar

[15]

D. P. Foster and H. P. Young, Stochastic evolutionary game dynamics, Theoretical Population Biology, 38 (1990), 219-232.  doi: 10.1016/0040-5809(90)90011-J.  Google Scholar

[16]

M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, Springer, New York, 1984. doi: 10.1007/978-1-4684-0176-9.  Google Scholar

[17]

M. O. Jackson and A. Watts, The evolution of social and economic networks, Journal of Economic Theory, 106 (2002), 265-295.  doi: 10.1006/jeth.2001.2903.  Google Scholar

[18]

M. KandoriG. J. Mailath and R. Rob, Learning, mutation, and long run equilibria in games, Econometrica, 61 (1993), 29-56.  doi: 10.2307/2951777.  Google Scholar

[19]

D. K. Levine and S. Modica, Dynamics in stochastic evolutionary models, Theoretical Economics, 11 (2016), 89-131.  doi: 10.3982/TE1978.  Google Scholar

[20]

D. P. Myatt and C. C. Wallace, A multinomial probit model of stochastic evolution, Journal of Economic Theory, 113 (2003), 286-301.  doi: 10.1016/S0022-0531(03)00069-3.  Google Scholar

[21]

H. H. Nax and B. S. R. Pradelski, Evolutionary dynamics and equitable core selection in assignment games, International Journal of Game Theory, 44 (2015), 903-932.  doi: 10.1007/s00182-014-0459-1.  Google Scholar

[22]

J. Newton, Coalitional stochastic stability, Games and Economic Behavior, 75 (2012), 842-854.  doi: 10.1016/j.geb.2012.02.014.  Google Scholar

[23]

J. Newton, Evolutionary game theory: A renaissance, Games, 9 (2018), 31, 67pp, URL http://www.mdpi.com/2073-4336/9/2/31. doi: 10.3390/g9020031.  Google Scholar

[24]

J. Newton, Conventions under heterogeneous behavioural rules, The Review of Economic Studies, 88 (2021), 2094-2118.  doi: 10.1093/restud/rdaa063.  Google Scholar

[25]

J. Newton and S. D. Angus, Coalitions, tipping points and the speed of evolution, Journal of Economic Theory, 157 (2015), 172-187.  doi: 10.1016/j.jet.2015.01.003.  Google Scholar

[26]

J. Newton and R. Sawa, A one-shot deviation principle for stability in matching problems, Journal of Economic Theory, 157 (2015), 1-27.  doi: 10.1016/j.jet.2014.11.015.  Google Scholar

[27]

T. W. Norman, Rapid evolution under inertia, Games and Economic Behavior, 66 (2009), 865-879.  doi: 10.1016/j.geb.2008.10.002.  Google Scholar

[28]

M. Peski, Generalized risk-dominance and asymmetric dynamics, Journal of Economic Theory, 145 (2010), 216-248.  doi: 10.1016/j.jet.2009.05.007.  Google Scholar

[29] W. H. Sandholm, Population Games and Evolutionary Dynamics, MIT Press, Cambridge, 2010.   Google Scholar
[30]

F. Vega-Redondo, The evolution of Walrasian behavior, Econometrica, 65 (1997), 375-384.  doi: 10.2307/2171898.  Google Scholar

[31]

H. P. Young, The evolution of conventions, Econometrica, 61 (1993), 57-84.  doi: 10.2307/2951778.  Google Scholar

[32]

H. P. Young, The dynamics of social innovation, Proceedings of the National Academy of Sciences, 108 (2011), 21285-21291.  doi: 10.1073/pnas.1100973108.  Google Scholar

show all references

References:
[1]

C. Alós-Ferrer and N. Netzer, The logit response dynamics, Games and Economic Behavior, 68 (2010), 413-427.  doi: 10.1016/j.geb.2009.08.004.  Google Scholar

[2]

C. Alós-Ferrer and K. H. Schlag, Imitation and Learning, in The handbook of rational and social choice, Oxford University Press, 2009. doi: 10.1093/acprof:oso/9780199290420.003.0012.  Google Scholar

[3]

I. ArieliY. BabichenkoR. Peretz and H. P. Young, The speed of innovation diffusion in social networks, Econometrica, 88 (2020), 569-594.  doi: 10.3982/ECTA17007.  Google Scholar

[4]

I. Arieli and H. P. Young, Stochastic learning dynamics and speed of convergence in population games, Econometrica, 84 (2016), 627-676.  doi: 10.3982/ECTA10740.  Google Scholar

[5]

L. E. Blume, The statistical mechanics of strategic interaction, Games and Economic Behavior, 5 (1993), 387-424.  doi: 10.1006/game.1993.1023.  Google Scholar

[6]

L. E. Blume, How noise matters, Games and Economic Behavior, 44 (2003), 251-271.  doi: 10.1016/S0899-8256(02)00554-7.  Google Scholar

[7]

O. Catoni, Simulated annealing algorithms and Markov chains with rare transitions, in Séminaire de Probabilités XXXIII (eds. J. Azéma, M. Émery, M. Ledoux and M. Yor), Springer, Berlin, 1709 (1999), 69–119. doi: 10.1007/BFb0096510.  Google Scholar

[8]

I.-K. Cho and K. Kasa, Learning and model validation, The Review of Economic Studies, 82 (2014), 45-82.  doi: 10.1093/restud/rdu026.  Google Scholar

[9]

Y.-J. Chu and T.-H. Liu, On the shortest arborescence of a directed graph, Science Sinica, 14 (1965), 1396-1400.   Google Scholar

[10]

Z. Cui and J. Zhai, Escape dynamics and equilibria selection by iterative cycle decomposition, Journal of Mathematical Economics, 46 (2010), 1015–1029, URL http://www.sciencedirect.com/science/article/pii/S0304406809001438. doi: 10.1016/j.jmateco.2009.11.014.  Google Scholar

[11]

E. Dokumacı and W. H. Sandholm, Large deviations and multinomial probit choice, Journal of Economic Theory, 146 (2011), 2151-2158.  doi: 10.1016/j.jet.2011.06.013.  Google Scholar

[12]

J. Edmonds, Optimum branchings, Journal of Research of the National Bureau of Standards, 71 (1967), 233-240.  doi: 10.6028/jres.071B.032.  Google Scholar

[13]

G. Ellison, Learning, local interaction, and coordination, Econometrica, 61 (1993), 1047-1071.  doi: 10.2307/2951493.  Google Scholar

[14]

G. Ellison, Basins of attraction, long run equilibria, and the speed of step-by-step evolution, Review of Economic Studies, 67 (2000), 17-45.  doi: 10.1111/1467-937X.00119.  Google Scholar

[15]

D. P. Foster and H. P. Young, Stochastic evolutionary game dynamics, Theoretical Population Biology, 38 (1990), 219-232.  doi: 10.1016/0040-5809(90)90011-J.  Google Scholar

[16]

M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, Springer, New York, 1984. doi: 10.1007/978-1-4684-0176-9.  Google Scholar

[17]

M. O. Jackson and A. Watts, The evolution of social and economic networks, Journal of Economic Theory, 106 (2002), 265-295.  doi: 10.1006/jeth.2001.2903.  Google Scholar

[18]

M. KandoriG. J. Mailath and R. Rob, Learning, mutation, and long run equilibria in games, Econometrica, 61 (1993), 29-56.  doi: 10.2307/2951777.  Google Scholar

[19]

D. K. Levine and S. Modica, Dynamics in stochastic evolutionary models, Theoretical Economics, 11 (2016), 89-131.  doi: 10.3982/TE1978.  Google Scholar

[20]

D. P. Myatt and C. C. Wallace, A multinomial probit model of stochastic evolution, Journal of Economic Theory, 113 (2003), 286-301.  doi: 10.1016/S0022-0531(03)00069-3.  Google Scholar

[21]

H. H. Nax and B. S. R. Pradelski, Evolutionary dynamics and equitable core selection in assignment games, International Journal of Game Theory, 44 (2015), 903-932.  doi: 10.1007/s00182-014-0459-1.  Google Scholar

[22]

J. Newton, Coalitional stochastic stability, Games and Economic Behavior, 75 (2012), 842-854.  doi: 10.1016/j.geb.2012.02.014.  Google Scholar

[23]

J. Newton, Evolutionary game theory: A renaissance, Games, 9 (2018), 31, 67pp, URL http://www.mdpi.com/2073-4336/9/2/31. doi: 10.3390/g9020031.  Google Scholar

[24]

J. Newton, Conventions under heterogeneous behavioural rules, The Review of Economic Studies, 88 (2021), 2094-2118.  doi: 10.1093/restud/rdaa063.  Google Scholar

[25]

J. Newton and S. D. Angus, Coalitions, tipping points and the speed of evolution, Journal of Economic Theory, 157 (2015), 172-187.  doi: 10.1016/j.jet.2015.01.003.  Google Scholar

[26]

J. Newton and R. Sawa, A one-shot deviation principle for stability in matching problems, Journal of Economic Theory, 157 (2015), 1-27.  doi: 10.1016/j.jet.2014.11.015.  Google Scholar

[27]

T. W. Norman, Rapid evolution under inertia, Games and Economic Behavior, 66 (2009), 865-879.  doi: 10.1016/j.geb.2008.10.002.  Google Scholar

[28]

M. Peski, Generalized risk-dominance and asymmetric dynamics, Journal of Economic Theory, 145 (2010), 216-248.  doi: 10.1016/j.jet.2009.05.007.  Google Scholar

[29] W. H. Sandholm, Population Games and Evolutionary Dynamics, MIT Press, Cambridge, 2010.   Google Scholar
[30]

F. Vega-Redondo, The evolution of Walrasian behavior, Econometrica, 65 (1997), 375-384.  doi: 10.2307/2171898.  Google Scholar

[31]

H. P. Young, The evolution of conventions, Econometrica, 61 (1993), 57-84.  doi: 10.2307/2951778.  Google Scholar

[32]

H. P. Young, The dynamics of social innovation, Proceedings of the National Academy of Sciences, 108 (2011), 21285-21291.  doi: 10.1073/pnas.1100973108.  Google Scholar

Figure 1.  Cycles. For given least cost correspondence, the set of cycles, closed cycles and simple cycles
Figure 2.  Aggregation of states in a CLE decomposition/Edmonds' algorithm. This diagram illustrates cyclic decomposition, moving step by step from $ \mathscr{P}_0 $ to $ \mathscr{P}_4 $. The cost function $ C(\cdot, \cdot) $ is given by edge weights, with missing edges denoting transitions with infinite cost. The values of $ C(\cdot, \cdot) $ on the initial partition $ \mathscr{P}_0 $ are assumed. Costs for partitions $ \mathscr{P}_{\ell} $, $ \ell>0 $, are calculated as described in the text. Least cost transitions are denoted by an underlined cost and a red arrow, so that a subset of elements in a partition is a cycle if is the vertex set for a (graphical) simple cycle of such edges in the diagram. At each step, one simple cycle is consolidated. For example, in moving from $ \mathscr{P}_0 $ to $ \mathscr{P}_1 $, cycle $ \{\{u\}, \{v\} , \{w\} \} \subset \mathscr{P}_0 $ is consolidated to form $ \{u, v, w\} \in \mathscr{P}_1 $, with the costs of transitions to and from $ \{u, v, w\} $ given by expressions (6) and (7) in the text. For example, $ C(\{u, v, w\}, \{y\}) = \min\{4-4+\infty, 4-2+ \infty, 4-2+5 \} = 7 $
Figure 3.  Disaggregation of states under Edmonds' algorithm. This diagram illustrates disaggregation and the construction of a spanning tree under Edmonds' algorithm, moving step by step from $ \mathscr{P}_4 $ to $ \mathscr{P}_0 $. At each step a composite is expanded into the cycle that formed it during the aggregation phase. For example, $ \{x, y, z\} \in \mathscr{P}_3 $ is expanded to $ \{\{x, y\}, \{z\} \} \subset \mathscr{P}_2 $ and edges from $ \{x, y\} $ to $ \{z\} $ and from $ \{z\} $ to $ \{x, y\} $ are added. Next, edges to or from the composite that is expanded are assigned to the elements of the cycle that solved (6) or (7) when the cycle was consolidated during the aggregation phase. For example, the edge from $ \{x, y, z\} $ to $ \{u, v, w\} $ is replaced by an edge from $ \{x, y\} $ to $ \{u, v, w\} $. Finally, an edge in the expanded cycle is deleted (denoted by a dotted line in the diagram). If the expanded composite was not the root of the tree at the previous step (e.g. $ \{x, y, z\} $ in $ \mathscr{P}_3 $), then the element of the cycle with an outgoing edge to outside of the cycle (e.g. $ \{x, y\} $ in $ \{\{x, y\}, \{z\}\} $) has its outgoing edge within the cycle deleted (e.g. the edge from $ \{x, y\} $ to $ \{z\} $). If the expanded composite was the root of the tree at the previous step (e.g. $ \{u, v, w\} $ in $ \mathscr{P}_1 $), then the element of the cycle with the highest least cost transition (e.g. $ \{u\} $ in $ \{\{u\}, \{v\}, \{w\}\} $) has its outgoing edge deleted (e.g. the edge from $ \{u\} $ to $ \{v\} $)
Figure 2. Edges connect composites to their pieces below them in the diagram. Edge weights give $ \underline{C}(\cdot) $ for the composite at the lower end of the edge in question. For each composite $ \alpha $, we give $ r_{\alpha} $ which measures the order of magnitude of the probability placed on $ \alpha $ by the invariant measure. These are calculated using the values of $ \underline{C}(\cdot) $. For example, $ \{x, y\} $ has $ r_{\{x, y\}} = 2 $, therefore by Lemma 3.1, one of its pieces has $ r = 2 $ and none have $ r<2 $. As $ \underline{C}(\{x\}) = 1< 2 = \underline{C}(\{y\}) $ and Lemma 2.1 states that $ \underline{C}(\{x\}) + r_{\{x\}} = \underline{C}(\{y\}) + r_{\{y\}} $, it must be that $ r_{\{x\}} = 3 $ and $ r_{\{y\}} = 2 $">Figure 4.  The tree structure of decompositions. The tree structure of the decomposition considered in Figure 2. Edges connect composites to their pieces below them in the diagram. Edge weights give $ \underline{C}(\cdot) $ for the composite at the lower end of the edge in question. For each composite $ \alpha $, we give $ r_{\alpha} $ which measures the order of magnitude of the probability placed on $ \alpha $ by the invariant measure. These are calculated using the values of $ \underline{C}(\cdot) $. For example, $ \{x, y\} $ has $ r_{\{x, y\}} = 2 $, therefore by Lemma 3.1, one of its pieces has $ r = 2 $ and none have $ r<2 $. As $ \underline{C}(\{x\}) = 1< 2 = \underline{C}(\{y\}) $ and Lemma 2.1 states that $ \underline{C}(\{x\}) + r_{\{x\}} = \underline{C}(\{y\}) + r_{\{y\}} $, it must be that $ r_{\{x\}} = 3 $ and $ r_{\{y\}} = 2 $
[1]

Felix X.-F. Ye, Yue Wang, Hong Qian. Stochastic dynamics: Markov chains and random transformations. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2337-2361. doi: 10.3934/dcdsb.2016050

[2]

Demetris Hadjiloucas. Stochastic matrix-valued cocycles and non-homogeneous Markov chains. Discrete & Continuous Dynamical Systems, 2007, 17 (4) : 731-738. doi: 10.3934/dcds.2007.17.731

[3]

William H. Sandholm. Local stability of strict equilibria under evolutionary game dynamics. Journal of Dynamics & Games, 2014, 1 (3) : 485-495. doi: 10.3934/jdg.2014.1.485

[4]

Astridh Boccabella, Roberto Natalini, Lorenzo Pareschi. On a continuous mixed strategies model for evolutionary game theory. Kinetic & Related Models, 2011, 4 (1) : 187-213. doi: 10.3934/krm.2011.4.187

[5]

Anna Lisa Amadori, Astridh Boccabella, Roberto Natalini. A hyperbolic model of spatial evolutionary game theory. Communications on Pure & Applied Analysis, 2012, 11 (3) : 981-1002. doi: 10.3934/cpaa.2012.11.981

[6]

Ross Cressman, Vlastimil Křivan. Using chemical reaction network theory to show stability of distributional dynamics in game theory. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021030

[7]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051

[8]

Katarzyna PichÓr, Ryszard Rudnicki. Stability of stochastic semigroups and applications to Stein's neuronal model. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 377-385. doi: 10.3934/dcdsb.2018026

[9]

Xin Zhao, Tao Feng, Liang Wang, Zhipeng Qiu. Threshold dynamics and sensitivity analysis of a stochastic semi-Markov switched SIRS epidemic model with nonlinear incidence and vaccination. Discrete & Continuous Dynamical Systems - B, 2021, 26 (12) : 6131-6154. doi: 10.3934/dcdsb.2021010

[10]

Alison M. Melo, Leandro B. Morgado, Paulo R. Ruffino. Decomposition of stochastic flows generated by Stratonovich SDEs with jumps. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3209-3218. doi: 10.3934/dcdsb.2016094

[11]

Ido Polak, Nicolas Privault. A stochastic newsvendor game with dynamic retail prices. Journal of Industrial & Management Optimization, 2018, 14 (2) : 731-742. doi: 10.3934/jimo.2017072

[12]

King-Yeung Lam. Dirac-concentrations in an integro-pde model from evolutionary game theory. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 737-754. doi: 10.3934/dcdsb.2018205

[13]

H.Thomas Banks, Shuhua Hu. Nonlinear stochastic Markov processes and modeling uncertainty in populations. Mathematical Biosciences & Engineering, 2012, 9 (1) : 1-25. doi: 10.3934/mbe.2012.9.1

[14]

Yu Wu, Xiaopeng Zhao, Mingjun Zhang. Dynamics of stochastic mutation to immunodominance. Mathematical Biosciences & Engineering, 2012, 9 (4) : 937-952. doi: 10.3934/mbe.2012.9.937

[15]

Serap Ergün, Sirma Zeynep Alparslan Gök, Tuncay Aydoǧan, Gerhard Wilhelm Weber. Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra's algorithm. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1085-1100. doi: 10.3934/jimo.2018086

[16]

Leonid Shaikhet. Stability of delay differential equations with fading stochastic perturbations of the type of white noise and poisson's jumps. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3651-3657. doi: 10.3934/dcdsb.2020077

[17]

Feng Bao, Thomas Maier. Stochastic gradient descent algorithm for stochastic optimization in solving analytic continuation problems. Foundations of Data Science, 2020, 2 (1) : 1-17. doi: 10.3934/fods.2020001

[18]

Sofian De Clercq, Wouter Rogiest, Bart Steyaert, Herwig Bruneel. Stochastic decomposition in discrete-time queues with generalized vacations and applications. Journal of Industrial & Management Optimization, 2012, 8 (4) : 925-938. doi: 10.3934/jimo.2012.8.925

[19]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[20]

Mrinal K. Ghosh, Somnath Pradhan. A nonzero-sum risk-sensitive stochastic differential game in the orthant. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021025

 Impact Factor: 

Metrics

  • PDF downloads (28)
  • HTML views (25)
  • Cited by (0)

Other articles
by authors

[Back to Top]