Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions

2017/03/03 by Asish Ghoshal, Ghoshal, Asish, Jean Honorio +1
Computer Science · #Artificial Intelligence in Games #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.1703.01218

openalex publication_date 2017/03/03 · openalex created_date 2017/03/16 · openalex updated_date 2026/07/28

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² 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.

Related

• Provable Computational and Statistical Guarantees for Efficient Learning of Continuous-Action Graphical Games
• On Sparse Discretization for Graphical Games
• Computing Pure Nash Equilibria via Markov Random Fields
• Linear Game Theory : Reduction of complexity by decomposing large games into partial games
• Computational and Data Requirements for Learning Generic Properties of Simulation-Based Games