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

We consider the problem of learning sparse polymatrix games from observationsof strategic interactions. We show that a polynomial time method based on$\ell_{1,2}$-group regularized logistic regression recovers a game, whose Nashequilibria are the $\epsilon$-Nash equilibria of the game from which the datawas generated (true game), in $\mathcal{O}(m^4 d^4 \log (pd))$ samples ofstrategy profiles --- where $m$ is the maximum number of pure strategies of aplayer, $p$ is the number of players, and $d$ is the maximum degree of the gamegraph. Under slightly more stringent separability conditions on the payoffmatrices of the true game, we show that our method learns a game with the exactsame Nash equilibria as the true game. We also show that $\Omega(d \log (pm))$samples are necessary for any method to consistently recover a game, with thesame Nash-equilibria as the true game, from observations of strategicinteractions. We verify our theoretical results through simulation experiments.

Learning Sparse Polymatrix Games in Polynomial Time and Sample Complexity