Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions
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 $\Omega(k \log n)$ samples are necessary for any procedure to recover the PSNE set from observations of joint actions.
Cite
Text
Ghoshal and Honorio. "Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions." International Conference on Artificial Intelligence and Statistics, 2017.Markdown
[Ghoshal and Honorio. "Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions." International Conference on Artificial Intelligence and Statistics, 2017.](https://mlanthology.org/aistats/2017/ghoshal2017aistats-learning/)BibTeX
@inproceedings{ghoshal2017aistats-learning,
title = {{Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions}},
author = {Ghoshal, Asish and Honorio, Jean},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2017},
pages = {1532-1540},
url = {https://mlanthology.org/aistats/2017/ghoshal2017aistats-learning/}
}