On the sample complexity of learning graphical games
- 1 October 2017
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
Abstract
We analyze the sample complexity of learning graphical games from purely behavioral data. We assume that we can only observe the players' joint actions and not their payoffs. We analyze the sufficient and necessary number of samples for the correct recovery of the set of pure-strategy Nash equilibria (PSNE) of the true game. Our analysis focuses on directed graphs with n nodes and at most k parents per node. Sparse graphs correspond to k ϵ O(1) with respect to n, while dense graphs correspond to k ϵ O(n). By using VC dimension arguments, we show that if the number of samples is greater than O(kn log 2 n) for sparse graphs or O(n 2 log n) for dense graphs, then maximum likelihood estimation correctly recovers the PSNE with high probability. By using information-theoretic arguments, we show that if the number of samples is less than Q(kn log 2 n) for sparse graphs or Q(n 2 log n) for dense graphs, then any conceivable method fails to recover the PSNE with arbitrary probability.Keywords
Other Versions
This publication has 10 references indexed in Scilit:
- From behavior to sparse graphical games: Efficient recovery of equilibriaPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2017
- On influence, stable behavior, and the most influential individuals in networks: A game-theoretic approachArtificial Intelligence, 2014
- Polynomial-time computation of exact correlated equilibrium in compact gamesPublished by Association for Computing Machinery (ACM) ,2011
- Local and global price of anarchy of graphical gamesTheoretical Computer Science, 2011
- The complexity of computing a Nash equilibriumCommunications of the ACM, 2009
- Computing correlated equilibria in multi-player gamesJournal of the ACM, 2008
- Correlated equilibria in graphical gamesPublished by Association for Computing Machinery (ACM) ,2003
- Assouad, Fano, and Le CamPublished by Springer Science and Business Media LLC ,1997
- Subjectivity and correlation in randomized strategiesJournal of Mathematical Economics, 1974
- Non-Cooperative GamesAnnals of Mathematics, 1951