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.
@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
This site last compiled Tue, 24 Jul 2018 21:03:04 +0000