From behavior to sparse graphical games: Efficient recovery of equilibria
- 13 February 2017
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
- p. 1220-1227
- https://doi.org/10.1109/allerton.2016.7852374
Abstract
In this paper we study the problem of exact recovery of the pure-strategy Nash equilibria (PSNE) set of a graphical game from noisy observations of joint actions of the players alone. 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 present an ℓ1-regularized logistic regression based algorithm for recovering the PSNE set exactly, that is both computationally efficient — i.e. runs in polynomial time — and statistically efficient — i.e. has logarithmic sample complexity. Specifically, we show that the sufficient number of samples required for exact PSNE recovery scales as O(poly(k) log n). We also validate our theoretical results using synthetic experiments.Keywords
Other Versions
This publication has 6 references indexed in Scilit:
- On influence, stable behavior, and the most influential individuals in networks: A game-theoretic approachArtificial Intelligence, 2014
- User-Friendly Tail Bounds for Sums of Random MatricesFoundations of Computational Mathematics, 2011
- Local and global price of anarchy of graphical gamesTheoretical Computer Science, 2011
- High-dimensional Ising model selection using ℓ1-regularized logistic regressionThe Annals of Statistics, 2010
- A Continuation Method for Nash Equilibria in Structured GamesJournal of Artificial Intelligence Research, 2006
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963