Learning Sparse Polymatrix Games in Polynomial Time and Sample Complexity
This work addresses the challenge of efficiently learning game structures in multi-agent systems, with potential applications in economics and AI, though it is incremental as it builds on existing regularization techniques for sparse recovery.
The paper tackles the problem of learning sparse polymatrix games from observed strategic interactions, showing that a polynomial-time method using ℓ1,2-group regularized logistic regression recovers a game with ε-Nash equilibria matching the true game in O(m^4 d^4 log(pd)) samples, and under stricter conditions, learns a game with exact Nash equilibria, while proving a lower bound of Ω(d log(pm)) samples for consistent recovery.
We consider the problem of learning sparse polymatrix games from observations of strategic interactions. We show that a polynomial time method based on $\ell_{1,2}$-group regularized logistic regression recovers a game, whose Nash equilibria are the $ε$-Nash equilibria of the game from which the data was generated (true game), in $\mathcal{O}(m^4 d^4 \log (pd))$ samples of strategy profiles --- where $m$ is the maximum number of pure strategies of a player, $p$ is the number of players, and $d$ is the maximum degree of the game graph. Under slightly more stringent separability conditions on the payoff matrices of the true game, we show that our method learns a game with the exact same Nash equilibria as the true game. We also show that $Ω(d \log (pm))$ samples are necessary for any method to consistently recover a game, with the same Nash-equilibria as the true game, from observations of strategic interactions. We verify our theoretical results through simulation experiments.