{
  "id": "1703.01218",
  "version": "v1",
  "published": "2017-03-03T15:55:16.000Z",
  "updated": "2017-03-03T15:55:16.000Z",
  "title": "Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions",
  "authors": [
    "Asish Ghoshal",
    "Jean Honorio"
  ],
  "comment": "Accepted to AISTATS 2017, Florida. arXiv admin note: substantial text overlap with arXiv:1607.02959",
  "categories": [
    "cs.LG"
  ],
  "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^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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-03-03T15:55:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "necessary conditions",
      "learning graphical games",
      "behavioral data",
      "sufficient",
      "joint actions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}