Learning Sparse Polymatrix Games in Polynomial Time and Sample Complexity

Asish Ghoshal, Jean Honorio
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1486-1494, 2018.

Abstract

We consider the problem of learning sparse polymatrix games from observations of strategic interactions. We show that a polynomial time method based on ℓ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 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-ghoshal18b, title = {Learning Sparse Polymatrix Games in Polynomial Time and Sample Complexity}, author = {Ghoshal, Asish and Honorio, Jean}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1486--1494}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/ghoshal18b/ghoshal18b.pdf}, url = {https://proceedings.mlr.press/v84/ghoshal18b.html}, abstract = {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 $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.} }
Endnote
%0 Conference Paper %T Learning Sparse Polymatrix Games in Polynomial Time and Sample Complexity %A Asish Ghoshal %A Jean Honorio %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-ghoshal18b %I PMLR %P 1486--1494 %U https://proceedings.mlr.press/v84/ghoshal18b.html %V 84 %X 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 $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.
APA
Ghoshal, A. & Honorio, J.. (2018). Learning Sparse Polymatrix Games in Polynomial Time and Sample Complexity. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1486-1494 Available from https://proceedings.mlr.press/v84/ghoshal18b.html.

Related Material