{"ID":6024117,"CreatedAt":"2026-07-08T01:00:23.257252134Z","UpdatedAt":"2026-07-09T19:11:46.74728655Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.05580","arxiv_id":"2607.05580","title":"Dynamics and Convergences for Markov Coevolutionary Opinion Formation Games in Dynamic Social Networks","abstract":"While deterministic variants of the coevolutionary opinion formation games such as the K-Nearest Neighbor (K-NN) game, e.g., in Bhawalkar et al., in a dynamic social network can sometimes be shown to stabilize using potential functions or localized smoothness arguments, introducing stochasticity fundamentally changes the mathematical landscape. In the \"K-NN Markov game\", network topologies evolve via a time-varying, randomized selection process. Proving whether such a system, as a special case of general-sum Markov games, converges to an equilibrium is a profoundly non-obvious and challenging theoretical question. Multiagent reinforcement learning has been shown to derive Nash (minimax) equilibria in two-player zero-sum Markov games and Markov potential games (along with some price-of-anarchy types of results). In recent work, optimistic dynamics are shown to converge to correlated equilibria in general-sum Markov games while the price-of-anarchy bounds are unknown. We thus analyze playing specific no-regret algorithms in general-sum Markov games for convergence to a stricter set than correlated equilibria. We integrate the convergence analysis techniques from multi-agent reinforcement learning in works of Wei et al. and online learning in a recent work of Anagnostides et al.. Specifically in (general-sum) Markov games, since the regret of the optimistic gradient ascent algorithm would have extra positive terms coming from Q-values, taking care of these terms requires non-trivial extra work setting an appropriate range of our learning rate and deriving the threshold on the number of iterations for convergence or a bounded price of anarchy, significantly different from those in the assumption in a main technical theorem of Anagnostides et al.. We analyze a weaker sense of convergences to approximate Nash equilibria by playing optimistic gradient ascents in general-sum Markov games.","short_abstract":"While deterministic variants of the coevolutionary opinion formation games such as the K-Nearest Neighbor (K-NN) game, e.g., in Bhawalkar et al., in a dynamic social network can sometimes be shown to stabilize using potential functions or localized smoothness arguments, introducing stochasticity fundamentally changes t...","url_abs":"https://arxiv.org/abs/2607.05580","url_pdf":"https://arxiv.org/pdf/2607.05580v1","authors":"[\"Po-An Chen\",\"Chi-Jen Lu\",\"Chuang-Chieh Lin\",\"Jim Shi\",\"Chih-Chieh Hung\"]","published":"2026-07-06T19:26:02Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[\"Reinforcement Learning\"]","has_code":false}