# Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions

arXiv: https://arxiv.org/abs/1703.01218 · HTML: https://mlsanity.com/paper/1703.01218/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2017.

## Built on by (most cited first, 1 of 1)

- [Learning to Infer Structures of Network Games](https://mlsanity.com/paper/2206.08119/) (2022)

## Abstract (arXiv)

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(k2 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.