Stochastic dynamics and Edmonds’ algorithm

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.

Coauthored with William Sandholm.

Published in the Journal of Dynamics and Games (2022). Link to paper.

Attribution: Thumbnail image of the moon by Mark Tegethoff on Unsplash.