From Behavior to Sparse Graphical Games: Efficient Recovery of Equilibria
This provides a method for efficiently analyzing strategic interactions in graphical games, which is incremental as it builds on existing game theory frameworks with specific parametric assumptions.
The paper tackles the problem of exactly recovering pure-strategy Nash equilibria from noisy observations in sparse linear influence games, achieving this with a computationally and statistically efficient algorithm that requires sample complexity scaling as O(poly(k) log n).
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 $\ell_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 $\mathcal{O}(\mathrm{poly}(k) \log n)$. We also validate our theoretical results using synthetic experiments.