Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions

Asish Ghoshal, Jean Honorio
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1532-1540, 2017.

Abstract

In this paper we obtain sufficient and necessary conditions on the number of samples required for exact recovery of the pure-strategy Nash equilibria (PSNE) set of a graphical game from noisy observations of joint actions. We consider sparse linear influence games — a parametric class of graphical games with linear payoffs, and represented by directed graphs of n nodes (players) and in-degree of at most k. We show that one can efficiently recover the PSNE set of a linear influence game with O(k2logn) samples, under very general observation models. On the other hand, we show that Ω(k \log n) samples are necessary for any procedure to recover the PSNE set from observations of joint actions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-ghoshal17b, title = {{Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions}}, author = {Ghoshal, Asish and Honorio, Jean}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {1532--1540}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/ghoshal17b/ghoshal17b.pdf}, url = {https://proceedings.mlr.press/v54/ghoshal17b.html}, abstract = {In this paper we obtain sufficient and necessary conditions on the number of samples required for exact recovery of the pure-strategy Nash equilibria (PSNE) set of a graphical game from noisy observations of joint actions. We consider sparse linear influence games — a parametric class of graphical games with linear payoffs, and represented by directed graphs of n nodes (players) and in-degree of at most k. We show that one can efficiently recover the PSNE set of a linear influence game with $O(k^2 \log n)$ samples, under very general observation models. On the other hand, we show that $Ω(k \log n)$ samples are necessary for any procedure to recover the PSNE set from observations of joint actions.} }
Endnote
%0 Conference Paper %T Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions %A Asish Ghoshal %A Jean Honorio %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-ghoshal17b %I PMLR %P 1532--1540 %U https://proceedings.mlr.press/v54/ghoshal17b.html %V 54 %X In this paper we obtain sufficient and necessary conditions on the number of samples required for exact recovery of the pure-strategy Nash equilibria (PSNE) set of a graphical game from noisy observations of joint actions. We consider sparse linear influence games — a parametric class of graphical games with linear payoffs, and represented by directed graphs of n nodes (players) and in-degree of at most k. We show that one can efficiently recover the PSNE set of a linear influence game with $O(k^2 \log n)$ samples, under very general observation models. On the other hand, we show that $Ω(k \log n)$ samples are necessary for any procedure to recover the PSNE set from observations of joint actions.
APA
Ghoshal, A. & Honorio, J.. (2017). Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:1532-1540 Available from https://proceedings.mlr.press/v54/ghoshal17b.html.

Related Material