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 and 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.

[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.

[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.

[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.

[5]

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

[6]

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

[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.

[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.

[9]

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

[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.

[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.

[12]

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

[13]

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

[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.

[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.

[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.

[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.

[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.

[19]

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

[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.

[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.

[22]

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

[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.

[24]

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

[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.

[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.

[27]

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

[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.

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

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

[31]

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

[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.

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.

[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.

[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.

[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.

[5]

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

[6]

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

[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.

[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.

[9]

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

[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.

[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.

[12]

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

[13]

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

[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.

[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.

[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.

[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.

[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.

[19]

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

[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.

[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.

[22]

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

[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.

[24]

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

[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.

[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.

[27]

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

[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.

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

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

[31]

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

[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.

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 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 and 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 and 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 and 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 and 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 and 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 and 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 and Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051

[8]

Michel Benaïm, Antoine Bourquin, Dang H. Nguyen. Stochastic persistence in degenerate stochastic Lotka-Volterra food chains. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022023

[9]

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

[10]

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 and Continuous Dynamical Systems - B, 2021, 26 (12) : 6131-6154. doi: 10.3934/dcdsb.2021010

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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 and Management Optimization, 2019, 15 (3) : 1085-1100. doi: 10.3934/jimo.2018086

[17]

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

[18]

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

[19]

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

[20]

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

 Impact Factor: 

Metrics

  • PDF downloads (252)
  • HTML views (209)
  • Cited by (0)

Other articles
by authors

[Back to Top]