Learning the Structure and Parameters of Large-Population Graphical Games from Behavioral Data

摘要

We consider learning, from strictly behavioral data, thestructure and parameters of linear influence games(LIGs), a class of parametric graphical games introduced byIrfan and Ortiz (2014). LIGs facilitate causal strategicinference (CSI): Making inferences from causal interventionson stable behavior in strategic settings. Applications includethe identification of the most influential individuals in large(social) networks. Such tasks can also support policy-makinganalysis. Motivated by the computational work on LIGs, we castthe learning problem as maximum-likelihood estimation (MLE) of agenerative model defined by pure-strategy Nash equilibria(PSNE). Our simple formulation uncovers the fundamentalinterplay between goodness-of-fit and model complexity: goodmodels capture equilibrium behavior within the data whilecontrolling the true number of equilibria, including thoseunobserved. We provide a generalization bound establishing thesample complexity for MLE in our framework. We propose severalalgorithms including convex loss minimization (CLM) andsigmoidal approximations. We prove that the number of exact PSNEin LIGs is small, with high probability; thus, CLM is sound. Weillustrate our approach on synthetic data and real-world U.S.congressional voting records. We briefly discuss our learningframework's generality and potential applicability to generalgraphical games. color="gray">