In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming ``$\mathsf{ETH}$ for $\mathsf{PPAD}$", we show that, for every fixed discount factor, there is no polynomial-time algorithm for computing inverse-polynomially accurate coarse correlated equilibria in discounted general-sum Markov games when players learn independently in decentralized settings. Complementing this hardness result, we provide what appears to be the first \emph{radically uncoupled} algorithm with sub-exponential convergence guarantees to coarse correlated equilibria in discounted general-sum Markov games without imposing any structural restrictions on the game. Our algorithm is a \emph{layered} variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting. Finally, we develop both full-feedback and partial feedback versions of the aforementioned algorithm and establish sub-exponential convergence guarantees for each case.
Asrin Efe Yorulmaz, Uğur Aydın, Tamer Başar· 0 citations
Classical opinion dynamics typically assume a fixed mapping from private opinions to public signals, such as linear exchange, saturated signaling, or discrete public actions. In this paper, we show that these communication mappings can be derived from a strategic communication game played on a weighted influence network. Each agent acts as a receiver estimating its neighbors'states and as a sender broadcasting a public signal to influence its audience. We prove that the network's effect on a sender is summarized by a scalar, network-induced exaggeration factor, and the network game decouples into independent scalar cheap talk problems. The communication rules then emerge as behavioral regimes of one model: aligned incentives recover linear averaging; persuasive senders facing naive receivers produce saturated signaling; and persuasive senders facing Bayesian receivers cannot credibly reveal their opinions, so equilibrium communication becomes an interval quantizer, providing a game-theoretic foundation for continuous-opinion discrete-action (CODA) dynamics. Embedded in repeated opinion updates, the resulting strategic-CODA dynamics preserve opinion clustering and exclude extremism. The model predicts that a speaker exaggerates more when their audience is less influenced by them, and that under strong exaggeration, credible public expression collapses to a binary stance even while private opinions remain continuous.
Hassan Munif, Anthony Couthures, V. Varma et al.· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
