Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions
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^2 \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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the Sample Complexity of Learning Graphical Games
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 numbe…
Characterization of equilibrium existence and purification in general Bayesian games
This paper studies Bayesian games with general action spaces, correlated types and interdependent payoffs. We introduce the condition of ``decomposable coarser payoff-relevant information'', and show that this condition …
Learning the Structure and Parameters of Large-Population Graphical Games from Behavioral Data
We consider learning, from strictly behavioral data, the structure and parameters of linear influence games (LIGs), a class of parametric graphical games introduced by Irfan and Ortiz (2014). LIGs facilitate causal strat…
A Characterization of Reny's Weakly Sequentially Rational Equilibrium through $\varepsilon$-Perfect $γ$-Weakly Sequentially Rational Equilibrium
A weakening of sequential rationality of sequential equilibrium yields Reny's (1992) weakly sequentially rational equilibrium (WSRE) in extensive-form games. WSRE requires Kreps and Wilson's (1982) consistent assessment …
FormFrom Behavior to Sparse Graphical Games: Efficient Recovery of Equilibria
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 …