Article Contents
Article Contents

# Stochastic dynamics and Edmonds' algorithm

• *Corresponding author: Jonathan Newton
• 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.

Mathematics Subject Classification: Primary: 60J10, 05C85; Secondary: 60G52, 91A22.

 Citation:

• 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] 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. Arieli, Y. Babichenko, R. 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. Kandori, G. 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.

Figures(4)