English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The works of (Daskalakis et al., 2009, 2022; Jin et al., 2022; Deng et al.,2023) indicate that computing Nash equilibria in multi-player Markov games is acomputationally hard task. This fact raises the question of whether or notcomputational intractability can be circumvented if one focuses on specificclasses of Markov games. One such example is two-player zero-sum Markov games,in which efficient ways to compute a Nash equilibrium are known. Inspired byzero-sum polymatrix normal-form games (Cai et al., 2016), we define a class ofzero-sum multi-agent Markov games in which there are only pairwise interactionsdescribed by a graph that changes per state. For this class of Markov games, weshow that an $\epsilon$-approximate Nash equilibrium can be found efficiently.To do so, we generalize the techniques of (Cai et al., 2016), by showing thatthe set of coarse-correlated equilibria collapses to the set of Nashequilibria. Afterwards, it is possible to use any algorithm in the literaturethat computes approximate coarse-correlated equilibria Markovian policies toget an approximate Nash equilibrium.

Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria