Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions

Asish Ghoshal; Jean Honorio

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(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.

Related Material

@InProceedings{pmlr-v54-ghoshal17b, title = {{Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions}}, author = {Asish Ghoshal and Jean Honorio}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {1532--1540}, year = {2017}, editor = {Aarti Singh and Jerry Zhu}, volume = {54}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/ghoshal17b/ghoshal17b.pdf}, url = {http://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.} }

%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 %J Proceedings of Machine Learning Research %P 1532--1540 %U http://proceedings.mlr.press %V 54 %W PMLR %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.

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 PMLR 54:1532-1540